留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

李晶 刘传凯 王勇 古楠楠 石锐 李琳

李晶, 刘传凯, 王勇, 等 . 基于渐非凸渐凹化过程的子图匹配算法[J]. 北京航空航天大学学报, 2015, 41(7): 1202-1207. doi: 10.13700/j.bh.1001-5965.2014.0505
引用本文: 李晶, 刘传凯, 王勇, 等 . 基于渐非凸渐凹化过程的子图匹配算法[J]. 北京航空航天大学学报, 2015, 41(7): 1202-1207. doi: 10.13700/j.bh.1001-5965.2014.0505
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)

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

doi: 10.13700/j.bh.1001-5965.2014.0505
基金项目: 国家自然科学基金(61305137)
详细信息
    作者简介:

    李晶(1982—),女,山东济宁人,工程师,jing_li@outlook.com

    通讯作者:

    刘传凯(1983—),男,山东潍坊人,工程师,chuankai.liu@gmail.com,主要研究方向为空间操作、视觉导航.

  • 中图分类号: TP391

Subgraph matching algorithm based on graduated nonconvexity and concavity procedure

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

     

  • [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.
  • 加载中
计量
  • 文章访问数:  477
  • HTML全文浏览量:  0
  • PDF下载量:  545
  • 被引次数: 0
出版历程
  • 收稿日期:  2014-08-11
  • 修回日期:  2014-11-20
  • 刊出日期:  2015-07-20

目录

    /

    返回文章
    返回
    常见问答