Summed Area Table
Encyclopedia
A summed area table is an algorithm
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 (xy) in the summed area table is just the sum of all the pixels above and to the left of (xy), 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 (xy) 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

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 neuroimaging
Neuroimaging
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 voxels
Voxel
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.

Video Lectures

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK