基于改进Census变换的局部立体匹配算法

赵 杰，张肖帅，赵茏菲，郭莉莉，贺光美

(1.河北大学 电子信息工程学院，河北 保定 071000；2. 河北省数字医疗工程重点实验室，河北 保定 071000)

基于改进Census变换的局部立体匹配算法

赵 杰，张肖帅，赵茏菲，郭莉莉，贺光美

(1.河北大学 电子信息工程学院，河北 保定 071000；2. 河北省数字医疗工程重点实验室，河北 保定 071000)

针对基于传统Census变换的立体匹配算法鲁棒性差和精度不高的问题，提出一种基于改进Census变换的自适应权重立体匹配算法。首先，用Census变换窗口中邻域像素的中值来替换中心像素的灰度值，克服了邻域像素对中心像素的依赖；然后用自适应权重的方法分别计算匹配代价和进行立体匹配，得到初始视差；最后通过左右一致性校验和亚像素提精的方法得到稠密的视差图。实验结果表明，该算法有很强的鲁棒性和很高的匹配精度。

立体匹配；Census变换；自适应权重；中值；左右一致性校验

立体视觉中的立体匹配一直是国内外研究的难点和热点。目前常用的方法是基于区域的立体匹配方法，包括局部立体匹配和全局立体匹配[1]。文献[2-5]实现了全局的方法，精度较高，但不太适合在低成本独立的立体视觉系统上实现。文献[1，6]分别利用SAD(Sum of Absolute Difference)和NCC(Normalized Cross Correlation)的局部方法来进行匹配，得到了比较精确的视差图，但很难应用于实际的场合之中。最近出现了半全局的匹配方法[7]，此方法的精度及复杂度位于全局和局部之间，而且适合用于FPGA(Field Programmable Gata Array)等硬件的实现。

文献[8]提出一种非参数变换Census变换，此方法有较强的鲁棒性，在实际的应用中能够得到较好的视差图。文献[9]用像素灰度的绝对值差(Absolute Difference， AD)和Census变换后的汉明距离作为联合匹配代价，构造自适应十字骨架进行立体匹配，获得了高精度的匹配结果。

传统的Census变换有一定的局限性，首先，邻域像素对中心像素的灰度值大小过分依赖，一旦中心像素像素值发生较大变化，会对匹配结果造成很大影响；其次，忽略了中心像素与邻域像素的像素信息，导致匹配精度下降。本文提出一种改进的Census变换来克服以上缺陷。首先，用Census窗口中邻域像素灰度值的中值替代中心像素的值作为参考值，来克服对中心像素的依赖；其次，将自适应权重的方法[10]用到了Census变换中，增加了像素之间的像素信息，使匹配精度提高，再次用自适应权重的方法进行代价聚合，根据极线约束通过WTA(Winner-Takes-All)的方法求出代价和最小时对应的视差，即为匹配点的视差；最后通过左右一致性校验和亚像素求精的方法对初始视差图的视差求精，得到最终的视差图。

1 Census变换

1.1 传统的Census变换

Census变换是一种用于局部立体匹配的非参数变换，变换过程简单，只用到了加法和异或等运算。对图像I中像素p进行变换时，首先以p为中心像素选一个窗口，然后用窗口中每一个邻域像素分别与中心像素比较，如果比中心像素小就用0表示，否则用1表示。表达式如下

(1)

式中：C为变换结果；p为中心像素；qi(i=1,2,…,8)为邻域像素；I(p)和I(qi)分别为其对应灰度值。

最后，将每一个像素的比较结果串成一个码串CV(p)，表达式如下

(2)

如图1所示，以大小为3×3的变换窗口为例，变换过程如下。

图1 Census变换示意图

1.2 Census变换的改进

传统的Census变换中对中心像素的依赖性太大，一旦中心像素受到噪声(例如椒盐或斑点噪声)干扰，会对变换结果产生很大影响。针对此缺陷，本文提出用邻域像素qi的中值来替换中心像素p的灰度值。首先将邻域像素qi从小到大进行排序；然后求取序列的中值，若中值为整数则直接替换中心像素值，若不是则通过四舍五入得到整数值作为所需参考值。中值求取过程如图2。

图2 中值计算示意图

传统方法中，中心像素受到噪声等影响时，像素之间的比较结果可能会发生大的变化，导致匹配代价增大；改进方法中，用邻域像素中值替代中心像素作为新的参考值，当受到噪声影响时，变换结果则不会变化。例如图1中，当中心像素由127变为110时，传统方法变化前的码串为00101001，变化后为01111111，码串发生了大的变化，而用改进的方法变换后，结果仍为00101011。因此，本文方法能有效减小椒盐噪声或斑点噪声对图像造成的影响，同时也能很好地保留图像的边缘信息，鲁棒性得到增强。

文中采用自适应权重的方法进行Census变换，首先为邻域的每个像素自适应地分配一个权重，然后用权重作差，用绝对值差和(SAD)作为新的匹配代价。具体的实现过程如下：

(3)

式中：w(R,P)=exp(-Δc/γc)；Δc为邻域像素与中心像素的欧氏距离，在灰度图像中代表像素强度的差异，在彩色图中代表色彩信息的差异；γc是一个常数，用来调整w的大小。类似地，用同样的方法对左图进行变换，得到WC(xl,y)(k)，从而得到两个变换窗口的匹配代价如下

(4)

式中：xl=xr+d。本文把MC(xr,xl,y)作为之后的匹配代价，既增加了像素之间的像素信息，减少了误匹配率，又使得匹配代价更小。

1.3 匹配代价聚合

代价聚合阶段，选定匹配窗口的大小为W，与文献[10]相似，为窗口中每个像素分配不同的的权重，本文用双权重的办法增加更多像素间的信息。wA(R,P)为右图像匹配窗口邻域像素的权重，wA(L,Q)为左图像的权重，最终的聚合代价为

(5)

式中：W=2s+1；s为匹配窗口的半径；xl=xr+d。最后采用局部优化算法WTA计算出代价D的最小值，此时对应的匹配点为最佳匹配，同时获得初始视差图。

2 视差的提精

由以上过程得到的初始视差，存在很多异常值，降低了结果视差图的可信度。为了减少误差，本文采用左右一致性校验和亚像素求精的方法对其进行处理得到更精确可信的视差图。

首先，通过左右一致性校验检测出这些异常值。例如，左视差图DL中的一点p，与右图中的对应点作差比较，表达式如下

(6)

式中：DL(p)为左视差图点p的视差值；DR(p-(DL(p),0))为对应点视差值；δ为阈值(一般取1)。如果差值大于阈值则认为是异常值，反之为正常值。

异常值包括误匹配点和遮挡点，误匹配点就是由于某种原因错误匹配的点，它们与对应的极线有交点；而遮挡点只在一幅图像中出现，它们与对应极线没有交点[9]。这里对不同区域采用不同的处理，对于封闭区域用异常值周围邻近的可信的视差值来替代；对于深度不连续区域，首先检测出视差图的边缘，在异常值的两边邻近选出两个点p1和p2，哪一个点的匹配代价更小就用哪个点对应的视差值来替代异常值。以上处理方法简单有效，减少了误匹配率。

其次，本文用基于二次多项式差值的亚像素求精方法[12]减少了由视差离散造成的误匹配。对于像素点p，经过差值后得到的视差为d*，公式如下

(7)

式中：C(p,d)为最终代价和；d=DL(p)；d+=d+1；d-=d-1。

最后，将视差结果通过一个3×3的中值滤波器将结果平滑，得到最终精确的视差图。图3为视差提精前后的Teddy视差图，灰黑色代表异常值，可以看出提精后异常值显著减少。

图3 视差提精前后对比图

3 实验结果及分析

图4为本文算法的整个流程图，首先对Census变换进行改进，用邻域像素的中值来替换中心像素，再进行自适应加权，然后进行变换计算匹配代价，再通过WTA的优化策略得到代价和的最小值，从而得到左右视图的初始视差，最后经过视差提精得到最终视差图。

图4 本文算法流程图

为了得到本算法更合适的匹配支持窗口，首先Census变换窗口选用5×5，用不同大小的支持窗口对Teddy图像的深度不连续区域(Disc)、非遮挡区域(Nocc)以及所有区域(All)做了实验，根据不同区域误匹配率的大小来选择最合适的窗口。图5a～5c分别代表Teddy图像所有区域、非遮挡区域和深度不连续区域的误匹配率，很明显当窗口大于9×9时误匹配率下降得很慢了，为了使计算复杂度更小，同时有较低的误匹配率，本文选择9×9的窗口作为最佳匹配窗口。

图5 各区域不同窗口的平均误匹配率

本文算法比传统Census变换的立体匹配算法有更强的抗噪能力。图6为改进Census和传统Census加入椒盐噪声后的匹配结果对比图，实验中对Teddy左右图像加入噪声密度为0.05的椒盐噪声，支持窗口都为9×9，Census变换窗口都为5×5，γc为16，视差搜索范围均为60。从图6中的结果可以看出，改进的Census变换在加入噪声时的匹配精度要高于传统Census变换，在深度不连续区域、非遮挡区域和所有区域的匹配结果均优于传统的方法。

图6 加入噪声后的误匹配率

为了比较本文算法与其他算法的效果，将视差图提交到了Middlebury网站[13]进行评估，网站提供了4组标准图像Tsukuba、Venus、Teddy和Cones，都已经进行了校正，视差的搜索范围分别为0～15、0～19、0～59、0～59。实验中Census变换窗口为5×5，支持窗口的大小为9×9，γc为16。得到的结果如表1所示，很明显本文算法远远优于传统的Census算法；与网站排名第二的ADCensus算法[9]相比，Cones图像在深度不连续区域的误匹配率降低了0.58， 但整体相比还是有一定差距；本文算法优于当前很多种优秀的算法，例如和当前优秀的分割树算法SegmentTree[14]相比，Tsukuba和Venus图像的误匹配率略高，但Teddy和Cones的误匹配率低，整体上与算法SegmentTree精度相当；和经典的AdaptWeight[10]相比，除了Tsukuba图像的非遮挡区域和所有区域，其他图像的匹配结果均优于AdaptWeight算法；和优秀的全局匹配算法NonLocalFilter[15]相比，除了Venus图像其他图像的匹配结果均优于NonLocalFilter算法。由此可见本文算法的匹配精确度还是很高的。

表1 匹配结果评估表(误匹配像素比的比较) %

图7是本文算法对Tsukuba，Venus，Teddy，Cones四幅图像进行匹配得到的视差结果图。图7a为分别为四幅图像灰度图，图7b为真实视差图，图7c为本文最终视差图，图7d为匹配错误的点图，其中黑色和白色区域为异常值点。

图7 本实验结果对比图

为了进一步验证算法的实用性，对真实场景的图像进行立体匹配，实验结果如图8所示。从图中可以看出，本文算法可以很明显地得到各个物体目标，适用于幅度失真的真实场景中。

图8 真实场景结果图

表2为本文方法和传统方法的运行时间对比结果。本实验环境为Intel Core2 2 GHz CPU，2 Gbyte内存，MATLAB7.1。Census变换窗口为5×5，支持窗口为9×9，γc=16。

表2 实际运行时间 ms

从运行时间来看，本文算法时间比传统方法时间要长，这与理论是相吻合的，两次自适应权重的加入使计算复杂度增加，导致了时间的加长。考虑到本文没有对程序进行优化，可以对程序代码进一步的优化提高运行的速度；另外，本文算法的运算大部分都是加减，有少量的乘除，可以通过硬件进行并行加速，提高算法的效率。因此，本文在时间上可以有很大提升。

4 结论

本文提出一种基于改进Census变换的自适应权重局部立体匹配算法，用变换窗口邻域像素的中值代替中心像素灰度值，增强了变换时的稳健性；变换时用自适应权重的方法给窗口每一个邻域像素分配权重，增加了像素间的像素信息，提高了匹配的准确性；在代价聚合时再一次用自适应权重求得匹配代价和，进一步提高匹配精度；最后通过视差提精得到稠密的视差图，结果表明，本文优于传统的Census变换算法以及很多当前优秀的匹配算法。今后主要研究通过对FPGA设计合理的流水线，实现在时间上的加速，从而使算法更具有实时性。

[1] SCHARSTEIN D，SZELISKI R. A taxonomy and evaluation of dense two-frame stereo correspondence algorithms[J]. Comput. Vision，2002(47)：7-42.

[2] YU W，CHEN T，FRANCHETTI F，HOE J C. High performance stereo vision designed for massively data parallel platforms[J]. Circuits Syst. Video Technol.，2010，20(11)：1509-1519.

[3] WANG L，LIAO M，GONG M，et al. High-quality real-time stereo using adaptive cost aggregation and dynamic programming[C]//Proc. International Symposium on 3D Data Processing：Visualization and Transmission. Chapel Hill，North Carolina，USA：IEEE Press，2006：798-805.

[4] JENSEN L B W，KJAER-NIELSEN A，PAUWELS K， ea al. A two-level real-time vision machine combining coarse- and fine-grained parallelism[J]. Real-Time Image Proceeding，2010(5)：291-304.

[5] 武翠芳，王永芳，刘静，等.一种改进的基于BP的立体匹配算法[J]，电视技术，2011，35(20)：28-31.

[6] EINECKE N，EGGERT J.A two-stage correlation method for stereoscopic depth estimation[C]//Proc. International Conference on Digital Image Computing：Techniques and Applications. Sydney：IEEE Press， 2010：227-234.

[7] HIRSCHMULLER H. Accurate and efficient stereo processing by semi-global matching and mutual information[J]. IEEE Computer Society Conference on Computer Vision and Pattern Recognition， 2005(2)：807-814.

[8] ZABIH R，WOODFILL J.Non-parametric local transforms for computing visual correspondence[C]//Proc. European Conference on Computer Vision. Stockholm，Sweden：[ s.n.]，1994：151-158.

[9] MEI X，SUN X，ZHOU M C，et a1. On building an accurate stereo matching system on graphics hardware [C]//Proc. IEEE International Conference on Computer Vision Workshops. Barcelona：IEEE Press，2011：467-474.

[10] YOON K J，KWEON I S. Adaptive support-weight approach for correspondence search[J]. Pattern Analysis and Machine Intelligence，2006，28(4)：650-656.

[11] PALMER S E. Modern theories of Gestalt perception[J].Mind & Language，1990，5(4)：289-293.

[12] YANG Q，WANG L，YANG R，et al. Stereo matching with color-weighted correlation，hierarchical belief propagation and occlusion handling[J]. IEEE TPAMI，2009，31(3)：492-504.

[13] SCHARSTEIN D， SZELISKI R. Middlebury stereo evaluation [EB/OL].[2014-07-15]. http：//vision.middlebury.edu/stereo/eval/.

[14] MEI X，SUN X，DONG W，et al. Segment-tree based cost aggregation for stereo matching[J]. IEEE Conference on Computer Vision and Pattern Recognition，2013(7)： 313-320.

[15] YANG Q. A non-local cost aggregation method for stereo matching[J]. IEEE Conference on Computer Vision and Pattern Recognition，2012(7)：1402-1409.

赵 杰(1969— )，教授，博士，主要研究方向为图像处理；

张肖帅(1988— )，硕士生，主研数字图像处理；

赵茏菲(1988— )，硕士生，主研数字图像处理。

责任编辑：时 雯

Improved Census Transform for Local Stereo Match

ZHAO Jie，ZHANG Xiaoshuai，ZHAO Longfei，GUO Lili，HE Guangmei

(1.CollegeofElectronicandInformationEngineering，HebeiUniversity，HebeiBaoding071000，China；2.KeyLaboratoryofDigitalMedicalEngineeringinHebeiProvince，HebeiBaoding071000，China)

In order to improve the robustness and accuracy of stereo matching based on Census transform， a adaptive weighting stereo matching algorithm based on improved Census transform is proposed. Firstly， the gray value of central pixel is replaced by the median of neighborhood pixels of the transform window， which overcomes the dependence of neighborhood pixels on the center pixel； secondly， the initial parallax is obtained by using the adaptive weighting algorithm on the cost calculation and stereo matching； lastly， the last disparity map is obtained by means of left-right cheking and sub-pixel enhancement.The results demonstrate that this method is more robust and accurate.

stereo matching； Census transform； adapting weighting； median； left-right cheking

【本文献信息】赵杰，张肖帅，赵茏菲,等.基于改进Census变换的局部立体匹配算法[J].电视技术,2015，39(11).

河北省卫生厅科研基金项目(20120395)；河北省教育厅科学技术研究重点项目(ZD20131086)；河北大学中西部高校提升综合实力工程项目

TP391

A

10.16280/j.videoe.2015.11.002

2014-08-11