基于渐非凸渐凹化过程的子图匹配算法

《基于渐非凸渐凹化过程的子图匹配算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、2015年7月北京航空航天大学学报July2015第41卷第7期JournalofBeijingUniversityofAeronauticsandAstronauticsV01．41No．7http：??bhxb．buaa．edu．ca、buaa@buaa．edu．cnDOI：10．13700／j．bh．1001-5965．2014．0505基于渐非凸渐凹化过程的子图匹配算法李晶1’2，刘传凯”，王勇1’4，古楠楠5，石锐2，李琳2(1．中国酒泉卫星发射中心，酒泉732750；2．重庆大学通信工程学院，重庆400044；3．北京航

2、天飞行控制中心，北京100094；4．哈尔滨工业大学航天学院，哈尔滨150006；5．首都经济贸易大学统计学院，北京100026)摘要：如何实现外点存在情况下的鲁棒高效匹配是图匹配领域的关键问题之一．针对此问题，提出将渐非凸渐凹化过程(GNCCP)用于子图匹配，即将外点存在情况下的图匹配问题建模为一个基于相似矩阵的二次组合优化问题，然后通过扩展GNCCP来近似优化，是一种新的采用二阶约束图匹配算法．相较于现有算法，提出的算法优势在于可以泛化目标函数定义方式，有效处理外点存在的情况的图匹配问题，且能同时实现有向图匹配和无向图匹配．人工

3、数据与真实数据上的实验证实了算法的有效性．关键词：图匹配；组合优化；渐非凸渐凹化过程(GNCCP)；关键点对应；有向图中图分类号：TP391文献标识码：A文章编号：1001-5965(2015)07．1202．06图匹配是指在一定最优性条件下，寻找两个图顶点间的匹配关系．它是计算机视觉与模式识别领域的一个基础问题，在很多具体任务，如图形图像识别⋯、跟踪旧1、行为识别¨。中有重要应用．图匹配算法在计算机视觉与模式识别领域的应用研究已经有40多年的历史”。．从算法的角度来看，一般将图匹配分为精准图匹配与非精准图匹配，其中精准图匹配是指图

4、(或其一部分)之间满足严格的结构一致性，即匹配后图(或其一部分)的顶点标签、边的邻接关系及权重完全一致．非精准图匹配是指允许匹配后的图(或其一部分)存在一定的顶点标签，边的邻接关系及权重的误差，通过定义一种误差度量方式并最小化，来寻找最优的图(或其一部分)之间的对应关系．从应用角度讲，在计算机视觉应用中，由于物体形变、遮挡、视角变换、图像采集传输过程中的噪声等客观原因，从图像中提取的图结构之间往往不可避免地存在差异，因此在这些任务中非精准图匹配算法的应用更为普遍．不同于早期的非精准图匹配算法，如基于树搜索并采用编辑距离作为误差度量的

5、算法¨1，近年来非精准图匹配算法的一个显著特点是基于一个良好定义的目标函数。6。0

6、．具体来说，目标函数的形式可以分为基于邻接矩阵的目标函数㈧8。9’“川和基于相似矩阵的目标函数"'10’13。14

7、．其中基于邻接矩阵的目标函数通常利用两个权重邻接矩阵分别存储两个待匹配权重图的边的邻接关系及权重，然后将图匹配问题转换成为两个权重邻接矩阵的匹配．采用这种形式的目标函数的一个主要优势在于较低的存储复杂度．与此不同，近年来很多算法采用基于相似矩阵的目标函数，其优势在于更为灵活的边的相似度量方式的定义，比如可以采用高斯核的形式．而且当待匹配

8、的图较为稀疏时，采用基于相似矩阵的目标函数的图匹配算法同样具有可接受的存储复杂度与计算复杂度．此外，基于相似矩阵的目标函数更容易推收稿日期：2014-08一11；录用日期：2014·11-20；网络出版时间：2014—12-0910：12网络出版地址：WWW．cnki．net／kcms／detail／11．2625．V．20141209．1012．001．html基金项目：国家自然科学基金(61305137)作者简介：李晶(1982一)，女，山东济宁人，工程师，jing—li@outlook．corn+通讯作者：刘传凯(1983一)

9、，男，山东潍坊人，工程师，chuankai．1iu@gmail．corn，主要研究方向为空间操作、视觉导航．引用格式：李晶，刘传觊，王勇，等．基于淅非凸渐凹化过程的子图匹配算法fJJ．北京航空航天大学学报。2015，41(7)：1202·1207．Li)，LiuCK，WangY，ota1．Subgraphmatchingalgorithmbasedongraduatednonconvexltyandconcavityprocedure【)j．JourealofBeljingUniversityofAeronauticsandAstr

10、onautics，2015，41(7)：1202-1207(inChinese)．第7期李晶，等：基于渐非凸渐凹化过程的子图匹配算法1203广到高阶图匹配算法，事实上，现有高阶图匹配算法采用的目标函数均为基于相似矩阵的目标函数在高阶约