Surface Rough Matching Algorithm Based on Maximum Weight Clique

A surface rough matching algorithm is presented. The algorithm converts surface matching problem into maximum weight clique searching problem in graph theory, and the optimal point correspondence set is represented by the maximum weight clique. The algorithm includes point matching, point correspondence graph construction, and maximum weight clique generation. In point matching stage, both high curvature points and uniform sampling points are selected as the candidate points, then we do point matching by spin-image method, and get the initial point correspondence set. In point correspondence graph construction stage, we construct graph edges by compatibility constraints including distance constraint, normal constraint and uniqueness constraint, and construct the vertex weight by correlation coefficient of spin-images. In maximum weight clique generation stage, we use branch and bound based clique searching algorithm to find the maximum weight clique representing the optimal correspondences. Experimental result demonstrates the algorithm is robust, effective and extensible, and capable of dealing with partial surface matching problem and featureless surface matching problem.