智能多图匹配算法如何让计算机精准“找同款”

几十张从不同角度、在不同光照下拍摄的同一座古建筑的照片。如果让你把每张照片里的同一个窗户、同一根柱子一一对应地连线找出来，虽然费点眼神，但对人类大脑来说并不是难事。如果把这个任务交给计算机，可能会立刻抓狂。在计算机视觉领域，这个让机器在多张图片中寻找对应特征点的技术，被称为多图匹配（Multi-Graph Matching）。这篇论文提出了一种聪明的“渐进式”算法，成功破解了多图匹配中长期存在的计算误差和噪声干扰难题：

为了让计算机理解图片，先提取出一些关键的特征点（比如建筑的屋角、窗户的边缘）。如果只看孤立的点，计算机很容易认错。于是，科学家在这些点之间连上线，把它们织成一张“几何网”，这就是图（Graph）。连线不仅代表点和点之间的连接，还记录了它们之间的距离、角度等几何结构信息。图匹配的核心任务：就是要把第一张图的“蜘蛛网”，完美地扣在第二张图的“蜘蛛网”上，实现点对点、线对线的精准重合。

当匹配的图片从两张变成一堆（多图匹配）时，难度呈指数级上升。多图匹配需要满足两个互相制约的指标：

（1）局部亲和度（Affinity）：两张图之间两两比对，看起来越像，亲和度越高。

（2）全局一致性（Consistency）：这是多图匹配的铁律。简单来说，如果图A中的某个点匹配到了图B的点1，图B的点1匹配到了图C的点2，那么图A的这个点直接匹配图C时，必须也指向点2。这就好比一个闭环，不能出现前后矛盾。

此前，科学界在处理这两个指标时，经常陷入两个极端：

（1）有些方法在一开始就强行要求所有图片必须满足“全局一致性”。这就像在一场未经调查的传话游戏中，第一个人传错了话（初始匹配误差），后面的人为了保持“队伍一致”，只能跟着错下去，导致误差在迭代中被无限放大。

（2）另一些方法先不管全局，让每两张图自己去配对（优化亲和度），最后再用数学方法强行把结果“抹平”拧成一个闭环（光谱平滑技术）。这种方法在后期平滑时，完全抛弃了图片本身的特征相似度信息，结果往往不尽如人意。

为了打破这个僵局，作者提出了一个解法：基于组合的亲和度优化与渐进式一致性正则化（CAO-C算法），就像一场侦探破案的过程：

（1）破案前期（前几次迭代）：侦探们（计算机）主要依靠现场发现的蛛丝马迹（局部亲和度评分）来寻找线索，因为此时直觉和表面相似度最能提供有效信息。这时候不需要设定太死板的规矩（一致性权重极低或为0）。

（2）破案后期（随着迭代深入）：随着各种线索逐渐丰富，表面看起来像的东西可能开始混淆视听。此时，侦探开始逐步加强逻辑审查（逐渐提高一致性的权重）。用严格的“闭环逻辑”去修正那些前后矛盾的局部错误线索。

由于每次都计算全局的大闭环非常消耗算力（复杂度高达 O(N⁴ⁿ)），作者还非常贴心地设计了两种高效的变体算法：CAO-UC（节点一致性）和CAO-PC（两两一致性）。它们就像是在团队里设立了“组长”或“两两监督机制”，在大幅降低计算复杂度的同时，依然保持了极高的匹配准确率。

实际应用中，图片往往没那么干净。比如拍一辆车，背景里还会有树木、路人或者路灯。这些不属于目标的点被称为离群点（Outliers）。如果强行让它们参与匹配，就会变成派对里的捣蛋鬼，把原本正确的匹配搞得一团糟。

论文的另一个重大贡献，是设计了一套内点提取机制（Inlier Eliciting Mechanism）：

（1）算法会对每个节点进行“逻辑审查”，计算节点一致性（Node-wise Consistency）或节点亲和度。

（2）那些真正属于物体的点（内点），在多张图里都能对得上，得分自然高；而背景里乱入的点，前后逻辑无法自圆其说，得分就会很低。

（3）最终，算法会像筛沙子一样，把得分低的背景点直接“戴上口罩”屏蔽掉（置为0），只让真正有用的目标点参与核心计算。

为了验证这套算法到底厉害不厉害，研究团队在虚拟数据集和真实图像库上都进行了严苛的测试。

在 Fig. 1 的各项随机图测试中，可以直观地看到随着图像变形（Deform）加剧或干扰点（Outlier）增多，代表本文提出方法（如红色、粉色、橙色等 CAO 家族曲线）的准确率（Accuracy）始终稳居上方，明显优于传统的RRWM等基准方法。而在计算时间（Time）对比中，高效变体算法展现出了极佳的性价比。

研究团队还把算法应用到了现实世界的照片中，比如 CMU 的房屋和酒店序列照片（含有不同视角变化），以及著名的 WILLOW 真实物体数据集（包含鸭子、汽车、摩托车等近百张跨越不同场景的真实照片）。

在Fig. 7的视觉结果中，绿线代表正确的配对，红线代表错误的配对，白点代表被算法成功揪出来的背景干扰点（Outliers）。可以看到，无论是面对视角转动极大的汽车（Car）、还是形状各异的鸭子（Duck），CAO-C* 算法下的画面几乎全被代表正确的绿线铺满，而其他对比方法（如 MPM、MatchLift）则出现了明显的红线交错或误配。

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

ORCID：0000-0001-9639-7679

DOI：10.1109/TPAMI.2015.2477832