top of page

Using Spatial Order to Boost the Elimination of Incorrect Feature Matches

Lior Talker, Yael Moses and Ilan Shimshoni

CVPR 16' Paper

C++ Code - Coming Soon...

Abstract:

Correctly matching feature points in a pair of images is
an important preprocessing step for many computer vision
applications. In this paper we propose an efficient method
for estimating the number of correct matches without explicitly
computing them. In addition, our method estimates
the region of overlap between the images. To this end, we
propose to analyze the set of matches using the spatial order
of the features, as projected to the x-axis of the image.
The set of features in each image is thus represented by a sequence.
This reduces the analysis of the matching problem
to the analysis of the permutation between the sequences.
Using the Kendall distance metric between permutations
and natural assumptions on the distribution of the correct
and incorrect matches, we show how to estimate the abovementioned
values. We demonstrate the usefulness of our
method in two applications: (i) a new halting condition
for RANSAC based epipolar geometry estimation methods
that considerably reduce the running time, and (ii) discarding
spatially unrelated image pairs in the Structure-from-
Motion pipeline. Furthermore, our analysis can be used to
compute the probability that a given match is correct based
on the estimated number of correct matches and the rank
of the features within the sequences. Our experiments on
a large number of synthetic and real data demonstrate the
effectiveness of our method. For example, the running time
of the image matching stage in the Structure-from-Motion
pipeline may be reduced by about 99% while preserving
about 80% of the correctly matched feature points.

bottom of page