About sortings errors in MaximumFinder.java

[José]

I am taking a look to the MaximumFinder implementation in ImageJ 148t
(source code available in http://pastebin.com/wRrZqXiE ) trying to
understand the function analyzeAndMarkMaxima(), and I have some questions
about it:

- How is the value of maxSortingError computed? (line 392) Could you
explain that computation?

- Why is the condition in the if in line 569  "v2 > v0 + maxSortingError"?
Could it be "v2 > v0"?

- Is it possible for sorting errors to happen in ByteProcessor?

Thanks.

José Díaz de Greñu

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

[Michael Schmid]

Hi José,

this really goes into the details of the MaximumFinder...

The MaximumFinder starts be sorting the maxima by descending value. For speed, this is done with 64-bit integers with the value encoded in the 32 most significant bits and the x, y coordinates encoded in the least significant bits.
The reason for the "maxSortingError" is that sorting the maxima is done with 32-bit integer accuracy. This might be insufficient for floating point images in some cases, so one has to care about cases where maxima with equal 32-bit values have actually different pixel values.

For ByteProcessors and ShortProcessors, the maxSortingError is set to zero in
 public ByteProcessor findMaxima(ip, tolerance, threshold, outputType, excludeOnEdges, isEDM)

Having maxSortingError=0 for byte&short data should be fine unless there is a very strange pixel value calibration, where the difference between two pixel values is well below 10^-9 of the total range of pixels (Find Maxima uses calibrated pixel values).


Michael
________________________________________________________________
On Aug 2, 2014, at 19:21, José wrote:

> I am taking a look to the MaximumFinder implementation in ImageJ 148t
> (source code available in http://pastebin.com/wRrZqXiE ) trying to
> understand the function analyzeAndMarkMaxima(), and I have some questions
> about it:
>
> - How is the value of maxSortingError computed? (line 392) Could you
> explain that computation?
>
> - Why is the condition in the if in line 569  "v2 > v0 + maxSortingError"?
> Could it be "v2 > v0"?
>
> - Is it possible for sorting errors to happen in ByteProcessor?
>
> Thanks.
>
> José Díaz de Greñu
>
> --
> ImageJ mailing list: http://imagej.nih.gov/ij/list.html

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

[José]

Thanks for your answer,

I keep looking at the source code and other questions arise:

- Could you explain why the threshold is bringed down in line 381?
( threshold -= (globalMax-globalMin)*1e-6; )

- Also, could you explain why the maxSortingError is computing according to
the formula in line 392?
( maxSortingError = 1.1f * (isEDM ? SQRT2/2f : (globalMax-globalMin)/2e9f);
)

Thanks again.
José




2014-08-04 12:35 GMT+02:00 Michael Schmid <[hidden email]>:

> Hi José,
>
> this really goes into the details of the MaximumFinder...
>
> The MaximumFinder starts be sorting the maxima by descending value. For
> speed, this is done with 64-bit integers with the value encoded in the 32
> most significant bits and the x, y coordinates encoded in the least
> significant bits.
> The reason for the "maxSortingError" is that sorting the maxima is done
> with 32-bit integer accuracy. This might be insufficient for floating point
> images in some cases, so one has to care about cases where maxima with
> equal 32-bit values have actually different pixel values.
>
> For ByteProcessors and ShortProcessors, the maxSortingError is set to zero
> in
>  public ByteProcessor findMaxima(ip, tolerance, threshold, outputType,
> excludeOnEdges, isEDM)
>
> Having maxSortingError=0 for byte&short data should be fine unless there
> is a very strange pixel value calibration, where the difference between two
> pixel values is well below 10^-9 of the total range of pixels (Find Maxima
> uses calibrated pixel values).
>
>
> Michael
> ________________________________________________________________
> On Aug 2, 2014, at 19:21, José wrote:
>
> > I am taking a look to the MaximumFinder implementation in ImageJ 148t
> > (source code available in http://pastebin.com/wRrZqXiE ) trying to
> > understand the function analyzeAndMarkMaxima(), and I have some questions
> > about it:
> >
> > - How is the value of maxSortingError computed? (line 392) Could you
> > explain that computation?
> >
> > - Why is the condition in the if in line 569  "v2 > v0 +
> maxSortingError"?
> > Could it be "v2 > v0"?
> >
> > - Is it possible for sorting errors to happen in ByteProcessor?
> >
> > Thanks.
> >
> > José Díaz de Greñu
> >
> > --
> > ImageJ mailing list: http://imagej.nih.gov/ij/list.html
>
> --
> ImageJ mailing list: http://imagej.nih.gov/ij/list.html
>

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

[Michael Schmid]

Hi Jose,

the answer to your first question is the comment in the code:
The threshold is reduced to avoid rounding errors (caused by the finite
numeric accuracy). As far as I see, rounding errors could occur only in
the make8bit method, so in principle it would be better to do it there.
A relative error of 1e-6 is a (rather conservative) estimate of the
accuracy of floats.

Concerning maxSortingError, when converting to 32-bit integers, the whole
data range between globalMax and globalMin is mapped to an integer range
of 2e9. The maximum rounding error for the difference between two values
is therefore (globalMax-globalMin)/2e9f.
For Euclidian distance maps (isEDM=true), there is a special correction,
which can change the value by up to sqrt(2)/2. But that's another story...

Michael
_____________________________________________________________________


On Tue, August 5, 2014 22:17, José  wrote:

> Thanks for your answer,
>
> I keep looking at the source code and other questions arise:
>
> - Could you explain why the threshold is bringed down in line 381?
> ( threshold -= (globalMax-globalMin)*1e-6; )
>
> - Also, could you explain why the maxSortingError is computing according
> to
> the formula in line 392?
> ( maxSortingError = 1.1f * (isEDM ? SQRT2/2f :
> (globalMax-globalMin)/2e9f);
> )
>
> Thanks again.
> José
>
>
>
>
> 2014-08-04 12:35 GMT+02:00 Michael Schmid <[hidden email]>:
>
>> Hi José,
>>
>> this really goes into the details of the MaximumFinder...
>>
>> The MaximumFinder starts be sorting the maxima by descending value. For
>> speed, this is done with 64-bit integers with the value encoded in the
>> 32
>> most significant bits and the x, y coordinates encoded in the least
>> significant bits.
>> The reason for the "maxSortingError" is that sorting the maxima is done
>> with 32-bit integer accuracy. This might be insufficient for floating
>> point
>> images in some cases, so one has to care about cases where maxima with
>> equal 32-bit values have actually different pixel values.
>>
>> For ByteProcessors and ShortProcessors, the maxSortingError is set to
>> zero
>> in
>>  public ByteProcessor findMaxima(ip, tolerance, threshold, outputType,
>> excludeOnEdges, isEDM)
>>
>> Having maxSortingError=0 for byte&short data should be fine unless there
>> is a very strange pixel value calibration, where the difference between
>> two
>> pixel values is well below 10^-9 of the total range of pixels (Find
>> Maxima
>> uses calibrated pixel values).
>>
>>
>> Michael
>> ________________________________________________________________
>> On Aug 2, 2014, at 19:21, José wrote:
>>
>> > I am taking a look to the MaximumFinder implementation in ImageJ 148t
>> > (source code available in http://pastebin.com/wRrZqXiE ) trying to
>> > understand the function analyzeAndMarkMaxima(), and I have some
>> questions
>> > about it:
>> >
>> > - How is the value of maxSortingError computed? (line 392) Could you
>> > explain that computation?
>> >
>> > - Why is the condition in the if in line 569  "v2 > v0 +
>> maxSortingError"?
>> > Could it be "v2 > v0"?
>> >
>> > - Is it possible for sorting errors to happen in ByteProcessor?
>> >
>> > Thanks.
>> >
>> > José Díaz de Greñu
>> >
>> > --
>> > ImageJ mailing list: http://imagej.nih.gov/ij/list.html
>>
>> --
>> ImageJ mailing list: http://imagej.nih.gov/ij/list.html
>>
>
> --
> ImageJ mailing list: http://imagej.nih.gov/ij/list.html
>

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