基于跨尺度隨機(jī)游走的立體匹配算法

李鏘 段子陽 張一帆 朱程濤

(1．天津大學(xué) 微電子學(xué)院，天津 300072；2.中國(guó)科學(xué)技術(shù)大學(xué) 中國(guó)科學(xué)院空間信息處理與應(yīng)用系統(tǒng)技術(shù)重點(diǎn)實(shí)驗(yàn)室(聯(lián)合)，安徽 合肥 230027)

立體視覺是從兩個(gè)或多個(gè)視點(diǎn)觀察同一景物，以獲取在不同視角下的感知圖像；通過三角測(cè)量原理計(jì)算圖像像素點(diǎn)間的視差來獲取景物的三維信息[1]?，F(xiàn)階段，該技術(shù)已廣泛應(yīng)用于機(jī)器人導(dǎo)航、無人駕駛、虛擬現(xiàn)實(shí)、三維重建等領(lǐng)域[2]。立體視覺技術(shù)主要涉及攝像機(jī)標(biāo)定、圖像預(yù)處理、立體匹配、三維重建等步驟。立體匹配是其中最重要也是最困難的步驟，其主要目的是通過相應(yīng)的算法獲取參考圖像與目標(biāo)圖像之間對(duì)應(yīng)匹配點(diǎn)間的關(guān)系，生成相應(yīng)的視差圖，依據(jù)視差圖信息及三角測(cè)量原理即可得到場(chǎng)景的深度信息。

Scharstein等[1]將立體匹配算法分為4個(gè)步驟：匹配代價(jià)計(jì)算、代價(jià)聚合、視差計(jì)算、視差求精。立體匹配算法通常被分為局部算法和全局算法。局部算法通常采用基于窗口濾波的方式實(shí)現(xiàn)匹配，Yoon等[3]提出一種自適應(yīng)支持權(quán)重算法，該算法根據(jù)窗口內(nèi)每個(gè)像素與中心像素的顏色相似性、距離相似性進(jìn)行權(quán)重分配，其本質(zhì)是一種雙邊濾波的過程，可以有效保護(hù)邊緣深度信息，但運(yùn)算復(fù)雜度較大；Hosni等[4]提出用引導(dǎo)濾波代替雙邊濾波的局部算法，該算法在降低算法復(fù)雜度的同時(shí)提升了匹配精度；Yang等[5]提出一種半局部代價(jià)聚合方法，將整幅圖像作為核函數(shù)窗口，利用最小生成樹進(jìn)行代價(jià)匹配；Mei等[6]先對(duì)圖像進(jìn)行分割，后采用半局部方法對(duì)每個(gè)分割塊求取子樹，然后根據(jù)貪心算法，將各個(gè)分割對(duì)應(yīng)的子樹進(jìn)行合并；Hamzah等[7]提出迭代引導(dǎo)濾波用于代價(jià)聚合過程，以保持和改善圖像邊緣信息；Williem等[8]使用深度學(xué)習(xí)來執(zhí)行自引導(dǎo)濾波過程，不需要任何引導(dǎo)圖像進(jìn)行監(jiān)督。局部算法具有計(jì)算簡(jiǎn)單、速度快、能進(jìn)行圖像實(shí)時(shí)處理的優(yōu)點(diǎn)，但由于缺乏對(duì)視差關(guān)系的合理約束導(dǎo)致算法在低紋理區(qū)域、遮擋區(qū)域的匹配精度不高。

全局算法通過在能量方程中引入視差約束懲罰項(xiàng)，能有效處理低紋理區(qū)域及遮擋區(qū)域的匹配問題。目前常用的全局算法有圖割算法(Graph Cut，GC)[9]、置信傳播(Belief Propagation，BP)[10]、動(dòng)態(tài)規(guī)劃(Dynamic Programming，DP)[11]等。基于圖割和置信傳播的立體匹配算法需要大量的計(jì)算資源，計(jì)算復(fù)雜度高，實(shí)時(shí)性較差。Shen等[12]首先將隨機(jī)游走算法(RW)應(yīng)用于立體匹配中，該算法能夠產(chǎn)生精確的全局函數(shù)最優(yōu)解；Jin[13]等提出了改進(jìn)的重啟動(dòng)與隨機(jī)游走算法(ARW)，該算法能在相對(duì)較低的計(jì)算復(fù)雜度下得到高精度的匹配結(jié)果。

傳統(tǒng)的立體匹配算法大多是建立在單尺度模式下，Zhang等[14]提出跨尺度的局部算法，該算法模擬人眼視覺系統(tǒng)采取由粗到細(xì)(Coarse to Fine)的策略融合多尺度圖像信息用于匹配，實(shí)現(xiàn)了立體匹配算法由單尺度向多尺度的轉(zhuǎn)變，提升了立體匹配的精度；Liu等[15]提出Census變換與多尺度空間結(jié)合的立體匹配算法，提高了在弱紋理區(qū)域和視差不連續(xù)區(qū)域的匹配精度。

傳統(tǒng)的跨尺度算法未能有效考慮鄰近點(diǎn)之間的視差約束關(guān)系，致使算法在低紋理及遮擋區(qū)域的匹配精度有限。為了提升上述區(qū)域的精度，本研究充分結(jié)合多尺度以及全局算法的優(yōu)勢(shì)，首先用中心對(duì)稱的Census變換和梯度信息相結(jié)合來計(jì)算多尺度下的匹配代價(jià)；然后利用超像素分割[16]分別對(duì)各尺度下的圖像進(jìn)行分割，并在分割區(qū)域內(nèi)進(jìn)行匹配代價(jià)聚合，再利用重啟動(dòng)與隨機(jī)游走算法進(jìn)行全局上的優(yōu)化；最后，利用正則化約束進(jìn)行多尺度匹配代價(jià)融合，以實(shí)現(xiàn)高精度的匹配效果。

1 算法描述

文中算法流程如圖1所示，步驟如下：

步驟1 對(duì)立體匹配圖像對(duì)進(jìn)行高斯下采樣分解，得到不同尺寸的圖像對(duì)，低分辨率分解層上對(duì)應(yīng)的最大視差值也相應(yīng)減小；

步驟2 在各個(gè)分解層上分別進(jìn)行匹配代價(jià)計(jì)算和代價(jià)聚合，得到各個(gè)尺度下的匹配代價(jià)卷，提出將中心對(duì)稱的Census變換與梯度信息相結(jié)合計(jì)算匹配代價(jià)，然后利用超像素分割進(jìn)行快速初始聚合，再使用重啟動(dòng)與隨機(jī)游走算法對(duì)其進(jìn)行全局上的優(yōu)化；

步驟3 對(duì)各個(gè)尺度分辨率下的匹配代價(jià)卷進(jìn)行跨尺度融合，以實(shí)現(xiàn)匹配代價(jià)的有效融合更新；

步驟4 在最終的匹配代價(jià)卷上先采用引導(dǎo)濾波再次代價(jià)聚合，再使用WTA算法計(jì)算得出初始視差圖；

步驟5 對(duì)初始視差圖采用權(quán)重中值濾波對(duì)視差進(jìn)行精細(xì)化，得到最終的視差圖。

圖1 本文算法流程圖

1.1 計(jì)算匹配代價(jià)

傳統(tǒng)Census變換是通過選取中心像素的灰度值作為參考，將其與窗口中各像素的灰度值進(jìn)行比較，并用0和1表示大小關(guān)系。傳統(tǒng)Census變換[17]的公式如下：

(1)

H(I(u，v)，I(u+i，v+j))=

(2)

傳統(tǒng)Census變換能夠在一定程度上降低噪聲帶來的干擾，但仍存在一定的局限性：變換結(jié)果完全依賴于中心點(diǎn)的灰度值，一旦中心像素點(diǎn)受到外界因素的干擾，Census編碼結(jié)果會(huì)發(fā)生巨大變化，導(dǎo)致誤匹配，降低匹配精度；其次，由于窗口內(nèi)像素都要與中心像素進(jìn)行比較再生成二進(jìn)制碼流形式，算法復(fù)雜度較高。故文中引入了中心對(duì)稱的Census變換[18]，只有中心對(duì)稱的像素點(diǎn)被比較，可以有效降低因外界干擾引起的變化，增強(qiáng)其抗噪聲的魯棒性；同時(shí)可以降低Census變換的計(jì)算復(fù)雜度。中心對(duì)稱的Census變換[18]的公式如下：

Tl(u，v)=?H(I(u-i，y-j)，I(u+i，v+j))

(3)

Tr(u，v)=?H(I(u-i，y-j)，I(u+i，v+j))

(4)

其中，坐標(biāo)(u-i，y-j)和(u+i，y+j)表示中心對(duì)稱的坐標(biāo)點(diǎn)，通過變換窗口可被轉(zhuǎn)化為二值向量。

于是基于兩個(gè)二值向量的漢明距離，可以得出參考圖像和目標(biāo)圖像兩個(gè)窗口之間的匹配代價(jià)：

Cr(u，v，d)=Ham(Tl(u，v)，Tr(u+d，v))

(5)

Cl(u，v，d)=Ham(Tl(u，v)，Tr(u-d，v))

(6)

式中，Cl(u，v，d)表示以左圖作為參考圖像，在像素點(diǎn)(u，v)、水平視差為d時(shí)的匹配代價(jià)；同理可知Cr(u，v，d)。

考慮到Census變換在重復(fù)和相似紋理區(qū)域可能會(huì)造成匹配模糊，為了解決這個(gè)問題，文中引入梯度信息來計(jì)算匹配代價(jià)，加強(qiáng)對(duì)圖像邊緣信息的獲取，增強(qiáng)圖像邊界的魯棒性。梯度圖像匹配定義為

(7)

(8)

最后，通過融合中心對(duì)稱的Census變換和梯度圖像匹配可得最終的匹配代價(jià)：

(9)

1.2 代價(jià)聚合

文中首先應(yīng)用超像素分割算法進(jìn)行代價(jià)聚合，一方面這種基于分割區(qū)域的聚合方法對(duì)噪聲變化更具魯棒性；另一方面，由于圖像計(jì)算尺寸的減小，運(yùn)算時(shí)間能夠大幅降低，同時(shí)也減少了對(duì)硬件內(nèi)存的需要。文中使用線性迭代聚類算法(SLIC)[16]進(jìn)行超像素分割，其公式定義為

(10)

其中：ns表示屬于超像素區(qū)域s中像素的數(shù)量；Fr(s，d)表示以右圖像為參考圖像的聚合匹配代價(jià)，同樣對(duì)左圖像進(jìn)行計(jì)算Fl(s，d)。

之后再使用改進(jìn)的重啟動(dòng)與隨機(jī)游走算法對(duì)聚合結(jié)果進(jìn)行全局優(yōu)化。該方法不僅能減少計(jì)算量，而且避免了隨機(jī)游走方法造成的視差圖過度平滑和置信傳播算法對(duì)于有環(huán)網(wǎng)絡(luò)不能收斂到最優(yōu)解的問題，可以達(dá)到理論上的最優(yōu)值[1]。隨機(jī)游走算法代價(jià)能量函數(shù)定義表示為

E(X)=μEdata(X)+Esmooth(X)

(11)

(12)

(13)

其中：式(12)中的xi和yi分別表示最終輸出的匹配代價(jià)值和初始匹配代價(jià)值，對(duì)應(yīng)于式(10)的Fr(s，d)；向量Edata(X)是向量X和向量Y之間的歐式距離的平方；wij是向量X的分量xi和向量Y的分量yi之間的連接權(quán)值；D是權(quán)值矩陣W的行元素組成的對(duì)角矩陣；N(i)屬于平滑項(xiàng)的支撐區(qū)域；μ是Edata(X)和Esmooth(X)兩者之間的調(diào)節(jié)項(xiàng)。

標(biāo)準(zhǔn)的重啟動(dòng)與隨機(jī)游走全局最優(yōu)化算法實(shí)現(xiàn)對(duì)E(X)的最優(yōu)化求解得到最優(yōu)解X，其求解過程可以轉(zhuǎn)換為如下的迭代方程：

(14)

使用與邊緣權(quán)重成比例的概率值將匹配成本傳遞到相鄰節(jié)點(diǎn)，其中邊緣權(quán)重受相鄰超像素之間的亮度相似性的影響：

(15)

全局能量函數(shù)中平滑項(xiàng)易導(dǎo)致圖像邊界視差模糊，通過添加額外的保真項(xiàng)可有效改善上述問題。此外，通過添加可見項(xiàng)可有效提升遮擋區(qū)域的匹配性能：

(16)

1.3 跨尺度融合

當(dāng)前大部分立體匹配算法都是在圖像原始分辨率尺寸上進(jìn)行處理的，在高紋理區(qū)域能取得準(zhǔn)確的視差值，但在低紋理或者重復(fù)紋理區(qū)域則效果不佳?？紤]到人眼視覺系統(tǒng)是在不同尺度上處理接收到的視覺信號(hào)，并且對(duì)細(xì)節(jié)信息非常敏感。本研究借鑒文獻(xiàn)[14]提出的多尺度聚合框架，實(shí)現(xiàn)匹配代價(jià)的有效融合，首先按照如下方式進(jìn)行各尺度下匹配代價(jià)的融合更新：

(17)

(18)

由于式(18)所得融合后的匹配代價(jià)在各尺度之間是相互獨(dú)立的，故在式(17)中加入二范數(shù)正則化項(xiàng)，以保證在多尺度下的一致性：

(19)

(20)

(21)

1.4 視差計(jì)算及求精

為了更有效突出圖像邊緣信息、增強(qiáng)紋理結(jié)構(gòu)，對(duì)多尺度融合后的匹配代價(jià)卷采用引導(dǎo)濾波[4]進(jìn)行再次代價(jià)聚合：

(22)

然后對(duì)其采用WTA(Winner- TakE-All)求解即可獲得場(chǎng)景的視差圖：

(23)

其中：d0∈{1，2，…，dmax}。

最后對(duì)所得視差圖進(jìn)行左右一致性檢測(cè)，對(duì)錯(cuò)誤像素和遮擋像素重新賦值，再進(jìn)行權(quán)重中值濾波，這一方式可以在濾除噪聲的同時(shí)，保護(hù)視差圖的邊緣信息不被模糊。

通過上述過程，可以有效提高視差圖精度，降低誤匹配率。

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

本文采用標(biāo)準(zhǔn)的Middlebury V3[20]立體匹配數(shù)據(jù)集來驗(yàn)證算法的有效性，利用MATLAB編程實(shí)現(xiàn)所提算法及相關(guān)對(duì)比算法。計(jì)算機(jī)配置為：Windows10，Inter(R)Core(TM)i5-7400，3.00 GHz主頻CPU，8 GB內(nèi)存。

為驗(yàn)證文中所提算法的有效性，本研究選取了經(jīng)典的引導(dǎo)濾波算法[4]、單尺度的ARW算法[13]、基于跨尺度的立體匹配算法[14]與文中所提算法進(jìn)行實(shí)驗(yàn)對(duì)比。圖2所示為上述各立體匹配算法所得視差圖(截選Middlebury V3[20]立體匹配數(shù)據(jù)集中的Adirondack、Piano、Playtable、Teddy及其相應(yīng)的標(biāo)準(zhǔn)視差圖)；表1所示為相應(yīng)算法于非遮擋區(qū)域(Non)以及所有區(qū)域(All)的誤匹配率，誤差閾值取1；圖3為Adirondack圖像視差匹配區(qū)域標(biāo)記圖，其中綠色區(qū)域表示遮擋區(qū)域誤匹配，紅色區(qū)域表示非遮擋區(qū)域誤匹配。

表1 不同算法的誤匹配率

Table 1 Mismatch rates of different algorithms

匹配圖像誤匹配率/%文獻(xiàn)[4]算法文獻(xiàn)[13]算法文獻(xiàn)[14]算法 本文算法 非遮擋區(qū)域所有區(qū)域非遮擋區(qū)域所有區(qū)域非遮擋區(qū)域所有區(qū)域非遮擋區(qū)域所有區(qū)域Adirondack9.7511.8110.1316.1416.0421.546.6212.01ArtL15.9125.8222.6439.7213.7521.6813.9124.35Jadeplant31.8541.8627.1543.2928.6939.4523.2738.46Motorcycle11.7215.6011.4220.1910.2613.479.4217.18MotorcycleE12.8316.6511.6620.3411.4514.698.7317.15Piano18.1921.8917.8023.3415.9921.1815.3619.98PianoL37.9140.8536.3940.9036.4437.8135.5438.31Pipes12.8533.9415.9129.5515.7428.8712.7726.17Playroom22.6131.1322.6032.8626.4735.9218.1628.77Playtable46.0248.7119.0327.1214.8923.0114.5622.34PlaytableP14.4018.1615.2723.8415.2117.5213.0521.14Recycle10.8212.8013.9619.7411.2113.689.8211.50Shelves37.4338.4038.1141.6535.6938.9936.2537.51Teddy7.8413.378.5117.828.3416.827.0612.81Vintage39.6543.3329.7434.9531.5538.4523.6928.27加權(quán)平均誤匹配率10.0425.0518.1927.4217.5423.6814.7322.23

由表1可以看出，文獻(xiàn)[13]基于單尺度的ARW算法在所有區(qū)域的加權(quán)平均誤匹配率為27.42%，而文中所提算法在所有區(qū)域的加權(quán)平均誤匹配率為22.23%。相比之下文中所提算法加權(quán)平均誤匹配率有所下降，表明采用多尺度融合的文中算法可以有效利用多尺度信息，從而提高立體匹配精度。文獻(xiàn)[14]基于跨尺度的立體匹配算法在所有區(qū)域的加權(quán)平均誤匹配率為23.68%，與文中算法相比匹配精度也較低。

由表1可知，對(duì)于Adirondack圖像的立體匹配，相比于文獻(xiàn)[13- 14]的算法，文中所提算法在非遮擋區(qū)域的誤匹配率大幅度降低，誤匹配率的降低在視差圖上的表現(xiàn)為，文中所提算法得出的視差圖整體輪廓更為清晰，圖像噪點(diǎn)較少，且邊界較為平滑。由圖3可以看出，文中所提算法紅色區(qū)域(非遮擋區(qū)域誤匹配)與其他算法相比，明顯誤匹配區(qū)域更少。針對(duì)圖2中的Playtable圖像的重復(fù)紋理區(qū)域和低紋理區(qū)域(紅色方框區(qū)域?yàn)榫哂械图y理的地毯區(qū)域，綠色方框區(qū)域代表的是低紋理和重復(fù)紋理交叉的白色椅子)，觀察文中算法與其他算法在以上兩個(gè)區(qū)域的視差圖，可以看出文中算法可以很好地建模低紋理及重復(fù)紋理區(qū)域的對(duì)應(yīng)關(guān)系。同時(shí)針對(duì)PianoL不同光照條件下的測(cè)試圖像，由表1可知，文中算法相較于其他算法在光照條件不同時(shí)，誤匹配率較低，證明文中算法對(duì)光照條件具有較好的魯棒性。

表2為各算法的運(yùn)行時(shí)間比較，文獻(xiàn)[4]采用經(jīng)典的引導(dǎo)濾波進(jìn)行立體匹配，其運(yùn)行時(shí)間最短；文中算法與基于單尺度的ARW算法[13]相比，需要在多個(gè)尺度上進(jìn)行匹配代價(jià)和代價(jià)聚合，運(yùn)行時(shí)間勢(shì)必增加。

表2 不同算法的運(yùn)行時(shí)間

(a)原始測(cè)試圖像

(b)標(biāo)準(zhǔn)視差圖

(c)文獻(xiàn)[4]視差區(qū)域標(biāo)記圖

(d)文獻(xiàn)[13]視差區(qū)域標(biāo)記圖

(e)文獻(xiàn)[14]視差區(qū)域標(biāo)記圖

(f)本文算法視差區(qū)域標(biāo)記圖

針對(duì)Teddy圖像的不同匹配代價(jià)方法視差圖如圖4所示，其中圖4(b)為使用中心對(duì)稱的Census變換，圖4(c)為使用中心對(duì)稱的Census變換和梯度信息相結(jié)合。對(duì)比圖4(b)和圖4(c)可以看出，在Teddy圖像的左下角的遮擋區(qū)域，圖4(c)算法效果更好，證明了有效結(jié)合梯度信息可以提高在遮擋區(qū)域的匹配精度。同時(shí)結(jié)合不同匹配代價(jià)方法的誤匹配率結(jié)果(表3)可以看出，文中使用中心對(duì)稱的Census變換和梯度信息相結(jié)合較單一匹配代價(jià)方法匹配精度更高，證明了文中算法結(jié)合方式的有效性。

綜合上述實(shí)驗(yàn)結(jié)果及分析可知，文中所提算法與傳統(tǒng)的引導(dǎo)濾波算法[4]相比，可以有效降低誤匹配率，圖像邊緣信息更加突出；與單尺度的ARW算法[13]相比，文中算法在進(jìn)行多尺度的融合后可以有效提升立體匹配的精度；與基于跨尺度的立體匹配算法[14]相比，文中所提算法在代價(jià)聚合階段通過全局優(yōu)化可以有效考慮到圖像鄰近像素之間的約束關(guān)系，減少誤匹配點(diǎn)，能夠提高整體的匹配精度，獲得效果更好的視差圖。同時(shí)由表4可以看出，與文獻(xiàn)[7- 8]算法相比，文中算法匹配精度更高。

(a)標(biāo)準(zhǔn)視差圖

(b)CS-CT

(c)CS-CT+Gradient

Fig.4 Teddy image of disparity map with different matching cost methods

表3 不同匹配代價(jià)方法的誤匹配率

表4 文中算法與Middlebury部分算法的誤匹配率的對(duì)比

Table 4 Mismatch rate comparision between the proposed algorithm and Middlebury algorithm

算法誤匹配率/%非遮擋區(qū)域所有區(qū)域文獻(xiàn)[7]算法19.126.2文獻(xiàn)[8]算法17.024.6本文算法14.722.2

3 結(jié)論

在基于單尺度的重啟動(dòng)與隨機(jī)游走立體匹配算法基礎(chǔ)上，結(jié)合跨尺度代價(jià)聚合框架，提出了跨尺度的重啟動(dòng)與隨機(jī)游走算法。該算法在代價(jià)聚合步驟中有效結(jié)合局部算法和全局算法的優(yōu)點(diǎn)，先利用超像素分割實(shí)現(xiàn)代價(jià)聚合，再通過重啟動(dòng)與隨機(jī)游走算法進(jìn)行全局優(yōu)化，最后通過跨尺度模型實(shí)現(xiàn)多尺度匹配代價(jià)的有效融合。在視差求精階段，采用一系列優(yōu)化方法(如引導(dǎo)濾波、左右一致性檢測(cè)、中值濾波等)來提高最后視差圖的精度。實(shí)驗(yàn)結(jié)果表明，文中所提算法可以有效提升立體匹配的精度。