基于多特征融合與樹(shù)形結(jié)構(gòu)代價(jià)聚合的立體匹配算法

郁懷波, 胡越黎,3, 徐 杰

(1. 上海大學(xué)上海市電站自動(dòng)化技術(shù)重點(diǎn)實(shí)驗(yàn)室, 上海200444; 2. 上海大學(xué)微電子研究與開(kāi)發(fā)中心, 上海200444;3. 上海大學(xué)機(jī)電工程與自動(dòng)化學(xué)院, 上海200444)

雙目立體視覺(jué)是計(jì)算機(jī)視覺(jué)領(lǐng)域的熱門(mén)話題之一. 立體匹配算法主要可以分為2 大類：全局算法和局部算法. 全局算法通常是通過(guò)定義一個(gè)全局能量函數(shù)并尋找最優(yōu)解來(lái)得到視差圖.全局算法包括動(dòng)態(tài)規(guī)劃[1]、置信區(qū)間傳播[2]和圖割算法[3]等. 雖然全局算法準(zhǔn)確率較高, 但是算法運(yùn)算量較大, 難以達(dá)到實(shí)時(shí)性要求; 局部算法則是通過(guò)像素點(diǎn)周?chē)木植啃畔?lái)判斷視差值, 速度較快且易于實(shí)現(xiàn), 但是其匹配代價(jià)計(jì)算方式和代價(jià)聚合區(qū)域的選擇是難點(diǎn).

常用的匹配代價(jià)計(jì)算方式包括灰度的絕對(duì)差值之和(sum of absolute differences, SAD)、灰度的差值平方和(sum of squared differences,SSD)以及灰度值的歸一化互相關(guān)(normalized crosscorrelation, NCC). 然而, 這些匹配代價(jià)計(jì)算方式對(duì)于噪聲、相機(jī)增益、偏置都非常敏感,在弱紋理區(qū)域的匹配效果不佳[4]. 中值濾波、高斯拉普拉斯算子和圖像梯度幅值[5]等圖像預(yù)處理方式可以有效濾除噪聲, 但是由此得到的視差圖邊緣部分不夠清晰[4]. 互信息(mutual information, MI)[6]、Rank 變換和Census 變換等非參數(shù)方法對(duì)噪聲具有較高的魯棒性, 得到的視差圖邊緣部分也較清晰, 但是由于沒(méi)有考慮到圖像的顏色信息, 故在圖像的重復(fù)結(jié)構(gòu)區(qū)域往往會(huì)造成誤匹配. 可見(jiàn), 匹配代價(jià)計(jì)算方式的合理性直接關(guān)系到立體匹配算法的準(zhǔn)確度.

為了在深度不連續(xù)區(qū)域得到精確的視差, 用于代價(jià)聚合的區(qū)域應(yīng)該僅僅包含同一深度的像素點(diǎn). 目前, 代價(jià)聚合方式主要分為2 大類[7]：①對(duì)每個(gè)像素點(diǎn)從預(yù)先定義的多個(gè)聚合窗口中選擇最佳的窗口[8], 或者自適應(yīng)調(diào)整每個(gè)像素點(diǎn)的聚合區(qū)域[9]; ②對(duì)于大小和形狀固定的聚合窗口, 自適應(yīng)調(diào)整窗口的權(quán)值[10]. 然而所有這些代價(jià)聚合方式都只考慮每個(gè)像素點(diǎn)周?chē)木植啃畔? 這必然會(huì)在弱紋理區(qū)域產(chǎn)生誤匹配, 存在深度不連續(xù)區(qū)域匹配精度不高的問(wèn)題.

為此, 針對(duì)立體匹配中弱紋理區(qū)域和深度不連續(xù)區(qū)域的匹配精度問(wèn)題, 本工作提出了一種基于多特征融合的樹(shù)形結(jié)構(gòu)代價(jià)聚合立體匹配算法, 該算法總體分為4 個(gè)步驟：①融合圖像梯度、圖像顏色以及圖像的Census 變換進(jìn)行匹配代價(jià)計(jì)算; ②根據(jù)由原始圖像顏色信息生成的最小生成樹(shù)進(jìn)行匹配代價(jià)聚合; ③使用多方向掃描線優(yōu)化, 進(jìn)一步提高在弱紋理區(qū)域的匹配準(zhǔn)確率; ④使用左右一致性檢測(cè)標(biāo)記出誤匹配點(diǎn), 基于視差統(tǒng)計(jì)直方圖對(duì)誤匹配點(diǎn)進(jìn)行修正.

1 基于多特征融合的匹配代價(jià)計(jì)算

Census 變換與像素灰度值的具體大小存在著弱相關(guān)性, 只涉及像素之間的相對(duì)大小之間的聯(lián)系, 因而Census 變換對(duì)噪聲具有強(qiáng)魯棒性. 但是, 在圖像的重復(fù)結(jié)構(gòu)或相似結(jié)構(gòu)區(qū)域,Census 變換的這種特性可能會(huì)導(dǎo)致誤匹配. 與Census 變換相反, 基于顏色特征的SAD 在這些紋理復(fù)雜區(qū)域有著較好的表現(xiàn)效果. 再考慮到基于梯度的匹配代價(jià)可以最大限度地提取出原始圖像的材質(zhì)信息, 進(jìn)一步提高在弱紋理區(qū)域內(nèi)的匹配精度, 因此本工作提出了一種融合圖像的梯度信息、顏色信息以及Census 變換的匹配代價(jià)計(jì)算方法.

1.1 基于梯度的匹配代價(jià)

圖像的梯度包含豐富的結(jié)構(gòu)信息. 由于圖像的梯度不受圖像絕對(duì)亮度的影響, 即使雙目相機(jī)成像的亮度不同, 圖像的梯度依然能較好地衡量2 幅圖像的相似性, 故基于梯度的匹配代價(jià)被廣泛應(yīng)用在立體匹配算法中. 基于梯度的匹配代價(jià)計(jì)算方法為

式中, Cgrad(p, d)表示像素點(diǎn)p 在視差為d 時(shí)的基于梯度的匹配代價(jià); ?x和?y分別為x 方向和y 方向的基于單色灰度值的梯度算子; IL(p)和IR(p, d)分別為左圖像中的像素點(diǎn)p 和右圖像中視差為d 所對(duì)應(yīng)的像素點(diǎn).

1.2 基于Census 變換的匹配代價(jià)

Census 變換是一種局部非參數(shù)變換, 即將變換窗口內(nèi)的像素的強(qiáng)度值映射到一個(gè)比特串,從而捕捉到圖像的結(jié)構(gòu)信息, 并以該比特串代替變換窗口內(nèi)的中心像素點(diǎn). 具體定義為

式中, Np是以像素點(diǎn)p 為中心的變換窗口; ?為位拼接算子, 用來(lái)把單獨(dú)的二進(jìn)制位連接成比特串; Ip和Iq分別為像素點(diǎn)p 和q 的像素值. 對(duì)于在左圖中像素點(diǎn)p 以及右圖中視差為d對(duì)應(yīng)的像素點(diǎn)q, 在分別得到Census 變換后的比特串Census(p)和Census(q)后, 基于Census變換的匹配代價(jià)即為2 串比特串之間的漢明距離. 用⊕來(lái)表示漢明距離算子, 則基于Census變化的匹配代價(jià)可表示為

1.3 基于顏色的匹配代價(jià)

基于顏色的匹配代價(jià)是立體匹配算法中最常用的匹配代價(jià)計(jì)算方法, 其具體操作如下: 令p 和q 分別為左圖中像素點(diǎn)以及右圖中視差為d 所對(duì)應(yīng)的像素點(diǎn), 則基于顏色的匹配代價(jià)定義R, G, B 這3 個(gè)通道顏色差值的平均值為

1.4 多特征匹配代價(jià)融合

將基于梯度、Census 變換和顏色的匹配代價(jià)進(jìn)行融合, 形成最終的多特征匹配代價(jià):

式中, CAD, Ccen和Cgrad分別為基于顏色、基于Census 變換和基于梯度的匹配代價(jià), 由式(4), (3)和(1)定義; 截?cái)嗪瘮?shù)T(C, t)定義為[4]

式(5)中的tAD, tcen和tgrad分別為基于顏色、基于Census 變換和基于梯度的匹配代價(jià)的截?cái)嚅撝? 是用來(lái)確保當(dāng)匹配代價(jià)融合時(shí)不過(guò)分偏向于某一種匹配代價(jià). α, β, λ 為調(diào)整參數(shù), 用來(lái)控制各個(gè)匹配代價(jià)在融合時(shí)的權(quán)值, α 和λ 分別用來(lái)調(diào)整基于顏色和梯度的匹配代價(jià)的權(quán)重, 通常λ 取為α 的4 倍, 這樣使基于梯度的匹配代價(jià)能夠補(bǔ)償基于顏色的匹配代價(jià)在弱紋理區(qū)域內(nèi)噪聲魯棒性較低的不足; 調(diào)整參數(shù)β 是用來(lái)調(diào)整基于Census 變化的匹配代價(jià)的權(quán)重的, 通常取大于α 和λ 的值, 使最終融合的匹配代價(jià)能夠同時(shí)表達(dá)原始圖像的顏色信息和基于Census 變換的結(jié)構(gòu)信息.

2 基于樹(shù)形結(jié)構(gòu)的匹配代價(jià)聚合

傳統(tǒng)的代價(jià)聚合通常是基于一個(gè)預(yù)先定義的、大小固定的窗口, 或根據(jù)顏色等信息自適應(yīng)生成的代價(jià)聚合窗口, 但是基于窗口的代價(jià)聚合從根本上限制了每個(gè)像素點(diǎn)只能根據(jù)其周?chē)木植啃畔?lái)對(duì)視差值進(jìn)行判斷, 因而在某些情況下根本無(wú)法找到一個(gè)最合適的聚合窗口. 與基于窗口的代價(jià)聚合不同, 文獻(xiàn)[11]提出的基于樹(shù)形結(jié)構(gòu)的代價(jià)聚合對(duì)于每一個(gè)像素點(diǎn), 都考慮到了原始圖像上除該像素點(diǎn)以外所有的像素點(diǎn). 本工作使用該樹(shù)形結(jié)構(gòu)對(duì)基于多特征融合的匹配代價(jià)進(jìn)行聚合, 從而進(jìn)一步提高匹配準(zhǔn)確度.

2.1 樹(shù)形結(jié)構(gòu)的建立

將原始左圖作為建立最小生成樹(shù)的引導(dǎo)圖像, 用G=(V, E)表示, 其中頂點(diǎn)V 為所有的圖像像素點(diǎn), 邊E 為所有鄰近像素點(diǎn)之間的邊. 令s 和r 為一組鄰近的像素點(diǎn), 則這2 個(gè)頂點(diǎn)之間的邊的權(quán)重定義為這2 個(gè)像素點(diǎn)的像素灰度差值:

在由原始左圖生成的平面四連通無(wú)向圖G 中, 去掉權(quán)重較大的邊, 即生成了用來(lái)對(duì)匹配代價(jià)進(jìn)行聚合的最小生成樹(shù).

2.2 基于樹(shù)形結(jié)構(gòu)的代價(jià)聚合

首先, 從葉節(jié)點(diǎn)往根節(jié)點(diǎn)方向進(jìn)行代價(jià)聚合(見(jiàn)圖1(a)). 圖中, 每條邊上的數(shù)字表示相鄰2 個(gè)節(jié)點(diǎn)之間的距離. 從葉節(jié)點(diǎn)往根節(jié)點(diǎn)的代價(jià)聚合值

式中, P(vc)表示像素點(diǎn)vc的父節(jié)點(diǎn), 函數(shù)S(p, q)表示像素點(diǎn)p 和q 的相似性. 令D(p, q)為最小生成樹(shù)中p, q 這2 個(gè)像素點(diǎn)的距離, 那函數(shù)么S(p, q)定義為

式中, σ 是一個(gè)常數(shù), 用來(lái)控制2 個(gè)像素點(diǎn)的相似性程度. 然后, 再?gòu)母?jié)點(diǎn)往葉節(jié)點(diǎn)進(jìn)行代價(jià)聚合, 從而得到每個(gè)像素點(diǎn)最終的代價(jià)聚合值(見(jiàn)圖1(b)). 因此, 最小生成樹(shù)上每一個(gè)像素點(diǎn)的代價(jià)聚合值為

圖1 代價(jià)聚合過(guò)程Fig.1 Cost aggregation process

3 多方向掃描線優(yōu)化

考慮到在實(shí)際場(chǎng)景中, 除物體邊緣區(qū)域外視差變換都是連續(xù)的, 即相鄰像素點(diǎn)之間的視差值應(yīng)變化不大. 為此, 在全局能量函數(shù)中新增視差平滑約束項(xiàng)[12]

式中,C 為根據(jù)最小生成樹(shù)聚合后并依據(jù)每個(gè)像素點(diǎn)代價(jià)聚合時(shí)的權(quán)值(即式(9)中的S(p,q))進(jìn)行歸一化后的匹配代價(jià); p,d 分別為待匹配圖像中的像素點(diǎn)及其視差值; p′,d′分別為像素點(diǎn)p領(lǐng)域中的像素點(diǎn)及其視差值; ε 為視差平滑約束項(xiàng); G 為待匹配圖像的梯度; λ 是一個(gè)調(diào)整參數(shù), 用來(lái)調(diào)整視差平滑約束的強(qiáng)度. 對(duì)于該能量函數(shù), 在原始圖像的上下左右4 個(gè)方向上分別使用動(dòng)態(tài)規(guī)劃對(duì)該全局能量函數(shù)進(jìn)行求解. 動(dòng)態(tài)規(guī)劃的遞推表達(dá)式為[12]

經(jīng)過(guò)多方向掃描線優(yōu)化后的每個(gè)像素點(diǎn)的最終代價(jià)值用e 表示, 根據(jù)WTA(winner-takes-all)策略, 對(duì)于每個(gè)像素點(diǎn)p, 使得e(p, d)最小的d 即為該像素點(diǎn)的視差值.

4 視差修正

由上述步驟所得的初始視差圖在弱紋理區(qū)域和深度不連續(xù)區(qū)域內(nèi)包含很多誤匹配點(diǎn), 因此需要對(duì)誤匹配點(diǎn)進(jìn)行修正, 從而得到精確的視差圖. 本工作對(duì)誤匹配點(diǎn)進(jìn)行視差修正的方法是使用左右一致性檢測(cè)標(biāo)記誤匹配點(diǎn), 并基于視差統(tǒng)計(jì)直方圖對(duì)誤匹配點(diǎn)進(jìn)行修正.

4.1 左右一致性檢測(cè)

左右一致性檢測(cè)的原理是空間中一點(diǎn)在左圖像和右圖像中的視差值應(yīng)相同. 分別以左右圖像作為基準(zhǔn)求得視差圖DL和DR. 對(duì)左圖中的像素點(diǎn)p, 根據(jù)DL找到其在右圖中的對(duì)應(yīng)點(diǎn)p ?(DL(p), 0). 如果DL(p) = DR(p ?(DL(p), 0)), 則表示該像素點(diǎn)通過(guò)左右一致性檢測(cè), 是穩(wěn)定點(diǎn); 否則該像素點(diǎn)為誤匹配點(diǎn).

4.2 誤匹配點(diǎn)視差修正

誤匹配點(diǎn)的特征是在其周?chē)徲騼?nèi)總是存在正確視差像素點(diǎn), 即通過(guò)左右一致性檢測(cè)的穩(wěn)定點(diǎn). 對(duì)于檢測(cè)出的誤匹配點(diǎn)p, 根據(jù)其周?chē)徲騼?nèi)的穩(wěn)定點(diǎn)的視差值建立一個(gè)視差統(tǒng)計(jì)直方圖Hp, 該直方圖中的峰值所對(duì)應(yīng)的視差d 即認(rèn)為是該誤匹配點(diǎn)p 的修正后的視差值:

5 算法總體流程

算法的總體流程如圖2 所示. 在匹配代價(jià)計(jì)算部分, 首先分別計(jì)算基于梯度、基于Census變換和基于顏色的匹配代價(jià), 并對(duì)這3 種匹配代價(jià)進(jìn)行融合; 接著使用樹(shù)形結(jié)構(gòu)對(duì)融合后的匹配代價(jià)進(jìn)行聚合; 然后使用多方向掃描線優(yōu)化, 進(jìn)一步提高算法匹配的準(zhǔn)確度; 最后基于視差統(tǒng)計(jì)直方圖, 將未通過(guò)左右一致性檢測(cè)的誤匹配點(diǎn)進(jìn)行視差修正, 得到最終準(zhǔn)確的視差圖.

6 測(cè)試結(jié)果與分析

使用C++來(lái)驗(yàn)證本算法的有效性. 測(cè)試平臺(tái)為CPU i7-6700HQ、內(nèi)存8 GB 的電腦; 編譯軟件為VS 2013; 測(cè)試中所用的測(cè)試圖像來(lái)自Middlebury 測(cè)試集. 測(cè)試結(jié)果表明, 立體匹配算法中參數(shù)的選取對(duì)算法效果有較大影響, 經(jīng)過(guò)分析得到各參數(shù)的設(shè)置情況如下: 式(5)中匹配代價(jià)的截?cái)嚅撝祎grad=40, tAD=10, tcen=100, 融合權(quán)值α=0.25, β=1, γ=0.1, Census 變換的窗口大小取11×11, 式(9)中的相似性調(diào)整參數(shù)σ 為0.05, 式(11)中的視差平滑約束強(qiáng)度調(diào)整參數(shù)λ 為0.1, 視差統(tǒng)計(jì)直方圖統(tǒng)計(jì)的鄰域大小為11×11.

同時(shí), 為了更好地對(duì)本算法進(jìn)行評(píng)測(cè), 還選取了Middlebury 測(cè)試集中的NonLocal filter算法和SemiGlob 算法進(jìn)行對(duì)比. NonLocal filter 算法是經(jīng)典的基于樹(shù)形結(jié)構(gòu)代價(jià)聚合的非局部立體匹配算法, 在聚合的過(guò)程中只考慮顏色信息; SemiGlob 算法是一種半全局立體匹配算法, 在8 個(gè)方向上對(duì)全局能量函數(shù)進(jìn)行求解, 能量函數(shù)中的視差平滑約束項(xiàng)是固定的常數(shù).NonLocal filter, SemiGlob 和本算法的測(cè)試結(jié)果如圖3 所示.

圖2 算法整體流程Fig.2 Flow chart of the algorithm

圖3 結(jié)果視差圖對(duì)比Fig.3 Comparison of result disparity map

圖3 中從左往右依次為Middlebury 測(cè)試集中的Tsukuba, Venus, Teddy 和Cones 測(cè)試圖像. 在Tsukuba 測(cè)試圖像中, 本算法與NonLocal filter 算法都能較好地保留臺(tái)燈連接桿的邊緣部分, 且在Teddy 測(cè)試圖像中本算法的效果優(yōu)于NonLocal filter 算法效果. 本算法在4 張測(cè)試圖像的弱紋理區(qū)域以及深度不連續(xù)區(qū)域都能得到清晰、平滑的視差圖.

為了對(duì)匹配算法的效果進(jìn)行定量分析, 根據(jù)Middlebury 測(cè)試集提供的4 張測(cè)試圖像所對(duì)應(yīng)的標(biāo)準(zhǔn)視差圖進(jìn)行誤匹配率計(jì)算. 表1 列出了3 種算法的誤匹配率, 其中n-occ 表示非遮擋區(qū)域, all 表示所有區(qū)域, disc 表示深度不連續(xù)區(qū)域. 誤匹配率越小則立體匹配算法準(zhǔn)確度越高.由表1 中的數(shù)據(jù)可見(jiàn), 本算法在Tsukuba, Venus 和Teddy 3 張測(cè)試集圖像上的誤匹配率均低于SemiGlob 算法, 且在Venus 和Teddy 2 張測(cè)試圖像上的N-occ 非遮擋區(qū)域優(yōu)于NonLocal filter 算法. 測(cè)試得到的平均誤匹配率為6.38%, 低于SemiGlob 的7.50%, 略高于NonLocal filter 算法的5.48%.

表1 誤匹配率對(duì)比Table1 Error ratio comparison %

為進(jìn)一步驗(yàn)證本算法的實(shí)用性, 使用2 組實(shí)際場(chǎng)景進(jìn)行測(cè)試, 其測(cè)試結(jié)果如圖4 所示. 本算法得到的視差圖較好地保留了原始圖像的輪廓, 視差圖整體較平滑, 效果較好.

圖4 實(shí)際場(chǎng)景測(cè)試Fig.4 Actual scene test

由于拍攝的圖像沒(méi)有標(biāo)準(zhǔn)深度圖, 故通過(guò)選取一些顯著的特征點(diǎn), 比較特征點(diǎn)處實(shí)際深度與匹配計(jì)算得到的深度, 來(lái)對(duì)算法提取深度信息的準(zhǔn)確性進(jìn)行定量評(píng)價(jià)(見(jiàn)表2). 對(duì)于每一個(gè)測(cè)試場(chǎng)景, 分別選取5 個(gè)測(cè)試點(diǎn), 并根據(jù)測(cè)試點(diǎn)的實(shí)際深度與匹配深度計(jì)算得到平均測(cè)距誤差率, 最終得到測(cè)試場(chǎng)景1 和2 的平均測(cè)距誤差率分別為5.76%和5.55%, 基本達(dá)到雙目視覺(jué)深度信息提取的要求, 證明了本算法的實(shí)用性.

表2 實(shí)際場(chǎng)景測(cè)試誤差分析Table2 Error analysis of actual scene test

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

針對(duì)立體匹配中弱紋理區(qū)域和深度不連續(xù)區(qū)域的匹配精度不高的問(wèn)題, 提出了一種基于多特征融合的樹(shù)形結(jié)構(gòu)代價(jià)聚合立體匹配算法. 首先在代價(jià)計(jì)算部分融合了圖像的梯度、顏色和圖像的Census 變換; 其次基于所有像素點(diǎn), 在由原始圖像構(gòu)成的樹(shù)形結(jié)構(gòu)上進(jìn)行代價(jià)聚合; 接著加入平滑約束在多方向上進(jìn)行掃描線優(yōu)化, 進(jìn)一步提高算法在弱紋理區(qū)域的準(zhǔn)確度;最后使用左右一致性檢測(cè)誤匹配點(diǎn), 并根據(jù)視差統(tǒng)計(jì)直方圖進(jìn)行修正.

通過(guò)與Middlebury 測(cè)試集上另外2 種立體匹配算法Nonlocal filter 和SemiGlob 的對(duì)比表明, 本算法具有較好的立體匹配效果; 另外, 通過(guò)2 個(gè)實(shí)際場(chǎng)景的測(cè)試表明了本算法具有較高的實(shí)用性.