Re: Computing a neighborhood window efficiently

Posted by Stephan Saalfeld on
URL: http://imagej.273.s1.nabble.com/Computing-a-neighborhood-window-efficiently-tp3685960p3685970.html

Hi,

getting the sum or mean of arbitrarily large rectangles can be
accelerated by preprocessing the image into an integral image:

http://en.wikipedia.org/wiki/Summed_area_table

That way, accessing the sum is constant in time, namely 4 add
operations:

I(x_max,y_max) + I(x_min,y_min) - I(x_min,y_max) - I(x_max,y_min)

Note that you have to make sure that this will get you quite large
numbers which requires storing them in a larger type (e.g. summing up
bytes into byte wouldn't work, you would have to go for short, int or
long).  No insertion or replacement required, that is you can use []
instead of Collections which, in Java, is almost always faster and
allows you to not use Objects but basic types that do not acquire space
in the heap.

Do that first and later check how to optimize the code.

Good luck,
Stephan


On Sun, 2011-01-16 at 03:36 -0800, 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!
> Here is a link to the question I posted on StackOverflow (it shows the code
> for the algorithm optimization).
> http://stackoverflow.com/questions/4699396/java-code-optimization-on-matrix-windowing-computes-in-more-time
> http://stackoverflow.com/questions/4699396/java-code-optimization-on-matrix-windowing-computes-in-more-time 
> Is there another way to compute that? What am I doing wrong in Java ?(in C++
> it is optimized)
>