integral image

An integral image, also called a summed-area table, is a precomputation that lets you add up the pixel values inside any rectangle in constant time, no matter how large the rectangle. Naively, summing a 100-by-100 region means adding ten thousand numbers, and doing this at many positions and scales is ruinously slow. The integral image trick reduces every such rectangle sum to exactly four lookups and three additions, which is the single optimization that made real-time feature detection (Viola-Jones face detection, SURF) practical on early-2000s hardware.

The construction is one pass. The integral image is a new array the same size as the original, where the value at a location is the sum of all original pixels above and to the left of it, inclusive. You can fill it in a single sweep using the recurrence that each entry equals the original pixel plus the entry above plus the entry to the left minus the entry diagonally up-left (the subtraction corrects for the overlap that was added twice). After this one-time cost, the original image is no longer needed for rectangle queries.

Querying is the elegant part. The sum of pixels inside any axis-aligned rectangle is obtained by inclusion-exclusion using its four corners in the integral image: take the value at the bottom-right corner, subtract the values at the corners directly above the rectangle and directly to its left, and add back the value at the top-left corner (which was subtracted twice). Four memory reads, regardless of whether the rectangle is 4 pixels or 4 million. This O(1) rectangle sum is what powers Haar-like features (sums of bright minus dark rectangles) in cascade detectors and box-filter approximations of Gaussian derivatives in SURF.

The same idea extends naturally. Integral images of squared pixel values let you compute the variance inside any rectangle in constant time (useful for adaptive thresholding and normalization). Multiple integral images at different gradient orientations give integral histograms, which accelerate dense HOG. Higher-dimensional summed-area tables, and rotated (45-degree) integral images, exist for specialized features. The one caution is numerical: integral values grow with image area and can overflow 32-bit integers for large or high-bit-depth images, so implementations use 64-bit integers or floating point and may tile very large images.