计算机图像匹配的三十年演变史

有没有玩过手机上的“全景拍照”？拿着手机转动一圈，咔哒一声，一张气势磅礴、毫无裁剪痕迹的超宽幅风景照就诞生了。或者，当你走在街上打开手机导航，实景AR功能会自动把箭头精准地贴在真实的马路上。

在这些神奇技术的背后，其实隐藏着计算机视觉领域最核心、最基础的一项看家本领——图像匹配（Image Matching）。简单来说，它就像是计算机在玩一场高难度的“连线游戏”：在两张或多张从不同角度、不同时间、甚至不同拍摄设备拍下的照片里，找出哪些部分代表的是同一个东西，并把它们牢牢地连在一起。

这篇论文梳理了这项让计算机拥有“火眼金睛”的技术在过去三十年里的进化史——从人类专家用数学公式精心雕刻的“手艺活”，到如今让AI自己去悟的“深度学习”。为了让你清晰直观地了解这门技术的宏大架构，论文作者在开篇就给出了这张清晰的“全景思维导图”：

这张图展示了图像匹配的完整生命周期。整个过程就像一条精密的流水线，从最左边的“特征检测（寻找关键点）”，到中间的“特征描述（给关键点办身份证）”，再到核心的“匹配方法（连线与纠错）”，最后延伸到右侧的SfM（三维重建）、SLAM（机器人定位导航）等丰富应用。

在AI大爆发之前，要教会计算机认出两张照片里的“同款物体”，科学家们只能依靠纯手工设计的规则。这被称为手工特征时代（Handcrafted Features）。这个时期的计算机玩连线游戏要经历两个极其严苛的步骤：

（1）特征检测（Feature Detection）：面对一张几百万像素的照片，计算机不可能去挨个对比每个像素。而是去寻找那些最特殊的地方，比如两条线交叉的“角点”（Corner），或者像肚脐眼一样的“斑点”（Blob）。

角点派：比如经典的Harris算法，专门寻找图像中亮度变化剧烈的边缘交叉点。

斑点派：比如享誉世界的SIFT算法（尺度不变特征变换），通过模拟人类眼睛看物体“远近皆可认出”的原理，在图像的各种缩放尺度下寻找最稳定的圆形斑点区域。

（2）制作“数字身份证”：特征描述（Feature Description）：找到点还不够，计算机很容易把“左眼的关键点”错连到“右眼”上。为了不认错，计算机必须给每一个找到的点办理一张独一无二的“身份证”——用一串高维度的数学向量，记录这个点周围像素的梯度变化和纹理特征。比如SIFT算法就会把一个点周围的秘密编成一个128维的数字身份证，只要身份证对得上，两张图里的点就能连上线。这种手工设计的特征非常经典，甚至在今天依然广泛应用于各种轻量级设备中。然而，人类的经验是有极限的。当遇到白天到黑夜的剧烈光照变化，或者极端的拍摄角度倾斜时，手工设计的身份证往往就会“失灵”，导致连线游戏彻底崩溃。

随着深度学习（Deep Learning）的席卷，科学家们开始让神经网络（CNN）自己去图片里找规律呢？图像匹配进入了可学习特征时代（Learnable Features）。

AI展现出了令人惊叹的“视觉直觉”。像 SuperPoint、LF-Net 这样的现代算法，不再像传统方法那样生硬地去计算几何导数，而是直接吞下整张图片，通过数以万计的场景数据训练，自己去感悟图片里哪些地方最容易被重复识别，哪些特征最适合用来做身份证。更厉害的是，现在许多算法将“寻找关键点”和“办身份证”合二为一（端到端训练），AI在给自己做关键点标记的同时，就已经把极其强悍、能抵抗黑夜和角度变化的身份证做好了。这种从“人工设计”到“AI自悟”的转变，让计算机图像匹配的准确率实现了质的飞跃。

无论是手工特征还是AI特征，在第一轮盲目连线后，结果往往惨不忍睹。因为图片里可能会有大量重复的纹理（比如一片一模一样的斑马线，或者大楼的一排窗户），导致计算机产生数以千计的错误匹配（Mismatches/Outliers）。如果不把这些错误的“恶作剧连线”删掉，后续的三维重建就会变成一团乱麻。

在这张展示真实图像匹配的图里，作者展示了算法在DAISY、DTU、Retina（视网膜图像）、RemoteSensing（遥感地图）和VGG等数据集上的连线大考。图中密密麻麻的蓝色线条代表被算法成功识别出来的正确连线，而右侧motion field里的黑色线条则代表那些混淆视听、最终被无情剔除的错误连线。为了剔除这些错误，科学家们发明了各种“纠错裁判”：

（1）重采样派（如经典的RANSAC算法）：这位裁判是个“死脑筋”，它会在成千上万条连线里，随机挑选几个幸运儿，推导出一个几何模型，然后去检验其他连线符不符合这个模型。不符合的，通通判定为错误并砍掉。虽然效果好，但在错误连线极多时，它会算得非常慢。

（2）松弛与局部保存派（如LPM算法）：这位裁判非常聪明，它提出了一个“邻里邻居要和睦”的假设：如果两条连线都是正确的，那么它们在第一张图里的邻居，在第二张图里应该也还是邻居。通过这种高效的局部一致性检查，LPM算法能在短短几毫秒内把错线拔除，成为了速度与激情的代表。

如果有些图片完全没有纹理（比如一张白纸，或者医学上的CT断层扫描），计算机找不到关键点，也办不出身份证，连线游戏还能玩吗？这就涉及到了论文中梳理的另外两大硬核分支：图匹配（Graph Matching）与点集配准（Point Set Registration）。

既然单个点没有特征，那我们就看“大局”。计算机把所有的点连成一张无形的网络（蜘蛛网），或者看成一团云雾（点云）。它不关心某个点长什么样，它只关心这些点组成的几何骨架整体如何对齐。为了测试算法处理纯几何骨架的能力，科学家们经常使用下面这些好玩的测试对象：

图4展示了用来做2D非刚性对齐实验的鲨鱼、鲸鱼轮廓，以及汉字“福”和“北京”的圆点骨架；图5则展示了计算机视觉界最著名的两位明星-3D点云构成的“斯坦福兔子（Bunny）”和“大灰狼（Wolf）”。即使这些点没有任何颜色和纹理，像GoICP或APM这样的算法依然能通过全局优化，把两只错位的兔子完美重合在一起。

论文指出，虽然我们已经取得了长足的进步，但未来依然充满挑战：

（1）现有的方法大多是“先连线、再纠错”的两步走，未来如何让AI在连线的一瞬间就做到“零误配”？

（2）如何让计算机不仅能匹配“同一辆车的两张照片”，还能匹配“一只哈士奇和一只金毛”之间的对应语义部位（都是狗的鼻子）？

（3）如何让一张白天的红外线夜视照片，和一张白天的普通彩色照片实现像素级的精准重合？

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

ORCID：0000-0001-9639-7679

DOI：10.1007/s11263-020-01359-2