鄰域相關信息的改進Census變換立體匹配算法

馬 利，李晶皎，馬 技

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

2.遼寧大學 信息學院，沈陽 110036

鄰域相關信息的改進Census變換立體匹配算法

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

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

2.遼寧大學 信息學院，沈陽 110036

1 引言

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

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

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

2 利用鄰域相關信息的改進Census變換

2.1 傳統Census變換

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

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

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

Census變換僅依賴于中心像素與鄰域像素的灰度值大小的比較，當中心像素受到噪聲影響發生幅度失真的時候，相應的Census變換也隨之發生變化，引起誤匹配。而在視差不連續區域，由于像素灰度值變化范圍大，僅僅依靠與中心像素灰度值大小的比較，不足以對視差變化進行有效表示，從而導致匹配精度不高。

2.2 利用鄰域相關信息的Census變換

傳統Census變換盡管很大程度上提高了圖像在受由于攝像過程中攝像機自身及亮度變化影響時的匹配質量，但當中心像素受噪聲影響較大、幅度失真嚴重的時候，立體匹配的穩健性仍會受到嚴重影響，同時在視差不連續區域、紋理單一區域傳統Census變換本身具有誤匹配較高的情況。為了進一步提高匹配質量，本文提出了一種利用鄰域相關信息的Census變換立體匹配算法。

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

對于任意一個像素Census變換窗口求取其窗口內鄰域的均值，即計算St內像素的鄰域灰度均值。

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

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

圖1為不同情況下改進的Census變換的具體過程。

圖1 不同情況下原算法與改進算法的變換過程

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

3 利用鄰域相關信息的Census變換立體匹配算法

根據文獻[1]，局部算法由匹配代價計算、代價聚合、視差圖優化三部分構成。在利用鄰域相關信息的Census變換立體匹配算法中，算法流程如圖2所示。

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

3.1 初始匹配代價計算

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

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

3.2 并行分層權重代價聚合

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

并應用Guassian函數評價色彩差異 f(Δcpq)和空間距離差異 f(Δgpq)的相關性：

從而得到代價聚合局部像素對中心像素的支持權重。

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

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

其中，w(x，y，m，0)、w(x，y，0，n)分別是在W×W 窗口內行、列方向的權重值，C′col(x，y，d)為行方向對初始匹配代價的權重代價聚合，Ccol(x，y，d)是對行權重代價聚合C′col(x，y，d)在列方向上權重代價聚合。并行多層權重代價聚合方法是在每一視差等級上先后對行、列方向上代價進行權重平均，是復雜度從原算法的O(W2d)降低為O(2Wd)。

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

4 實驗結果及分析

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

本文算法對4組測試立體圖像對的稠密視差結果如圖3所示，直接反映了本文算法的優劣，其中第1列和第2列為標準立體圖像對的左圖和標準視差圖，從上到下分別是Tsukuba、Venus、Teddy和Cones，第3列為本文算法得到的視差圖，第4列圖像為本文算法得到的視差圖與標準視差圖之間的差異，圖中黑色區域為在無遮擋區域誤匹配區域，灰色區域為遮擋區域誤匹配區域，白色大片區域為正確匹配區域。第5列圖像是本文算法匹配正確的像素點與匹配錯誤的像素點整體對比的誤差圖，灰色區域表示匹配正確的區域，黑色和白色的區域表示匹配錯誤的區域。

圖3 本文算法對Middlebury數據集的匹配結果

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

圖4 本文算法與Middlebury數據集幾種改進Census算法的立體匹配結果對比

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

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

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

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

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

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

5 結論

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

實驗表明，本文方法能夠對基于Census變換的立體匹配算法的匹配準確度有一定的提高，并同時具有較高的魯棒性。算法的結構簡單，復雜性低，適于硬件實現。如何進一步提高算法的精確度，尤其是采用合適的遮擋區域插值算法，并使算法具有實時快速的特點，將是未來的研究方向。

[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]賴小波，朱世強.基于互相關信息的非參數變換立體匹配算法[J].浙江大學學報：工學版，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].南京郵電大學學報：自然科學版，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

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

立體匹配；Census變換；鄰域相關信息；代價聚合；視差不連續

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.

國家自然科學基金（No.60970157）；遼寧省教育廳一般科技項目（No.L2012003）。

馬利（1978—），女，博士研究生，講師，CCF會員，研究領域為計算機視覺，嵌入式；李晶皎（1964—），女，博士，教授，研究領域為模式識別，嵌入式；馬技（1980—），男，博士研究生，講師，研究領域為計算機視覺。E-mail：mali@lnu.edu.cn

2014-05-09

2014-07-17

1002-8331（2014）24-0016-05

CNKI網絡優先出版：2014-08-19，http∶//www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1405-0081.html