Graphical Models With Application In Point Pattern Matching

Point pattern matching(PPM) is an important and foundational issue in pattern recognition and computer vision. Its research result is widely used in many areas, such as imge processing, object recognition and tracking, computational Chemistry, astronomy, etc. However, high comlexity exists in PPM due to large difference between the two point sets to be matched. By now, PPM is still an open problem, which is a hot topic many researchers focus on.Graphical model is an effective fashion to express structural information. Many attentions are focused on the way to process the PPM problem with graphical models, which is also the main direction to deal with the PPM problem. We utilize several different graphical models and different graphical-model-denoted ways to deal with the PPM problem. The main contents and innovations are as follows:1. A point pattern matching algorithm based on Q-spectra of line graph is proposed. Firstly, a weighted completed graph is constructed for each point set; Secondly, a line graph is constructed for each point with the first k shortest edges, and then spectral decomposition is performed on the signless Laplacian matrix associated with the line graph. The eigenvalues(Q-spectra) obtained form the spectral decomposition are used to represent the point's feature, and the matching probability is calculated; Finally, the optimal matching is found by KM algorithm as the final matching result. The proposed algorithm can obtain a better matching result under translation, zoom and rotation etc., and also can deal with the matching problem of the two point sets in different size. Experimental results show that the effectiveness of the proposed algorithm.2. An algorithm for point pattern matching is proposed, which combines local relative shape context and Q-spectra. Firstly, a line graph is constructed for each point, and the spectral decomposition is performed on the signless Laplacian matrix of line graph; Secondly, the eigenvalues obtained from the spectral decomposition are used to represent the point's feature, and the initial matching probability is calculated; Thirdly, a descriptor named local relative shape context is defined to compute the similarity diatance between any two points; Finally, Q-spectra method is combined with local relative shape context via a probabilistic relaxation approach to get the matching result. Experimental results indicate that the proposed algorithm has a higher accuracy. 3. An algorithm based on QR decomposition (orthogonal-triangular decomposition) is described. Firstly, a weighted complete graph is constructed for each point set; Secondly, QR decomposition is performed on the weighted adjacent matrices associated with the two weighted complete graphs, then the orthogonal matrices obtained from QR decomposition are used to match the two point sets. Thirdly, in order to improve the matching accuracy, we propose a simple method for incorrect matches detecting relied on the correspondence of the first K similar neighbors of the matched pairs. Finally, the frame work of iterative detecting and matching is established to get the matching result. The proposed algorithm, when applied to a wide experimental data, has shown higher accuracy and can achieve a better matching result under large affine transformation.4. A point pattern matching algorithm based on the spectra of directed graphs is presented. Firstly, two weighted complete graphs are constructed with feature points extracted from the two images; Secondly, a method for edge orienting is proposed to transform each weighted complete graph to a directed graph; Thirdly, two skew-symmetric matrices associated with respective directed graphs are established; Fourthly, spectral decomposition is performed on the two skew-symmetric matrices to get a spectral representation of the feature points with half of the eigenvectors; The final matching result is obtained by comparing the spectral representation of each point. We theoretically analyze that our algorithm can well deal with the matching problem under affine transformation. The expreiments applied to synthetic data and real-world images show the effectiveness of our method. Moreover, as an application of this algorithm, we apply it to remote sensing image registration, the result is satisfying.