文章快速检索 高级检索

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

Subgraph matching algorithm based on graduated nonconvexity and concavity procedure
LI Jing1,2, LIU Chuankai3, WANG Yong1,4, GU Nannan5, SHI Rui2, LI Lin2
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
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
﻿

1 公式化方法

M=N时,X退化为一个置换矩阵.

GH的相似矩阵可以按照以下形式构建：

xX按行抽取的复制,并同时以此更新离散域的定义D1

2 优化算法

x←Frank-Wolfe(x,A,η)

ηη+δη

y←argmax yTFη(x),s.t. yC1

λ←argmax Fη(x+λ(y-x)),

s.t. 0≤λ≤1

yx+λ(y-x)

3 实验比较

3.1 人工数据集

 图 1 人工数据集上的实验结果 Fig. 1 Experimental results of artificial datasets
3.2 真实数据集

 图 2 真实数据集上的实验结果 Fig. 2 Experimental results of real datasets

4 结 论

 [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. Click to display the text [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. Click to display the text [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. Click to display the text [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. Click to display the text [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. Click to display the text [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. Click to display the text [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. Click to display the text [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. Click to display the text [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. Click to display the text [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. Click to display the text [12] Liu Z Y. Graph matching: A new concave relaxation function and algorithm[J].Acta Automatica Sinica, 2012, 38(5): 725-731. Click to display the text [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. Click to display the text [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. Click to display the text [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. Click to display the text [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. Click to display the text [18] Yang X, Qiao H, Liu Z Y.Partial correspondence based on subgraph matching[J].Neurocomputing, 2013, 122: 193-197. Click to display the text [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. Click to display the text [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. Click to display the text [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. Click to display the text

文章信息

LI Jing, LIU Chuankai, WANG Yong, GU Nannan, SHI Rui, LI Lin

Subgraph matching algorithm based on graduated nonconvexity and concavity procedure

Journal of Beijing University of Aeronautics and Astronsutics, 2015, 41(7): 1202-1207.
http://dx.doi.org/10.13700/j.bh.1001-5965.2014.0505