三维图匹配算法  

Three-dimensional graph matching algorithm

作　　者：孟琭[1] 魏子然 Meng Lu;Wei Ziran(College of Information Science and Engineering,Northeastern University,Shenyang 110000,China)

机构地区：[1]东北大学信息科学与工程学院,沈阳110000

出　　处：《中国图象图形学报》2019年第5期794-804,共11页Journal of Image and Graphics

基　　金：国家自然科学基金项目(61101057)~~

摘　　要：目的现有的图匹配算法大多应用于二维图像,对三维图像的特征点匹配存在匹配准确率低和计算速度慢等问题。为解决这些问题,本文将分解图匹配算法扩展应用在了三维图像上。方法首先将需要匹配的两个三维图像的特征点作为图的节点集;再通过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 t

关 键 词：图匹配 三维图像处理 图论 路径跟踪算法 人工智能 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]