Feature Matching Based On Graph Structure

Establishing consistent correspondences between two sets of visual features is an essential problem in computer vision and pattern recognition,which is generally formulated and solved by graph matching.Graph matching aims to find a mapping between the nodes of two graphs that preserves the relationships between the nodes as much as possible.Graph matching is widely used in various applications,such as image retrieval,object recognition,object categorization and feature tracking.Graph matching is usually formulated as a quadratic assignment problem(QAP).Since QAP is NP-complete,graph matching is also NP-complete.The existing graph matching methods are commonly divided into exact and approximate graph matching methods.Exact graph matching methods are usually more complex and time-consuming than approximate ones.Moreover,exact graph matching methods are not robust to noise or variation in real world graphs.Therefore,we focus on approximate graph matching methods.This paper proposes a graph matching method based on mixed multiple relations.Considering the limitation of the traditional way of computing the compatibility,an improved compatibility based on weighted local and global information for graph matching is proposed.In addition,graph matching can be considered an optimization problem,so we use the belief propagation(BP)algorithm to solve the problem to obtain the optimal solution.This paper proposes a graph matching method based on mixed multiple relations.The relative relations of image features in local space remain unchanged after deformation,including unary relation,binary relation and ternary relation.The unary relation is the relationship of feature points.The binary relation is the compatibility of the two matching pairs.The ternary relation is the similarity of two triangles from the three matching pairs.This paper obtains the initial feature matching through the mixed multiple relations for graph matching.Considering the above procedure can not get the compete matching,the method of computing the transformation matrix based on the least squares and then obtaining the corresponding point position based on the transformation matrix is proposed for compete matching.This paper performs experiments on some data sets to demonstrate that our method is effective in graph matching.This paper proposes an improved compatibility based on weighted local and global information for graph matching.Because the traditional way of computing the compatibility based on the Euclidean distance does not consider the direction information and topology information of global features,the compatibility can not be better to express the relationship of the matching pairs.An improved compatibility based on weighted local and global information for graph matching is proposed for the problem.The Euclidean distance and direction information are considered to compute the local compatibility.The global central point is introduced to compute the global compatibility and then the problem of computing the compatibility of two matching pairs is translated into the problem of computing the compatibility based on the topology information of the three matching pairs.This paper uses the matching accuracy and objective score as the evaluation criterion and compares with the state-of-the-art graph matching algorithms.Experimental results demonstrate that our method is robust for rotation,scaling and deformation.This paper proposes a novel method for graph matching based on belief propagation.Graph matching can be considered an optimization problem and an objective function based on energy function is proposed,so we use the BP algorithm to obtain the optimal solution for graph matching.To match the nodes of the two graph,we first model this graph matching problem with an MRF,and then use the BP algorithm to approximate the marginal probability for graph matching.For each node,we select the node within another graph that has the largest matching probability to the node as its matching node.To achieve the one-to-(at most)-one matching constraint,we present a method for removing bad matches based on the topological structure of the graphs.We obtain the sets of reliable matching pairs,and form the vector description of nodes based on the special relationship between nodes.The node that has the largest similarity is the matching node.This paper uses the matching accuracy and objective score as the evaluation criterion and compares with the state-of-the-art graph matching algorithms.Experimental results demonstrate that our method is effective and stable in graph matching.