Summed area table

From Wikipedia, the free encyclopedia
Jump to: navigation, search

A summed area table is a data structure and algorithm for quickly and efficiently generating the sum of values in a rectangular subset of a grid. In the image processing domain, it is also known as an integral image. It was first introduced to computer graphics in 1984 by Frank Crow for use with mipmaps. In computer vision it was first prominently used within the Viola–Jones object detection framework in 2001. 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 functions.[1]

The algorithm[edit]

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:[2][3]

 I(x,y) = \sum_{\begin{smallmatrix} x' \le x \\ y' \le y\end{smallmatrix}} i(x',y')

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:

 I(x,y) = i(x,y) + I(x-1,y) + I(x,y-1) - I(x-1,y-1)\,
A description of computing a sum in the Summed Area Table data structure/algorithm

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

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

Extensions[edit]

  • This method is naturally extended to continuous domains.[1]
  • The method can be also extended to high-dimensional images.[4] If the corners of the rectangle are x^p with p in \{0,1\}^d, then the sum of image values contained in the rectangle are computed with the formula
 \sum_{p\in\{0,1\}^d }(-1)^{d-\|p\|_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 time-stamp.

  • This method has been extended to high-order integral image. In,[5] Phan et al. 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.

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

 I_1(x,y) = \sum_{\begin{smallmatrix} x' \le x \\ y' \le y\end{smallmatrix}} i(x',y')
 I_2(x,y) = \sum_{\begin{smallmatrix} x' \le x \\ y' \le y\end{smallmatrix}} i^2(x',y')

The variance is given by:

 \operatorname{Var}(X) = \frac{1}{n} \sum_{i=1}^n (x_i - \mu)^2.

Let S_1 and S_2 denote the summations of block ABCD of I_1 and I_2, respectively. S_1 and S_2 are computed quickly by integral image. Now, we manipulate the variance equation as:

 \operatorname{Var}(X) = \frac{1}{n} \sum_{i=1}^n (x_i^2 - 2\cdot\mu\cdot x_i + \mu^2) 
= \frac{1}{n} \sum_{i=1}^n ((x_i)^2) - 2\cdot\sum_{i=1}^n(\mu\cdot x_i) + \sum_{i=1}^n(\mu^2))
= \frac{1}{n} \sum_{i=1}^n ((x_i)^2) - 2\cdot\sum_{i=1}^n(\mu\cdot x_i) + n\cdot(\mu^2))

= \frac{1}{n} \sum_{i=1}^n ((x_i)^2) - 2\cdot\mu \cdot \sum_{i=1}^n(x_i) + n\cdot(\mu^2))
= \frac{1}{n} (S_2 - 2\cdot S_1/n \cdot S_1 + n\cdot((S_1/n)^2))
= \frac{1}{n} (S_2 - (S_1)^2/n)

Where \mu=S_1/n and S_2=\sum_{i=1}^n (x_i^2).

Similar manipulations can be made for skewness and kurtosis (which requires 3rd and 4rd[clarification needed] integral images). See http://vision.okstate.edu/pubs/ssiai_tp_1.pdf for more details.

References[edit]

  1. ^ a b Finkelstein, Amir; neeratsharma (2010). "Double Integrals By Summing Values Of Cumulative Distribution Function". Wolfram Demonstration Project. 
  2. ^ Crow, Franklin (1984). "Summed-area tables for texture mapping". SIGGRAPH '84: Proceedings of the 11th annual conference on Computer graphics and interactive techniques. pp. 207–212. 
  3. ^ Viola, Paul; Jones, Michael (2002). "Robust Real-time Object Detection". International Journal of Computer Vision. 
  4. ^ Tapia, Ernesto (January 2011). "A note on the computation of high-dimensional integral images". Pattern Recognition Letters 32 (2). doi:10.1016/j.patrec.2010.10.007. 
  5. ^ Phan, Thien; Larson, Eric; Sohoni, Sohum; and Chandler, Damon (2012). "Performance-analysis-based acceleration of image quality assessment". IEEE Southwest Symposium on Image Analysis and Interpretation. 

External links[edit]

Lecture videos