首页 | 本学科首页   官方微博 | 高级检索  
     

基于渐非凸渐凹化过程的子图匹配算法
引用本文:李晶,刘传凯,王勇,古楠楠,石锐,李琳. 基于渐非凸渐凹化过程的子图匹配算法[J]. 北京航空航天大学学报, 2015, 41(7): 1202-1207. DOI: 10.13700/j.bh.1001-5965.2014.0505
作者姓名:李晶  刘传凯  王勇  古楠楠  石锐  李琳
作者单位:1.中国酒泉卫星发射中心, 酒泉 732750
基金项目:国家自然科学基金(61305137)
摘    要:如何实现外点存在情况下的鲁棒高效匹配是图匹配领域的关键问题之一.针对此问题,提出将渐非凸渐凹化过程(GNCCP)用于子图匹配,即将外点存在情况下的图匹配问题建模为一个基于相似矩阵的二次组合优化问题,然后通过扩展GNCCP来近似优化,是一种新的采用二阶约束图匹配算法.相较于现有算法,提出的算法优势在于可以泛化目标函数定义方式,有效处理外点存在的情况的图匹配问题,且能同时实现有向图匹配和无向图匹配.人工数据与真实数据上的实验证实了算法的有效性. 

关 键 词:图匹配   组合优化   渐非凸渐凹化过程(GNCCP)   关键点对应   有向图
收稿时间:2014-08-11

Subgraph matching algorithm based on graduated nonconvexity and concavity procedure
LI Jing,LIU Chuankai,WANG Yong,GU Nannan,SHI Rui,LI Lin. Subgraph matching algorithm based on graduated nonconvexity and concavity procedure[J]. Journal of Beijing University of Aeronautics and Astronautics, 2015, 41(7): 1202-1207. DOI: 10.13700/j.bh.1001-5965.2014.0505
Authors:LI Jing  LIU Chuankai  WANG Yong  GU Nannan  SHI Rui  LI Lin
Affiliation:1.Jiuquan Satellite Launch Center, Jiuquan 732750, China2. College of Communication Engineering, Chongqing University, Chongqing 400044, China3. Beijing Aerospace Flight Control Center, Beijing 1000944. School of Astronautics, Harbin Institute of Technology, Harbin 150006, China5. College of Statistics, Capital University of Economics and Business, Beijing 100026, China
Abstract:To achieve robust and efficient matching with outliers is a fundamental problem in the field of graph matching. To tackle this problem, a novel subgraph matching algorithm was proposed, which was based on the recently proposed graduated nonconvexity and concavity procedure (GNCCP). Specifically speaking, the graph matching problem in the existence of outliers was firstly formulated as a quadratic combinatorial optimization problem based on the affinity matrix, which was then optimized by extending the GNCCP. This is a new second-order constraint graph matching algorithm. Compared with the existing algorithms, there are mainly three benefits for the proposed algorithm, which are as follows. Firstly, it has a flexible objective function formulation; secondly, it is effective in graph matching problems with outliers; thirdly, it is applicable on both directed graphs and undirected graphs. Simulations on both synthetic and real world datasets validate the effectiveness of the proposed method.
Keywords:graph matching  combinatorial optimization  graduated nonconvexity and concavity procedure (GNCCP)  point correspondence  directed graph
本文献已被 CNKI 万方数据 等数据库收录!
点击此处可从《北京航空航天大学学报》浏览原始摘要信息
点击此处可从《北京航空航天大学学报》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号