智能算法如何破解多图匹配的“传话游戏”迷局

20张从不同角度、在不同天气下拍摄的同一辆汽车的照片。如果让你找出每张照片里对应的车大灯、后视镜和车轮，你会通过整体结构轻松搞定。如果把这个任务交给计算机，它面对的就不是直观的画面，而是一堆由点（特征点）和线（点与点之间的相对位置）织成的“蜘蛛网”，在计算机科学中这被称为图（Graph）。让机器在多张复杂的图之间建立一一对应的正确连线，就是学术界极具挑战性的多图匹配（Multi-Graph Matching）难题。这项研究中，用一套充满大局观的“一致性驱动”机制，成功终结了多图匹配领域长期存在的“传话游戏”误差迷局。

过去，让计算机处理多张图片的匹配时，主流做法是：直接比对一堆图太难，先让图A和图B匹配，再让图B和图C匹配，以此类推。这种串行的两两匹配极易发生错误累积。就像玩传话游戏，第二个人听错了一点点（初始匹配误差），传到第20个人时，答案早就面目全非了（误差传播）。如果你换个顺序，先让图C和图B配对，最终算出来的答案可能和之前完全相反。这种缺乏全局统筹的算法，让计算机陷入了“前后矛盾”的死胡同。

为了打破这个僵局，这篇研究提出了一种统一的轮换优化框架（Alternating Optimization）。给计算机引入了两个极具智慧的“度量裁判”，让整个匹配过程完全脱离“盲人摸象”：

（1）全局一致性裁判（Graph-wise Consistency）-选出“靠谱组长”

算法在一开始，不会盲目决定以哪张图为主，而是会纵观全局，计算所有图的“大局观得分”。哪个图与其他所有图的底子最贴合、矛盾最少，它就会被选为参考图（Reference Graph），也就是这个团队的“组长”。有了核心组长，其他所有图只需要向组长看齐，原本复杂的乱网连线立刻变成了一个高效的“星型结构”。

（2）两两一致性裁判（Pairwise Consistency）-规划“发言顺序”

选出组长后，剩下的图要如何进行微调和迭代？算法并不会随机点名，而是通过“两两一致性”指标，算一算谁当前最不听话、错得最离谱。错得最厉害的图会被排在最前面优先更新调整。这种自适应的“排队机制”，不仅让算法收敛得极快，还从源头上掐断了错误在图与图之间传播的可能。

Fig. 1（a）展示了两张输入图之间复杂的“局部亲和度矩阵（Affinity Matrix）”。矩阵中的黑白方块代表了点与点、线与线之间错综复杂的几何相似度评分。Fig. 1（b）展示了框架的核心灵魂-以绿色圆圈为核心的“参考图（组长）”。算法在每一步迭代中，固定其他绝大部分图（Fixed graphs），集中精力只微调更新那张最需要纠错的“更新图（Updating graph）”。通过这种轮流切换（Alternating）的方式，将多图匹配问题完美降维简化。

实际计算中，计算机视觉的sub-problem（子问题）求解非常复杂（属于NP-complete难题）。机器在微调某一张图时，很有可能“聪明反被聪明误”，新算出来的连线得分反而不如上一轮。 针对这一点，论文增加了一个注重性价比的得分非递减路径选择策略（Score-non-descending path selection）。每次机器提出新方案时，裁判就会冷酷地比对新旧得分：只要新方案让整体的大局分退步了，这个方案就会被直接丢弃，继续维持原判。这确保了算法在进化过程中绝对不走回头路。

在论文的Fig. 2实验对比图中，展示了在变形（Deform）、干扰点（Outlier）和边密度（Density）等各种恶劣噪声下，不同策略的准确率（Accuracy）演进。图中采用了“一致性驱动+路径选择”的实线和虚线，其准确率随着迭代圈数（Iteration）的推进表现出陡峭的上升趋势，最终成果明显优于随机选择参考图的水平线。

这套框架还有一个特点-强大的灵活性与包容性。就像是一个万能的“主机箱”，市面上现有的各种优秀的pairwise（两两图匹配）求解器（比如经典的RRWM、GAGM、FGM等），都可以当成“显卡”直接插在这个机箱里使用（Out-of-box 方式）。

论文中，团队不仅在虚拟随机图上进行了严苛的测试，还用这套算法去Willow-ObjectClass（汽车、鸭子、摩托车等真实物体）以及CMU-POSE经典真实动态序列图像等真实赛场上测试。实验数据一致证明，不管里面插的是哪种图匹配solvers，只要套上这层“一致性驱动”的外壳，匹配的抗噪能力和准确率就会获得全方位的升级。

作者简介：严骏驰，上海交通大学人工智能学院教授（兼计算机科学与工程系），主要从事机器学习及其与组合优化、图学习、计算机视觉等方向的交叉研究。曾在 IBM Research（IBM研究院）任研究员/首席研究员多年，长期致力于将学习方法与组合优化、图匹配等问题相结合。

ORCID：0000-0001-9639-7679

DOI：10.1109/TIP.2014.2387386