鄰域相關(guān)信息的改進(jìn)Census變換立體匹配算法

馬 利，李晶皎，馬 技

1.東北大學(xué) 信息科學(xué)與工程學(xué)院，沈陽 110819

2.遼寧大學(xué) 信息學(xué)院，沈陽 110036

鄰域相關(guān)信息的改進(jìn)Census變換立體匹配算法

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

1.東北大學(xué) 信息科學(xué)與工程學(xué)院，沈陽 110819

2.遼寧大學(xué) 信息學(xué)院，沈陽 110036

1 引言

近年來隨著機(jī)器人導(dǎo)航、航天探測和障礙物檢測等應(yīng)用的發(fā)展，立體視覺作為能夠通過兩幅二維圖像來提供三維信息的計(jì)算機(jī)視覺技術(shù)也得到了迅猛發(fā)展。立體視覺中的關(guān)鍵技術(shù)為立體匹配技術(shù)，即如何在拍攝同一場景的兩幅二維圖像中找到相對應(yīng)的部分，提取視差信息，從而提供能夠恢復(fù)出該部分的深度信息。早期的立體匹配研究[1]主要集中在如何實(shí)現(xiàn)高品質(zhì)的視差圖，因而忽略了計(jì)算復(fù)雜性和實(shí)時(shí)性的要求。近年來，研究者將研究重點(diǎn)集中在處理的執(zhí)行時(shí)間和匹配質(zhì)量之間的折衷方案，也就是以獲得最大精度為目標(biāo)，同時(shí)進(jìn)行速度的最優(yōu)化[2-4]。

在立體匹配算法中分全局算法和局部算法[1]，全局算法匹配精度高[5]，但計(jì)算復(fù)雜，計(jì)算量較大；局部算法效率較高，易于實(shí)現(xiàn)，但易造成誤匹配，尤其在視差不連續(xù)區(qū)域、紋理單一區(qū)域，導(dǎo)致局部算法的匹配精度低。在局部算法[6]中，以像素差絕對值（Sum of Absolute Different，SAD）、像素差平方和（Sum of Squared Differences，SSD）、歸一化互相關(guān)（Normalized Cross Correlation，NCC）為代表，但這些算法對于由于攝像機(jī)增益、畸變所引起的圖像失真較為敏感，所以研究者提出了非參數(shù)變換算法[7]——Rank變換和Census變換來解決這一問題，同時(shí)提高了處理速度，能滿足立體匹配對實(shí)時(shí)性的需求。Rank變換和Census變換是將左右圖像中匹配點(diǎn)鄰域窗口內(nèi)的像素灰度值與匹配點(diǎn)灰度值進(jìn)行比較，對圖像進(jìn)行非參數(shù)變換，然后進(jìn)行左右圖像匹配。這種處理方法會(huì)在匹配點(diǎn)的像素灰度值受噪聲影響發(fā)生畸變時(shí)產(chǎn)生誤匹配，同時(shí)當(dāng)匹配點(diǎn)處于視差不連續(xù)區(qū)域、紋理單一區(qū)域時(shí)，其匹配的正確性較低。在近幾年的研究中，文獻(xiàn)[8]提出了基于梯度和灰度圖像的改進(jìn)Census算法，該算法將梯度信息引入Census變換，來提高處于邊緣區(qū)域像素的匹配精度。文獻(xiàn)[9]提出基于互相關(guān)信息的非參數(shù)變換立體匹配算法，將平均值作為Census算法中心像素的灰度值，并對變換窗口內(nèi)的像素用雙線性插值替代，從而提高算法的魯棒性。文獻(xiàn)[8]的算法由于需要進(jìn)行邊緣檢測，增加了相應(yīng)的計(jì)算復(fù)雜性，而文獻(xiàn)[9]在匹配精度方面雖有提升，但在紋理單一區(qū)域、視差不連續(xù)區(qū)域匹配精度有待進(jìn)一步提高。文獻(xiàn)[10]中利用多位信息進(jìn)行Census變換，但其改進(jìn)過程中變換結(jié)果存在不唯一性特點(diǎn)，導(dǎo)致在不同紋理區(qū)域誤匹配較大。

本文提出了一種鄰域相關(guān)信息的改進(jìn)Census算法，利用多位信息表示中心像素與鄰域信息的差異，使經(jīng)過Census變換后的圖像在圖像視差不連續(xù)、紋理單一區(qū)域的信息表示更為豐富，并可以有效減少噪聲對匹配質(zhì)量的影響，進(jìn)一步提高匹配精度。

2 利用鄰域相關(guān)信息的改進(jìn)Census變換

2.1 傳統(tǒng)Census變換

Census變換[7]是一種基于局部的非參數(shù)變換，它對于亮度變化具有很高的魯棒性，通過計(jì)算像素灰度值的相關(guān)順序來表示像素的灰度值。Census變換是以像素p為中心點(diǎn)，選取一個(gè)特定窗口，將窗口內(nèi)中心像素以外的像素 p′與中心像素的灰度值進(jìn)行比較，產(chǎn)生一個(gè)比特串來表示中心像素。在比較過程中，窗口中的一個(gè)像素灰度值大于中心像素，則相應(yīng)位置為1，反之，為0。公式（1）給出了具體表示。

對于中心像素則通過將窗口內(nèi)的所有像素的比較結(jié)果串連(?)，得到比特向量r來表示中心像素 p與窗口內(nèi)像素 p′灰度值比較關(guān)系，Census變換函數(shù)Tct(I，x，y，St)定義為：

其中n，m∈[-(st-1)/2，(st+1)/2]，St為Census變換窗口。I(x，y)為立體匹配圖像對中左圖或右圖中的像素 p的灰度值。

Census變換僅依賴于中心像素與鄰域像素的灰度值大小的比較，當(dāng)中心像素受到噪聲影響發(fā)生幅度失真的時(shí)候，相應(yīng)的Census變換也隨之發(fā)生變化，引起誤匹配。而在視差不連續(xù)區(qū)域，由于像素灰度值變化范圍大，僅僅依靠與中心像素灰度值大小的比較，不足以對視差變化進(jìn)行有效表示，從而導(dǎo)致匹配精度不高。

2.2 利用鄰域相關(guān)信息的Census變換

傳統(tǒng)Census變換盡管很大程度上提高了圖像在受由于攝像過程中攝像機(jī)自身及亮度變化影響時(shí)的匹配質(zhì)量，但當(dāng)中心像素受噪聲影響較大、幅度失真嚴(yán)重的時(shí)候，立體匹配的穩(wěn)健性仍會(huì)受到嚴(yán)重影響，同時(shí)在視差不連續(xù)區(qū)域、紋理單一區(qū)域傳統(tǒng)Census變換本身具有誤匹配較高的情況。為了進(jìn)一步提高匹配質(zhì)量，本文提出了一種利用鄰域相關(guān)信息的Census變換立體匹配算法。

利用鄰域相關(guān)信息的Census變換立體匹配算法主要對Census變換窗口中鄰域像素與中心像素進(jìn)行比較，同時(shí)利用鄰域像素與鄰域均值的灰度差異，用多位信息來表示鄰域像素與中心像素的區(qū)別，使中心像素的表示更加精確，利于提高匹配的精度。

對于任意一個(gè)像素Census變換窗口求取其窗口內(nèi)鄰域的均值，即計(jì)算St內(nèi)像素的鄰域灰度均值。

式中n，m∈[-(st-1)/2，(st+1)/2]，num為Census變換窗口內(nèi)像素個(gè)數(shù)。

式中T為閾值。對于圖像中不同紋理情況下閾值不同，不能采用固定閾值，則定義閾值T：

圖1為不同情況下改進(jìn)的Census變換的具體過程。

圖1 不同情況下原算法與改進(jìn)算法的變換過程

從圖1中可以看出，在紋理單一區(qū)，對于大于中心像素的像素“193”和“198”，根據(jù)與均值不同的灰度差，可對應(yīng)得到變換碼為“00”、“01”，而在原變換中沒有區(qū)別。在視差不連續(xù)區(qū)，大于中心像素的“214”、“250”，對應(yīng)變換碼為“00”、“01”，有效地區(qū)分了鄰域像素與中心像素差異。

3 利用鄰域相關(guān)信息的Census變換立體匹配算法

根據(jù)文獻(xiàn)[1]，局部算法由匹配代價(jià)計(jì)算、代價(jià)聚合、視差圖優(yōu)化三部分構(gòu)成。在利用鄰域相關(guān)信息的Census變換立體匹配算法中，算法流程如圖2所示。

圖2 本文立體匹配算法流程圖

3.1 初始匹配代價(jià)計(jì)算

初始匹配代價(jià)是立體匹配算法中的基礎(chǔ)，經(jīng)過改進(jìn)Census變換后，通過計(jì)算左右圖中像素的比特向量r1和r2的漢明距得到像素間的相似性，在視差搜索范圍[dmin，dmax]內(nèi)，不同視差等級d下初始匹配代價(jià)Rct：

因在改進(jìn)的Census變換中，采用多位信息表示，一定程度上增加了矢量比特向量r的位數(shù)，所以在漢明距計(jì)算部分采用了文獻(xiàn)[11]中稀疏漢明距計(jì)算法，通過計(jì)算左右圖像中匹配窗口中特定點(diǎn)的漢明距來替代對窗口中所有像素進(jìn)行漢明距計(jì)算的方法，從而減少計(jì)算量。并將每個(gè)像素在不同視差下的初始匹配代價(jià)存儲在視差空間圖像（Disparity Space Image，DSI）中，即應(yīng)用尺寸為視差等級×圖形寬度×圖像高度(disparity× width×height)，三維數(shù)據(jù)結(jié)構(gòu)對每個(gè)視差等級的初始匹配代價(jià)進(jìn)行存儲。

3.2 并行分層權(quán)重代價(jià)聚合

自適應(yīng)權(quán)重（Adaptive Support Weight）算法[12]是局部算法中較好的代價(jià)聚合方法。該算法采用固定大小的支持窗口，根據(jù)窗口內(nèi)各像素q與待匹配的像素 p的色彩差異和空間位置差異來給予不同權(quán)重，從而得到可靠的聚合窗口。在色彩差異計(jì)算中采用CIELab色彩空間中Lab 3個(gè)分量的歐式距離Δcpq表示，空間位置差異定義為行、列之間的歐式距離Δgpq。

并應(yīng)用Guassian函數(shù)評價(jià)色彩差異 f(Δcpq)和空間距離差異 f(Δgpq)的相關(guān)性：

從而得到代價(jià)聚合局部像素對中心像素的支持權(quán)重。

對于參考圖像中的待匹配像素p和聚合窗內(nèi)像素q，在目標(biāo)圖像中對應(yīng)像素和，在 p和的支持窗口內(nèi)，待匹配像素p和可能匹配像素差異度C′(p,)為：

為了降低代價(jià)聚合的復(fù)雜度，本文算法采用并行分層權(quán)重代價(jià)聚合方法，即對待匹配像素在不同視差等級d進(jìn)行分層雙通道累加方法。雙通道累加方法[13]將加權(quán)計(jì)算拆分為行和列兩個(gè)方向進(jìn)行獨(dú)立計(jì)算，從而快速進(jìn)行代價(jià)累加。該方法首先對聚合窗口內(nèi)每行初始匹配代價(jià)與相應(yīng)權(quán)值的內(nèi)積進(jìn)行累加，與相應(yīng)權(quán)重值的累加和進(jìn)行歸一化計(jì)算，得到行方向匹配代價(jià)的聚合結(jié)果；對所得的行代價(jià)聚合結(jié)果與相應(yīng)列的權(quán)重進(jìn)行內(nèi)積，與相應(yīng)權(quán)值的累加和歸一化計(jì)算后得到最后的代價(jià)聚合結(jié)果。

其中，w(x，y，m，0)、w(x，y，0，n)分別是在W×W 窗口內(nèi)行、列方向的權(quán)重值，C′col(x，y，d)為行方向?qū)Τ跏计ヅ浯鷥r(jià)的權(quán)重代價(jià)聚合，Ccol(x，y，d)是對行權(quán)重代價(jià)聚合C′col(x，y，d)在列方向上權(quán)重代價(jià)聚合。并行多層權(quán)重代價(jià)聚合方法是在每一視差等級上先后對行、列方向上代價(jià)進(jìn)行權(quán)重平均，是復(fù)雜度從原算法的O(W2d)降低為O(2Wd)。

應(yīng)用WTA（Winner-Take-All）策略選取最小代價(jià)值的視差d作像素的最終視差，從而得到稠密視差圖。

4 實(shí)驗(yàn)結(jié)果及分析

為測試本文算法的有效性，利用Middlebury大學(xué)網(wǎng)站的標(biāo)準(zhǔn)立體匹配算法測試平臺所提供的4對基準(zhǔn)彩色圖像Tsukuba，Venus，Teddy和Cones對算法進(jìn)行了匹配測試，并根據(jù)其正確匹配率進(jìn)行了性能分析。按照測試要求，對于以上4組測試立體圖像對，與測試平臺所要求的參數(shù)保持一致，本文參數(shù)設(shè)置如下，Census變換窗口為11×11；并行分層權(quán)重代價(jià)聚合窗口為35×35，γc=5，γg=17.5。誤匹配評估閾值設(shè)為1。

本文算法對4組測試立體圖像對的稠密視差結(jié)果如圖3所示，直接反映了本文算法的優(yōu)劣，其中第1列和第2列為標(biāo)準(zhǔn)立體圖像對的左圖和標(biāo)準(zhǔn)視差圖，從上到下分別是Tsukuba、Venus、Teddy和Cones，第3列為本文算法得到的視差圖，第4列圖像為本文算法得到的視差圖與標(biāo)準(zhǔn)視差圖之間的差異，圖中黑色區(qū)域?yàn)樵跓o遮擋區(qū)域誤匹配區(qū)域，灰色區(qū)域?yàn)檎趽鯀^(qū)域誤匹配區(qū)域，白色大片區(qū)域?yàn)檎_匹配區(qū)域。第5列圖像是本文算法匹配正確的像素點(diǎn)與匹配錯(cuò)誤的像素點(diǎn)整體對比的誤差圖，灰色區(qū)域表示匹配正確的區(qū)域，黑色和白色的區(qū)域表示匹配錯(cuò)誤的區(qū)域。

圖3 本文算法對Middlebury數(shù)據(jù)集的匹配結(jié)果

表1為本文算法與Middlebury測試平臺及已發(fā)表的改進(jìn)Census算法的性能評估結(jié)果。主要包括與ADCensus[14]、RTCensus[2]、SAD-IGMCT[8]、MI-nonpara[9]、NIMCT[10]的立體匹配性能評估，采用誤匹配像素百分比來對非遮擋區(qū)（nocc）、視差不連續(xù)區(qū)（disc）和總體匹配（all）進(jìn)行性能評估。圖4為本文算法計(jì)算的視差圖與以上算法計(jì)算視差圖的比較，從左到右分別是本文算法、ADCensus、SAD-IGMCT、MI-nonpara、NIMCT。本文算法RINCensus的相應(yīng)結(jié)果在Middlebury測試平臺評估界面http：//vision.middlebury.edu/stereo/eval/可查。

圖4 本文算法與Middlebury數(shù)據(jù)集幾種改進(jìn)Census算法的立體匹配結(jié)果對比

表1 本文算法與Middlebury平臺幾種改進(jìn)Census算法的立體性能評估

從表1和圖4可以看出：相比ADCensus算法和RTCensus算法在立體匹配的正確率方面，本文算法略低，但高于SAD-IGMCT算法、MI-nonpara算法和NIMCT算法；在視差不連續(xù)區(qū)本文算法低于網(wǎng)站排名第2的ADCensus算法，與RTCensus算法接近，但明顯優(yōu)于其他算法。本文算法在較大的弱紋理區(qū)域也能夠獲得稠密視差圖，在紋理單一區(qū)域、遮擋區(qū)域和視差不連續(xù)區(qū)域也能保持較明顯的邊界。

由于本文算法采用了WTA策略進(jìn)行初始代價(jià)選取，Census窗口的尺寸對匹配算法相似度計(jì)算具有重要影響。圖5描述了本文算法和傳統(tǒng)Census算法在代價(jià)聚合窗口為3×3時(shí)不同Census窗口對無遮擋區(qū)域匹配正確率的影響。此外，傳統(tǒng)Census算法在光照等因素引起的畸變情況下其性能優(yōu)于其他相似度測量算法，如SAD算法[1]。本文算法除具有原算法的優(yōu)越性之外，在一定程度上提高了由噪聲引起失真的圖像對的匹配精度。圖6為本文算法和傳統(tǒng)Census算法對存在隨機(jī)噪聲的立體匹配對在不同Census窗口情況下的匹配結(jié)果的比較。

圖5 不同Census變換窗口尺寸對匹配質(zhì)量的影響

圖6 噪聲情況下不同Census窗口尺寸對匹配質(zhì)量的影響

由圖5和圖6可以看出：（1）Census窗口M尺寸越小，誤匹配率R越高；隨著M增大，誤匹配率R降低，主要原因在于窗口M取值較小的時(shí)候，窗口內(nèi)的抗噪聲能力較差，導(dǎo)致容易發(fā)生誤匹配。（2）隨著Census窗口M尺寸逐漸增大，當(dāng)大于一定值時(shí)，誤匹配R增加，這是由于在視差不連續(xù)區(qū)域窗口越大，對Census變換結(jié)果影響較大，引起了誤匹配。

5 結(jié)論

本文針對傳統(tǒng)Census變換的不足，提出了一種利用鄰域相關(guān)信息的改進(jìn)Census變換立體匹配算法。應(yīng)用2位信息來表示像素與中心像素、像素與鄰域灰度均值的灰度差異對Census變換進(jìn)行了改進(jìn)，通過稀疏漢明距計(jì)算得到初始匹配代價(jià)；經(jīng)過并行分層權(quán)重代價(jià)聚合提高匹配精度，并降低了代價(jià)聚合計(jì)算復(fù)雜度；經(jīng)過亞像素插值、左右一致性檢測和遮擋區(qū)插值等視差圖后處理得到了稠密視差圖。

實(shí)驗(yàn)表明，本文方法能夠?qū)贑ensus變換的立體匹配算法的匹配準(zhǔn)確度有一定的提高，并同時(shí)具有較高的魯棒性。算法的結(jié)構(gòu)簡單，復(fù)雜性低，適于硬件實(shí)現(xiàn)。如何進(jìn)一步提高算法的精確度，尤其是采用合適的遮擋區(qū)域插值算法，并使算法具有實(shí)時(shí)快速的特點(diǎn)，將是未來的研究方向。

[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]賴小波，朱世強(qiáng).基于互相關(guān)信息的非參數(shù)變換立體匹配算法[J].浙江大學(xué)學(xué)報(bào)：工學(xué)版，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ìn)型權(quán)重核的快速局部立體匹配[J].南京郵電大學(xué)學(xué)報(bào)：自然科學(xué)版，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

針對傳統(tǒng)Census變換在視差不連續(xù)區(qū)域和噪聲干擾情況下誤匹配率較高的情況，提出了一種利用鄰域相關(guān)信息的改進(jìn)Census變換立體匹配算法。根據(jù)鄰域像素的相關(guān)信息，將傳統(tǒng)的Census變換中像素與鄰域像素的差異應(yīng)用2位信息表示，使變換后的圖像在視差不連續(xù)區(qū)域的信息表示更為豐富，同時(shí)減少噪聲對匹配質(zhì)量的影響。通過并行化自適應(yīng)匹配代價(jià)聚合、亞像素插值、左右一致性約束、遮擋區(qū)插值，最終得到了稠密視差圖。經(jīng)Middlebury立體圖片測試表明，該算法結(jié)構(gòu)簡單，復(fù)雜度低，具有較高的魯棒性，有效地提高了匹配精度。

立體匹配；Census變換；鄰域相關(guān)信息；代價(jià)聚合；視差不連續(xù)

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.

國家自然科學(xué)基金（No.60970157）；遼寧省教育廳一般科技項(xiàng)目（No.L2012003）。

馬利（1978—），女，博士研究生，講師，CCF會(huì)員，研究領(lǐng)域?yàn)橛?jì)算機(jī)視覺，嵌入式；李晶皎（1964—），女，博士，教授，研究領(lǐng)域?yàn)槟Ｊ阶R別，嵌入式；馬技（1980—），男，博士研究生，講師，研究領(lǐng)域?yàn)橛?jì)算機(jī)視覺。E-mail：mali@lnu.edu.cn

2014-05-09

2014-07-17

1002-8331（2014）24-0016-05

CNKI網(wǎng)絡(luò)優(yōu)先出版：2014-08-19，http∶//www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1405-0081.html