Comparative evaluation of 2D feature correspondence selection algorithms

Chen Zhao, Jiaqi Yang, Yang Xiao, Zhiguo CaoarXiv 2019 · arXiv

Overview

This paper provides a comprehensive benchmarking study of eight prominent 2D feature correspondence selection algorithms. By evaluating both classical parametric methods and modern non-parametric approaches across four diverse datasets, the authors offer a practical guide for developers. The findings indicate that while no single algorithm dominates every scenario, Vector Field Consensus (VFC) offers the best overall robustness, while Grid-based Motion Statistics (GMS) is the clear winner for real-time applications.

The Challenge of Feature Matching

In computer vision, "feature matching" is the process of finding corresponding points between two images—a critical step for tasks like 3D reconstruction (SfM), SLAM, and image stitching. The standard pipeline involves detecting keypoints, describing them with vectors (like SIFT or ORB), and matching them based on similarity.

However, this raw matching process is notoriously "noisy." External factors like lighting changes, blur, and viewpoint shifts often result in a high number of "outliers" (false matches). Correspondence selection algorithms act as a filter to keep only the "inliers" (correct matches). While many algorithms exist, developers often struggle to choose the right one because most are tested in isolation or under very specific conditions. This paper fills that gap with a rigorous, head-to-head comparison.

Methods

The authors evaluate eight algorithms, categorized into two families:

Parametric Methods

These assume matches must fit a specific geometric model, such as a homography or fundamental matrix.

  • RANSAC: The classic "hypothesize-and-verify" approach.
  • USAC: A modern, "universal" framework that optimizes every step of the RANSAC pipeline.

Non-parametric Methods

These rely on more general constraints like local geometric consistency or motion smoothness.

  • NNSR (Nearest Neighbor Similarity Ratio): A simple descriptor-based filter.
  • ST (Spectral Technique) & GTM (Game Theory Matching): Methods using affinity matrices to find consistent clusters.
  • VFC (Vector Field Consensus): Treats matching as a vector field interpolation problem.
  • GMS (Grid-based Motion Statistics): A high-speed method that counts matches in small neighborhoods.
  • LPM (Locality Preserving Matching): Focuses on maintaining the local neighborhood structure of points.

Experimental Setup and Datasets

The study utilizes four standard datasets to simulate various real-world "nuisances":

  • VGG: A hybrid dataset covering blur, viewpoint change, zoom, rotation, and JPEG compression.
  • Symbench: Focuses on extreme lighting changes and different rendering styles (e.g., matching a photo to a painting).
  • Heinly: Specifically targets large-scale zoom and rotation.
  • AdelaideRMF: Contains "multi-structure" scenes where objects move at different depths, creating parallax that breaks simple geometric assumptions.
Sample images from the four evaluation datasets: (a) VGG, (b) Symbench, (c) Heinly, and (d) AdelaideRMF.

Comparative Performance Analysis

The benchmarking reveals that performance is highly dependent on the "inlier ratio" and the specific type of image distortion.

Robustness and Precision

VFC and RANSAC emerged as top performers across the widest variety of datasets. NNSR provides high precision (the matches it keeps are usually correct) but very low recall (it throws away too many good matches). Conversely, LPM offers high recall, making it useful when a dense set of correspondences is required. The study also found that using NNSR to prune matches before applying more complex algorithms significantly boosts the performance of parametric methods like USAC.

Efficiency and Real-time Performance

GMS is orders of magnitude faster than the competition, capable of processing thousands of matches in milliseconds. This makes it the ideal choice for mobile or robotics applications where computational resources are limited.

Quantitative comparison of precision, recall, and efficiency (F-measure vs. Time) across the VGG, Symbench, and Heinly datasets.

Handling Complex Geometry

Parametric methods like RANSAC and USAC excel when the scene is a flat plane, but they struggle significantly with "multi-structure" scenes (AdelaideRMF) where multiple geometric models exist simultaneously. In these cases, non-parametric methods like VFC and LPM significantly outperformed parametric ones, which often failed to converge on a single correct model.

Conclusion

The study concludes that there is "no free lunch" in correspondence selection. Developers should choose algorithms based on their specific constraints: VFC for general robustness, GMS for speed, and NNSR for high-precision pre-filtering. Future research should focus on handling extremely low inlier rates (below 10%), potentially through deep learning-based approaches that can model more complex, non-linear deformations.

Summary updated

Abstract

Correspondence selection aiming at seeking correct feature correspondences from raw feature matches is pivotal for a number of feature-matching-based tasks. Various 2D (image) correspondence selection algorithms have been presented with decades of progress. Unfortunately, the lack of an in-depth evaluation makes it difficult for developers to choose a proper algorithm given a specific application. This paper fills this gap by evaluating eight 2D correspondence selection algorithms ranging from classical methods to the most recent ones on four standard datasets. The diversity of experimental datasets brings various nuisances including zoom, rotation, blur, viewpoint change, JPEG compression, light change, different rendering styles and multi-structures for comprehensive test. To further create different distributions of initial matches, a set of combinations of detector and descriptor is also taken into consideration. We measure the quality of a correspondence selection algorithm from four perspectives, i.e., precision, recall, F-measure and efficiency. According to evaluation results, the current advantages and limitations of all considered algorithms are aggregately summarized which could be treated as a "user guide" for the following developers.
BibTeX
@misc{zhao2019comparative,
  author = {Chen Zhao and Jiaqi Yang and Yang Xiao and Zhiguo Cao},
  title = {{Comparative evaluation of 2D feature correspondence selection algorithms}},
  year = {2019},
  eprint = {1904.13383},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1904.13383},
}
Figure