Re: Computing a neighborhood window efficiently

Posted by Stephan Saalfeld on Jan 17, 2011; 3:38am
URL: http://imagej.273.s1.nabble.com/Computing-a-neighborhood-window-efficiently-tp3685960p3685964.html

Hi,

infected by the discussion on integral images I wrote a small plugin
that demonstrates the speed gain with an interactive mean-smooth.  With
an image open, call the plugin `Integral Smooth' and click and drag with
the mouse in the image canvas to change the size of the smooth-kernel.
ENTER leaves the smoothed image, ESC cancels.

http://fly.mpi-cbg.de/saalfeld/download/integral_smooth.jar

The jar contains both binaries and sources.

Best,
Stephan




On Mon, 2011-01-17 at 00:55 +0100, Stephan Saalfeld wrote:

> Hi,
>
> > [...]
> > Concerning the integral image I guess that the formula to compute the sum
> > vector shall be:
> > int[] sum = new int[w * h];
> >
> > sum[0] = mat[0];
> > for (int i = 1; i < w; i++)
> > sum[i] = sum[i - 1] + mat[i];
> > for (int j = 1; j < h; j++)
> >         {
> >             sum[j * w] = sum[(j - 1) * w] + mat[j * w];
> >             for (int i = 1; i < w; i++)
> > sum[j * w + i] = sum[(j - 1) * w + i] + sum[j * w + i - 1] +
> >                        mat[j * w + i] - sum[(j - 1) * w + i -1];
> > }
> > am I wrong?
>
> No---looks correct.  I would just save a few operations and array
> accesses and, probably, put it into a long:
>
> long[] sum = new long[w * h];
> int s = 0;
> for (int i = 0; i < w; ++i) {
> s += mat[i]
> sum[i] = s;
> }
> for (int j = 1; j < h; ++j)
> {
> int jw = j * w;
> sum[jw] = sum[jw - w] + mat[jw];
> for (int i = 1; i < w; ++i) {
> int jwi = jw + i;
> sum[jwi] =
> sum[jwi - w] + sum[jwi - 1] +
> mat[jwi] - sum[jwi - w - 1];
> }
>
> Best,
> Stephan