基于改进Census变换和多尺度空间的立体匹配算法*

刘建国 俞力 柳思健 王帅帅

(武汉理工大学 现代汽车零部件技术湖北省重点实验室∥汽车零部件技术湖北省协同创新中心， 湖北 武汉 430070)

立体匹配是计算机视觉研究最为活跃的领域之一，作为双目立体视觉的核心组成部分，其主要任务是找到真实环境中物体上的某一点在左右视图上的对应点.而真实世界中因为外界环境(如光照不均匀、遮挡、弱纹理、倾斜区域等)问题使得物体成像发生相应的变化，从而给双目匹配带来挑战.Scharstein等[1]对立体匹配算法进行了总结分类，把匹配的过程分为4个步骤：匹配代价计算、匹配代价聚合、初始视差计算和视差优化，并根据计算视差值方式的不同把立体匹配算法分为全局匹配算法[2- 3]和局部匹配算法[4- 7].全局匹配算法通过构建全局约束，大多能够获取高质量的视差图，主要有动态规划、置信传播[2]、图割法[3]，但是算法的时间复杂度高、计算效率低，是其明显的弊端.局部匹配算法在寻找匹配点时仅考虑匹配点邻域内像素对匹配对的影响，通常运行速度快、执行效率高，但是它对一些由于遮挡和弱纹理等造成的模糊比较敏感，易造成误匹配，如何选择合适的支持窗口和像素匹配代价的计算方法是个难点.

传统的局部立体匹配代价计算方法主要有基于绝对差(AD)、平方差(SD)[1]、自适应权重(AW)[4]以及自适应匹配窗口的算法等几种.近年来，相关研究学者提出许多新的匹配代价算法.Yoon等[4]提出一种变权重系数的成本聚类的方法，该权重系数根据像素间的颜色相似度和距离来计算得到，颜色越相近，空间距离越近，权重系数越大.Zhang等[5]提出基于交叉区域匹配窗口的匹配算法，利用颜色相似性和距离限制得到由多条相邻的水平分割线或者竖直分割线组成的匹配窗口，该窗口是自适应的，所以能很好地解决匹配中弱纹理的问题.Shen[6]提出基于梯度测量和非参数变换的方法：Rank和Census变换，该方法提高了匹配精度和鲁棒性，但传统Census变换依赖于中心像素灰度值的大小，对噪声比较敏感，支持区域的选择合理性也会影响匹配精度.Stentoumis等[7]对视差空间进行3D滤波，采用顺序约束和唯一性约束来选择3D滤波区域内的像素点，以局部高斯函数为核函数，给选取的像素点分配适当的权重系数，此方法考虑到了视差空间内的3D信息，匹配正确率有所提高.

在代价聚合阶段，传统聚合算法的共同点是在输入图像为细尺度上进行聚合的，然而人类是在多尺度[8- 9]下产生的立体视觉效果，受到这种生物启发,在传统的算法上采用多尺度聚合比细尺度聚合更为合理.

在视差计算阶段，选择使用局部算法中聚合代价最小的候选点作为最终匹配点，因为局部匹配算法更多地依靠匹配代价计算和代价聚合来保证视差图的质量，通常用“赢家通吃”(WTA)[10- 11]的算法，该方法虽然简单、快速有效，但容易受噪声等因素的影响而产生视差突变，使获得的视差图存在较多的误匹配点和异常值.

文中提出一种改进的局部立体匹配算法对Census变换进行改进，采用一种增加变换窗口信息均值判断和自适应权重的计算方法，提高算法鲁棒性；在代价聚合阶段，将引导图[12]聚合算法融入高斯金字塔构中，并结合正则变换方法来加强层间一致性匹配代价运算，提高视差图精度；最后，在视差处理中，采用多层次的视差优化步骤，包括误匹配点检测、区域投票策略和亚像素增强[9,13].

1 算法描述

根据Scharstein等[1]对立体匹配算法的分类和评价，立体匹配算法通常包括以下步骤：代价计算、代价聚合、视差计算和视差优化.文中算法也遵循该流程.

1.1 匹配代价计算

传统的Census变换[14]是以像素p为中心选取一个矩形变换窗口W(p)，选取该中心像素的灰度值作为参考值，将矩形变换窗口内各点像素q的灰度值分别与中心像素p的灰度值进行比较，并用0和1来表示其大小关系.Census变换的实质就是将像素p与以其为中心的窗口映射成一个比特流，用该比特流作为中心像素点的Census变换码.映射关系为

(1)

式中，I(p)、I(q)分别为像素点p、q的灰度值.由映射关系得到对应的比特流，定义如下：

(2)

式中，符号⊗表示按位连接，Np表示p的领域.

如图1所示，变换窗口大小为3×3，中心像素的灰度值为68，领域各像素的灰度值如图1(a)所示，其Census变换后的比特串为10010100.

图1 Census变换示意图Fig.1 Schematic diagram of census transform

由图1(a)可知，传统的Census变换能够在一定程度上改善图像受到噪声干扰时的立体匹配性能，但仍存在如下局限性：变换结果完全依赖于中心点的灰度值，一旦中心像素点受到外界因素的干扰，Census变换编码结果会发生巨大变化，导致误匹配，降低匹配精度；其次，变换窗口大小的选择也将影响到算法的匹配精度，窗口选取过大会增加深度不连续区域的误匹配率，且会增加算法的运行时间；窗口选取过小，则包含窗口内领域像素的信息较少，使得匹配精度下降，噪点增多.

(3)

式中，Ta为设定的阈值.阈值的选取不宜选大，过大的阈值会影响匹配精度，所以选择较小的阈值即可.根据对图像相邻点的分析及在不同阈值下的Census变化仿真选取的阈值区间为[15,20]，文中采用的阈值为17，则有

(4)

式中,Iz(p)是经阈值判断后变换窗口中心点的灰度值，图2给出了改进Census变换的对比图.

图2 Census变换对比图Fig.2 Comparison charts using different Census transform

通过对比可知,改进的Census变换能有效降低因外界干扰而引起的Census变换码的变化.此外，采用自适应权重的方法区别对待窗口的像素，根据相似性原则，窗口内与待匹配像素颜色信息越接近的像素点分配越大的权重；如图3(a)所示，当窗口中心点处于深度连续区域时，由连续性假设可知，窗口内其他点与中心点处于相似深度，颜色信息相近，即可认为是窗口内的“有效点”.与之对应的是当窗口中心点处于深度不连续区域时，表示窗口内的某些点与中心点处在不同深度，即颜色信息差异大，这些点被认为是“无效点”.所以当某中心点变换窗口包含的“有效点”越多时，即可认为匹配精度越高，反之则越低.图3(b)中的黑色部分表示的是误匹配区域.

图3 视差连续区域与不连续区域误匹配分布示意图

Fig.3 Mismatch distribution in depth continuous and discontinuous area

文中采用的自适应权重的颜色相似性方法引入了颜色强度信息，即采用绝对灰度值的方法(AD)[15]，CAD(p,d)表示左图中点(xp,yp)和右图中点(xp-d,yp)的平均灰度差值，这里Ii(p)表示第i个RGB通道的灰度值，即：

(5)

C(p,d)即为改进的Census变换与AD方法相结合的函数，

(6)

(7)

图4 中心点领域点的权值分配Fig.4 Distribution of weights in the center point domain

1.2 匹配代价聚合

成本聚合是局部匹配算法中重要的一步，其目的是借助一个匹配窗口对视差空间进行过滤，减小匹配的歧义性.实现方法是假设匹配窗口内的点均有相似的视差值，把窗口内的所有像素点按照一定的权重系数累加起来.Hosni等[16- 17]详细介绍并评估了现有的代价聚合算法，指出大部分聚合算法的思想是试图区分中心像素点与其领域内相似的点和非相似的点，赋予相似的点更多的权重、非相似的点更少的权重.常用判断两点是否相似的标准有距离、颜色、测地距离及空间距离等，很多算法的匹配结果能够和全局匹配算法相媲美.

但是，传统的代价聚合算法往往是在细尺度下进行的，它们在处理高纹理区域时表现得非常好，而在弱纹理和近无纹理区域的效果不理想.为了进一步提升算法对更符合人类视觉系统的多尺度空间的自适应性，采用尺度空间理论中的经典表示——高斯金字塔结构[18],通过连续采样和亚抽样得到高斯金字塔结构，再在每个尺度空间上单独计算匹配聚合代价值，并利用正则变换来加强层间一致性匹配代价运算,最后根据多尺度空间计算得到其最优解.

对每个尺度下的图像进行代价聚合算法，在对比了双边滤波器和基于高斯核的聚合算法之后，采取引导图滤波算法，其优势在于：首先，其复杂度与图像大小无关，与滤波窗口大小无关，能提高匹配效率；其次，引导图滤波能够梯度保持，所以即使在强度突变的位置颜色信息量较少，但只要能提供足够的梯度信息，就能实现较好的跟随效果.这样就起到了一个很好的区分视差连续区域和视差不连续区域的作用，提高该区域的匹配精度.

先通过对图像进行高斯下采样，可以得到多副成对图像，多尺度代价聚合模型下每层的代价聚合计算公式为

(8)

假设引导图像I和滤波器输出q之间存在一个局部的线性对应关系.这里定义q是I在中心像素为k的窗口wk的线性变换，即：

qi=akIi+bk， ∀i∈wk

(9)

式中，ak、bk为窗口内的恒定系数.这个局部线性关系保证了输出图像q的边缘与引导图像I的边缘保持一致，因为q=aI.利用引导图滤波进行代价聚合的详细过程见文献[17]，这里直接给出引导图滤波器的核函数，即：

(10)

(11)

其中，β为正则化因子，在不同尺度下，同一像素的代价一致，如果正则化因子越大，即说明同一像素不同尺度间的一致性约束越强，这会加强对弱纹理区域的视差估计，从而提高在弱纹理区域的匹配精度.

当前正是我国扶贫工作的攻坚时期，扶贫模式也由粗放式调整为精准式。在落实政策的过程中，乡村旅游可作为精准扶贫的媒介。

1.3 视差计算和优化

在完成代价聚合步骤后，接下来选择具有最低聚合费用的偏移值作为最终的视差值(即WTA:赢家通吃策略)[20]，获得的初始视差值为

(12)

式中，Sd={dmin,…,dmax}为可能的所有视差值，C(p,d)为视差值为d时的匹配代价值.赢家通吃的方法快速有效，通过预保留聚合费用值可以很容易地获得该检测结果而不增加太多的计算量.

初始视差图在遮挡区域和深度不连续区域会存在一些误匹配点，所以需要进行视差优化，即采用误匹配点检测、区域投票策略和亚像素增强[9,13]的方法来建立更完整的视差图.这里定义在视差计算中得到左右图的视差图，分别用DL和DR表示，视差图中每个点都称为视差点.

误匹配点检测：采用左右一致性检测的方法来检测误匹配视差点[9].通过比较左图和右图匹配对的视差点的视差值，把视差点分为遮挡点和非遮挡点，即

(13)

(14)

(15)

图5 视差后处理的结果Fig.5 Results of disparity post-processing

2 实验结果

2.1 匹配代价评估

在19幅Middlebury匹配图中，改进的Census算法与传统的Census变换算法对比结果如表1所示，主要对比了算法的平均匹配精度和时间效率，除了匹配代价算法不一样外，其余所有步骤保持一致.

表1 传统Census算法与改进Census算法的对比

Table 1 Comparison of traditional Census method and improved Census method

匹配代价算法误码率/%运行时间/sCT1)8.430.41ImCT2)8.020.63

1)CT表示Census变换方法，即原始的统计变换算法；2)ImCT表示文中改进的Census变换方法，即改进后的匹配代价算法

表2 无视差优化的匹配算法对比

Table 2 Performance evaluations on algorithms without disparity refinement

匹配图像误码率/%CT-GFCG-GFCT-STCG-STCT-NLCG-NL改进算法Tsukuba4.3174.2963.2333.1313.3253.2643.212Venus2.0371.2721.5741.4331.8261.6051.171Teddy8.7348.8758.2339.3777.8619.2667.962Cones4.7335.3674.8745.0565.0454.5214.642Aloe7.8967.8057.2138.7177.6946.2016.722Art12.44312.37213.05413.70613.62513.83712.231Baby15.6525.8547.6865.6739.1177.5055.511Baby23.7525.7637.1967.5576.7556.7343.551Books13.42610.87211.70312.31412.42514.9279.421Cloth12.8171.6460.9111.2241.5650.9721.803Cloth25.9456.9975.9345.9136.3064.9115.872Dolls7.1927.3337.8167.6458.3277.5747.141Lampshade115.08711.72410.46212.43513.35611.0039.871Flowerpots9.30110.91313.24513.10416.66618.83710.112Reindeer10.50410.4839.86212.82611.64514.0179.471Rock13.8344.6773.4723.9353.7634.0163.461Rock22.6723.7872.7433.2253.2463.0642.631Wood15.0034.6626.1246.78511.31710.7364.391Wood24.6053.0715.9274.6364.0543.4433.172平均误码率/%6.8436.7226.9047.2957.7877.7065.911

1)下标代表7种算法在每一幅测试图的排名.

表3 视差优化后的匹配算法及计算时间对比

Table 3 Running time of Middlebury stereo pairs by stereo algorithms with disparity refinement

匹配算法非遮挡区域误码率/%全部区域误码率/%计算时间/sCT-GF6.4513.827.02CG-GF6.1312.878.05CT-ST6.4214.254.69CG-ST6.2713.205.68CT-NL7.2015.325.02CG-NL6.8114.065.31改进算法4.5111.877.22

从表1中可以看出ImCT提升了匹配精度且未增加太多时间.

2.2 无视差优化评估

执行所有的算法及采用赢家通吃策略来计算初始视差值，表2比较了改进算法与其它几种算法的结果，视差图的像素阈值误差为1.0%，表中可以看到改进算法在11/19幅匹配对中排名第1、19幅匹配对的平均误码率在表2最后1排，相比其他算法，改进算法的平均误码率最低，即匹配精度更优.

2.3 视差优化评估

算法经过视差优化后的评估结果及运算时间如表3所示.算法因考虑到窗口内均值像素点计算和多尺度空间，所以计算时间会增加，但因采用引导图滤波算法及尺度空间个数，选取了一合适的值，故在提高匹配精度的同时并未增加太大的时间复杂度.图6具体给出了Venus、Baby1、Rock1的视差图，其中在非遮挡区域的误匹配点用红色点标记出来.

图6 7种算法得到的视差优化图Venus、Baby1、Rock1

Fig.6 Disparity refinement maps of Venus，Baby1 and Rock1 obtained by the seven algorithms

3 结语

文中通过分析传统Census匹配算法的缺陷，提出一种基于变换窗口信息均值判断和自适应权重的Census变换方法，提高了在视差不连续区域的匹配精度.在代价聚合阶段引入多尺度空间的概念，采用高斯金字塔结构，将引导图滤波算法融合到该结构中，并添加正则化项来加强层间一致性匹配代价运算，充分提高在弱纹理区域的匹配精度.在视差选择阶段，采用一系列优化方法(如误匹配点检测、区域投票策略和亚像素增强等)来提高最后的视差图精度.实验结果表明，文中算法的匹配精度优于当前部分优秀的局部算法，时间复杂度相对长一些.目前算法主要在CPU上实现，今后的研究将围绕如何使算法并行化而展开，从而达到实时性的效果.

参考文献：

[1] SCHARSTEIN D,SZELISKI R.A taxonomy and evaluation of dense two-frame stereo correspondence algorithms [J].International Journal of Computer Vision,2002,47(1):7- 42.

[2] BESSE F,ROTHER C,FITZGIBBON A,et al.PMBP:PatchMatch belief propagation for correspondence field estimation [J].International Journal of Computer Vision,2014,110(1):2- 13.

[3] LIANG Q,YANG Y,LIU B.Stereo matching algorithm based on ground control points using graph cut [C]∥2014 7th International Congress on Image and Signal Processing(CISP).Dalian:IEEE,2015:503- 508.

[4] YOON K J,KWEON I S.Adaptive support-weight approach for correspondence search [J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2006,28(4):650- 656.

[5] ZHANG K,LU J,LAFRUIT G.Cross-based local stereo matching using orthogonal integral images [J].IEEE Transactions on Circuits & Systems for Video Technology,2009,19(7):1073- 1079.

[6] SHEN Y.Efficient normalized cross correlation calculation method for stereo vision based robot navigation [J].Frontiers of Computer Science,2011,5(2):227- 235.

[7] STENTOUMIS C,GRAMMATIKOPOULOS L,KALISPERAKIS I,et al.On accurate dense stereo-matching using a local adaptive multi-cost approach [J].Isprs Journal of Photogrammetry & Remote Sensing,2014,91(91):29- 49.

[8] SHEN S.Accurate multiple view 3D reconstruction using patch-based stereo for large-scale scenes [J].IEEE Transactions on Image Processing A Publication of the IEEE Signal Processing Society,2013,22(5):1901- 1914.

[9] MEI X,SUN X,ZHOU M,et al.On building an accurate stereo matching system on graphics hardware [C]∥Proceeding of IEEE International Conference on Computer Vision Workshops.Barcelona:IEEE,2011:467- 474.

[10] ZHANG D.The algorithm of WTA stereo matching based on the human detection method [J].Electronic Test,2013(5):66- 68.

[11] XIAO J,XIA L,LIN L,et al.A segment-based stereo matching method with ground control points [C]∥Proceeding of International Conference on Environmental Science and Information Application Technology.Wuhan:IEEE,2010:306- 309.

[12] HE K,SUN J,TANG X.Guided image filtering [J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2013,35(6):1397- 1409.

[13] TIWARI K C,ARORA M K,SINGH D.Subpixel target enhancement in hyperspectral images [J].Proceedings of the International Society for Optical Engineering,2011,63(1):63- 68.

[14] STEIN F.Efficient computation of optical flow using the census transform [J].Lecture Notes in Computer Science,2004,3175:79- 86.

[15] CHAMBON S,CROUZIL A.Similarity measures for image matching despite occlusions in stereo vision [J].Pattern Recognition,2011,44(9):2063- 2075.

[16] HOSNI A,BLEYER M,GELAUTZ M.Secrets of adaptive support weight techniques for local stereo matching [J].Computer Vision & Image Understanding,2013,117(6):620- 632.

[17] MIN D,LU J,DO M N.A revisit to cost aggregation in stereo matching:How far can we reduce its computational redundancy [C]∥Proceeding of IEEE International Conference on Computer Vision.Barcelona:IEEE,2011:1567- 1574.

[18] ZHANG K,FANG Y,MIN D,et al.Cross-scale cost aggregation for stereo matching [C]∥Proceeding of IEEE Conference on Computer Vision and Pattern Recognition.Columbus:IEEE,2014:1590- 1597.

[19] 祝世平,李政.基于改进梯度和自适应窗口的立体匹配算法 [J].光学学报,2015,35(1):115- 123.

ZHU Shi-ping,LI Zheng.A stereo matching algorithm using improved gradient and adaptive window [J].Acta Optica Sinica,2015,35(1):115- 123.

[20] CHANG X,ZHOU Z,WANG L,et al.Real-time accurate stereo matching using modified two-pass aggregation and winner-take-all guided dynamic programming [C]∥Proceeding of International Conference on 3d Imaging,Mode-ling,Processing,Visualization and Transmission.Hangzhou:IEEE,2011:73- 79.

[21] MEI X,SUN X,DONG W,et al.Segment-tree based cost aggregation for stereo matching [C]∥Proceeding of IEEE International Conference on Acoustics,Speech and Signal Processing.Portland:IEEE,2013:313- 320.

[22] YANG Q.A non-local cost aggregation method for stereo matching [C]∥Proceeding of IEEE Conference on Computer Vision and Pattern Recognition.Providence:IEEE,2012:1402- 1409.