Summed-area table

A summed-area table is a data structure and algorithm for quickly summing the values in any rectangular part of a grid, and in image processing it is also called an integral image. Each cell of the table holds the sum of all values above and to the left of it, inclusive, and the whole table can be built in a single pass over the image. Once built, the sum over any rectangle needs exactly four array references, whatever the size of the rectangle. Frank Crow introduced it to computer graphics in 1984 for use with mipmaps, and it was popularized in computer vision by Lewis and then named the integral image and used prominently in the Viola-Jones object detection framework in 2001. The idea extends to higher dimensions and to higher powers of the image, which allows quick local variance, skewness and kurtosis, and an implementation may need a larger data type for the sums to avoid overflow.