Reusing work across image windows
A box filter or local contrast estimate may ask for many overlapping rectangular regions of the same image. Summing each region from scratch repeats additions. An integral image, also called a summed-area table, stores prefix sums so that any valid axis-aligned rectangle can be queried with four table values.
Let be a real-valued image with integer rows and columns, indexed from one. We treat a fixed image and exact arithmetic first. A box average is not claimed to be an ideal antialiasing filter; it is only a cheap local statistic.
Constructing the table
Definition 11.1.1
(Integral image (summed-area table))
For an image with rows and columns, the integral image is the array with sentinel values and
Thus is the sum of all pixels in the rectangle with corners and . The sentinel row and column are zero; they do not represent extra image pixels.
For construction, the same prefix is obtained from its neighbors:
The overlap of the upper and left prefixes is subtracted once because those two sums count it twice. Computing entries in increasing row and column order makes each predecessor available. This recurrence is the special case of the next result in which the rectangle is a single pixel.
Proposition 11.1.2
(Four-corner rectangle sum)
Let and , and let be the sum of over and . Then
Proof
(Splitting the prefix rectangle into four blocks)
The prefix rectangle with corners and is the disjoint union of four blocks:
- the target ,
- the strip above it, ,
- the strip to its left, ,
- the corner .
Write for the sum of over a block ; an empty block has sum , which agrees with the sentinel values. Then
Therefore the right-hand side of the formula equals
Taking and gives , which is the recurrence above.
Proof X-ray
Where the four terms come from
The one non-obvious move is the decomposition into , , and . Subtracting the two strip prefixes and removes and exactly once, but it removes the corner block twice, because lies inside both prefixes. The final term puts it back once. This is inclusion–exclusion on two overlapping regions.
The hypothesis and is what makes the indices and legal; the zero sentinels extend the same formula to rectangles touching the top or left border, where , or is empty. The upper bounds and keep every corner inside the table.
The argument only uses that sums over disjoint blocks add and can be subtracted. It never uses that is a picture, so the same formula holds for the array of squared pixel values, which is what the local variance below needs.
With constant-time array access and exact constant-time arithmetic, construction costs time and the padded table uses space. Each rectangle query uses a constant number of table accesses and arithmetic operations. This claim is for a fixed precomputed image: changing one pixel can change every prefix whose bottom-right corner lies below and to its right.
A local mean and variance
For the image
its ordinary prefix table, omitting the zero sentinels, is
Worked example 11.1.3
(Building the table with the recurrence)
Row and column only involve sentinels. For example . For an interior entry,
and for the last entry
Both agree with the table. As a check, the entries of add up to .
The mean and variance of a window need two prefix tables, one for and one for . The variance formula used below is the following identity.
Proposition 11.1.4
(Variance from two sums)
Let be real numbers with , sum , sum of squares and mean . Then the population variance satisfies
Proof
(Expanding the square)
Expand and sum over :
where was used. Dividing by gives the identity.
Worked example 11.1.5
(Mean and variance of a window)
Take rows through and columns through . Its sum is and its area is , so its mean is . Build a second prefix table from elementwise. Its corresponding corner values give squared sum .
The population variance of these six samples is
This is not the sample-variance convention with denominator . In exact arithmetic the variance is nonnegative; floating-point subtraction of two close quantities may lose accuracy, so an implementation must consider numerical precision and its chosen policy.
Worked example 11.1.6
(Rectangles that touch the border)
When or the formula reads the zero sentinels. For rows through and columns through ,
and the entries do add up to . A rectangle with one row is also allowed: for row and columns through ,
matching .
Common mistake
(Off-by-one corners)
Using and instead of and drops the first row and column of the rectangle. For rows through and columns through the wrong formula gives , which is the sum of the smaller rectangle formed by row and columns through (), not the required . The subtracted prefixes must stop just before the rectangle starts.
Common mistake
(Squaring the sum instead of summing squares)
The variance needs , not . For the window above, whereas the sum of squares is ; using would make the variance , although the six values are not all equal. This is why a second table built from is required.
Boundaries and updates are part of the contract
Counterexample mode
Two edge policies give different means
At the top-left pixel of this image, a centered window extends outside the array. Cropping it to the four available pixels gives sum and mean . Padding the missing positions with zeros and averaging all nine gives . Neither is automatically the other: the boundary rule and divisor must be specified.
A prefix table answers static-image rectangles efficiently; it does not make updates free. If pixel changes, every stored prefix with and changes by the same increment. Dynamic updates require recomputation or another data structure. For squared sums, changing a pixel also changes its square by the appropriate difference, not generally by the original increment.
Exercises with solutions
Quick check
(What does the four-corner formula give when and ?)
Put the same row and column into every term.
Solution · Answer
The value of that pixel; all earlier prefixes cancel, as in the recurrence for .
Quick check
(What is the sum of all pixels in the example?)
Which single table entry covers the whole image?
Solution · Answer
.
Quick check
(Which divisor gives in the edge example?)
Count the pixels that survive cropping.
Solution · Answer
Four, the number of retained pixels after cropping.
Quick check
(Can the old prefix table be used unchanged after modifying ?)
Which prefixes contain the pixel ?
Solution · Answer
No. Every non-sentinel prefix contains that pixel and must be updated or recomputed.
Exercise 11.1.7
(Using the tables and of the example, find the population variance of the window with rows through and columns through .)
Core
The table of squared pixels has entries and .
Solution(3)
- 1
Sum of the window from
The corners with read the zero sentinels, so
- 2
Sum of squares from
In the same way
which agrees with .
- 3
Apply the variance identity
Because: The window has pixels, so .