Re: Computing a neighborhood window efficiently

Posted by Stephan Saalfeld on Jan 16, 2011; 2:11pm
URL: http://imagej.273.s1.nabble.com/Computing-a-neighborhood-window-efficiently-tp3685960p3685967.html

Hi Johannes and all,

ah---sorry for repeating your reply---haven't read it before posting...

Note that the given example suffers from writing the sums of many many
floats into float.  That might be o.k. for images of average size but
could generate problems due to float having limited accuracy for larger
numbers than for smaller ones.  This may not only affect the accuracy of
the sum itself but can accumulate errors during summing up.  Adding a
very small B to a very large A may result in A.  One would have to
carefully check if, in a specific situation, the results are fine.

To prevent error accumulation during summing up, I once wrote a helper
class:

http://pacific.mpi-cbg.de/cgi-bin/gitweb.cgi?p=mpicbg.git;a=blob;f=mpicbg/util/RealSum.java

which stores intermediate sums and always adds up sums of equally sized
sets of numbers.  By that, it reduces the effect of the accumulated
mistakes.

Best,
Stephan



On Sun, 2011-01-16 at 13:55 +0100, Johannes Schindelin wrote:

> Hi,
>
> On Sun, 16 Jan 2011, Serafino wrote:
>
> > I'm trying to implement a version of the Spatial Fuzzy C-Means as a
> > plugin for image segmentation. I need to calculate a spatial function
> > over a neighborhood window for each pixel of an image and this step
> > slows thing down a bit if I simply implement the windowing as in the
> > mean shift filter (ie by simply cycling through each each and creating a
> > window ex nihilo). I thought up some optimizations, but doing them in
> > Java leads to worse results than the unoptimized one!
>
> In Java, creating a lot of objects or indirection leads to suboptimal
> results.
>
> For example, using a 1-dimensional array instead of a 2-dimensional one
> helps.
>
> For example, using a fixed-size array always beats using a collection.
>
> For example, using int instead of Integer accelerates the code. Note that
> this is not possible with Java Collections; your int would always be boxed
> into Integer instances.
>
> In general, there are quite a few pitfalls for C++ programmers who think
> they can program Java just the same way. Have a look at
> http://pacific.mpi-cbg.de/wiki/index.php/Tips_for_C%2B%2B_developers for
> a list of common mistakes (not including your problems, though).
>
> You specific question, how sums of rectangular[*1*] neighborhoods can be
> calculated efficiently, has a totally different answer, though: construct
> a second matrix S containing the sum of the rectangles between the upper
> left corner and the current coordinate. Then, the sum of arbitrary
> rectangles (x1 - x2, y1 - y2) can be calculated as
>
> S(x1, y1) + S(x2, y2) - S(x1, y2) - S(x2, y1)
>
> A sketch using ImageJ's API for 32-bit images:
>
> int w = image.getWidth(), h = image.getHeight();
> float[] pixels = (float[])image.getProcessor().getPixels();
> float[] sum = new int[w * h];
>
> sum[0] = pixels[0];
> for (int i = 1; i < w; i++)
> sum[i] = sum[i - 1] + pixels[i];
> for (int j = 1; j < h; j++) {
> sum[j * w] = sum[(j - 1) * w] + pixels[j * w];
> for (int i = 1; i < w; i++)
> sum[j * w + i] = sum[(j - 1) * w + i]
> + pixels[j * w + i - 1] + pixels[j * w + i];
> }
>
> Note: I wrote this in the mail client, so it is not even compile-tested.
>
> Note2: there might be another 1% performance gain from using
> for (int j = w; j < w * h; j += w)
> together with the obvious changes in the rest of the code.
>
> Note3: the performance of this algorithm does not depend on the size of
> the neighborhood, but the memory complexity is larger than your
> solutions'.
>
> Ciao,
> Johannes
>
> Footnote *1*: you almost mislead me by using the term "radius" suggesting
> circular neighborhoods :-)