Integral image

An integral image is used to quickly calculate pixel sums within rectangular sections of images. The term is derived from the concept of discrete integration .

origin

The method is based on the concept of the summed area tables , which was developed for texture mapping and was first introduced by Franklin C. Crow in 1984. Paul Viola and Michael Jones first used the process for image processing in 2001.

definition

In each point of the integral image, there is the sum of all pixels within the rectangle between the current point and the origin of the image. The point (x, y) is the sum of the pixels within the rectangle that is spanned by the points (0,0), (x, 0), (0, y) and (x, y). ${\ displaystyle I _ {\ Sigma}}$

{\ displaystyle I _ {\ Sigma} (x, y) = \ sum _ {i = 0} ^ {i \ leq x} \ sum _ {j = 0} ^ {j \ leq y} I (i, j) }

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

In order to calculate the pixel sum of any area of the original image, only 4 points in the integral image have to be accessed.

example

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

{\ displaystyle I _ {\ Sigma} (\ mathrm {Fl {\ ddot {a}} che} _ {D}) = I _ {\ Sigma} (P_ {1}) + I _ {\ Sigma} (P_ {4} ) -I _ {\ Sigma} (P_ {2}) - I _ {\ Sigma} (P_ {3})}

The great advantage of this method is that, regardless of the size of the area, only one value from 4 pixel values of the integral image has to be calculated for the calculation of the pixel sums of the original image.

Video lectures

a theory behind the integral image algorithm

Individual evidence

[1] Franklin C. Crow: Summed-Area Tables for Texture Mapping, Computer Graphics, Volume 18, Number 3 July 1984

[2] Paul Viola, Michael Jones: Rapid Object Detection using Boosted Cascade of Simple Features