EP08_03 — 🟢 Integral Image: Rectangular Sums in Constant Time
8.14.3 EP08_03 🟢 Integral Image: Rectangular Sums in Constant Time
Imagine a security camera processing 30 frames per second, and for each frame the system must scan the image at dozens of positions and scales, testing at each one a set of rectangular features to decide “is there a face here?”. If computing the sum of intensities for each rectangle required summing pixel by pixel, the system would have no chance of real-time evaluation — the bottleneck would lie precisely in the most repetitive part of the algorithm. It is exactly this bottleneck that the integral image eliminates.
The Haar Cascade evaluates thousands of rectangular features per window, at multiple positions and scales — something unfeasible in real time if each rectangle required summing its pixels one by one. The integral image, defined in the section on Haar Cascade, solves this problem: once precomputed, the sum of intensities of any rectangular region is obtained with just four lookups and three arithmetic operations, regardless of the size of the rectangle.
You have been tasked with implementing this structure from scratch: first, compute the integral image from the original image; then, answer arbitrary rectangular queries using it.
8.14.3.1 📋 Implementation Guidelines
Input: Read the dimensions \(H \times W\) of the image and its \(H \times W\) integer intensity values.
Integral image: Compute, for each position \((i,j)\) (indexing starting from \(0\), [row][column]), \[
II(i,j) = \sum_{i' \le i,\ j' \le j} I(i', j'),
\] that is, the sum of all pixels above and to the left of \((i,j)\), including the position itself.
Queries: Read the integer \(Q\) and then \(Q\) lines, each with four integers \(x_1\ y_1\ x_2\ y_2\) — the top-left and bottom-right corners of a rectangle, both inclusive, with \(0 \le x_1 \le x_2 < W\) and \(0 \le y_1 \le y_2 < H\).
Rectangular sum in O(1): For each query, compute the sum of intensities within the rectangle using exclusively values already present in \(II\) (without traversing the original pixels): \[
S(x_1,y_1,x_2,y_2) = II(y_2,x_2) - II(y_2, x_1{-}1) - II(y_1{-}1, x_2) + II(y_1{-}1, x_1{-}1),
\] treating any term with a row or column index equal to \(-1\) as \(0\).
Output: First, print the complete integral image — \(H\) lines with \(W\) integers each. Then, for each query, print a single integer: the sum of the corresponding region.
8.14.3.2 📌 Computational Constraints
Do not recalculate by brute force: the answer to each query must use the four-term formula on \(II\), not a direct sum of the rectangle’s pixels (even though the numerical result is the same, the point of the exercise is precisely this technique).
Rectangles with inclusive coordinates:\((x_1,y_1)\) and \((x_2,y_2)\) belong to the summed region.
Boundary handling: when querying \(II\) with index \(-1\) (when \(x_1=0\) or \(y_1=0\)), use the value \(0\).
8.14.3.3 🧠 Theoretical Foundation
Element
Role in Haar Cascade
Integral image \(II\)
Precomputed once per image, in time \(O(HW)\)
O(1) query
Each Haar feature (difference between sums of rectangular regions) is evaluated with few operations, regardless of the rectangle’s area
Scalability
It is this constancy that makes it feasible to evaluate thousands of features, at multiple positions and scales, in real time
Inclusion-exclusion principle
The four terms of the formula sum the desired region and subtract exactly the areas counted in excess
8.14.3.4 📦 Input and Output Specification (VPL)
Input:
Line 1: Integers \(H\) and \(W\).
Next \(H\) lines: \(W\) integers each (original image).
Next line: Integer \(Q\).
Next \(Q\) lines: four integers \(x_1\ y_1\ x_2\ y_2\).
Output:
\(H\) lines with \(W\) integers each (the integral image).
\(Q\) lines, one per query, with the sum of the corresponding region.
8.14.3.5 📌 Examples
Input
Output
Observation
3 3
1 2 3
4 5 6
7 8 9
1
0 0 2 2
1 3 6
5 12 21
12 27 45
45
The query covers the entire image; the sum coincides with \(II(2,2)\) and with the sum of all 9 values.
3 3
1 2 3
4 5 6
7 8 9
2
1 1 2 2
0 0 1 1
1 3 6
5 12 21
12 27 45
28
12
The first query uses the four terms of the formula; the second coincides directly with \(II(1,1)\), since it starts at the origin.
🎮 Simulator EP08_03: Rectangular Sum with Integral ImageInternal
Choose a rectangle (x1, y1) – (x2, y2). The integral image II includes virtual border (−1) with zeros for exception-free validation.