图匹配模型、算法及其在计算机视觉中的应用

CORC > 自动化研究所 > 中国科学院自动化研究所 > 毕业生 > 博士学位论文

题名	图匹配模型、算法及其在计算机视觉中的应用
作者	杨旭
学位类别	工学博士
答辩日期	2014-05-26
授予单位	中国科学院大学
授予地点	中国科学院自动化研究所
导师	乔红 ; 刘智勇
关键词	图匹配计算机视觉特征对应组合优化高阶约束结构模式识别 Graph matching computer vision feature correspondence combinatorial optimization high-order constraints structural pattern recognition
其他题名	Graph Matching Models, Algorithms and Their Applications in Computer Vision
学位专业	模式识别与智能系统
中文摘要	特征对应是计算机视觉领域的一个基础问题，很多重要的计算机视觉应用，比如二维/三维物体识别、三维重建、跟踪等，都是建立在已经确定特征间对应关系的基础上，但实际上如何实现鲁棒的特征对应仍是一个有挑战性的研究方向。特征对应问题可以通过图匹配来良好定义，通过将特征点及其描述子表示为图的顶点及其标签，特征点间的空间关系表示为图的边及其权重。由于图匹配算法普遍有较高的复杂度，它在计算机视觉领域的应用有一段低潮期。但是近年来，随着计算机硬件水平的提高、计算方式的改进，计算机的计算、存储能力逐步可以满足图匹配算法及其实际应用的要求。另一方面，计算机视觉领域产生了很多新的结构性数据的处理需求，同时引入结构约束也被认为是很多传统计算机视觉问题突破瓶颈的关键，因此开展图匹配模型、算法及其在计算机视觉中应用的研究是适逢其时的、必要的、也是可行的。我们针对该领域仍然存在的一些关键问题展开系列研究，取得了以下成果： (1) 针对现有结构模型判别性不足的问题，提出一种对几何变换鲁棒的有向结构模型，包括一种利用近邻约束的惩罚外点匹配的二次正则项，基于该有向结构模型将特征对应问题转化为有向图匹配问题，并针对同规模图匹配问题与子图匹配问题，分别提出基于凸凹松弛过程与渐非凸渐凹化过程的有向图匹配优化算法。 (2) 针对现有算法不能有效解决待匹配的两个图中均存在外点的问题，提出权重共同子图匹配的概念，并给出了建模与优化算法。不同于现有算法先匹配所有点，然后从中挑选最优匹配的思路，权重共同子图匹配将这两步融合在一个优化问题中，直接定位于寻找两个权重图中最相似的子图，从而解决了现有算法与原问题并不等价而导致匹配不鲁棒的问题。 (3) 针对目前高阶图匹配算法复杂度过高的问题，首次提出基于邻接张量的高阶图匹配算法，有效降低了高阶图匹配问题的运算复杂度与存储复杂度，尤其是在制约高阶图匹配算法应用的存储复杂度方面，将现有算法的O(N6<上标!>)存储复杂度降低到O(N3<上标!>)。 (4)面向月面图像处理的实际需求，根据月球车采集的月面图像的真实特点，提出一种概率解释的图匹配算法，并以此算法为核心提出月面图像对应的策略，对完成这一挑战性任务起到重要的推动作用。
英文摘要	Feature correspondence is a fundamental problem in computer vision, which lays the foundations for many important tasks, such as object recognition, 3D reconstruction, tracking. Feature correspondence can be well defined by graph matching, by representing the feature points by graph vertices, and representing the adjacency relations between feature points by edges. Furthermore the feature appearance descriptors can be assigned as labels to vertices, and the structural descriptors can be assigned as weights to edges. Since the graph matching algorithms usually involve high computational and storage complexities, they are not very popular in computer vision field for a long period of time. However, with the developments of computer hardware and computing forms, the computer computational and storage abilities are becoming more compatible with current graph based algorithms. On the other hand, there are increasing requirements for structural data processing, and incorporating structural cues is also considered as one important way to improve traditional computer vision methods. Generally speaking, it is necessary, feasible, and the right time to focus the research of graph matching algorithms and their applications in computer vision. Targeting on some key issues in this field, several research findings have been achieved in this dissertation, which are listed as follows. (1) To tackle the problem that existing structural models are lack in discriminating ability, we have proposed a directed structural model which is robust to object geometric transformations, together with a coherence term to deal with the outlier matching. Thus the correspondence problem is transformed into a directed graph matching problem. And for equal sized graph matching and subgraph matching, two optimization algorithms, which are respectively based on the convex-concave relaxation procedure (CCRP) and graduated nonconvexity and concavity procedure (GNCCP) are proposed. (2) We have proposed the concept of weighted common subgraph matching (WCS) to deal with the matching problem when both graphs containing outliers, together with the objective functions and corresponding optimization algorithms. A few existing algorithms which are also applicable on the WCS problem, typically first match all the vertices, and then select the best assignments, but it can be proved that such a two-step strategy is not totally equivalent with original problem. By contrast, the proposed WCS algorithm...
语种	中文
其他标识符	201118014628066
内容类型	学位论文
源URL	[http://ir.ia.ac.cn/handle/173211/6607]
专题	毕业生_博士学位论文
推荐引用方式 GB/T 7714	杨旭. 图匹配模型、算法及其在计算机视觉中的应用[D]. 中国科学院自动化研究所. 中国科学院大学. 2014.