Corner and Keypoint Detection

Why Does This Exist?

When comparing two images—whether to stitch a panorama, track an object in a video, or construct a 3D model from multiple views—an algorithm needs reliable reference points. You cannot simply compare every pixel in image A to every pixel in image B; that is computationally impossible and highly sensitive to slight shifts in lighting or rotation.

Instead, we need to extract sparse, distinct features from an image that remain identifiable even if the image is scaled, rotated, or partially obscured. These features are called keypoints. Corners are excellent keypoints because, unlike a flat region or a straight edge, a corner represents a point where image intensity changes sharply in multiple directions. This makes it a highly localizable anchor. The development of robust corner and keypoint detectors like the Harris Corner Detector and SIFT (Scale-Invariant Feature Transform) fundamentally enabled classical object tracking, image stitching, and 3D reconstruction long before deep learning took over.

Think of It Like This

How It Actually Works

Finding corners involves mathematical techniques that search for regions of high contrast in multiple directions. The classical approach, pioneered by the Harris Corner Detector, works through a sliding window mechanism.

1. The Sliding Window

The algorithm conceptually slides a small window over the image and calculates the difference in pixel intensities between the window's current position and slightly shifted positions in all directions.

• Flat region: Shifting the window in any direction results in almost zero change in intensity.
• Edge: Shifting the window along the edge results in no change, but shifting perpendicular to the edge results in a large change.
• Corner: Shifting the window in any direction results in a large change in intensity.

2. The Structure Tensor

Instead of actually shifting the window in every possible direction, the Harris detector uses the image gradients (derivatives). It computes the horizontal derivative ($I_x$) and vertical derivative ($I_y$) for every pixel. It then constructs a $2 \times 2$ matrix, known as the Structure Tensor or the second-moment matrix, over the local window:

$M = \sum w(x,y) \begin{bmatrix} I_x^2 & I_x I_y \\ I_x I_y & I_y^2 \end{bmatrix}$

Here, $w(x,y)$ is a weighting function, typically a Gaussian, that gives more importance to pixels near the center of the window.

3. Eigenvalues and the Corner Response

The behavior of the local window is entirely captured by the two eigenvalues, $\lambda_1$ and $\lambda_2$, of the matrix $M$.

• If both $\lambda_1$ and $\lambda_2$ are small, the region is flat.
• If one eigenvalue is large and the other is small, the region is an edge.
• If both $\lambda_1$ and $\lambda_2$ are large, the region is a corner.

To avoid the computationally expensive eigenvalue calculation, the Harris detector computes a response score $R$ using the determinant and trace of the matrix:

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

Where $\det(M) = \lambda_1 \lambda_2$ and $\text{trace}(M) = \lambda_1 + \lambda_2$. If $R$ is greater than a certain threshold, the pixel is marked as a corner.

4. Scale Invariance (SIFT and SURF)

While the Harris detector is rotation-invariant (a corner is a corner even if you spin the image), it is not scale-invariant. If you zoom in significantly, a sharp corner might appear as a smooth, rounded edge, and the small sliding window will no longer detect it as a corner. Modern keypoint detectors like SIFT solve this by searching for features across multiple scales of the image (an image pyramid), ensuring that the keypoints can be matched even if the object is closer or further away from the camera.

Code

1import numpy as np2import cv23
4def detect_harris_corners(image_path: str) -> np.ndarray:5    # Read the image and convert to grayscale6    img = cv2.imread(image_path)7    gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)8    9    # Convert to float32 for cornerHarris function10    gray = np.float32(gray)11    12    # Calculate Harris corners: block size 2, aperture 3, k 0.0413    dst = cv2.cornerHarris(gray, 2, 3, 0.04)14    15    # Dilate to mark the corners more visibly16    dst = cv2.dilate(dst, None)17    18    # Threshold for an optimal value to mark corners in red19    img[dst > 0.01 * dst.max()] = [0, 0, 255]20    21    # -> Returns image with corners marked22    return img

Watch Out For

The Quick Version

• Keypoints are highly distinct, localizable features in an image used for tracking and matching across frames.
• Corners are ideal keypoints because they exhibit high contrast changes in all directions, unlike flat regions or edges.
• The Harris Corner Detector uses image gradients to build a Structure Tensor, identifying corners by looking for regions with two large eigenvalues.
• Basic corner detectors are rotation-invariant but fail when the image is scaled (zoomed in or out).
• Advanced algorithms like SIFT introduce scale invariance by detecting features across multiple resolutions.