基于改进自适应权重的三边滤波立体匹配算法

潘卫华，杜 旭

华北电力大学 计算机系，河北 保定 071000

1 引言

双目立体视觉赋予了计算机类似人类视觉的能力，左右两台平行放置的摄像机模拟人类的两个眼睛，通过改变摄像机位置，从各个角度采集拍摄场景的二维信息[1]。由于摄像机参数已知，可通过公式计算得到摄像机与拍摄位置的距离，从而进一步得到拍摄场景的深度信息[2]。双目立体匹配是计算机视觉中的重要分支，广泛用于三维重建、自动驾驶、机器人导航与避障等领域，因此提高双目立体匹配算法的匹配精确度和运行速度具有重要的意义[3]。

根据获取视差图方式的不同，双目立体匹配算法分为全局立体匹配算法和局部立体匹配算法[4]。全局立体匹配算法指在整个图像集或者某个子集内寻求能量函数的极小值，从而得到双目立体匹配的视差图（Disparity Map），该算法匹配精度较高，但是得到准确匹配结果的同时也带来了巨大的计算复杂度，从而大大降低了匹配速度[5]。局部立体匹配算法是通过匹配代价函数计算某一窗口相邻两个像素之间的相似性得到匹配代价，对代价进行聚合，最后，通过胜者为王（WTA）优化方案进行视差优化，得到最终视差图[6]。局部立体匹配方法的复杂度为O(NWD),N、W、D分别是图像大小、窗口大小和视差范围，相比全局立体匹配算法，局部算法的匹配速度有了大幅度提高，但是匹配结果略有逊色。

近年来，许多学者提出了一系列双目立体匹配改进算法。Einecke 等[7]提出了一种基于标准互相关函数的局部立体匹配算法，该算法提高了立体匹配的准确率，但是图像边缘处的匹配效果不佳。龚文彪等[8]提出了一种基于颜色内相关的自适应权重方法，很大程度上消除了光照差异对匹配精度的影响，但是匹配速度没有得到很好的提高。Yoon 等[9]根据色彩相似性和几何距离确定权重，提出了一种自适应支持权重（ASW）算法，降低了匹配复杂度，但无法有效解决边缘匹配模糊性问题。全局匹配算法[10-11]通过添加几何方向向量约束，建立斜面匹配模型，有效解决了倾斜平面匹配模糊的问题，但是很大程度上增加了匹配复杂度，增加了运算时间。基于双边滤波器的自适应权重立体匹配算法[12-13]取得了与全局算法相当的匹配结果，但在视差不同、颜色相似处的匹配效果不佳。

针对以上问题，本文通过引入边界强度项，分别从颜色特征和距离特征两方面测量两个像素之间视差不连续性的强度，边界线索在文献[14]中用于构造更忠实的树，来改进基于最小生成树（MST）的代价聚合方法[15]，对传统的双边滤波自适应权重算法进行改进，提出一种三边滤波自适应权重匹配方法，在有效提高匹配精度的同时，通过递归实现，满足了双目立体匹配实时性的要求[16]。在Middlebury 基准测试集上的实验结果验证了引入的边界强度项的有效性。

2 双边滤波立体匹配

2.1 双目立体匹配原理

典型的双目立体视觉系统可由图1表示，两台平行放置的摄像机从不同视角捕获相同的场景，得到摄像机的左右视图。

图1 双目立体视觉示意图

其中，P点为三维世界中的物理点，在左右摄像机上的成像点分别为pl和pr,f为焦距，根据三角测量原理可得：

点P距离拍摄点的距离（深度）D为：

其中，d=dl-dr称为视差（Disparity）。

双目立体匹配过程可由图2表示，局部立体匹配算法的处理过程包括匹配代价计算，代价聚合，视差优化和视差细化，局部立体匹配算法的准确性和效率性都高度依赖于代价聚合步骤。

图2 双目立体视觉系统流程

2.2 双边滤波自适应权重

自适应权重（ASW）算法属于局部立体匹配的新技术，而基于双边滤波器的ASW 方法实现了出色的性能。ASW方法的关键思想是估计支持窗口内每个像素的单个权重，然后汇总加权代价。在基于双边滤波器（BF）的权重函数中，权重与该像素和中心像素之间的颜色相似性和空间距离成正比[17]。因此，执行代价聚合等同于使用具有边缘保留属性的BF来过滤代价量。双边滤波权重函数遵循颜色规则和空间规则。

（1）颜色规则：如果两个像素具有相似的颜色，则它们更可能位于相同的视差范围，因此权重应该很高。颜色相似性定义为：

其中，q是以像素p为中心的支撑窗口内的像素。参数λc为调整颜色相似性项。颜色距离ΔCpq表示p和q的颜色之间的欧几里德距离：

（2）空间规则：如果两个像素在空间上接近，则它们更可能位于相同的视差范围，因此权重应该高。空间距离项定义为：

其中，参数λd为调整空间距离项，空间距离ΔDpq表示p和q的坐标(x,y)之间的欧几里德距离：

然后，将这两个项组合作为最终的BF权重函数：

3 改进算法

所提出的基于三边滤波（TF）的ASW方法包括以下五个步骤：（1）预处理；（2）匹配代价计算；（3）匹配代价聚合；（4）视差优化；（5）视差细化。在这个流程中，提出了TF权重函数及其在代价聚合步骤中的递归实现。这五个步骤如图3所示。

图3 TF的ASW方法步骤示意图

（1）预处理：为了去除孤立的像素，应用标准中值滤波（3×3窗口）来预处理输入的原始图像。

（2）匹配代价计算：文献[18]提出颜色和梯度的截断绝对差异匹配代价函数，来计算两个像素之间的匹配代价。一对候选点之间的原始匹配代价Cd(p)为：

其中，d是视差，∇x是x方向的导数；ε平衡颜色和导数项；τ1和τ2是截断值，以减少被遮挡像素的影响。

（3）代价聚合：ASW方法用于在支持窗口内聚合原始匹配代价，使用不对称策略来计算权重掩模，在视差为处的像素p的聚合代价为：

其中，ωp表示以像素p为中心的支持窗口，q是ωp中的支持像素。

（4）视差优化：采用常用的胜者为王优化策略从一组候选集中选择最佳视差D(p)：

（5）视差细化：在最后一步中，通过左右一致性检查，选择稳定、有效的像素，对生成的视差图D(⋅)进行后处理以消除误匹配并处理遮挡区域的匹配问题。稳定像素应通过一致性检查，并且有效像素应满足D(⋅)＞0，否则在每个视差水平d处的每个像素p的新匹配代价被重新计算：

然后，对该新匹配代价执行聚合步骤以获得新的聚合代价，其后是视差优化步骤以生成最终视差图。

3.1 三边滤波（TF）权重

颜色规则和空间规则可以解决大多数深度模糊问题，但无法为位于不同视差的两个附近像素分配准确的权重，因此，本节提出边界规则，引入一个新的边界强度项We来解决模糊性问题，即如果两个邻近像素之间存在边界，则它们不太可能位于相同的视差，因此权重应该更低。

其中，参数λe为调整边界强度项，边界强度距离ΔEpq是使用局部能量模型计算的[19]。具体地，图像的局部能量为不同取向上的能量组合，给定图像I，像素p处的局部能量表示为：

其中，*表示卷积运算符，奇数相位滤波器Fθ,odd和偶数相位滤波器Fθ,even是方向θ处的一对正交滤波器，其通过文献[20]中使用的偏移高斯函数的差来计算局部能量对边界具有最大响应。偶数相位滤波器Fθ,even定位边界的位置，像素p的相位定义为：

其中，θmax是给出最大响应的方向：

对于两个相邻像素i和j，它们的边界强度ΔE(i,j)的距离表示为：

对于任意两个像素p和q，可以定义连接它们的线。假设在该连接线上有N个像素，那么它们的边界强度是：

其中m和m+1 代表两个相邻像素。

如果两个像素之间没有边界，则边界强度项等于1，边界越强，边界强度项越小。然后，将提出的边界强度项与先前的颜色相似性项和空间距离项组合，形成TF权重函数Wtf(p,q)：

3.2 三边递归滤波

由于上文所提出的TF权重函数的实现非常耗时并且不能真正满足实时性的要求。因此，在本节提出一种递归三边滤波（RTF）权重函数，它受到双边递归滤波RBF的启发，以提高其计算效率。

设x表示阶数为n的递归系统的1-D输入，y表示输出。一般递归系统为：

根据上述通式，一阶递归滤波器的输出可以简化为：

因此1-D BF可以聚合为：

其中，x表示2-D 图像的扫描线，q是该扫描线上的像素。在BF 权重函数的递归实现中，颜色相似性被重新定义为：

其中，i和i+1 表示两个相邻像素。空间距离项被重新定义为：

然后可以通过水平和垂直执行上述1-D 递归实现来计算最终的2-D双边滤波结果。

3.1节提出的TF权重函数由两部分组成，BF部分和增加的边界强度部分。这两个部分可以分别计算然后加起来。让x表示扫描线，然后像素q处的x的1-D TF值是：

BF 部分的递归实现在式（21）已给出，将边界强度项重新定义为：

颜色相似项和空间距离项与RBF 权重函数中定义的相同，使用新的边界强度项，由数学归纳法可得：

在提出的三边递归滤波权重函数中，使用四对正交滤波器来检测边界，这些滤波器是预先计算的并且是所有测试图像的常数。卷积运算可分为三个步骤：（1）离散傅里叶变换（DFT）；（2）乘法；（3）逆DFT（iDFT）。DFT和iDFT 的计算复杂度是O(NlbN)，其中N表示图像大小。因此，边界检测的计算复杂度是O(NlbN)。然后，单独执行双边滤波部分和边界强度的递归实现，计算复杂度均为O(N)，因此，除了边界检测之外，三边滤波的递归实现的计算复杂度是O(N)，其独立于支持窗口大小。

4 实验结果与分析

4.1 匹配精度分析

实验使用 3.4 GHz、Inter Core i7 CPU 和 8 GB 内存的高性能计算机，搭建VS2015+OPencv3.0.0 开发平台，使用C++编程实现。

实验样本来自于Middlebury测试集的Tsukuba（384×288，最大深度为16）、Teddy（450×375，最大深度为59）、Venus（433×383，最大深度为19）以及Cones（450×375，最大深度为59）四组双目视觉图像对。

4.1.1 实验1

共进行三次实验，对RTF算法和其他双目立体匹配算法进行比较。在第一个实验中，为了更好地比较每种方法的代价聚合步骤，选择了匹配代价计算，代价聚合和Winner-Take-Al（lWTA）优化步骤运行，而不受预处理和后处理的影响。原始视差图由WTA优化策略直接传递，因此没有进行如中值滤波等任何后处理操作。匹配代价计算步骤的参数设置为相同的值，即{θ,τ1,τ2}={0.1，6，1}。对于代价聚合参数，为每种方法测试了20多个参数设置并选择了最佳参数，从而保证图像集上的平均误差最小，其中RTF：{λe,λc,λd}={0.08,0.7,0.04},RBF：{λc,λd}={0.4,0.06},TF：{λe,λc,λd,r}={0.06,0.08,0.02,0.06,17}，BF：{λc,λd,r}={30,7,17}。误差阈值设定为1，为了更好地观察由每种方法计算的原始视差图，在图4 中，将误差像素标记为红色，用蓝色框标记了颜色相似但视差不同的像素所在区域，从实验结果可以看出，三边滤波比双边滤波在颜色相似但视差不同的区域误匹配点更少，匹配结果更精确，证明了边界强度项的有效性。

4.1.2 实验2

实验2 中，为了测试所提算法的稳健性，为图像集添加了密度为3%的椒盐噪声，如图5（b）所示，通过比较RTF与RBF非遮挡区域的平均误匹配率，来验证增加的边界强度的有效性，实验结果的视觉比较和定量比较图5和表1所示。

图4 颜色相似视差不同区域边缘分布图

图5 添加噪声匹配图

表1 添加噪声的误匹配率 %

定量比较表明，RTF比RBF在处理噪声方面表现良好，其平均错误率为4.48%，低于RBF12.90%的误匹配率，因为这是基于局部能量边缘检测，孤立的嘈杂的椒盐像素对边界项没有影响，因此本文算法对噪声具有较好的稳健性。

4.1.3 实验3

通过实验1 和实验2，验证了三边滤波比双边滤波的精度高，在颜色相似但视差不同的区域效果尤其明显，在实验3中，将三边递归滤波自适应权重（RTF）算法的匹配结果与双边滤波自适应权重算法（BF）、三边滤波自适应权重算法（TF）、双边递归滤波自适应权重算法（RBF）以及递归边缘感知滤波算法（REAF）算法进行比较，图6 列举了五种双目立体匹配算法在Middlebury样本上的匹配结果。

通过视差图可见，本文提出的边界强度项是有效的，在颜色相似但视差不同的像素点的匹配效果优于其他算法，此外，由于在RTF算法中，引导图像表示为无向图G=(V,E)，顶点V是所有图像像素，而边缘E是相邻像素之间的所有边缘。所有像素通过四连接网格连接，每个像素的加权代价首先水平聚合（从左到右，然后从右到左），然后垂直聚合（从上到下，然后从下到上）。这导致每个像素的代价通过四连接的网格路径传播到其他像素，很好地保证图像边缘处的平滑连续性。

根据Middlebury Web 的方法计算并比较上述双目立体匹配算法得到的视差图的误码率，比较结果如图7～图11 所示，从图中可以看出本文所提的边界强度项是有效的，通过比较可以观察到RTF（TF）在平均误差方面以及在大多数立体图像对中比RBF（BF）匹配结果更优，RTF 产生较少的误差像素，在平均错误率方面优于其他方法，并且在大多数列中显示出更好的准确度，尤其是在表示深度不连续附近的区域（图6 中的白色区域）名为disc的列中，表现更加突出。

图6 不同算法视差图比较

图7 Tsukuba数据集的误码率

图8 Venus数据集的误码率

图9 Teddy数据集的误码率

图10 Cones数据集的误码率

图11 平均误码率

4.2 效率评估

通过比较Middlebury基准提供的四个标准，计算评估以上每种方法的代价聚合步骤运行时间，可得统计图，如图12、图13。

图12 递归算法运行时间

图13 非递归算法运行时间

由图12、图13 可知，递归代价聚合方法RTF、RBF和REAF 算法运行速度远远快于非递归的双边滤波BF和三边滤波TF 算法，在第3 章中分析了RTF 的计算复杂度为O(N)，RBF 和REAF 算法的复杂度也为O(N)，算法复杂度与支持窗口大小无关。因此，采用递归滤波方法进行代价聚合非常有效。另一方面，RTF比RBF耗时多，是因为与RBF 相比，RTF 需要边界检测操作。边界检测的平均执行时间约为90 ms，且RTF 包括增加了边界强度项的运算，因此，基于RTF 的代价聚合比基于RBF的代价聚合速度慢，但是在匹配精度上有了很大的提高。具体而言，RTF、RBF 中的代价聚合需要四次扫描，即两次水平扫描和两次垂直扫描，而非递归的代价聚合需要两次完全扫描，即从叶到根然后从根到叶，这样大大增加了运行时间，降低了匹配速度，递归实现显著提高了计算效率。TF、BF 的计算复杂度取决于支持窗口大小，这两种方法非常慢，从图12 和图13 中，可以观察到 RTF、RBF 比 TF、BF 快将近 100 倍，这证明了递归实现的高效性。

5 结束语

通过阅读文献资料，研究发现双边滤波自适应权重算法不能有效地解决由视差不同但颜色相似的像素引起的模糊匹配问题。因此，本文提出了一种三边滤波代价聚合方法，通过引入边界强度项来扩展双边滤波，在该三边滤波代价聚合方法的基础上，进一步提出了三边递归滤波自适应权重代价聚合方法，从理论角度和实际运行时间角度分析了其计算复杂度，实验结果显示该方法相较其他立体匹配方法匹配结果更精确，运算速度更快，证明了边界强度项的有效性和递归实现的高效性。