立体视觉入门指南（7）：立体匹配

关于立体匹配，我之前写了很多博客，重复去写就没有必要，学习的朋友请阅读如下链接。

本文我们随便聊聊立体匹配的方法论和弱纹理恢复问题。

文章目录

立体匹配系列

0

双目立体匹配步骤详解

1 SGM系列

理论恒叨系列

【理论恒叨】【立体匹配系列】经典SGM：（1）匹配代价计算之互信息（MI）
【理论恒叨】【立体匹配系列】经典SGM：（2）匹配代价计算之Census变换
【理论恒叨】【立体匹配系列】经典SGM：（3）代价聚合（Cost Aggregation）
【理论恒叨】【立体匹配系列】经典SGM：（4）视差计算、视差优化

码上实战系列

【码上实战】【立体匹配系列】经典SGM：（1）框架与类设计
【码上实战】【立体匹配系列】经典SGM：（2）代价计算
【码上实战】【立体匹配系列】经典SGM：（3）代价聚合
【码上实战】【立体匹配系列】经典SGM：（4）代价聚合2
【码上实战】【立体匹配系列】经典SGM：（5）视差优化
【码上实战】【立体匹配系列】经典SGM：（6）视差填充
【码上实战】【立体匹配系列】经典SGM：（7）弱纹理优化

2 PatchMatch系列

理论恒叨系列

【理论恒叨】【立体匹配系列】经典PatchMatch: （1）Slanted support windows倾斜支持窗模型
【理论恒叨】【立体匹配系列】经典PatchMatch: （2）基于PatchMatch的视差估计
【理论恒叨】【立体匹配系列】经典PatchMatch: （3）后处理（一致性检查与视差填充）

码上实战系列

【码上实战】【立体匹配系列】经典PatchMatch: （1）框架
【码上实战】【立体匹配系列】经典PatchMatch: （2）主类
【码上实战】【立体匹配系列】经典PatchMatch: （3）随机初始化
【码上实战】【立体匹配系列】经典PatchMatch: （4）代价计算
【码上实战】【立体匹配系列】经典PatchMatch: （5）迭代传播
【码上实战】【立体匹配系列】经典PatchMatch: （6）后处理

3 AD-Census系列

理论恒叨系列

【理论恒叨】【立体匹配系列】经典AD-Census: （1）代价计算
【理论恒叨】【立体匹配系列】经典AD-Census: （2）十字交叉域代价聚合（Cross-based Cost Aggregation）
【理论恒叨】【立体匹配系列】经典AD-Census: （3）扫描线优化（Scanline Optimization）
【理论恒叨】【立体匹配系列】经典AD-Census: （4）多步骤视差优化

码上实战系列

【码上实战】【立体匹配系列】经典AD-Census: （1）框架
【码上实战】【立体匹配系列】经典AD-Census: （2）主类
【码上实战】【立体匹配系列】经典AD-Census: （3）代价计算
【码上实战】【立体匹配系列】经典AD-Census: （4）十字交叉域代价聚合
【码上实战】【立体匹配系列】经典AD-Census: （5）扫描线优化
【码上实战】【立体匹配系列】经典AD-Census: （6）多步骤视差优化

如果你能学会SGM和PatchMatch，那么立体匹配你就完全入门了。

关于方法论

而真正需要学习的是立体匹配的方法论，从SGM算法，你可以学习马尔科夫随机场是如何应用于立体匹配的，进而你可以深入去了解马尔科夫随机场这个经典的理论，它在三维重建里应用比较广泛，你会在不同的地方看到它的身影，简而言之，大部分标签分配问题都可以用马尔科夫随机场来建模，而解决马尔科夫随机场这个能量最优问题，都是用效率高的近似方法，比如SGM的扫描线优化(Scanline Optimize)、动态规划(Dynamic Programming)、置信度传播（Belief Propagation）、合作优化（Cooperative Optimization）等。

我们会发现，无论在科学研究还是在工程实践中，建模都很重要且关键，当你发现立体匹配问题可以转化为标签分配问题便很快想到可以用马尔科夫随机场建模，进而尝试用众多成熟的优化算法之一去解决问题。大多数论文都是这样产出，研究进展的突破就在你转化问题的那一瞬间，当然前提是你要掌握一定数量的算法模型，这便是你应该掌握的基本知识之一。

而从PatchMatch算法上，和SGM对比我们可以明显感知到，基于离散空间的标签分配方法似乎并不是立体匹配问题的最优解，而基于连续空间的视差平面方法，在精度和效果上有明显的优势。尤其是在边界和细小结构的恢复上，离散空间带来的不精确性以及SGM的代价聚合模型对边界的处理并不清晰（或者说并不精确），使得SGM和PatchMatch差距明显，下图是一个例子：
原图SGMPatchMatch
边界恢复问题，并不能说是离散空间的问题，现在的深度神经网络，本质上还是离散空间的标签分配方法，但是将效果提升到了另一层次，对边界的恢复也比传统的标签分配方法要更好，但是在最终点云的精度上，对比PatchMatch并没有显现出优势，如果深度神经网络能在精度上打败传统几何算法，那算得上是一种全方位的颠覆，但是这并非不可能发生，因为目前所知的传统算法也并非在最好的状态，就算目前来看几何精度最好的PatchMatch也有精度分辨率，最终视差精细化时还是落到了离散空间，所以它未来被深度学习网络超越是可能的。

我觉得理论上的观点是，如果深度学习和传统几何都受到同样的关注度和研究度，那么传统几何算法的结果精确度一定会持续表现出优势，而深度学习的结果完整度和准确度也让传统几何算法难以望其项背。但是现实情况是，深度学习有着远超传统几何算法的关注度和研究度，这一定程度上导致深度学习和某些注重精度的工业实践中存在一个鸿沟，所以你可以看到，在精度无比重要的精确测量领域，比如工业测量、测绘、定位抓取等，深度学习还很少应用，反而是原理简单而精度很高的结构光重建技术大行其道。

而在一些不过分追求高精度的应用中，比如自动驾驶里的深度获取，并不需要每个点的精度都非常高，而完整度显得更重要，毕竟车前是否有物，和其离车距离是否足够精确两者之间，显然前者要更重要；再比如目前很流行的深度相机，虽然大多都是传统算法，但实际上很多情况下其并不需要非常高的精度，而采用传统算法居多的原因是传统算法的低算力，如果深度学习算力要求下降，或者芯片算力增强，则深度学习也将变得主流。

关于弱纹理恢复问题

弱纹理恢复是立体匹配的老大难，辐射差异对所有立体匹配来说至关重要，这是区分两个点是否为同一点的最关键信息。但是弱纹理的辐射差异十分微小且辐射值高度相似，这给基于局部窗口的立体匹配方法带来很大困难。

目前我所知的弱纹理恢复方法，大体上是有两类，一类是聚类分割法、一类是多尺度估计法。

聚类分割法建立的假设是局部的一块颜色相近的弱纹理区域极可能是属于同一块连续表面的，通常这个表面会假设为一个平面，在这个假设下有两类具体的思路去完成优化：
1、先对所有像素完成视差估计，在对像素进行聚类分割，对于恢复失败的像素，用同一块内的其他有效视差进行平面拟合，拟合方程可用来填补该缺失像素。
2、先对像素进行聚类分割，再基于聚类后的尺度上进行立体匹配，再将匹配结果映射到细粒度的像素尺度上。
这类方法实际应用是很少的，因为其假设看上去有明显缺陷，聚类分割本身就存在过分割和欠分割的问题难解决，且前景背景颜色相近的情况并不少见，这让问题反而变得更加棘手。

我这里想多聊聊另一类方法：多尺度估计方法。尺度是在我们人类感知中很重要的因子，如果将一块纯白的墙超近距离放在你的眼前，你肯定一头雾水，不知道这是什么东西，而且你的距离感会非常弱，感知不到这东西离你的眼睛到底有多远。而当距离慢慢拉远，你渐渐看到了墙周围的信息而推断出这是一堵墙，且距离感也会越来越清晰。尺度的大小决定了我们在有限视野内能接受到的信息范围，显然信息范围越大对我们的识别和定位都有好处，但也要认识到信息范围越大同时也会导致单位元尺寸下的信息清晰度变弱，两者必然是相互矛盾的。

回到立体匹配问题上，我们显然无法单靠一个像素信息来完成左右像素的配对，像素周围的局部信息是必须的，但是前提是局部窗口有足够的信息熵，在上一个例子来说，在距离拉远的过程中，在看到白墙轮廓之前，你都依旧无法识别它，所以对弱纹理来说，对局部信息范围的扩大需求显得尤为突出，我们认识到周围信息的范围对识别并定位能力非常重要，所以我们希望更大的窗口以接受更大范围的信息，所以增大窗口尺寸往往对弱纹理的优化有一定的帮助。

但增大窗口尺寸往往带来的是增大数倍的计算量，所以其实更实用的是减小图像分辨率，生成多个分辨率下的多尺度图像，在低分辨率尺度上对弱纹理取得更好的效果并投影到高分辨率尺度上。

我这里做了组对比实验来验证多尺度下的的SGM算法效果：
原图原图匹配1/2图匹配1/4图匹配
随着图像分辨率尺度的变小，在墙面上的视差越来越完整。这是多尺度匹配有助于恢复弱纹理的一个佐证。