论文《Orientation-guided geodesic weighting for PatchMatch-based stereo matching》学习_oggw

Abstract

近年来，基于patchmatch的局部立体匹配方法取得了很大的进展，它使用了具有相似强度或颜色的紧凑和过度分割的区域。摘要提出了一种基于方向导向的测地线加权策略，利用patch作为支持区域，从patch中的一个支持像素沿导向方向搜索到感兴趣像素的近似最短路径。OGGW是通过累积路径上相连像素之间的亮度差异或颜色差异来计算的。通过模型拟合得到匹配成本更新后，利用OGGW对更新后的成本进行加权平均，得到经过筛选的成本体积。此外，本文还提出了一种将PatchMatch滤波器与曲面拟合(PMF-CS)相结合的滤波方法。通过曲面拟合并去除离群点，寻找一种可靠的回归模型来估计patch上的差异，从而获得亚像素精度的视差图。我们进行了大量的实验来评估OGGW和PMF-CS在成本体积滤波和视差估计方面的性能。实验结果表明，我们的算法能够产生准确的立体匹配结果，并优于目前最先进的基于patch的匹配方法。

1. Introduction

（2016SCI一区）在计算机视觉领域，密集双目匹配已经被研究了几十年，并在许多应用中得到应用，如导航[23]、场景重建[40]、对象识别[12]和3D恢复[11]。视觉任务要求从密集匹配中获得高精度的视差图。然而，由于噪声、失真或遮挡，生成的视差图有时可能不需要重新负责。为了解决这些问题，研究人员一直致力于开发各种条件下的鲁棒立体匹配算法。根据Scharstein和Szeliski[30]提出的稠密两帧立体匹配算法的分类和评价，大多数立体匹配算法可以分为全局匹配算法和局部匹配算法。一般来说，全局方法通常将立体匹配问题表示为在马尔可夫随机场模型上定义的能量函数上的极小化，其中平滑假设可以获得更好的结果，但计算代价较高。这是因为使用图切割[6,16]、最大表面[31]或信念传播[33]的全局能量最小化算法通常很耗时。另一方面，局部方法首先计算一对立体图像之间的立体匹配代价;然后在假设相邻像素可能位于同一目标上，从而具有相似的差异的基础上，在局部区域采用自适应支持加权进行成本聚集；最后采用赢家通吃（WTA）策略从聚集的成本中提取差异图。

该方法是一种高效实现快速边缘感知聚合的局部方法。提出了两个子问题:一是利用自适应支持加权(ASW)方法来评估同一局部区域内相邻像素对当前感兴趣像素的贡献，本文将其称为“锚点像素”;另一种侧重于局部区域，如可移动窗口[24]和自适应窗口[15]，以保持深度不连续。

通过广泛的评价研究，对现有的基于支持加权的局部立体匹配方法进行了总结。最近，基于代价量的边缘感知过滤使得局部匹配算法能够在结果质量和计算速度方面与全局算法竞争。Yoon和Kweon[41]将双边滤波器(BF)[37]引入到立体匹配中，实现边缘感知视差计算。由于BF计算量大，为了提高计算速度，出现了越来越多的方法，如快速BF[25]、O(1) BF[26]和实时BF[38]。然而，这些基于量化的方法并不能很好地执行[28]。He等人提出的导频滤波器(GF)在实时处理速度下获得了比BF更好的高质量结果。它也被应用于平滑[27]中的成本量，并在速度和准确性方面优于Middlebury基准[29]上的大多数本地方法。然而,由于GF预定义的方形窗口形状缺乏空间适应性，因此它的性能并不总是很好。此外，在基于交叉的局部多点滤波(CLMF)方法[18]中引入了自适应支持区域，其性能优于BF和GF，避免了固定窗口覆盖不相关区域。然而，CLMF方法只使用强度或颜色相似度的自适应支持权重，而忽略了像素之间可能由测地线距离表示的空间信息。在加权平均过程中，测地线距离无疑会直接影响局部区域中支持像素到锚点像素的加权。Hosni等人提出了一种测地线支持加权，它与测地线距离成反比。在一个方形窗口中，支撑像素与锚点像素之间的测地线距离定义为两个像素之间最短路径上的代价，其计算方法为相邻点之间8连通性的色差序列的最小和。由于最短路径是从正方形支持窗口中支持像素与锚点像素之间的所有可能路径集合中选择的，因此无法有效地实现该策略。

与基于分割方法获取立体匹配支持区域的方法[4,20,36,39]相比，基于patch的过分割方法[2,3,19]具有更好的性能。图像补丁包括具有相似强度或颜色的像素，并且具有紧凑和规则的形状[7]，被用作支持区域，以确保在一个区域内不会发生大的视差跳转。这就是为什么在局部立体匹配中，基于patch的方法比基于分段的方法有优势。

本文通过参考图1(a)所示的候选匹配像素与目标图像之间的成本计算，构建初始成本体积。Tan等人在视差图[35]上提出了一种带有局部多项式逼近和距离制导(multipoint LPA)的多点滤波方法。该方法通过结合强度或颜色信息以及像素的空间位置信息来估计差异，避免了由于信息不完整而导致的平滑错误。但是，如果在WTA步骤中排除了正确的差异，那么对于算法来说更新视差图可能为时已晚。考虑到成本体积包含了相对像素更全面的信息，对成本体积进行了两个步骤。首先，我们对初始成本体积采用多点LPA法，通过模型拟合得到所有的成本更新。其次，提出了一种面向导向的测地线加权策略，对更新后的成本进行加权平均。对初始成本卷中所有点的成本进行归一化处理。以规格化成本为0.5的点为例，说明成本体积滤波的过程，过程中每一步的效果如图1所示。图1(b)给出了选择的初始成本点。然后使用每个切片的多点LPA模型分别对这些成本进行平滑处理，获得如图1©所示的成本更新，最后使用图1(d)所示的OGGW策略的加权平均过程对更新后的成本进行边缘感知过滤。在代价更新的加权平均过程中，我们选择简单线性迭代聚类算法[1]获得patch作为OGGW策略的支持区域。有两个观察结果表明，SLIC方法优于其他最先进的方法[17,21,22]。一是SLIC获得的patch较好地保留了图像中物体的边界，二是SLIC方法运行时间较短。从参考图像中获得的小块不仅作为更新代价加权平均的支持区域，而且也应用于视差估计过程。由于来自同一patch的像素更有可能共享相同的物体曲面，因此每个patch的视差图都是通过曲面模型得到的，这种曲面模型具有亚像素级的精度。这种方法被称为带有曲面拟合(PMF-CS)的PatchMatch过滤器。PMF-CS方法在视差图[19]上的精度高于使用常数(PMF-C)或倾斜平面拟合(PMF-S)的PatchMatch滤波器。

本文提出了一种新的局部立体匹配方法，主要有两个贡献:(1)提出了一种对更新成本进行加权平均的OGGW策略，用于过滤成本体积;(2)提出了一种通过去除离群点的曲面拟合得到每个patch上可靠模型的PMF-CS方法，以获得具有亚像素精度的视差图。实验结果证明了该方法的优越性。

2. Outline of the proposed method

首先，我们的方法的预处理部分由两个步骤组成:(1)使用SLIC获得参考图像上所需的patch数量，用预定义的patch总数对[1]方法进行处理; (2)将经过校正的立体图像作为输入[32]进行成本体积的初始化。

其次，对成本-体积滤波过程分两步进行：（1）为了抑制成本-体积上的噪声，采用多点LPA方法[35]通过模型拟合获得初始成本的成本更新；以及（2）对更新成本进行加权平均，提出了一种OGGW策略，通过搜索沿引导方向的近似最短路径来获得从贴片中的支持像素到锚像素的权重。然后，得到具有边缘保留的滤波代价体积。然后，通过WTA步骤获得初始视差图，通过左右交叉检查程序选择无遮挡的像素。为了提高视差图的精度，提出了一种对初始视差图上每个patch进行可靠曲面拟合的PMF-CS方法。最后，我们得到了具有亚像素精度的视差图。我们的方法框架如图2所示。

3. Cost volume filtering

该方法包括两个步骤。一个是使用多点LPA方法的成本更新。该方法将空间位置、强度值或颜色分量加入到LPA模型中，更新初始代价$C(p,p_d)$，初始代价$C(p,p_d)$由参考图像$I_R$上的像素p和目标图像$I_T$上相应的像素$p_d$通过移位d计算得到。另一个过程是使用OGGW补丁策略对更新成本进行加权平均。将参考图像$I_R$分解为K个具有 P = { P ( k ) ∣ ⋃ K = 1 K P ( k ) = I R , ∀ k ≠ l , P ( k ) ⋂ P ( l ) = ∅ } P=\{P(k)|\bigcup_{K=1}^KP ( k ) = I _R, ∀ k \neq l,P ( k )\bigcap P ( l ) = ∅\} P={P(k)∣⋃K=1K​P(k)=IR​,∀k​=l,P(k)⋂P(l)=∅} 。这里K取决于预定义的patch数量，标记为K的patch上像素p记为p∈p (K)，如图3所示。

[35]的作者认为，LPA模型是基于参考图像中以像素qi为中心的方形窗口${\Omega }_{qi}$中的匹配代价建立的，锚点像素p是${\Omega }_{qi}$中的像素之一，且p∈${\Omega }_{qi}$。利用其简单性和较高的计算效率，采用系数为Aqi和Bqi的线性回归模型拟合方形窗的匹配代价。线性多点LPA模型如下：


最后一个C‘’(p, pd)通过对更新后的代价Cqi(p, pd)进行加权平均得到，这些代价Cqi (p, pd)来自多个LPA模型，这些模型以patch p(k)中的每个像素qi为中心，锚点像素p的相关加权得到。

正方形窗口大小的选择${\Omega }_{q_i}$通过多点LPA模型拟合和patch P(k)对更新成本进行加权平均的成本更新的q i有待确定。一个具有固定计算复杂度的方形窗口大小的盒形滤波器被多点LPA模型用来更新成本。锚点像素p的最终成本估计是通过对更新后的像素p的成本进行加权平均得到的，像素p已经与以patch p (k)中每个像素为中心的多个LPA模型进行了拟合。边界上的像素的一个补丁覆盖的多点LPA模型如图4所示,窗口的大小广场多点LPA模型被定义为$(2r_w-1)\times (2r_h-1)$,这是由最大宽度w和高度r h的补丁。patch P(k)的形状是任意的，取决于参考图像的过度分割。同时，patch P(k)的大小是由patch内的像素数量决定的，记作|P(k)|。

如图1所示，通过对更新后的成本进行加权平均，可以得到更可靠的成本体积滤波。在加权平均过程中，使用patch作为支持区域，不会使滤波后的代价体积中的物体边界过于平滑。

4. Orientation-guided geodesic weighting (OGGW)

在本节中，我们将讨论成本更新加权平均过程中锚像素p和支持像素q i之间的加权$w_{p{q}_i}$。尽管已有许多用于局部立体匹配的ASW方法被提出，但没有一种是专门用于拼接计算的。以下两个方面提供了为什么patchweightingis不同于目前的ASW方法:(1)同一patch中具有相似强度或颜色的像素以及相近的空间距离，使得同一patch上的支持像素到锚点像素的权重更加可靠;(2) patch是内部所有像素的一个固定的支持区域，因此我们不需要为每个像素寻找每个支持区域。为了获得测地线支撑的重量，Hosnietal。[14]利用[5]的方法计算大地测量的近似值，即从支持像素到位于正方形支持窗口中心的锚点像素的距离。在这个过程中，可以使用遮罩来计算相邻点的色差，它至少通过三次向前和向后的迭代，以行的主要顺序遍历整个正方形支撑窗口。对于一个有效的替代方案，我们关注于从每个支持像素到补丁中的锚像素的定向引导搜索，以计算近似最短路径，而不是以方括号窗口中所有像素的行主顺序多次迭代的向前和向后搜索。因此，本文提出了一种新的OGGW策略。从一个支持像素到锚点像素的加权计算，首先沿着引导方向搜索一个近似的最短路径，然后计算沿着这个路径相邻点之间的距离序列的总和，作为一个近似的测地线距离。相邻两个点之间的距离是根据两个像素的亮度差或颜色差异来定义的。

根据最终获得的成本估算Eq.(3), $w_{pq}$我用作支持像素的加权问我在补丁P (k)的锚像素的加权计算P。参考图像中的信息,以及像素之间的权重$w_{p{q}_i}$我是由p和qi

$\gamma$是一个用户定义的参数来控制权重。D(p, qi)是支撑像素i和锚点像素之间的近似测地线距离，通过在几乎恒定强度或颜色的引导方向上搜索像素的等值来近似计算hortestpatha。如图5(a)所示，q_{in} (n = 1,2,3，…，8)表示像素$q_i$的8个连通性。计算了像素q i与其8个连通邻居q in之间的强度或色差


Opqi是orientation-guided子集决定由pixel $q_i$指引方向像素p。如图5所示(一个),pixel qi可能是位于八锚像素的相对取向[8]p,其中方向左,右,前,和底部是四个主要方向。如果像素q i位于像素p的扩展方向与左侧扩展方向之间的区域，则定义为位于像素p的方向左上部，则定义为右上部、左下部、右下部。根据图5(a)所示的像素q i与p之间的空间位置，像素q i位于像素p的左上角，像素p位于像素q i的右下角。然后定义右下方向为从像素q i到锚点像素p的引导方向，计算近似测地线距离。当确定引导方向时，然后从分别对应于八个引导方向的八个可能子集{O left、O right、O top、O bottom、O top left、O top right、O bottom left、O bottom right}中选择定向引导子集O pq i。像素qi的8个连通性，包括8个像素qin(n = 1,2,3，…,8)分为八orientation-guided子集Oleft = {qi4、qi5 qi6}, Oright = {qi1、qi2 qi8}, Otop = {qi6、qi7 qi8}, Obottom = {qi2、qi3 qi4}, Otop−左= {qi5、qi6 qi7}, Otop-right = {qi1、qi7 qi8}, Obottom-left = {qi3、qi4 qi5},和Obottom-right = {qi1、qi2 qi3}。每个像素都有3个像素，保证从像素qi到p的引导方向上的所有候选像素都被用来比较累积的差异。从像素qi到锚点像素p的近似最短路径的每一步都是由其定向引导子集中的一个选择决定的。

根据式（6），通过最小化两个分量之和来获得近似测地距离d（p，q I）：一个是q i及其方向引导像素q i的差d（q i，q I），另一个是它们各自先前的近似测地距离d（p，q n）到锚像素p，如图5（b）所示。因此，用公式（4）将选定的最小距离转换为较大的支承权重。幸运的是，通过在方向引导子集中累积像素的近似测地线距离，可以获得当前支持像素到锚像素的近似测地线距离。如图5所示(b),像素qin orientation-guided子集总是比像素位于靠近我的锚像素的空间距离,这些更紧密的像素的优先级计算的近似测地线距离锚像素。因此，这种OGGW策略可以降低测地线距离计算的计算成本，使我们能够有效地计算出patch上的权值。算法1总结了我们OGGW策略的算法步骤。

5. PatchMatch filter with curved surface fitting (PMF-CS)

通过成本量筛选的过程，由多个LPA模型更新初始成本量，并利用OGGW策略进行加权平均进行成本更新。然后得到过滤后的成本体积。然后，使用WTA方案从过滤后的代价体积中提取粗视差图，并使用左右交叉检查检测遮挡的像素。最后，得到具有像素精度的立体图像上对应像素之间的初始差异。

为了模拟一个场景的视差，使用PMF- c和PMF- s方法[19]开发了一个PatchMatch filter (PMF)来近似patch上的常量平面或倾斜平面。然而，场景中物体的表面大多不是平面或倾斜平面，估计的常数或倾斜平面可能并不代表物体表面的真实差异。为了获得更精确的视差图，我们提出了一种曲面拟合方法，称为PMF-CS，该方法用于基于PatchMatch滤波器的初始视差图拟合。

其中q表示patch P(k)中的像素，坐标为(x q, y q);a k, b k, c k, d k, e k, f k是用最小二乘法计算出的曲面的参数。其次，为了识别离群值，我们计算了WTA步骤后的初始视差与曲面拟合估计视差之间的残差。如果一个视差的残差大于所有其他视差残差的95%，则视该视差为离群值，并在拟合过程中去除。将曲面模型分离出来后，只剩下不完整的曲面模型的求取过程就完成了。因此，对每个patch建立了一个更加可靠的曲面模型，得到了具有亚像素精度的视差图。

该方法得到的场景曲面精度高于PMF-C和PMF-S，如图6所示。从参考图像中获取的patch边界覆盖在其视差图上。然后分别用常数、倾斜平面和曲面拟合patch P(k)上像素点的视差值。曲面拟合结果与常数拟合或斜平面拟合结果相比，精度更高。

6. Experimental results and discussion

我们在本文中提出的OGGW和PMF-CS策略的性能与当前在米德尔伯里网站[29]上最先进的算法进行了比较。

6.1. Parameter selection

我们对所有图像对使用相同的参数。参数K是预处理步骤中使用的patch数量，它影响了OGGW策略的精度和计算复杂度。在本文中，OGGW的计算复杂度主要与公式(6)中给出的近似测地线距离的计算有关。假设参考图像上的patch数量为K, patch P (K) (K = 1,2,3，…其中，K)包括所有带有标签K的像素，所有像素的OGGW计算复杂度为吗?K =1 | P (K) |
2，其中|P(k)|为patch P(k)的大小。我们的算法对4个不同patch编号的标准Middlebury数据集[29]的结果如图7所示。如图7(a)所示，计算复杂度随着patch数量的增加而降低。然而，更小的patch尺寸会降低对更新成本进行加权平均的可靠计算，并且会导致视差图上的错误像素比例更高，如图7(b)所示。“Teddy”和“Cones”数据集的视差图上出现错误的像素百分比最低，为5000块，而“Tsukuba”和“Venus”数据集上出现错误的像素百分比最低，为6000块。计算OGGW策略中权重的另一个参数γ也对成本更新的加权平均过程产生影响。因此，在K和γ之间进行双参数测试，以检查我们的算法的性能，如图8所示。在此基础上，观察到两个参数之间的折衷关系，并将其设置为K=6000和γ=10。

6.2. Results evaluation

首先，使用方形窗口作为支撑区域，将我们的OGGW策略与GEO[14]策略在获取近似测地线距离方面进行比较，参考文献[14]。我们还使用补丁作为OGGW策略的支持区域来进行测试。我们分别使用带有方形窗口的地理策略、带有方形窗口的OGGW策略和带有补丁的OGGW策略来计算成本聚合步骤的支持权重。局部立体匹配的其他步骤与地理策略中的步骤相同。最有效的局部立体匹配加权平均算法GF[27]的计算复杂度为每个像素O(1)，与支持区域的大小无关。然而，GEO和OGGW策略的计算复杂性取决于它们支持区域的大小。GEO策略在O(|W|)时间内执行，其中|W|为正方形窗口内的像素个数。我们的OGGW策略在O(|P(k)|)时间内执行，其中|P(k)|是patch中的像素个数。通过运行时间的实验，可以很好地反映计算结果。对数据集进行了校正，消除了径向畸变，使图像对只存在水平差异。此外，使用MATLAB R2012b在3.0 GHz CPU和4gb RAM的标准PC上测试运行时间的对比如表1所示。由于我们的OGGW策略需要一定的时间来确定导向方向，因此，带有方形支持窗口的OGGW策略的运行时间要比GEO策略的运行时间长。但是，我们使用补丁作为固定的支持区域的OGGW策略比移动支持区域的GEO策略运行得快得多。这表明我们使用patch的OGGW策略在计算支持权重时更有效。如图9所示，使用我们的OGGW策略和支持加权的补丁来提高视差图的可靠性，我们的OGGW策略以更高的运行速度和更低的像素误差百分比来优于GEO策略。图15给出了米德尔伯里[29]数据集的更多对比实验。

其次，我们比较了使用OGGW的加权策略和最新的自适应支持加权策略的性能，包括GEO[14]、GF[27]和CLMF[18]。一个例子是Middlebury数据集

“Baby”[29]大小为413×370像素，如图10所示。对于这些算法，参数设置与原始参考中的相同。结果表明，基于补丁的OGGW策略在提供更好的视差估计和边界保持方面取得了最好的性能。为了更好地理解为什么我们提出的OGGW策略在加权平均滤波方面优于传统的自适应支持加权策略，图11中示出了数据集“Teddy”的特写部分的示例。OGGW策略通过沿着引导方向搜索近似最短路径来累积测地线距离，这使得具有相似强度或颜色的像素和近似空间距离成为重要的连接。此外，我们引入了patch作为OGGW策略的支持区域，以避免区域跨越深度不连续。这样就得到了更可靠的权重，从patch中的支持像素到锚点像素。OGGW是在边界保留的情况下过滤成本体积的关键策略。

然后，我们将所提出的PMF-CS方法与PMF-C和PMF-S[19]方法的性能进行了比较。这些方法分别适用于曲面模型、正平面模型和倾斜平面模型。以Middlebury数据集 “Bowling” (具有443×370像素)[29]为例，仅进行遮挡检测和填充，并使用三种PatchMatch过滤器，如图12所示。与PMF-C和PMF-S相比，PMF-CS方法对不同深度物体表面的重建效果更好。为了理解为什么PMF-CS在视差估计上比PMF-C和PMF-S表现得更好，图13给出了一个带有数据集“锥”的特写部分的例子。在三种基于补丁的方法中，我们的PMF-CS在锥的顶部和边缘表现最好。我们的PMF-CS方法相对于pmf - c和PMF-S[19]的主要优点是，在patch上使用的是曲面拟合模型，而不是常数或倾斜的平面模型。平面模型并不总能很好地表示物体的表面，而曲面模型可以很好地表示多种类型的表面，包括正面、倾斜和曲面。然而，曲面拟合的计算复杂度随着拟合函数阶数的增加而增加。最后，我们在四个标准的Middlebury数据集[29]“Tsukuba”（384×288像素）、“Venus”（434×383像素）、“Teddy”（450×375像素）上运行本地立体匹配算法，结合我们的OGGW策略和PMF-CS方法在代价体积滤波过程中的视差估计，并以450×375像素的“锥”来测试我们的算法的性能。结果如图14所示。我们的算法在“Tsukuba”、“Venus”、“Teddy”和“Cones”数据集上的性能在Middlebury网站（第2版）上进行了评估，并根据所有像素（all）、非遮挡像素（vis）和近深度不连续可见像素（disc）中的错误像素百分比进行排序。表2显示了我们的算法和其他本地方法的结果，如PMF[19]、PatchMatch[3]、CLMF[18]、GF[27]和GEO[14]。我们的算法名列榜首。在图15所示的其他数据集[29]上也进行了比较实验，结果证明了我们方法的优越性。

7. Conclusion

提出了一种新的基于更新代价加权平均的局部立体匹配方法。本文主要有两个方面的贡献。所提出的OGGW策略提供了一个合理的支持权重，通过搜索从支持像素到相同的贴片中的锚像素的引导方向的近似最短路径，这提供了保留边界不连续性的期望属性。我们还提出了一种基于曲面拟合和离群点去除的PMF-CS方法来估计亚像素精度的视差图。通过大量的实验验证了该方法的有效性，并显示了其相对于当前最新方法的独特性。与最新方法的比较也表明，我们的OGGW和PMF-CS策略在当前流行的基于补丁的方法上具有竞争力。我们的进一步工作将集中在降低权重计算的计算成本和改进基于补丁的回归模型上。