Precompute once, then read any rectangle's total in four lookups. Each cell of the summed-area table holds the sum of every pixel above-and-to-the-left; the sum over any axis-aligned box is then I(D) − I(B) − I(C) + I(A) — constant time, no matter how big the box. Down the center, data flows: the pixels go in, one pass builds the table, the rectangle sum comes out. The blue team builds and defends it; the red team tries to break it.
source Viola & Jones, Rapid Object Detection using a Boosted Cascade of Simple Features, CVPR 2001, I-511–I-518 — semanticscholar.org (no stable DOI; conference proceedings — AMBER). Rendered, not quoted.
The table is not searched; it is accumulated. Build it in a single sweep, top-left to bottom-right:
I(y,x) = pixel(y,x) + I(y,x−1) + I(y−1,x) − I(y−1,x−1) — the left run plus the up run, minus the corner counted twice.
Then any box with inclusive corners top-left (r0,c0), bottom-right (r1,c1) is read by inclusion–exclusion at four points:
A = I(r0−1,c0−1) · B = I(r0−1,c1) · C = I(r1,c0−1) · D = I(r1,c1), off-grid = 0. Sum = D − B − C + A. The build is O(N); every query after is O(1).
The integral image is a two-dimensional prefix sum. In 1D, a running total turns any interval sum into two subtractions; in 2D it takes four, by inclusion–exclusion. Crow's summed-area tables (1984) used the same object for texture mapping.
Viola & Jones (2001) gave it its role in vision: with the table in hand, every Haar feature is a handful of rectangle reads, so a boosted cascade can scan a whole image in real time. Each sphere is the next one's premise — the prefix sum feeds the cascade next door.
The blue team's live check: re-run the O(1) formula against the brute-force sum over every one of the 441 rectangles on the constructed image. If red tampers, this badge is where it shows.
A small constructed 6×6 image (fixed-seed, integer intensities 0–9). This is the raw input — the thing whose rectangle sums we want, fast:
One pass over it accumulates the integral image below — each cell already the sum of everything above-and-to-its-left. That table is what you feed the panel.
Change any corner — the sum is computed from four lookups on the spot, and checked against the brute-force total. Never looked up whole.
What the machine produces, proven: the four-corner formula returns every rectangle's pixel sum in O(1), matching the brute-force sum exactly over all 441 rectangles of the 6×6 image — the table built in one pass, the top-left cell equal to the first pixel, a 1×1 box returning its single value.
The blue team's witness (left) confirms the 441-way match live; the red team (right) tries to make it wrong.
And the sums grow: a large bright image overflows a naïve 32-bit accumulator, so precision — not just speed — is a design choice. The integral image is not free detection; it is a constant-time rectangle-sum, and everything Viola–Jones does is built to need nothing more than that.
"Viola & Jones invented the integral image." Cut. The object is Crow's summed-area table (1984); their contribution was the detector that made it matter — Haar features + AdaBoost + cascade.
"Any region sum is four lookups." Cut. Only axis-aligned rectangles. General shapes take more tables or more reads; a rotated box needs the tilted integral image.
"The table is free once built." Kept, corrected. Build is O(N) time and a full extra buffer of memory; the win is amortised over many queries, not conjured.
The red team's move: drop the +I(A) inclusion–exclusion term (compute D − B − C). Boxes touching the origin still look right; any interior box double-subtracts its top-left corner and mis-sums.
Remove the correction and the witness (window 7) recomputes over all 441 rectangles, disagrees with brute force, and turns red. Nothing is faked; the attack is real and it is caught.