Summed Area Table
Encyclopedia
A summed area table 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 mipmap
s but wasn't widely used in the computer vision community until its prominent use in the Viola–Jones object detection framework twenty years later.
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:
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
The method can be also extended to high dimensional images. If the corners of the rectangle are
with 
in 
, then the sum of image values contained in the rectagle are computed with the formula
where
is the integral image at 
and 
the image dimension. The notation 
correspond in the example to 
, 
, 
, 
and 
. In neuroimaging
, for example, the images have dimension
or 
, when using voxels
or voxels with time-stamp.
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
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 mipmap
Mipmap
In 3D computer graphics texture filtering, MIP maps are pre-calculated, optimized collections of images that accompany a main texture, intended to increase rendering speed and reduce aliasing artifacts. They are widely used in 3D computer games, flight simulators and other 3D imaging systems. The...
s but wasn't widely used in the computer vision community until its prominent use in the Viola–Jones 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:
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:
Extensions
This method is naturally extended to continuous domains .The method can be also extended to high dimensional images. If the corners of the rectangle are
with in , then the sum of image values contained in the rectagle are computed with the formula
where
is the integral image at and the image dimension. The notation correspond in the example to , , , and . In neuroimagingNeuroimaging
Neuroimaging includes the use of various techniques to either directly or indirectly image the structure, function/pharmacology of the brain...
, for example, the images have dimension
or , when using voxelsVoxel
A voxel is a volume element, representing a value on a regular grid in three dimensional space. This is analogous to a pixel, which represents 2D image data in a bitmap...
or voxels with time-stamp.