What are Integral Images and how does it speed up processing in SURF?

Hi, I'm doing some undergraduate research, and I have been recently reading about the image processing algorithms SIFT and SURF.

I think I've read enough to understand how SIFT works and when it is preferable to use. However, I'm stuck on SURF. I've read that it being "3 times faster than SIFT" is attributed to the use of Integral Images.

From what I understand, an integral image is a summed area table, which is just a very efficient way of calculating the sum of values in a rectangular section of a grid (only 4 calculations).

This is where I am stuck. I have read over Herbert Bay's paper on SURF, and I can't figure out ,specifically, how this integral images algorithm is applied to the SURF algorithm, and what makes it so fast.

Maybe I have just been looking at it too long, or it's just out of my league. In either case I was hoping that someone else would be able to share their knowledge with me.

Thanks in advance for any help,

CJ

Answer 1

[Anand]

I can give this a try. Look at Fig. 1 in the paper. For SURF, you convolve your image with the filters on the right (3rd and 4th) instead of the filters on the left (1st and 2nd).

In order to evaluate the result of convolving a pixel with the 3rd filter without integral images would involve performing something like (14 + 14 + 14 + 2) 44 additions and 15 multiplications. This was obtained as follows:

1. 15 multiplications to multiply the pixels in the middle black region by -2.

2. 14 additions each to add all pixels in the upper white region, middle black region and lower white regions.

3. 2 additions to add the result of additions in the 3 regions.

If instead you use integral images, you only need 5 additions/subtractions and 1 multiplication.

1. 1 subtraction for each of the 3 regions (lower right pixel of integral image at that region minus upper left pixel of integral image at that region).

2. 1 multiplication to multiply the result for the middle region by -2.

3. 2 additions to add the result of additions in the 3 regions.

A picture would have been a lot easier.

Hope this was understandable.