Point Pattern Matching And Its Application

Point Pattern Matching (PPM) is an important and fundamental issue in computer vision and pattern recognition, which is widely used in stereovision, autonomous navigation, medical imaging analysis, remote imaging registration, object recognition and tracking, drug design and DNA sequences prediction. It is a research hot spot in such kind of fields. Though lots of scholars are studying the issue, there is still no such a universal method and theoretic frame accepted, for research background restricted. Furthermore, PPM is a NP hard problem with outliers, noise and geometric distortion, which is still an open problem.On the research status quo of PPM,we start with constructing PPM algorithm framework, and propose a basic PPM algorithm framework (BF). Then the key problems and technologies of BF including matching evaluation function, feature extraction, matching & recognition, and geometric transformations and their parameters solving, are studied systematically in the thesis. Based on these, series of PPM algorithms are advanced under different geometric transformation on the BF, and at the same time, their applications on different categories are studied respectively. The survey of main content is as follow:1. After lucubrating on the existing PPM algorithms, we propose the BF, which has such universality that most of the algorithms can be regarded as an instance of the framework. And we can also construct series of algorithms based on the BF. Furthermore, key problems and technologies are studied in the thesis. We also discuss the corresponding theory of the framework and basic methods and ideas in the paper.2. Matching evaluation function is discussed in the thesis. PPM is formulated into an optimization problem of specific evaluation function. And Euclid distance measure,Hausdorff distance measure and maximum likelihood method are used to construct unrestricted evaluation function. The outlier restriction, correspondence restriction, geometric restriction, smoothing restriction on interpolation transformation model and corresponding theoretic problems are all well studied in the thesis. And their specific mathematic expressions are given out.3. Point's feature extraction in point set (PFE) is studied in the thesis. First, the conception of point's feature in point set (PF) is defined, and the basic requirement of PF is given out. Based on these, we advance the point's primitive character and feature extraction methods. The KL feature extraction method for PF (KL-PFE) is proposed. The paper reasons out that the KL-PFE is more universal than the PFE method in the classic eigenvector approach (spectral corresponding method), and gets some basic rules for PFE. Based on this, a sorting algorithm for PFE (SA-PFE) is presented. But the KL(SA)-PFE are fragile to outliers. To solve this problem, an orientation & distance based topology (ODT) method for PFE (ODT-PFE) is presented, which is robust to outliers. After that the paper naturally relates ODT-PFE with the state of art technology, Shape Context.4. Series of PPM algorithms based on the BF are proposed.(1) PPM algorithms based on KL (SA) feature are proposed which can solve the PPM problem under isometric, similarity and affine transformation. Then their application on stereovision matching is studied. The proposed algorithms are anti-noise but failed while outliers appear.(2) In order to match point patterns with outliers, soft matching algorithms are proposed based on ODT (SC) feature. And their application on space detector autonomous landing is studied. The methods are robust to outliers but can not solve PPM problem under higher dimensional transformation.(3) To realize PPM with noise and outliers under affine transformation, the Iterative Affine Parameter Estimation Algorithm for PPM (IAPEA) is proposed. Then, the paper applies IAPEA on pose estimation. IAPEA is an algorithm based on analytical method, and its defect is that it can't deal with PPM problem with serious transformation, bigger noise or large number of outliers.(4) In order to overcome the shortcoming of IAPEA, a random searching technology, swarm intelligence, is introduced to solve PPM problem. An algorithm based on ant colony optimization is proposed for affine PPM, which can handle with big noise and large number of outliers. And also an algorithm based on particle swarm optimization is proposed for projective PPM. At last, two algorithms are applied in fingerprint identification and aerial image mosaic respectively.(5) Two algorithms for non-rigid PPM are proposed. The paper deeply studies the non-rigid deformation, soft matching method and their relationship. Based on these, a soft matching framework for non-rigid PPM is given out. Then there are two specific instances proposed, namely space filter combined with deterministic annealing algorithm and space filter combined with relaxation labeling algorithm for non-rigid PPM. In the end, their applications on hand tracking and medical registration are studied respectively.