基于颜色与边缘融合的非局部立体匹配算法

邓 宇，谌贵辉，李忠兵，张军豪，亢宇欣，夏旭洪

西南石油大学 电气信息学院，成都 610500

1 引言

立体匹配技术作为双目视觉系统中最关键的一个环节，主要解决如何将同一空间中的场景点在不同视角的投影图像中的像素点一一对应起来的问题，其广泛应用于机器人导航[1]、目标识别定位[2]、三维重建[3]、虚拟现实等领域。Scharstein 等[4]将稠密立体匹配算法分为四个步骤：（1）匹配代价计算；（2）代价聚合；（3）视差计算；（4）视差优化。根据执行步骤的不同分为了全局算法和局部算法，它们都部分或全部地包含以上步骤。全局算法[5-7]首先建立一个能量代价函数，然后通过最小化能量函数去求解视差。全局算法虽能获得十分精确的视差，但计算量大。局部算法[8-9]则是在给定视差下通过一定的相似性度量准则计算匹配代价，并在一个有限的支持窗口内进行聚合，采用胜者为王（Winner Takes All，WTA）策略求取初始视差，最后执行视差优化步骤。局部方法的核心在于代价聚合，大多数代价聚合方法都视为在代价体上的滤波。Yoon 等[10]将双边滤波引入到代价聚合中，创新性地提出了自适应权重法。Rhemann等[11]利用引导滤波[12]进行代价聚合。由于引导滤波的计算复杂度与滤波核大小无关，因此在实时系统中应用广泛。上述代价聚合方法都是在有限的支持窗口中进行聚合，这会导致图像中的像素不能正确地贡献给其他所有像素而陷入局部最优解。

Yang[13]首次提出了基于最小生成树（Minimum Spanning Tree，MST）的非局部代价聚合算法，将聚合窗口扩展到整个图像，通过计算图像的MST，可以快速完成代价聚合。学者们在此基础上又提出了许多改进算法[14-18]，使得匹配效果进一步改善。虽然文献[13]中的算法在匹配精度和运算效率上都取得了很好的效果，但还具有两方面的缺陷：其一，采用的基于颜色-梯度的代价计算方法导致无纹理区域中像素的匹配代价近似为0，不能为代价聚合提供有效的贡献。其二，只采用颜色信息构造边权函数，导致在颜色分布相似的图像边缘产生误匹配。针对无纹理区域问题，重新构造了基于颜色-梯度的匹配代价函数，提高了无纹理区域像素对代价聚合的贡献率；针对边缘问题，引入了颜色与边缘融合的自适应边权函数，提高了算法在边缘的匹配精度。算法的总体流程如图1所示。

图1 算法总体流程图

2 匹配代价计算

匹配代价计算是通过某种相似性度量准则计算左右两幅图像对应点之间的相似性。文献[13]采用颜色强度和梯度的截断绝对差作为匹配代价，即对应于图像中每一个像素点p在视差d下，有：

式中，I(p)和I′(p+d)分别表示参考图像上中心像素和视差为d时该像素在目标图像上对应像素的强度；α用以平衡颜色项和梯度项；τcol、τgrd为截断阈值；∇x表示图像像素在x方向上的梯度。

由于无纹理区域像素的像素值分布均匀，采用上述匹配代价函数计算时，在该区域中像素的匹配代价值近似为0，在使用3.2节中非局部算法进行聚合时，在树结构上传递的代价值也即为0，对其他像素基本无影响，这与纹理区域中像素相比，它们对代价聚合的贡献率较低，且通过WTA策略为这些像素选择视差时，会出现一对多的情况。故针对在无纹理区域出现误匹配的问题，重新构造了基于颜色-梯度的代价计算函数，如下式：

通过上述变换将零匹配代价项转换为正的匹配代价项（ln2），即通过适度提升无纹理区域像素的匹配代价来提高该区域像素对代价聚合的贡献，从而增加像素的可区分性。在数学上可以证明提出的代价计算函数是单调递增的，用x代替原算法中代价函数Cd(p) 的值，对应的代价函数可表示为f(x)=x，那么可表示为h(x)=ln(1+ex)，两代价函数的对比图如图2 所示。当原匹配代价为0 时，式（1）、（2）的最大绝对差为ln2；而当原匹配代价增加时，二者绝对差则大大减小，且无限逼近于0。因此提出的方法对纹理区域的影响很小，但能有效地处理无纹理区域。

图2 匹配代价对比图

如图3所示，分别为采用两种代价计算方法得到的未经视差优化的视差图。图中红色区域表示在未遮挡区域中的误匹配点。（b）、（e）是在原方法下的视差结果，（c）、（f）是在改进方法下的视差结果。从图中黄色方框表示的无纹理区域中可以看出，改进后算法的红色区域减小，说明改进后代价计算方法能明显改善在无纹理区域中的匹配结果。

图3 不同代价计算方法下的初始视差图

3 代价聚合

由于单个像素的匹配易受到噪声影响，需利用邻域像素的信息进行代价聚合，以提高匹配的可靠性。对于传统局部算法，中心像素仅能从邻域有限的支持窗口内获得支持，而忽略了窗口外像素的影响。而非局部聚合算法利用树结构的特性，天然地建立全图像素间的关系，聚合范围不再受约束，并且聚合过程不需要迭代，只需要两次遍历树结构就能得到所有点的代价聚合值，大幅度降低了算法复杂度。

基于MST的非局部算法[13]中，将参考图像I视为四连通无向图，其中顶点集合V代表图I中的所有像素，边集合E是图像I中所有四邻域像素之间的边，并通过一个加权函数将其映射到实数权值。若存在T为G的子图且无闭环，并且T中的边权值之和最小，则T为G的最小生成树。文中采用Kruskal算法从G中贪心地选择权值最小的边来生成MST。

3.1 基于颜色与边缘融合的边权函数

在原算法中边权函数定义为相邻像素颜色强度的绝对差，即设s和r是一对相邻像素，则权重定义如下：

由于该边权函数只依赖于图像的颜色信息，容易导致在图像中具有颜色相似的边缘区域造成误匹配，因此提出了颜色与边缘相融合的边权函数。

（1）颜色加权函数

上述颜色权重只采用RGB三个通道中最大权重作为边权值，而忽略了其他两个通道的影响，因此提出了加权三通道联合边权作为最终的颜色权重，定义为：

通过融合三个通道的权重，增强了颜色加权函数的鲁棒性，为后续构造MST奠定了良好的基础。

（2）边缘加权函数

边缘权重是通过边缘提取后的二值图像中计算得到的。边缘检测采用具有较强抗噪性能的自适应阈值[19]的Canny算子。为了保证图像边缘信息的完整性，匹配图像采用恒定时间的中值滤波[20]去除图像噪声。该滤波方法不仅能抑制噪声，同时还能有效保护图像的边缘细节，且计算复杂度与滤波核大小无关。如图4为分别采用5×5 的恒定时间中值滤波与均值滤波的效果对比图，从图中可以看出中值滤波在边缘保持效果上更好，并采用结构相似性（Structural Similarity，SSIM）进行了客观评价，SSIM（中值滤波）=0.85，SSIM（均值滤波）=0.82，其结果也表明中值滤波效果更好。

因为图像在边缘提取后被二值化，所以在边缘图像中相邻像素s、r的灰度值只包含两种情况，即I(s),I(r)∈{0,1}。当相邻像素s、r为边缘点或非边缘点时，有或。因此相邻像素s、r的边缘权重定义为：

图4 滤波效果对比

（3）融合边权函数

利用上述颜色权重和边缘权重进行融合以解决在颜色相似的边缘区域易产生误匹配的问题。根据经验公式，融合后的边权函数如下式：

式中，λ是调节颜色项和边缘项比例的调节因子。

使用该融合后的边权函数在边缘区域时，采用边缘和颜色信息共同计算边权，而在其他区域时，则采用颜色信息计算边权。对于不同区域的判定则与边缘提取的准确性息息相关。本文采用自适应阈值的Canny 算子进行边缘检测，由于噪声等因素的干扰，会出现伪边缘现象，造成有时判断错误。如图5所示为边缘检测结果，在黄色方框表示的具有相似深度信息的高纹理区域出现了伪边缘。在构造树结构时，希望尽可能地保留具有相似深度的点之间的边，最大可能地剔除跨深度的边。因此，此处出现的伪边缘会增大高纹理区域像素点间的边权值，而降低该区域的代价聚合。

图5 Canny边缘检测结果

对于伪边缘现象，通常由于光照等外界因素导致噪声点引入，或者图像场景较为复杂，纹理信息比较丰富，都会不可避免地引入伪边缘。但是图像中的边缘与场景的深度边缘之间是一种包含与被包含的关系，因此与原算法只采用单一颜色信息构造边权重相较而言，边缘信息的引入能够在一定程度上改善具有颜色相似的深度边缘区域的匹配效果。最后使用融合后的边权函数去构造MST，这里简称新构造的MST为MST-CE。

3.2 基于MST-CE的代价聚合

采用非局部代价聚合算法[13]在MST-CE上进行代价聚合。设两像素p、q之间的距离D(p,q)是MST-CE上沿最短路径的边权值之和。设Cd(p)表示像素p在视差d下的匹配代价，则非局部聚合代价表示为匹配代价的加权和：

其中，S(p,q)表示两像素间的相似性，参数σ是用于调整两像素之间相似性的常数。

对图像中所有像素进行代价聚合只需要通过两次遍历树结构就能有效地计算出来，聚合过程如图6 所示。第一次遍历（图6（a）），从树的叶节点到根节点。对于像素p，其代价值在访问完所有子节点才会被更新，即：

图6 在MST-CE上的代价聚合

在MST-CE树结构上进行代价聚合，得到聚合代价值后通过WTA策略求取视差。图7为所提算法与基于MST算法的视差图及局部放大对比。以真实视差图为参照，所提算法相较于基于MST 的算法能够更加有效地保护图像边缘，在深度不连续区域的匹配效果有较明显的改善。

4 视差优化

视差优化采用文献[13]中提出的非局部视差优化算法。首先以左右图像为参考图像，依次运行非局部代价聚合算法得到相应的左右视差图；然后采用左右一致性检测，将所有像素划分为稳定像素和不稳定像素；最后利用划分的像素重新构造匹配代价体，构造如下：

式中，D(p)表示初始左视差图。因此对于不稳定像素在视差d上的代价被重置为0。再利用3.2节的非局部代价聚合算法将新的代价值在树结构上进行聚合，将视差值从稳定像素传播到不稳定像素。

5 实验结果与分析

为验证算法的有效性，在Middlebury[21]的19个数据集上对算法进行了评估，包括4个标准数据集和15个扩展的数据集，其中误差阈值均设为1.0。实验硬件平台为配置2.8 GHz 主频的CPU、8 GB 内存的台式电脑；软件平台为Visual Studio2015，编程语言为C++。

图7 算法视差图比较

本文算法的具体参数通过大量实验确定，具体如表1所示。其中标准数据集中参数λ设为0.6，参数σ设为0.1；扩展数据集中参数λ设为0.2，参数σ设为0.04；对比算法保持与原文献一致的参数。

表1 算法具体参数

5.1 代价计算性能测试

为验证改进的代价计算方法的性能，在MST非局部算法框架下，将改进的代价计算方法（Proposed）与原代价计算方法（Original）、基于截断灰度差绝对值（Truncated Absolute Differences，TAD）、基于梯度（Grad）、基于Census的代价计算方法进行对比。在Middlebury的19个数据集上进行了测试，算法性能如表2 所示。从表中可知，改进的代价计算方法与其他四种典型的代价计算方法相较而言，误匹配率最低，且在运行时间上相差无几。

5.2 算法对比分析

为了验证算法的总体性能，将改进后的算法与原算法[13]（MST）、基于引导滤波的算法（GF）[11]和基于分割树的算法[14]（ST-1）进行对比。算法的初始视差都是采用代价计算、代价聚合和WTA策略计算得到，不采用视差优化技术。对于标准数据集，在三种不同区域进行测试，即非遮挡区域（nonocc）、全部区域（all）、不连续区域（disc），其结果如表3 所示。对于深度不连续区域多分布在边缘区域，因此“disc”一栏中的数据能够表明算法在边缘区域的匹配效果。从表3 可知，在“disc”一栏中改进算法的误匹配率均小于MST，与ST-1和GF相比也具有很大的优势。因此，在“disc”中的良好性能说明了本文提出的融合边权函数的必要性。

表2 代价计算方法性能测试结果

表3 不同算法在标准数据集上不同区域的匹配误差（未经视差后处理） %

为进一步验证算法性能，在15 个扩展数据集上进行了测试，其结果如表4所示。在这19个数据集上改进算法在10 个数据集上取得了最低误差，且平均误匹配率最小。为了在视觉上进行更加直观的比较，图8给出了其中3幅图像未经视差优化的视差图（从上到下依次为原图、真实视差图、GF视差图、ST-1视差图、MST视差图、本文视差图），用红色表示在未遮挡区域中的误匹配像素。从图中可以看出，改进后算法的红色区域明显减小，在图中黄色方框表示的边缘区域上改进后算法的匹配效果相比其他三种算法也更加理想。但是由于算法在代价计算中采用的颜色与梯度两种测度对噪声都比较敏感，且在边缘检测中出现了伪边缘，致使边权重的构建不是十分准确，从而导致了算法在某些纹理较为丰富的图像上的改善效果并不是十分明显。

表4 不同算法在非遮挡区域中的匹配误差 %

图8 未经视差优化的视差图

最后采用文献[13]中的视差优化算法对初始视差进行优化。如图9 为MST 算法和MST-CE 算法在标准数据集上视差优化后的视差结果，在这4 个数据集上，平均误匹配率从5.48%下降到了5.34%。

图9 标准数据集视差优化后结果

6 结束语

本文对基于MST 非局部算法进行了两方面的改进。针对原算法在无纹理区域像素的匹配代价对代价聚合贡献率低的问题，重新构造了基于颜色-梯度的匹配代价函数，有效改善了在无纹理区域的匹配效果。针对边权函数的构造只采用单一的颜色信息，导致了在颜色相似的图像边缘出现错误匹配，提出了颜色与边缘融合的自适应边权函数。在Middlebury 19个数据集上的评估表明，算法有效地提高了在无纹理以及边缘区域的匹配精度。但是由于算法在代价计算中选择的测度对噪声较为敏感，以及边缘检测中出现了伪边缘，导致算法对一些纹理较丰富的图像的改善效果并不是十分明显。今后将针对代价计算进行进一步的研究，测试更多测度并进行融合；针对边缘检测将进行进一步约束，提高检测的准确性，从而提高算法的匹配精度。