Variance-Filter

[Herbie]

Dear experts,

in the Java source code of the linear/nonlinear filter functions we find for
the Variance-Filter a comment telling us:

"Variance: sum of squares - square of sums"

As far as I know, it should read:

"Variance: sum of squares - n * mean^2"

(In both cases the normalization isn't included.)

Could somebody who knows the code better than I do, have a look at the
implementation?

Thanks

Herbie



--
Sent from: http://imagej.1557.x6.nabble.com/

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

[Gabriel Landini]

On Sunday, 21 January 2018 18:56:27 GMT you wrote:
> in the Java source code of the linear/nonlinear filter functions we find for
> the Variance-Filter a comment telling us:
>
> "Variance: sum of squares - square of sums"
>
> As far as I know, it should read:
> "Variance: sum of squares - n * mean^2"
> (In both cases the normalization isn't included.)

Hi Herbie,
I think that it might be the naive algorithm described in:

https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance
- - - -
 Let n ← 0, Sum ← 0, SumSq ← 0
 For each datum x:
       n ← n + 1
       Sum ← Sum + x
       SumSq ← SumSq + x × x
   Var = (SumSq − (Sum × Sum) / n) / (n − 1)
This algorithm can easily be adapted to compute the variance of a finite
population: simply divide by N instead of n − 1 on the last line.
- - - -

It seems to be the same as line 596 of the RanjFilters.java:

float value = (float)((sums[1] - sums[0]*sums[0]/kNPoints)/kNPoints);

Cheers

Gabriel

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

[Kenneth Sloan-2]

This "naïve algorithm" should be stamped out.  There is no real advantage over making two passes through the data.

It's the kind of things old farts like me used to revel in, back in the 1970's.  Now, the risks of numerical error far outweigh whatever "efficiency" gain might be there (and, it's not at all clear to me that there *is* an efficiency gain.

--
Kenneth Sloan
[hidden email]
Vision is the art of seeing what is invisible to others.

> On 21 Jan 2018, at 13:11 , Gabriel Landini <[hidden email]> wrote:
>
> On Sunday, 21 January 2018 18:56:27 GMT you wrote:
>> in the Java source code of the linear/nonlinear filter functions we find for
>> the Variance-Filter a comment telling us:
>>
>> "Variance: sum of squares - square of sums"
>>
>> As far as I know, it should read:
>> "Variance: sum of squares - n * mean^2"
>> (In both cases the normalization isn't included.)
>
> Hi Herbie,
> I think that it might be the naive algorithm described in:
>
> https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance
> - - - -
> Let n ← 0, Sum ← 0, SumSq ← 0
> For each datum x:
>       n ← n + 1
>       Sum ← Sum + x
>       SumSq ← SumSq + x × x
>   Var = (SumSq − (Sum × Sum) / n) / (n − 1)
> This algorithm can easily be adapted to compute the variance of a finite
> population: simply divide by N instead of n − 1 on the last line.
> - - - -
>
> It seems to be the same as line 596 of the RanjFilters.java:
>
> float value = (float)((sums[1] - sums[0]*sums[0]/kNPoints)/kNPoints);
>
> Cheers
>
> Gabriel
>
> --
> ImageJ mailing list: http://imagej.nih.gov/ij/list.html

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

[Michael Schmid]

Hi Kenneth and all,

yes, the built-in variance mechanism uses the 'Naïve algorithm'.
Nevertheless, I think the problem of numerical errors is not a real issue:
The image data have floating-point accuracy at best (approx 24 bits
accuracy), while the summation is done with double precision, having
more than twice the number of bits (approx 53 bits accuracy).

For radius >2, the algorithm also takes advantage of the fact that one
need not sum over all values each time, it does so only the first time
in each row. For further values, only the new values are added and those
not in the sum any more subtracted.
Again, this will introduce tiny numerical errors, but their impact is
small since everything is done with double-precision accuracy.


Michael
________________________________________________________________
On 21/01/2018 20:47, Kenneth Sloan wrote:

> This "naïve algorithm" should be stamped out.  There is no real advantage over making two passes through the data.
>
> It's the kind of things old farts like me used to revel in, back in the 1970's.  Now, the risks of numerical error far outweigh whatever "efficiency" gain might be there (and, it's not at all clear to me that there *is* an efficiency gain.
>
> --
> Kenneth Sloan
> [hidden email]
> Vision is the art of seeing what is invisible to others.
>
>
>
>
>
>> On 21 Jan 2018, at 13:11 , Gabriel Landini <[hidden email]> wrote:
>>
>> On Sunday, 21 January 2018 18:56:27 GMT you wrote:
>>> in the Java source code of the linear/nonlinear filter functions we find for
>>> the Variance-Filter a comment telling us:
>>>
>>> "Variance: sum of squares - square of sums"
>>>
>>> As far as I know, it should read:
>>> "Variance: sum of squares - n * mean^2"
>>> (In both cases the normalization isn't included.)
>>
>> Hi Herbie,
>> I think that it might be the naive algorithm described in:
>>
>> https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance
>> - - - -
>> Let n ← 0, Sum ← 0, SumSq ← 0
>> For each datum x:
>>        n ← n + 1
>>        Sum ← Sum + x
>>        SumSq ← SumSq + x × x
>>    Var = (SumSq − (Sum × Sum) / n) / (n − 1)
>> This algorithm can easily be adapted to compute the variance of a finite
>> population: simply divide by N instead of n − 1 on the last line.
>> - - - -
>>
>> It seems to be the same as line 596 of the RanjFilters.java:
>>
>> float value = (float)((sums[1] - sums[0]*sums[0]/kNPoints)/kNPoints);
>>
>> Cheers
>>
>> Gabriel
>>
>> --
>> 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

[Herbie]

Dear Kenneth,

agreed but it turns out that my problem is even more "surprising".

I shall post example images obtained from the 16bit image provided by David
Schaffer in his recent thread.

Best

Herbie



--
Sent from: http://imagej.1557.x6.nabble.com/

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

[Herbie]

Dear Gabriel,

thank you very much for your help, the macro (off-list), and the link
pointing me to the algorithm.

My supposition that the observed effect with the sample image provided
by David
Schaffer in his recent thread may be due to the possibly signed 16bit
format turned out to be wrong because "Signed_16-bit_to_Unsigned.js"
doesn't recognize this image as being signed 16bit.

Attached please find two results from David's sample image when applying
the "Variance Filter" with "Radius 1.5".

-- Result image "VarianceResult_Orig.tif" is directly obtained from
David's sample image that shows an effective gray value range from 32758
to 32867.

-- Result image "VarianceResult_Base.tif" is obtained from David's
sample image after subtraction of value 32758 that gives an effective
gray value range from 0 to 109.

Maybe someone can explain these results.
I must admit that I didn't expect it which in turn may be due to my
insufficient understanding of the nonlinear "Variance Filter".

Best

Herbie
Am 21.01.18 um 20:11 schrieb Gabriel Landini:

> On Sunday, 21 January 2018 18:56:27 GMT you wrote:
>> in the Java source code of the linear/nonlinear filter functions we find for
>> the Variance-Filter a comment telling us:
>>
>> "Variance: sum of squares - square of sums"
>>
>> As far as I know, it should read:
>> "Variance: sum of squares - n * mean^2"
>> (In both cases the normalization isn't included.)
>
> Hi Herbie,
> I think that it might be the naive algorithm described in:
>
> https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance
> - - - -
>   Let n ← 0, Sum ← 0, SumSq ← 0
>   For each datum x:
>         n ← n + 1
>         Sum ← Sum + x
>         SumSq ← SumSq + x × x
>     Var = (SumSq − (Sum × Sum) / n) / (n − 1)
> This algorithm can easily be adapted to compute the variance of a finite
> population: simply divide by N instead of n − 1 on the last line.
> - - - -
>
> It seems to be the same as line 596 of the RanjFilters.java:
>
> float value = (float)((sums[1] - sums[0]*sums[0]/kNPoints)/kNPoints);
>
> Cheers
>
> Gabriel
>
> --
> ImageJ mailing list: http://imagej.nih.gov/ij/list.html
>

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

[Michael Schmid]

Hi everyone,

sorry, there is a bug in the Variance filter, and it is my fault - it
does not use double precision for the multiplication (but it should).
I'll submit the fixed version to Wayne.

Again, sorry for all the trouble!

Michael
________________________________________________________________

On 22/01/2018 10:54, Herbie wrote:

> Dear Gabriel,
>
> thank you very much for your help, the macro (off-list), and the link
> pointing me to the algorithm.
>
> My supposition that the observed effect with the sample image provided
> by David
> Schaffer in his recent thread may be due to the possibly signed 16bit
> format turned out to be wrong because "Signed_16-bit_to_Unsigned.js"
> doesn't recognize this image as being signed 16bit.
>
> Attached please find two results from David's sample image when applying
> the "Variance Filter" with "Radius 1.5".
>
> -- Result image "VarianceResult_Orig.tif" is directly obtained from
> David's sample image that shows an effective gray value range from 32758
> to 32867.
>
> -- Result image "VarianceResult_Base.tif" is obtained from David's
> sample image after subtraction of value 32758 that gives an effective
> gray value range from 0 to 109.
>
> Maybe someone can explain these results.
> I must admit that I didn't expect it which in turn may be due to my
> insufficient understanding of the nonlinear "Variance Filter".
>
> Best
>
> Herbie
> Am 21.01.18 um 20:11 schrieb Gabriel Landini:
>> On Sunday, 21 January 2018 18:56:27 GMT you wrote:
>>> in the Java source code of the linear/nonlinear filter functions we
>>> find for
>>> the Variance-Filter a comment telling us:
>>>
>>> "Variance: sum of squares - square of sums"
>>>
>>> As far as I know, it should read:
>>> "Variance: sum of squares - n * mean^2"
>>> (In both cases the normalization isn't included.)
>>
>> Hi Herbie,
>> I think that it might be the naive algorithm described in:
>>
>> https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance
>> - - - -
>>   Let n ← 0, Sum ← 0, SumSq ← 0
>>   For each datum x:
>>         n ← n + 1
>>         Sum ← Sum + x
>>         SumSq ← SumSq + x × x
>>     Var = (SumSq − (Sum × Sum) / n) / (n − 1)
>> This algorithm can easily be adapted to compute the variance of a finite
>> population: simply divide by N instead of n − 1 on the last line.
>> - - - -
>>
>> It seems to be the same as line 596 of the RanjFilters.java:
>>
>> float value = (float)((sums[1] - sums[0]*sums[0]/kNPoints)/kNPoints);
>>
>> Cheers
>>
>> Gabriel
>>
>> --
>> 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

[Wayne Rasband-2]

> On Jan 22, 2018, at 7:37 AM, Michael Schmid <[hidden email]> wrote:
>
> Hi everyone,
>
> sorry, there is a bug in the Variance filter, and it is my fault - it does not use double precision for the multiplication (but it should). I'll submit the fixed version to Wayne.

Michael’s fix for this bug is in the latest ImageJ daily build (1.51u24).

-wayne

> Again, sorry for all the trouble!
>
> Michael
> ________________________________________________________________
>
> On 22/01/2018 10:54, Herbie wrote:
>> Dear Gabriel,
>> thank you very much for your help, the macro (off-list), and the link pointing me to the algorithm.
>> My supposition that the observed effect with the sample image provided by David
>> Schaffer in his recent thread may be due to the possibly signed 16bit format turned out to be wrong because "Signed_16-bit_to_Unsigned.js" doesn't recognize this image as being signed 16bit.
>> Attached please find two results from David's sample image when applying the "Variance Filter" with "Radius 1.5".
>> -- Result image "VarianceResult_Orig.tif" is directly obtained from David's sample image that shows an effective gray value range from 32758 to 32867.
>> -- Result image "VarianceResult_Base.tif" is obtained from David's sample image after subtraction of value 32758 that gives an effective gray value range from 0 to 109.
>> Maybe someone can explain these results.
>> I must admit that I didn't expect it which in turn may be due to my insufficient understanding of the nonlinear "Variance Filter".
>> Best
>> Herbie
>> Am 21.01.18 um 20:11 schrieb Gabriel Landini:
>>> On Sunday, 21 January 2018 18:56:27 GMT you wrote:
>>>> in the Java source code of the linear/nonlinear filter functions we find for
>>>> the Variance-Filter a comment telling us:
>>>>
>>>> "Variance: sum of squares - square of sums"
>>>>
>>>> As far as I know, it should read:
>>>> "Variance: sum of squares - n * mean^2"
>>>> (In both cases the normalization isn't included.)
>>>
>>> Hi Herbie,
>>> I think that it might be the naive algorithm described in:
>>>
>>> https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance
>>> - - - -
>>>   Let n ← 0, Sum ← 0, SumSq ← 0
>>>   For each datum x:
>>>         n ← n + 1
>>>         Sum ← Sum + x
>>>         SumSq ← SumSq + x × x
>>>     Var = (SumSq − (Sum × Sum) / n) / (n − 1)
>>> This algorithm can easily be adapted to compute the variance of a finite
>>> population: simply divide by N instead of n − 1 on the last line.
>>> - - - -
>>>
>>> It seems to be the same as line 596 of the RanjFilters.java:
>>>
>>> float value = (float)((sums[1] - sums[0]*sums[0]/kNPoints)/kNPoints);
>>>
>>> Cheers
>>>
>>> Gabriel

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

[Herbie]

Dear Wayne, dear Michael,

thanks for the as always prompt action!

No trouble here!
We all know that there are always glitches in software that remain
unrecognized for some time.

I'm really happy that it wasn't a false alarm from my side ...

The results from the mentioned sample image are now as expected and
identical.

Great

Herbie

:::::::::::::::::::::::::::::::::::::::::::
Am 22.01.18 um 20:34 schrieb Wayne Rasband:

>> On Jan 22, 2018, at 7:37 AM, Michael Schmid <[hidden email]> wrote:
>>
>> Hi everyone,
>>
>> sorry, there is a bug in the Variance filter, and it is my fault - it does not use double precision for the multiplication (but it should). I'll submit the fixed version to Wayne.
>
> Michael’s fix for this bug is in the latest ImageJ daily build (1.51u24).
>
> -wayne
>
>
>> Again, sorry for all the trouble!
>>
>> Michael
>> ________________________________________________________________
>>
>> On 22/01/2018 10:54, Herbie wrote:
>>> Dear Gabriel,
>>> thank you very much for your help, the macro (off-list), and the link pointing me to the algorithm.
>>> My supposition that the observed effect with the sample image provided by David
>>> Schaffer in his recent thread may be due to the possibly signed 16bit format turned out to be wrong because "Signed_16-bit_to_Unsigned.js" doesn't recognize this image as being signed 16bit.
>>> Attached please find two results from David's sample image when applying the "Variance Filter" with "Radius 1.5".
>>> -- Result image "VarianceResult_Orig.tif" is directly obtained from David's sample image that shows an effective gray value range from 32758 to 32867.
>>> -- Result image "VarianceResult_Base.tif" is obtained from David's sample image after subtraction of value 32758 that gives an effective gray value range from 0 to 109.
>>> Maybe someone can explain these results.
>>> I must admit that I didn't expect it which in turn may be due to my insufficient understanding of the nonlinear "Variance Filter".
>>> Best
>>> Herbie
>>> Am 21.01.18 um 20:11 schrieb Gabriel Landini:
>>>> On Sunday, 21 January 2018 18:56:27 GMT you wrote:
>>>>> in the Java source code of the linear/nonlinear filter functions we find for
>>>>> the Variance-Filter a comment telling us:
>>>>>
>>>>> "Variance: sum of squares - square of sums"
>>>>>
>>>>> As far as I know, it should read:
>>>>> "Variance: sum of squares - n * mean^2"
>>>>> (In both cases the normalization isn't included.)
>>>>
>>>> Hi Herbie,
>>>> I think that it might be the naive algorithm described in:
>>>>
>>>> https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance
>>>> - - - -
>>>>    Let n ← 0, Sum ← 0, SumSq ← 0
>>>>    For each datum x:
>>>>          n ← n + 1
>>>>          Sum ← Sum + x
>>>>          SumSq ← SumSq + x × x
>>>>      Var = (SumSq − (Sum × Sum) / n) / (n − 1)
>>>> This algorithm can easily be adapted to compute the variance of a finite
>>>> population: simply divide by N instead of n − 1 on the last line.
>>>> - - - -
>>>>
>>>> It seems to be the same as line 596 of the RanjFilters.java:
>>>>
>>>> float value = (float)((sums[1] - sums[0]*sums[0]/kNPoints)/kNPoints);
>>>>
>>>> Cheers
>>>>
>>>> Gabriel
>
> --
> ImageJ mailing list: http://imagej.nih.gov/ij/list.html
>

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