基于改進Census變換的局部立體匹配算法

趙 杰，張肖帥，趙蘢菲，郭莉莉，賀光美

(1.河北大學 電子信息工程學院，河北 保定 071000；2. 河北省數字醫療工程重點實驗室，河北 保定 071000)

基于改進Census變換的局部立體匹配算法

趙 杰，張肖帥，趙蘢菲，郭莉莉，賀光美

(1.河北大學 電子信息工程學院，河北 保定 071000；2. 河北省數字醫療工程重點實驗室，河北 保定 071000)

針對基于傳統Census變換的立體匹配算法魯棒性差和精度不高的問題，提出一種基于改進Census變換的自適應權重立體匹配算法。首先，用Census變換窗口中鄰域像素的中值來替換中心像素的灰度值，克服了鄰域像素對中心像素的依賴；然后用自適應權重的方法分別計算匹配代價和進行立體匹配，得到初始視差；最后通過左右一致性校驗和亞像素提精的方法得到稠密的視差圖。實驗結果表明，該算法有很強的魯棒性和很高的匹配精度。

立體匹配；Census變換；自適應權重；中值；左右一致性校驗

立體視覺中的立體匹配一直是國內外研究的難點和熱點。目前常用的方法是基于區域的立體匹配方法，包括局部立體匹配和全局立體匹配[1]。文獻[2-5]實現了全局的方法，精度較高，但不太適合在低成本獨立的立體視覺系統上實現。文獻[1，6]分別利用SAD(Sum of Absolute Difference)和NCC(Normalized Cross Correlation)的局部方法來進行匹配，得到了比較精確的視差圖，但很難應用于實際的場合之中。最近出現了半全局的匹配方法[7]，此方法的精度及復雜度位于全局和局部之間，而且適合用于FPGA(Field Programmable Gata Array)等硬件的實現。

文獻[8]提出一種非參數變換Census變換，此方法有較強的魯棒性，在實際的應用中能夠得到較好的視差圖。文獻[9]用像素灰度的絕對值差(Absolute Difference， AD)和Census變換后的漢明距離作為聯合匹配代價，構造自適應十字骨架進行立體匹配，獲得了高精度的匹配結果。

傳統的Census變換有一定的局限性，首先，鄰域像素對中心像素的灰度值大小過分依賴，一旦中心像素像素值發生較大變化，會對匹配結果造成很大影響；其次，忽略了中心像素與鄰域像素的像素信息，導致匹配精度下降。本文提出一種改進的Census變換來克服以上缺陷。首先，用Census窗口中鄰域像素灰度值的中值替代中心像素的值作為參考值，來克服對中心像素的依賴；其次，將自適應權重的方法[10]用到了Census變換中，增加了像素之間的像素信息，使匹配精度提高，再次用自適應權重的方法進行代價聚合，根據極線約束通過WTA(Winner-Takes-All)的方法求出代價和最小時對應的視差，即為匹配點的視差；最后通過左右一致性校驗和亞像素求精的方法對初始視差圖的視差求精，得到最終的視差圖。

1 Census變換

1.1 傳統的Census變換

Census變換是一種用于局部立體匹配的非參數變換，變換過程簡單，只用到了加法和異或等運算。對圖像I中像素p進行變換時，首先以p為中心像素選一個窗口，然后用窗口中每一個鄰域像素分別與中心像素比較，如果比中心像素小就用0表示，否則用1表示。表達式如下

(1)

式中：C為變換結果；p為中心像素；qi(i=1,2,…,8)為鄰域像素；I(p)和I(qi)分別為其對應灰度值。

最后，將每一個像素的比較結果串成一個碼串CV(p)，表達式如下

(2)

如圖1所示，以大小為3×3的變換窗口為例，變換過程如下。

圖1 Census變換示意圖

1.2 Census變換的改進

傳統的Census變換中對中心像素的依賴性太大，一旦中心像素受到噪聲(例如椒鹽或斑點噪聲)干擾，會對變換結果產生很大影響。針對此缺陷，本文提出用鄰域像素qi的中值來替換中心像素p的灰度值。首先將鄰域像素qi從小到大進行排序；然后求取序列的中值，若中值為整數則直接替換中心像素值，若不是則通過四舍五入得到整數值作為所需參考值。中值求取過程如圖2。

圖2 中值計算示意圖

傳統方法中，中心像素受到噪聲等影響時，像素之間的比較結果可能會發生大的變化，導致匹配代價增大；改進方法中，用鄰域像素中值替代中心像素作為新的參考值，當受到噪聲影響時，變換結果則不會變化。例如圖1中，當中心像素由127變為110時，傳統方法變化前的碼串為00101001，變化后為01111111，碼串發生了大的變化，而用改進的方法變換后，結果仍為00101011。因此，本文方法能有效減小椒鹽噪聲或斑點噪聲對圖像造成的影響，同時也能很好地保留圖像的邊緣信息，魯棒性得到增強。

文中采用自適應權重的方法進行Census變換，首先為鄰域的每個像素自適應地分配一個權重，然后用權重作差，用絕對值差和(SAD)作為新的匹配代價。具體的實現過程如下：

(3)

式中：w(R,P)=exp(-Δc/γc)；Δc為鄰域像素與中心像素的歐氏距離，在灰度圖像中代表像素強度的差異，在彩色圖中代表色彩信息的差異；γc是一個常數，用來調整w的大小。類似地，用同樣的方法對左圖進行變換，得到WC(xl,y)(k)，從而得到兩個變換窗口的匹配代價如下

(4)

式中：xl=xr+d。本文把MC(xr,xl,y)作為之后的匹配代價，既增加了像素之間的像素信息，減少了誤匹配率，又使得匹配代價更小。

1.3 匹配代價聚合

代價聚合階段，選定匹配窗口的大小為W，與文獻[10]相似，為窗口中每個像素分配不同的的權重，本文用雙權重的辦法增加更多像素間的信息。wA(R,P)為右圖像匹配窗口鄰域像素的權重，wA(L,Q)為左圖像的權重，最終的聚合代價為

(5)

式中：W=2s+1；s為匹配窗口的半徑；xl=xr+d。最后采用局部優化算法WTA計算出代價D的最小值，此時對應的匹配點為最佳匹配，同時獲得初始視差圖。

2 視差的提精

由以上過程得到的初始視差，存在很多異常值，降低了結果視差圖的可信度。為了減少誤差，本文采用左右一致性校驗和亞像素求精的方法對其進行處理得到更精確可信的視差圖。

首先，通過左右一致性校驗檢測出這些異常值。例如，左視差圖DL中的一點p，與右圖中的對應點作差比較，表達式如下

(6)

式中：DL(p)為左視差圖點p的視差值；DR(p-(DL(p),0))為對應點視差值；δ為閾值(一般取1)。如果差值大于閾值則認為是異常值，反之為正常值。

異常值包括誤匹配點和遮擋點，誤匹配點就是由于某種原因錯誤匹配的點，它們與對應的極線有交點；而遮擋點只在一幅圖像中出現，它們與對應極線沒有交點[9]。這里對不同區域采用不同的處理，對于封閉區域用異常值周圍鄰近的可信的視差值來替代；對于深度不連續區域，首先檢測出視差圖的邊緣，在異常值的兩邊鄰近選出兩個點p1和p2，哪一個點的匹配代價更小就用哪個點對應的視差值來替代異常值。以上處理方法簡單有效，減少了誤匹配率。

其次，本文用基于二次多項式差值的亞像素求精方法[12]減少了由視差離散造成的誤匹配。對于像素點p，經過差值后得到的視差為d*，公式如下

(7)

式中：C(p,d)為最終代價和；d=DL(p)；d+=d+1；d-=d-1。

最后，將視差結果通過一個3×3的中值濾波器將結果平滑，得到最終精確的視差圖。圖3為視差提精前后的Teddy視差圖，灰黑色代表異常值，可以看出提精后異常值顯著減少。

圖3 視差提精前后對比圖

3 實驗結果及分析

圖4為本文算法的整個流程圖，首先對Census變換進行改進，用鄰域像素的中值來替換中心像素，再進行自適應加權，然后進行變換計算匹配代價，再通過WTA的優化策略得到代價和的最小值，從而得到左右視圖的初始視差，最后經過視差提精得到最終視差圖。

圖4 本文算法流程圖

為了得到本算法更合適的匹配支持窗口，首先Census變換窗口選用5×5，用不同大小的支持窗口對Teddy圖像的深度不連續區域(Disc)、非遮擋區域(Nocc)以及所有區域(All)做了實驗，根據不同區域誤匹配率的大小來選擇最合適的窗口。圖5a～5c分別代表Teddy圖像所有區域、非遮擋區域和深度不連續區域的誤匹配率，很明顯當窗口大于9×9時誤匹配率下降得很慢了，為了使計算復雜度更小，同時有較低的誤匹配率，本文選擇9×9的窗口作為最佳匹配窗口。

圖5 各區域不同窗口的平均誤匹配率

本文算法比傳統Census變換的立體匹配算法有更強的抗噪能力。圖6為改進Census和傳統Census加入椒鹽噪聲后的匹配結果對比圖，實驗中對Teddy左右圖像加入噪聲密度為0.05的椒鹽噪聲，支持窗口都為9×9，Census變換窗口都為5×5，γc為16，視差搜索范圍均為60。從圖6中的結果可以看出，改進的Census變換在加入噪聲時的匹配精度要高于傳統Census變換，在深度不連續區域、非遮擋區域和所有區域的匹配結果均優于傳統的方法。

圖6 加入噪聲后的誤匹配率

為了比較本文算法與其他算法的效果，將視差圖提交到了Middlebury網站[13]進行評估，網站提供了4組標準圖像Tsukuba、Venus、Teddy和Cones，都已經進行了校正，視差的搜索范圍分別為0～15、0～19、0～59、0～59。實驗中Census變換窗口為5×5，支持窗口的大小為9×9，γc為16。得到的結果如表1所示，很明顯本文算法遠遠優于傳統的Census算法；與網站排名第二的ADCensus算法[9]相比，Cones圖像在深度不連續區域的誤匹配率降低了0.58， 但整體相比還是有一定差距；本文算法優于當前很多種優秀的算法，例如和當前優秀的分割樹算法SegmentTree[14]相比，Tsukuba和Venus圖像的誤匹配率略高，但Teddy和Cones的誤匹配率低，整體上與算法SegmentTree精度相當；和經典的AdaptWeight[10]相比，除了Tsukuba圖像的非遮擋區域和所有區域，其他圖像的匹配結果均優于AdaptWeight算法；和優秀的全局匹配算法NonLocalFilter[15]相比，除了Venus圖像其他圖像的匹配結果均優于NonLocalFilter算法。由此可見本文算法的匹配精確度還是很高的。

表1 匹配結果評估表(誤匹配像素比的比較) %

圖7是本文算法對Tsukuba，Venus，Teddy，Cones四幅圖像進行匹配得到的視差結果圖。圖7a為分別為四幅圖像灰度圖，圖7b為真實視差圖，圖7c為本文最終視差圖，圖7d為匹配錯誤的點圖，其中黑色和白色區域為異常值點。

圖7 本實驗結果對比圖

為了進一步驗證算法的實用性，對真實場景的圖像進行立體匹配，實驗結果如圖8所示。從圖中可以看出，本文算法可以很明顯地得到各個物體目標，適用于幅度失真的真實場景中。

圖8 真實場景結果圖

表2為本文方法和傳統方法的運行時間對比結果。本實驗環境為Intel Core2 2 GHz CPU，2 Gbyte內存，MATLAB7.1。Census變換窗口為5×5，支持窗口為9×9，γc=16。

表2 實際運行時間 ms

從運行時間來看，本文算法時間比傳統方法時間要長，這與理論是相吻合的，兩次自適應權重的加入使計算復雜度增加，導致了時間的加長。考慮到本文沒有對程序進行優化，可以對程序代碼進一步的優化提高運行的速度；另外，本文算法的運算大部分都是加減，有少量的乘除，可以通過硬件進行并行加速，提高算法的效率。因此，本文在時間上可以有很大提升。

4 結論

本文提出一種基于改進Census變換的自適應權重局部立體匹配算法，用變換窗口鄰域像素的中值代替中心像素灰度值，增強了變換時的穩健性；變換時用自適應權重的方法給窗口每一個鄰域像素分配權重，增加了像素間的像素信息，提高了匹配的準確性；在代價聚合時再一次用自適應權重求得匹配代價和，進一步提高匹配精度；最后通過視差提精得到稠密的視差圖，結果表明，本文優于傳統的Census變換算法以及很多當前優秀的匹配算法。今后主要研究通過對FPGA設計合理的流水線，實現在時間上的加速，從而使算法更具有實時性。

[1] SCHARSTEIN D，SZELISKI R. A taxonomy and evaluation of dense two-frame stereo correspondence algorithms[J]. Comput. Vision，2002(47)：7-42.

[2] YU W，CHEN T，FRANCHETTI F，HOE J C. High performance stereo vision designed for massively data parallel platforms[J]. Circuits Syst. Video Technol.，2010，20(11)：1509-1519.

[3] WANG L，LIAO M，GONG M，et al. High-quality real-time stereo using adaptive cost aggregation and dynamic programming[C]//Proc. International Symposium on 3D Data Processing：Visualization and Transmission. Chapel Hill，North Carolina，USA：IEEE Press，2006：798-805.

[4] JENSEN L B W，KJAER-NIELSEN A，PAUWELS K， ea al. A two-level real-time vision machine combining coarse- and fine-grained parallelism[J]. Real-Time Image Proceeding，2010(5)：291-304.

[5] 武翠芳，王永芳，劉靜，等.一種改進的基于BP的立體匹配算法[J]，電視技術，2011，35(20)：28-31.

[6] EINECKE N，EGGERT J.A two-stage correlation method for stereoscopic depth estimation[C]//Proc. International Conference on Digital Image Computing：Techniques and Applications. Sydney：IEEE Press， 2010：227-234.

[7] HIRSCHMULLER H. Accurate and efficient stereo processing by semi-global matching and mutual information[J]. IEEE Computer Society Conference on Computer Vision and Pattern Recognition， 2005(2)：807-814.

[8] ZABIH R，WOODFILL J.Non-parametric local transforms for computing visual correspondence[C]//Proc. European Conference on Computer Vision. Stockholm，Sweden：[ s.n.]，1994：151-158.

[9] MEI X，SUN X，ZHOU M C，et a1. On building an accurate stereo matching system on graphics hardware [C]//Proc. IEEE International Conference on Computer Vision Workshops. Barcelona：IEEE Press，2011：467-474.

[10] YOON K J，KWEON I S. Adaptive support-weight approach for correspondence search[J]. Pattern Analysis and Machine Intelligence，2006，28(4)：650-656.

[11] PALMER S E. Modern theories of Gestalt perception[J].Mind & Language，1990，5(4)：289-293.

[12] YANG Q，WANG L，YANG R，et al. Stereo matching with color-weighted correlation，hierarchical belief propagation and occlusion handling[J]. IEEE TPAMI，2009，31(3)：492-504.

[13] SCHARSTEIN D， SZELISKI R. Middlebury stereo evaluation [EB/OL].[2014-07-15]. http：//vision.middlebury.edu/stereo/eval/.

[14] MEI X，SUN X，DONG W，et al. Segment-tree based cost aggregation for stereo matching[J]. IEEE Conference on Computer Vision and Pattern Recognition，2013(7)： 313-320.

[15] YANG Q. A non-local cost aggregation method for stereo matching[J]. IEEE Conference on Computer Vision and Pattern Recognition，2012(7)：1402-1409.

趙 杰(1969— )，教授，博士，主要研究方向為圖像處理；

張肖帥(1988— )，碩士生，主研數字圖像處理；

趙蘢菲(1988— )，碩士生，主研數字圖像處理。

責任編輯：時 雯

Improved Census Transform for Local Stereo Match

ZHAO Jie，ZHANG Xiaoshuai，ZHAO Longfei，GUO Lili，HE Guangmei

(1.CollegeofElectronicandInformationEngineering，HebeiUniversity，HebeiBaoding071000，China；2.KeyLaboratoryofDigitalMedicalEngineeringinHebeiProvince，HebeiBaoding071000，China)

In order to improve the robustness and accuracy of stereo matching based on Census transform， a adaptive weighting stereo matching algorithm based on improved Census transform is proposed. Firstly， the gray value of central pixel is replaced by the median of neighborhood pixels of the transform window， which overcomes the dependence of neighborhood pixels on the center pixel； secondly， the initial parallax is obtained by using the adaptive weighting algorithm on the cost calculation and stereo matching； lastly， the last disparity map is obtained by means of left-right cheking and sub-pixel enhancement.The results demonstrate that this method is more robust and accurate.

stereo matching； Census transform； adapting weighting； median； left-right cheking

【本文獻信息】趙杰，張肖帥，趙蘢菲,等.基于改進Census變換的局部立體匹配算法[J].電視技術,2015，39(11).

河北省衛生廳科研基金項目(20120395)；河北省教育廳科學技術研究重點項目(ZD20131086)；河北大學中西部高校提升綜合實力工程項目

TP391

A

10.16280/j.videoe.2015.11.002

2014-08-11