Re: Computing a neighborhood window efficiently

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

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