基于几何约束的图匹配算法研究

摘要

近年来，随着模式识别和计算机视觉的发展，图匹配相关技术得到了广泛的关注。作为计算机视觉领域的基本问题，图匹配不仅用于科学研究，同时广泛应用于目标识别、物体跟踪、行为分析等领域。图匹配问题是指优化两个图节点之间的一致性关系。经过数十年的研究，已经产生大量的算法致力于解决图匹配问题，然而，由于该问题本身具有组合优化的性质，并且是个NP难问题，我们很难得到全局最优解。因此，大多数的算法都是通过求解近似最优解来解决图匹配问题的，研究的主要目标在于找到匹配准确率更高而且更快速的算法。
　　在本文中，对当前图匹配算法进行了充分的调研，主要将现有的图匹配算法分为两类，一类是基于离散域的优化方法，另一类是基于连续域的优化方法，而本文提出的基于几何约束的图匹配算法就是一种基于连续域的优化算法。事实上，图匹配问题容易受到外点以及形变噪声等因素的影响，针对于此，本文主要完成了以下工作，并采用Synthetic、CMU House等数据集进行了实验验证。
　　首先，分析了当前基于路径流的图匹配算法在求解优化过程中存在奇异点的问题;然后，为了解决奇异点对算法准确率的影响，提出了探索奇异点并在该点处探索多个路径分支的方法，以找到具有更优的匹配目标值的解路径的方法;其次，由于在采用解点路径估计的方法来探索奇异点时，会造成一定的计算消耗，因此，为了降低在探索奇异点时的计算消耗，并加速算法的收敛，提出了自适应步长的策略，在算法迭代过程中，对步长进行动态的调节来达到加速收敛的目的;最后，由于GNCCP(Graduated Nonconvexity and Concavity Procedure)算法也是一种基于路径流的图匹配算法，并且使用隐含的方式实现了部分图匹配问题，因此，在本文中，将前面所提出的一系列策略与GNCCP算法相结合，解决了GNCCP算法中存在奇异点的问题，提高了匹配的准确率。
　　实验结果表明，无论在匹配准确率方面，还是在匹配目标值方面，我们所提出的图匹配算法均实现了良好的匹配效果。

目录

声明

致谢

摘要

1 引言

1．1 研究背景及挑战

1．1．1 研究背景与意义

1．1．2 研究困难与挑战

1．2 国内外研究现状

1．3 论文主要研究内容

1．4 论文组织结构

2 图匹配相关理论介绍

2．1 图匹配问题的概述

2．1．1 图的基本概念

2．1．2 图匹配的基本概念

2．2 特征提取及图的构建

2．2．1 图像特征提取

2．2．2 图的构建

2．3 相似性度量方法

2．4 目标函数松弛形式

2．5 主流的图匹配算法

2．5．1 离散域优化方法

2．5．2 连续域优化方法

2．6 本章小结

3 基于几何约束的图匹配算法

3．1 问题的提出

3．1．1 基于路径流的图匹配算法

3．1．2 数值延拓法的理论内容

3．1．3 奇异点概述

3．2 算法详细内容

3．2．1 奇异点探索方法

3．2．2 分支切换方法

3．2．3 自适应步长策略

3．3 在GNCCP算法中的应用

3．3．1 GNCCP算法理论基础

3．3．2 算法详细内容

3．3．3 算法复杂度分析

3．4 本章小结

4 实验设计与分析

4．1 实验对比方法介绍

4．2 图匹配算法评价指标

4．3 实验结果与分析

4．3．1 实验设置

4．3．2 实验结果分析

4．4 本章小结

5．1 总结

5．2 展望

参考文献

作者简历及攻读硕士学位期间取得的研究成果

学位论文数据集