基于改進(jìn)Census變換的局部立體匹配算法

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

(1.河北大學(xué) 電子信息工程學(xué)院，河北 保定 071000；2. 河北省數(shù)字醫(yī)療工程重點(diǎn)實(shí)驗(yàn)室，河北 保定 071000)

基于改進(jìn)Census變換的局部立體匹配算法

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

(1.河北大學(xué) 電子信息工程學(xué)院，河北 保定 071000；2. 河北省數(shù)字醫(yī)療工程重點(diǎn)實(shí)驗(yàn)室，河北 保定 071000)

針對(duì)基于傳統(tǒng)Census變換的立體匹配算法魯棒性差和精度不高的問(wèn)題，提出一種基于改進(jìn)Census變換的自適應(yīng)權(quán)重立體匹配算法。首先，用Census變換窗口中鄰域像素的中值來(lái)替換中心像素的灰度值，克服了鄰域像素對(duì)中心像素的依賴(lài)；然后用自適應(yīng)權(quán)重的方法分別計(jì)算匹配代價(jià)和進(jìn)行立體匹配，得到初始視差；最后通過(guò)左右一致性校驗(yàn)和亞像素提精的方法得到稠密的視差圖。實(shí)驗(yàn)結(jié)果表明，該算法有很強(qiáng)的魯棒性和很高的匹配精度。

立體匹配；Census變換；自適應(yīng)權(quán)重；中值；左右一致性校驗(yàn)

立體視覺(jué)中的立體匹配一直是國(guó)內(nèi)外研究的難點(diǎn)和熱點(diǎn)。目前常用的方法是基于區(qū)域的立體匹配方法，包括局部立體匹配和全局立體匹配[1]。文獻(xiàn)[2-5]實(shí)現(xiàn)了全局的方法，精度較高，但不太適合在低成本獨(dú)立的立體視覺(jué)系統(tǒng)上實(shí)現(xiàn)。文獻(xiàn)[1，6]分別利用SAD(Sum of Absolute Difference)和NCC(Normalized Cross Correlation)的局部方法來(lái)進(jìn)行匹配，得到了比較精確的視差圖，但很難應(yīng)用于實(shí)際的場(chǎng)合之中。最近出現(xiàn)了半全局的匹配方法[7]，此方法的精度及復(fù)雜度位于全局和局部之間，而且適合用于FPGA(Field Programmable Gata Array)等硬件的實(shí)現(xiàn)。

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

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

1 Census變換

1.1 傳統(tǒng)的Census變換

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

(1)

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

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

(2)

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

圖1 Census變換示意圖

1.2 Census變換的改進(jìn)

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

圖2 中值計(jì)算示意圖

傳統(tǒng)方法中，中心像素受到噪聲等影響時(shí)，像素之間的比較結(jié)果可能會(huì)發(fā)生大的變化，導(dǎo)致匹配代價(jià)增大；改進(jìn)方法中，用鄰域像素中值替代中心像素作為新的參考值，當(dāng)受到噪聲影響時(shí)，變換結(jié)果則不會(huì)變化。例如圖1中，當(dāng)中心像素由127變?yōu)?10時(shí)，傳統(tǒng)方法變化前的碼串為00101001，變化后為01111111，碼串發(fā)生了大的變化，而用改進(jìn)的方法變換后，結(jié)果仍為00101011。因此，本文方法能有效減小椒鹽噪聲或斑點(diǎn)噪聲對(duì)圖像造成的影響，同時(shí)也能很好地保留圖像的邊緣信息，魯棒性得到增強(qiáng)。

文中采用自適應(yīng)權(quán)重的方法進(jìn)行Census變換，首先為鄰域的每個(gè)像素自適應(yīng)地分配一個(gè)權(quán)重，然后用權(quán)重作差，用絕對(duì)值差和(SAD)作為新的匹配代價(jià)。具體的實(shí)現(xiàn)過(guò)程如下：

(3)

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

(4)

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

1.3 匹配代價(jià)聚合

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

(5)

式中：W=2s+1；s為匹配窗口的半徑；xl=xr+d。最后采用局部?jī)?yōu)化算法WTA計(jì)算出代價(jià)D的最小值，此時(shí)對(duì)應(yīng)的匹配點(diǎn)為最佳匹配，同時(shí)獲得初始視差圖。

2 視差的提精

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

首先，通過(guò)左右一致性校驗(yàn)檢測(cè)出這些異常值。例如，左視差圖DL中的一點(diǎn)p，與右圖中的對(duì)應(yīng)點(diǎn)作差比較，表達(dá)式如下

(6)

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

異常值包括誤匹配點(diǎn)和遮擋點(diǎn)，誤匹配點(diǎn)就是由于某種原因錯(cuò)誤匹配的點(diǎn)，它們與對(duì)應(yīng)的極線有交點(diǎn)；而遮擋點(diǎn)只在一幅圖像中出現(xiàn)，它們與對(duì)應(yīng)極線沒(méi)有交點(diǎn)[9]。這里對(duì)不同區(qū)域采用不同的處理，對(duì)于封閉區(qū)域用異常值周?chē)徑目尚诺囊暡钪祦?lái)替代；對(duì)于深度不連續(xù)區(qū)域，首先檢測(cè)出視差圖的邊緣，在異常值的兩邊鄰近選出兩個(gè)點(diǎn)p1和p2，哪一個(gè)點(diǎn)的匹配代價(jià)更小就用哪個(gè)點(diǎn)對(duì)應(yīng)的視差值來(lái)替代異常值。以上處理方法簡(jiǎn)單有效，減少了誤匹配率。

其次，本文用基于二次多項(xiàng)式差值的亞像素求精方法[12]減少了由視差離散造成的誤匹配。對(duì)于像素點(diǎn)p，經(jīng)過(guò)差值后得到的視差為d*，公式如下

(7)

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

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

圖3 視差提精前后對(duì)比圖

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

圖4為本文算法的整個(gè)流程圖，首先對(duì)Census變換進(jìn)行改進(jìn)，用鄰域像素的中值來(lái)替換中心像素，再進(jìn)行自適應(yīng)加權(quán)，然后進(jìn)行變換計(jì)算匹配代價(jià)，再通過(guò)WTA的優(yōu)化策略得到代價(jià)和的最小值，從而得到左右視圖的初始視差，最后經(jīng)過(guò)視差提精得到最終視差圖。

圖4 本文算法流程圖

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

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

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

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

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

表1 匹配結(jié)果評(píng)估表(誤匹配像素比的比較) %

圖7是本文算法對(duì)Tsukuba，Venus，Teddy，Cones四幅圖像進(jìn)行匹配得到的視差結(jié)果圖。圖7a為分別為四幅圖像灰度圖，圖7b為真實(shí)視差圖，圖7c為本文最終視差圖，圖7d為匹配錯(cuò)誤的點(diǎn)圖，其中黑色和白色區(qū)域?yàn)楫惓Ｖ迭c(diǎn)。

圖7 本實(shí)驗(yàn)結(jié)果對(duì)比圖

為了進(jìn)一步驗(yàn)證算法的實(shí)用性，對(duì)真實(shí)場(chǎng)景的圖像進(jìn)行立體匹配，實(shí)驗(yàn)結(jié)果如圖8所示。從圖中可以看出，本文算法可以很明顯地得到各個(gè)物體目標(biāo)，適用于幅度失真的真實(shí)場(chǎng)景中。

圖8 真實(shí)場(chǎng)景結(jié)果圖

表2為本文方法和傳統(tǒng)方法的運(yùn)行時(shí)間對(duì)比結(jié)果。本實(shí)驗(yàn)環(huán)境為Intel Core2 2 GHz CPU，2 Gbyte內(nèi)存，MATLAB7.1。Census變換窗口為5×5，支持窗口為9×9，γc=16。

表2 實(shí)際運(yùn)行時(shí)間 ms

從運(yùn)行時(shí)間來(lái)看，本文算法時(shí)間比傳統(tǒng)方法時(shí)間要長(zhǎng)，這與理論是相吻合的，兩次自適應(yīng)權(quán)重的加入使計(jì)算復(fù)雜度增加，導(dǎo)致了時(shí)間的加長(zhǎng)?？紤]到本文沒(méi)有對(duì)程序進(jìn)行優(yōu)化，可以對(duì)程序代碼進(jìn)一步的優(yōu)化提高運(yùn)行的速度；另外，本文算法的運(yùn)算大部分都是加減，有少量的乘除，可以通過(guò)硬件進(jìn)行并行加速，提高算法的效率。因此，本文在時(shí)間上可以有很大提升。

4 結(jié)論

本文提出一種基于改進(jìn)Census變換的自適應(yīng)權(quán)重局部立體匹配算法，用變換窗口鄰域像素的中值代替中心像素灰度值，增強(qiáng)了變換時(shí)的穩(wěn)健性；變換時(shí)用自適應(yīng)權(quán)重的方法給窗口每一個(gè)鄰域像素分配權(quán)重，增加了像素間的像素信息，提高了匹配的準(zhǔn)確性；在代價(jià)聚合時(shí)再一次用自適應(yīng)權(quán)重求得匹配代價(jià)和，進(jìn)一步提高匹配精度；最后通過(guò)視差提精得到稠密的視差圖，結(jié)果表明，本文優(yōu)于傳統(tǒng)的Census變換算法以及很多當(dāng)前優(yōu)秀的匹配算法。今后主要研究通過(guò)對(duì)FPGA設(shè)計(jì)合理的流水線，實(shí)現(xiàn)在時(shí)間上的加速，從而使算法更具有實(shí)時(shí)性。

[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，F(xiàn)RANCHETTI 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] 武翠芳，王永芳，劉靜，等.一種改進(jìn)的基于BP的立體匹配算法[J]，電視技術(shù)，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— )，教授，博士，主要研究方向?yàn)閳D像處理；

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

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

責(zé)任編輯：時(shí) 雯

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

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

河北省衛(wèi)生廳科研基金項(xiàng)目(20120395)；河北省教育廳科學(xué)技術(shù)研究重點(diǎn)項(xiàng)目(ZD20131086)；河北大學(xué)中西部高校提升綜合實(shí)力工程項(xiàng)目

TP391

A

10.16280/j.videoe.2015.11.002

2014-08-11