193.178.155.99 at 12:11, 13 October 2009

2009-10-13T12:11:28Z

New page

A '''summed area table''' (also known as an '''integral image''') is a [[data structure]] and [[algorithm]] for quickly and efficiently generating the sum of values in a rectangular subset of a grid. It was first introduced to [[computer graphics]] in 1984 by [[Franklin C. Crow|Frank Crow]] for use with [[mipmap]]s. In [[computer vision]], it was first prominently used within the [[Viola–Jones object detection framework]] in 2002. However, historically, this principle is very well known in the study of multi-dimensional probability distribution functions, namely in computing 2D (or ND) probabilities (area under the probability distribution) from the respective [[cumulative distribution function]]s.<ref>{{cite conference
| first = Amir
| last = Finkelstein
| authorlink =
| coauthors =
| title = Double Integrals By Summing Values Of Cumulative Distribution Function
| booktitle = Wolfram Demonstration Project
| pages =
| year = 2010
| url = http://demonstrations.wolfram.com/DoubleIntegralsBySummingValuesOfACumulativeDistributionFunct/ }}
</ref>

==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:<ref>{{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 }}
</ref><ref>{{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://www.hpl.hp.com/techreports/Compaq-DEC/CRL-2001-1.pdf }}
</ref>

: <math> I(x,y) = \sum_{\begin{smallmatrix} x' \le x \\ y' \le y\end{smallmatrix}} i(x',y')</math>

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:

: <math> I(x,y) = i(x,y) + I(x-1,y) + I(x,y-1) - I(x-1,y-1)\,</math>
[[Image:Prm VJ fig3 computeRectangleWithAlpha.png|thumb|right|Finding the sum of a rectangular area]]

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, having A=(x0, y1), B=(x1, y1), C=(x1, y0) and D=(x0, y0), the sum of <math>i(x,y)</math> over the rectangle spanned by A, B,C and D is just

: <math>\sum_{\begin{smallmatrix} x0 \le x \le x1 \\ y0 \le y \le y1 \end{smallmatrix}} i(x,y) = I(C) + I(A) - I(B) - I(D).</math>

==Extensions==
This method is naturally extended to continuous domains.<ref>{{cite conference
| first = Amir
| last = Finkelstein
| authorlink =
| coauthors = neeratsharma
| title = Double Integrals By Summing Values Of Cumulative Distribution Function
| booktitle = Wolfram Demonstration Project
| pages =
| year = 2010
| url = http://demonstrations.wolfram.com/DoubleIntegralsBySummingValuesOfACumulativeDistributionFunct/ }}
</ref>

The method can be also extended to high dimensional images.<ref>{{cite journal|last=Tapia|first=Ernesto|title=A note on the computation of high-dimensional integral images|journal=Pattern Recognition Letters|date=January 2011|volume=32|issue=2|doi=10.1016/j.patrec.2010.10.007}}</ref> If the corners of the rectangle are <math>x^p</math> with <math>p</math> in <math>\{0,1\}^d</math>, then the sum of image values contained in the rectangle are computed with the formula

: <math> \sum_{p\in\{0,1\}^d }(-1)^{d-\|p\|_1} I(x^p) \,</math>

where <math>I(x)</math> is the integral image at <math>x</math> and <math>d</math> the image dimension. The notation <math>x^p</math> correspond in the example to <math>d=2</math>, <math>A=x^{(0,0)}</math>, <math>B=x^{(1,0)}</math>, <math>C=x^{(1,1)}</math> and <math>D=x^{(0,1)}</math>. In [[neuroimaging]], for example, the images have dimension <math>d=3</math> or <math>d=4</math>, when using [[voxel]]s or voxels with time-stamp.

==References==

<references/>

==External links==

; Lecture videos:
* [http://www.youtube.com/watch?v=mM5JY-Q6hiM An introduction to the theory behind the integral image algorithm]
* [http://www.youtube.com/watch?v=-SI117NdjJ8 A demonstration to a continuous version of the integral image algorithm, from the Wolfram Demonstrations Project]

[[Category:Digital geometry]]
[[Category:Computer graphics data structures]]

Category:Singular integrals - Revision history

193.178.155.99 at 12:11, 13 October 2009