How is integral image used in image processing?

Hi,

With integral image, the task of calculating the area of an upright rectangular region is reduced to four operations. Thus, the computation time is invariant to size of the rectangular. HOWEVER the result of the four operation is the SUM of pixel (of integral image) within the rectangular region. SO HOW is the SUM used for object detection?

My understanding (correct me if i'm wrong)

Let say i have an image with 100*100 pixels. So the resultant integral image will be 100*100 pixels as well. The used of integral image is because its computational time of any rectangle region is almost constant(invariant to size). So let say i have an object of interest in the image, the object is in a 50*50 pixels window. So the calculate of the sum of pixel within the window is constant time even if the window size increase. >>>after this point i'm stuck. How is value of the sum of pixel within a rectangular window useful?

Thanks

[Sean de Wolski]

It sounds like you're talking about something involving a convolution. I'm not sure what though. Please show an image and/or explain the goal.

[Walter Roberson]

The calculation of the area of a rectangle is not invariant with the size of the rectangle: instead it is proportionate to the log of the maximum dimension of the rectangle. Make the rectangle size a few quadrillion digits long and you aren't going to be calculating the area in constant time.

[Kyle]

Viola–Jones object detection framework and SURF uses integral image to speed up the processing time. But i cant figure out how they improve the time by using integral image.

[Walter Roberson]

Technical note: "integral image" is defined at http://en.wikipedia.org/wiki/Summed_area_table

Answer 1

[David Young]

Here's a simplified example, that relates to the (more complex) ways that SURF uses integral images.

Suppose you want to estimate the x-gradient of an image at a particular position and scale. A high-quality (in some sense) result is given by summing the pixelwise product of the image with the x-derivative of a Gaussian mask, but maybe this is too expensive.

Instead, you might make a fast approximation by summing the pixels in a rectangular region to the left of the point of interest, doing the same for a region to the right, and then taking the difference between the two sums. The size of the region sets the scale at which you're estimating the gradient. In MATLAB, something like this:

% set xpos and ypos to be position of interest, s to be 
% half the size of region of interest (scale parameter)
lregion = Image(ypos-s:ypos+s, xpos-s:xpos-1);
rregion = Image(ypos-s:ypos+s, xpos+1:xpos+s);
lmean = mean(lregion(:));
rmean = mean(rregion(:));
xgradient = (rmean - lmean) / s;

Now suppose you want to speed it up further. Clearly, the integral image can be used to do that, since most of the computation just makes the sums of the pixels in rectangular regions.

Lots of computations can use variants of this approach: Haar and Walsh transforms are important examples.

[Kyle]

In convolution, the filter(kernel) multiple with the pixel it is overlapping. Then the sum of the multiplication is the new value for the convolved image.(at the center of the kernel)

So if my filter is the approximation of x-derivative of a Gaussian mask (where part of the mask is weighted uniformly ), when convolve this filter with integral image. I'll have the advantage of getting the sum of convolution faster. (use integral image get the sum of area where the filter overlap then multiple with the uniform weighted filter).

If Integral image is used in this way for speed. Then if i would to use the normal Gaussian mask (not the approximation), i could not use the integral image to find the sum of an area then multiple with the kernel as there are no uniform part of in the kernel.

Am i in the correct direction?

Image of the gaussian kernel and its approximation on the right

<http://www.google.com.my/imgres?q=second+order+gaussian+kernel&hl=en&client=firefox-a&rls=org.mozilla:en-US:official&channel=np&biw=1366&bih=624&tbm=isch&tbnid=7ybuoWmle9IS8M:&imgrefurl=http://www.nowpublishers.com/product.aspx%3Fproduct%3DCGV%26doi%3D0600000017%26section%3Dx1-113r2&docid=QYOrnyHReS6z4M&w=513&h=87&ei=T1tWTv2LE9CJrAfB2eXBCg&zoom=1&iact=hc&vpx=453&vpy=187&dur=66&hovh=69&hovw=410&tx=236&ty=55&page=4&tbnh=35&tbnw=208&start=55&ndsp=18&ved=1t:429,r:2,s:55>

[Walter Roberson]

Shortcut to the image alone:

http://www.nowpublishers.com/10.1561%5CCGV06%5C0600000017%5CCGV01743x.gif

[David Young]

Yes, I think your comment is correct: the integral image is only helpful if your mask is largely composed of uniform rectangular areas.