三维图匹配算法

Three-dimensional graph matching algorithm

目的现有的图匹配算法大多应用于二维图像,对三维图像的特征点匹配存在匹配准确率低和计算速度慢等问题。为解决这些问题,本文将分解图匹配算法扩展应用在了三维图像上。方法首先将需要匹配的两个三维图像的特征点作为图的节点集;再通过Delaunay三角剖分算法,将三维特征点相连,则相连得到的边就作为图的边集,从而建立有向图;然后,根据三维图像的特征点构建相应的三维有向图及其邻接矩阵;再根据有向图中的节点特征和边特征分别构建节点特征相似矩阵和边特征相似矩阵;最后根据这两个特征矩阵将节点匹配问题转化为求极值问题并求解。结果实验表明,在手工选取特征点的情况下,本文算法对相同三维图像的特征点匹配有97. 56%的平均准确率;对不同三维图像特征点匹配有76. 39%的平均准确率;在三维图像有旋转的情况下,有90%以上的平均准确率;在特征点部分缺失的情况下,平均匹配准确率也能达到80%。在通过三维尺度不变特征变换(SIFT)算法得到特征点的情况下,本文算法对9个三维模型的特征点的平均匹配准确率为98. 78%。结论本文提出的基于图论的三维图像特征点匹配算法,经实验结果验证,可以取得较好的匹配效果。

Objective Graph matching involves establishing a one-to-one correspondence between the feature points of two images on the basis of graph theory.As a basic problem in computer vision,graph matching is closely related to many computer vision areas,such as object tracking,image classification,object recognition,contour matching,and so on.Existing graph matching algorithms are mostly applied to two-dimensional images,and many problems,such as low accuracy rate and slow calculation speed,remain in matching feature points from three-dimensional images.To solve these problems,this study generalized the factorized graph matching algorithm to three-dimensional images.Method The three-dimensional graph matching method comprises five main steps.In the first step,the feature points of the two three-dimensional images that must be matched are used as the node set of the graph.Then,the three-dimensional feature points are connected by the Delaunay triangulation algorithm,and the obtained edges are used as the edge sets of the graph to establish the directed graph.In the second step,the starting node matrix is computed on the basis of the structure of the directed graph,and each element with a value of 1 represents the starting node of the edge in the graph.The ending node matrix can be computed in the same manner.The starting node matrix and the ending node matrix can be combined to represent which node of each edge in the graph is initiated and which node is terminated.In the third step,we use the graph’s degree and eccentricity as the node’s feature to build node feature vectors.We also use the edge length and the angle between the edge and the plane XOY as the edge’s feature to build edge feature vectors.The node feature adjacency matrix can be calculated according to the node feature vectors.The number of matrix rows is equal to the number of one graph’s nodes.The number of matrix columns is equal to the number of the other graph’s nodes.The value of each element in the matrix can be calculated on the basis of the Euclidean distance between corresponding nodes from the two graphs and represents the degree of similarity between two nodes in the graphs.Similarly,the edge feature adjacency matrix can be calculated on the basis of edge feature vectors.The node feature adjacency matrix and edge feature adjacency matrix can be used to delineate the degree of similarity between nodes and edges from two graphs.In the fourth step,using the starting node matrix,ending node matrix,node feature adjacency matrix,and edge feature adjacency matrix,we can build a special matrix K to transform the threedimensional graph matching problem into a problem of solving a node matching matrix X to maximize an equation J.In the fifth step,the maximum value solution of equation J is a quadratic assignment Problem;therefore,we use the path following algorithm to obtain the optimal solution by splitting the equation J into a series of concave and convex expressions and then find the optimal solution X by iterative approximation.The solution matrix X is the node matching matrix and represents the feature point matching result from two three-dimensional images.Result We tested and validated our method in five experiments.In the first experiment,we manually picked 102 feature points from a three-dimensional image in the dataset that comprised nine three-dimensional car images and had a 97.56%average accuracy rate in feature point matching from the same three-dimensional images.In the second experiment,we achieved a 76.39%average accuracy rate from the feature point matching from different three-dimensional images from the dataset.In the third experiment,we rotated the three-dimensional images every 10°from 10°to 180°and matched all 102 manually selected feature points from the same three-dimensional images;the average accuracy rate of matching was 90%.In the fourth experiment,we randomly removed several feature points from the three-dimensional images.During the removal,the accuracy rate of matching decreased.Nevertheless,removing a maximum of 30 feature points still yielded an 80%accuracy rate of matching.In the first four experiments,we used the manually selected feature points from the three-dimensional images;furthermore,we validated our method on the feature points automatically obtained by the 3 D scale-invariant feature transform(SIFT)algorithm and achieved a 98.78%average accuracy rate in the feature point matching of the three-dimensional images.Conclusion The three-dimensional image feature point matching algorithm based on graph theory proposed in this work was tested and validated by five experiments.Results indicate that our method can achieve good matching results for manually selected feature points and automatically calculated feature points.