Estimating the Number of Correct Matches Using Only Spatial Order

Area of Science:

• Computer Vision
• Image Processing
• Computational Geometry

Background:

• Accurate feature matching is crucial for computer vision tasks like Structure-from-Motion (SfM).
• Existing methods often require explicit computation of all matches, which can be inefficient.
• Robust estimation of correct matches is needed for reliable geometric reconstruction.

Purpose of the Study:

• To develop an efficient method for estimating the number of correct feature matches between image pairs without explicit computation.
• To leverage the spatial ordering of features for match quality assessment.
• To enhance computer vision pipelines by providing a faster and more accurate match validation mechanism.

Main Methods:

• Representing feature matches as sequences based on their spatial projection onto the x-axis.
• Utilizing Kendall and Spearman Footrule distance metrics to analyze permutations of these sequences.
• Applying the developed method as a halting condition for RANSAC, for discarding unrelated image pairs in SfM, and for probabilistic match correctness estimation.

Main Results:

• The proposed method efficiently estimates the number of correct feature matches.
• Significant speed-up (approx. 90%) in the image matching stage of SfM pipelines was achieved.
• Preservation of approximately 85% of spatially overlapping image pairs was demonstrated.
• The method provides a reliable way to assess match quality and relevance.

Conclusions:

• The novel approach of analyzing feature sequences with permutation distances offers an efficient alternative to explicit match computation.
• This method significantly enhances the performance of Structure-from-Motion pipelines by reducing processing time and improving pair selection.
• The technique is versatile, finding applications in RANSAC, SfM, and direct match quality assessment.