71. 三维重建6——立体匹配2

本篇我们继续解读Stefano教授的经典讲义 Stereo Vision: Algorithms and Applications，今天的重点是代价聚合。

一. 代价聚合的引入

在上一篇文章70. 三维重建5——立体匹配1中，我已经为你介绍了立体匹配的整体流程和面临的基本挑战。我们看到用固定窗口的方式计算的代价立方体，其遵循的假设和实际情况不符合，所以导致代价立方体中有大量的错误，进而使得最终的视差图也有大量的错误。具体来说：

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

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

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

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

为了解决这种问题，人们的第一个想法是对代价立方体进行局部聚合，使得其中的噪声更低，代价值更准确。然后再计算视差。

其实，局部代价聚合的思想和一般的图像去噪没有太大区别，它也是基于如下的几个假设：

• 空间上接近的像素，其视差值也是接近的，于是代价值也是接近的
• 像素值接近的像素，其视差值也是接近的，于是代价值也是接近的
• 左右两张图的相邻像素，在关键信息上具有局部相似性

我们现在来看看，基于以上的假设，人们创造了哪些经典的代价聚合算法。

二. 代价聚合的各种方案

2.1 基于空间假设的方案

2.1.1 固定尺寸的方形支持窗(Fixed Window)

最基础的方案还是FW，我还是把这种方案的结果列在这里。这种方案理解和实现都很容易，且非常便于并行化，在现代处理器上也比较容易做到实时运行，非常容易采用FPGA这样的硬件进行实现，性价比很足。然而它的缺点也很明显，之前已经说过了，这里不再赘述。

2.1.2 多个不同位置的候选支持窗中选择1个(Shiftable Windows)

FW的假设是只有当前像素为中心的邻域像素都具有同一视差，这显然是一种过于理想的假设。而在Shiftable Windows方案中，我们计算一个像素点所在的不同位置的支持窗的加权平均代价，并给每个支持窗一个分数。得分最优的那个作为当前像素的支持窗，那么代价就由这个窗口计算得到。比如在下图中，如果支持窗为5x5大小，那么实际上根据当前像素点在支持窗内位置的不同，我们一共可以有25个候选支持窗（图中画的是17个）。我们可以选择所有支持窗中代价最小的那个——这在一定程度上可以减少支持窗内不同深度像素的影响。

相比FW，似乎效果提升不明显，能观察到一些局部得到了改善。 2.1.3 合并多个不同位置的支持窗(Multiple Windows)

我认为Shiftable Windows的效果之所以没有很大提升，是因为最终支持窗只包括了很少一部分与当前像素同视差的像素，其他的都在选择过程中被丢掉了。而Multiple Windows方案则尝试改变最终支持窗的形状（从矩形改为不规则形状），从而选择更多的同性质的像素。它利用较小的基础支持窗尺寸，并同时计算以当前像素为中心的支持窗的多个邻域支持窗的代价值。然后从这些邻域支持窗中选择代价最小的几个，并与中心支持窗的代价整合到一起。如下图所示是选择了8个邻域支持窗+1个中心支持窗（即9窗口法， 9W），最终有5个支持窗的代价会整合到一起。根据需要，也可以选择5W，或25W等等方案。你可以看到，最终的支持窗的形状不再是规整的方形了。

观察这种方案的结果，确实能看出在一些物体边缘处视差图有了提升。

2.1.4 不同尺寸，不同位置的支持窗中选择1个 (Variable Windows)

这种方案扩展了Shiftable Windows方案，对某些像素，我们会计算不同大小的、包含了该像素在内的多个支持窗的平均权重，再从里面选择代价最小的那个，作为最终的支持窗。为了减少计算量，相邻像素之间会传播支持窗的尺寸信息，这样部分像素就不用在不同尺寸的支持窗之间进行搜索选择了。下图展示了同一个像素的多种候选支持窗，有大有小，有不同的位置。最终从里面选出代价最小的那个。

效果如何呢？下面是结果。我们看到相比上面几种方法，这里的结果确实要好了一些，你可以特别观察原始图中标记为白色方块的地方，比如灯架。

2.1.5 小结

刚才讲的几种方案，都是认为通过在指定像素坐标周围可以找到和该像素同样视差的像素。于是就尝试用不同尺寸，不同位置的支持窗口去指导这种搜寻任务，最终的支持窗始终是用方形的基本块组成的，而且支持窗内的像素也基本上没有区分不同的权重。你应该可以想到，这种思路还是太粗暴，始终还是有缺陷的。现在让我们看看基于像素值的假设，能不能得到更好的结果。

2.2 基于像素颜色一致性假设的方案

这类方案最直接的想法是先把图像通过某种特征（例如亮度、颜色）进行预先分割，得到的结果中每一块的视差是平滑变化的. 比如Mean Shift算法，可以把下面的图像分割成右下图的样子：

有了分割结果后，就可以用各种技巧来进行代价聚合了。我们看几种方案：

2.2.1 利用分割结果计算聚合权重(Segmentation-Based)

这种方案中，首先对参考图像R进行分割。然后在计算代价时，可以对支持窗口中每个像素指定不同的权重。在支持窗内属于同一分块的像素，权重为1，不同分块的，权重为一个非常小的值\lambda， 然后把所有像素的代价加权平均到一起，成为中心像素的代价值。

这种方法需要一个较好的分割算法，我们看看结果，物体的边界确实清晰了一些，不过还存在一些小错误和噪声。

2.2.2 同时结合固定窗口和分割块 (Fast Aggregation)

这个方法相比上面提到的直接采用分割块进行聚合的方法的不同是同时还利用到了固定窗口的思想。如下图所示，首先对参考图像做了分割。接着所有与中心像素同一块的像素代价值加权平均到一起， 同时再计算固定尺寸方形支持窗的聚合代价。这两个代价整合到一起作为最终的代价值。作者提到，采用FW计算部分代价，是为了避免在高纹理区域分割块很小，导致较大的噪声。另外这里采用了积分图这样的方式来加速FW代价的计算，所以整体速度比较快。这个也是Stefano教授参与了的工作。

这个算法的结果好坏与固定窗口大小、分割块准确性等等都相关，不同参数得到的结果不太一致。参数调到位后，效果似乎特别好。

以上两种方案都是直接采用硬分割来做聚合的基础。虽然比起之前的纯基于空间相似度的方案看起来更科学了，但结果和分割质量优劣非常相关。分割类算法一般更加强调局部颜色的一致性，空间上的相似性很少利用。所以导致最终结果还是不够理想。现在我们看看把两种方案有机结合起来的算法。

2.2.3 利用颜色距离计算权重(Segment Support)

刚才的方案都是分别给同一分块、不同分块的像素设置固定的权重。现在介绍的是一种利用像素的颜色差异自适应的计算权重的算法。这里是先对图像做分割，然后对支持窗内与中心像素同一个分割块的像素设权重为1，不同分割块的像素则应用与中心像素的颜色距离来计算权重。注意看Stefano Mattoccia教授是本文的作者之一哦。相比2.2.1介绍的基于分割结果进行硬权重设置的方法，现在这个算法为非同一块的像素设置了自适应的权重，避免了过分割带来的断裂问题，能更好的消除弱纹理区域的噪声

2.3 同时使用空间距离和颜色距离的方案

这种算法认为如果两个像素颜色接近、且空间距离小，那么它们的视差值大概率是接近的，很多方案都尝试利用滤波算法获得更好的权重。

2.3.1 基于双边滤波思想计算自适应权重(Adaptive Weights)

我在文章4. 数码相机内的图像处理-更多图像滤波中给你介绍过双边滤波。这种滤波器在处理图像时，对于任何一个像素，会根据空间距离、像素值距离给予它的邻域像素不同的权重，再把邻域内的像素加权平均到一起。这样就可以达到保边滤波的目的：

那么，在进行代价聚合时，也可以采用这种思想。我们依然用方形的支持窗，但是在支持窗内每个像素都根据其到中心像素的空间距离和像素值距离，给予不同的权重。根据这些权重把代价值加权平均到一起，实际上是隐式的对图像进行了分割。

你可以看到下面的结果，在很多地方都有进步，但确实也产生了一些错误。尤其是不同的颜色、同一个物距的物体，被错误的赋以了不同的权重，导致结果错误，另外物体表面的亮度噪声也容易导致干扰。

2.3.2 加速双边权重计算 (Fast Bilateral Stereo framework-FBS)

这是一种叫做Fast Bilateral Stereo framework的方案， Stefano是第一作者。由于双边滤波计算自适应权重是非常非常慢的，所以这种方案希望能用某种快速的方法近似求取联合双边权重，最终得到不亚于分割类算法、自适应权重类算法的效果。

它首先采用了一个较大的WxW的支持窗，又把每个支持窗分成很多wxw的小块。对于每个小块的中心，根据它到大支持窗的中心的空间距离计算一个权重Ws。然后再根据这个小块的平均颜色和中心像素的颜色距离，计算一个权重Wc。然后再将Ws和Wc整合起来，用于计算最终中心像素的匹配代价。

实际上，它的思想就是用分块的方式降低了双边滤波权重的计算量。作者指出，当分块大小合理时，能达到和自适应权重相当的效果，但速度大大提升。不过随着分块大小变大，效果也就慢慢变差了。

作者指出可以用积分图和查找表等技巧来提升算法速度，并且还能够利用GPU将这个算法并行化执行，大大提升速度。总之，分块计算是这个算法的核心思想。有趣的是，这个算法框架简称FBS，实际上和后面我会专门撰文描述的另外一个方法The fast bilateral solver的简称一致，而且其中都用到了类似的思想，但后者更加现代，更加值得独立讲解。

2.3.3 在分割的基础上结合FBS的分块计算的思想(Fast Segmentation-driven)

Stefano等后面又发表了Fast Segmentation-Driven算法，把分块的思想和分割结合到了一起。作者依然采用较大的方形支持窗，并对图像进行超像素分割。相比2.2.1提到的直接分割然后计算分割块内每个像素的权重的方法，这里作者把大支持窗分成了很多小块，如下所示。这样后续的所有计算都是基于小块的中心来计算的，这样就大大减少了计算量。比如下面这个是21x21的支持窗，本来需要计算441个点的权重。但把窗口分成了49个小块后，就只需要计算49个点的权重了，你说快不快。

当然，和FBS一样，效果也跟分块的大小高度相关，分块越大，效果越差。

2.3.4 受引导滤波启发的O(1)方案

这种方案比较有趣，它受引导滤波启发，首先认为任何1个点p，如果它有一个邻域点q。那么我们要计算p点的聚合后代价时，可以这样做：

• 以q点位中心，确定一个窗口
• 在这个窗口内，计算一组线性稀疏(a, b)，它们代表了左右两图中相应窗口内的整体信息
• p点的聚合后代价可以认为是用左右两图中两个像素的值，通过这组线性系数组合而成的。当输入图是灰度图时，a是1x2的矩阵，如果输入图是彩色图，那么a是1x6的矩阵。而b是标量， E也是标量。

对于点p来说，它一共有N个邻域像素，对每个邻域像素都可以应用上面的式子，来计算出1个p的代价。那么p的最终聚合代价是上面所有邻域线性系数组合而成的均值。

2.3.1节中介绍的Adaptive Weights方法需要非常复杂的计算，

而这里的方法只需要提前算出线性组合系数即可（论文中有描述，此处忽略），聚合过程计算量与窗口大小无关，所以是O(1)的。最终得到的效果也挺不错

2.4 局部一致性：利用两幅图像局部视差及颜色、空间平滑性假设

前面的几种方法已经使用到了这样一种假设：在图像支持窗范围内，视差是平滑变化的。现在介绍的这种方法叫做Locally Consistent(LC), 也是咱们这份讲义的作者Stefano教授的大作。它观察到下面这个重要线索，如下图所示：对于任何一个像素点（红色点），我们可以假设它的视差值应该和它支持窗范围内的任何一个点（蓝色点）的视差一致（即认为这个支持窗是正对相机的平面）。这样，对于每个支持窗内的点（图中共有25个点）都会给红色点提供一个潜在的视差值。作者认为，可以把这些信息整合起来，构建某种似然函数。最后，通过这种似然函数，可以为红色点确定一个更优的视差值。

我们任意选择红色点g的某个邻域点f（蓝色）来看看，可以直观的想到，红色点的视差值为f点的视差d的似然值跟下面几个因素相关：

• g和f的空间、颜色接近程度
• 定义f' = f - d为f在视差d时的对应点，g' = g - d, 那么似然度也跟g'和f'的接近程度有关
• 似然度还跟g和g'的颜色接近度有关

通过这些观察，可以先用某种方法计算出初始的视差图，再用刚才讲到的这些约束条件对视差值进行优化。能够让效果变得更好。而且对于初始视差图的算法并没有强制要求，适应性很广。你可以从下面的图中看到，用LC叠加上前面讲的FBS之后，效果确实变优了。

即便叠加到最基础的FW的结果上，效果提升也非常明显

LC可以叠加到很多其他的算法基础上，并且取得了很不错的成绩。实际上，局部一致性的思想影响深远。我后面会独立撰文描述的PatchMatch算法，也是用到了这样的思想的。

三. 总结

在局部代价聚合这一部分，Stefano教授列出了大量案例供我们学习。这些案例基本上遵循下面的假设：

• 空间上接近的像素，其视差值也是接近的，于是代价值也是接近的
• 像素值接近的像素，其视差值也是接近的，于是代价值也是接近的
• 左右两张图的相邻像素，在关键信息上具有局部相似性

为了利用这些假设，许多方法采用了分割、或是双边滤波、引导滤波等高级算法的思想，取得了不断的进步。然而，局部代价聚合方案毕竟少利用了图像的全局信息，所以最终得到的效果都还是有缺陷的。在下一篇文章中，我为你介绍全局视差优化的思想，看看这条路上的几种经典算法。

四. 参考资料

1. Stefano Mattoccia, Stereo Vision: Algorithms and Applications
2. 70. 三维重建5——立体匹配1