图匹配算法及其在月面图片关键点匹配中的应用

CASIA OpenIR > 毕业生 > 博士学位论文

	图匹配算法及其在月面图片关键点匹配中的应用
	张宇仁
	2016-05
学位类型	工学博士
中文摘要	在很多计算机视觉问题中，图是表示结构特征的有效载体，而图匹配是获取图之间关系的重要方式。过去，由于受到计算机计算能力的限制，图匹配算法未能得到广泛的应用。目前，计算机计算能力不断提升，这使得图匹配算法能被高效地求解。与此同时，计算机视觉问题中涌现出越来越多的具有结构性的数据，因此进一步开展图匹配模型、算法以及应用的研究是必要的。关键点匹配是图匹配算法的典型应用，也是计算机视觉领域中的一个基础问题和重要组成部分。本论文中，结合月球车导航与控制中歧义性关键点匹配的实际应用问题，进行了一系列关于图匹配建模、算法和应用方面的研究，主要成果如下： 1. 为解决关键点匹配中歧义性局部特征所造成的问题，提出以权重共同子图匹配的方式对关键点匹配进行建模的方法。传统的基于图匹配的关键点匹配算法不直接求解共同子图匹配问题，而往往采用先匹配再排序的方式。相比之下本论文中直接对权重共同子图匹配问题进行建模，并使用凸凹松弛过程高效地求解，有效避免了先匹配后排序方式造成的误差。另外，针对月面图片的特性设计了对光照、尺度和旋转不变的有向边特征和相应的无向边特征，进一步弥补了传统结构约束的缺陷。 2. 提出了基于局部仿射不变性约束的图匹配算法。局部仿射不变性约束对尺度、方向等因素都具有鲁棒性，是构建图匹配目标函数的良好依据。本文中将它引入图匹配建模，并分别介绍了基于该约束子图匹配和共同子图匹配建模和优化方法。分析与实验证明新的图匹配算法与传统基于一、二阶约束的图匹配算法相比，能够有效提高图匹配算法的鲁棒性，且不会增加算法的复杂度。 3. 提出了基于权威性和枢纽性的子图匹配算法。首先，通过梳理谱图匹配算法的发展脉络，分析了其与基于谱方法的网页排序算法之间的共通与差异之处；在此基础上，通过借鉴经典网页排序算法 HITS 模型的核心思想，设计了新的基于谱分解的图匹配算法；通过引入权威性和枢纽性两个概念，使图匹配算法获得了对外点更强的鲁棒性。 4. 针对月球车长距离定位中图片关键点匹配的实际任务，提出了层级图匹配策略。基于这种策略可以有效考虑局部和全局的结构约束，从而应对月面图片中局部表观特征判别性弱和局部形变所造成的困难。同时，针对月面图片中难以提取关键点的问题，提出了服务于图匹配算法的特征点提取方法。最终，整个匹配问题最终在图匹配框架下被完整地求解。本论文中，不仅从算法的角度探索了图匹配算法的建模、约束和求解方法，还根据月面图片的特点针对性地设计了机制与策略，最终在月面图片匹配任务中取得了优异的效果，在理论和应用中都具有重要的意义。
英文摘要	Graph is an effective representation of structures in many computer vision prob- lems, and graph matching is a basic operation to acquire relations among graphs. In the past, the development and utilization of graph matching is constrained by the compu- tational power of computers. Recently, with the rapid growth of computational power, efficient application of graph matching method is becoming feasible. Besides, structures emerge in various computer vision problems. Due to the above reasons, it is imperative to conduct research on graph matching model,algorithm, and application. Key points correspondence is a typical application of graph matching. It is also a fundamental and crucial problem in computer vision field. In this thesis, we conduct a series of research on the modeling, algorithm, and appli- cation of graph matching algorithms, targeting at the practical application of matching ambiguous keypoints for the lunar rover’s navigation and control. The main contribu- tions of this thesis are as follows: 1. To address ambiguous keypoint matching problem on lunar surface images,we propose to model it with weight common subgraph matching. Traditional graph matching based keypoint correspondence methods do not model the common subgraph matching problem directly, but rather take the approach of ”ranking after matching”. We model the keypoint matching problem with common subgraph matching directly and solve it with an convex-concave relaxation based algorithm to avoid the error cased by the ranking. Besides, new edge directional features which is robust against illumination, scale and rotation is proposed targeted at lunar surface images to cover the shortage of traditional edge features. 2. A new constraint, locally affine invariance constraint, is introduced into graph matching. Locally affine invariance constraints in invariant to scale and orientation, and is also robust against deformation, which makes it a good constraint to construct graph matching problem. We introduce the modeling and solution of common subgraph matching algorithm and common subgraph matching algorithm based on locally affine invariance constraint. It is proved through analysis and experiment that the new graph matching algorithm performs better without incurring higher computational complexi- ty. 3. A novel spectral graph matching algorithm based on authority and hubness is proposed. The spectral graph matching methods are analyzed and compared with spectral webpage ranking algorithm. Inspired by the famous HITS model for webpage ranking, we propose a new spectral graph matching method incorporating authority and hubness. The new matching algorithm provided better robustness against outliers. 4. Targeted at the practical task of lunar surface image matching for long distance localization, we propose a new cascade graph matching strategy to fully utilize structure property of the keypoints. Based on the new strategy, both local and global constraint are considered such that the dependency on local appearance feature is alleviated. Furthermore, a keypoint detection protocol is proposed to serve the graph matching method for better performance. The matching problem is finally solved in a graph matching framework. In this thesis, we not only explore the modeling, constrains, and optimization method for graph matching from the viewpoint of algorithm, but also design scheme and strategy of graph matching according to the features of lunar surface images, and finally achieve excellent performance on the lunar surface matching task. Hence, the study has important meaning for both academic sense and applied value.
关键词	图匹配计算机视觉月面图片匹配组合优化
语种	中文
文献类型	学位论文
条目标识符	http://ir.ia.ac.cn/handle/173211/11618
专题	毕业生_博士学位论文
推荐引用方式 GB/T 7714	张宇仁. 图匹配算法及其在月面图片关键点匹配中的应用[D]. 北京. 中国科学院研究生院,2016.

条目包含的文件
文件名称/大小	文献类型	版本类型	开放类型	使用许可
201218014628109张宇仁.p（13871KB）	学位论文		限制开放	CC BY-NC-SA