Feature Detection

Feature detection finds a sparse set of image locations, usually called keypoints or interest points, that can be found again in other images of the same scene. Corners, blobs, and regions with stable boundaries are typical choices, because their position can be pinned down in both image directions and survives changes in viewpoint, scale, and lighting. Detection is the first stage of the local-feature pipeline: each keypoint is then summarized by a descriptor, and descriptors are compared across images in feature matching. In video, detected points are the starting points of feature tracking.

Problem Definition

Given an image $I$, return a set of locations, often with a scale and shape attached, such that the same physical scene points would be selected in another image of the scene taken under different conditions. What counts as “the same” depends on the expected transformation between images: a small shift between video frames, a rotation and zoom, a change of viewpoint that foreshortens a surface, or a change in illumination.

The task is defined by its use, not by a semantic label. A detector does not need to find “objects” or “meaningful parts”; it needs to find points whose position is well defined by the local intensity pattern and is reproducible. Points in uniform regions and along straight edges fail this test, for the reason explained by the aperture problem: a patch there can slide in at least one direction without changing.

Input and Output

The input is a grayscale image, sometimes an image pyramid or scale space built from it. The output is a list of keypoints, each with:

• Position $(x, y)$, at pixel or subpixel precision.
• Scale $\sigma$, the size of the neighborhood, for scale-invariant detectors.
• Orientation $\theta$, if one is assigned, usually in a separate step before description.
• Shape, an ellipse rather than a circle, for affine-covariant detectors.
• Response, the detector score, used to rank keypoints and keep the strongest $N$.

Strictly, these geometric attributes are covariant rather than invariant: when the image is rotated or scaled, the detected scale and orientation change with it. Tuytelaars and Mikolajczyk point out that invariance is then obtained in the descriptor, by normalizing the patch with the detected attributes.

Desirable Properties

Tuytelaars and Mikolajczyk’s survey of local feature detectors lists the properties of an ideal local feature:

• Repeatability. A high fraction of features detected in the part of the scene visible in two images should be detected in both. The survey calls this arguably the most important property.
• Distinctiveness. The underlying intensity pattern should vary enough for the feature to be told apart from others and matched.
• Locality. Small features are less likely to be occluded and are better approximated by simple local models of the deformation between images.
• Quantity. Enough features to cover small objects, with a count that a threshold can adjust.
• Accuracy. Precise localization in position, and in scale and shape where these are estimated.
• Efficiency. Fast enough for time-critical applications.

Repeatability is achieved either by invariance, modeling a transformation such as rotation, scaling, or an affine map and designing the detector to be unaffected by it, or by robustness, reducing sensitivity to small disturbances such as noise, blur, and compression. The properties trade off against each other: more locality leaves less information for distinctiveness, and more invariance discards information that could have helped tell features apart.

Challenges

• Scale change. A corner at one zoom level is a rounded blob at another; detectors working at a single scale miss the correspondence.
• Viewpoint change. Out-of-plane rotation foreshortens circular neighborhoods into ellipses.
• Illumination change and noise. Contrast changes alter detector responses, so fixed thresholds select different points in each image.
• Uneven coverage. Textured areas produce many keypoints and plain areas almost none, while geometric estimation works best with points spread across the image.
• Speed. Real-time systems leave only a fraction of the frame time for detection.

Approaches

Corner detectors

Moravec’s detector (1980) measured the change in a window’s intensities when it is shifted by one pixel in a few discrete directions and declared a corner where even the smallest change is large. The Harris corner detector turned this into an analytic measure: a Taylor expansion of the shifted sum of squared differences yields the $2 \times 2$ structure tensor of image gradients, and the corner score combines its determinant and trace. Shi and Tomasi kept the same matrix but used its smaller eigenvalue, the condition that makes the tracking equations well conditioned (see feature tracking).

FAST trades the gradient analysis for intensity comparisons. Its segment test, introduced by Rosten and Drummond in earlier work, accepts a pixel as a corner if a contiguous arc of pixels on a 16-pixel circle around it is entirely brighter or entirely darker than the center by a threshold. The 2006 paper learned a decision tree that decides the test while examining as few circle pixels as possible. The authors reported that it processed live PAL video in under 7% of the available time, against 120% for Harris and 300% for SIFT’s detection stage, and noted that it is sensitive to noise.

Blob and scale-space detectors

Corner detectors work at a fixed scale. Scale-space detectors search over position and scale together and return a characteristic scale for each point. The scale-normalized Laplacian of Gaussian responds most strongly where the filter size matches a blob, and SIFT approximates it with a difference of Gaussians, finding extrema across neighboring positions and scales in a pyramid. The determinant of the Hessian, the matrix of second derivatives, is a second blob measure that responds less to straight edges than the Laplacian does. SURF approximates the Hessian with box filters on integral images, for speed (see feature descriptors).

Mikolajczyk and Schmid’s Harris–Laplace detector combines the two ideas: it localizes points with a scale-adapted Harris measure and selects the scale at which the normalized Laplacian is maximal.

Affine-covariant regions

Scale invariance handles zoom and in-plane rotation, but a change of viewpoint stretches a neighborhood differently in different directions. Harris-Affine and Hessian-Affine iteratively adapt each region’s elliptical shape using the second-moment matrix until the normalized patch is isotropic. Maximally stable extremal regions (MSER), introduced by Matas et al., take a different route: thresholding the image at every level produces nested connected components, and the detector keeps those whose area changes least over a range of thresholds. The set of extremal regions is unchanged by monotonic changes of intensity, and their detection covaries with continuous geometric transformations.

In the comparison by Mikolajczyk et al. (2005), MSER or Hessian-Affine obtained the best repeatability in most experiments, Hessian-Affine and Harris-Affine produced several times more corresponding regions than the others, and no detector was best for all scene types and transformations. The authors concluded that the detectors are complementary and recommended combining several.

Learned detectors

Learning-based detectors replace a hand-designed response with a trained network. SuperPoint computes keypoints and descriptors for a whole image in one forward pass of a convolutional network. It is trained without manual labels, by first learning corners on synthetic shapes and then aggregating detections over random homographic warps of real images. Joint learning of detection, description, and matching is covered in feature matching.

Datasets and Benchmarks

Detector evaluations use image pairs related by a known homography, so that ground-truth correspondences are available everywhere: planar scenes, or a camera that only rotates. The Oxford affine dataset of Mikolajczyk et al. has eight sequences of six images each, covering viewpoint change, zoom and rotation, blur, JPEG compression, and illumination change. HPatches, a larger collection of 116 sequences with illumination or viewpoint changes, was designed for descriptors but is also used for detector repeatability, as in the SuperPoint paper.

Evaluation Metrics

The standard measure is the repeatability score, built on a criterion by Schmid, Mohr, and Bauckhage (2000). Points are mapped from one image to the other with the ground-truth homography, and only the part of the scene visible in both images is considered. Two detections correspond if they lie within a small distance of each other (Mikolajczyk and Schmid used 1.5 pixels) and, for regions, if their overlap error is small; Mikolajczyk et al. (2005) used an overlap error below 40%. The score is the number of correspondences divided by the smaller of the two detection counts.

The score depends on how many points are detected: a few points selected with sharp thresholds tend to be stable, while very dense detections can correspond by accident. Mikolajczyk et al. therefore reported it together with the number of correspondences and as a function of the number of detections. Because detectors serve matching, they are also judged downstream by matching precision, homography accuracy, or pose accuracy, as described in feature matching.

Applications

• Image matching and stitching, through descriptor matching and robust model fitting with RANSAC.
• Structure from motion and SLAM, where keypoints become the 2D observations of reconstructed 3D points.
• Feature tracking in video, starting from corners selected by the Shi–Tomasi criterion.
• Camera calibration, where checkerboard corners are detected with subpixel accuracy.
• Object recognition and image retrieval, which used local features before learned global representations.

Open Problems

• Extreme appearance change, such as day–night and seasonal change, where hand-designed detectors rarely fire at the same locations.
• Repeatability versus matchability. A point can be detected reliably and still be ambiguous, as on repetitive facades, so detector quality cannot be judged in isolation.
• Low-texture scenes, where few points exist; detector-free dense matchers avoid the detection step altogether.
• Benchmark limits. Homography-based benchmarks test planar scenes, which do not capture occlusions and depth discontinuities in real 3D scenes.