📘

Compute Harris Corner Detector Response

MediumMatrix, Linear Filtering 📚 Computer Vision 1

The Harris Corner Detector identifies interest points by analyzing local image structure through the autocorrelation matrix A. The corner response R is calculated using:

R = det(A) - k × (trace(A))²

where:

det(A) = Axx × Ayy - Axy²
trace(A) = Axx + Ayy

Given pre-computed gradient sums Axx, Ayy, Axy, and sensitivity constant k, calculate the Harris response R.

Constraints:

k = 0.04 (default)
Axx, Ayy, Axy are non-negative floats
0 ≤ Axx, Ayy ≤ 1000

Examples:

| Input | Output | |-------|--------| | Axx=100, Ayy=100, Axy=0, k=0.04 | 9600.0 | | Axx=500, Ayy=500, Axy=10, k=0.04 | 209600.0 |

Example:

Input:

Axx=100, Ayy=100, Axy=0, k=0.04

Output:

8400.0

Reasoning:

First, compute the determinant: $\det(A) = A_{xx} \cdot A_{yy} - A_{xy}^2 = 100 \cdot 100 - 0^2 = 10000$
Then, compute the trace: $\text{trace}(A) = A_{xx} + A_{yy} = 100 + 100 = 200$
Next, compute the penalty term: $k \cdot (\text{trace}(A))^2 = 0.04 \cdot 200^2 = 0.04 \cdot 40000 = 1600$
Finally, compute the Harris response: $R = \det(A) - k \cdot (\text{trace}(A))^2 = 10000 - 1600 = 8400.0$ , which matches the sample output.

More from Computer Vision 1

Semi-Global Matching Cost AggregationHard Compute Depth Map from DisparityMedium Stereo Rectification CheckEasy Oriented BRIEF DescriptorHard Gaussian Scale SpaceMedium

1. Background Knowledge

The Harris Corner Detector (Harris & Stephens, 1988) is a fundamental algorithm for detecting interest points in images. It analyzes the local structure through the autocorrelation matrix (also called structure tensor):

$A = \begin{bmatrix} \sum I_x^2 & \sum I_x I_y \\ \sum I_x I_y & \sum I_y^2 \end{bmatrix} = \begin{bmatrix} A_{xx} & A_{xy} \\ A_{xy} & A_{yy} \end{bmatrix}$

where I_x and I_y are image gradients.

Harris Response Function: $R = \det(A) - k \cdot (\text{trace}(A))^2$

$\det(A) = A_{xx} \cdot A_{yy} - A_{xy}^2$
$\text{trace}(A) = A_{xx} + A_{yy}$
$k$ is a sensitivity constant (typically 0.04-0.06)

Interpretation:

Condition	Region Type
R > 0 (large)	Corner
R < 0 (large negative)	Edge
	R

2. Algorithm Approach

Compute image gradients $I_x$ , $I_y$ using Sobel/Scharr operators
Calculate products: $I_x^2$ , $I_y^2$ , $I_x I_y$
Apply Gaussian weighting to get $A_{xx}$ , $A_{yy}$ , $A_{xy}$
Compute Harris response R at each pixel
Apply non-maximum suppression to find corners

3. Step-by-Step Strategy

Compute determinant: $A_{xx} \cdot A_{yy} - A_{xy}^2$
Compute trace: $A_{xx} + A_{yy}$
Apply formula: $R = \det - k \cdot$ \text{trace} $^2$

4. Common Pitfalls

Forgetting to square the trace
Using wrong sign (det - ktrace² not det + ktrace²)
Not handling negative results (edges have negative R)

5. Time & Space Complexity

Aspect	Complexity
Time	O(1) for single pixel response
Space	O(1)

For full image: O(n²) where n is image dimension.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.