The Research And Application Of Algorithm For Point Pattern Matching In Three-dimensional Space

As the development of technology, our world becomes more and more smart. In many fields, we demand to match two images or recognize some information in an image. Thus, image matching becomes a basic technique in many applications.In a long term, a lot of studies focused on gray level image matching, and got some good results. But it was hard to match big images in real time environments. Aimed to overcome this weak point, part of studies tried to use feature based matching. As the simplest feature, the point pattern, which is extracted from the borders and corners or other significant parts of the image, becomes more and more popular. This kind of method is called point pattern matching.Because the task of point pattern matching focus on the significant points, point pattern matching is much faster and more robust than using gray level pixel points. Due to its powerful advantage, varies of algorithms were applied in point pattern matching. In these methods, shape context is really successful and has already been used in many fields. The shape context descriptor is a feature descriptor with rich information, the feature of one point depends on the relative positions with other points. Shape context was designed with translation invariance and robust with small noise, this is very important in point pattern matching. If we do standardization before extracting the descriptor, and add a tangent orientation for each point, we can also get scale and rotation invariance.Even though the shape context is a very powerful method, it has some shortages. Firstly, shape context is only for two dimensional matching space, there is no intuitive method to get the shape context descriptor in three or higher dimensional matching space. In addition, shape context is not good at matching the points with big angle rotation, big noise and outliers. Some studies improved shape context by adding more features or combining it with other algorithms, and these were exactly worked very well. The improved methods can be used in the point sets with big angle rotation, and also performed much better with noise and outliers. However, few studies try to establish a three dimensional point pattern model based on shape context.The main work of this paper is that we present a novel method to solve three dimensional point pattern matching problem based on shape context. Despite of the descriptor born with translation and scale invariance, we also solved three dimensional rotation very well. We calculated the center of mass and the relative positive point of the point set as the invariance points. Two invariance points and one current point, three dimensional rotation can be solved with three points. Then we use a ball domain to cover the whole point set, after we divided the ball with some cutting tactics, the number of the points in each small domain could be the feature descriptor of the current point. Using modified chi-square test to evaluate the similarity of two points. The similarity is measured by the matching cost between two points. Having a matching cost matrix, the point pattern matching problem could be converse into bipartite graph minimum weight matching. Then we use Kuhn-Munkres algorithm to solve bipartite graph matching, the result of bipartite graph matching is the result of our point pattern matching.In order to test the performance of our proposed method, we designed the comparative experiments with synthetic point sets and real data sets respectively. The result demonstrated that three dimensional point pattern matching problem can be solved by the proposed algorithm, and the performance is better than other algorithms.The proposed method is effective and robust. It could be a basis algorithm in three dimensional point pattern matching. The performance might be improved by combining it with other methods. The thinking of these designs might be utilized in higher dimensional point pattern matching.