比ransac算法好的匹配算法（基于Census变换的自适应权值Hamming距离立体匹配算法）

比ransac算法好的匹配算法（基于Census变换的自适应权值Hamming距离立体匹配算法）英文引用格式：Zhang Bo，Xie Ming，Liu Jie. Stereo matching algorithm using adaptive weight Hamming distance based on Census transform[J].Application of Electronic Technique，2016，42(12)：119-121，125.中文引用格式：张波，谢明，刘杰. 基于Census变换的自适应权值Hamming距离立体匹配算法[J].电子技术应用，2016，42(12)：119-121，125.TP391文献标识码：A10.16157/j.issn.0258-7998.2016.12.031

张 波，谢 明，刘 杰

(南京工业大学 电气工程与控制科学学院，江苏 南京211800)

传统的Census Hamming距离立体匹配算法往往由于将邻域像素等同对待，从而缺少足够的匹配信息，造成较高的误匹配率。对此提出了一种自适用加权的Hamming距离算法，通过引入邻域像素空间距离，使在距离测算时将邻域像素分等级计算，丰富了匹配图像的信息。并且使用梯度图像像素之间的距离作为聚合代价计算的权值，实验证明其对于噪声有一定的抗干扰性，并且能够很好地反映纹理等信息，同时引入稀疏聚合窗口来减少算法的复杂度。最后进行亚像素插值增大匹配的正确性。通过对比试验证明，此算法不仅能够提高匹配的准确性和抗干扰性，还能减少算法的复杂度，适用于实时的立体匹配。

Census变换；加权Hamming距离；梯度图像；稀疏聚合窗口

TP391

文献标识码：A

10.16157/j.issn.0258-7998.2016.12.031

中文引用格式：张波，谢明，刘杰. 基于Census变换的自适应权值Hamming距离立体匹配算法[J].电子技术应用，2016，42(12)：119-121，125.

英文引用格式：Zhang Bo，Xie Ming，Liu Jie. Stereo matching algorithm using adaptive weight Hamming distance based on Census transform[J].Application of Electronic Technique，2016，42(12)：119-121，125.

0 引言

现如今随着人工智能的发展，用于获取三维信息的立体视觉算法变得越来越重要，目前已经提出了很多立体视觉的算法，并且成功应用于机器人导航^[1]、现实环境中三维重建^[2]以及智能车辆障碍物的检测^[3]等。然而，现在多数的实时立体视觉对于弱纹理区域缺少足够的精确性，以至于还需要其他的传感器来辅助检测这些障碍物。

立体视觉匹配算法一般分为：全局匹配算法和局部匹配算法，本次主要针对局部匹配算法。通常的局部匹配算法(如：像素差绝对值（SAD）、像素差平方和（SSD）归一化互相关（NCC）等)往往对畸变引起的图像失真较为敏感，为此ZABIN R和WOODFILL J^[4]提出了Census和Rank变换。文献[5]提出将图像的梯度图引入Census变换匹配，需要改变相应的系数才能得到较好的效果。文献[6]虽然将原先的密集矩阵变为稀疏矩阵，但是边缘区域的误匹配率还是很高。基于上述讨论，本文提出基于Census变换一种新的初始匹配代价计算的匹配算法。

1 传统的Census变换与初始匹配代价计算

传统Census变换对于亮度变化具有很高的鲁棒性。Census变换的函数如式（1）：

其中，P(u，v)为中心像素值，s_t为变换窗口，大小为n×m。Census变换匹配算法的处理速度很大程度上取决于变换窗口s_t的大小，窗口越大，匹配的准确率越高，相反其视差连续性越差，处理的时间也就越长，所以选择合适大小的窗口也是很重要的问题，本文将在第4节进行试验，获得最佳窗口大小。

传统Hamming距离并没有考虑邻域像素与中心像素的空间距离关系，而将像素邻域的所有像素无偏差地处理，很容易造成误匹配，如图1所示两个像素窗口并不匹配，但是计算他们的Hamming距离的结果显示这两个窗口匹配。而本文提出的一种新的距离计算方法能够解决这个问题。

2 改进的加权Hamming距离初始匹配代价计算

本文提出的初始匹配代价计算方法并不是完全使用Census变换之后的比特串。首先根据式（2）计算两个窗口之间的距离，也就是初始匹配代价e_cTN：

由上面的计算说明可知，因为加入了空间距离的权重系数，本文提出的加权Hamming距离测算比传统方法更有优势，更能体现出像素邻域的信息。

3 稀疏匹配代价聚合

为了提高census变换匹配的准确性，通常的算法是增大变换的窗口，这样往往造成边缘模糊化。而梯度图像可以表示出图像的纹理信息，而且通过Soble算子计算梯度并不会太多地增加算法复杂度，所以本文采用梯度图像来增加匹配图像的信息。

在此采用自适用权重的算法^[7]，同时引入梯度信息和稀疏窗口，由于在初始匹配代价计算的过程中将空间距离已经引入，所以在此并不包括空间距离信息。

匹配聚合代价公式如下：

为了降低代价聚合的复杂度，本文还采用了稀疏聚合窗口和分层权重代价聚合。稀疏窗口^[6]是将原先的密集聚合窗口改为变为每隔一行选择一次采样，每隔一列选择一次采样聚合，实验证明，采用稀疏聚合窗口不仅不会降低匹配的准确率，而且能够大幅地降低算法的复杂度。并行分层权重代价聚合方法，即对待匹配像素在不同视差等级d进行分层双通道累加方法。双通道累加方法^[8]将加权计算拆分为行和列两个方向进行独立计算，从而快速进行代价累加。该方法首先对聚合窗口内每行初始匹配代价与相应权值的内积进行累加，与相应权重值的累加和进行归一化计算，得到行方向匹配代价的聚合结果；对所得的行代价聚合结果与相应列的权重进行内积，与相应权值的累加和归一化计算后得到最后的代价聚合结果。并行多层权重代价聚合方法是在每一视差等级上先后对行、列方向上代价进行权重平均，使复杂度从原算法的O(w²d)降低为O(2wd)。其中w为聚合窗口大小。

4 算法对比

本文对Middlebury大学网站的标准立体匹配算法测试平台所提供的4对基准彩色图像Tsukuba、Venus、Teddy和Cones进行匹配测试，Census变换窗口从5×5到23×23，密集代价聚合窗口从5×5到23×23，稀疏聚合窗口从5×5到19×19，在电脑上通过视觉库opencv进行处理，电脑CPU主频为2.6 GHz，内存2 GB。

本文首先对Census变换 Hamming立体匹配做了实验，并且采用单个像素匹配，Census变换窗口大小由5×5到23×23。为了获得较好的效果，本文算法聚合所使用的Census变换窗口大小为17×17，虽然增大会进一步降低误匹配率，但是减少幅度并不大，而且会增大算法复杂度。所以在此将Census Hamming单像素立体匹配算法的最优匹配窗口定为17×17，然后使用本文所提出的自适用权值Hamming密集聚合和稀疏聚合算法(Census变换窗口为17×17)进行了实验，实验结果见表1。由表1可知，随着聚合的窗口的增大，其平均误匹配率减小，并且密集聚合在21×21趋于平稳。

图2是通过以上实验得到的最终匹配视差结果，Census变换窗口大小为17×17，密集聚合匹配算法聚合窗口大小21×21，离散聚合匹配算法聚合窗口大小15×15。依次为：匹配原图、Hamming稀疏聚合视差图、Hamming密集聚合视差图、真实视差图。

图3、图4是对SAD（见opencv2）、Census聚合（变换窗口17×17）、本文提出的密集聚合算法以及稀疏聚合算法进行的对比试验。 其中图3是对加入白噪声后的图像进行的实验。由图3、图4可知，在误匹配率方面，本文提出的密集和离散聚合算法虽然在处理速度上小于SAD和Census聚合这两种算法，但是其误匹配率也远远小于SAD和Census聚合这两种算法。稀疏和密集聚合算法分别在24.7 f/s和19.9 f/s趋于平稳，适用于实时立体匹配。综合误匹配和处理速度来看，提出的基于Census变换的权值稀疏聚合立体匹配算法更有优势。

表2是与几种改进Census算法的比较，这些算法包括SAD-iGMCT、RTCensus提出的改进Census立体匹配算法^[9，10]。由表2看出，匹配正确率方面，本文算法低于RTCensus算法和SAD-IGMCT算法，但是高于其他算法。本文提出的算法适用于实时的立体匹配。

5 结束语

本文针对传统的Census Hamming匹配算法的不足，提出了一种使用变换窗口中空间距离作为权值的新的初始匹配代价的计算方法。本文将空间距离加入了初始距离的测算，使初始匹配代价的计算更加偏重于距离中心像素较近的像素；并且引入了梯度图像和稀疏聚合窗口，提高匹配程度；加入邻域像素与像素均值之间的距离，减少了因中间像素异常而产生的误匹配；而稀疏聚合窗口可以在匹配误差率相差不大的情况下降低算法的复杂度，适用于实时匹配。

参考文献

[1] MEGER D，FORSSEEN P E，LAI K，et al.Curious George，an attentive semantic robot[J].Robotics and Autonomous Systems，2008，56(6)：503-511.

[2] 佟帅，徐晓刚，易成涛.基于视觉的三维重建技术综述[J].计算机应用研究，2011，28(7)：2411-2417.

[3] BOHREN J，FOOTE T，KELLER J.The Ben franklin racing teams entry[J].Journal of Field Robotics，2008，25(9)：598-614.

[4] ZABIH R.WOODFILL J.Non-parametric local transforms for computing visual correspondence[C].ECCV’94.Berlin Heidelberg：Springer，1994：151-158.

[5] AMBROSCH K，KUBINGER W.Accurate hardware-based stereo vision[J].Computer Vision and Image Understanding，2010，114(11)：1303-1316.

[6] HUMENBERGER M，ZINNER C.A fast stereo matching algorithm suitable for embedded real-time systems[J].Computer Vision and Image Understanding，2010，114(11)：1180-1202.

[7] 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.

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

[9] 张晗玥.基于Census变换的区域立体匹配算法研究[D]. 沈阳：辽宁大学，2013.

[10] Middlebury.Middlebury stereo evaluation-Version 2[EB/OL].（2015-07-01）[2016-04-01].http：//vision.middlebury.edu/stereo/eval/.