基于Census變換的自適應(yīng)權(quán)值Hamming距離立體匹配算法

張 波，謝 明，劉 杰

(南京工業(yè)大學(xué) 電氣工程與控制科學(xué)學(xué)院，江蘇 南京 211800)

基于Census變換的自適應(yīng)權(quán)值Hamming距離立體匹配算法

張 波，謝 明，劉 杰

(南京工業(yè)大學(xué) 電氣工程與控制科學(xué)學(xué)院，江蘇 南京 211800)

傳統(tǒng)的Census+Hamming距離立體匹配算法往往由于將鄰域像素等同對待，從而缺少足夠的匹配信息，造成較高的誤匹配率。對此提出了一種自適用加權(quán)的Hamming距離算法，通過引入鄰域像素空間距離，使在距離測算時將鄰域像素分等級計算，豐富了匹配圖像的信息。并且使用梯度圖像像素之間的距離作為聚合代價計算的權(quán)值，實驗證明其對于噪聲有一定的抗干擾性，并且能夠很好地反映紋理等信息，同時引入稀疏聚合窗口來減少算法的復(fù)雜度。最后進行亞像素插值增大匹配的正確性。通過對比試驗證明，此算法不僅能夠提高匹配的準(zhǔn)確性和抗干擾性，還能減少算法的復(fù)雜度，適用于實時的立體匹配。

Census變換；加權(quán)Hamming距離；梯度圖像；稀疏聚合窗口

0 引言

現(xiàn)如今隨著人工智能的發(fā)展，用于獲取三維信息的立體視覺算法變得越來越重要，目前已經(jīng)提出了很多立體視覺的算法，并且成功應(yīng)用于機器人導(dǎo)航[1]、現(xiàn)實環(huán)境中三維重建[2]以及智能車輛障礙物的檢測[3]等。然而，現(xiàn)在多數(shù)的實時立體視覺對于弱紋理區(qū)域缺少足夠的精確性，以至于還需要其他的傳感器來輔助檢測這些障礙物。

立體視覺匹配算法一般分為：全局匹配算法和局部匹配算法，本次主要針對局部匹配算法。通常的局部匹配算法(如：像素差絕對值（SAD）、像素差平方和（SSD）歸一化互相關(guān)（NCC）等)往往對畸變引起的圖像失真較為敏感，為此 ZABIN R和 WOODFILL J[4]提出了 Census和Rank變換。文獻[5]提出將圖像的梯度圖引入Census變換匹配，需要改變相應(yīng)的系數(shù)才能得到較好的效果。文獻[6]雖然將原先的密集矩陣變?yōu)橄∈杈仃?，但是邊緣區(qū)域的誤匹配率還是很高?；谏鲜鲇懻摚疚奶岢龌贑ensus變換一種新的初始匹配代價計算的匹配算法。

1 傳統(tǒng)的Census變換與初始匹配代價計算

傳統(tǒng)Census變換對于亮度變化具有很高的魯棒性。Census變換的函數(shù)如式（1）：

其中，P(u，v)為中心像素值，st為變換窗口，大小為 n×m。Census變換匹配算法的處理速度很大程度上取決于變換窗口 st的大小，窗口越大，匹配的準(zhǔn)確率越高，相反其視差連續(xù)性越差，處理的時間也就越長，所以選擇合適大小的窗口也是很重要的問題，本文將在第4節(jié)進行試驗，獲得最佳窗口大小。

傳統(tǒng) Hamming距離并沒有考慮鄰域像素與中心像素的空間距離關(guān)系，而將像素鄰域的所有像素?zé)o偏差地處理，很容易造成誤匹配，如圖1所示兩個像素窗口并不匹配，但是計算他們的Hamming距離的結(jié)果顯示這兩個窗口匹配。而本文提出的一種新的距離計算方法能夠解決這個問題。

圖1 3個5×5匹配窗口的像素

2 改進的加權(quán)Hamming距離初始匹配代價計算

本文提出的初始匹配代價計算方法并不是完全使用Census變換之后的比特串。首先根據(jù)式（2）計算兩個窗口之間的距離，也就是初始匹配代價 ecTN：

其中， ▽gi，j為兩個像素之間的歐式距離，n×m為窗口大小，γg為一個常數(shù)，根據(jù)文獻[7]取 γg為 17.5。這樣就可以根據(jù)像素點距離中心點的距離賦予相應(yīng)的權(quán)重，距離近權(quán)重值大，遠則小，也就是相異像素距離中心像素越近，那么其越不匹配。通過這樣計算就能減少Hamming+Census所產(chǎn)生的誤匹配像素。

由上面的計算說明可知，因為加入了空間距離的權(quán)重系數(shù)，本文提出的加權(quán)Hamming距離測算比傳統(tǒng)方法更有優(yōu)勢，更能體現(xiàn)出像素鄰域的信息。

3 稀疏匹配代價聚合

為了提高 census變換匹配的準(zhǔn)確性，通常的算法是增大變換的窗口，這樣往往造成邊緣模糊化。而梯度圖像可以表示出圖像的紋理信息，而且通過Soble算子計算梯度并不會太多地增加算法復(fù)雜度，所以本文采用梯度圖像來增加匹配圖像的信息。

在此采用自適用權(quán)重的算法[7]，同時引入梯度信息和稀疏窗口，由于在初始匹配代價計算的過程中將空間距離已經(jīng)引入，所以在此并不包括空間距離信息。

匹配聚合代價公式如下：

▽c(I，J)′為像素I與像素J在Lab色彩空間的梯度像素歐氏距離，γ▽c為常數(shù)，這里取 7.5。▽c(I，J)為 Lab空間的領(lǐng)域像素J與此窗口的像素均值LμI之間的歐式距離，γc=5。引入▽c(I，J)，一方面可以豐富匹配的特征數(shù)，更重要的是它并沒有使用中心像素，而是使用了均值像素，這樣就可以很好地減少因中間像素異常造成的誤匹配。

為了降低代價聚合的復(fù)雜度，本文還采用了稀疏聚合窗口和分層權(quán)重代價聚合。稀疏窗口[6]是將原先的密集聚合窗口改為變?yōu)槊扛粢恍羞x擇一次采樣，每隔一列選擇一次采樣聚合，實驗證明，采用稀疏聚合窗口不僅不會降低匹配的準(zhǔn)確率，而且能夠大幅地降低算法的復(fù)雜度。并行分層權(quán)重代價聚合方法，即對待匹配像素在不同視差等級d進行分層雙通道累加方法。雙通道累加方法[8]將加權(quán)計算拆分為行和列兩個方向進行獨立計算，從而快速進行代價累加。該方法首先對聚合窗口內(nèi)每行初始匹配代價與相應(yīng)權(quán)值的內(nèi)積進行累加，與相應(yīng)權(quán)重值的累加和進行歸一化計算，得到行方向匹配代價的聚合結(jié)果；對所得的行代價聚合結(jié)果與相應(yīng)列的權(quán)重進行內(nèi)積，與相應(yīng)權(quán)值的累加和歸一化計算后得到最后的代價聚合結(jié)果。并行多層權(quán)重代價聚合方法是在每一視差等級上先后對行、列方向上代價進行權(quán)重平均，使復(fù)雜度從原算法的O(w2d)降低為O(2wd)。其中w為聚合窗口大小。

4 算法對比

本文對Middlebury大學(xué)網(wǎng)站的標(biāo)準(zhǔn)立體匹配算法測試平臺所提供的4對基準(zhǔn)彩色圖像Tsukuba、Venus、Teddy和 Cones進行匹配測試，Census變換窗口從 5×5到 23× 23，密集代價聚合窗口從 5×5到 23×23，稀疏聚合窗口從 5×5到 19×19，在電腦上通過視覺庫 opencv進行處理，電腦CPU主頻為2.6 GHz，內(nèi)存2 GB。

本文首先對Census變換+Hamming立體匹配做了實驗，并且采用單個像素匹配，Census變換窗口大小由5×5到 23×23。為了獲得較好的效果，本文算法聚合所使用的Census變換窗口大小為17×17，雖然增大會進一步降低誤匹配率，但是減少幅度并不大，而且會增大算法復(fù)雜度。所以在此將Census+Hamming單像素立體匹配算法的最優(yōu)匹配窗口定為 17×17，然后使用本文所提出的自適用權(quán)值 Hamming密集聚合和稀疏聚合算法(Census變換窗口為17×17)進行了實驗，實驗結(jié)果見表1。由表1可知，隨著聚合的窗口的增大，其平均誤匹配率減小，并且密集聚合在21×21趨于平穩(wěn)。

圖2是通過以上實驗得到的最終匹配視差結(jié)果，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趨于平穩(wěn)，適用于實時立體匹配。綜合誤匹配和處理速度來看，提出的基于Census變換的權(quán)值稀疏聚合立體匹配算法更有優(yōu)勢。

圖2 本文提出算法的匹配結(jié)果

圖3 4種匹配誤差率隨聚合窗口變化趨勢(白噪聲)

圖4 4種匹配算法幀率隨聚合窗口變換趨勢

表1 自適用權(quán)值漢明距聚合匹配結(jié)果(單位：%)

表2是與幾種改進Census算法的比較，這些算法包括SAD-iGMCT、RTCensus提出的改進Census立體匹配算法[9，10]。由表2看出，匹配正確率方面，本文算法低于RTCensus算法和SAD-IGMCT算法，但是高于其他算法。本文提出的算法適用于實時的立體匹配。

5 結(jié)束語

本文針對傳統(tǒng)的Census+Hamming匹配算法的不足，提出了一種使用變換窗口中空間距離作為權(quán)值的新的初始匹配代價的計算方法。本文將空間距離加入了初始距離的測算，使初始匹配代價的計算更加偏重于距離中心像素較近的像素；并且引入了梯度圖像和稀疏聚合窗口，提高匹配程度；加入鄰域像素與像素均值之間的距離，減少了因中間像素異常而產(chǎn)生的誤匹配；而稀疏聚合窗口可以在匹配誤差率相差不大的情況下降低算法的復(fù)雜度，適用于實時匹配。

Stereo matching algorithm using adaptive weight Hamming distance based on Census transform

Zhang Bo，Xie Ming，Liu Jie
（College of Electrical Engineering and Control Science，Nanjing Tech University，Nanjing 211800，China）

Traditional Census+Hamming distance stereo matching algorithm often treated since the neighboring pixels equally,which usually resulted in a high mismatching rate because of lacking of sufficient matching information.So this paper proposed a Stereo matching algorithm using adaptive weight Hamming distance based on Census transform by introducing spatial distance between neighbor pixels and their center pixel,which enriched the information of matching images.In order to increase the noise immunity and texture information,the paper used distance between pixels of gradient image as the weight of costs aggregation.At the same time,it used sparse aggregation windows to reduce the complexity of the algorithm.At last，post-processing sub-pixel interpolation was introduced to reduce mismatching rate.The result of the experiments show that the proposed algorithm can not only improve the matching accuracy，but also reduce the complexity of the algorithm,and it is suitable for real time stereo matching.

Census transform；weight Hamming distance；gradient image；sparse aggregation window

TP391

A

10.16157/j.issn.0258-7998.2016.12.031

張波，謝明，劉杰.基于 Census變換的自適應(yīng)權(quán)值 Hamming距離立體匹配算法[J].電子技術(shù)應(yīng)用，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.