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

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

中文关键词  图匹配  多图匹配  增量匹配  高阶图匹配

英文关键词  graph matching  multiple graph matching  incremental matching  higher-order graph matching

中文摘要

      图匹配试图求解二图或多图之间节点的对应关系. 在图像图形领域, 图匹配是一个历久弥新的基础性问题. 从优化的角度来看, 图匹配问题是一个组合优化问题, 且在一般情形下具有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.