计算机视觉中图匹配研究进展:从二图匹配迈向多图匹配  

Recent advance on graph matching in computer vision:from two-graph matching to multi-graph matching

作　　者：严骏驰 杨小康[2] YAN Jun-chi;YANG Xiao-kang(Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai 200240, China;Artificial Intelligence Institute, Shanghai Jiao Tong University, Shanghai 200240, China)

机构地区：[1]上海交通大学计算机科学与工程系,上海200240 [2]上海交通大学人工智能研究院,上海200240

出　　处：《控制理论与应用》2018年第12期1715-1724,共10页Control Theory & Applications

基　　金：国家自然科学基金项目(61602176)资助~~

摘　　要：图匹配试图求解二图或多图之间节点的对应关系.在图像图形领域,图匹配是一个历久弥新的基础性问题.从优化的角度来看,图匹配问题是一个组合优化问题,且在一般情形下具有非确定性多项式复杂程度(non-deter-ministic polynomial, NP)难度的性质.在过去数十年间,出现了大量求解二图匹配的近似算法,并在各个领域得到了较为广泛的应用.然而,受限于优化问题本身的理论困难和实际应用中数据质量的种种限制,各二图匹配算法在匹配精度上的性能日益趋近饱和.相比之下,由于引入了更多信息且往往更符合实际问题的设定,多图的协同匹配则逐渐成为了一个新兴且重要的研究方向.本文首先介绍了经典的二图匹配方法,随后着重介绍近年来多图匹配方法的最新进展和相关工作.最后,本文讨论了图匹配未来的发展.Graph matching refers to the problem of finding vertex correspondence among two or multiple graphs, which is a fundamental problem in computer vision and computer graphics. As a combinational optimization problem, graph matching is NP-hard in general settings. Classic two-graph matching has met its limitations in matching accuracy because of its NP nature and limits in data qualities. In contrast to the classic two-graph matching setting, until recently matching multiple graphs with consistent correspondences start to emerge for their practical usefulness and methodological potential for further innovation. Starting by a brief introduction for traditional two-graph matching, we walk through the recent development of multiple graph matching methods, including details for both models and algorithms. Finally, several directions for future work are discussed.

关 键 词：图匹配 多图匹配 增量匹配 高阶图匹配 

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]