CODE: Coherence Based Decision Boundaries
for Feature Matching

Introduction

A key challenge in feature correspondence is the difficulty in differentiating true and false matches at a local descriptor level. This forces adoption of strict similarity thresholds that discard many true matches. However, if analysed at a global level, false matches are usually randomly scattered while true matches tend to be coherent (clustered around a few dominant motions), thus creating a coherence based separability constraint. This paper proposes a non-linear regression technique that can discover such a coherence based separability constraint from highly noisy matches and embed it into a correspondence likelihood model. Once computed, the model can filter the entire set of nearest neighbour matches (which typically contains over 90% false matches) for true matches. We integrate our technique into a full feature correspondence system which reliably generates large numbers of good quality correspondences over wide baselines where previous techniques provide few or no matches. Paper, C++ Code Libraries, 2010, 2013 Matlab Code

Idea

CODE matching is based on a simple observation. True matches tend to move in a coherent manner while wrong matches tend to be randomly scattered. This forms a motion consistency constraint which can be exploited to to differentiate true and false matches. To exploit this constraint, we develop an efficient non-linear regression which can rapidly compute a match constituency score from a very noisy set of feature matches. As the match consistency score takes the form of a continuous curve, it can be computed from a small set of matches and extrapolated across the entire image. This allows our CODE matching to scale to very large numbers of features.

To build a complete system, we integrate CODE matching with a powerful GPU A-SIFT feature matcher. The result is a highly effective wide-baseline feature matcher. Link to timing information A-SIFT.

Results

Visualisation	Precision	Recall	F-number
NRDC feature matching	0.75	0.48	0.59
Mode Seeking	0.23	0.97	0.38
CODE matching	1	0.95	0.97

Evaluation on the ETH toys dataset. Precision is the percentage of image pairs where the matcher correctly determines if there exist common elements in both frames. Recall is the percentage of image pairs with common elements which are detected. Observe that CODE matching has both high precision and recall.

Observe that CODE scales easily to very large numbers of features. This is because it estimates a continuous function defining the score of every possible match. This makes match verification very fast as it only requires reading of the score.