Summed-area table

As the name suggests, the value at any point (x, y) in the summed-area table is the sum of all the pixels above and to the left of (x, y), inclusive:{{cite conference

| first = Franklin

| last = Crow

| title = Summed-area tables for texture mapping

| book-title = SIGGRAPH '84: Proceedings of the 11th annual conference on Computer graphics and interactive techniques

| pages = 207–212

| year = 1984

| doi = 10.1145/800031.808600

| url = https://dl.acm.org/doi/pdf/10.1145/800031.808600 | url-access = subscription

}}

{{cite conference

| first = Paul

| last = Viola

|author2=Jones, Michael

| title = Robust Real-time Object Detection

| book-title = International Journal of Computer Vision

| year = 2002

| url = http://www.hpl.hp.com/techreports/Compaq-DEC/CRL-2001-1.pdf }}

$$I(x,y)\; =\; \backslash sum\_\{\backslash begin\{smallmatrix\}\; x\text{'}\; \backslash le\; x\; \backslash \backslash \; y\text{'}\; \backslash le\; y\backslash end\{smallmatrix\}\}\; i(x\text{'},y\text{'})$$

where $i(x,y)$ is the value of the pixel at (x,y).

The summed-area table can be computed efficiently in a single pass over the image, as the value in the summed-area table at (x, y) is just:{{cite web | last1=BADGERATI | title=Computer Vision – The Integral Image | url=https://computersciencesource.wordpress.com/2010/09/03/computer-vision-the-integral-image/ | website=computersciencesource.wordpress.com | access-date=2017-02-13|date=2010-09-03}}

$$I(x,y)\; =\; i(x,y)\; +\; I(x,y-1)\; +\; I(x-1,y)\; -\; I(x-1,y-1)$$ (Noted that the summed matrix is calculated from top left corner)

File:Summed area table.png

Once the summed-area table has been computed, evaluating the sum of intensities over any rectangular area requires exactly four array references regardless of the area size. That is, the notation in the figure at right, having {{math|1=A = (x₀, y₀)}}, {{math|1=B = (x₁, y₀)}}, {{math|1=C = (x₀, y₁)}} and {{math|1=D = (x₁, y₁)}}, the sum of {{math|i(x,y)}} over the rectangle spanned by A, B, C, and D is:

This method is naturally extended to continuous domains.

The method can be also extended to high-dimensional images.{{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 | pages=197–201 | doi=10.1016/j.patrec.2010.10.007|bibcode=2011PaReL..32..197T }} If the corners of the rectangle are $x^p$ with $p$ in $\backslash \{0,1\backslash \}^d$, then the sum of image values contained in the rectangle are computed with the formula

$$\backslash sum\_\{p\backslash in\backslash \{0,1\backslash \}^d\; \}(-1)^\{d-\backslash |p\backslash |\_1\}\; I(x^p)$$

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

This method has been extended to high-order integral image as in the work of Phan et al.{{cite book| last1=Phan|first1=Thien| last2=Sohoni|first2=Sohum| last3=Larson|first3=Eric C.| last4=Chandler|first4=Damon M.|title=2012 IEEE Southwest Symposium on Image Analysis and Interpretation |chapter=Performance-analysis-based acceleration of image quality assessment | date=22 April 2012| pages=81–84| doi=10.1109/SSIAI.2012.6202458|hdl=11244/25701 | url=http://vision.okstate.edu/pubs/ssiai_tp_1.pdf| isbn=978-1-4673-1830-3| citeseerx=10.1.1.666.4791|s2cid=12472935 }} who provided two, three, or four integral images for quickly and efficiently calculating the standard deviation (variance), skewness, and kurtosis of local block in the image. This is detailed below:

To compute variance or standard deviation of a block, we need two integral images:

$$I(x,y)\; =\; \backslash sum\_\{\backslash begin\{smallmatrix\}\; x\text{'}\; \backslash le\; x\; \backslash \backslash \; y\text{'}\; \backslash le\; y\backslash end\{smallmatrix\}\}\; i(x\text{'},y\text{'})$$

$$I^2(x,y)\; =\; \backslash sum\_\{\backslash begin\{smallmatrix\}\; x\text{'}\; \backslash le\; x\; \backslash \backslash \; y\text{'}\; \backslash le\; y\backslash end\{smallmatrix\}\}\; i^2(x\text{'},y\text{'})$$

The variance is given by:

$$\backslash operatorname\{Var\}(X)\; =\; \backslash frac\{1\}\{n\}\; \backslash sum\_\{i=1\}^n\; (x\_i\; -\; \backslash mu)^2.$$

Let $S\_1$ and $S\_2$ denote the summations of block $ABCD$ of $I$ and $I^2$, respectively. $S\_1$ and $S\_2$ are computed quickly by integral image. Now, we manipulate the variance equation as:

$$\backslash begin\{align\}$$

\operatorname{Var}(X)

&= \frac{1}{n} \sum_{i=1}^n \left(x_i^2 - 2 \mu x_i + \mu^2\right) \\[1ex]

&= \frac{1}{n} \left[\sum_{i=1}^n x_i^2 - 2 \sum_{i=1}^n \mu x_i + \sum_{i=1}^n \mu^2\right] \\[1ex]

&= \frac{1}{n} \left[\sum_{i=1}^n x_i^2 - 2\sum_{i=1}^n \mu x_i + n \mu^2\right] \\[1ex]

&= \frac{1}{n} \left[\sum_{i=1}^n x_i^2 - 2 \mu \sum_{i=1}^n x_i + n \mu^2\right] \\[1ex]

&= \frac{1}{n} \left[S_2 - 2 \frac{S_1}{n} S_1 + n \left(\frac{S_1}{n}\right)^2\right] \\[1ex]

&= \frac{1}{n} \left[S_2 - \frac{S_1^2}{n}\right]

\end{align}

Where $\backslash mu=S\_1/n$ and $S\_2\; =\; \backslash sum\_\{i=1\}^n\; x\_i^2$.

Similar to the estimation of the mean ($\backslash mu$) and variance ($\backslash operatorname\{Var\}$), which requires the integral images of the first and second power of the image respectively (i.e. $I,\; I^2$); manipulations similar to the ones mentioned above can be made to the third and fourth powers of the images (i.e. $I^3(x,y),\; I^4(x,y)$.) for obtaining the skewness and kurtosis.

But one important implementation detail that must be kept in mind for the above methods, as mentioned by F Shafait et al.{{cite journal| last1=Shafait|first1=Faisal| last2=Keysers|first2=Daniel| last3=M. Breuel|first3=Thomas|editor-first1=Berrin A. |editor-first2=Kathrin |editor-last1=Yanikoglu |editor-last2=Berkner | title=Efficient implementation of local adaptive thresholding techniques using integral images| journal=Electronic Imaging| volume=6815| pages=681510–681510–6| date=January 2008| doi=10.1117/12.767755| url=http://www.csse.uwa.edu.au/~shafait/papers/Shafait-efficient-binarization-SPIE08.pdf| series=Document Recognition and Retrieval XV |bibcode=2008SPIE.6815E..10S | citeseerx=10.1.1.109.2748|s2cid=9284084 }} is that of integer overflow occurring for the higher order integral images in case 32-bit integers are used.

The data type for the sums may need to be different from and larger than the data type used for the original values, in order to accommodate the largest expected sum without overflow. For floating-point data, error can be reduced using compensated summation.

• Prefix sum

• [http://www.codeproject.com/Articles/441226/Haar-feature-Object-Detection-in-Csharp Summed table implementation in object detection]

• [https://www.youtube.com/watch?v=mM5JY-Q6hiM An introduction to the theory behind the integral image algorithm]
• [https://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