,

(華東理工大學(xué)化工過(guò)程先進(jìn)控制和優(yōu)化技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室,上海 200237)

一種基于多鄰域非線性擴(kuò)散的動(dòng)態(tài)規(guī)劃全局立體匹配算法

耿冬冬,羅娜

(華東理工大學(xué)化工過(guò)程先進(jìn)控制和優(yōu)化技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室,上海200237)

雙目立體視覺(jué)匹配通過(guò)兩幅具有一定視差的圖像獲得精確、稠密的視差圖。為了解決動(dòng)態(tài)規(guī)劃立體匹配算法橫條紋瑕疵以及精度低的問(wèn)題,提出了一種基于多鄰域非線性擴(kuò)散的立體匹配算法。該算法采用AD測(cè)度函數(shù)構(gòu)建視差空間,根據(jù)行列像素之間的約束關(guān)系,基于非線性擴(kuò)散的代價(jià)聚合方法,通過(guò)圖像邊緣的動(dòng)態(tài)優(yōu)化尋求全局能量函數(shù)最優(yōu)值得到稠密視差圖。在Middlebury測(cè)試集上的實(shí)驗(yàn)結(jié)果表明,該算法的平均誤匹配率為5.60%,相比IIDP動(dòng)態(tài)規(guī)劃全局匹配算法,精度提高了39.9%,有效地解決了橫向條紋問(wèn)題,改善了邊緣模糊情況,且提升了算法的穩(wěn)定性。與其他全局匹配算法相比,本文算法誤匹配率降低了38.2%,在圖像參數(shù)的11個(gè)指標(biāo)中有9項(xiàng)指標(biāo)排名第1。

動(dòng)態(tài)規(guī)劃; 立體匹配; 非線性擴(kuò)散; 視差; 代價(jià)疊加

作為計(jì)算機(jī)視覺(jué)領(lǐng)域的一個(gè)重要研究方向,立體視覺(jué)可以重構(gòu)場(chǎng)景的三維幾何信息,已被廣泛應(yīng)用于移動(dòng)機(jī)器人的自主導(dǎo)航系統(tǒng)、航空及遙感測(cè)量、工業(yè)自動(dòng)化工件檢測(cè)等領(lǐng)域。為從平面圖像中恢復(fù)深度信息,立體匹配技術(shù)通過(guò)三角測(cè)量原理,建立合適的匹配約束和匹配準(zhǔn)則以尋找同一場(chǎng)景在不同觀察點(diǎn)下投影圖像中像素間的一一對(duì)應(yīng)關(guān)系,并由此得到相應(yīng)的視差圖像,算法的性能直接影響到圖像深度的分析以及后期三維重建場(chǎng)景的準(zhǔn)確性和效果。因此,立體匹配算法一直是計(jì)算機(jī)視覺(jué)領(lǐng)域的一個(gè)中心研究問(wèn)題,對(duì)立體匹配算法的研究具有重要的意義。

針對(duì)實(shí)際問(wèn)題中匹配的不確定性,研究者們提出了不同的立體匹配算法[1-2]。根據(jù)匹配約束條件和搜索策略的不同,算法可以分為局部支持鄰域準(zhǔn)則的局部立體匹配算法[3-4]以及采用全局策略的全局立體匹配算法[5-6]。局部匹配方法的優(yōu)點(diǎn)是計(jì)算復(fù)雜度低、運(yùn)算速度快,因此被較多實(shí)時(shí)立體視覺(jué)系統(tǒng)所采用。但由于是基于局部尋優(yōu),對(duì)弱紋理、遮擋等局部歧義區(qū)域較敏感,相對(duì)全局算法來(lái)說(shuō),易造成誤匹配,因此視差圖的誤匹配率比較高。全局匹配算法通過(guò)引入平滑函數(shù)項(xiàng),將對(duì)應(yīng)的匹配問(wèn)題轉(zhuǎn)化為尋找能量函數(shù)的全局最優(yōu)解問(wèn)題,再通過(guò)各種全局最優(yōu)算法求得能量函數(shù)的最小值。全局匹配算法主要包括最大流/最小割的圖割算法(Graph Cut,GC)[7-8]、動(dòng)態(tài)規(guī)劃算法(Dynamic Programming,DP)、模擬退火算法(Simulated Annealing,SA)[9]以及置信度傳播算法(Belief Propagation,BP)[10-12]等。全局匹配算法的誤匹配率低,準(zhǔn)確率較高,能夠獲得較精準(zhǔn)的稠密視差圖,但是計(jì)算量大,計(jì)算時(shí)間較長(zhǎng)。

作為目前立體匹配中廣泛應(yīng)用的動(dòng)態(tài)規(guī)劃立體匹配算法[13],在計(jì)算出初始匹配代價(jià)的基礎(chǔ)上,用動(dòng)態(tài)規(guī)劃算法進(jìn)行全局優(yōu)化,視差圖的質(zhì)量得到了明顯的提高,但是該算法的缺點(diǎn)是缺少對(duì)掃面線之間的約束限制,因此生成的視差圖上帶有明顯的條紋狀瑕疵。針對(duì)這一問(wèn)題,Birchfield等[14]提出在垂直方向上,將可信度高區(qū)域內(nèi)的視差向可信度低的區(qū)域擴(kuò)張,改善了視差效果。Leung等[15]提出了快速的IDP方法,加強(qiáng)了圖像的掃面線之間的視差連續(xù)性,但是算法本身需要迭代多次,且視差圖質(zhì)量依賴于設(shè)置的初始值。Scharstein等[16]使用獨(dú)立灰度動(dòng)態(tài)規(guī)劃算法(IIDP)降低邊緣處的遮擋代價(jià),取得了較好的效果,但橫向條紋問(wèn)題仍然存在。

為解決視差圖的條紋瑕疵問(wèn)題以及降低誤匹配率,本文在動(dòng)態(tài)規(guī)劃算法的基礎(chǔ)上,提出了一種基于多鄰域非線性擴(kuò)散的動(dòng)態(tài)規(guī)劃全局立體匹配算法。該算法不僅有效地解決了水平方向上的條紋瑕疵問(wèn)題,而且在圖像邊緣處改善了邊緣模糊問(wèn)題,提升了算法的精度和準(zhǔn)確性。

1 算法基礎(chǔ)

1.1視差匹配約束關(guān)系

圖像的成像是物體從三維投影到二維空間的過(guò)程,大量信息丟失,同時(shí)伴隨著空間噪聲、相機(jī)切向和徑向畸變的存在,使得視差匹配問(wèn)題本身存在固有的不確定性。一般情況下,源圖(Resource)中的像素點(diǎn),在匹配圖(Matching)中會(huì)存在多個(gè)候選匹配點(diǎn),因而導(dǎo)致了匹配歧義。為了使匹配更有效,需要引入一系列的約束來(lái)降低像素點(diǎn)之間的誤匹配,從而提高匹配質(zhì)量和效率。本文算法遵循下列約束條件:

(1) 順序一致性約束。在源圖中具有一定順序的像素點(diǎn),在目標(biāo)圖中也具有相應(yīng)的順序。即Rm

(2) 視差范圍約束。限定立體匹配搜索的視差空間是有限的,即d∈[0,dmax],其中d是匹配點(diǎn)的視差值。

(3) 遮擋約束。當(dāng)圖像中存在遮擋區(qū)域時(shí),左遮擋與右遮擋不能同時(shí)出現(xiàn)。

1.2全局能量代價(jià)函數(shù)的構(gòu)造

基于能量代價(jià)函數(shù)的全局優(yōu)化算法的本質(zhì)是將立體匹配問(wèn)題轉(zhuǎn)化為求取視差的最優(yōu)解問(wèn)題。首先要構(gòu)造一個(gè)建立在視差空間的全局能量代價(jià)函數(shù),然后利用全局優(yōu)化算法來(lái)求取使代價(jià)函數(shù)取得最小值時(shí)的視差值d。

立體匹配的全局能量代價(jià)函數(shù)包括匹配像素間的數(shù)據(jù)項(xiàng)Edata(d)、衡量圖像對(duì)中匹配像素點(diǎn)之間的相似性、像素間的視差平滑懲罰項(xiàng)Esmooth(d),約束相鄰像素間的不連續(xù)性。

E(d)=Edata(d)+λEsmooth(d)

(1)

式(1)的解空間為D(d1,d2,…,dn),其中n為行內(nèi)像素的個(gè)數(shù),di為第i個(gè)像素的視差值。通過(guò)最小化該函數(shù)得出匹配的視差圖Edata(d)如下:

Edata(d)=∑(DSI(x,y,d))

(2)

其中,DSI是視差的疊加代價(jià)。

Esmooth(d)=∑ρ(d(x,y)-d(x+1,y))+

ρ(d(x,y)-d(x,y+1))

(3)

其中,ρ是視差的單調(diào)遞增函數(shù),使得視差處處平滑。

現(xiàn)有的全局優(yōu)化動(dòng)態(tài)規(guī)劃匹配算法的一個(gè)問(wèn)題是在計(jì)算每個(gè)像素點(diǎn)的匹配代價(jià)后直接構(gòu)建包含有平滑約束的全局能量函數(shù),并未考慮匹配代價(jià)疊加,從而導(dǎo)致動(dòng)態(tài)規(guī)劃立體匹配中的橫條紋瑕疵問(wèn)題。另一個(gè)問(wèn)題是在圖像的邊緣處,深度是不連續(xù)的,在邊緣再平滑將會(huì)造成邊界的模糊。邊界模糊的很大原因是由于在此處的視差代價(jià)計(jì)算過(guò)大,不符合真實(shí)情況。對(duì)此,本文在原有的視差空間基礎(chǔ)上重新設(shè)計(jì)視差空間,根據(jù)降低平滑代價(jià)的思想優(yōu)化原有Esmooth,定義全新的平滑優(yōu)化項(xiàng)解決邊緣模糊問(wèn)題。

2 多鄰域非線性擴(kuò)散DP立體匹配算法

2.1概述

在立體匹配算法框架的基礎(chǔ)上,本文算法結(jié)構(gòu)主要分為3個(gè)部分。首先是使用相似性測(cè)度函數(shù)建立待匹配圖像對(duì)的視差空間;其次通過(guò)非線性擴(kuò)散方法對(duì)得到的視差空間進(jìn)行匹配代價(jià)聚合;最后用優(yōu)化邊緣的動(dòng)態(tài)規(guī)劃算法來(lái)建立全局匹配代價(jià)函數(shù)。

2.2視差空間圖像的建立

雖然立體匹配算法有多種,但是求解步驟通常包括原始匹配代價(jià)計(jì)算、匹配代價(jià)聚集、視差最優(yōu)化計(jì)算以及視差求精4個(gè)步驟。通過(guò)相似性測(cè)度函數(shù)計(jì)算原始匹配代價(jià),對(duì)圖像進(jìn)行不同視差下的灰度相似性測(cè)度,得到原始的視差空間圖像(DSI),如圖1所示。

圖1 視差空間圖像Fig.1 Disparity space image

DSI是三維空間中不同視差d下所對(duì)應(yīng)的x-y切面,該空間中的每個(gè)坐標(biāo)值(x,y,d)表示像素點(diǎn)(x,y)在視差為d時(shí)的匹配代價(jià)值C(x,y,d),該值可用式(4)表示:

C(x,y,d)=f(IL(x,y),IR(x,y))

(4)

其中函數(shù)f(…)表示相似性測(cè)度函數(shù)。

2.3基于多鄰域非線性擴(kuò)散的匹配代價(jià)聚合

由于包括IIDP方法在內(nèi)的動(dòng)態(tài)規(guī)劃算法并沒(méi)有考慮到行與行之間的像素約束關(guān)系,因此往往會(huì)出現(xiàn)比較明顯的橫向條紋,即動(dòng)態(tài)規(guī)劃立體匹配中的橫條紋瑕疵問(wèn)題。本文引入非線性擴(kuò)散方法解決立體匹配中的條紋問(wèn)題。

在圖像處理領(lǐng)域中,非線性擴(kuò)散可以用于圖像的平滑處理,可以進(jìn)行圖像鄰域的交互,從而擴(kuò)大局部數(shù)據(jù)的影響。擴(kuò)散過(guò)程中,灰度值在圖像中傳播,當(dāng)所有像素的灰度值相等時(shí)達(dá)到平衡。本文在Perona等[17]提出的將非線性擴(kuò)散與圖像內(nèi)容相聯(lián)系的PM模型的基礎(chǔ)上,對(duì)區(qū)域內(nèi)和區(qū)域間采取不同的濾波策略,從而得出DSI的擴(kuò)散規(guī)則如下:

DSI(x,y,d)=(1-4β)DSI(x,y,d)+

(5)

其中:DSI(x′,y′,d)是像素點(diǎn)(x,y)的多鄰域,即與點(diǎn)(x,y)直接相連的上、下、左、右以及對(duì)角線上的像素點(diǎn);β表示控制擴(kuò)散速度的參數(shù);N8定義如下:

N8={(-1,-1),(0,-1),(1,-1),(1,0),

(1,1),(0,1),(-1,1),(-1,0)}

(6)

將非線性擴(kuò)散匹配代價(jià)聚合方法加入視差計(jì)算框架中,構(gòu)建新的待優(yōu)化問(wèn)題模型。多鄰域非線性擴(kuò)散代價(jià)聚合可以考慮到行間像素點(diǎn)的約束信息,因此減少橫向條紋,提高匹配質(zhì)量。

2.4動(dòng)態(tài)規(guī)劃尋徑求解優(yōu)化的全局能量函數(shù)

因原有的平滑優(yōu)化項(xiàng)會(huì)導(dǎo)致邊緣模糊的問(wèn)題,在原有的視差函數(shù)ρ的基礎(chǔ)上與某個(gè)單調(diào)遞減函數(shù)乘積,利用在此區(qū)域降低平滑代價(jià)的思想優(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ù),在圖像的邊緣處,灰度值的變化較大,因此可以降低灰度值相差較大處的平滑代價(jià),優(yōu)化邊緣。

動(dòng)態(tài)規(guī)劃解決匹配問(wèn)題的思想是,在源圖與目標(biāo)圖中對(duì)應(yīng)的掃描線上尋找最小匹配代價(jià)路徑。設(shè)m、l、r分別代表上一階段的3種匹配狀態(tài):匹配、左圖可見(jiàn)(左遮擋)、右圖可見(jiàn)(右遮擋)。同理,設(shè)M、L、R分別表示目前狀態(tài)。在加入限定的約束條件后,排除雙遮擋(即左右均遮擋)的情形,那么匹配狀態(tài)轉(zhuǎn)換只有7種形式,如圖2所示。通過(guò)以上假設(shè),可將問(wèn)題轉(zhuǎn)化為動(dòng)態(tài)規(guī)劃的范疇[18]。

圖2 動(dòng)態(tài)規(guī)劃立體匹配算法的狀態(tài)變換形式Fig.2 Style of state transition of dynamic programming stereo matching algorithm

圖3所示為動(dòng)態(tài)規(guī)劃路徑的實(shí)例,在當(dāng)前的匹配狀態(tài)中,左右掃描線上的a、b、c、f、g、k6個(gè)像素點(diǎn)實(shí)現(xiàn)了正確匹配,d和e像素點(diǎn)發(fā)生了左遮擋,即在右掃描線上是不可見(jiàn)的,而h和i像素點(diǎn)在左掃描線上不可見(jiàn),即右遮擋點(diǎn)。

圖3 動(dòng)態(tài)規(guī)劃路徑尋找Fig.3 Routine of dynamic programming

用動(dòng)態(tài)規(guī)劃在源圖與目標(biāo)圖之間對(duì)應(yīng)掃描線上尋找最優(yōu)路徑的過(guò)程,就是求解某一視差分配的路徑或者最優(yōu)軌跡(即最優(yōu)視差分布)使得能量代價(jià)函數(shù)E(d)取值最小,即P(d)=arg min(E(d))。此時(shí)尋優(yōu)路徑搜索出的路徑包括了遮擋點(diǎn)和匹配的像素點(diǎn)的信息。在算法中,用檢測(cè)到的遮擋點(diǎn)的像素左最鄰近的點(diǎn)的視差填充遮擋點(diǎn),提高了匹配精度。填充的部分程序如下:

for (x=start;x!=end;x+=1)

{

intd= disp[x] ;

if (disp[x] ==occLabel)

disp[x]=oldd ;

else

oldd=d;

}

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

目前,立體匹配算法的主要評(píng)價(jià)標(biāo)準(zhǔn)是美國(guó)Middlebury College的Scharsitein提出的立體匹配評(píng)價(jià)標(biāo)準(zhǔn)和評(píng)價(jià)平臺(tái)[19],本文采用該平臺(tái)提供的標(biāo)準(zhǔn)立體圖像測(cè)試集Tsukuda圖像、Sawtooth圖像、Venus圖像和Map圖像檢驗(yàn)本文算法的效果,并依此進(jìn)行分析。

對(duì)于匹配所產(chǎn)生視差圖的評(píng)價(jià)主要通過(guò)定量衡量標(biāo)準(zhǔn)的誤匹配率(Percentage of Bad Matching,PBM)體現(xiàn),定義PBM為

(8)

其中:δd為視差容差,一般取值為1.0;N為圖像的像素點(diǎn)總數(shù)。該指標(biāo)反映了算法得到的視差值dc(x,y)與真實(shí)視差值dT(x,y)的誤差大于δd的像素個(gè)數(shù)在整幅圖像中的比例。

測(cè)試集圖像的源圖像、真實(shí)的視差圖、IIDP動(dòng)態(tài)規(guī)劃全局匹配算法得到的視差圖以及本文方法得到的視差圖對(duì)比結(jié)果如圖4所示。

圖4(a)～4(d)中,對(duì)于Tsukuba圖像,本文算法相比原有IIDP全局算法的誤匹配率降低了28%,在無(wú)紋理區(qū)域和非遮擋區(qū)域的誤匹配率分別降低了40%和31.8%,橫向條紋得到了明顯的改善,且修復(fù)了邊緣模糊的問(wèn)題。在圖4(e)～4(f)中,對(duì)于Sawtooth圖像,改進(jìn)后的全局算法相比原算法的誤匹配率下降了34%,而在無(wú)紋理區(qū)域和非遮擋區(qū)域的誤匹配率分別降低了48.8%和50%。在第3幅測(cè)試圖像Venus中,改進(jìn)的全局算法相比原有算法的誤匹配率降低了51.6%,在無(wú)紋理區(qū)域和非遮擋區(qū)域的無(wú)匹配率分別降低了58.5%和60.7%。同時(shí),在圖4(d)和圖4(i)兩幅深度圖中,有較為清晰的黑色或者灰色的紋理,代表此處是遮擋部分,可見(jiàn)本文算法能夠有效地識(shí)別遮擋區(qū)域。因而本文方法對(duì)帶有遮擋的圖像依然具有穩(wěn)定的匹配效果,相比于傳統(tǒng)動(dòng)態(tài)規(guī)劃算法,提高了匹配的魯棒性。在Map圖像中,改進(jìn)的全局算法相比原有的全局算法的誤匹配率降低了75.5%,在無(wú)遮擋區(qū)域和連續(xù)區(qū)域的誤匹配率分別降低了88.3%和62.7%。本文算法所獲得的視差圖都大幅度地提高了匹配的精度,且明顯改善了動(dòng)態(tài)規(guī)劃全局算法中的“橫條紋瑕疵”問(wèn)題,提高了匹配的準(zhǔn)確性,證明了算法的可行性和正確性。在匹配算法耗時(shí)方面,測(cè)試所用計(jì)算機(jī)的配置為Intel Core i3,4 G內(nèi)存,算法運(yùn)行時(shí)間如表1所示?？梢钥闯?本文的改進(jìn)算法在提高匹配精度的同時(shí),也保證了算法的執(zhí)行時(shí)間。

圖4 對(duì)標(biāo)準(zhǔn)圖像Tsukuda、Sawtooth、Venus和Map的實(shí)驗(yàn)結(jié)果對(duì)比Fig.4 Comparsion of experiment results for standard images of Tsukuda、Sawtooth、Venus and Map

表1 算法運(yùn)行時(shí)間

相似性測(cè)度函數(shù)中常用的有灰度差的平方(SD)、灰度差的絕對(duì)值(AD)等。本文用這兩種測(cè)度函數(shù)測(cè)評(píng)Middlebury提供的標(biāo)準(zhǔn)立體匹配數(shù)據(jù)集圖像,對(duì)比數(shù)據(jù)如表2所示。

從表2可以看出,在所有評(píng)價(jià)結(jié)果中,AD方法的結(jié)果完全優(yōu)于SD方法,因此,本文算法在原始匹

配代價(jià)計(jì)算選用AD方法,即

C(x,y,d)=|IL(x,y)-IR(x-d,y)|

(9)

為了更好地評(píng)測(cè)本文算法的立體匹配效果,將其與其他幾種著名的算法進(jìn)行對(duì)比,對(duì)比結(jié)果如表3所示。從表3可以看出,本文的全局算法對(duì)所有圖像的平均誤匹配率為5.60%,相比于IIDP全局算法的9.32%,誤匹配率降低了39.9%。

表3中還對(duì)比了Scanline 全局[16]、Di快速匹配[20]等全局立體匹配算法以及RTCensus[21]算法。綜合各個(gè)指標(biāo),本文算法不僅平均誤匹配率在所有算法中最低,且在圖像參數(shù)的11個(gè)指標(biāo)中有9項(xiàng)指標(biāo)排名第1,本文算法的表現(xiàn)均優(yōu)于其他全局算法和局部算法,體現(xiàn)出了更好的準(zhǔn)確精度和匹配質(zhì)量。

表2 SD、AD測(cè)度函數(shù)表現(xiàn)

表3 本文方法與IIDP全局算法的參數(shù)對(duì)比

4 結(jié) 論

在深入研究現(xiàn)有算法的基礎(chǔ)上,本文提出了一種基于多鄰域的非線性擴(kuò)散動(dòng)態(tài)規(guī)劃立體匹配算法,增加了多鄰域非線性擴(kuò)散進(jìn)行代價(jià)疊加計(jì)算,提高了算法整體的準(zhǔn)確性,明顯改善了傳統(tǒng)動(dòng)態(tài)算法的“橫條紋瑕疵”問(wèn)題,降低了誤匹配率。在視差優(yōu)化階段,在圖像的邊緣處降低平滑代價(jià),從而改善了邊緣模糊的問(wèn)題。本文算法與傳統(tǒng)動(dòng)態(tài)優(yōu)化算法相比,具有更準(zhǔn)確、效率更高、邊緣清晰的特點(diǎn)。針對(duì)不同測(cè)試圖像的實(shí)驗(yàn)結(jié)果表明,本文算法的平均誤匹配率為5.60%,算法的效果和精度遠(yuǎn)遠(yuǎn)高于改進(jìn)前的IIDP全局優(yōu)化算法,且匹配的穩(wěn)定性得到加強(qiáng)。與其他全局算法的對(duì)比結(jié)果表明,本文算法具有更好的精度和準(zhǔn)確度。

[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),柴穎,李逵.一種快速雙目視覺(jué)立體匹配算法[J].光學(xué)學(xué)報(bào),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

國(guó)家自然科學(xué)基金(61403140);上海市自然科學(xué)基金(13ZR1411500)

耿冬冬(1991-),男,碩士生,主要研究方向?yàn)閳D像處理、雙目視覺(jué)。E-mail:wintergeng@foxmail.com

羅 娜,E-mail:naluo@ecust.edu.cn