Summed-area table

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 introduced to computer graphics in 1984 by Frank Crow for use with mipmaps. In computer vision it was popularized by Lewis and then given the name "integral image" and prominently used within the Viola–Jones object detection framework in 2001. 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.

The algorithm

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:

I

(

x

,

y

)

=

∑

x

′

≤

x

y

′

≤

y

i

(

x

′

,

y

′

)

{\displaystyle I(x,y)=\sum _{\begin{smallmatrix}x'\leq x\\y'\leq y\end{smallmatrix}}i(x',y')}

where

i

(

x

,

y

)

{\displaystyle 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:

I

(

x

,

y

)

=

i

(

x

,

y

)

+

I

(

x

,

y

−

1

)

+

I

(

x

−

1

,

y

)

−

I

(

x

−

1

,

y

−

1

)

{\displaystyle 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)

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 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:

∑

x

0

<

x

≤

x

1

y

0

<

y

≤

y

1

i

(

x

,

y

)

=

I

(

D

)

+

I

(

A

)

−

I

(

B

)

−

I

(

C

)

{\displaystyle \sum _{\begin{smallmatrix}x_{0}<x\leq x_{1}\\y_{0}<y\leq y_{1}\end{smallmatrix}}i(x,y)=I(D)+I(A)-I(B)-I(C)}

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

x

p

{\displaystyle x^{p}}

with

p

{\displaystyle p}

in

{

0

,

1

}

d

{\displaystyle \{0,1\}^{d}}

, then the sum of image values contained in the rectangle are computed with the formula

∑

p

∈

{

0

,

1

}

d

(

−

1

)

d

−

‖

p

‖

1

I

(

x

p

)

{\displaystyle \sum _{p\in \{0,1\}^{d}}(-1)^{d-\|p\|_{1}}I(x^{p})}

where

I

(

x

)

{\displaystyle I(x)}

is the integral image at

x

{\displaystyle x}

and

d

{\displaystyle d}

the image dimension.