1.引言
本文是PatchMatchStereo[1]第二篇拾遗，主要讲解PatchMatch的深度/视差传播策略，以及在其基础上，介绍几种基于PatchMatch的改进传播策略，分别是ETH的Gipuma[2]方法和华中科技大学的ACMM[3]。不同于SGM在极线纠正之后的影像上进行同名极线(核线)上搜索，PatchMatchStereo在整个视差空间内进行搜索，既保证全局搜索的准确性，又提升了算法的效率。但其本身的传播策略无法极尽GPU效能，以至于PMS的立体像对视差估计速度比较慢。直到Gipuma等方法提出新的传播策略后，才使得GPU加速和PatchMatch算法在多视图立体中应用成为可能，因此，本文主要介绍传统方法中的视差/深度传播策略，并简要介绍一个在传播方面的经典深度学习方法。
2.PatchMatchStereo——串行传播策略
PMS虽然可以得到较为精确的视差估计结果，又因为随机算法的原理而使得算法本身可以以较低的显存消耗估计较大的分辨率的影像，但PMS的问题就是因为其串行传播(当前像素的传播视差必须来源于左右临近像素迭代的结果)而导致效率低下，因此，想要PatchMatch类型的算法达到秒级的深度图估计效率，需要提出一种新的传播策略。
图2 PMS串行传播策略
3.Gipuma——棋盘格传播策略
PMS是按照对角线方向进行视差空间的串行传播，也就是每一个像素都受限于前一个像素，从而无法彻底利用GPU资源，ETH则提出一种可利用GPU多核结构的四周扩散传播策略。如图3所示，该方法将一张图中所有的像素，按照国际象棋格分割为红黑两组，主要思想是，每次仅更新单个组别，而且每一个像素更新的深度传播至来源于局部领域。如图3-b)，标准的局部领域可以设计为20个局部邻域像素，从而利用更大的感受野来传播深度，以更快地算法收敛。图3-c)则是另一种加快传播地策略，进利用最近、最远的八个邻域像素对应的视差进行传播。
图3 红黑棋盘深度扩散示意图
从图4可以看出，深度估计的精度均值会很快收敛，而完整度随着迭代次数的增加也不断提升。一般实验迭代八次可以得到很好的结果，到最后的迭代过程中，仅有一些边缘细节在改变。
图4 迭代精度结果
Gipuma还有一个贡献是将PMS拓展到了多视图立体中，同时加上了多视图中的几何一致性检验，即通过共面单应变换来确定多视图的共视关系，因进行视角选择和匹配代价计算，本文不再赘述。开源代码为：https://github.com/kysucix/fusibile
4.ACMM——自适应棋盘格采样
Gipuma提出的棋盘格策略不仅使得深度估计的效率不断提升，还将PatchMatch引入了多视图几何的算法之中，在其基础上，华中科技大学根据gipuma中棋盘格的固定采样问题提出了一种自适应棋盘格采样策略(图5右)。
首先，ACMM采用Gipuma中的思想对中的像素进行划分，并分为红黑两组。不同与使用固定的期盼，ACMM将扩散领域扩展成四个V形区域和四个长条区域(图5 右)。每个V形区域包含7个样本，而每个长条区域包含11个样本(注：图5右图仅为示意图)，论文中数值和代码吻合。然后在这样的区域重随机采样，并进行视差对比。同时引入多视图的检测，这意味着一个拥有更小的多视图匹配代价的视差可以更好的表示三维平面。通过实验表明这样的策略可以加速算法的收敛，同时提升了算法的精度。
图5 Gipuma(左)与ACMM(右)采样策略对比
当然，ACMM方法中自适应传播策略仅仅是一个小改进，在深度传播之后，ACMM还进行了视角选择和多尺度、多视角的几何一致性检验，并以低分辨率下的深度图上采样后的结果，利用几何一致性指导高分辨率深度图的深度估计，文中利用前向-后向重投影误差来表示这个几何一致性，在优化后的结果，特别是弱纹理部分的完整度(图6-f)则大大增加。
图6 深度估计结果比较
5.深度学习方法——SPN
传统方法固然有其精度高的优势，但还需要提及深度学习方法，这里我们介绍一种经典的深度补全应用上的传统方法——空间传播网络(Spatial Propagation Network[4]，以下简称为SPN)。SPN是通过监督学习方法，学习深度/分割结果在特征上的空间临近关系，进而指导稀疏图向稠密图的转换。
在该文中，SPN主要用于图像分割应用，方法与深度估计的原理一致，网络结构如图7所示，首先，利用RGB图通过一个神经网络学习在不同方向上的当前像素与临近像素的邻接关系(Affinity)，图7中，guidance network输出了四个绿色的结果就表示四个传播方向的邻接关系图。然后输入一个粗略的分割掩膜，通过与四个传播方向的邻接关系卷积运算，再通过反卷积得到优化结果，本质上，是通过RGB或者高维特征，计算每个像素在邻域内与其他像素的邻接关系，从而来学习卷积核中的权重，越相似的特征，其学习到的权重越大。
图7 SPN网络图
文中一开始介绍了一种单路四向传播的策略(图8-a)，为了传播效率和准确度，又介绍了三路四向传播的策略(图8-b)。对于单路四向传播，以从左向右传播为例(1式)，
a)单路四向传播策略 b)三路四向传播策略
图8 SPN传播策略
将预分割结果输入到三路四向SPN网络中，可以得到更为精确的结果，而且相比较基于深度学习的马尔可夫场方法效率更快且精度更高。
图9 图像分割结果
6.总结
本文主要回忆了PMS的传播方法，并介绍了在此基础上的一些改进方法，例如Gipuma和ACMM等多视图立体的传统方法，还有基于深度学习的SPN网络。可以看到，虽然本质上深度传播知识一种加快收敛的策略，但却能在弱纹理的空间上，极大地提升估计精度和分割精度。目前在ETH3D高分辨率数据集跑分上，领先的方法85%以上都是基于传播和PatchMatch改进的方法，在GPU加速下，可以估计出非常完整且高精度的场景和物体模型。下一篇文章，我们将介绍最新的CVPR2021的PatchMatchNet[5]，这篇文章不仅将PMS的思想深度学习化，而且是少有的将传播策略使用在多视图立体中的方法，敬请期待。
参考文献
[1] Bleyer M, Rhemann C, Rother C. PatchMatch Stereo-Stereo Matching with Slanted Support Windows[C]//Bmvc. 2011, 11: 1-11.
[2] Galliani S, Lasinger K, Schindler K. Gipuma: Massively parallel multi-view stereo reconstruction[J]. Publikationen der Deutschen Gesellschaft für Photogrammetrie, Fernerkundung und Geoinformation e. V, 2016, 25(361-369): 2.
[3] Xu Q, Tao W. Multi-scale geometric consistency guided multi-view stereo[C]//Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2019: 5483-5492.
[4] Liu S, De Mello S, Gu J, et al. Learning affinity via spatial propagation networks[J]. arXiv preprint arXiv:1710.01020, 2017.
[5] Wang F, Galliani S, Vogel C, et al. PatchmatchNet: Learned Multi-View Patchmatch Stereo[J]. arXiv preprint arXiv:2012.01411, 2020.
