邻域相关信息的改进Census变换立体匹配算法

马 利，李晶皎，马 技

1.东北大学 信息科学与工程学院，沈阳 110819

2.辽宁大学 信息学院，沈阳 110036

邻域相关信息的改进Census变换立体匹配算法

马 利1，2，李晶皎1，马 技1，2

1.东北大学 信息科学与工程学院，沈阳 110819

2.辽宁大学 信息学院，沈阳 110036

1 引言

近年来随着机器人导航、航天探测和障碍物检测等应用的发展，立体视觉作为能够通过两幅二维图像来提供三维信息的计算机视觉技术也得到了迅猛发展。立体视觉中的关键技术为立体匹配技术，即如何在拍摄同一场景的两幅二维图像中找到相对应的部分，提取视差信息，从而提供能够恢复出该部分的深度信息。早期的立体匹配研究[1]主要集中在如何实现高品质的视差图，因而忽略了计算复杂性和实时性的要求。近年来，研究者将研究重点集中在处理的执行时间和匹配质量之间的折衷方案，也就是以获得最大精度为目标，同时进行速度的最优化[2-4]。

在立体匹配算法中分全局算法和局部算法[1]，全局算法匹配精度高[5]，但计算复杂，计算量较大；局部算法效率较高，易于实现，但易造成误匹配，尤其在视差不连续区域、纹理单一区域，导致局部算法的匹配精度低。在局部算法[6]中，以像素差绝对值（Sum of Absolute Different，SAD）、像素差平方和（Sum of Squared Differences，SSD）、归一化互相关（Normalized Cross Correlation，NCC）为代表，但这些算法对于由于摄像机增益、畸变所引起的图像失真较为敏感，所以研究者提出了非参数变换算法[7]——Rank变换和Census变换来解决这一问题，同时提高了处理速度，能满足立体匹配对实时性的需求。Rank变换和Census变换是将左右图像中匹配点邻域窗口内的像素灰度值与匹配点灰度值进行比较，对图像进行非参数变换，然后进行左右图像匹配。这种处理方法会在匹配点的像素灰度值受噪声影响发生畸变时产生误匹配，同时当匹配点处于视差不连续区域、纹理单一区域时，其匹配的正确性较低。在近几年的研究中，文献[8]提出了基于梯度和灰度图像的改进Census算法，该算法将梯度信息引入Census变换，来提高处于边缘区域像素的匹配精度。文献[9]提出基于互相关信息的非参数变换立体匹配算法，将平均值作为Census算法中心像素的灰度值，并对变换窗口内的像素用双线性插值替代，从而提高算法的鲁棒性。文献[8]的算法由于需要进行边缘检测，增加了相应的计算复杂性，而文献[9]在匹配精度方面虽有提升，但在纹理单一区域、视差不连续区域匹配精度有待进一步提高。文献[10]中利用多位信息进行Census变换，但其改进过程中变换结果存在不唯一性特点，导致在不同纹理区域误匹配较大。

本文提出了一种邻域相关信息的改进Census算法，利用多位信息表示中心像素与邻域信息的差异，使经过Census变换后的图像在图像视差不连续、纹理单一区域的信息表示更为丰富，并可以有效减少噪声对匹配质量的影响，进一步提高匹配精度。

2 利用邻域相关信息的改进Census变换

2.1 传统Census变换

Census变换[7]是一种基于局部的非参数变换，它对于亮度变化具有很高的鲁棒性，通过计算像素灰度值的相关顺序来表示像素的灰度值。Census变换是以像素p为中心点，选取一个特定窗口，将窗口内中心像素以外的像素 p′与中心像素的灰度值进行比较，产生一个比特串来表示中心像素。在比较过程中，窗口中的一个像素灰度值大于中心像素，则相应位置为1，反之，为0。公式（1）给出了具体表示。

对于中心像素则通过将窗口内的所有像素的比较结果串连(⊗)，得到比特向量r来表示中心像素 p与窗口内像素 p′灰度值比较关系，Census变换函数Tct(I，x，y，St)定义为：

其中n，m∈[-(st-1)/2，(st+1)/2]，St为Census变换窗口。I(x，y)为立体匹配图像对中左图或右图中的像素 p的灰度值。

Census变换仅依赖于中心像素与邻域像素的灰度值大小的比较，当中心像素受到噪声影响发生幅度失真的时候，相应的Census变换也随之发生变化，引起误匹配。而在视差不连续区域，由于像素灰度值变化范围大，仅仅依靠与中心像素灰度值大小的比较，不足以对视差变化进行有效表示，从而导致匹配精度不高。

2.2 利用邻域相关信息的Census变换

传统Census变换尽管很大程度上提高了图像在受由于摄像过程中摄像机自身及亮度变化影响时的匹配质量，但当中心像素受噪声影响较大、幅度失真严重的时候，立体匹配的稳健性仍会受到严重影响，同时在视差不连续区域、纹理单一区域传统Census变换本身具有误匹配较高的情况。为了进一步提高匹配质量，本文提出了一种利用邻域相关信息的Census变换立体匹配算法。

利用邻域相关信息的Census变换立体匹配算法主要对Census变换窗口中邻域像素与中心像素进行比较，同时利用邻域像素与邻域均值的灰度差异，用多位信息来表示邻域像素与中心像素的区别，使中心像素的表示更加精确，利于提高匹配的精度。

对于任意一个像素Census变换窗口求取其窗口内邻域的均值，即计算St内像素的邻域灰度均值。

式中n，m∈[-(st-1)/2，(st+1)/2]，num为Census变换窗口内像素个数。

式中T为阈值。对于图像中不同纹理情况下阈值不同，不能采用固定阈值，则定义阈值T：

图1为不同情况下改进的Census变换的具体过程。

图1 不同情况下原算法与改进算法的变换过程

从图1中可以看出，在纹理单一区，对于大于中心像素的像素“193”和“198”，根据与均值不同的灰度差，可对应得到变换码为“00”、“01”，而在原变换中没有区别。在视差不连续区，大于中心像素的“214”、“250”，对应变换码为“00”、“01”，有效地区分了邻域像素与中心像素差异。

3 利用邻域相关信息的Census变换立体匹配算法

根据文献[1]，局部算法由匹配代价计算、代价聚合、视差图优化三部分构成。在利用邻域相关信息的Census变换立体匹配算法中，算法流程如图2所示。

图2 本文立体匹配算法流程图

3.1 初始匹配代价计算

初始匹配代价是立体匹配算法中的基础，经过改进Census变换后，通过计算左右图中像素的比特向量r1和r2的汉明距得到像素间的相似性，在视差搜索范围[dmin，dmax]内，不同视差等级d下初始匹配代价Rct：

因在改进的Census变换中，采用多位信息表示，一定程度上增加了矢量比特向量r的位数，所以在汉明距计算部分采用了文献[11]中稀疏汉明距计算法，通过计算左右图像中匹配窗口中特定点的汉明距来替代对窗口中所有像素进行汉明距计算的方法，从而减少计算量。并将每个像素在不同视差下的初始匹配代价存储在视差空间图像（Disparity Space Image，DSI）中，即应用尺寸为视差等级×图形宽度×图像高度(disparity× width×height)，三维数据结构对每个视差等级的初始匹配代价进行存储。

3.2 并行分层权重代价聚合

自适应权重（Adaptive Support Weight）算法[12]是局部算法中较好的代价聚合方法。该算法采用固定大小的支持窗口，根据窗口内各像素q与待匹配的像素 p的色彩差异和空间位置差异来给予不同权重，从而得到可靠的聚合窗口。在色彩差异计算中采用CIELab色彩空间中Lab 3个分量的欧式距离Δcpq表示，空间位置差异定义为行、列之间的欧式距离Δgpq。

并应用Guassian函数评价色彩差异 f(Δcpq)和空间距离差异 f(Δgpq)的相关性：

从而得到代价聚合局部像素对中心像素的支持权重。

对于参考图像中的待匹配像素p和聚合窗内像素q，在目标图像中对应像素和，在 p和的支持窗口内，待匹配像素p和可能匹配像素差异度C′(p,)为：

为了降低代价聚合的复杂度，本文算法采用并行分层权重代价聚合方法，即对待匹配像素在不同视差等级d进行分层双通道累加方法。双通道累加方法[13]将加权计算拆分为行和列两个方向进行独立计算，从而快速进行代价累加。该方法首先对聚合窗口内每行初始匹配代价与相应权值的内积进行累加，与相应权重值的累加和进行归一化计算，得到行方向匹配代价的聚合结果；对所得的行代价聚合结果与相应列的权重进行内积，与相应权值的累加和归一化计算后得到最后的代价聚合结果。

其中，w(x，y，m，0)、w(x，y，0，n)分别是在W×W 窗口内行、列方向的权重值，C′col(x，y，d)为行方向对初始匹配代价的权重代价聚合，Ccol(x，y，d)是对行权重代价聚合C′col(x，y，d)在列方向上权重代价聚合。并行多层权重代价聚合方法是在每一视差等级上先后对行、列方向上代价进行权重平均，是复杂度从原算法的O(W2d)降低为O(2Wd)。

应用WTA（Winner-Take-All）策略选取最小代价值的视差d作像素的最终视差，从而得到稠密视差图。

4 实验结果及分析

为测试本文算法的有效性，利用Middlebury大学网站的标准立体匹配算法测试平台所提供的4对基准彩色图像Tsukuba，Venus，Teddy和Cones对算法进行了匹配测试，并根据其正确匹配率进行了性能分析。按照测试要求，对于以上4组测试立体图像对，与测试平台所要求的参数保持一致，本文参数设置如下，Census变换窗口为11×11；并行分层权重代价聚合窗口为35×35，γc=5，γg=17.5。误匹配评估阈值设为1。

本文算法对4组测试立体图像对的稠密视差结果如图3所示，直接反映了本文算法的优劣，其中第1列和第2列为标准立体图像对的左图和标准视差图，从上到下分别是Tsukuba、Venus、Teddy和Cones，第3列为本文算法得到的视差图，第4列图像为本文算法得到的视差图与标准视差图之间的差异，图中黑色区域为在无遮挡区域误匹配区域，灰色区域为遮挡区域误匹配区域，白色大片区域为正确匹配区域。第5列图像是本文算法匹配正确的像素点与匹配错误的像素点整体对比的误差图，灰色区域表示匹配正确的区域，黑色和白色的区域表示匹配错误的区域。

图3 本文算法对Middlebury数据集的匹配结果

表1为本文算法与Middlebury测试平台及已发表的改进Census算法的性能评估结果。主要包括与ADCensus[14]、RTCensus[2]、SAD-IGMCT[8]、MI-nonpara[9]、NIMCT[10]的立体匹配性能评估，采用误匹配像素百分比来对非遮挡区（nocc）、视差不连续区（disc）和总体匹配（all）进行性能评估。图4为本文算法计算的视差图与以上算法计算视差图的比较，从左到右分别是本文算法、ADCensus、SAD-IGMCT、MI-nonpara、NIMCT。本文算法RINCensus的相应结果在Middlebury测试平台评估界面http：//vision.middlebury.edu/stereo/eval/可查。

图4 本文算法与Middlebury数据集几种改进Census算法的立体匹配结果对比

表1 本文算法与Middlebury平台几种改进Census算法的立体性能评估

从表1和图4可以看出：相比ADCensus算法和RTCensus算法在立体匹配的正确率方面，本文算法略低，但高于SAD-IGMCT算法、MI-nonpara算法和NIMCT算法；在视差不连续区本文算法低于网站排名第2的ADCensus算法，与RTCensus算法接近，但明显优于其他算法。本文算法在较大的弱纹理区域也能够获得稠密视差图，在纹理单一区域、遮挡区域和视差不连续区域也能保持较明显的边界。

由于本文算法采用了WTA策略进行初始代价选取，Census窗口的尺寸对匹配算法相似度计算具有重要影响。图5描述了本文算法和传统Census算法在代价聚合窗口为3×3时不同Census窗口对无遮挡区域匹配正确率的影响。此外，传统Census算法在光照等因素引起的畸变情况下其性能优于其他相似度测量算法，如SAD算法[1]。本文算法除具有原算法的优越性之外，在一定程度上提高了由噪声引起失真的图像对的匹配精度。图6为本文算法和传统Census算法对存在随机噪声的立体匹配对在不同Census窗口情况下的匹配结果的比较。

图5 不同Census变换窗口尺寸对匹配质量的影响

图6 噪声情况下不同Census窗口尺寸对匹配质量的影响

由图5和图6可以看出：（1）Census窗口M尺寸越小，误匹配率R越高；随着M增大，误匹配率R降低，主要原因在于窗口M取值较小的时候，窗口内的抗噪声能力较差，导致容易发生误匹配。（2）随着Census窗口M尺寸逐渐增大，当大于一定值时，误匹配R增加，这是由于在视差不连续区域窗口越大，对Census变换结果影响较大，引起了误匹配。

5 结论

本文针对传统Census变换的不足，提出了一种利用邻域相关信息的改进Census变换立体匹配算法。应用2位信息来表示像素与中心像素、像素与邻域灰度均值的灰度差异对Census变换进行了改进，通过稀疏汉明距计算得到初始匹配代价；经过并行分层权重代价聚合提高匹配精度，并降低了代价聚合计算复杂度；经过亚像素插值、左右一致性检测和遮挡区插值等视差图后处理得到了稠密视差图。

实验表明，本文方法能够对基于Census变换的立体匹配算法的匹配准确度有一定的提高，并同时具有较高的鲁棒性。算法的结构简单，复杂性低，适于硬件实现。如何进一步提高算法的精确度，尤其是采用合适的遮挡区域插值算法，并使算法具有实时快速的特点，将是未来的研究方向。

[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/3）：7-42.

[2]Humenberger M，Zinner C，Weber M，et al.A fast stereo matching algorithm suitable for embedded real-time systems[J].Computer Vision and Image Understanding，2010，114（11）：1180-1202.

[3]Drazic V，Sabater N.A precise real-time stereo algorithm[C]// Proceedings of the 27th Conference on Image and Vision Computing，2012：138-143.

[4]Kowalczuk J，Psota E T，Pérez L C.Real-time stereo matching on CUDA using an iterative refinement method for adaptive support-weight correspondences[J].IEEE Transactions on Circuits and Systems for Video Technology，2013，23（1）：94-104.

[5]Yang Q，Wang L，Ahuja N.A constant-space belief propagation algorithm for stereo matching[C]//2010 IEEE Conference on Computer Vision and Pattern Recognition（CVPR），2010：1458-1465.

[6]Stefano L D，Marchionni M，Mattoccia S.A fast area-based stereo matching algorithm[J].Image and Vision Computing，2004，22（12）：983-1005.

[7]Zabih R，Woodfill J.Non-parametric local transforms for computing visual correspondence[C]//ECCV’94.Berlin Heidelberg：Springer，1994：151-158.

[8]Ambrosch K，Kubinger W.Accurate hardware-based stereo vision[J].Computer Vision and Image Understanding，2010，114（11）：1303-1316.

[9]赖小波，朱世强.基于互相关信息的非参数变换立体匹配算法[J].浙江大学学报：工学版，2011，45（9）：1636-1642.

[10]Ma L，Li J，Ma J，et al.A modified census transform based on the neighborhood information for Stereo matching algorithm[C]//2013 Seventh International Conference on Image and Graphics（ICIG），2013：533-538.

[11]Ambrosch K，Zinner C，Leopold H.A miniature embedded stereo vision system for automotive applications[C]//26th Convention of Electrical and Electronics Engineers，2010.

[12]Yoon K J，Kweon I S.Adaptive support-weight approach for correspondence search[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2006，28（4）：650-656.

[13]刘天亮，霍智勇，朱秀昌，等.基于DAISY描述符和改进型权重核的快速局部立体匹配[J].南京邮电大学学报：自然科学版，2012，32（4）：70-76.

[14]Mei X，Sun X，Zhou M，et al.On building an accurate stereo matching system on graphics hardware[C]//2011 IEEE International Conference on Computer Vision Workshops（ICCV Workshops），2011：467-474.

MA Li1，2,LI Jingjiao1,MA Ji1，2

1.School of Information Science&Engineering,Northeastern University,Shenyang 110819,China
2.School of Information,Liaoning University,Shenyang 110036,China

This paper proposes a modified Census transform which is based on information of the neighborhood for stereo matching to improve the classic Census transform by reducing mismatching of depth discontinuity as well as the noise disturbance.This new Census transform utilizes 2 bit to represent the differences between the pixel and its neighborhood.The result image of the transform provides more details on depth discontinuity and minimizes the impact of noise on the quality of matching.A dense disparity map is then generated through paralleled adaptive cost aggregation,stereo correspondence, sub-pixel interpolation and interpolation of the occluded regions.The evaluation of Middlebury stereo images shows that the proposed algorithm enhances the accuracy of matching with concise structure and low complexity with strong robustness.

stereo matching;Census transform;related information of neighborhood;cost aggregation;depth discontinuity

针对传统Census变换在视差不连续区域和噪声干扰情况下误匹配率较高的情况，提出了一种利用邻域相关信息的改进Census变换立体匹配算法。根据邻域像素的相关信息，将传统的Census变换中像素与邻域像素的差异应用2位信息表示，使变换后的图像在视差不连续区域的信息表示更为丰富，同时减少噪声对匹配质量的影响。通过并行化自适应匹配代价聚合、亚像素插值、左右一致性约束、遮挡区插值，最终得到了稠密视差图。经Middlebury立体图片测试表明，该算法结构简单，复杂度低，具有较高的鲁棒性，有效地提高了匹配精度。

立体匹配；Census变换；邻域相关信息；代价聚合；视差不连续

A

TP391

10.3778/j.issn.1002-8331.1405-0081

MA Li,LI Jingjiao,MA Ji.Modified Census transform with related information of neighborhood for stereo matching algorithm.Computer Engineering and Applications,2014,50（24）：16-20.

国家自然科学基金（No.60970157）；辽宁省教育厅一般科技项目（No.L2012003）。

马利（1978—），女，博士研究生，讲师，CCF会员，研究领域为计算机视觉，嵌入式；李晶皎（1964—），女，博士，教授，研究领域为模式识别，嵌入式；马技（1980—），男，博士研究生，讲师，研究领域为计算机视觉。E-mail：mali@lnu.edu.cn

2014-05-09

2014-07-17

1002-8331（2014）24-0016-05

CNKI网络优先出版：2014-08-19，http∶//www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1405-0081.html