Research Of Point Set Pattern Matching Based On Spectral Graph Method

Point pattern matching is an essential part of many computer version or pattern recognition tasks; it has very wide range of applications, and is currently the hotpot of various studies. Now, Point pattern matching is widely used in stereovision, autonomous navigation, object recognition and tracking, medical imaging analysis, remote imaging registration, drug design and DNA sequences prediction, etc. Spectral graph theory is applied to this problem have some advantages, such as high efficiency and good effect.This work analyzed the drawback of Scott and Longuet-Higgins method and Shapiro and Brady method, proposed a novel approach of spectral graph method. The most important part of this new method is constructing a new-type proximity matrix. This method does pretty well in the condition of large scale transformation and point-jitter of images, and has the advantages of graph spectral method: algorithmic complexity is better than iterative method proposed in last two decades. The new method proposed in this work were tested extensively in heterogeneous case, include synthetic data and real image taken from benchmark of computer version.This work summarizes the spectral graph methods about the matching algorithm in previous papers, and made some improvements and refinement, proposed an algorithm framework. The algorithm framework is divided into two steps, the first step is to choose a combination of distance function, the framework itself provides a set of improved distance function, and additional functions can also be added depending on the application requirement. The resulting distance function is the product of the selected function, this product give prominence to the distance functions that are appropriate for the particular application. The second step is to build the Gaussian weighted proximity matrix or Laplacian matrix for singular value decomposition. The advantages of this framework is algorithms can be generated according to the specific needs of applications, the framework have good flexibility in implementation, in each step, the generated code can be re-used, reduce the programming time.