Harris Corner Response

To solve this problem, you just need to understand what the Harris response is and how to compute it from the entries of a 2×2 matrix, without worrying about the full detector pipeline.

---

1. Background Knowledge (Key Concepts)

The structure tensor (or second-moment matrix) at a pixel summarizes how image intensity changes around that pixel using image gradients $I_x$ and $I_y$. For a small neighborhood, it can be written as:

$$M = \begin{pmatrix} I_x^2 & I_x I_y \\ I_x I_y & I_y^2 \end{pmatrix} = \begin{pmatrix} a & b \\ b & c \end{pmatrix}$$

The eigenvalues $\lambda_1,$\lambda$_2$ of $M$ measure the gradient variation along two principal directions.

• Both large: intensity changes strongly in two directions → corner
• One large, one small: strong change in one direction only → edge
• Both small: little change → flat region

Explicitly computing eigenvalues per pixel is expensive. The Harris corner detector instead uses the determinant and trace of $M$ to approximate a corner score:

$$R = \det(M) - k \cdot \text{trace}(M)^2$$

This scalar Harris response $R$ is large positive for corners, large negative near edges, and near zero in flat regions.

---

2. Algorithm / General Approach

Given the 2×2 structure tensor $M = \begin{pmatrix} a & b \\ b & c \end{pmatrix}$:

1. Compute:

• Determinant: $\det(M) = ac - b^2$
• Trace: $\text{trace}(M) = a + c$

2. Plug into the Harris response formula:

$$R = \det(M) - k \cdot \text{trace}(M)^2$$

3. Use the sign and magnitude of $R$ to interpret the pixel:

• $R > 0$: likely corner
• $R < 0$: likely edge
• $R \approx 0$: likely flat

The coding problem usually just asks you to compute $R$ from $a, b, c, k$, not to perform non-maximum suppression or thresholding.

---

3. Step-by-Step Strategy to Implement

Assume the function gets $a, b, c$ and $k$ as inputs:

1. Extract matrix entries

• You may be given $I_x$ and $I_y$ or directly $a = I_x^2$, $b = I_x I_y$, $c = I_y^2$.
• In this problem, you can treat $a, b, c$ as already provided components of $M$.

2. Compute determinant

det_M = a * c - b * b

3. Compute trace

trace_M = a + c

4. Compute Harris response

R = det_M - k * (trace_M ** 2)

5. Return R

• The caller can later compare $R$ against thresholds or use it in further steps.

That’s all the math required for this problem.

---

4. Common Pitfalls

• Wrong formula for determinant: Ensure $ac - b^2$, not $ab - c^2$ or other permutations.
• Forgetting to square the trace: The formula uses $\text{trace}(M)^2$, i.e., $(a + c)^2$, not just $a + c$.
• Misusing $k$:
• $k$ is a scalar (typically $0.04$–$0.06$); don’t square it or modify it.
• Make sure its type matches your other values (float vs int).
• Precision issues: If values are large, use floating-point arithmetic (e.g., float or double) to avoid overflow or truncation.
• Sign interpretation:
• The problem may not require classification (corner/edge/flat), only computing $R$. If you do classify, use given thresholds or note that exact boundary around 0 is approximate.

---

5. Time & Space Complexity

For computing the Harris response at a single pixel:

• Time complexity:
• A constant number of arithmetic operations → $O(1)$.
• Space complexity:
• Only a few scalar variables (det, trace, R) → $O(1)$.

If extended over an image with $N$ pixels, computing $R$ for each pixel is $O(N)$ time and $O(1)$ extra space per pixel (or $O(N)$ if you store all responses).