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

彭彬彬, 朱大奇

?

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

彭彬彬, 朱大奇

1引言

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

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

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

2算法的改進

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

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

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

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

圖3　線性生長示例圖Fig.3　The example of linear growth

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

圖4　跳躍生長示意圖Fig.4　The leaping growth diagram

2.2代價函數(shù)

匹配代價是整個立體匹配算法的基礎(chǔ),是對不同的視差進行灰度相似性測量。測量兩點差異性的主要有SAD(像素灰度差的絕對值和)函數(shù)和SSD(像素灰度差的絕對值平方和)函數(shù)。

SAD函數(shù):

(1)

SSD函數(shù):

(2)

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

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

(3)

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

3.1快速生長算法匹配步驟

快速生長算法匹配步驟如下:

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

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

(4)

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

3.2視差圖平滑與可靠度計算

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

(5)

閾值Ve為差錯能量的均值,表達式為:

Ve=αmean(Ed)

(6)

(7)

(8)

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

4實驗分析

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

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

圖5　Teddy原圖Fig.5　Teddy image

圖6　步長為2的跳躍生長匹配Fig.6　Stereo matching:step 2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5總結(jié)

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

參考文獻:

[1]張元元,張麗艷,楊博文.基于雙目立體視覺的無線柔性坐標測量系統(tǒng)[J].儀器儀表學(xué)報,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].計算機工程與設(shè)計,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é)報:自然科學(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]郭龍源,孫長銀,楊萬扣,等.SIFT特征點引導(dǎo)的區(qū)域立體匹配算法[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].電子測量與儀器學(xué)報,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é)報,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].計算機科學(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-),重慶人,碩士研究生,主要研究方向為圖像分析與視頻處理。

朱大奇男(1964-),安徽安慶人,教授,博士生導(dǎo)師,主要研究方向為智能故障診斷、水下機器人路徑規(guī)劃與控制。

(上海海事大學(xué) 水下機器人與智能系統(tǒng)實驗室,上海201306)

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

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

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

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

中圖分類號：TP 391

文獻標識碼：A