Advanced Search
Volume 41 Issue 7
Jul.  2015
Turn off MathJax
Article Contents
Journal of Beijing University of Aeronautics and Astronautics  > 2015  >  41(7): 1202-1207.
LI Jing, LIU Chuankai, WANG Yong, et al. 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(in Chinese)
Citation: LI Jing, LIU Chuankai, WANG Yong, et al. 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(in Chinese)
shu

Subgraph matching algorithm based on graduated nonconvexity and concavity procedure

doi: 10.13700/j.bh.1001-5965.2014.0505
  • 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 Date: 11 Aug 2014
  • Rev Recd Date: 20 Nov 2014
  • Publish Date: 20 Jul 2015
    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.

     

    • FullText(HTML)
  • loading
    • References(24)
  • [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.
    • Relative Articles
    • Supplements(0)
    • Cited By
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索
    Get Citation
    PDF
    XML

    Article Metrics

    Article views(741) PDF downloads(551) Cited by()
    Proportional views
    Related

    Copyright © Journal of Beijing University of Aeronautics and Astronautics

    Address: Editorial Department of Journal of Beijing University of Aeronautics and Astronautics, 37 Xueyuan Road, Haidian District, Beijing Post Code: 100191 Email: jbuaa@buaa.edu.cn

    Supported by: Beijing Renhe Information Technology Co., Ltd.    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return