Find maxima .. algorithm discription

classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

Find maxima .. algorithm discription

HPatel
Is there a document that details the "Find Maxima" algorithm by Michael Schmid?

Thanks,
HPatel
Reply | Threaded
Open this post in threaded view
|

Re: Find maxima .. algorithm discription

Michael Schmid-3
Hi,

sorry, there is no publication on it (at least none that I am aware of,
probably I have reinvented the wheel), but it is rather simple code:
(1) Find the local maxima
(2) Sort them in descending sequence
(3) For each local maximum, do a flood fill algorithm with the gray level
tolerance (without modifying the original, it is done on a temporary
scratch image). Maxima where flood filling reaches a previously filled
area (i.e., area of other maximum within the tolerance) are discarded.
(4) In case of 'single points' output, if there are several points having
the highest value inside the flood-filled area, use the one that is
closest to their geometric center.

Segmentation is a bit more difficult (it stems from older ImageJ
versions), and I am currently about to see whether it can't be done faster
and with better accuracy...

Michael
_____________________________________________________________________


On Wed, December 9, 2009 22:00, HPatel wrote:
> Is there a document that details the "Find Maxima" algorithm by Michael
> Schmid?
>
> Thanks,
> HPatel
Reply | Threaded
Open this post in threaded view
|

Re: Find maxima .. algorithm discription

HPatel
Michael,

Thanks for this.
Do you know if someone has converted this to C++ or C?

Thanks,
Hitesh


Michael Schmid-3 wrote
Hi,

sorry, there is no publication on it (at least none that I am aware of,
probably I have reinvented the wheel), but it is rather simple code:
(1) Find the local maxima
(2) Sort them in descending sequence
(3) For each local maximum, do a flood fill algorithm with the gray level
tolerance (without modifying the original, it is done on a temporary
scratch image). Maxima where flood filling reaches a previously filled
area (i.e., area of other maximum within the tolerance) are discarded.
(4) In case of 'single points' output, if there are several points having
the highest value inside the flood-filled area, use the one that is
closest to their geometric center.

Segmentation is a bit more difficult (it stems from older ImageJ
versions), and I am currently about to see whether it can't be done faster
and with better accuracy...

Michael
_____________________________________________________________________


On Wed, December 9, 2009 22:00, HPatel wrote:
> Is there a document that details the "Find Maxima" algorithm by Michael
> Schmid?
>
> Thanks,
> HPatel
Reply | Threaded
Open this post in threaded view
|

Re: Find maxima .. algorithm discription

Michael Schmid-3
Hi Hitesh,

no sorry, no idea about a C or C++ code like this. But it should be  
straightforward...

Michael
________________________________________________________________

On 11 Dec 2009, at 20:58, HPatel wrote:

> Michael,
>
> Thanks for this.
> Do you know if someone has converted this to C++ or C?
>
> Thanks,
> Hitesh
>
>
>
> Michael Schmid-3 wrote:
>>
>> Hi,
>>
>> sorry, there is no publication on it (at least none that I am  
>> aware of,
>> probably I have reinvented the wheel), but it is rather simple code:
>> (1) Find the local maxima
>> (2) Sort them in descending sequence
>> (3) For each local maximum, do a flood fill algorithm with the  
>> gray level
>> tolerance (without modifying the original, it is done on a temporary
>> scratch image). Maxima where flood filling reaches a previously  
>> filled
>> area (i.e., area of other maximum within the tolerance) are  
>> discarded.
>> (4) In case of 'single points' output, if there are several points  
>> having
>> the highest value inside the flood-filled area, use the one that is
>> closest to their geometric center.
>>
>> Segmentation is a bit more difficult (it stems from older ImageJ
>> versions), and I am currently about to see whether it can't be  
>> done faster
>> and with better accuracy...
>>
>> Michael
>> _____________________________________________________________________
>>
>>
>> On Wed, December 9, 2009 22:00, HPatel wrote:
>>> Is there a document that details the "Find Maxima" algorithm by  
>>> Michael
>>> Schmid?
>>>
>>> Thanks,
>>> HPatel
>>
>>
>
> --
> View this message in context: http://n2.nabble.com/Find-maxima- 
> algorithm-discription-tp4141919p4153412.html
> Sent from the ImageJ mailing list archive at Nabble.com.
Reply | Threaded
Open this post in threaded view
|

Re: Find maxima .. algorithm discription

Ayman
In reply to this post by Michael Schmid-3
<quote author="Michael Schmid-3">
Hi,

sorry, there is no publication on it (at least none that I am aware of,
probably I have reinvented the wheel), but it is rather simple code:
(1) Find the local maxima
(2) Sort them in descending sequence
(3) For each local maximum, do a flood fill algorithm with the gray...

Dear Michael,

I have a followup question about this algorithm. In the ImageJ documentation for "Find Maxima,"  it is stated "Maxima are ignored if they do not stand out from the surroundings by more than [the noise tolerance]." I would have expected that this means that there must be a nonzero number of pixels contiguous with a maximum that exceed the threshold, defined as the maximum minus the noise tolerance.

However, when I used the "Maxima within tolerance" option for the output of "Find Maxima", which the documentation suggests should return all contiguous pixels around the maximum that exceed this threshold, it returned numerous maxima with just one point. This seems inconsistent with my interpretation of how the noise tolerance is used to reject maxima that do not stand out from their surroundings.

Could you clarify how the noise tolerance is used to decide which maxima are ignored?
Reply | Threaded
Open this post in threaded view
|

Re: Find maxima .. algorithm discription

Ayman
In reply to this post by Michael Schmid-3
<quote author="Michael Schmid-3">
Hi,

sorry, there is no publication on it (at least none that I am aware of,
probably I have reinvented the wheel), but it is rather simple code:
(1) Find the local maxima
(2) Sort them in descending sequence
(3) For each local maximum, do a flood fill algorithm with the gray...

Dear Michael,

I have a followup question about this algorithm. In the ImageJ documentation for "Find Maxima,"  it is stated "Maxima are ignored if they do not stand out from the surroundings by more than [the noise tolerance]." I would have expected that this means that there must be a nonzero number of pixels contiguous with a maximum that exceed the threshold, defined as the maximum minus the noise tolerance.

However, when I used the "Maxima within tolerance" option for the output of "Find Maxima", which the documentation suggests should return all contiguous pixels around the maximum that exceed this threshold, it returned numerous maxima with just one point. This seems inconsistent with my interpretation of how the noise tolerance is used to reject maxima that do not stand out from their surroundings.

Could you clarify how the noise tolerance is used to decide which maxima are ignored?
Reply | Threaded
Open this post in threaded view
|

Re: Find maxima .. algorithm discription

Michael Schmid-3
Hi Ayman,


maybe an example is best:

Say, you have a maximum of pixel value 100 and the tolerance is 10.

If the maximum is a single pixel surrounded by pixels with a value  
less than 100-10=90, then 'Maximum within tolerance' will give you  
that pixel only.

If it has a neighbor of, say, pixel value 95, and everything around  
this is below 90, 'Maximum within tolerance' gives you these two  
pixels, the one with 100 and with 95.

If there are three adjacent pixels in a row, with values 100, 91 and  
98, everything else below 90, they will be considered a single  
maximum and you will see all three pixels in 'Maximum within tolerance'.

If the three pixels in a row are 100, 89, 95, again everything else  
below 90, only the '100' will be considered 'Maximum within  
tolerance', because the 89 is below the tolerance limit. The 95 is  
not separated from the next maximum (the '100') by a value less than  
95-10=85, so it is not considered a maximum.

If the three pixels are 100, 84, 95, everything around them not  
higher than 84, you get two maxima, each one pixel large: the '100'  
and the '95'.


Michael
________________________________________________________________

On 6 Jul 2011, at 23:12, Ayman wrote:

> Hi,
>
> sorry, there is no publication on it (at least none that I am aware  
> of,
> probably I have reinvented the wheel), but it is rather simple code:
> (1) Find the local maxima
> (2) Sort them in descending sequence
> (3) For each local maximum, do a flood fill algorithm with the gray...
>
> Dear Michael,
>
> I have a followup question about this algorithm. In the ImageJ  
> documentation
> for "Find Maxima,"  it is stated "Maxima are ignored if they do not  
> stand
> out from the surroundings by more than [the noise tolerance]." I  
> would have
> expected that this means that there must be a nonzero number of pixels
> contiguous with a maximum that exceed the threshold, defined as the  
> maximum
> minus the noise tolerance.
>
> However, when I used the "Maxima within tolerance" option for the  
> output of
> "Find Maxima", which the documentation suggests should return all  
> contiguous
> pixels around the maximum that exceed this threshold, it returned  
> numerous
> maxima with just one point. This seems inconsistent with my  
> interpretation
> of how the noise tolerance is used to reject maxima that do not  
> stand out
> from their surroundings.
>
> Could you clarify how the noise tolerance is used to decide which  
> maxima are
> ignored?
>
> --
> View this message in context: http://imagej.588099.n2.nabble.com/ 
> Find-maxima-algorithm-discription-tp4141919p6556029.html
> Sent from the ImageJ mailing list archive at Nabble.com.
Reply | Threaded
Open this post in threaded view
|

Re: Find maxima .. algorithm discription

Ayman
Dear Michael,

I searched the source code archive in ImageJ's developer resources and was unable to find the source code for "Find Maxima". Do you know where this code might be available? I ask because there are many different algorithms for flood filling and I'd like to incorporate the one that "Find Maxima" uses. Alternatively, would you be able to provide the source code?

Ayman

<quote author="Michael Schmid-3">
Hi Ayman,


maybe an example is best:

Say, you have a maximum of pixel value 100 and the tolerance is 10.

If the maximum is a single pixel surrounded by pixels with a value  
less than 100-10=90, then 'Maximum within tolerance' will give you  
that pixel only.

If it has a neighbor of, say, pixel value 95, and everything around  
this is below 90, 'Maximum within tolerance' gives you these two  
pixels, the one with 100 and with 95.

If there are three adjacent pixels in a row, with values 100, 91 and  
98, everything else below 90, they will be considered a single  
maximum and you will see all three pixels in 'Maximum within tolerance'.

Reply | Threaded
Open this post in threaded view
|

Re: Find maxima .. algorithm discription

Jan Eglinger-3
Hi Ayman,

On 14.07.2011 6:53 PM, Ayman wrote:
> I searched the source code archive in ImageJ's developer resources and was
> unable to find the source code for "Find Maxima". Do you know where this
> code might be available? I ask because there are many different algorithms
> for flood filling and I'd like to incorporate the one that "Find Maxima"
> uses. Alternatively, would you be able to provide the source code?

When you start "Plugins > Utilities > Find Commands..." or just press
[L], and then type your command of interest "Find Maxima" with "Show
full information" checked, you will see that the command resides in

Find Maxima... (in Process) [ij.plugin.filter.MaximumFinder]

You can find the source code for example on Fiji's git repository:

http://fiji.sc/cgi-bin/gitweb.cgi?p=imagej.git;a=blob;f=ij/plugin/filter/MaximumFinder.java

Hope that helps,
Jan
Reply | Threaded
Open this post in threaded view
|

Re: Find maxima .. algorithm discription

Nonbee
In reply to this post by Michael Schmid-3
Hi!
Could you tell me about the algorithm for finding the local maxima.
I don't know (1) Find the local maxima .

Thanks.
Reply | Threaded
Open this post in threaded view
|

Re: Find maxima .. algorithm discription

Michael Schmid-3
On Jul 16, 2015, at 09:47, Nonbee wrote:

> Hi!
> Could you tell me about the algorithm for finding the local maxima.
> I don't know (1) Find the local maxima .

The algorithm of the ImageJ 'Find Maxima' command has been discussed several times in the mailing list, see the archives.
  https://list.nih.gov/cgi-bin/wa.exe?REPORT&z=4&1=IMAGEJ&L=IMAGEJ

E.g. you will find these hits (these are long links; join the lines if the mailer should break them into more than one line):

https://list.nih.gov/cgi-bin/wa.exe?A2=ind1107&L=IMAGEJ&P=R3330&1=IMAGEJ&9=A&I=-3&J=on&d=No+Match%3BMatch%3BMatches&z=4

https://list.nih.gov/cgi-bin/wa.exe?A2=ind0912&L=IMAGEJ&P=R11737&1=IMAGEJ&9=A&I=-3&J=on&d=No+Match%3BMatch%3BMatches&z=4

There is also a description in the source code,
https://github.com/imagej/imagej1/blob/master/ij/plugin/filter/MaximumFinder.java

Michael

--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html