Corner Detection: Harris, Shi-Tomasi & FAST

"Flat regions tell you nothing. Edges only commit in one direction. Me? I am interesting from every angle, and I have the eigenvalues to prove it."

A Structurally Confident Corner Detector

Chapter 9 celebrated edges as the most informative pixels in a single image. The moment a second image enters the picture, the celebration sours. This chapter's opening problem is correspondence: pick a point in image one, find the same physical point in image two. For that job, edges have a fatal flaw, and the first task of this section is to understand the flaw precisely, because the cure is the definition of a corner.

1. The Correspondence Problem and the Aperture Problem Beginner

Imagine sliding a small window over a photograph and asking, at each location, a simple question: if I nudge this window a few pixels in any direction, does the patch of pixels inside it change? Three qualitatively different answers exist. Over a blank wall, the patch looks identical no matter where you nudge it; a matcher trying to localize that patch in another image would find thousands of equally good positions. Along an edge, the patch changes when you cross the edge but stays the same when you slide along it; the matcher can pin down one coordinate but not the other. Only at a corner, where two edges meet or texture varies in two directions, does every nudge change the patch. A corner is localizable in both dimensions, and that is the whole reason this chapter hunts for corners rather than edges.

The edge case has a classical name: the aperture problem. Seen through a small aperture, a moving edge appears to move only perpendicular to itself; its motion along its own direction is invisible. The same ambiguity that ruins edge matching here will return in Chapter 15 as the central obstacle of optical flow, and the detectors built in this section are exactly the points where optical flow is well posed. Figure 10.1.1 makes the three-way distinction visual.

2. The Structure Tensor: Measuring Change in All Directions Intermediate

To turn the sliding-window thought experiment into an algorithm, write it down. Let $I(x, y)$ be a grayscale image and consider shifting a window $W$ by a small offset $(u, v)$. The summed squared difference between the original and shifted patch is

$$ E(u, v) \;=\; \sum_{(x,y) \in W} w(x, y)\, \big[ I(x+u,\, y+v) - I(x, y) \big]^2, $$

where $w$ is a weighting window (Gaussian in practice, so that pixels near the center count more). For small shifts, the first-order Taylor expansion $I(x+u, y+v) \approx I + u\, I_x + v\, I_y$ replaces the image difference with the image gradients $I_x$ and $I_y$, the same quantities the Sobel operator of Chapter 3 computes. Substituting and collecting terms gives a quadratic form

$$ E(u, v) \;\approx\; \begin{bmatrix} u & v \end{bmatrix} M \begin{bmatrix} u \\ v \end{bmatrix}, \qquad M \;=\; \sum_{(x,y) \in W} w(x,y) \begin{bmatrix} I_x^2 & I_x I_y \\ I_x I_y & I_y^2 \end{bmatrix}. $$

The $2 \times 2$ matrix $M$ is the structure tensor (also called the second-moment matrix), and it compresses everything the window knows about local geometry into three numbers. Because $M$ is symmetric, it has two non-negative eigenvalues $\lambda_1 \geq \lambda_2$ with orthogonal eigenvectors, and the quadratic form means exactly this: shifting the window by one pixel along the first eigenvector changes the patch by $\lambda_1$; along the second, by $\lambda_2$. The eigenvalues are the answers to the sliding-window question, measured in the two most informative directions.

The classification follows immediately, and Figure 10.1.2 draws it. If both eigenvalues are small, no shift changes anything: flat. If one is large and the other small, the patch changes only across one direction: edge. If both are large, every shift changes the patch: corner. Note the pleasant continuity with Chapter 9: an edge detector looks for one large gradient direction; a corner detector demands two.

3. The Harris Response Intermediate

In 1988, eigenvalue decompositions were expensive, and Harris and Stephens wanted a corner score for every pixel of every frame. Their trick: you do not need the eigenvalues themselves, only a function that is large when both are large. The determinant and trace of $M$ deliver them indirectly, since $\det M = \lambda_1 \lambda_2$ and $\operatorname{tr} M = \lambda_1 + \lambda_2$, both computable directly from the tensor entries. The Harris response is

$$ R \;=\; \det M - k\,(\operatorname{tr} M)^2 \;=\; \lambda_1 \lambda_2 - k\,(\lambda_1 + \lambda_2)^2, $$

with $k$ an empirical constant, conventionally between 0.04 and 0.06. Work through the three cases: both eigenvalues small gives $R \approx 0$; one large eigenvalue makes the trace term dominate, driving $R$ negative; two large eigenvalues make the determinant win, $R$ large and positive. One formula, three regimes, no eigendecomposition. The purple contour in Figure 10.1.2 shows the resulting decision boundary curving through the eigenvalue plane.

The full detector is the response map plus two cleanup steps: threshold $R$ to keep only confident corners, and apply non-maximum suppression so that each corner contributes one detection rather than a blob of high-response pixels (the same hygiene Canny applied to edges in Chapter 9). The implementation below builds all of it from operations you already own from Chapter 3: two Sobel passes, three Gaussian blurs, and pixelwise arithmetic.

import cv2
import numpy as np

def harris_response(gray: np.ndarray, k: float = 0.05,
                    sigma: float = 1.5) -> np.ndarray:
    """Harris corner response for every pixel, from first principles."""
    g = gray.astype(np.float32) / 255.0
    Ix = cv2.Sobel(g, cv2.CV_32F, 1, 0, ksize=3)    # horizontal gradient
    Iy = cv2.Sobel(g, cv2.CV_32F, 0, 1, ksize=3)    # vertical gradient
    # Structure-tensor entries: products of gradients, Gaussian-windowed
    Sxx = cv2.GaussianBlur(Ix * Ix, (0, 0), sigma)
    Syy = cv2.GaussianBlur(Iy * Iy, (0, 0), sigma)
    Sxy = cv2.GaussianBlur(Ix * Iy, (0, 0), sigma)
    det = Sxx * Syy - Sxy * Sxy                      # lambda1 * lambda2
    trace = Sxx + Syy                                # lambda1 + lambda2
    return det - k * trace * trace

img = cv2.imread("building.jpg", cv2.IMREAD_GRAYSCALE)
R = harris_response(img)

# Keep strong responses that are also the maximum of their 7x7 neighborhood
threshold = 0.01 * R.max()
is_local_max = (R == cv2.dilate(R, np.ones((7, 7), np.uint8)))
ys, xs = np.where((R > threshold) & is_local_max)
print(f"{len(xs)} corners")        # typical photo of a building: ~400 corners

4. Shi-Tomasi: A Better Score for Trackers Intermediate

Six years after Harris, Shi and Tomasi revisited the response formula while building a feature tracker and proposed something simpler: score each pixel by the smaller eigenvalue alone,

$$ R_{\text{ST}} \;=\; \min(\lambda_1, \lambda_2). $$

The reasoning is beautifully task-driven. A tracker's failure mode is drift along the direction of least information, and that direction's information content is exactly $\lambda_2$. If the worst direction is still strong, the point is trackable; the strength of the best direction is irrelevant once the worst one passes the bar. Geometrically (Figure 10.1.2 again, the teal lines) the acceptance region becomes a clean quadrant: $\min(\lambda_1, \lambda_2) > t$. On modern hardware the eigenvalues of a symmetric $2\times2$ matrix cost a square root, so the historical motivation for avoiding them is gone, and Shi-Tomasi is the default corner scorer in OpenCV's aptly named function:

corners = cv2.goodFeaturesToTrack(
    img,                  # 8-bit grayscale input
    maxCorners=500,       # cap on detections, strongest first
    qualityLevel=0.01,    # accept corners above 1% of the best score
    minDistance=10,       # spatial spread: no two corners closer than this
    blockSize=3)          # structure-tensor window size
print(corners.shape)      # (500, 1, 2): float32 (x, y), ready for tracking

The minDistance parameter deserves a comment because it encodes a lesson detectors keep re-learning: raw response strength concentrates wherever texture is strongest, but downstream geometry wants coverage. Estimating a homography from 500 corners on one bush and zero on the rest of the frame is numerically legal and practically useless. Spreading detections, whether by minimum distance, per-tile quotas, or adaptive suppression, is standard practice in every serious pipeline, including the SLAM systems of Chapter 14.

5. FAST: Corners at Video Rate Intermediate

Harris and Shi-Tomasi compute gradients, products, and blurs for every pixel: a few dozen floating-point operations each. That is nothing for one photograph and a budget-breaker for a robot processing 60 frames per second on an embedded CPU while also doing everything else. FAST (Features from Accelerated Segment Test, Rosten and Drummond, 2006) attacks the cost with a different philosophy: do not measure cornerness, just test for it, as cheaply as possible.

The segment test examines a Bresenham circle of 16 pixels at radius 3 around a candidate pixel $p$ with intensity $I_p$. The candidate is a corner if at least $n$ contiguous pixels on the circle are all brighter than $I_p + t$ or all darker than $I_p - t$, for a threshold $t$. The standard choice is $n = 9$ (FAST-9), which empirically beats the original $n = 12$ on repeatability. The intuition maps back to Figure 10.1.1: a flat region has no such run, an edge has two runs of about half the circle that are interrupted, and a corner has one long unbroken run of "different" on the outside of the corner.

Two engineering moves make FAST genuinely fast. First, a quick-reject: examine the four compass pixels (top, right, bottom, left); if fewer than three of them are sufficiently brighter or darker, no run of 9 can exist, and most of the image exits after four comparisons. Second, Rosten and Drummond trained a decision tree (classic ID3, on labeled corner data) that orders the remaining pixel tests to maximize information gain, then compiled the tree to branchy code. The detector that results performs a handful of byte comparisons per pixel, no multiplications at all, and runs comfortably at video rate on a microcontroller. The price: FAST returns no cornerness measure of its own, so for non-maximum suppression a score $V$ (the largest $t$ for which the pixel remains a corner) is computed for accepted candidates only.

fast = cv2.FastFeatureDetector_create(
    threshold=25,             # intensity margin t for the segment test
    nonmaxSuppression=True,
    type=cv2.FAST_FEATURE_DETECTOR_TYPE_9_16)   # FAST-9 on a 16-pixel circle
kps = fast.detect(img, None)
print(f"with NMS: {len(kps)} keypoints")

fast.setNonmaxSuppression(False)
print(f"without NMS: {len(fast.detect(img, None))} keypoints")
# with NMS: 1247 keypoints
# without NMS: 4108 keypoints   (clumps of adjacent detections)

6. Choosing a Detector Beginner

Three detectors, one decision. Table 10.1.1 condenses the trade-offs that the previous sections developed, and one column matters more than the others: none of these detectors survives a change of scale. A corner at one zoom level is a smooth curve at another; the structure tensor and the segment test both operate at a single, fixed neighborhood size. Fixing that is an idea important enough to get its own section, and Section 10.2 builds it.

The table's speed column explains the field's revealed preference: when ORB (Section 10.4) needed a detector to pair with its binary descriptor, it chose FAST and patched its weaknesses (adding a pyramid for scale, an intensity-centroid orientation, and a Harris score for ranking) rather than starting from Harris. Detector and descriptor choices are rarely independent.