Research On The Algorithms For Point Pattern Matching Based On Spectral Method

The purpose of point pattern matching (PPM) is to find out the matching points between two related point sets, which research result is widely used in many areas, such as computer vision, computational biology and chemistry, etc. However, high complexity exists in PPM due to large difference between the two point sets to be matched, which make the PPM still an open problem by now. In this thesis, we make use of the spectral method to deal with the PPM problem. The main idea is to construct adjacency or Laplacian matrix of graphs on the feature point sets, and then get the corresponding eigenvalues and eigenvectors by performing the singular value decomposition (SVD) on the obtained matrix, that is the spectrum, which is used to solve the PPM problem.Based on the spectral method, we propose two matching algorithms in this thesis, the main work and research results are as follows:1. A point pattern matching method combined Laplacian spetrum with Hungarian algorithm is presented. The algorithm, which is based on the spectral method, firstly, construct Laplacian matrix on feature point sets of the images, respectively, and perform SVD on them. Secondly, an initial matching relation matrix is constructed by the results of the decomposition, and then transform the matrix by using Hungarian algorithm, which makes a minimum matching cost between two feature point sets. Finally, we can get a new matching matrix, which make the feature points match. The experimental results show the algorithm can get better matching results.2. Spectral correspondence for point pattern matching combined with the analysis of geometric consistency is proposed. Considered the traditional spectral matching algorithms which only consider the problem of attribute domain of the feature points, we propose an algorithm which combines the attribute domain the of the feature points with structure information. Firstly, spectral similarity between the matched point-sets is defined by the eigenvectors of Laplacian matrix. Secondly, an object function in hybrid form is given by incorporating geometric compatibility represented by neighborhood. Finally, the given object function is solved by utilizing probabilistic relaxation. Comparative experiments applied to synthetic data and real-world images demonstrate the proposed method possesses better precision and time performance.