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请求全文
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[张宇仁]的文章
百度学术
百度学术中相似的文章
[张宇仁]的文章
必应学术
必应学术中相似的文章
[张宇仁]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。