Compute Integral Image

easyPROImage ProcessingComputer Vision 1

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

Input: image is a $3 \times 3$ grid $S$ of pixel intensities, with $S(0,0)=1$ top-left and $S(2,2)=9$ bottom-right.
Output: a grid of the same size where $I(i,j)$ is the total of the rectangle running from the top-left corner down to row $i$ , column $j$ .
The top row is just running totals: $1,\ 1+2=3,\ 3+3=6$ . The left column likewise: $1,\ 5,\ 12$ .
Interior cells combine neighbours: $I(1,1) = 5 + 3 + 5 - 1 = 12$ , which matches $1+2+4+5$ . The $-1$ is there because $I(0,0)$ sits inside both $I(0,1)$ and $I(1,0)$ , so it was counted twice.
The same rule gives $I(1,2) = 6 + 6 + 12 - 3 = 21$ and $I(2,1) = 8 + 12 + 12 - 5 = 27$ , and $I(2,2) = 9 + 21 + 27 - 12 = 45$ , the sum of every pixel.
Notice: any rectangle's sum now needs only four corner values. For example, the bottom-right $2 \times 2$ block is $45 - 6 - 12 + 1 = 28 = 5+6+8+9$ .

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

More from Computer Vision 1

Semi-Global Matching Cost Aggregationhard Compute Depth Map from Disparitymedium Stereo Rectification Checkeasy Oriented BRIEF Descriptorhard Gaussian Scale Spacemedium

Concept primerPREVIEW

Background Knowledge

The concept of an integral image, also known as a summed-area table, is a fundamental technique in image processing and computer vision. It is used to efficiently calculate the sum of pixel values within a rectangular region of an image. This is particularly useful in algorithms that require repeated calculations of region sums, such as object detection and feature extraction. The integral image $I$ at position $(i, j)$ represents the cumulative sum of all pixel values at or above row $i$ and at or to the left of column $j$ in the original image $S$ .

The definition of the integral image can be expressed mathematically as: $I(i, j) = \sum_{i' \leq i} \sum_{j' \leq j} S(i', j')$ However, computing this directly for each position (i, j) can be inefficient due to the repetitive nature of the summation. A more efficient approach utilizes the recurrence relation: $I(i, j) = S(i, j) + I(i-1, j) + I(i, j-1) - I(i-1, j-1)$ This recurrence allows for the computation of the integral image in a single pass through the image, making it much more efficient for large images.

Understanding how to apply this recurrence relation and handle boundary conditions (where $i < 0$ or $j < 0$ ) is crucial for implementing an efficient algorithm to compute the integral image. The boundary conditions are typically handled by considering $I(i, j) = 0$ when $i < 0$ or $j < 0$ , which provides a base case for the recurrence.

Algorithm/Approach

The general approach to solving this problem involves using dynamic programming to compute the integral image based on the given recurrence relation. This approach takes advantage of the overlapping subproblems in the computation of the integral image, storing the results of subproblems to avoid redundant computation.

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results