張 波，謝 明，劉 杰

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

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

張 波，謝 明，劉 杰

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

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

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

0 引言

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

立體視覺匹配算法一般分為：全局匹配算法和局部匹配算法，本次主要針對(duì)局部匹配算法。通常的局部匹配算法(如：像素差絕對(duì)值（SAD）、像素差平方和（SSD）歸一化互相關(guān)（NCC）等)往往對(duì)畸變引起的圖像失真較為敏感，為此 ZABIN R和 WOODFILL J[4]提出了 Census和Rank變換。文獻(xiàn)[5]提出將圖像的梯度圖引入Census變換匹配，需要改變相應(yīng)的系數(shù)才能得到較好的效果。文獻(xiàn)[6]雖然將原先的密集矩陣變?yōu)橄∈杈仃嚕沁吘墔^(qū)域的誤匹配率還是很高。基于上述討論，本文提出基于Census變換一種新的初始匹配代價(jià)計(jì)算的匹配算法。

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

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

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

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

圖1 3個(gè)5×5匹配窗口的像素

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

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

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

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

3 稀疏匹配代價(jià)聚合

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

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

匹配聚合代價(jià)公式如下：

▽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ù)，更重要的是它并沒有使用中心像素，而是使用了均值像素，這樣就可以很好地減少因中間像素異常造成的誤匹配。

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

4 算法對(duì)比

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

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

圖2是通過以上實(shí)驗(yàn)得到的最終匹配視差結(jié)果，Census變換窗口大小為 17×17，密集聚合匹配算法聚合窗口大小21×21，離散聚合匹配算法聚合窗口大小15× 15。依次為：匹配原圖、Hamming稀疏聚合視差圖、Hamming密集聚合視差圖、真實(shí)視差圖。

圖3、圖4是對(duì)SAD（見opencv2）、Census聚合（變換窗口17×17）、本文提出的密集聚合算法以及稀疏聚合算法進(jìn)行的對(duì)比試驗(yàn)。其中圖3是對(duì)加入白噪聲后的圖像進(jìn)行的實(shí)驗(yàn)。由圖3、圖4可知，在誤匹配率方面，本文提出的密集和離散聚合算法雖然在處理速度上小于SAD和 Census聚合這兩種算法，但是其誤匹配率也遠(yuǎn)遠(yuǎn)小于SAD和 Census聚合這兩種算法。稀疏和密集聚合算法分別在 24.7 f/s和19.9 f/s趨于平穩(wěn)，適用于實(shí)時(shí)立體匹配。綜合誤匹配和處理速度來看，提出的基于Census變換的權(quán)值稀疏聚合立體匹配算法更有優(yōu)勢。

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

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

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

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

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

5 結(jié)束語

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

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.