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

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

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