Progressive Feature Matching: Incremental Graph Construction and Optimization

Abstract

We present a novel feature matching algorithm that systematically utilizes the geometric properties of image features such as position, scale, and orientation, in addition to the conventional descriptor vectors. In challenging scenes, in which repetitive structures and large view changes are present, it is difficult to find correct correspondences using conventional approaches that only use descriptors, as the descriptor distances of correct matches may not be the least among the candidates. The feature matching problem is formulated as a Markov random field (MRF) that uses descriptor distances and relative geometric similarities together. Assuming that the layout of the nearby features does not considerably change, we propose the bidirectional transfer measure to gauge the geometric consistency between the pairs of feature correspondences. The unmatched features are explicitly modeled in the MRF to minimize their negative impact. Instead of solving the MRF on the entire features at once, we start with a small set of confident feature matches, and then progressively expand the MRF with the remaining candidate matches. The proposed progressive approach yields better feature matching performance and faster processing time. Experimental results show that the proposed algorithm provides better feature correspondences in many challenging scenes, i.e., more matches with higher inlier ratio and lower computational cost than those of the state-of-the-art algorithms. The source code of our implementation is open to the public.