📘

Compute Integral Image

Compute the integral image (summed-area table) of a 2D grayscale image.

The integral image $I$ at position $(i, j)$ is defined as the sum of all pixel values at or above row $i$ and at or to the left of column $j$ in the original image $S$ :

$I(i, j) = \sum_{i' \leq i} \sum_{j' \leq j} S(i', j')$

The integral image can be computed efficiently using the recurrence:

$I(i, j) = S(i, j) + I(i-1, j) + I(i, j-1) - I(i-1, j-1)$

with $I(i, j) = 0$ when $i < 0$ or $j < 0$ .

Integral images are used extensively in computer vision for fast computation of rectangular region sums, enabling algorithms like Viola-Jones face detection and SURF feature detection.

Example:

Input:

image = [[1, 2, 3],
         [4, 5, 6],
         [7, 8, 9]]

Output:

[[1, 3, 6], [5, 12, 21], [12, 27, 45]]

Reasoning:

We start by initializing the first element of the integral image $I(0, 0)$ as the value of the first pixel in the original image $S(0, 0)$ , which is $1$ .
Then, we calculate the subsequent elements in the first row using the recurrence relation: $I(0, 1) = S(0, 1) + I(0, 0) = 2 + 1 = 3$ and $I(0, 2) = S(0, 2) + I(0, 1) = 3 + 3 = 6$ .
For the subsequent rows, we apply the recurrence relation $I(i, j) = S(i, j) + I(i-1, j) + I(i, j-1) - I(i-1, j-1)$ , for example, $I(1, 0) = S(1, 0) + I(0, 0) + I(1, -1) - I(0, -1) = 4 + 1 + 0 - 0 = 5$ and $I(1, 1) = S(1, 1) + I(0, 1) + I(1, 0) - I(0, 0) = 5 + 3 + 5 - 1 = 12$ .
The final output is the completed integral image $I$ , which is $\begin{bmatrix} 1 & 3 & 6 \\ 5 & 12 & 21 \\ 12 & 27 & 45 \end{bmatrix}$ .

Constraints:

Input: 2D list of integers (grayscale image)
Return: 2D list of integers (integral image, same dimensions)
Use pure Python (no numpy)
Image dimensions: 1 <= rows, cols <= 100

Editor

Python 3.13.1

Test Results

0/0

Run code to see test results.

📘