Adaptive Graph Matching

Establishing correspondence between point sets lays the foundation for many computer vision and pattern recognition tasks. It can be well defined and solved by graph matching. However, outliers may significantly deteriorate its performance, especially when outliers exist in both point sets and meanwhile the inlier number is unknown. In this paper, we propose an adaptive graph matching algorithm to tackle this problem. Specifically, a novel formulation is proposed to make the graph matching model adaptively determine the number of inliers and match them, then by relaxing the discrete domain to its convex hull the discrete optimization problem is relaxed to be a continuous one, and finally a graduated projection scheme is used to get a discrete matching solution. Consequently, the proposed algorithm could realize inlier number estimation, inlier selection, and inlier matching in one optimization framework. Experiments on both synthetic data and real world images witness the effectiveness of the proposed algorithm.