Summed Area Table

A Summed Area Table (also known as an Integral Image) is an algorithm for quickly and efficiently generating the sum of values in a rectangular subset of a grid. It was first introduced to the computer graphics world in 1984 for use in mipmaps but wasn't widely used in the computer vision community until its prominent use in the Viola and Jones robust real-time object detection framework twenty years later.

The Algorithm

As the name suggests, the value at any point $(x,y)$ in the summed area table is just the sum of all the pixels above and to the left of $(x,y)$, inclusive: [cite conference
first = Franklin
last = Crow
authorlink =
coauthors =
title = Summed-area tables for texture mapping
booktitle = SIGGRAPH '84: Proceedings of the 11th annual conference on Computer graphics and interactive techniques
pages = 207-212
year = 1984
url = http://www.soe.ucsc.edu/classes/cmps160/Fall05/papers/p207-crow.pdf ] [cite conference
first = Paul
last = Viola
authorlink =
coauthors = Jones, Michael
title = Robust Real-time Object Detection
booktitle = International Journal of Computer Vision
pages =
year = 2002
url = http://research.microsoft.com/~viola/Pubs/Detect/violaJones_IJCV.pdf ] $sat(x,y)\; =\; sum\_\{x\text{'}\; le\; x,y\text{'}\; le\; y\}\; i(x\text{'},y\text{'})$

Moreover, the summed area table can be computed efficiently in a single pass over the image, using the fact that the value in the summed area table at $(x,y)$ is just:

$sat(x,y)\; =\; sat(x-1,y)\; +\; sum\_\{x\text{'}\; le\; x\}\; i(x\text{'},y)$

Once the summed area table has been computed, the task of evaluating any rectangle can be accomplished in constant time with just four array references. Specifically, using the notation in the figure at right, the value is just:

$sum\_\{A(x)\; le\; x\text{'}\; le\; B(x),\; A(y)\; le\; y\text{'}\; le\; D(y)\}\; i(x\text{'},y\text{'})\; =\; sat(A)\; +\; sat(C)\; -\; sat(B)\; -\; sat(D)$

References