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

doi:10.13700/j.bh.1001-5965.2014.0505

北京航空航天大学学报 ›› 2015, Vol. 41 ›› Issue (7): 1202-1207.doi: 10.13700/j.bh.1001-5965.2014.0505

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

李晶^1,2, 刘传凯³, 王勇^1,4, 古楠楠⁵, 石锐², 李琳²

1. 中国酒泉卫星发射中心, 酒泉 732750;
2. 重庆大学通信工程学院, 重庆 400044;
3. 北京航天飞行控制中心, 北京 100094;
4. 哈尔滨工业大学航天学院, 哈尔滨 150006;
5. 首都经济贸易大学统计学院, 北京 100026

收稿日期:2014-08-11 修回日期:2014-11-20 出版日期:2015-07-20 发布日期:2015-07-30
通讯作者: 刘传凯(1983—),男,山东潍坊人,工程师,chuankai.liu@gmail.com,主要研究方向为空间操作、视觉导航. E-mail:chuankai.liu@gmail.com
作者简介:李晶(1982—),女,山东济宁人,工程师,jing_li@outlook.com
基金资助:
国家自然科学基金(61305137)

Subgraph matching algorithm based on graduated nonconvexity and concavity procedure

LI Jing^1,2, LIU Chuankai³, WANG Yong^1,4, GU Nannan⁵, SHI Rui², LI Lin²

1. Jiuquan Satellite Launch Center, Jiuquan 732750, China;
2. College of Communication Engineering, Chongqing University, Chongqing 400044, China;
3. Beijing Aerospace Flight Control Center, Beijing 100094;
4. School of Astronautics, Harbin Institute of Technology, Harbin 150006, China;
5. College of Statistics, Capital University of Economics and Business, Beijing 100026, China

Received:2014-08-11 Revised:2014-11-20 Online:2015-07-20 Published:2015-07-30

摘要/Abstract

摘要： 如何实现外点存在情况下的鲁棒高效匹配是图匹配领域的关键问题之一.针对此问题,提出将渐非凸渐凹化过程(GNCCP)用于子图匹配,即将外点存在情况下的图匹配问题建模为一个基于相似矩阵的二次组合优化问题,然后通过扩展GNCCP来近似优化,是一种新的采用二阶约束图匹配算法.相较于现有算法,提出的算法优势在于可以泛化目标函数定义方式,有效处理外点存在的情况的图匹配问题,且能同时实现有向图匹配和无向图匹配.人工数据与真实数据上的实验证实了算法的有效性.

关键词: 图匹配, 组合优化, 渐非凸渐凹化过程(GNCCP), 关键点对应, 有向图

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.

Key words: graph matching, combinatorial optimization, graduated nonconvexity and concavity procedure (GNCCP), point correspondence, directed graph

中图分类号:

TP391

李晶, 刘传凯, 王勇, 古楠楠, 石锐, 李琳. 基于渐非凸渐凹化过程的子图匹配算法[J]. 北京航空航天大学学报, 2015, 41(7): 1202-1207.

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 A, 2015, 41(7): 1202-1207.

参考文献

[1] Leordeanu M, Hebert M, Sukthankar R.Beyond local appearance: Category recognition from pairwise interactions of simple features[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition.Piscataway, NJ: IEEE Press, 2007: 1-8.
[2] Jiang H, Yu S X, Martin D R.Linear scale and rotation invariant matching[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(7): 1339-1355.
[3] Brendel W, Todorovic S.Learning spatiotemporal graphs of human activities[C]//Proceedings of IEEE International Conference on Computer Vision.Piscataway, NJ: IEEE Press, 2011: 778-785.
[4] Conte D, Foggia P, Sansone C, et al.Thirty years of graph matching in pattern recognition[J].International Journal of Pattern Recognition and Artificial Intelligence, 2004, 18(3): 265-298.
[5] Tsai W H, Fu K S.Error-correcting isomorphisms of attributed relational graphs for pattern analysis[J].IEEE Transactions on Systems, Man and Cybernetics, 1979, 9(12): 757-768.
[6] Umeyama S. An eigendecomposition approach to weighted graph matching problems[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 1988, 10(5): 695-703.
[7] Leordeanu M, Hebert M.A spectral technique for correspondence problems using pairwise constraints[C]//Preceedings of the IEEE International Conference on Computer Vision.Piscataway, NJ: IEEE Press, 2005, II: 1482-1489.
[8] Zaslavskiy M, Bach F, Vert J P.A path following algorithm for the graph matching problem[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(12): 2227-2242.
[9] Liu Z Y, Qiao H, Xu L.An extended PATH following algorithm for graph matching problem[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(7): 1451-1456.
[10] Gold S, Rangarajan A.A graduated assignment algorithm for graph matching[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 1996, 18(4): 377-388.
[11] Almohamad H, Duffuaa S.A linear programming approach for the weighted graph matching problem[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 1993, 15(5): 522-525.
[12] Liu Z Y. Graph matching: A new concave relaxation function and algorithm[J].Acta Automatica Sinica, 2012, 38(5): 725-731.
[13] Egozi A, Keller Y, Guterman H.A probabilistic approach to spectral graph matching[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(1): 18-27.
[14] Torresani L, Kolmogorov V, Rother C.A dual decomposition approach to feature correspondence[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(2): 259-271.
[15] Torr P H S. Solving markov random fields using semi definite programming[C]//Proceedings of Artificial Intelligence and Statistics, 2003.
[16] Liu Z Y, Qiao H.A convex-concave relaxation procedure based subgraph matching algorithm[J].Journal of Machine Learning Research: W&CP, 2012, 25: 237-252.
[17] Liu Z Y, Qiao H.Graduated nonconvexity and concavity procedure for partial graph matching[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014, 36(6): 1258-1267.
[18] Yang X, Qiao H, Liu Z Y.Partial correspondence based on subgraph matching[J].Neurocomputing, 2013, 122: 193-197.
[19] Zhou F, De La Torre F.Factorized graph matching[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Piscataway, NJ: IEEE Press, 2012: 127-134.
[20] Frank M, Wolfe P.An algorithm for quadratic programming[J].Naval Research Logistics Quarterly, 1956, 3(1-2): 95-110.
[21] Jaggi M. Revisiting frank-wolfe: Projection-free sparse convex optimization[C]//Proceedings of the 30th International Conference on Machine Learning (ICML-13).[S.l.]: International Machine Learning Society, 2013: 427-435.
[22] Kuhn H W. The Hungarian method for the assignment problem[J].Naval Research Logistics Quarterly, 1955, 2(1-2): 83-97.
[23] Boyd S, Vandenberghe L.Convex optimization[M].Cambridge: Cambridge University Press, 2004: 464-466.
[24] Leordeanu M, Sukthankar R, Hebert M.Unsupervised learning for graph matching[J].International Journal of Computer Vision, 2012, 96(1): 28-45.

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

Subgraph matching algorithm based on graduated nonconvexity and concavity procedure

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 11

编辑推荐

Metrics

本文评价

[1]	李红, 张志宾. 基于快速模拟退火的组合聚类算法[J]. 北京航空航天大学学报, 2019, 45(8): 1646-1652.
[2]	石山, 刘德鹏, 李成茂. 基于改进粒子群优化算法的飞机作动系统功率调度[J]. 北京航空航天大学学报, 2016, 42(10): 2024-2030.
[3]	谭昌柏, 匡衡. 基于动态规划的飞机多交点装配离散公差优化[J]. 北京航空航天大学学报, 2015, 41(5): 802-810.
[4]	张诚, 马华东, 傅慧源. 基于时空关联图模型的视频监控目标跟踪[J]. 北京航空航天大学学报, 2015, 41(4): 713-720.
[5]	曹涛, 董长虹. 基于组合优化策略的月球软着陆最优轨道设计[J]. 北京航空航天大学学报, 2012, (11): 1537-1541.
[6]	张淳,秦世引,赵丹培,刘尊言. 基于星图匹配的小视场空间图像畸变校正[J]. 北京航空航天大学学报, 2008, 34(09): 1016-1019.
[7]	庄朝文, 富立, 滕继涛, 范跃祖. 车辆导航系统中超前滞后校正方法[J]. 北京航空航天大学学报, 2004, 30(07): 640-643.
[8]	高鹏, 富立, 范跃祖. 车辆组合导航定位系统中测量元件的参数修正[J]. 北京航空航天大学学报, 2003, 29(8): 730-733.
[9]	高鹏, 富立, 范跃祖. GPS/DRS/DMAP汽车定位导航系统[J]. 北京航空航天大学学报, 2002, 28(6): 699-702.
[10]	彭飞, 柳重堪, 张其善. 基于代价函数的组合导航系统地图匹配算法[J]. 北京航空航天大学学报, 2002, 28(3): 261-264.
[11]	苏惠敏, 周鹏, 陈哲. 基于D-S证据理论的GPS/MM组合系统车辆定位算法[J]. 北京航空航天大学学报, 2001, 27(2): 157-160.