70. 三维重建5-立体匹配1

在上一篇文章69. 三维重建4-立体校正(Recitification)中，我们看到通过立体校正算法，可以把双摄图像对校正到标准形态，使得两幅图像的对极线水平对齐，就好像是我们创造了两个内参相同的虚拟相机，它们指向同一个方向进行拍摄原来的场景，得到两幅新的图像。

当做到这一点后，就可以很方便的在水平方向搜索一个图像上的一点在另外一个图像上的对应点。如下图所示，左图上的一点p在右图上的对应点是p'，接下来就很方便的进行三角测距，确定物点P的物距了。

物距Z的计算公式可以很容易通过相似三角形得出：

这里面, X_R-X_T叫做视差，而b是两个相机光心的距离, f是焦距。这样，求取空间点和相机之间距离的关键就变成了求取其投影点视差了。而整个图像上所有点的视差构成了一幅图像，这个图像叫做视差图，如下所示：

而通过校正后的一对图像获取到视差图的过程，叫做立体匹配，它有点像玩连连看的游戏：给计算机一对输入图像，指定左图上的某个点，要求算法在右图上找到它对应的投影点，然后将两个点的横坐标相减得到该点的视差。

今天我就来好好聊聊立体匹配。我最喜欢的关于立体匹配算法的基础教学课件是意大利Bologna大学的Stefano Mattoccia教授在2012年编写的"Stereo vision: algorithms and applications"（当时他还在佛罗伦萨大学）。

这份讲义涵盖了立体匹配的诸多基础知识，据我了解很多人也是通过这份文档入门的。由于内容过于丰富，读者自己阅读时可能会理不清其中的逻辑关系，或丢失掉一些细节信息。我希望结合自己的理解，对这份讲义加以导读，帮助你更快的入门。

一. 从基础的立体匹配方法开始

先来看看下面两幅经过立体校正的图像，一幅称为Reference图像(R)，一幅称为Target图像(T)。现在希望求取两幅图像的视差图，正如我上面所说，这是一个让计算机做连连看游戏的过程——给定R图上一点，我们在T图的同一行上搜索和R图点匹配的同名点。

这时，我们会将水平搜索约束在一个范围内[0, ]，如下图所示

现在的问题是，如何判断最匹配的点呢？

一般来说，我们会定义某种匹配代价，用来衡量两个像素的相似程度。那么匹配代价最低的那个像素，就会被选为同名点。

最基本的匹配代价就是两个像素的像素值的绝对差（我们可以暂且把图像当做是单通道的灰度图像），那么匹配代价就是：

如果最小视差为0，候选的视差值d的值域范围是从0到dmax的整数，那么可视化一下所有的匹配代价如下图所示：

从所有的候选像素中挑选匹配代价最低的作为最终的同名点，这个策略被称为Winner Takes All (WTA)，所谓的赢者通吃

那么，按照这种方法算出的视差图如何呢？我们看看下面的结果，并和Groundtruth做下对比：

肉眼判断视差图是否有错误可以通过下面几个准则来观察：

• 视差是近大远小的，表现到视差图上则是近亮远暗
• 同一个物距的物体表面的视差亮度是一致的
• 在物体的边缘，如果物距发生了突变，那么视差图上也应该有突变的边缘
• 物距渐变时，视差图上也是平滑变化的

很明显，相比理想结果，这种方法的得到的视差图充满了噪声，很多地方可以肉眼可见明显的错误。我们上面这种简单的立体匹配算法很明显是不足的。接下来，我会先谈谈立体匹配的困难之处，再分析一下解决这些困难的方法。

二. 立体匹配的困难之处

在讲义中，Stefano教授提到的困难之处包括了：

在实际场景中，可以同时包含了以上多种困难之处，难怪立体匹配如此困难，上面那种简单的方法无法奏效。那么该如何应对这些问题呢？

三. 立体匹配的基本思路和流程

我们来看看解决上述困难的基本思路：

3.1 图像预处理 Preprocess

立体匹配的困难最终的反映为搜索同名点失败上，如果是因为两幅图像的亮度、噪声不一致，一般会先对图像做预处理，使得两幅图像的整体质量区域一致。这里面典型的方法有（这里括号中提到的参考文献都是原讲义的参考文献，读者可以自行查阅）

3.2 代价计算 Cost Computation

刚才计算同名点匹配代价时采用的是单个像素点的绝对值的差异，这样很容易受到噪声的干扰。规避方法有两类：

• 换用更鲁棒的单像素的代价函数
• 采用邻域支持窗来计算整体代价

我们一个个讲。

1. 换用更鲁棒的单像素的代价函数

这一类方法依然是利用左右图像上单一的像素点进行代价计算。人们设计了很多不同的代价函数计算方式，分别都有自己的优缺点，这里列出如下：

像素差异绝对值 Absolute Differences

平方差 Squared Differences

上面两种代价函数都容易受到噪声的干扰，于是就有了更加鲁棒的函数，比如：

截断绝对差 Truncated Absolute Differences (TAD）

将绝对差限制在<=T的范围内，避免噪声引起过大的代价。这是一种简单的策略，其实并不比上面两种好多少，因为T很难确定

还有更复杂的，通过某种对图像内容不敏感的方式来确定两个像素的不相似度，比如Birchfield and Tomasi [27]中提到的方法。它考虑了当前像素，以及其旁边的两个像素。

总之，仅仅考虑单个像素，还是很难得到好的结果。更好的方式是通过计算所关注的像素点的邻域的整体情况，来提升信噪比，减少噪声的影响。我们把这个邻域范围称为“支持窗(Support Window)”，通过支持窗内所有像素来计算一个匹配代价值。

采用邻域支持窗来计算整体代价

这种策略就是把单个像素的计算转换为一个支持窗内的整体计算了，比如：

像素绝对差值和 Sum of Absolute differences (SAD)

像素差值平方和Sum of Squared differences (SSD)

截断绝对差值和 Sum of truncated absolute differences (STAD)

除了这些简单的代价函数，还有更多方法，比如利用两个图像的互相关信息的，利用图像梯度域信息的，或是利用一些非参数方法的，等等。你可以参考原讲义，找到参考文献来阅读。

总之，我们可以为R中的每个像素点和选定的T中的像素点计算一个代价，并且这个代价还具有很高的区分度。如前所述，我们是在一个范围[dmin, dmax]中搜索匹配点，因此对任何一个R中的像素点，可以算出dmax - dmin + 1种代价值。如果图像的宽高分别为W和H，那么我们总共会得到W x H x (dmax - dmin + 1）种代价值。所有这些代价值可以存储到一个立方体中，这就是所谓的代价立方体，如下所示：

3.3 代价聚合(Cost Aggregation)和视差优化(Disparity Optimization)

通过支持窗计算代价已经对图像的噪声、光照不一致等等提升了一定的鲁棒性，但依然有很多问题遗留下来。我用一个基本的例子加以说明。让我们用一个改进的流程来处理之前给出的一对图像：计算一个简单固定尺寸方形支持窗内的截断绝对差值和STAD，然后用WTA策略计算视差。

看看上面的结果，比起最基础的方案，视差图似乎平滑了很多，没有了大片的噪声。但是很多局部是错误的，比如说灯罩边缘变得凹凸不平，背景出现异常的亮区，右上角也出现了异常的噪声，灯架断开，等等。

固定支持窗，英文是Fixed Window，简称FW。上述结果不够理想，是因为FW策略违背了一些基础假设。我们一一列举一下：

1. FW假设支持窗是正对相机的平面，支持窗内的所有点的视差是一致的，这显然和实际情况不一样。比如下面场景标注的支持窗，就显然不是正对相机的平面：这里人头部分是带弧度的，而下图的平面应该是倾斜的。

2. 支持窗忽略了窗口内深度不连续，甚至有突变的情况，而强行把窗口内的视差值加权平均到一起。这就会导致产生的视差图内出现大量的物体边缘错误。如下图所示：

理想情况下，支持窗应该只包含同一深度的像素点，像下面一样。我后面会给出一些进行这些努力的方法。然而，现实情况是由于固定方形窗口的优点，很多算法还是采用了它。于是为了避免上面这种包含过多不同视差像素在同一个支持窗的现象，就需要适当的减小窗口的大小。但这又和我们一开始用支持窗来去除视差图中的噪声，提升信噪比的初衷违背了——于是，就需要根据实际场景的要求，经验性的调整支持窗的大小，这显然不是一件容易的事情。

3. 当场景中有大面积的重复纹理、无纹理的部分时，小尺寸的支持窗无法解决同名点计算错误的问题，这种情况下可能出现很多候选像素点的代价值都一样，难以区分的情况。比较好的策略是在这些区域用尽可能大的支持窗，来提升信噪比和像素之间的区分度。而这又和上面希望减小支持窗大小避免深度不连续影响相矛盾——显然一个单一尺寸的支持窗无法应对两种情况。

很明显，当完成3.2节所说的代价计算得到代价立方体后，由于计算过程中的上述问题，代价立方体中肯定有许多的噪声和错误。下面右图是另外一个场景，你应该也能观察到其视差图中的错误。

尽管固定支持窗有这样那样的缺点，但它理解和实现都很容易，且非常便于并行化，在现代处理器上也比较容易做到实时运行，非常容易采用FPGA这样的硬件进行实现，性价比很足！所以很多传统算法的代价计算这一步都是采用固定大小支持窗来完成的。而要继续提升最终算法的效果，还得靠后续的步骤。

这里主要有两大类思路，也就是局部聚合思路，和全局优化思路。

3.3.1 代价聚合(Cost Aggregation)

局部聚合思路是通过对代价立方体中同一视差的代价进行某种程度的聚合，来减少或消除错误代价的影响，这一步就是所谓的代价聚合(Cost Aggregation)。比如下面左图，同一个视差的窗口我们会扩大并将代价立方体中相应的代价聚合在一起。而下面右图则说明在聚合过程中要避免混合不同视差的像素。

Stefano Mattoccia教授的讲义中介绍了各种各样代价聚合方法，它们一般来说是通过调整支持窗的位置、形状、窗内各像素的权重等等来完成聚合的。我会在下一篇文章中为你导读讲义中提到的各种各样的局部代价聚合方法。总之，通过局部的代价聚合，有可能得到非常不错的效果，比如下图中所示的一个利用了局部一致性的方案，相比FW的效果得到了很大的提升。

3.3.2 视差优化(Disparity Optimization)

而全局优化思路，则是希望寻找到每个像素的最优视差结果，使得全局的、整体的匹配代价最小，这一步被称为视差优化(Disparity Optimization)。于是这个过程就变成了一个最优化某个能量函数的过程，该函数通常写成如下的形式：

等号右边第1项是数据项，用于约束全局代价最小化。但是代价立方体中通常含有噪声和错误，直接最小化求得的结果也会有很多问题，所以还需要第2项平滑项。这一项一般用于给出某些额外的约束条件，比如通常假设整个图像的视差是平滑变化的。这样视差的大变化只会在场景内视差边缘处产生，一般也和图像内物体边缘高度相关。

对上述能量函数的最优化过程是一个非常困难的问题，所以一般会有一些近似求解方法，比如讲义中提到的：

还有就是用将全局能量函数的最优化转换为针对图像中的子部分的最优化，比如约束到某些扫描线方向上的最优化，然后利用动态规划或扫描线优化等方式去求解。

关于视差优化，我也会在后面专门的文章中再阐述细节。但至少当时，全局法的效果确实比起很多局部法要好，我们看下面这些例子，就很清楚了：

3.4 视差后处理(Disparity Refinement)

前面介绍的步骤最终将输出一张视差图，然而正如你已经看到的，即便是在上面那些受约束的场景，得到的视差图依然不是完美的，还是有很多错误。因此，还需要一个后处理的步骤，来消除其中的错误，得到更准确的视差图，这一步被Stefano教授称为Disparity Refinement。我感觉Disparity Refinement比较容易和全局法的Disparity Optimization在字面上混淆，因此就翻译做视差后处理吧，如下图所示。

这一步需要解决哪些问题呢？这包括了：

• 亚像素插值：我们上面计算的视差值都是离散的整数值，但实际场景物体存在连续变化的视差，我们希望得到以浮点数表示的更精细的视差值。一般来说，会采用某种二次的抛物线插值法，得到连续的视差值，计算量也比较低，结果也不错。

噪声和错误消除：有时候会简单采用图像滤波的技术来处理视差图，也能得到不错的结果。从简单的中值滤波，到复杂的双边滤波都有人尝试。我会在之后的文章专门介绍一种强大的滤波类的处理方法。另外一个重要的技巧是双向匹配，这种方法分别以双目图像中左图和右图作为参考图像R计算两个视差图（缺点：增加了计算量)。然后它认为一对匹配点的视差值是互反的，也就是说一对正确匹配点的视差值会非常接近。如果不满足这个条件那么对应的视差值应该就是错误的。比如下面红色点的视差就计算错误了，而绿色点则是正确的。

关于视差后处理，可谈的内容也挺多的，考虑到篇幅限制，这里就先不深入了，之后的文章再补上吧。总之，通过组合前面的步骤，我们就可以得到最终的视差图了。

四. 总结和展望

今天这一篇文章是我要写的关于立体匹配的文章的第1篇，主要是对Stefano Mattoccia教授的讲义的一个导读。主要为你介绍了立体匹配的一些基本概念和步骤。在接下来的几篇文章中，我还是会继续导读这份讲义，主要展开讲解代价聚合、视差优化，以及视差后处理。当这些部分都搞清楚后，我就会再介绍一些经典的算法，包括传统的局部法、全局法、半全局法，以及基于深度学习的某些方法。希望整个内容能有机的连成一片。

当然，毕竟这是一个2012~2013年间的讲义，很多后来的优秀方法都没有包含在内。比如我现在团队所开发的方法，已经能在非常非常挑战的场景下得到非常非常精细的结果了，这是以前这些方法无法想象的。但Stefano教授提到的这些本质性的挑战和优化思想，依然在指引着后来的研究者。我在之后也会介绍今年CVPR中我们的一篇文章，看看我们是如何把传统视觉方法和深度学习方法结合起来，用到匹配中的。

五. 参考资料

1. Stefano Mattoccia, Stereo Vision: Algorithms and Applications, 2012
2. 69. 三维重建4-立体校正(Recitification)