72. 三维重建7-立体匹配3

上一次的文章71. 三维重建6——立体匹配2中，我主要阐述了各种经典的局部代价聚合方法。本篇我们继续解读Stefano教授的经典讲义 Stereo Vision: Algorithms and Applications，今天的重点是视差计算和优化(Disparity Computation/Optimization)。

一. 视差计算和优化的基本思想

正如我在文章70. 三维重建5——立体匹配1中所提到的，立体匹配的经典流程如下。

我们之前所讲解的局部法(上图左边路径)虽然已经取得了不错的成就，但由于仅仅利用了图像的局部信息，始终在一些场景下会出现较为明显的错误。而经典的利用全局信息进行视差优化的思路(上图右边路径)，则是希望寻找到每个像素的最优视差结果，使得全局的、整体的匹配代价最小，这一步被称为视差优化(Disparity Optimization)。于是这个过程就变成了一个最优化某个能量函数的过程，该函数通常写成如下的形式：

等号右边第1项是数据项，它衡量计算出的视差与实际输入图像关系的差异。一般来说，可以用下面的式子来表示，其中C表示代价函数。

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

对上述能量函数的最优化过程是一个非常困难的问题，所以人们发明了各种各样近似求解的方法。今天我们就简单顺着Stefano Mattoccia教授的讲义来看看这些方法。

二. 同时利用二维信息的全局优化算法

首先是早期且经典的三类方法：

2.1 基于图割的方法(Graph Cuts)

这里提到的方法最早的源头实际上是这篇文章：

在这篇文章中，作者提出了一种叫做move的概念，在立体匹配这个语境下，我们姑且将它理解为对像素的视差值进行的赋值操作吧。作者提到，传统的算法一般一次做单一像素的视差值赋值操作，这被作者称为standard move。而作者则创造了两种算法，分别称为 alpha-beta-swap or alpha-expansion ，能一次做大量像素的move。比如下面这张图，(a)是原始状态，像素的视差值有三种可能的值，分别用三种颜色来表示。(b)是一次standard move，有1个像素的视差值发生了从绿色到红色的改变 (c)是一次 alpha-beta-swap，可以看到许多红色和绿色像素视差值发生了交换 (d)是一次 alpha-expansion ，可以看到许多绿色像素变为了红色像素，相当于红色像素的范围扩大了。

作者提出，只要合理的利用这两种操作中的任何一种，就可以实现对初始视差图的优化，而优化的过程则是用图割算法(Graph Cut)来完成的。比如，当采用 expansion算法时，整体算法流程如下。其核心流程是轮询可能的视差值d(d位于dmin和dmax之间)，对于单次循环，将部分像素的视差值设置为当前轮到的d。选择哪些像素呢？选择的是让总体的代价降低的像素。

下面是这篇文章展示的结果，依然是经典的测试图像，其中(b)是标准视差图。(c)是swap算法的结果 (d)是expansion算法的结果。

和固定窗口的基础算法相比，明显效果要好很多

但我们也可以看到在边缘遮挡处，还有较多缺陷。于是Stefano教授提到的下面这篇文章，就基于上面的expansion算法进行改进，提升了边缘处的准确性。

两位作者在原本的能量函数中引入了新的一项，其中Eocc是将某个像素设置为遮挡像素所带来的代价：

优化此能量函数的关键是构建图的过程，我简单把expansion算法的图列在下面，此时看个大概即可，我在之后有机会会详细阐述这两篇论文。这里每个像素的视差值可能为 alpha，也可能不是。于是它们就需要和两个终端节点 alpha及非alpha连接在一起。另外像素间也有连接。最终是通过最小割算法来求得使得能量最小的解。

总之，我们就先看看作者展示的效果吧。下面右图就是上面的第一篇论文的效果，可以看到边缘处有很多问题，一些遮挡像素没有正确标识。而中间是引入了遮挡项后的结果，遮挡像素被正确的标识出来了。

看总体结果，利用图割进行alpha-expansion算法优化的方法，结合极少量的后处理确实取得了比很多局部法好很多的效果。

2.2 基于置信度传播的方法(Belief Propagation)

教授列出的第二类方法基于置信度传播技术。这里提到的论文是下面这篇

算法的总体流程图如下：

你可以看到，在完成固定窗口的初始视差计算后，它对图像进行了超像素分割。然后对每一个分割块内部，进行了1个平面拟合，相当于每个分割块都有自己的视差值。如果就此打住，那么每个分割块之间的视差值很可能出现不连续的情况，因此还需强调块与块之间的连续性。于是作者的代价函数中平滑项做了改进，它特别强调邻域块的视差不相等时的代价，这里公式里面的SN就是代表邻域块。

。

为了优化这个能量函数，作者采用了置信度传播技术，在邻域块之间传递信息。最后给出的效果如下，看起来很不错哦。

2.3 合作优化(Cooperation optimization)

下一类方法是中科大的两位学者提出的合作优化方法，论文如下：

这里的算法流程图如下

有趣的是这个方案实际上也用了超像素分割，和前面置信度传播的方式很相似。这里要解决的问题依然是得到最优的平面拟合参数，使得块内的代价最优，且块间的视差具有一致性。方案是同时优化一个分割块和它的所有邻域的代价，并且将这种结果通过迭代计算的方式进行传播，最后会达到收敛。

这里，能量函数被表示为了每个分割块的能量之和：

而为了优化结果，我们需要优化每一块和其邻域的能量和，这里i, j代表不同的块，j是i的邻域块编号。

这里面，每一块的能量具体可以表示为：

为了计算遮挡区域的代价，作者采用了左右对照的方式来定位遮挡区域像素，并赋以一定的代价：

我们来看看最终的结果, 也非常好，似乎背景部分相比置信度传播的略差点。

三. 在一维方向进行能量优化的算法

前面列出的几种方法虽然看起来得到了不错的结果，然而他们也具有极大的缺陷，就是计算量特别大。在当时的计算机上典型的图像很多需要一分钟以上才能匹配完成。所以又有学者提出了在1D方向进行优化能量函数的方法。这里主要包括基于动态规划的方法和半全局匹配的方法。我们分别看一看。

3.1 基于动态规划的方法

下图是动态规划求解的示意图，在某个水平线上，左图有a到k共8个像素，右图也有8个像素。我们的问题变成了寻找左图和右图的匹配像素对的问题。每个潜在的匹配对之间都会形成一个代价，所有这些代价会构成一个矩阵。问题就转换为了寻找这个矩阵中代价最小的路径的问题——是的，这是一个经典的寻路问题，正好可以用动态规划的方式去求解。

由于每次优化是在单条扫描线上进行，因此效率非常高，速度也很快，Stefano教授提到在当时的计算机上约1秒钟即可完成典型图像的计算。但这个方法要求场景具有这样的特点：如果两个物体在左图上一个在左，一个在右，那么它们在右图上应该遵循同样的左右顺序。然而这在很多实际的场景中并不成立。另外由于仅仅在1D方向上进行优化，它还会产生强烈的水平撕裂感，如下图所示：

3.2 基于半全局匹配的方法

最早提出半全局匹配(Semi-Global Matching)的是下面这篇文章

在这篇文章中，作者定义了下面这样的能量函数

这里面第1项是数据项，即给像素p赋以视差Dp的代价。第二项是平滑项，如果像素p的邻域点q与它的视差值相差1，那么给予一个小的代价P1。第三项用于处理视差不连续的情况，如果邻域点q和p的视差相差大于1，那么给予代价P2。

虽然看起来多了一些信息，但本质上这个能量函数和本文一开始提出的原始能量函数没有大的区别，如果直接去优化它还是一个NP难的问题。于是作者采用了在N个不同的1D方向上计算匹配代价，并将这些代价加到一起作为总代价的方法。

在单个方向上，代价变为下面这样：

这里r代表某个方向向量。比如如果p点的坐标为(x,y)，我们把r设置为(1, 0)，那么p-r就是(x-1, 0)，代价值就是在左水平线上计算的。

如果在(x-1,y)处可能的视差值有7个，那么这个方向上的代价就是：

如果每次只用1个方向的信息来作为代价，你可以想见肯定会出现很多错误。我把8个方向的结果列在下面

所以作者提出需要把几个方向的计算结果整合到一起，最后整合的结果是这样的：

这个算法的计算效率也很高，大概几秒钟即可完成计算，且在边缘和无纹理区域都比较准确。相比动态规划的方法，没有明显的撕裂现象，但其内存消耗是很大的。总体来说其计算复杂度是O(WHD)，D是视差等级总数。

这个方法在简单场景取得了不错的效果，但是遇到更加复杂的场景，特别是在弱纹理、无纹理的平坦区域会有明显的问题。

后面作者又在下面这篇文章中做了改进，重点解决无纹理区域等问题。

这次，作者提出了以下3个假设：

1. 平坦区域无深度跳变
2. 平坦区域依然有部分高纹理像素
3. 平坦区域可以视为1个平面

于是，作者就提出先对图像做超像素分割，并在每个平坦区域内部用半全局方法做能量最小化得到视差值。这个操作只在平坦区域进行，因此不会有额外的计算量。然后再通过双向比较区分出错误匹配的像素，然后再通过插值方法来修补错误。下面是讲义中列出的结果：

3.3 基于半全局匹配+支持窗聚合的方法

这是Stefano教授自己的文章

该方法首先还是用最基础的局部算法计算出匹配代价立方体，接下来还是按照半全局方法在4个方向上进行代价计算并整合在一起，其中单个方向上的代价为：

这里，r代表reference, t代表target。等号左边就是像素p取视差d的代价，而其中第1项是如下这样聚合而来，这也是和普通的不做聚合的半全局匹配方法的重要区别。

上面公式中，权重的公式如下，其中Sr代表参考像素点对应的超像素块。这里显然还需要对图像进行超像素分割。

最后在总代价立方体上执行WTA算法即可得到视差图。效果如下，看起来比起之前的方法效果又上了一个台阶。不过由于这里加入了代价聚合项，因此速度会慢很多。

四. 利用局部一致性优化视差

上面讲的都是想办法利用全局信息来对能量函数进行优化的方案。这一小节提到的则是一种通过添加局部一致性约束得到更好结果的思想。

我在71. 三维重建6——立体匹配2中已经介绍了局部一致性(Local Consistant)约束给局部聚合方法带来的效果提升。我们小小回顾一下：下面这幅图中红色点是我们关心的点，它有25个包括其自身在内的邻域像素。每个像素都有自己通过最简单的固定窗口法得到的视差值，其中可能有N种可能的视差值，每种视差值可能都会有自己的似然值，那么红色像素点的视差值应该是似然最大的那个。

总体思想是这样，我们现在看看如何把它应用到视差优化这个过程中

4.1 将局部一致性作为立体匹配算法的后处理操作

还是Stefano教授自己的文章，这里主要是将LC作为局部一致性的后处理步骤。

论文的主要流程如下，可以看到通过前面讲的动态规划或者半全局方法我们可以得到一张稠密的视差图Ds，然后通过LC(局部一致性)操作，可以同时得到两张视差图

和

，接着通过左右检查可以得到

，其中标明了错误像素，最后利用插值算法对错误像素进行修补，得到最终的视差图。

与原始的局部一致性论文一致，在参考图像和目标图像上，每个像素都会计算所谓"累积似然值"。粗暴一点理解，就是对任意一个像素，我们计算它的视差为某个值d的可能性。最后，这个像素的视差值就是似然值(可能性）最大的那一个。这样我们就可以得到参考图像和目标图像的视差图，即上图中的 DR 和 DT 。进而通过后面的常规流程，得到最终的视差图。

作者实验了两种初始的视差计算算法，一个是我们在3.2节提到的解决了平坦区域的半全局匹配算法，命名为C-Semiglobal，另外一种是基于固定窗口的实时算法，所谓RealTimeGPU. 我们通过下面两张图可以看到，两种算法的结果在应用了局部一致性约束后处理后，都得到了很大的提升。

事实上，在Middleburry数据集客观排名上，两种算法的结果在应用了LC后分别提升了12名及49名！

4.2 加速局部一致性计算

4.1介绍的方法有非常不错的效果，然而在作者实验中典型的图像大概需要在单核CPU上15秒才能完成计算，还是不够快。于是在下面这篇文章中，作者提出了近似计算的加速方法，使得最终只需要2s左右即可完成计算：

首先，4.1的方法为什么慢，慢在哪里？作者分析主要是在计算每个像素的累积似然值这里。我们看下图中，如果已知像素f和其匹配点f'的视差值分别为d和-d，那么红色像素g和g'，它们的视差值为d及-d的似然值是多少呢?

按照LC算法的原始方法，这跟g/g'点与f/f'点的空间及颜色相似度，以及g/g'点之间的颜色相似度相关。于是写出来就是下面这个复杂的公式，自然计算量也比较大。尤其是对于红色点来说，它需要对每一个邻域像素(f/f'只是其中一个）都进行这样复杂的计算。

于是在这时候，作者认为可以对上面公式做近似计算，即对图内的空间、颜色相似度采用块计算的方法，减少计算量。而图间的颜色相似度依然采用逐像素计算，避免精度损失太多。

另外，作者还提出减少支持窗的尺寸从而减少累积似然度所需要计算的点数。同时，还加入了分块操作，进一步利用到了处理器的多个核来并行计算：

最终其速度果然大大提升，而效果看起来也还挺不错：

4.3 进一步结合超像素分割和局部一致性

虽然看起来利用4.1、4.2的方法已经取得了非常好的效果，但作者的研究还未止步。接下来他又探索了结合超像素分割和局部一致性约束的方案，并发表在下面的文章中：

这次的算法分为了两个阶段。

第一个阶段先用前面讲的C-Semiglobal算法进行了初始匹配，然后应用LC算法得到视差图，以及每个像素的似然值。然后用超像素分割算法分割图像，并对图像的每一个分割块内部做进一步的处理。

对于每一个超像素块内部，作者利用左右对照检查，标记了错误像素(黄色)，以及稳定像素(橙色)。而对稳定像素，又会根据是否和当前超像素块内的主视差差距过大来进行区分。差异过大的像素会会留到第二个阶段进行进一步匹配。

在第二个阶段，作者调整超像素分割算法的参数，得到更大的分割块。然后，仅对在第一阶段标记出需要特别匹配的像素，再一次应用调整了参数后的局部一致性算法，从而使得之前得到的稳定视差值可以传播到这些待处理像素上。

该算法使得原始的C-Semiglobal算法的排名整整提升了14名！

五. 总结

视差计算和优化的方法很多，今天我们顺着Stefano教授的讲义看到了如下这些类别的算法：

• 同时利用二维信息的经典算法：图割、置信度传播、合作优化
• 在1D方向进行匹配的算法，包括基于动态规划的算法，和基于不同方向扫描线优化的半全局匹配算法
• 基于局部一致性约束进行后处理的算法

这里面每一类算法都有自己的特点，而且总体看来这里介绍的算法都比上一篇文章介绍的局部代价聚合方法的效果更优。这是可以理解的，因为毕竟今天介绍的算法或多或少利用到了更加全局的信息。然而，即便如此我们目前得到的结果依然还有进一步改进的空间，这些就是视差后处理要完成的任务，我会在下一篇文章中加以讲解。

六. 参考资料

• Stefano Mattoccia, Stereo Vision
• 70. 三维重建5——立体匹配1
• 71. 三维重建6——立体匹配2
• 文章中以图片形式截取了关键论文的标题等信息，如有需要你可以直接下载阅读