A novel clique formulation for the visual feature matching problem

Abstract

© 2015, Springer Science+Business Media New York. This paper presents CCMM (acronym for image Clique Matching), a new deterministic algorithm for the visual feature matching problem when images have low distortion. CCMM is multi-hypothesis, i.e. for each feature to be matched in the original image it builds an association graph which captures pairwise compatibility with a subset of candidate features in the target image. It then solves optimum joint compatibility by searching for a maximum clique. CCMM is shown to be more robust than traditional RANSAC-based single-hypothesis approaches. Moreover, the order of the graph grows linearly with the number of hypothesis, which keeps computational requirements bounded for real life applications such as UAV image mosaicing or digital terrain model extraction. The paper also includes extensive empirical validation.