Summed-area table

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

A summed-area table, also known as an integral image, is a data structure that lets you quickly compute the sum of any rectangular region in a grid of numbers (such as an image).

How it works
- Define I(x, y) as the sum of all pixels i(x′, y′) with x′ ≤ x and y′ ≤ y (including the pixel at (x, y)).
- You can build I in one pass, using the simple update:
I(x, y) = i(x, y) + I(x, y − 1) + I(x − 1, y) − I(x − 1, y − 1).
(Build from the top-left corner.)

Querying a rectangle
- Once I is known, the sum of values inside any rectangle can be obtained with four lookups, no matter how large the rectangle is.
- If you label the rectangle’s corners as A = (x0, y0), B = (x1, y0), C = (x0, y1), D = (x1, y1), then the sum over that area is:
sum = I(D) + I(A) − I(B) − I(C).

Extensions
- The idea naturally extends to higher dimensions. For a d-dimensional image, you combine the integral image values at the 2^d corners with signs based on the corner coordinates.
- It also works in continuous domains.

Applications and extensions
- In graphics, it helps with fast shading and mipmaps; in computer vision, it’s a key component of fast feature detection (for example, the Viola–Jones detector).
- You can use multiple integral images to compute block statistics quickly. For example, use I for the sum and I² for the sum of squares to get block variance efficiently. If S1 is the sum over a block and S2 is the sum of squares, the variance is Var(X) = (S2 − S1² / n) / n, where n is the number of pixels in the block. Higher moments (for skewness and kurtosis) can be done with I³ and I⁴.

Practical notes
- Be mindful of integer overflow: sums can exceed 32-bit limits; use larger data types as needed.
- For floating-point data, compensated summation can help reduce rounding errors.