基于改进Census变换与最小生成树的立体匹配算法∗

于修成 宋 燕 李 航

（上海理工大学光电信息与计算机工程学院 上海 200093）

1 引言

立体匹配是计算机视觉的基础和研究热点之一，是通过寻找双目或多目图像中的对应点进而估计场景深度信息的过程，在机器人导航、虚拟现实 、以 及 三 维 重 构 等 领 域 得 到 广 泛 应 用［1～2］。Scharstein［3］对当前现有立体匹配算法进行了分类研究，对诸多算法在性能上进行了详细的分析对比，建立了较全面的测试体系。此外，Scharstein提供了相应的测试数据集以及比较方法，同时将立体匹配的过程大致分为四个阶段：代价计算、代价聚合、视差计算/优化、视差强化等。

在代价计算中，常见代价计算方法是将像素差异的绝对值作为匹配代价。Pollard［4］等证明通过将图像梯度信息引入到匹配代价计算中，可以增强匹配代价对幅度等失真的抗干扰能力；Zabin［5］等提出将非参数变换引入到代价计算中，可以显著减少光照和噪声等干扰的影响。Hirschmuller［6］等提出Census变换在光照失真的条件下具有很好的稳健性。但传统Census变换依赖于中心像素灰度值大小，对噪声比较敏感。通过代价计算得到的匹配代价存在较大的噪声，将其作为视差选择的标准会造成较大的误匹配，因此需要将当前代价和其邻域代价进行聚合。常见的代价聚合方法有盒子滤波、高斯滤波，此类滤波器实现简单，但往往会模糊图像深度边界。Yoon［7］等使用双边滤波进行代价聚合，在保留深度边界的同时增加了算法的复杂度。Rhemann［8］等将导向滤波引入代价聚合，使得聚合的效果和时间效率得以进一步提升。然而，以上聚合算法都是基于支持窗口内的聚合，忽略了窗口外的像素信息，因此通过此类算法得到的视差图还有待进一步完善。Yang［9］等将图像看作是一张无向图，并对无向图进行去除最大边界处理得到最小生成树，然后在最小生成树上进行代价聚合。这样的聚合方式将支持窗口扩展到整幅图像，进一步提高了匹配的精度。在视差选择和优化中，根据优化算法的不同可以将立体匹配算法分为局部立体匹配和全局立体匹配。局部匹配是选择最小匹配代价对应的视差作为最终的视差，而全局算法则是建立一个全局能量函数，对函数进行求最优化即可得到最终的视差图。在全局算法中，较为经典的算法包括动态规划［10］、图割法［11］、置信传播［12］等。需要说明的是，通过以上方法得到的视差图仍存在误匹配，从而需对视差图进一步强化如左右一致性检验、空洞填充、中值滤波等［13］。

通过以上分析，针对基于传统Census变化计算匹配代价存在的问题，本文提出一种基于增强Census变换的多尺度立体匹配算法。在代价计算阶段，首先将支持窗口内像素的加权平均值作为Census变换的参考值，该权重包含支持窗口内空间信息和像素差异信息，并为参考值增加一定的噪声容限α，然后通过比较得到四个状态的二进制表示。进而，在代价聚合阶段，基于多尺度图像采用最小生成树算法进行代价聚合，从而综合了图像中所有像素信息。该方法使得立体匹配率进一步提高，并在噪声情况下具有一定的稳健性。

2 算法描述

立体匹配算法由代价计算、代价聚合、视差选择和视差强化等步骤组成，本文所提的算法也包含以上步骤。

2.1 匹配代价计算

传统Census变换是将中心像素灰度值与支持窗口内所有像素进行比较生成匹配模板，然后进行非参数变换获得比特串，最后用汉明距离计算匹配代价，该算法对中心像素的依赖性强，抗干扰能力差。Chang［14］等提出用支持窗口内所有像素的均值作为参考值的算法（MCT），该算法将邻域像素信息融入参考值的计算，进一步提高了单像素匹配代价的可靠性，但不能很好地利用中心像素与邻域像素之间的关系。文献［15］提出用支持窗口内所有像素的加权平均灰度值作为参考值的算法（SWCT），其中权重由支持窗口内像素的空间信息决定，该算法进一步提高了Census算法的稳健性，但忽略了窗口内邻域像素与中间像素的差异信息。

针对上述Census变换存在的问题，提出一种改进的Census变换来计算匹配代价，每一个Census变化的参考值由支持窗口内像素的加权平均后得到。具体地，用支持窗口去扫描图像中的每一个像素，将窗口内像素的加权平均值作为Census变换参考值，其中权重由空间信息和支持窗口内像素差异共同决定。改进算法参考值计算公式与权重计算公式分别为

其中 p、q分别为支持窗口内中心像素和邻域像素索引，Iwm为用于Census变换的参考值，Wpq为像素 p、q之间的权重，D=∑Wpq为归一化常数，也为所有权重之和，N为支持窗口内所有像素，‖‖p-q为像素p、q之间的欧氏距离，rp为空间标准差，Ip、Iq为像素索引 p、q的像素值，rc为像素标准差。考虑到噪声的影响，为Census变换参考值增加一定的噪声容限α，则利用Census变换计算该支持窗口的比特串公式为

其中

其中C（p，d）为像素点 p在视差为d时的匹配代价，d∈[0，dmax]。 Ham[x，y]为计算比特串 x和 y的汉明距离，Tcen为截断阈值，λ为控制离群值参数。

由上述分析可见，传统Census算法采用支持窗口中心像素作为参考值，然而改进Census算法采用支持窗口内像素的加权平均值作为参考值，并对其增加噪声容限α。然后用四个状态对其进行表示，改进Census算法的抗干扰能力比传统Census强。此外，与SWCT算法采用基于窗口空间信息的加权平均值不同，改进算法采用基于窗口内空间信息和像素差异信息共同决定的加权平均值作为参考值，得到匹配率更高的视差图。以上几种方法得到的视差对比图如图1所示：由于Venus图像包含丰富的颜色信息，SWCT变换仅仅使用空间信息来求解权重，因此得到的视差图存在较多的误匹配点，得到的视差图比较粗糙，如图1（c）所示。图（d）为改进Census变换得到的视差图，与（c）相比，视差图平滑了许多，在视差不连续区域视差图有明显的改善（红色方框内）。因此，改进Census匹配代价计算方法有较强的稳健性，其匹配效果更加精准。

图1 SWCT与改进Census变换得到的视差图

2.2 匹配代价聚合

2.1节定义了基于像素的原始匹配代价，但由于基于像素的匹配代价易受噪声的影响，因此需要利用周围像素的匹配代价进行代价聚合，提高视差的区分性。传统代价聚合大都采用支持窗口进行聚合，最简单的是盒子滤波。基于支持窗口的代价聚合本质上只考虑了窗口内像素对中心像素的影响，窗口之外的像素影响彻底忽略。易见，此类算法匹配效果差，误匹配率高。

基于最小生成树的代价聚合将聚合窗口扩展到整幅图像，使得匹配的精度进一步提高。和以往的成本聚合方法不同，最小生成树算法首先将图像I表示为连接的无向图G（V，E），其中V是所有图

其中 I（s）、I（r）为边所连接的两个节点 s和 r 的像素值。然后，通过kruskal算法或prim算法进行优化，寻找两节点之间的最小连接，进而生成最小生成树。最小生成树中节点 p和q的距离是两个节点之间的连接边的权重之和，记为D（p，q），则 p、q之间相似度为像像素节点，E为连接节点的边，其权重为

其中σ为调节相似度常数。因此，对于像素点 p，其聚合后的匹配代价为

在不同尺度下分别对匹配代价图进行代价聚合，具体过程类似于文献［16］，最终的聚合代价为

其中 A 为 （S+1）×（S+1）的系数矩阵；S 为下采样层数；为第0层的匹配代价。

2.3 视差计算与强化

运用Winner-Takes-All（WTA）算法，选取对应匹配代价最小的视差作为最终的视差，从而得到视差图。获取视差的公式为

其中dfinal表示最小代价对应的最优视差；p为当前像素。

在视差强化阶段，首先通过左右一致性来检测匹配异常点，判断公式为

其中dL、dR为左右初始视差图，Th为视差阈值。不满足以上公式的点视为异常点，否则为稳定点。异常点需要进行修正。具体地，对于异常点 pout，在水平方向上分别往左和往右各找到第一个稳定点 pinL和 pinR。将异常点 pout的视差值修正为 pinL和pinR中的较小值，计算公式如下：

3 实验与结果分析

使用Middlebury2.0立体匹配评估测试平台对所提算法进行评估，测试图片包括2001，2003，2005，2006四个数据集中的 31组立体图像对［17］。实验环境为Visual studio 2013下C/C++编程环境，Windows 10，X64位系统，Intel Core i7处理器，内存为8GB。

为了验证所提算法的实际性能，除特殊说明之外，文中所涉及到的视差图都是未经过任何视差精化和后处理的初始视差图；对比实验中误差设置为一个像素差，也就是算法所得到的视差图与真实的视差图之间的差距大于1个像素则将该点标记为误匹配点。

3.1 匹配代价计算实验

为验证改进Census算法的有效性，选择基于梯度变换（GRD）、传统Census变换（CT）、基于平均值的Census变换（MCT）、基于加权平均的Census变换（SWCT）四种不同匹配代价方法和所提算法在Middlebury2.0中4组标准立体图像进行实验对比。通过非遮挡区域和所有区域的误匹配率来测试算法的性能，如表1、2所示。

表中结果表明，所提匹配代价计算方法未经过视差强化时在非遮挡区域的平均误匹配率为3.65%，所有区域的平均误匹配率为10.11%，与其他代价算法相比，本文提出的算法具有较低的误匹配率。

GRD、CT、SWCT与本文算法的视差图如图2所示，可以看出，本文算法的视差图中红色标记点（误匹配点）明显少于其他算法，在网格孔、边界交界处尤为明显；图2（b）和2（c）中弱纹理区域的误匹配点明显少于图2（a），说明基于Census变换的算法要比GRD在弱纹理处有较好的匹配效果；在边缘视差不连续区域，图2（a）的红色误匹配标记点明显比2（b）和2（c）少，表明基于像素差异信息的GRD算法要比CT和SWCT算法在视差不连续区域有较好的匹配效果；图2（d）为所提算法的视差图，由于其采用基于空间和像素差异信息的改进Census变换，可以看出在弱纹理区域和视差不连续区域的误匹配率明显减少，表明所提算法的误匹配率低、精度高。

图2 不同匹配代价算法获得的视差图

3.2 抗干扰测试

为了测试所提算法的稳健性，选取4种传统算法（GRD、CT、MCT和 SWCT）与本文算法进行比较。给4组标准立体图像加入噪声密度为3%的椒盐噪声，通过非遮挡区域的平均误匹配率来测试匹配算法的性能，实验结果与数据如图3和表3所示。

噪声实验结果表明，在增加一定的噪声后，本文算法均优于其他几种匹配算法，因此本文算法对噪声具有较好的稳健性。

表3 非遮挡区域在有噪声情况下的误匹配率

图3 加入椒盐噪声后，CT与所提算法对比图

3.3 27组数据集测试结果

为了进一步测试本文算法的总体性能，对Middlebury2.0平台另外27组立体图像对（M27）进行测试，通过非遮挡区域误匹配率百分比来对比相关算法与所提算法的性能。实验结果如表4所示，视差图未经细化处理，误差限制为1pixel。

表4表明，本文算法在27组立体图像对的平均误匹配率最低，仅为10.8%。在立体图像对Lampshade2中最高误匹配率为32.45%，本文算法仅为12.17%，误匹配率降低了20.28%；在Midd2中，最高误匹配率为50.66%，而本文算法仅为17.35%。实验结果表明，本文算法进一步降低了误匹配率，提高了匹配精度。

表4 非遮挡区域不同匹配代价计算方法误匹配率（M27）

4 结语

提出了一种改进的局部立体匹配算法，用支持窗口的加权平均灰度值作为Census变换的参考值，其中权重由支持窗口内的空间和像素差异信息共同决定。该算法融合像素差异信息，更好地利用了图像的纹理信息，使得匹配精度进一步提高。此外，该算法为Census参考值增加一定的噪声容限，通过四种状态得到比特串，从而使得匹配算法具有一定的抗干扰能力，增强了算法的稳健性。进而，利用最小生成树算法分别在不同分辨率尺度下进行代价聚合，充分利用了图像的细节信息，降低了图像在视差不连续区域和弱纹理区域的误匹配率。最后，运用实验对本文算法与相关算法进行比较，结果表明本文算法的匹配精度要明显优于其他算法，尤其是在视差不连续区域和弱纹理区域。在抗干扰测试中，所提算法也表现出较强的稳健性。需要说明的是，从误差标记的视差图中可以看出，本文算法在细节区域中的匹配精度还有待提高，这将是我们下一步的研究工作。