,
(華東理工大學化工過程先進控制和優(yōu)化技術(shù)教育部重點實驗室,上海 200237)
一種基于多鄰域非線性擴散的動態(tài)規(guī)劃全局立體匹配算法
耿冬冬,羅娜
(華東理工大學化工過程先進控制和優(yōu)化技術(shù)教育部重點實驗室,上海200237)
雙目立體視覺匹配通過兩幅具有一定視差的圖像獲得精確、稠密的視差圖。為了解決動態(tài)規(guī)劃立體匹配算法橫條紋瑕疵以及精度低的問題,提出了一種基于多鄰域非線性擴散的立體匹配算法。該算法采用AD測度函數(shù)構(gòu)建視差空間,根據(jù)行列像素之間的約束關(guān)系,基于非線性擴散的代價聚合方法,通過圖像邊緣的動態(tài)優(yōu)化尋求全局能量函數(shù)最優(yōu)值得到稠密視差圖。在Middlebury測試集上的實驗結(jié)果表明,該算法的平均誤匹配率為5.60%,相比IIDP動態(tài)規(guī)劃全局匹配算法,精度提高了39.9%,有效地解決了橫向條紋問題,改善了邊緣模糊情況,且提升了算法的穩(wěn)定性。與其他全局匹配算法相比,本文算法誤匹配率降低了38.2%,在圖像參數(shù)的11個指標中有9項指標排名第1。
動態(tài)規(guī)劃; 立體匹配; 非線性擴散; 視差; 代價疊加
作為計算機視覺領(lǐng)域的一個重要研究方向,立體視覺可以重構(gòu)場景的三維幾何信息,已被廣泛應(yīng)用于移動機器人的自主導(dǎo)航系統(tǒng)、航空及遙感測量、工業(yè)自動化工件檢測等領(lǐng)域。為從平面圖像中恢復(fù)深度信息,立體匹配技術(shù)通過三角測量原理,建立合適的匹配約束和匹配準則以尋找同一場景在不同觀察點下投影圖像中像素間的一一對應(yīng)關(guān)系,并由此得到相應(yīng)的視差圖像,算法的性能直接影響到圖像深度的分析以及后期三維重建場景的準確性和效果。因此,立體匹配算法一直是計算機視覺領(lǐng)域的一個中心研究問題,對立體匹配算法的研究具有重要的意義。
針對實際問題中匹配的不確定性,研究者們提出了不同的立體匹配算法[1-2]。根據(jù)匹配約束條件和搜索策略的不同,算法可以分為局部支持鄰域準則的局部立體匹配算法[3-4]以及采用全局策略的全局立體匹配算法[5-6]。局部匹配方法的優(yōu)點是計算復(fù)雜度低、運算速度快,因此被較多實時立體視覺系統(tǒng)所采用。但由于是基于局部尋優(yōu),對弱紋理、遮擋等局部歧義區(qū)域較敏感,相對全局算法來說,易造成誤匹配,因此視差圖的誤匹配率比較高。全局匹配算法通過引入平滑函數(shù)項,將對應(yīng)的匹配問題轉(zhuǎn)化為尋找能量函數(shù)的全局最優(yōu)解問題,再通過各種全局最優(yōu)算法求得能量函數(shù)的最小值。全局匹配算法主要包括最大流/最小割的圖割算法(Graph Cut,GC)[7-8]、動態(tài)規(guī)劃算法(Dynamic Programming,DP)、模擬退火算法(Simulated Annealing,SA)[9]以及置信度傳播算法(Belief Propagation,BP)[10-12]等。全局匹配算法的誤匹配率低,準確率較高,能夠獲得較精準的稠密視差圖,但是計算量大,計算時間較長。
作為目前立體匹配中廣泛應(yīng)用的動態(tài)規(guī)劃立體匹配算法[13],在計算出初始匹配代價的基礎(chǔ)上,用動態(tài)規(guī)劃算法進行全局優(yōu)化,視差圖的質(zhì)量得到了明顯的提高,但是該算法的缺點是缺少對掃面線之間的約束限制,因此生成的視差圖上帶有明顯的條紋狀瑕疵。針對這一問題,Birchfield等[14]提出在垂直方向上,將可信度高區(qū)域內(nèi)的視差向可信度低的區(qū)域擴張,改善了視差效果。Leung等[15]提出了快速的IDP方法,加強了圖像的掃面線之間的視差連續(xù)性,但是算法本身需要迭代多次,且視差圖質(zhì)量依賴于設(shè)置的初始值。Scharstein等[16]使用獨立灰度動態(tài)規(guī)劃算法(IIDP)降低邊緣處的遮擋代價,取得了較好的效果,但橫向條紋問題仍然存在。
為解決視差圖的條紋瑕疵問題以及降低誤匹配率,本文在動態(tài)規(guī)劃算法的基礎(chǔ)上,提出了一種基于多鄰域非線性擴散的動態(tài)規(guī)劃全局立體匹配算法。該算法不僅有效地解決了水平方向上的條紋瑕疵問題,而且在圖像邊緣處改善了邊緣模糊問題,提升了算法的精度和準確性。
1.1視差匹配約束關(guān)系
圖像的成像是物體從三維投影到二維空間的過程,大量信息丟失,同時伴隨著空間噪聲、相機切向和徑向畸變的存在,使得視差匹配問題本身存在固有的不確定性。一般情況下,源圖(Resource)中的像素點,在匹配圖(Matching)中會存在多個候選匹配點,因而導(dǎo)致了匹配歧義。為了使匹配更有效,需要引入一系列的約束來降低像素點之間的誤匹配,從而提高匹配質(zhì)量和效率。本文算法遵循下列約束條件:
(1) 順序一致性約束。在源圖中具有一定順序的像素點,在目標圖中也具有相應(yīng)的順序。即Rm (2) 視差范圍約束。限定立體匹配搜索的視差空間是有限的,即d∈[0,dmax],其中d是匹配點的視差值。 (3) 遮擋約束。當圖像中存在遮擋區(qū)域時,左遮擋與右遮擋不能同時出現(xiàn)。 1.2全局能量代價函數(shù)的構(gòu)造 基于能量代價函數(shù)的全局優(yōu)化算法的本質(zhì)是將立體匹配問題轉(zhuǎn)化為求取視差的最優(yōu)解問題。首先要構(gòu)造一個建立在視差空間的全局能量代價函數(shù),然后利用全局優(yōu)化算法來求取使代價函數(shù)取得最小值時的視差值d。 立體匹配的全局能量代價函數(shù)包括匹配像素間的數(shù)據(jù)項Edata(d)、衡量圖像對中匹配像素點之間的相似性、像素間的視差平滑懲罰項Esmooth(d),約束相鄰像素間的不連續(xù)性。 E(d)=Edata(d)+λEsmooth(d) (1) 式(1)的解空間為D(d1,d2,…,dn),其中n為行內(nèi)像素的個數(shù),di為第i個像素的視差值。通過最小化該函數(shù)得出匹配的視差圖Edata(d)如下: Edata(d)=∑(DSI(x,y,d)) (2) 其中,DSI是視差的疊加代價。 Esmooth(d)=∑ρ(d(x,y)-d(x+1,y))+ ρ(d(x,y)-d(x,y+1)) (3) 其中,ρ是視差的單調(diào)遞增函數(shù),使得視差處處平滑。 現(xiàn)有的全局優(yōu)化動態(tài)規(guī)劃匹配算法的一個問題是在計算每個像素點的匹配代價后直接構(gòu)建包含有平滑約束的全局能量函數(shù),并未考慮匹配代價疊加,從而導(dǎo)致動態(tài)規(guī)劃立體匹配中的橫條紋瑕疵問題。另一個問題是在圖像的邊緣處,深度是不連續(xù)的,在邊緣再平滑將會造成邊界的模糊。邊界模糊的很大原因是由于在此處的視差代價計算過大,不符合真實情況。對此,本文在原有的視差空間基礎(chǔ)上重新設(shè)計視差空間,根據(jù)降低平滑代價的思想優(yōu)化原有Esmooth,定義全新的平滑優(yōu)化項解決邊緣模糊問題。 2.1概述 在立體匹配算法框架的基礎(chǔ)上,本文算法結(jié)構(gòu)主要分為3個部分。首先是使用相似性測度函數(shù)建立待匹配圖像對的視差空間;其次通過非線性擴散方法對得到的視差空間進行匹配代價聚合;最后用優(yōu)化邊緣的動態(tài)規(guī)劃算法來建立全局匹配代價函數(shù)。 2.2視差空間圖像的建立 雖然立體匹配算法有多種,但是求解步驟通常包括原始匹配代價計算、匹配代價聚集、視差最優(yōu)化計算以及視差求精4個步驟。通過相似性測度函數(shù)計算原始匹配代價,對圖像進行不同視差下的灰度相似性測度,得到原始的視差空間圖像(DSI),如圖1所示。 圖1 視差空間圖像Fig.1 Disparity space image DSI是三維空間中不同視差d下所對應(yīng)的x-y切面,該空間中的每個坐標值(x,y,d)表示像素點(x,y)在視差為d時的匹配代價值C(x,y,d),該值可用式(4)表示: C(x,y,d)=f(IL(x,y),IR(x,y)) (4) 其中函數(shù)f(…)表示相似性測度函數(shù)。 2.3基于多鄰域非線性擴散的匹配代價聚合 由于包括IIDP方法在內(nèi)的動態(tài)規(guī)劃算法并沒有考慮到行與行之間的像素約束關(guān)系,因此往往會出現(xiàn)比較明顯的橫向條紋,即動態(tài)規(guī)劃立體匹配中的橫條紋瑕疵問題。本文引入非線性擴散方法解決立體匹配中的條紋問題。 在圖像處理領(lǐng)域中,非線性擴散可以用于圖像的平滑處理,可以進行圖像鄰域的交互,從而擴大局部數(shù)據(jù)的影響。擴散過程中,灰度值在圖像中傳播,當所有像素的灰度值相等時達到平衡。本文在Perona等[17]提出的將非線性擴散與圖像內(nèi)容相聯(lián)系的PM模型的基礎(chǔ)上,對區(qū)域內(nèi)和區(qū)域間采取不同的濾波策略,從而得出DSI的擴散規(guī)則如下: DSI(x,y,d)=(1-4β)DSI(x,y,d)+ (5) 其中:DSI(x′,y′,d)是像素點(x,y)的多鄰域,即與點(x,y)直接相連的上、下、左、右以及對角線上的像素點;β表示控制擴散速度的參數(shù);N8定義如下: N8={(-1,-1),(0,-1),(1,-1),(1,0), (1,1),(0,1),(-1,1),(-1,0)} (6) 將非線性擴散匹配代價聚合方法加入視差計算框架中,構(gòu)建新的待優(yōu)化問題模型。多鄰域非線性擴散代價聚合可以考慮到行間像素點的約束信息,因此減少橫向條紋,提高匹配質(zhì)量。 2.4動態(tài)規(guī)劃尋徑求解優(yōu)化的全局能量函數(shù) 因原有的平滑優(yōu)化項會導(dǎo)致邊緣模糊的問題,在原有的視差函數(shù)ρ的基礎(chǔ)上與某個單調(diào)遞減函數(shù)乘積,利用在此區(qū)域降低平滑代價的思想優(yōu)化,全新的Esmooth如下: Esmooth(d)=∑ρ(d(x,y)-d(x+1,y))× ρ′(|(I(x,y)-I(x+1,y))|)+ ρ(d(x,y)-d(x,y+1))× ρ′(|(I(x,y)-I(x,y+1))|) (7) 其中ρ′是和灰度值關(guān)聯(lián)的單調(diào)遞減函數(shù),在圖像的邊緣處,灰度值的變化較大,因此可以降低灰度值相差較大處的平滑代價,優(yōu)化邊緣。 動態(tài)規(guī)劃解決匹配問題的思想是,在源圖與目標圖中對應(yīng)的掃描線上尋找最小匹配代價路徑。設(shè)m、l、r分別代表上一階段的3種匹配狀態(tài):匹配、左圖可見(左遮擋)、右圖可見(右遮擋)。同理,設(shè)M、L、R分別表示目前狀態(tài)。在加入限定的約束條件后,排除雙遮擋(即左右均遮擋)的情形,那么匹配狀態(tài)轉(zhuǎn)換只有7種形式,如圖2所示。通過以上假設(shè),可將問題轉(zhuǎn)化為動態(tài)規(guī)劃的范疇[18]。 圖2 動態(tài)規(guī)劃立體匹配算法的狀態(tài)變換形式Fig.2 Style of state transition of dynamic programming stereo matching algorithm 圖3所示為動態(tài)規(guī)劃路徑的實例,在當前的匹配狀態(tài)中,左右掃描線上的a、b、c、f、g、k6個像素點實現(xiàn)了正確匹配,d和e像素點發(fā)生了左遮擋,即在右掃描線上是不可見的,而h和i像素點在左掃描線上不可見,即右遮擋點。 圖3 動態(tài)規(guī)劃路徑尋找Fig.3 Routine of dynamic programming 用動態(tài)規(guī)劃在源圖與目標圖之間對應(yīng)掃描線上尋找最優(yōu)路徑的過程,就是求解某一視差分配的路徑或者最優(yōu)軌跡(即最優(yōu)視差分布)使得能量代價函數(shù)E(d)取值最小,即P(d)=arg min(E(d))。此時尋優(yōu)路徑搜索出的路徑包括了遮擋點和匹配的像素點的信息。在算法中,用檢測到的遮擋點的像素左最鄰近的點的視差填充遮擋點,提高了匹配精度。填充的部分程序如下: for (x=start;x!=end;x+=1) { intd= disp[x] ; if (disp[x] ==occLabel) disp[x]=oldd ; else oldd=d; } 目前,立體匹配算法的主要評價標準是美國Middlebury College的Scharsitein提出的立體匹配評價標準和評價平臺[19],本文采用該平臺提供的標準立體圖像測試集Tsukuda圖像、Sawtooth圖像、Venus圖像和Map圖像檢驗本文算法的效果,并依此進行分析。 對于匹配所產(chǎn)生視差圖的評價主要通過定量衡量標準的誤匹配率(Percentage of Bad Matching,PBM)體現(xiàn),定義PBM為 (8) 其中:δd為視差容差,一般取值為1.0;N為圖像的像素點總數(shù)。該指標反映了算法得到的視差值dc(x,y)與真實視差值dT(x,y)的誤差大于δd的像素個數(shù)在整幅圖像中的比例。 測試集圖像的源圖像、真實的視差圖、IIDP動態(tài)規(guī)劃全局匹配算法得到的視差圖以及本文方法得到的視差圖對比結(jié)果如圖4所示。 圖4(a)~4(d)中,對于Tsukuba圖像,本文算法相比原有IIDP全局算法的誤匹配率降低了28%,在無紋理區(qū)域和非遮擋區(qū)域的誤匹配率分別降低了40%和31.8%,橫向條紋得到了明顯的改善,且修復(fù)了邊緣模糊的問題。在圖4(e)~4(f)中,對于Sawtooth圖像,改進后的全局算法相比原算法的誤匹配率下降了34%,而在無紋理區(qū)域和非遮擋區(qū)域的誤匹配率分別降低了48.8%和50%。在第3幅測試圖像Venus中,改進的全局算法相比原有算法的誤匹配率降低了51.6%,在無紋理區(qū)域和非遮擋區(qū)域的無匹配率分別降低了58.5%和60.7%。同時,在圖4(d)和圖4(i)兩幅深度圖中,有較為清晰的黑色或者灰色的紋理,代表此處是遮擋部分,可見本文算法能夠有效地識別遮擋區(qū)域。因而本文方法對帶有遮擋的圖像依然具有穩(wěn)定的匹配效果,相比于傳統(tǒng)動態(tài)規(guī)劃算法,提高了匹配的魯棒性。在Map圖像中,改進的全局算法相比原有的全局算法的誤匹配率降低了75.5%,在無遮擋區(qū)域和連續(xù)區(qū)域的誤匹配率分別降低了88.3%和62.7%。本文算法所獲得的視差圖都大幅度地提高了匹配的精度,且明顯改善了動態(tài)規(guī)劃全局算法中的“橫條紋瑕疵”問題,提高了匹配的準確性,證明了算法的可行性和正確性。在匹配算法耗時方面,測試所用計算機的配置為Intel Core i3,4 G內(nèi)存,算法運行時間如表1所示??梢钥闯?本文的改進算法在提高匹配精度的同時,也保證了算法的執(zhí)行時間。 圖4 對標準圖像Tsukuda、Sawtooth、Venus和Map的實驗結(jié)果對比Fig.4 Comparsion of experiment results for standard images of Tsukuda、Sawtooth、Venus and Map 表1 算法運行時間 相似性測度函數(shù)中常用的有灰度差的平方(SD)、灰度差的絕對值(AD)等。本文用這兩種測度函數(shù)測評Middlebury提供的標準立體匹配數(shù)據(jù)集圖像,對比數(shù)據(jù)如表2所示。 從表2可以看出,在所有評價結(jié)果中,AD方法的結(jié)果完全優(yōu)于SD方法,因此,本文算法在原始匹 配代價計算選用AD方法,即 C(x,y,d)=|IL(x,y)-IR(x-d,y)| (9) 為了更好地評測本文算法的立體匹配效果,將其與其他幾種著名的算法進行對比,對比結(jié)果如表3所示。從表3可以看出,本文的全局算法對所有圖像的平均誤匹配率為5.60%,相比于IIDP全局算法的9.32%,誤匹配率降低了39.9%。 表3中還對比了Scanline 全局[16]、Di快速匹配[20]等全局立體匹配算法以及RTCensus[21]算法。綜合各個指標,本文算法不僅平均誤匹配率在所有算法中最低,且在圖像參數(shù)的11個指標中有9項指標排名第1,本文算法的表現(xiàn)均優(yōu)于其他全局算法和局部算法,體現(xiàn)出了更好的準確精度和匹配質(zhì)量。 表2 SD、AD測度函數(shù)表現(xiàn) 表3 本文方法與IIDP全局算法的參數(shù)對比 在深入研究現(xiàn)有算法的基礎(chǔ)上,本文提出了一種基于多鄰域的非線性擴散動態(tài)規(guī)劃立體匹配算法,增加了多鄰域非線性擴散進行代價疊加計算,提高了算法整體的準確性,明顯改善了傳統(tǒng)動態(tài)算法的“橫條紋瑕疵”問題,降低了誤匹配率。在視差優(yōu)化階段,在圖像的邊緣處降低平滑代價,從而改善了邊緣模糊的問題。本文算法與傳統(tǒng)動態(tài)優(yōu)化算法相比,具有更準確、效率更高、邊緣清晰的特點。針對不同測試圖像的實驗結(jié)果表明,本文算法的平均誤匹配率為5.60%,算法的效果和精度遠遠高于改進前的IIDP全局優(yōu)化算法,且匹配的穩(wěn)定性得到加強。與其他全局算法的對比結(jié)果表明,本文算法具有更好的精度和準確度。 [1] TIPPETTS B,LEE D J,LILLYWHITE K,etal.Review of stereo vision algorithms and their suitability for resource-limited systems[J].Journal of Real-Time Image Processing,2016,11(1):5-25. [2] BROWN M Z,BURSCHKA D,HAGER G D.Advances in computational stereo [J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2003,25(8):993-1008. [3] DUMONT M,GOORTS P,MAESEN S,etal.Real-time local stereo matching using edge sensitive adaptive windows[C]//International Conference on Signal Processing and Multimedia Applications.Switzerland:Springer,2015:117-126. [4] HOSNI A,BLEYER M,GELAUTZ M.Secrets of adaptive support weight techniques for local stereo matching [J].Computer Vision & Image Understanding,2013,117(6):620-632. [5] PAN S C.Stereo matching algorithm based on belief propagation system[J].Applied Mechanics & Materials,2015,713/715:1931-1934. [6] KOLMOGOROV V,MONASSE P,TAN P.Kolmogorov and Zabih's graph cuts stereo matching algorithm[J].Image Processing on Line,2014(4):220-251. [7] TANIAI T,MATSUSHITA Y,NAEMURA T.Graph cut based continuous stereo matching using locally shared labels[C]//IEEE Conference on Computer Vision and Pattern Recognition.USA:IEEE Computer Society,2014:1613-1620. [8] KIM J H,KWON J W,YUN H K.Multi-baseline based texture adaptive belief propagation stereo matching technique for dense depth-map acquisition[C]//International Conference on Electronics,Information and Communications.USA:IEEE,2014:1-2. [9] HERRERA P J,PAJARES G,GUIJARRO M,etal.Combining support vector machines and simulated annealing for stereovision matching with fish eye lenses in forest environments [J].Expert Systems with Applications,2011,38(7):8622-8631. [10] WANG X,LIU Y.Accurate and fast convergent initial-value belief propagation for stereo matching[J].Plos One,2015,10(9):e0137530. [11] KLAUS A,SORMANN M,KARNER K.Segment-based stereo matching using belief propagation and a self-adapting dissimilarity measure[C]//International Conference on Pattern Recognition.USA:IEEE Computer Society,2006:15-18. [12] YANG Y,WANG X,LIANG Q.Belief propagation stereo matching algorithm based on ground control points and spatiotemporal consistency[C]//International Congress on Image and Signal Processing.USA:IEEE,2015:79-80. [13] OHTA Y,KANADE T.Stereo by intra- and inter-scanline search using dynamic programming [J].IEEE Transactions on Pattern Analysis & Machine Intelligence,1985,7(2):139-154. [14] BIRCHFIELD S,TOMASI C.Depth discontinuities by pixel-to-pixel stereo[J].International Journal of Computer Vision,1999,35(3):269-293. [15] LEUNG C,APPLETON B,SUN C.Fast stereo matching by iterated dynamic programming and quadtree subregioning[C]//British Machine Vision Conference.UK:[s.n.],2004:97-106. [16] SCHARSTEIN D,SZELISKI R.A taxonomy and evaluation of dense two-frame stereo correspondence algorithms[C]//Stereo and Multi-Baseline Vision.USA:IEEE,2001:131-140. [17] PERONA P,MALIK J.Scale-space and edge detection using anisotropic diffusion [J].IEEE Transactions on Pattern Analysis & Machine Intelligence,1990,12(7):629-639. [18] WANG P,CHEN C,WEI F F.A Stereo Matching Algorithm Based on Outline-Assisted Dynamic Programming[M].Berlin Heidelberg:Springer,2014:297-306. [19] WEI P Y.Research on stereo matching algorithms of binocular vision [D].Chongqing:Chongqing University,2009. [20] 狄紅衛(wèi),柴穎,李逵.一種快速雙目視覺立體匹配算法[J].光學學報,2009,29(8):2180-2184. [21] HUMENBERGER M,ZINNER C,WEBER M,etal.A fast stereo matching algorithm suitable for embedded real-time systems[J].Computer Vision & Image Understanding,2010,114(11):1180-1202. ADynamicProgrammingGlobalStereoMatchingAlgorithmBasedonMultipleNeighbors’NonlinearDiffusion GENGDong-dong,LUONa (KeyLaboratoryofAdvancedControlandOptimizationforChemicalProcesses,MinistryofEducation,EastChinaUniversityofScienceandTechnology,Shanghai200237,China) Binocular stereo matching can obtain the accuracy and dense disparity map by comparing two images.However,the utilization of dynamic programming algorithms may result in some shortcomings,such as stripe-like and low accuracy.Aiming these problems,this paper proposes a new stereo matching algorithm based on multiple neighbors’ nonlinear diffusion.Firstly,absolute difference test method is used to build disparity space image in raw costs computation period.And then,according to the constraint relation between rows and columns,multiple neighbors’ nonlinear diffusion of costs aggregation is proposed to improve the global costs function.Finally,dense disparity maps during the global optimization process are obtained by the edges-optimized DP optimization.The experiment results via Middlebury test images show that the proposed algorithm attains the average PBM5.60% and raises the accuracy39.9% than IIDP.Moreover,the problem of stripe-like is well solved and the edge-blurring is also improved.Compared with other global matching methods,the proposed algorithm reduces PBM by38.2% and has9of11indexes to rank the first. dynamic programming; stereo matching;nonlinear diffusion;disparity;costs aggregation TP391 A 1006-3080(2017)05-0677-07 10.14135/j.cnki.1006-3080.2017.05.012 2016-11-16 國家自然科學基金(61403140);上海市自然科學基金(13ZR1411500) 耿冬冬(1991-),男,碩士生,主要研究方向為圖像處理、雙目視覺。E-mail:wintergeng@foxmail.com 羅 娜,E-mail:naluo@ecust.edu.cn2 多鄰域非線性擴散DP立體匹配算法
3 實驗結(jié)果與分析
4 結(jié) 論