Posted by
dscho on
Jan 16, 2011; 12:55pm
URL: http://imagej.273.s1.nabble.com/Computing-a-neighborhood-window-efficiently-tp3685960p3685961.html
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 :-)