| In the1960s, Computer Pattern Recognition grows rapidly and soon develop into a new science. Now it has a wide range of applications, including computer vision, natural language processing, biological characteristics identification, search engine of internet, surveying, etc. As one of the most fundamental and crucial content of Pattern Recognition, the task of Point Pattern Matching(PPM) is to match the point pairs from two images which meet a certain geometric transformation by a certain Point Pattern Matching algorithm, so the object is identified or located. Due to its powerful advantage, PPM is widely used in biological characteristics identification (face recognition and iris recognition), medical image analysis and registration, handwriting recognition, remote sensing image registration, attitude estimation, computational biology and chemistry (protein structure identification and DNA sequence matching) etc.From the complexity of computational, point pattern matching problem can be summed up to two features that influence complexity, namely the matching degree and prior information. According to the two characteristics, the PPM problem can be divided into four kinds with different difficulty. Obviously, if there have enough prior information or a one to one correspondence, the matching becomes very simple. The point pattern studied in this paper is most complex, in which two sets cannot match completely and points has no priori information. Analysis and summarize the existing point pattern matching technology, we can divide these algorithms into two categories:the matching algorithm based on transformation and the matching algorithm based on matching relation. In this paper, we first introduce the PSO algorithm based on transformation, and then take some study and improvement on the algorithm based on matching relation.The algorithm based on the matching relation is also called algorithm based on feature matching, and this kind of method include spectral graph theory method, method based on the shape description operator (SC), etc. But in the calculation of the characteristics of point, the traditional SC algorithm determine the direction of polar coordinate by the tangential of point, and when the point set is rotating, the position of the point changes, so the effect is very poor. The improved RSC algorithm determine feature by the relative characteristics of two points, it can deal with small angle rotation, but when there is a big rotation (that is, the location of the point changes), the feature histogram dislocates, and thus the effect is also poor. In addition, neither SC no RSC can fully present the local message, which could weaken the influence of noise and interference point.In order to solve the limitation of the above algorithm, this paper put forward a new CSC descriptor based on the center point to describe the characteristic of point. In the CSC descriptor, the selection of the center point determines the position of point in the whole point sets, and the local information is highlighted by the special coefficient. Then we structure a weighted binary map of the PPM problem, solve the binary map with KuhnMunkres algorithm, and apply this algorithm to bioinformatics. The main work is as follows:First, I read a lot of literature and some books related to this problem. Reading some writings, to understand PPM problem and the research status of PPM technology, and write related algorithm program code with the matlab language.Second, the existing point pattern matching algorithms are analyzed and summed up. We put forward two kinds of algorithm based on two basic relationship between existed in point patterns, and also show the basic framework. Two classical algorithms is also be expressedThen, we analysis the insufficient of existing shape context algorithms (SC and CSC), and put forward a global CSC-KuhnMunkres algorithm. The feasibility and superior are proved through experiments. When there is a big rotation Angle or some interference of noise and revolutionary point, the matching rate of CSC-KuhnMunkres algorithm is much higher than the traditional SC and RSC algorithm. In addition, the algorithm does not need iteration and can be calculate directly, so the complexity of algorithm is greatly reduced.Finally, after studying the3D point pattern matching, we decrease the dimension and decompose complicated problem to simple problem. A new TCSC-KM algorithm based on CSC-KuhnMunkres is put forward to match the3D point sets. Experiments demonstrate that this method has got a fine consequence. |
