1. 简介我们知道现有立体匹配算法一般被分类为局部算法、全局算法和半全局算法其中局部算法和半全局算法是应用最为广泛。在局部算法中一个最简单的做法就是采用某种像素相似性度量比如像素灰度差的绝对值AD给定左图中的一个点p在右图中的对应行上假设输入是已经校正好的图像搜索与其AD值最小的点q这样得到的点q就是p在右图中对应的匹配点p、q的水平坐标差称作视差。然而这种做法所得到的视差图中会包含大量的噪声即错误的匹配对原因可能是多方面的如传感器噪声左右相机的采集性能差异图像中存在大面积无纹理、弱纹理或重复纹理左右相机接收的光照差异室外环境等。一个更好的做法是不直接匹配单个像素而是匹配像素点所在的区域这个区域叫做支撑窗口 (support window)支撑窗口的尺寸可以是固定的也可以是自适应变化的。如下式所示由于支撑窗口内的像素提供了更多的信息因此可以有效降低匹配歧义。式中表示以点p为中心的方窗口内的所有像素表示颜色差异度q - d 表示只对q的x坐标减d前提是已经做了双目较正即同空间中的同一个点在双目中投影点的y值是相同的。然而使用支撑窗口的做法是存在问题的实际上它隐性的遵从了一个假定即窗口内的所有像素具有相同的视差。然而这个假定在很多情况下并不成立比如A. 窗口内的像素与中心像素位于不同的表面B. 窗口所捕获的是一个倾斜表面或曲面即非平行表面这个平行指的应该是与相机成像平面平行。如下图 (a) 所示Q点实际上位于一个亚像素的视差平面上R位于倾斜平面上S位于一个弧形表面上许多研究人员主要关注的是A中所描述的情况为了解决这种问题一个比较有效的做法是对窗口内的像素采用自适应权重进行匹配如下式所示这样的方法可以很好的避免edge fattening边缘平滑问题权重计算所使用的方法可以是类似双边滤波的核函数也可以是基于测地线距离的核函数那么如何解决B中的问题呢我们知道空间中任意一点都可以认为是在一个唯一的平面上如下式所示该平面的参数为基于上面的想法2011年Michael Bleyer 提出了一个相当新颖的立体匹配算法叫PMS该算法的主要思想是对每一个像素计算一个独立的最优3D视差空间平面如果该像素位于一个曲面上那么该平面代表曲面在该像素点处的切面在这个基础上用于匹配的支撑窗口就是not fronto-parallel support window简称slanted support window。这样一来问题的挑战就转移到了如何为每一个像素点在所有可能的视差空间平面中挑选出最优的视差平面。显然视差平面的数量是无限多的因此通过遍历所有的视差平面来寻找最优平面是不可能的。Michael Bleyer 找到了一个巧妙的方法解决这个问题那就是采用Patch Match的思想Patch Match本身是一个高效求解近似最近邻场 (Nearest neighbor filed) 的方法主要包括初始化、空间传播、随机搜索三个步骤。除了Patch Match中的空间传播外作者还另外提出了视图传播和帧间传播用于连续的视频帧能够更好的帮助算法收敛。如下图所示利用PMS不仅可以直接估计亚像素视差还能够精确的重建倾斜表面甚至能够重建圆形的曲面。2. 算法2.1. 模型算法的目标是计算每一个像素所在的视差平面一旦得到了该像素的视差就可以按照下式来计算其中和是平面的参数和是像素p的x坐标和y坐标。注意这里所谓“平面”是的误导的它并不是欧几里德空间的平面而是 (x, y, disparity) 空间的平面。该平面包含了欧几里德空间的一些信息也包含了双目基线的信息且前提是图像做了双目较正。待求解的视差平面是在所有可能的平面中使得聚合匹配代价最小的那一个平面其中表示所有视差平面的集合。由于集合内元素的数目是无限的所以不可能像传统的局部匹配算法那样通过检查所有的平面来找到聚合代价最小的那一个平面传统的局部算法是在一个有限的离散视差空间中进行搜索的。像素p在视差平面f下的聚合代价是按照下式来计算的这里表示中心位置在p处的矩形窗口。如果应用在视频中这里的矩形窗口就由2D变成了3D其中第三维代表前一帧或者后一帧。权重函数采用了自适应权重目的是为了降低egde-fattenning问题式中是一个人为指定的参数表示像素p和像素q在RGB颜色空间中的距离。当然你也可以使用其他的权重函数只要它能提升效果就行。函数用来度量待匹配像素对之间的相似性这里采用的方法是在上式中是通过q的视差计算出来的所以值在一个连续的实数区间内它的颜色和梯度可以通过近邻像素进行线性插值得到。参数用于平衡颜色项和梯度项的比重。截断参数和可以增强匹配代价在遮挡区域内的鲁棒性。2.2. 基于patch match的视差推理有了以上的铺垫现在最重要的问题就是如何通过最小化匹配代价来为每一个像素找到一个最优的3D视差平面。这个问题可以通过patch match来解决首先对所有像素的视差平面进行随机初始化或根据某些先验信息进行初始化然后基于迭代传播空间传播、视图传播、帧间传播、平面细化不断地更新所有像素的平面参数。patch match的优点是只要至少有一个像素的初始化视差平面位于或接近最优平面就可以找到剩余所有像素的最优平面。2.2.1. 随机初始化patch match的第一步就是对左右视图的视差平面进行随机初始化原则上是可以直接对平面f的三个参数、、进行随机赋值但是这样做无法保证在可允许的视差空间中进行均等的采样。因此需要对像素设定一个视差搜索区间注意这个区间是连续的然后从该区间中随机挑选一个视差值作为该像素的初始视差这样就得到了视差空间中的一个点有了点P只要再得到一个单位法向量就能计算出平面参数如果想要使用fronto-parallel window可以将法向量设定为如果想关闭亚像素估计可以将限制在离散的整数范围内取值。2.2.2. 迭代如下图所示迭代过程中每一个像素将经历4个阶段空间传播、视图传播、帧间传播、平面细化一般先处理左图然后再处理右图。在偶数次迭代中从左上到右下依次遍历每一个像素在奇数次迭代中则顺序相反。空间传播 (spatial propogation)空间传播的思想基础是在位置上相邻的像素一般具有相近的视差。设当前像素p的视差平面为其邻域像素的视差平面为若则将像素q的视差平面赋予像素p在偶数次迭代中p为q的左侧和上侧的像素在奇数次迭代中q为p的右侧和下侧的像素。视图传播 (view propogation)视图传播的思想基础是左右图中的像素点与右左图中的对应匹配点应当具有相同的视差平面。设左右图像素p的视差平面为其在右左图中的对应像素的视差平面为若则将像素的视差平面赋予像素。帧间传播 (temporal propogation)帧间传播主要用于视频序列中其思想基础是当前帧的像素p与其相邻帧的像素q的坐标相同那么它们应当拥有相近的视差平面。很明显这个假设在帧率较高的视频中是成立的。设当前帧像素p视差平面为其前一帧或后一帧的像素q的视差平面为若则将像素p的视差平面赋予像素q。平面细化 (plane refinement)平面细化的目的是通过更新像素的视差平面进一步降低匹配代价。由于平面可以由一个点和一个法向量表示所以平面的更新可以通过点坐标和法向量的更新来得到。设的最大允许变化量为的最大允许变化量为然后从中随机选择一项数值来计算从随机选择三项数值来计算法向量式中用于将向量归一化为单位向量这样就得到了一个新的平面若则将视差平面赋予像素p。这一步需要经过多次迭代才能完成初始时设定然后每次迭代完后将直到迭代停止。假如像素当前的视差平面是完全错误的初次迭代使用较大的搜索范围就有可能将其转移到正确平面附近之后的迭代中不断的缩小搜索范围使得视差平面在当前平面附近捕获视差细节能够适用于弧形表面。后处理部分首先对左右视差图执行左右一致性检验在小于设定阈值的情况下该视差点就会被设定为无效点然后进行填充。填充的方法是搜索无效点左侧最近邻和右侧最近邻的有效像素点设它们的视差平面分别为和选择其中视差较小的那一个平面赋给当前无效点。之所以选择小的那一个是因为无效点多为遮挡区域的点而遮挡区域往往处于背景之中。这样的缺点就是容易导致视差图中产生水平条纹为了减轻水平条纹可以对视差做加权中值滤波滤波核的参数与匹配阶段所使用的参数相同。2.3. 后处理当发生遮挡时相邻像素的深度会有阶跃性变化所以需要对遮挡情况进行较验。较验的方式是判断相互匹配的两个点的视差是否一致。基于一个假设遮挡区往往是背景区域被前景遮挡而造成的视差错误而背景是离相机更远的区域所以视差是较小值。2.4. 为全局算法构建数据项全局算法对于遮挡区域和无纹理区域的处理要优于局部算法所以本文提出的匹配代价还可以应用到全局算法当中只不过此时将无法在使用连续的视差平面。下图显示了局部算法对于纹理匮乏的图像匹配失败而全局算法却很好的处理了这种情况。3.代码实现代码地址GitHub - ethan-li-coding/PatchMatchStereo: PatchMatchStereo倾斜窗口经典效果极佳OpenMVSColmap稠密匹配算法。完整实现代码规范注释清晰博客教学欢迎star4. 实验这里选择了MiddleBurry数据集中图像进行实验效果如下图可以看到该算法生成的视差图是稠密的而且边缘保持的非常好整体视差精度较高。5. 总结PMS算法不同于传统的局部算法它不是直接估计视差而是估计视差平面而且利用patch match思想在无限多的视差平面中来推理出最优视差平面。因此它的两个最大的优点是(1) 能够直接计算亚像素视差(2) 能够处理倾斜表面和曲面这是其他局部算法所不具备的。PMS算法的性能比较有限虽然在middleburry上表现的确惊艳但是在处理室外场景时鲁棒性不是特别好特别是对于较高的图像噪声、大面积的弱纹理或重复纹理等当然其他的算法也不能很好的处理其效果一般弱于SGM和ELAS等算法。PMS算法的速度比较慢因为它的所有处理流程都是顺序性的不能并行处理目前已经有一些算法改进了PMS中的传播方式使其能够并行处理并应用于GPU这里给出论文名称《Massively Parallel Multiview Stereopsis by Surface Normal Diffusion》。参考资料必须收藏双目立体匹配算法Patch Match Stereo实用详解教程【码上实战】【立体匹配系列】经典PatchMatch: 6后处理_李迎松~的博客-CSDN博客_码上实战PatchMatch Stereo - Stereo Matching with Slanted Support WindowsMichael Bleyer, Christoph Rhemann, Carsten RotherStereo Matching—State-of-the-Art and Research ChallengMichael Bleyer, Christian BreitenederMassively Parallel Multiview Stereopsis by Surface Normal Diffusion, Silvano Galliani, Katrin Lasinger, Konrad Schindler