Fast Haar-like Feature Computation using Integral Images

mediumFREEImage ProcessingFiltering, PreprocessingComputer Vision 1

Haar-like filters consist of adjacent rectangular regions used to detect visual features like edges or lines. A crucial aspect of their use is the speed with which their response can be calculated, regardless of the filter size. This efficiency is achieved by using an Integral Image representation.

The Integral Image $I(x,y)$ stores the sum of all pixel intensities in the original image that are above and to the left of position $(x,y)$ . Given the Integral Image, the sum of intensities within any rectangular region defined by top-left corner $(x_0, y_0)$ and bottom-right corner $(x_1, y_1)$ can be calculated with just four lookups:

$\text{Sum} = I(x_1, y_1) + I(x_0-1, y_0-1) - I(x_1, y_0-1) - I(x_0-1, y_1)$

Consider a 2-rectangle edge feature, defined by a Positive Region $R_P$ and an adjacent Negative Region $R_N$ . The filter's response is the difference between the sum of intensities in the positive region and the sum in the negative region:

$\text{Response} = \text{Sum}(R_P) - \text{Sum}(R_N)$

Your task is to compute the response of a vertical 2-rectangle Haar-like filter, given the Integral Image $I$ and the coordinates defining the two regions.

Example

Input

I = [[1, 2, 3, 4],
     [3, 6, 9, 12],
     [4, 8, 12, 16],
     [5, 10, 15, 20]]
rp = [0, 0, 1, 0]  # Positive region: rows 0-1, col 0
rn = [2, 0, 3, 0]  # Negative region: rows 2-3, col 0

Output

Reasoning

Calculate $\text{Sum}(R_P)$ for region $[0,0]$ to $[1,0]$ :
- $I(1,0) = 3$ , boundary terms are 0
- $\text{Sum}(R_P) = 3$
Calculate $\text{Sum}(R_N)$ for region $[2,0]$ to $[3,0]$ :
- $I(3,0) = 5$ , $I(1,0) = 3$
- $\text{Sum}(R_N) = 5 - 3 = 2$
Response = $3 - 2 = 1$

Constraints

The Integral Image $I$ contains non-negative integers
Coordinates are given as: $[x_0, y_0, x_1, y_1]$ (top-left to bottom-right)
All indices are 0-based
For indices $< 0$ , assume the integral image value is 0
The output must be an integer

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 primer

1. Background Knowledge

Haar-like features, introduced in the Viola-Jones face detection framework, are simple rectangular filters that capture local intensity differences to detect edges, lines, and textures in images. They enable rapid feature computation across scales using Integral Images (also called summed-area tables), which precompute prefix sums for constant-time rectangular region queries.

The Integral Image $I(x,y)$ for a grayscale image $i(x,y)$ is defined as:

I(x,y) = \sum_{x'=0}^{x} \sum_{y'=0}^{y} i(x',y')

This allows the sum over any rectangle $(x_0, y_0)$ to $(x_1, y_1)$ (inclusive) via:

\text{Sum} = I(x_1, y_1) + I(x_0-1, y_0-1) - I(x_1, y_0-1) - I(x_0-1, y_1)

Boundary handling: For $x<0$ or $y<0$ , $I(x,y) = 0$ .

A vertical 2-rectangle Haar filter has two adjacent rectangles: positive $R_P$ (e.g., left) and negative $R_N$ (e.g., right), with equal width and height. Response = $\text{Sum}(R_P) -$ \text{Sum} $(R_N)$ , highlighting vertical edges.

Prerequisites: 0-based indexing, grayscale images with non-negative pixels, basic 2D array access.

2. Algorithm Approach

Use direct rectangle sum queries on the given Integral Image $I$ (no need to compute it). For each region defined by $[x_0, y_0, x_1, y_1]$ :

Implement a rect_sum(x0, y0, x1, y1) function using the 4-lookup formula, clamping invalid indices to 0.
Compute $\text{Sum}(R_P)$ and $\text{Sum}(R_N)$ .
Return $\text{Sum}(R_P) -$ \text{Sum} $(R_N)$ as integer.

This is the core of Viola-Jones efficiency: O(1) per feature regardless of rectangle size.

Pseudocode:

def rect_sum(I, x0, y0, x1, y1):
 def safe_get(x, y):
 return I[y][x] if 0 <= x < len(I) and 0 <= y < len(I) else 0

 return (safe_get(x1, y1) + safe_get(x0-1, y0-1)
 - safe_get(x1, y0-1) - safe_get(x0-1, y1))

def haar_response(I, Rp, Rn): # Rp, Rn: [x0,y0,x1,y1]
 return rect_sum(I, *Rp) - rect_sum(I, *Rn)

3. Step-by-Step Strategy

Parse inputs: Extract coordinates for $R_P$ and $R_N$ (assume provided as lists/arrays).
Implement safe lookup: Handle out-of-bounds by returning 0 (per constraints).
Compute rectangle sums: Apply the integral formula twice.
Calculate response: Subtract sums; cast to int if needed.
Test edge cases: Empty regions ( $x_0 > x_1$ ), negative coordinates, full-image spans.

Vertical filter example: $R_P = [2,1,3,4]$ (left), $R_N = [4,1,5,4]$ (right).

4. Common Pitfalls

Off-by-one errors: Formula assumes inclusive corners; $x_0-1, y_0-1$ must be correctly clamped.
Index order: Images are row-major ( $I[y][x]$ ); confuse x/y.
No bounds check: Accessing $I[-1]$ crashes; always use safe_get.
Sign flip: Ensure positive minus negative (not reverse).
Floating-point: Output must be integer; sums are integers by constraint.
Assuming 1-based: Problem specifies 0-based.

5. Time & Space Complexity

Time: $O(1)$ per response (4 lookups), ideal for real-time detection (e.g., 160k+ features/sec in Viola-Jones).
Space: $O(1)$ extra (uses existing $I$ , size $O(HW)$ where $H,W$ are image dimensions).

This scales to thousands of filters over large images, enabling classifiers like AdaBoost.

solution.py

Python 3.13

Test results