彭彬彬, 朱大奇

?

基于區(qū)域快速生長(zhǎng)的雙目視覺立體匹配算法研究

彭彬彬, 朱大奇

1引言

雙目視覺[1]是計(jì)算機(jī)視覺的一個(gè)重要分支,在機(jī)器人導(dǎo)航、無人車駕駛、醫(yī)學(xué)影像重建等領(lǐng)域有著重要運(yùn)用。雙目視覺即由不同位置的兩臺(tái)攝像機(jī)拍攝同一幅場(chǎng)景,通過計(jì)算空間點(diǎn)在兩幅圖像中的視差獲得該點(diǎn)的三維坐標(biāo)值,圖1為平行雙目視覺示意圖。立體匹配[2-5]作為雙目視覺的關(guān)鍵問題,匹配的本質(zhì)是尋求同一空間景物在不同觀察點(diǎn)下投影圖像的像素間的一一對(duì)應(yīng)關(guān)系,并由此得到相應(yīng)的視差圖像[6]。匹配算法根據(jù)約束方式的不同大致分為2類[7]:一類為局部匹配算法,包括基于區(qū)域相關(guān)的立體匹配算法、基于特征檢測(cè)的立體匹配算法和梯度法[8];另一類為全局最優(yōu)算法[9-10],包括動(dòng)態(tài)規(guī)劃法、圖割法、置信度傳播算法等[11]。

圖1　平行雙目視覺示意圖Fig.1　Schematic diagram of parallel binocular vision

現(xiàn)有的立體匹配算法都是基于Marr提出的立體視覺理論[12]。雖然區(qū)域匹配[13]較全局匹配速度有較大的提高,但是仍然無法滿足雙目立體視覺導(dǎo)航系統(tǒng)所需要的實(shí)時(shí)性。對(duì)此,本文利用區(qū)域生長(zhǎng)技術(shù)進(jìn)行全局最優(yōu)化,并嘗試改進(jìn)生長(zhǎng)技術(shù),快速實(shí)現(xiàn)局部區(qū)域的立體匹配,進(jìn)而獲取可靠視差圖。

2算法的改進(jìn)

2.1基于區(qū)域的快速生長(zhǎng)算法

區(qū)域生長(zhǎng)的思路源自圖像分割[14]中的區(qū)域增長(zhǎng)算法。圖2是區(qū)域生長(zhǎng)分割示意圖。輸入圖像基于根點(diǎn)和預(yù)先設(shè)置的生長(zhǎng)條件進(jìn)行生長(zhǎng),在遍歷整幅圖像后,把輸入圖像分割成(R1-R6)六個(gè)不同區(qū)域。

圖2　區(qū)域生長(zhǎng)分割示意圖Fig.2　Schematic diagram of region growing segmentation

圖3是一個(gè)線性生長(zhǎng)示意圖。如圖3(a)所示為原圖,圖像的第一個(gè)像素為根點(diǎn)(紅色字體),門限為2,由第一個(gè)根點(diǎn)線性生長(zhǎng)后在像素為4(紅色字體)的點(diǎn)停止了,如圖3(b)所示,此時(shí)選擇此像素點(diǎn)為根點(diǎn)繼續(xù)生長(zhǎng),如圖3(c)所示,直至遍歷全圖。

圖3　線性生長(zhǎng)示例圖Fig.3　The example of linear growth

由Marr理論的視差連續(xù)性假設(shè):場(chǎng)景中相鄰像素的視差不會(huì)出現(xiàn)突變。由此假設(shè)可以利用跳躍式生長(zhǎng)法進(jìn)一步加速生長(zhǎng)算法。如圖4,跳躍2個(gè)像素點(diǎn)后,第4個(gè)點(diǎn)仍與根點(diǎn)相關(guān),則把這3個(gè)點(diǎn)都?xì)w入生長(zhǎng)區(qū)域;若第7個(gè)點(diǎn)與根點(diǎn)不相關(guān),則把生長(zhǎng)區(qū)域的下一個(gè)點(diǎn)作為根點(diǎn)進(jìn)行生長(zhǎng)。

圖4　跳躍生長(zhǎng)示意圖Fig.4　The leaping growth diagram

2.2代價(jià)函數(shù)

匹配代價(jià)是整個(gè)立體匹配算法的基礎(chǔ),是對(duì)不同的視差進(jìn)行灰度相似性測(cè)量。測(cè)量?jī)牲c(diǎn)差異性的主要有SAD(像素灰度差的絕對(duì)值和)函數(shù)和SSD(像素灰度差的絕對(duì)值平方和)函數(shù)。

SAD函數(shù):

(1)

SSD函數(shù):

(2)

上述公式中,IL(x,y)和IR(x-d,y)分別表示左圖和右圖的像素灰度值。

基于SSD函數(shù)思想,對(duì)于彩色圖像中m*n的塊匹配窗口,構(gòu)造差錯(cuò)能量函數(shù)表達(dá)式為:

(3)

3基于區(qū)域的快速生長(zhǎng)立體匹配

3.1快速生長(zhǎng)算法匹配步驟

快速生長(zhǎng)算法匹配步驟如下:

步驟1:在圖像中不屬于任何增長(zhǎng)區(qū)域的行中尋找根點(diǎn)(x,y)。

步驟2:應(yīng)用式(4)計(jì)算與根節(jié)點(diǎn)相鄰跳躍點(diǎn)的誤差能量,如果它低于設(shè)定的能量誤差閾值D,把這個(gè)點(diǎn)以及跳躍的點(diǎn)加入到視差區(qū)域,否則,返回1尋找新的根節(jié)點(diǎn)。其中l(wèi)是跳躍步長(zhǎng)。

(4)

步驟3:重復(fù)步驟1、2對(duì)圖像的每一行進(jìn)行計(jì)算,當(dāng)整幅圖片都被遍歷時(shí),算法停止。生長(zhǎng)出的視差區(qū)構(gòu)成視差圖d(i,j)。

3.2視差圖平滑與可靠度計(jì)算

在匹配過程中,由于會(huì)受到局部不明確圖像區(qū)域(遮擋區(qū)域、弱紋理區(qū)域)的影響,降低了獲得視差圖的可靠性。為了增加視差圖的可靠性,對(duì)差錯(cuò)能量通過設(shè)置閾值Ve加以過濾,如式(5)所示。

(5)

閾值Ve為差錯(cuò)能量的均值,表達(dá)式為:

Ve=αmean(Ed)

(6)

(7)

(8)

由式(7)和式(8)可以得出,當(dāng)視差圖的平均誤差能量越小時(shí),Rd的值越大,則視差圖越可靠。

4實(shí)驗(yàn)分析

針對(duì)匹配質(zhì)量和匹配時(shí)間問題,本文選用Middlebury大學(xué)立體圖像數(shù)據(jù)集中的Teddy立體圖像對(duì)進(jìn)行實(shí)驗(yàn)仿真。匹配窗口為(1*5),攝像機(jī)焦距f=30,攝像機(jī)之間的間距T=20,α=1,dmax=40。

圖5為兩幅同一物體的立體圖像,圖6為跳躍步長(zhǎng)為2的快速匹配結(jié)果,閾值D=70。

圖5　Teddy原圖Fig.5　Teddy image

圖6　步長(zhǎng)為2的跳躍生長(zhǎng)匹配Fig.6　Stereo matching:step 2

4.1各算法在不同閾值的視差圖比較

(1) 閾值D=20匹配效果

圖7(a)為區(qū)域生長(zhǎng)法的視差圖,圖7(b)為線性生長(zhǎng)法的視差圖,圖7(c)-(e)分別為跳躍生長(zhǎng)法步長(zhǎng)為2、3、4時(shí)的視差圖。實(shí)驗(yàn)參數(shù)分別為n=1,m=5,T=20,dα=1,dmax=40。分別計(jì)算5中方法的匹配時(shí)間和可靠度數(shù)值,見表1。

圖7　閾值D=20的實(shí)驗(yàn)結(jié)果Fig.7　Results:Threshold 20

匹配時(shí)間s可靠度Rd區(qū)域生長(zhǎng)8.790.005729線性生長(zhǎng)2.980.004721跳躍步長(zhǎng)21.990.004371跳躍步長(zhǎng)31.590.003813跳躍步長(zhǎng)41.370.003522

由圖7和表1可以看出,區(qū)域生長(zhǎng)算法的可靠度最高,但是耗時(shí)也最大,匹配時(shí)間為8.79秒,為最小匹配時(shí)間6倍以上,無法滿足雙目立體視覺導(dǎo)航系統(tǒng)所需的實(shí)時(shí)性要求。而跳躍生長(zhǎng)算法匹配時(shí)間較小,實(shí)時(shí)性高,但相對(duì)來說可靠度減低;可見跳躍步長(zhǎng)越大匹配時(shí)間越少,可靠度越 低。

(2) 閾值D=60匹配效果

圖8(a)為區(qū)域生長(zhǎng)法的視差圖,圖8(b)為線性生長(zhǎng)法的視差圖,圖8(c)-(e)分別為跳躍生長(zhǎng)法步長(zhǎng)為2、3、4時(shí)的視差圖。

圖8　閾值D=60的實(shí)驗(yàn)結(jié)果Fig.8　Results:Threshold 60

(3) 閾值D=90匹配結(jié)果

圖9(a)為區(qū)域生長(zhǎng)法的視差圖,圖9(b)為線性生長(zhǎng)法的視差圖,圖9(c)-(e)分別為跳躍生長(zhǎng)法步長(zhǎng)為2、3、4時(shí)的視差圖。

表2為三種跳躍生長(zhǎng)算法相對(duì)于線性生長(zhǎng)算法的可靠度與實(shí)時(shí)性對(duì)比,從中可以看出,改進(jìn)算法較線性生長(zhǎng)法的匹配時(shí)間節(jié)約了20%以上。跳躍步長(zhǎng)為2時(shí),在三個(gè)不同閾值的實(shí)驗(yàn)下可靠度下降最多為7.41%,此時(shí)時(shí)間節(jié)約了33.22%;下降最少時(shí)為3.03%,此時(shí)時(shí)間節(jié)約了20.59%。

圖9　閾值D=90的實(shí)驗(yàn)結(jié)果Fig.9　Results:Threshold 90

閾值對(duì)比跳躍步長(zhǎng)2跳躍步長(zhǎng)3跳躍步長(zhǎng)4閾值D=20時(shí)間節(jié)約%33.2246.6454.03可靠度下降%7.4119.2325.40閾值D=60時(shí)間節(jié)約%28.2636.2339.86可靠度下降%5.5610.9615.30閾值D=90時(shí)間節(jié)約%20.5924.5029.41可靠度下降%3.035.798.76

但是步長(zhǎng)為3和步長(zhǎng)為4兩種算法可靠度有大幅下降,這是因?yàn)樘S式生長(zhǎng)步長(zhǎng)越長(zhǎng)越省時(shí),但是過長(zhǎng)的步長(zhǎng)會(huì)影響匹配的可靠性,導(dǎo)致有些點(diǎn)無法匹配或者錯(cuò)誤匹配。實(shí)驗(yàn)表明,跳躍步長(zhǎng)為2時(shí)的生長(zhǎng)算法有較高的可靠度,并大大縮短了匹配時(shí)間,我們選擇跳躍步長(zhǎng)2算法為最佳算法?？梢钥闯霰疚奶岢龅奶S步長(zhǎng)2生長(zhǎng)算法具有很高的實(shí)時(shí)性和較好的可靠性,適用于實(shí)時(shí)機(jī)器人雙目視覺導(dǎo)航系統(tǒng)。

4.2跳躍步長(zhǎng)2生長(zhǎng)算法在不同閾值下與時(shí)間、可靠度的關(guān)系

為了進(jìn)一步了解閾值D與匹配時(shí)間消耗、視差可靠性之間的關(guān)系,選取閾值范圍(0,120),分別計(jì)算出跳躍步長(zhǎng)2算法的時(shí)間消耗和可靠性。圖10給出了時(shí)間消耗和可靠度的曲線圖。由圖10可以看出:在閾值D小于60時(shí),時(shí)間曲線大幅下降,等于60時(shí)匹配時(shí)間已小于1 s,之后下降變得平緩。隨著閾值的不斷增加,時(shí)間消耗越來越小。同時(shí)可以看出在閾值D大于20時(shí),視差圖的可靠性大幅增大,之后增長(zhǎng)變得平緩,在60-80之間可靠度最佳,D=70時(shí)達(dá)到最大值,隨后逐步下降。這是由于閾值D較小時(shí),生長(zhǎng)出來的區(qū)域過小導(dǎo)致匹配精確度不高,而閾值過大時(shí),生長(zhǎng)區(qū)域的能量誤差過大,也會(huì)導(dǎo)致匹配可靠度不高。因此,閾值在60-80之間時(shí)跳躍步長(zhǎng)為2的生長(zhǎng)匹配算法性能最佳,不僅匹配時(shí)間較小,而且可靠度也比較高,是一種理想的雙目視覺立體匹配算法。

圖10　跳躍步長(zhǎng)2不同閾值的時(shí)間比較和可靠度比較Fig.10　 Step 2 algorithm:comparison of time and reliability under different thresholds

5總結(jié)

本文提出了一種基于區(qū)域的實(shí)時(shí)立體匹配改進(jìn)算法。通過線性生長(zhǎng)和跳躍式快速生長(zhǎng)法在可靠度沒有明顯下降的境況下大大提高了匹配速度。通過實(shí)驗(yàn)對(duì)比得出結(jié)論:在步長(zhǎng)為2時(shí)跳躍式生長(zhǎng)法的時(shí)間消耗和可靠度都達(dá)到最佳。在閾值達(dá)到60時(shí),它的時(shí)間消耗已經(jīng)小于1 s,而此時(shí)卻有著較高的可靠度,并快速匹配生成了稠密視差圖?；诟倪M(jìn)算法,雙目立體視覺導(dǎo)航系統(tǒng)的實(shí)時(shí)性將大大提高。

參考文獻(xiàn):

[1]張?jiān)?張麗艷,楊博文.基于雙目立體視覺的無線柔性坐標(biāo)測(cè)量系統(tǒng)[J].儀器儀表學(xué)報(bào),2010,31(7):1613-1619.

ZHANG Yuanyuan,ZHANG Liyan,YANG Bowen.Protabla coordinate measurement system based on binocular stereo visio[J].Chinese Journal of Scientific Instrument,2010,31(7):1613-1619.

[2]Bai L,Jing X,Yue J,et al.A Weighted Color Image Stereo Matching Algorithm with Edge-Based Adaptive Window[C].2013 Seventh International Conference on Image and Graphics (ICIG),Qingdao,China,July 26-28,2013:539-544.

[3]原飛,范勇,劉暢,等.基于大窗口的自適應(yīng)立體匹配[J].計(jì)算機(jī)工程與設(shè)計(jì),2013,34(7):2441-2444.

YUAN Fei,FAN Yong,LIU Chang,et al.Adaptive stereo matching based on large window[J],Computer Engineering and Design,2013,34(7):2441-2444.

[4]霍智勇,朱秀昌.基于區(qū)域的立體匹配算法研究[J].南京郵電大學(xué)學(xué)報(bào):自然科學(xué)版,2011,31(3):44-49.

HUO Zhiyong,ZHU Xiuchang.Research of Region Based Stereo Matching Algorithms[J].Journal of Nanjing University of Posts and Telecommunications (Natural Science),2011,31(3):44-49.

[5]郭龍?jiān)?孫長(zhǎng)銀,楊萬扣,等.SIFT特征點(diǎn)引導(dǎo)的區(qū)域立體匹配算法[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(4):23-25,38.

GUO Longyuan,SUN Changyin,YANG Wankou,et al.Area-based stereo matching based on SIFT feature guidance[J].Computer Engineering and Applications,2013,49(4):23-25,38.

[6]Alvarez L,Deriche R,Sanchez J,et al.Dense disparity map estimation respecting image discontinuities:A PDE and scale-space based approach[J].Journal of Visual Communication and Image Representation,2002,13(1):3-21.

[7]Brown M Z,Burschka D,Hager G D.Advances in computational stereo[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2003,25(8):993-1008.

[8]王進(jìn)花,曹潔,李宇,等.一種基于特征融合的點(diǎn)特征目標(biāo)跟蹤算法[J].電子測(cè)量與儀器學(xué)報(bào),2010,24(6):536-541.

WANG Jinhua,CAO Jie,LI Yu,et al.Object tracking algorithm based on the feature fusion points[J].Journal of Electronic Measurement and Instrument,2010,24(6):536-541.

[9]石紅艷.基于雙目視覺的立體匹配算法的研究[D].燕山大學(xué),2013.

SHI Hongyan.The research on stereo matching algorithm based on binocular vision[D].Yanshan University.2013.

[10]王洋,范劍英,林立軍,等.物流配送路徑優(yōu)化理論在立體匹配技術(shù)中的應(yīng)用研究[J].哈爾濱理工大學(xué)學(xué)報(bào),2011,16(2):24-28.

WANG Yang,FAN Jianying,LIN Li-jun,et al.Optimization of Logistics Dispatching Route Theory Application and Research in Solid Matching Technic[J].Journal of Harbin University of Science and Technology,2011,16(2):24-28.

[11]Zhou Z,Li G,Fan J,et al.A new stereo matching algorithm based on image segmentation[C].2012 International Conference on Information and Automation (ICIA),Shenyang,China,6-8 June 2012:861-866.

[12]Marr D,Poggio T.A computational theory of human stereo vision[J].Proceedings of the Royal Society of London.Series B.Biological Sciences,1979,204(1156):301-328.

[13]張彥峰,黃向生,李杭,等.基于漸進(jìn)可靠點(diǎn)生長(zhǎng)的散斑圖快速立體匹配[J].計(jì)算機(jī)科學(xué),2014,41(z1):143-146.

ZHANG Yanfeng,HUANG Xiangsheng,LI Hang,et al.Fast Stereo Matching Based on Progressive Reliable Point Growing Matching for Speckle Pattern Images[J].Computer Science,2014,41(z1):143-146.

[14]Zhang L,Ji Q.A Bayesian Network Model for Automatic and Interactive Image Segmentation[J].IEEE Transactions on Image Processing,2011,20(9):2582-2593.

彭彬彬男(1989-),重慶人,碩士研究生,主要研究方向?yàn)閳D像分析與視頻處理。

朱大奇男(1964-),安徽安慶人,教授,博士生導(dǎo)師,主要研究方向?yàn)橹悄芄收显\斷、水下機(jī)器人路徑規(guī)劃與控制。

(上海海事大學(xué) 水下機(jī)器人與智能系統(tǒng)實(shí)驗(yàn)室,上海201306)

摘要：立體匹配是立體視覺的重要研究?jī)?nèi)容之一,視差圖的可靠性和計(jì)算復(fù)雜度直接影響了立體視覺的性能。針對(duì)目前雙目視覺立體匹配算法計(jì)算量過大,本文提出了一種基于快速生長(zhǎng)的區(qū)域立體匹配算法,應(yīng)用差錯(cuò)能量作為匹配代價(jià)分別進(jìn)行線性生長(zhǎng)和跳躍式生長(zhǎng),遍歷整幅圖像后得到視差圖,并采用均值濾波器濾除不可靠視差。實(shí)驗(yàn)表明該算法在保證較好可靠性的同時(shí)具有很好的實(shí)時(shí)性。

關(guān)鍵詞：立體匹配; 快速生長(zhǎng); 視差圖; 差錯(cuò)能量

Binocular Vision’s Stereo Matching Algorithm Research Based on Regional Rapid GrowthPENGBinbin,ZHUDaqi

(Laboratory of Underwater Vehicles and Intelligent System,Shanghai Maritime University,Shanghai 201306,China)

Abstract：Image stereo matching is one of the key research topics in stereo vision.Reliability of disparity maps and computational cost of algorithm directly affect the performance of stereo vision.Because the binocular vision stereo matching algorithm is complex,in this paper,a region matching algorithm based on the rapid growing is proposed.In the algorithm,the error energy is used as the matching cost for the linear growing and leaping growth.After traversing the entire image the disparity map is obtained,and the mean filter is used to filter out unreliable disparity.Experiments show that the algorithm ensures reliability and has good real-time performance.

Key words：stereo matching; rapid growing; disparity map; error energy

基金項(xiàng)目：上海市科委創(chuàng)新行動(dòng)計(jì)劃 (14JC1402800);國(guó)家自然科學(xué)基金青年項(xiàng)目(61503239)

中圖分類號(hào)：TP 391

文獻(xiàn)標(biāo)識(shí)碼：A