Fast rejecting mismatches using pair-wise similarity

Point matching problem seeks the optimal correspondences between two sets of points. However, the matching result often includes some mismatches that decrease the matching precision. In this paper, we propose a fast algorithm to reject mismatches using pair-wise similarity. The intuition of our algorithm is that the matches should be similar with their neighboring matches due to local consistency. Our algorithm consists of two steps. In the first step, the algorithm eliminates mismatches at the cost of rejecting some correct matches to obtain a refined matching result with a high precision. In the second step, the algorithm regains the correct matches rejected in the first step to improve the recall of the final matching result. The time complexity of the algorithm is O(n²), which is asymptotically faster than conventional algorithms that reject mismatches. We demonstrate the effectiveness of the proposed algorithm by multiple experiments over widely used datasets.