Source-linked AI summary
Faster and better: a machine learning approach to corner detection
Edward Rosten, Reid Porter, Tom Drummond
TL;DR
Corner detectors need both repeatability across viewpoints and enough efficiency for frame-rate processing. This paper develops machine-learned detectors from a segment-test heuristic, generalizes them for repeatability, and evaluates them on 3D scenes. The resulting detectors combine very high speed with improved repeatability.
Problem
Corner detectors must identify corresponding real-world 3D points across views while operating efficiently enough for frame-rate processing.
Method
The paper uses machine learning to derive FAST-9 from a segment-test heuristic and generalizes the detector into FAST-ER, optimized for repeatability.
Results
The detectors are computationally efficient and highly repeatable, with FAST-ER showing dramatic repeatability improvements over FAST-9, especially in noisy images.
Takeaways & Limitations
The paper concludes that machine learning can produce a corner detector that is both very fast and high quality.
Abstract
from arXiv · showhide
The repeatability and efficiency of a corner detector determines how likely it is to be useful in a real-world application. The repeatability is importand because the same scene viewed from different positions should yield features which correspond to the same real-world 3D locations [Schmid et al 2000]. The efficiency is important because this determines whether the detector combined with further processing can operate at frame rate. Three advances are described in this paper. First, we present a new heuristic for feature detection, and using machine learning we derive a feature detector from this which can fully process live PAL video using less than 5% of the available processing time. By comparison, most other detectors cannot even operate at frame rate (Harris detector 115%, SIFT 195%). Second, we generalize the detector, allowing it to be optimized for repeatability, with little loss of efficiency. Third, we carry out a rigorous comparison of corner detectors based on the above repeatability criterion applied to 3D scenes. We show that despite being principally constructed for speed, on these stringent tests, our heuristic detector significantly outperforms existing feature detectors. Finally, the comparison demonstrates that using machine learning produces significant improvements in repeatability, yielding a detector that is both very fast and very high quality.
I. INTRODUCTION
Corner detectors must balance real-time efficiency with repeatable localization of the same 3D points across views. The literature contains diverse edge-, edgel-, curvature-, and chain-based approaches, each defining corners through local geometric structure.
- Real-time video processing remains difficult because existing feature detectors leave little or no time at full frame rate.
- Repeatability matters because multiple views should detect the same real-world points for matching and database-based vision applications.
- Edge-based corner detectors: Edge-based detectors estimate corners from chained curves, curvature, slope changes, angles, or high second derivatives.
- Edge-based corner detectors: Many edge methods use fixed or adaptive support regions and smoothing scales to identify stable curvature maxima.
- Edge-based corner detectors: Edgel-based detectors examine local edge points or image windows, including curvature patterns, line intersections, gradient changes, and junction geometry.
2) Greylevel derivative based detectors:
Greylevel derivative detectors locate corners directly from image derivatives and related differential structure. Their methods range from gradient-based curvature measures to SSD, Hessian, Laplacian, and multiscale constructions.
- Some derivative methods measure corner strength from gradient direction changes, image curvature, or magnetic-vector-potential derivatives.
- Local SSD detectors: Local SSD detectors identify points with low self-similarity in all directions by comparing image patches with shifted versions.
- Local SSD detectors: Harris-style methods approximate the second derivative of SSD using a matrix H, whose eigenvalues or norms provide corner strength.
- Laplacian-based detectors: Laplacian-based detectors smooth images before computing second derivatives, while LoG and DoG responses support multiscale feature selection.
- Laplacian-based detectors: DoG approximates LoG and is faster to compute, while Hessian eigenvalue checks reject edge-like features.
3) Direct greylevel detectors:
Direct greylevel detectors inspect local image patches rather than relying primarily on explicitly chained edges. They model corners through wedges, self-dissimilarity, oriented energy, radial symmetry, or learned classifiers.
- Wedge model detectors: Wedge-model detectors treat corners as localized appearances containing one or more uniform-intensity wedges on a contrasting background.
- Wedge model detectors: Wedge methods use thresholding, moments, concentric arcs, Hough angles, gradients, and region dissimilarity to detect candidate corners.
- Self dissimilarity: Self-dissimilarity methods define corners as points whose surrounding pixels or patches are not similar to the center across orientations.
- Self dissimilarity: Other direct detectors use oriented Gabor energy or radial symmetry, with detected points corresponding to maxima of these responses.
- Machine learning based detectors: FAST uses a circle around a candidate pixel to train a decision-tree classifier for speed, while FAST-ER generalizes it for repeatability optimization.
B. Comparison of feature detectors
The paper reviews three categories of feature-detector evaluation and emphasizes repeatability across views as a broadly applicable quality measure, while noting that repeatability alone does not ensure useful features.
- Feature-detector evaluations compare corner recognition, system performance, and repeatability across multiple views.The review groups prior tests into three broad categories: object-recognition-style corner detection, application-level performance, and repeatability.
- Repeatability measures whether the same real-world features are detected from multiple views and provides an upper bound on detector performance.For image pairs, a feature is repeated when it is detected nearby in the second image; planar scenes permit homography-based correspondence.
- Repeatability can be misleading because detecting every pixel achieves 100% repeatability, while repeatable bright pixels may be unsuitable for further processing.The measure is independent of downstream processing, so high repeatability does not itself establish feature usefulness.
- Synthetic and transformed-image tests vary parameters such as corner geometry, contrast, noise, affine warps, and blur to assess detector behavior.Prior studies report detection positions, true-positive rates, localization errors, false-positive rates, and false-negative rates under these changes.
- Human-labeled ground truth for real images introduces subjective decisions, and some prior consistency tests assess feature counts without determining corner quality.Other comparisons report only a single operating point rather than a complete ROC curve or equivalent.
- System-level results may not generalize because the best detector varies with the descriptor, scene type, lighting conditions, or downstream application.Evaluations using only part of a system are more general than application performance, but detector suitability can still depend on descriptors and lighting.
A. FAST: Features from Accelerated Segment Test
FAST detects corners by testing contiguous bright or dark segments on a sixteen-pixel circle around a candidate pixel. A high-speed preliminary test rejects many non-corners, but the detector has speed and redundancy limitations.
- FAST classifies a candidate pixel as a corner when a contiguous segment of n circle pixels is all brighter or darker than the center by threshold t.The original detector used n = 12 and examined a circle of sixteen pixels.
- The high-speed test first examines pixels 1 and 9, then pixels 5 and 13, rejecting candidates that cannot satisfy the segment criterion.For n = 12, at least three of these four tested pixels must be sufficiently bright or dark for the candidate to remain possible.
- The remaining candidates are tested by examining all pixels in the circle after the preliminary rejection stage.This preserves the full segment-test criterion for candidates that pass the faster test.
- For n < 12, the high-speed test rejects fewer candidates and may require additional tests to determine whether a complete bright or dark ring exists.The weaker condition permits a corner when only two of four pixels are both sufficiently bright or both sufficiently dark.
- Detector efficiency depends on question ordering and the distribution of corner appearances, while adjacent pixels may produce multiple detected features.The selected pixel ordering is unlikely to be optimal for every appearance distribution.
B. Improving generality and speed with machine learning
The paper learns decision-tree corner detectors from labeled image pixels to improve the FAST heuristic’s generality and speed. Information-gain recursion produces compact executable classifiers, while additional threshold procedures support corner-strength computation.
- Machine learning is used to address FAST’s generality and speed limitations, while repeatability optimization is handled separately.The learned detector is derived from the heuristic using training data from the target application domain.
- Each ring pixel is assigned one of three states—darker, similar, or brighter than the center pixel by threshold t—and partitions the training pixels into three subsets.The subsets are Pd, Ps, and Pb.
- An ID3-style decision tree recursively selects the pixel with maximum information gain about whether each candidate is a corner.Recursion stops when a subset has zero entropy, meaning all its examples share the same corner label.
- The resulting tree correctly classifies the training corners and approximately embodies the chosen FAST rules before conversion into compiled C code.Identical subtrees can be merged by removing the boolean test that separates them.
- Forcing the first selected pixels in the three branches to be equal enables parallel vectorized tests, and most points are rejected after two tests.This optimization produces a significant speed increase, though exact speed depends on the learned tree and processor architecture.
- The learned detector is not precisely identical to the segment-test detector because the training data incompletely covers all possible corners.For FAST-n, all 43,046,721 pixel combinations can be added with low weight so the learned detector exactly computes the segment-test criterion.
- Corner strength is defined as the maximum threshold t at which a point remains classified as a corner, found efficiently by exploiting monotonicity and bisection.An iterative threshold-increase scheme is an alternative, advancing t enough to change the decision-tree path until detection fails.
IV. MEASURING DETECTOR REPEATABILITY
The paper evaluates corner-detector repeatability by checking whether features correspond to the same real-world locations across views. A 3D scene model supports reprojection-based measurement across varied geometric and textural conditions.
- Measurement: Repeatability tests whether a feature detected in one image is also detected near the same real-world point in another view.The measurement uses a small pixel margin to accommodate imperfect alignment, calibration, and localization.
- Measurement: R is computed as the ratio of repeated features to useful features, summed across image pairs.This is equivalent to a useful-feature-weighted average of pairwise repeatabilities.
- Measurement: A 3D surface model determines where detected features should reproject in other views, including visibility and occlusion effects.Bas-relief textures are modeled with a plane to test non-affine viewpoint warps.
- Datasets: The datasets cover corners caused by polyhedral geometry, planar texture, non-affine relief, viewpoint changes, scale changes, and radial distortion.The collection was designed to capture a wide range of geometric and textural corner types.
- FAST-ER optimization: FAST-ER is learned by optimizing a ternary decision tree for repeatability, detector density, and tree size using simulated annealing.The detector is evaluated under rotations, reflections, and intensity inversion, then a single tree is generated for efficiency.
- FAST-ER optimization: Unlimited tree complexity can produce a degenerate solution that detects one repeated feature per training image.This makes repeatability trivially perfect, motivating explicit complexity and feature-count costs.
A. Parameters and justification
The optimization weights were selected through a parameter-sensitivity study over 27 combinations and 100 runs per combination. The reported settings were reasonable rather than demonstrably optimal.
- Justification: The chosen parameters are reasonable but not optimal because the search is high-dimensional, locally multimodal, and expensive to evaluate.The authors report that 100 repeats of a 100,000-iteration optimization required about 200 hours on a 3GHz Pentium 4.
- Parameter study: 27 parameter combinations varied w_r, w_n, and w_s across three values each to assess detector sensitivity.The combinations were evaluated using mean area under the repeatability curve across the box, maze, and bas-relief datasets.
- Parameter study: Score variation was low even though the parameters each varied by a factor of four.The Table I settings were close to the best tested parameter set.
VI. RESULTS
The evaluation compares FAST and FAST-ER with other detectors on repeatability and speed across viewpoint, lighting, blur, and additional dataset conditions. FAST-ER is trained on a small subset and tested on substantially more image pairs.
- Evaluation design: The Oxford dataset models image warps with homographies and contains eight sequences of six images each.It provides an additional test of detector repeatability under approximately planar scene transformations.
- Evaluation design: The comparison includes repeatability under viewpoint changes, lighting changes, and blur, using the number of corners per frame as a control.Random points provide a baseline measure for the repeatability experiment.
- Evaluation design: FAST-ER is trained on 3 images forming 6 image pairs and tested on 85 images forming 688 image pairs.The parameters are then used without modification on the Oxford dataset.
DoG
The evaluation compares corner detectors on repeatability across feature density, image noise, and scene deformation, while also considering processing speed. FAST-ER achieves the strongest overall repeatability, whereas detector performance depends on noise, density, and deformation conditions.
- Noise robustness: FAST-n is not robust to noise because its speed-oriented design analyzes few pixels and therefore averages out less noise.The noise-performance drop is initially rapid before leveling off, while DoG is described as remarkably robust to noise.
- Noise robustness: FAST-ER outperforms all other detectors for Gaussian noise levels σ < 7 in the noise evaluation.Its training parameters bias it toward detecting more corners at a given threshold, producing a higher threshold for a fixed feature count and reducing noise effects.
- Repeatability: As corner density increases, every detector eventually loses repeatability, but FAST-ER shows the least pronounced decline.This makes the choice of corner density less critical for FAST-ER than for the other detectors.
- Scene deformation: Harris and Shi-Tomasi perform especially well at very low densities below 100 corners per frame, while Shi-Tomasi is strongest when deformations are largely affine.On the bas-relief dataset, where the affine assumption does not hold, Harris outperforms Shi-Tomasi.
- Scene deformation: Harris-Laplace outperforms DoG and Harris on the box dataset up to about 1000 points per frame, but results are less convincing under non-projective changes.The cited evaluation concerns repeatability across different scene datasets.
B. Speed
The FAST family combines machine-learned decision trees with a focus on efficient processing and repeatability. FAST-ER extends this approach to improve repeatability while remaining computationally efficient.
- Speed: FAST is much faster than the other tested feature detectors, while learned FAST is roughly twice as fast as the handwritten version.
- Speed: FAST-9 and FAST-ER provide efficient learned detectors, with FAST-9 identified as the most reliable FAST-n detector.
- Speed: Despite its increased complexity, FAST-ER remains much faster than all tested detectors except FAST-n.
- Speed: FAST and FAST-ER consume only a fraction of available processing time on modern hardware and enable video-rate processing on low-power hardware.
- Conclusions: Machine learning turns the segment-test heuristic into FAST-9, combining unmatched processing speed with excellent repeatability.
- Conclusions: Generalizing the detector enables direct optimization for repeatability, producing FAST-ER with dramatic repeatability improvements over FAST-9, especially in noisy images.
- Conclusions: FAST-ER is computationally efficient, has better repeatability, and is more consistent under variation in corner density than any other tested detector.