代價(jià)可變的S-census變換算法

陳蘇婷，吳月路，張艷艷

(1.南京信息工程大學(xué) 江蘇省氣象探測(cè)與信息處理重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210044；2.南京信息工程大學(xué) 江蘇省大氣環(huán)境與裝備技術(shù)協(xié)同創(chuàng)新中心，江蘇 南京 210044)

0 引 言

立體匹配算法主要有局部的和全局的兩大類匹配算法[1]。全局算法通過能量函數(shù)最小化獲得匹配結(jié)果，精度較高，效率較低。局部算法利用窗口內(nèi)的鄰域信息來進(jìn)行單像素的匹配，速度快，容易實(shí)現(xiàn)，但局部算法存在支持窗口的大小和合適的匹配代價(jià)選取等問題[2]。局部匹配算法對(duì)于理想圖像能夠獲得較高精度的匹配結(jié)果，但對(duì)幅度失真非常敏感，難以用于真實(shí)場(chǎng)景圖像的匹配。而基于census變換的匹配算法，在幅度失真方面具有較強(qiáng)的魯棒性，適用于真實(shí)場(chǎng)景圖像的立體匹配，但精度不高[3]。

針對(duì)上述基于census變換匹配算法的匹配精度不高等問題[4]，本文另辟蹊徑，從改進(jìn)代價(jià)計(jì)算角度以及減弱窗口變換過分依賴中心像素灰度的角度，提出一種基于可變權(quán)重代價(jià)計(jì)算與S-census變換(variable support-weight S-census transform，VSC)立體匹配算法。解決了單一匹配代價(jià)[5]計(jì)算帶來的匹配誤差高、窗口變換過度依賴中心像素灰度等問題。同時(shí)，算法在深度不連續(xù)區(qū)域也能夠得到比較精準(zhǔn)的視差圖。最后，實(shí)驗(yàn)結(jié)果驗(yàn)證了算法的有效性和實(shí)用性。

1 VSC算法的提出

局部匹配算法的核心就是采用待匹配像素周圍的信息進(jìn)行計(jì)算[6]。主要有區(qū)域匹配、特征匹配、相位匹配3大類。局部區(qū)域的非參數(shù)census變換立體匹配算法的實(shí)現(xiàn)主要步驟[7]是：首先對(duì)輸入的左右圖像進(jìn)行census變換，對(duì)變換后的左右圖像計(jì)算漢明距；其次進(jìn)行非局部代價(jià)聚合；最后采用WTA(winner-take-all)策略[8]進(jìn)行視差計(jì)算，得到最終的視差圖。

非參數(shù)census變換匹配算法，雖然能改善圖像受噪聲干擾時(shí)的匹配效果，主要有以下兩方面的不足：①未利用鄰域像素的灰度信息，變換結(jié)果未考慮鄰域像素間的比重關(guān)系。②匹配代價(jià)計(jì)算單一，對(duì)異常點(diǎn)辨識(shí)度不夠，易造成誤匹配。因此，本文針對(duì)局部的非參數(shù)census變換的立體匹配算法的以上兩點(diǎn)缺陷，提出了VSC立體匹配算法，算法流程如圖1所示。

圖1 VSC算法流程

如圖1所示，提出可變代價(jià)的S-census變換(variable cost S-census transform，VSC)算法。基本原理如下：首先在對(duì)周圍鄰域像素信息獲取方面，利用S-census變換替代原census變換，鄰域像素信息得到充分利用，提高算法匹配精度；其次，可變權(quán)重代價(jià)計(jì)算方法，能夠辨識(shí)異常點(diǎn)，減少誤匹配。最后，在基于非局部代價(jià)聚合獲取初始視差圖后，利用均值偏移的視差提精方法，處理不可信區(qū)域，進(jìn)一步提高視差精度，獲得最終視差圖。

在選取匹配窗口問題上，本文利用ORB[9]特征提取算法并配對(duì)，以匹配點(diǎn)為中心建立3×3大小的匹配窗口，ORB算法參考文獻(xiàn)[9]所述。在獲取匹配窗口后，本文算法分3個(gè)部分實(shí)現(xiàn)：S-census變換對(duì)窗口像素處理，采用可變權(quán)重匹配代價(jià)方法計(jì)算代價(jià)、獲得單像素視差，代價(jià)聚合法獲得初始視差圖，對(duì)初始視差圖進(jìn)一步視差優(yōu)化獲得最終視差圖。具體實(shí)現(xiàn)方案如下文。

2 S-census變換方法的提出

2.1 傳統(tǒng)Census變換

Census變換是局部的非參數(shù)變換，過程簡(jiǎn)單。對(duì)圖像I中的像素p進(jìn)行census變換，首先，選取窗口W(p)，p為中心。把窗口中各像素Q與p比較灰度值。假如Q處大于p處的，那么Q處變換結(jié)果β(Q,p)為0，否則為如式(1)所示

(1)

p點(diǎn)的census變換可以表示為

(2)

式中：?是連接相繼兩個(gè)比較結(jié)果，W′(p)是W(p)中不包含p的點(diǎn)集。根據(jù)以上所述方法可得二進(jìn)制串。

2.2 S-census變換方法

本文提出一種基于星型鄰域的S-census變換方法來解決傳統(tǒng)census變換的不足，S-census變換方法能夠消除中心灰度變化的影響、有效地處理諸如角點(diǎn)等特征。

S-census變換算法步驟如下：

(1)以(u,v)為中心的窗口，劃分窗口內(nèi)以過(u,v)為點(diǎn)的各條線段。線段劃分方式如圖2所示。

圖2 星型鄰域線段劃分

(2)計(jì)算各條線段上的灰度均勻度w

(3)

(3)取最小分布均勻度w，w對(duì)應(yīng)的區(qū)域灰度均值替換中心點(diǎn)(u,v)的灰度值。

(4)如2.1節(jié)所示方法進(jìn)行census變換。

這里，過點(diǎn)(u,v)的所有線段組合成star型，這也是本文所提的S-census(star-census)變換的由來。

線段W1,W2,W3,W4組成星狀，這也是本文所提星型鄰域的由來。根據(jù)式(2)可以得到如圖3所示各星型鄰域的灰度分布均勻度分別為W1=11 705，W2=355，W3=1016，W4=2774。因?yàn)閃2最小，所以取其對(duì)應(yīng)區(qū)域的灰度均值124作為中心點(diǎn)(u,v)灰度值，替換原灰度值127。

傳統(tǒng)的census變換如圖3所示，得到的二進(jìn)制碼串為110100110。當(dāng)窗口中心像素灰度在I′∈(110,125]范圍變化時(shí)，采用如圖3所示的傳統(tǒng)census變換得到的二進(jìn)制串由110100110變?yōu)?10100100。

圖3 傳統(tǒng)Census變換

如圖4所示為S-census變換圖，得到的二進(jìn)制碼串為110100100。當(dāng)窗口中心像素的灰度值變換在I′∈(110,125]范圍變化時(shí)，經(jīng)S-census變換后，二進(jìn)制串仍然是110100100，未有任何改變。由此可見，在抗干擾能力方面得到了有效地增強(qiáng)?？s小census變換過度依賴中心點(diǎn)亮度的情形，匹配代價(jià)計(jì)算精確度方面有了很好的提高。

圖4 S-census變換

3 可變權(quán)重匹配代價(jià)方法的提出

3.1 傳統(tǒng)基于漢明距的匹配代價(jià)計(jì)算

建立在S-census變換的基礎(chǔ)上，為了實(shí)現(xiàn)立體匹配，需進(jìn)行匹配代價(jià)計(jì)算與代價(jià)累積。而傳統(tǒng)基于census變換在匹配代價(jià)計(jì)算與代價(jià)累積上，對(duì)census變換后，對(duì)應(yīng)點(diǎn)間進(jìn)行漢明距計(jì)算[10]，統(tǒng)計(jì)對(duì)應(yīng)像素點(diǎn)的距離和來確定最佳匹配點(diǎn)。

代價(jià)計(jì)算公式如下

C(u,v,f)=Hammin(w1(u,v),w2(u-f,v))

(4)

式中：w1(u,v)代表左窗口S-census變換結(jié)果，w2(u-f,v)表示右邊窗口S-census變換結(jié)果，f表示窗口對(duì)應(yīng)點(diǎn)的視差距離。

代價(jià)累積公式如下

(5)

式中：m和n分別代表匹配窗口的寬度和高度，在設(shè)定視差f范圍內(nèi)，CSum最小時(shí)對(duì)應(yīng)的標(biāo)號(hào)即為該點(diǎn)的視差。

3.2 可變權(quán)重匹配代價(jià)計(jì)算

使用傳統(tǒng)的代價(jià)計(jì)算方法，其作為相似性測(cè)度方法，在深度間斷跳躍等區(qū)域誤匹配率高。原因是這種代價(jià)計(jì)算相似性測(cè)度過于單一，對(duì)異常值的辨識(shí)度不夠。因此，本文提出了基于漢明距的可變權(quán)重匹配代價(jià)計(jì)算方法。

基于權(quán)重可變漢明距的代價(jià)計(jì)算步驟如下：

(1)計(jì)算窗口大小h,h=m×n。

其中m和n分別代表匹配窗口的寬度和高度。h即表示經(jīng)窗口變換后碼的長(zhǎng)度。

(2)對(duì)變換的碼值依次賦予權(quán)重，權(quán)重因子δk

(6)

式中：k表示對(duì)變換碼編號(hào)，從左到右依次為1到h。

(3)可變權(quán)重代價(jià)計(jì)算。

代價(jià)計(jì)算公式如下

(7)

式中：w1k(u,v)表示左窗口對(duì)應(yīng)編號(hào)k的碼，w2k(u-f,v)表示右窗口對(duì)應(yīng)編號(hào)k的碼。

4 代價(jià)聚合與視差優(yōu)化

基于可變權(quán)重漢明距代價(jià)計(jì)算獲取單像素視差的基礎(chǔ)上，需進(jìn)行代價(jià)聚合以獲取視差圖，Yang提出了一種非局部代價(jià)聚合方法，此種方法復(fù)雜度比較低，能夠自適應(yīng)的聚合匹配代價(jià)。本文使用這種代價(jià)聚合方法。具體實(shí)現(xiàn)方法如參考文獻(xiàn)[9]所述。

為進(jìn)一步提高視差的區(qū)分性，采用一種均值偏移的視差提精方法進(jìn)行視差優(yōu)化，具體實(shí)現(xiàn)步驟如下：

(1)對(duì)于不可信的初始視差，用左右一致性的方法來進(jìn)行檢測(cè)。經(jīng)過左右一致性方法[11]檢測(cè)后，參考圖像視差估計(jì)主要分為高置信度集Dhc和低置信度集Dlc。

(2)視差圖采用均值偏移方法分割成子區(qū)域，每個(gè)子區(qū)域記為Si。建立可信視差估計(jì)統(tǒng)計(jì)直方圖Si，統(tǒng)計(jì)不同視差出現(xiàn)次數(shù)。

(8)

5 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證VSC算法的有效性，在MATLAB和VS2010+opencv軟件平臺(tái)上進(jìn)行了實(shí)驗(yàn)驗(yàn)證。采用Middlebury網(wǎng)站的4幅標(biāo)準(zhǔn)圖Cones圖、Teddy圖、Tsukuba圖、Venus圖等進(jìn)行了測(cè)試分析。實(shí)驗(yàn)分別從3個(gè)方面對(duì)VSC算法進(jìn)行驗(yàn)證。①改進(jìn)前后變換匹配率的比較驗(yàn)證；②代價(jià)區(qū)分度驗(yàn)證；③算法可行性驗(yàn)證。詳細(xì)內(nèi)容如下幾節(jié)所述。

5.1 S-census變換與census變換匹配率的比較

實(shí)驗(yàn)通過對(duì)兩種變換支持窗口大小的改變，來比較不同窗口下的匹配率。沒有進(jìn)行代價(jià)聚合，這樣能夠驗(yàn)證兩種變換對(duì)匹配的影響。支持窗口大小從3*3到15*15。選取標(biāo)準(zhǔn)測(cè)試圖像Cones圖、Teddy圖、Tsukuba圖、Venus圖。結(jié)果如圖5所示。

從實(shí)驗(yàn)結(jié)果圖5可以看出，改進(jìn)后的S-census變換匹配率明顯好于census變換匹配率。平均4個(gè)實(shí)驗(yàn)結(jié)果圖，匹配率大概提高了15%左右。說明S-census變換能夠有效地削弱變換過度依賴中心像素灰度的情況，驗(yàn)證了S-census變換的有效性。

圖5 S-census變換與census變換匹配率對(duì)比

5.2 代價(jià)區(qū)分度驗(yàn)證

傳統(tǒng)census變換的相似性測(cè)量標(biāo)準(zhǔn)是計(jì)算Hamming距，為驗(yàn)證本文所提可變權(quán)重代價(jià)計(jì)算的有效性，實(shí)驗(yàn)采用抽樣匹配點(diǎn)來進(jìn)行驗(yàn)證兩種代價(jià)計(jì)算區(qū)分度，即算法正確匹配點(diǎn)率，即(1-誤匹配點(diǎn)率)×100%。誤點(diǎn)率計(jì)算公式如下

(9)

δthresh為視差容差，N為像素總數(shù)，dc(x,y)為測(cè)試視差，dt(x,y)為真實(shí)視差。如圖6(a)所示對(duì)Teddy測(cè)試圖選取抽樣點(diǎn)，以保證其它條件一致的情況下，實(shí)驗(yàn)選取不同的視差值來驗(yàn)證改進(jìn)前后代價(jià)計(jì)算的區(qū)分度。實(shí)驗(yàn)結(jié)果如圖6(b)所示。

由圖6(b)，當(dāng)選取視差值遞增時(shí)，改進(jìn)后代價(jià)計(jì)算方法如三角形線條顯示，算法的區(qū)分度明顯高于星形線條所表示的傳統(tǒng)代價(jià)計(jì)算方法的區(qū)分度，在視差選取值為6時(shí)，前后代價(jià)計(jì)算區(qū)分度相差不大，這是因?yàn)榇颂帉?shí)驗(yàn)預(yù)設(shè)真實(shí)視差值為6，不影響整體算法區(qū)分度的驗(yàn)證。實(shí)驗(yàn)結(jié)果表明改進(jìn)后的代價(jià)計(jì)算方法區(qū)分度更高。

圖6 匹配點(diǎn)區(qū)分度對(duì)比

5.3 算法可行性驗(yàn)證

最后驗(yàn)證算法可行性，對(duì)比實(shí)驗(yàn)分析了本文算法與其它幾種匹配算法的誤匹配率，并對(duì)Middlebury平臺(tái)的4幅標(biāo)準(zhǔn)圖進(jìn)行實(shí)驗(yàn)，將實(shí)驗(yàn)視差圖與標(biāo)準(zhǔn)視差圖對(duì)比，充分說明本文算法的可行性。

表1是不同算法誤匹配百分比統(tǒng)計(jì)實(shí)驗(yàn)結(jié)果，其中nonocc、disc、all表示非遮擋區(qū)域、視差不連續(xù)區(qū)域、所有區(qū)域。誤匹配像素百分比E為

(10)

式中：dc(x,y)是點(diǎn)(x,y)在改進(jìn)算法得到視差圖中的視差值，dt(x,y)是真實(shí)視差圖中的視差值，M為圖像大小，誤差限δd=1，即當(dāng)匹配結(jié)果與真實(shí)視差圖相差1 pixel以上時(shí)，認(rèn)為該點(diǎn)是誤匹配點(diǎn)。幾種不同算法實(shí)驗(yàn)結(jié)果見表1。

表1 不同算法誤匹配百分比/%

由表1可知，CostFilter均誤匹配比率是5.54%，Assw-Grad均誤匹配比率是6.1%，AdpDP均誤匹配率是9.82%。VariableCross均誤匹配率是7.60%，本文VSC算法均誤匹配率是5.83%。從以上實(shí)驗(yàn)數(shù)據(jù)整體上來看，本文算法優(yōu)于Assw-Grad、AdpDP、VariableCross等算法。其中CostFilter是當(dāng)前最好的局部匹配算法。

驗(yàn)證算法的有效性，實(shí)驗(yàn)對(duì)Middlebury網(wǎng)站的4幅標(biāo)準(zhǔn)圖像進(jìn)行了測(cè)試，標(biāo)準(zhǔn)測(cè)試圖像從左到右依次是Cones圖、Teddy圖、Tsukuba圖、Venus圖。分辨率為450 pixel×375 pixel、450 pixel×375 pixel、384 pixel×288 pixel、434 pixel×383 pixel。實(shí)驗(yàn)時(shí)，4組圖像的視差搜索范圍為0-60 pixel、0-60 pixel、0-16 pixel、0-20 pixel。實(shí)驗(yàn)結(jié)果如圖7所示。

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

如圖7所示，VSC算法結(jié)果與真實(shí)視差圖的比較，本文VSC算法得到的視差圖整體比較光滑，在視差不連續(xù)區(qū)域和平坦區(qū)域可以取得較好的效果。

實(shí)驗(yàn)總結(jié)：實(shí)驗(yàn)分別從3個(gè)方面對(duì)VSC算法進(jìn)行驗(yàn)證：①改進(jìn)前后變換匹配率的比較驗(yàn)證；②算法區(qū)分度驗(yàn)證；③算法可行性驗(yàn)證。綜上3個(gè)指標(biāo)實(shí)驗(yàn)驗(yàn)證，充分說明了本文所提VSC算法具有可行性。

6 結(jié)束語(yǔ)

本文提出的VSC算法，克服了傳統(tǒng)census變換算法過度依賴中心像素灰度值的缺陷，解決了現(xiàn)有算法難以從圖像中獲取高精度視差的問題。在立體匹配時(shí)，通過加權(quán)區(qū)域海明距離均值和標(biāo)準(zhǔn)差信息來提高匹配的精度。采用非局部代價(jià)聚合方式，提高視差的可區(qū)分性，對(duì)于獲得的初始視差，進(jìn)一步采用基于均值偏移的視差提精方法，有效的處理了不可信視差區(qū)域，提高了視差精度。提出的VSC算法在匹配點(diǎn)權(quán)值區(qū)分度方面得到顯著提高。S-census變換與census變換相比，匹配率提高了約15%。改進(jìn)后的代價(jià)計(jì)算方法在視差匹配時(shí)區(qū)分度更高。與當(dāng)前優(yōu)秀的局部匹配算法CostFilter匹配精度相當(dāng)，在深度不連續(xù)區(qū)域也能夠得到比較精準(zhǔn)的視差圖。能夠?qū)崿F(xiàn)高精度的立體匹配。將VSC算法應(yīng)用于機(jī)器人自主導(dǎo)航地圖構(gòu)建中將是以后的主要研究方向與研究重點(diǎn)。

[1]ZHU Shiping,YAN Lina.Stereo matching algorithm based on improved Census transform and dynamic programming[J].Acta Optical Sinica,2016,36(4):208-216(in Chinese).[祝世平,閆利那.基于改進(jìn)Census變換和動(dòng)態(tài)規(guī)劃的立體匹配算法[J].光學(xué)學(xué)報(bào),2016,36(4):208-216.]

[2]ZHU Shiping,LI Zheng.Based on the improved gradient and stereo matching algorithm of adaptive window[J].Acta Optical Sinica,2015,35(1):115-123(in Chinese).[祝世平,李政.基于改進(jìn)梯度和自適應(yīng)窗口的立體匹配算法[J].光學(xué)學(xué)報(bào),2015,35(1):115-123.]

[3]MEN Yubo,MA Ning,ZHANG Guoyin,et al.Nonparametric transform and improve dynamic programming stereo matching algorithm[J].Journal of Harbin Institute of Technology,2015,47(3):60-65(in Chinese).[門宇博,馬寧,張國(guó)印,等.非參數(shù)變換和改進(jìn)動(dòng)態(tài)規(guī)劃的立體匹配算法[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào),2015,47(3):60-65.]

[4]De-Maeztu L,Villanueva A,Cabeza R.Stereo matching using gradient similarity and locally adaptive support-weight[J].Pattern Recognition Letters,2011,32(13):1643-1651.

[5]Zhan Y,Gu Y,Huang K,et al.Accurate image-guided ste-reo matching with efficient matching cost and disparity refinement[J].IEEE Transactions on Circuits & Systems for Video Technology,2016,26(9):1632-1645.

[6]Fan X,Wang X,Xiao Y.A shape-based stereo matching algorithm for binocular vision[C]//International Conference on Security,2014:70-74.

[7]Xu L,Au OC,Sun W,et al.Stereo matching with optimal local adaptive radiometric compensation[J].IEEE Signal Processing Letters,2015,22(2):131-135.

[8]Chang X,Zhou Z,Wang L,et al.Real-time accurate stereo matching using modified two-pass aggregation and winner-take-all guided dynamic programming[C]//International Confe-rence on 3d Imaging,2011:73-79.

[9]Rublee E,Rabaud V,Konolige K,et al.ORB:An efficient alternative to SIFT or SURF[C]//IEEE International Confe-rence on Computer Vision,2012:2564-2571.

[10]Zhang K,Fang Y,Min D,et al.Cross-scale cost aggregation for stereo matching[C]//IEEE Conference on Computer Vision & Pattern Recognition,2014:1590-1597.

[11]Lee Z,Juang J,Nguyen T.Local disparity estimation with three-mode cross census and advanced support weight[J].IEEE Tran-sactions on Multimedia,2013,15(8):1855-1864.

[12]Salehian B,Raie A,Fotouhi A,et al.Efficient interscanline consistency enforcing method for dynamic programming-based dense stereo matching algorithms[J].Journal of Electronic Imaging,2013,22(4):043028.