The Harris Corner Detector Idea

While edge detectors like Sobel and Canny are great at finding boundaries where image intensity changes abruptly in one direction, sometimes we need points that are even more distinct. Think about tracking an object in a video or matching features between two images taken from different viewpoints. A point along a straight edge can be ambiguous – if you slide a small patch along the edge, it looks pretty much the same. What we often need are points where the intensity changes significantly in multiple directions. These points are typically called corners.

Corners are valuable because they represent points where two or more edges meet, or points of high curvature. They tend to be more stable and easier to locate consistently even if the image undergoes rotation or small changes in viewpoint, compared to points along a simple edge.

So, how do we find these corners? The Harris Corner Detector, developed by Chris Harris and Mike Stephens in 1988, provides a popular and effective method based on analyzing local intensity variations.

The Sliding Window Intuition

Imagine taking a small, fixed-size window (say, 5x5 pixels) and sliding it across the image. For each position of the window, we ask: "How much does the content inside this window change if we shift the window just a tiny bit in any direction?"

Let's consider three scenarios:

1. Flat Region: If the window is currently over an area of uniform intensity (like a patch of clear sky or a plain wall), shifting the window slightly in any direction (horizontally, vertically, diagonally) won't change the appearance of the pixels within the window much, if at all. There's very little variation.
2. Edge Region: If the window is centered over a straight edge, shifting it along the direction of the edge might not cause a significant change in the window's content. However, shifting it perpendicular to the edge will cause a very noticeable change as the window moves across the intensity boundary. So, there's significant change, but primarily in only one direction.
3. Corner Region: If the window is centered over a corner or a point where texture changes significantly in multiple directions, then shifting the window slightly in any direction will result in a substantial change in the window's content. This is the primary characteristic the Harris detector looks for.

This intuition can be visualized like this:

Behavior of a sliding window when shifted slightly over different image regions. Corners exhibit significant changes for shifts in all directions.

Quantifying the Change with Gradients

Instead of actually shifting the window in all directions and calculating the difference (which would be slow), the Harris detector uses a more clever mathematical shortcut based on image gradients. Remember the gradients $I_x$ and $I_y$ we encountered with the Sobel operator? They measure the rate of intensity change in the horizontal (x) and vertical (y) directions, respectively.

The Harris detector looks at the distribution of these gradients within the window centered at a pixel $(x,y)$. It summarizes this information in a small 2x2 matrix, often called $M$ or the "structure tensor":

$$M = \sum_{\text{window}} \begin{bmatrix} I_x^2 & I_x I_y \\ I_x I_y & I_y^2 \end{bmatrix}$$

Don't worry too much about the matrix math itself. The important idea is that this matrix $M$ captures how the gradients are oriented within the window:

• Flat Region: Both $I_x$ and $I_y$ are small everywhere in the window, so the entries in $M$ will be small.
• Edge Region: Gradients are large, but mostly in one direction (perpendicular to the edge). For example, on a vertical edge, $I_x$ would be large and $I_y$ small. This structure is reflected in the matrix $M$.
• Corner Region: Gradients are large in multiple directions ($I_x$ and $I_y$ are both significant), leading to large values in the matrix $M$.

The Harris Response Score (R)

Harris and Stephens found a way to calculate a single score, called the corner response $R$, directly from this matrix $M$, without needing to compute complex things like eigenvalues explicitly. The formula is:

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

Where:

• $\det(M)$ is the determinant of the matrix $M$. It's calculated as $M_{11}M_{22} - M_{12}M_{21}$.
• $\text{trace}(M)$ is the trace of the matrix $M$. It's the sum of the diagonal elements: $M_{11} + M_{22}$.
• $k$ is a sensitivity parameter, usually a small value like 0.04 to 0.06. It's chosen empirically.

The value of $R$ tells us about the type of region the window is currently over:

• $R$ is large and positive: Indicates a corner. Both gradients ($I_x, I_y$) are significant and vary in direction within the window. This corresponds to the case where shifting the window in any direction causes a large change.
• $R$ is negative (large magnitude): Indicates an edge. There's significant gradient, but mainly in one direction. This corresponds to the case where shifting the window causes a large change only when moving perpendicular to the edge.
• $|R|$ is small: Indicates a flat region. Gradients are small in all directions. Shifting the window causes little change.

Finding the Corners

The Harris detector algorithm calculates this $R$ score for every pixel in the image (considering the window centered around that pixel). The result is a "cornerness map" where high positive values suggest corners.

To get the final corner points, two more steps are typically applied:

1. Thresholding: Only pixels with an $R$ score above a certain threshold value are considered potential corner candidates. This filters out flat regions and most edges.
2. Non-Maximum Suppression (NMS): It's likely that several pixels in a small neighborhood around a true corner will have high $R$ scores. NMS examines a small patch (e.g., 3x3 or 5x5) around each candidate pixel and keeps only the pixel with the highest $R$ score in that patch, suppressing the others. This ensures that we detect only a single, well-defined point for each corner.

Summary and Limitations

The Harris Corner Detector provides a computationally efficient way to identify points in an image where intensity changes significantly in multiple directions. It uses image gradients within a local window to compute a response score ($R$) that distinguishes corners from edges and flat regions.

It's a foundational technique for finding interesting points. One limitation is that the basic Harris detector is not scale-invariant. A corner might look like an edge if you zoom in very close, or a small texture pattern might look like a corner from far away but resolve into edges when zoomed in. The size of the window used in the calculation influences the scale at which corners are detected. More advanced detectors build upon these ideas to handle scale changes, but the core concept of analyzing local intensity structure remains fundamental.