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 |
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 |
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 |
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 |
In reply to this post by Kenneth Sloan-3
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 |
In reply to this post by Gabriel Landini
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 VarianceResult_Orig.tif (701K) Download Attachment VarianceResult_Base.tif (701K) Download Attachment |
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 |
> 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 |
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 |
Free forum by Nabble | Edit this page |