Image Feature Matching Using Nearest Neighbor Graph Model

With the rapid development of computer and information technology, image matching technology has become a very important technology in the field of computer vision, has extensive and practical applications in many fields, such as image retrieval, remote sensing image processing, object recognition and tracking, three-dimensional reconstruction, etc. Image matching based on feature has many advantages, such as small amount of calculation, good robustness, and is not sensitive to image deformation. So it has become a hot spot of current research. There be gray, rotation, perspective, scale change between images used for image matching and other factors, which leads to image matching problem with high complexity. So, the solution of the image matching problem remains a persistent and difficult task.Graph model can effectively describe structural information. Using the graph model representation method to solve the image feature point matching has been applied in many studies. In this thesis, using different nearest neighbor graph model to solve the problem of image feature point matching is studied. The main work is shown as follows:(1) The traditional Graph Transformation Matching (GTM) algorithm obtains good matching performance but returns little correct matches. To overcome this shortcoming, an Iterative Graph Transformation Matching (IGTM) algorithm is proposed. Generally, the proposed algorithm carries out the following steps:First, the algorithm generates the accurate correspondences from the initial one-to-one correspondence set by using GTM, whose process is similar to that in graph transformation matching algorithm; Then, it revises the initial correspondences by using the geometric relationship between the obtained correct matches and initial matches; Finally, based on the revised initial matches, the algorithm further searches the correct matches from the revised initializations by using graph transformation matching algorithm. Compared with GTM, the proposed algorithm explores the geometric relationship in the matching process and thus returns more accurate matches, which enhances the robustness of traditional GTM algorithm. Experimental results on real-world image database show that the proposed IGTM algorithm can significantly outperform GTM on the matching recall while retain the similar high matching precision.(2) Node importance measure is an important technology in complex network. We apply this technology to feature point matching, an image matching algorithm based on node importance measurement is proposed, which provides a new way for feature point matching algorithm research. The main idea of the algorithm is to utilize nearest neighbor graph model to represent the relationship between the matching correspondences, i.e., the vertices in the graph denote the correspondences. According to the similarity between correspondences to determine whether there is an edge between vertices. Due to the similarity between the correct matches is high, so, in the graph there are more edges are connected for correct matches, and have fewer edges for incorrect matches. Obviously, correct matches are more important than incorrect matches. Therefore, image feature matching problem can be implemented by measuring the importance of vertices in the graph. Upon the idea, two different nearest neighbor graph representation model and the corresponding node importance measurement are proposed. One is k-nearest neighbor (k-nn) graph model, using the spatial structure information between vertices to calculate the importance of vertices. The other is mutual k-nearest neighbor graph model, using vertex weighted degree information to measure the importance of vertices. Comparison experiment results on real-world image feature matching demonstrate the effectiveness and robustness of our algorithm.(3) The traditional image feature matching is just looking for the matching correspondence between image feature points, without digging deeper semantic information. This thesis gives a common visual pattern discovery algorithm based on cluster detection method. The algorithm not only obtains correct correspondence between two sets of visual feature points, but also indicates which correspondences belong to one pattern. A common visual pattern has coherent spatial layout, which is the noise and outliers do not have, and different visual patterns have different spatial layout. Therefore, in the mutual k-nn graph, matching correspondences within the same pattern are easy to form a tightly connected cluster, and different patterns have fewer edges to connect. Thus, visual pattern can be found through cluster detection technology. The relevant experiments on real image database verify the effectiveness of the proposed algorithm.