Summed area table

An integral image is used for rapid calculation of pixel sums within rectangular cutouts of images. The term is derived from the concept of discrete integration.

Origin

The method is based on the concept of Summed Area Tables which was developed in 1984 for the texture mapping. Paul Viola and Michael Jones used the method in 2001 for the first time for the image processing on.

Definition

At each point of the integral image is the sum of all pixels inside the rectangle between the current point and the origin of the image. In the point (x, y) is therefore the sum of the pixels within the rectangle of the points (0,0), (x, 0), ( 0, y ) and (x, y) is spanned.

The integral image can be effectively calculated in one pass, since the sum over for a pixel is always from the previous sum of the previous line plus the new pixels of the current line.

To calculate the sum of pixels of an arbitrary area of the original image that must be accessed to only 4 points in the integral image.

Example

The pixel sum of the area D in the adjacent figure is calculated according to

The great advantage of this method is that, regardless of the size of the area used to calculate the pixel sums of the original image, only one value of 4 pixel values ​​of the integral image must be always calculated.

Video lectures

• A theory behind the integral image algorithm