何人杰
摘 要:匹配算法是雙目立體視覺(jué)中關(guān)鍵技術(shù)之一。這里討論雙目立體視覺(jué)區(qū)域局部匹配的相似性測(cè)度函數(shù)、局部相關(guān)匹配算法,并分析其復(fù)雜度,進(jìn)而提出模板滑動(dòng)的匹配算法。在VC++平臺(tái)上,通過(guò)雙相機(jī)實(shí)驗(yàn)系統(tǒng)的標(biāo)準(zhǔn)測(cè)試圖及實(shí)際場(chǎng)景圖對(duì)所提方法進(jìn)行驗(yàn)證。分析和實(shí)驗(yàn)結(jié)果都表明了該改進(jìn)算法的有效性和快速性。
關(guān)鍵詞:雙目立體視覺(jué);區(qū)域相關(guān);立體匹配;標(biāo)準(zhǔn)測(cè)試圖
中圖分類號(hào):TP391文獻(xiàn)標(biāo)識(shí)碼:A
文章編號(hào):1004-373X(2009)12-068-03
Improvement of Regional Related Match Algorithm for
Binocular Stereo Vision and Its Implementation
HE Renjie
(Electronics and Information School,Northwestern Polytechnical University,Xi′an,710129,China)
Abstract:Match algorithm is one of key techniques in the binocular stereo vision system.The similarity functions,the regional related match algorithms for Binocular stereo vision are discussed and the algorithmic complexity is analyzed.Moreover,a new improved regional related match algorithm by sliding pattern plate is proposed to decrease the matching time and a test software is designed by using VC++ and OPEN-CV.A number of experiments are carried out through the two-camera system and the standard test images as well as practical sense images.The analytical and experimental results show that the improved method is effective and its matching time is decreased greatly.
Keywords:binocular stereo vision;regional related;stereo match;standard test image
0 引 言
立體視覺(jué)是計(jì)算機(jī)視覺(jué)的一個(gè)重要分支,主要研究如何借助成像技術(shù)從圖像中獲取場(chǎng)景中物體的三維信息[1-3] 。立體視覺(jué)的基本方法是從兩個(gè)或者多個(gè)視點(diǎn)去觀察同一場(chǎng)景,獲得在不同視角下的一組圖像;然后通過(guò)三角測(cè)量原理獲得不同圖像中對(duì)應(yīng)像素間的視差,并從中獲得深度信息,進(jìn)而與平面信息整合形成立體圖像。立體匹配是立體視覺(jué)算法中最重要也是最困難的部分。
根據(jù)匹配基元的不同,現(xiàn)有的立體匹配方法可大致分為三類:基于特征的匹配[4,5],基于區(qū)域的匹配[6]和基于相位的匹配[7]。
本文重點(diǎn)研究雙目視覺(jué)立體匹配中基于區(qū)域的局部匹配算法,對(duì)基于SAD(Sum of Absolute Difference)的區(qū)域匹配算法通過(guò)模板滑動(dòng)進(jìn)行了改進(jìn)。經(jīng)分析和多次實(shí)驗(yàn)結(jié)果表明,該改進(jìn)算法具有有效性和快速性。
1 雙目立體視覺(jué)區(qū)域局部匹配的理論基礎(chǔ)
1.1 相似性測(cè)度函數(shù)
匹配算法的實(shí)質(zhì)就是估計(jì)待匹配點(diǎn)和候選匹配點(diǎn)之間的相似性程度,評(píng)價(jià)這種相似性程度度量方法有多種。由于單個(gè)像素點(diǎn)所包含的信息太少,因而只依據(jù)單個(gè)像素點(diǎn)是的信息建立度量方法可靠性較差。為了提高相似性度量方法的可靠性,一般需要在匹配點(diǎn)上的一個(gè)小鄰域內(nèi)的像素點(diǎn)集合中進(jìn)行。
表1列出了目前幾種主要的相似性測(cè)度函數(shù)[6]。其中,IL(x,y),IR(x,y)分別代表左右圖像中像素坐標(biāo)(x,y)處的灰度值;IL(x,y),IR(x,y)分別表示左右圖中以坐標(biāo)(x,y)為中心,在窗口范圍U內(nèi)像素灰度的平均值。由于SAD相似性測(cè)度函數(shù)在時(shí)間以及匹配質(zhì)量方面較其他測(cè)度函數(shù)更具有優(yōu)勢(shì),且實(shí)現(xiàn)較簡(jiǎn)單[8]。這里研究選擇SAD作為局部相關(guān)匹配算法的相似性測(cè)度函數(shù)。
1.2 局部相關(guān)匹配算法原理
局部相關(guān)匹配算法是以基準(zhǔn)圖像中待匹配點(diǎn)為中心像素來(lái)創(chuàng)建一個(gè)大小為n×n的矩形窗,由該窗口內(nèi)的像素灰度分布來(lái)表征該像素。在第二幅圖像中,沿極線在視差范圍內(nèi)取出與基準(zhǔn)點(diǎn)鄰域同樣大小為n×n的像素鄰域,依次與匹配點(diǎn)的窗口進(jìn)行比較,最大相似性對(duì)應(yīng)的點(diǎn)就是最佳匹配。整個(gè)匹配過(guò)程如圖1所示。
表1 幾種相似性測(cè)度函數(shù)
名稱公式
SAD∑(i,j)∈U|IL(x+i,y+j)-IR(x+dx+i,y+j)|
ZSAD∑(i,j)∈U|[IL(x+i,y+j)-IR(x,y)]-
[IR(x+dx+i,y+j)-IR(x+dx,y)]|
SSD∑(i,j)∈U[IL(x+i,y+j)-IR(x+dx+i,y+j)]2
ZSSD∑(i,j)∈U[IL(x+i,y+j)-IL(x,y)]-
[IR(x+dx+i,y+j)-IR(x+dx,y)]2
SSD-N∑(i,j)∈U[IL(x+i,y+j)-IR(x+dx+i,y+j)]2∑(i,j)∈UIL(x+i,y+j)2∑(i,j)∈UIR(x+dx+i,y+j)2
SCP∑(i,j)∈UIL(x+i,y+j)IR(x+dx+i,y+j)
圖1 局部相關(guān)算法原理示意圖
1.3 局部相關(guān)匹配算法的時(shí)間復(fù)雜度
在圖1(a)中坐標(biāo)為(x,y)的像素點(diǎn),算法要計(jì)算圖1(b)中所有相關(guān)像素的相似性。根據(jù)極線約束以及視差約束,在圖1(b)中只需計(jì)算同一極線上,視差范圍內(nèi)的像素相似性即可,需要的計(jì)算量為:
T(x,y)=dmaxn2(1)
式中:n為正方形窗口邊長(zhǎng);dmax為最大視差。設(shè)W為圖像的寬度;H為圖像的高度,對(duì)于整幅圖片,全部相似性的計(jì)算量為:
T=∑0≤i 易知,局部相關(guān)匹配算法的時(shí)間復(fù)雜度為O(WHdmaxn2)。 1.4 局部相關(guān)匹配算法的改進(jìn) 若假設(shè)匹配窗口的邊長(zhǎng)為2n+1,對(duì)于每行像素,其相似性測(cè)度函數(shù)為P(x,y,d)=∑ni=-n|IL(x+i,y)-IR(x+i+d,y)|;在模板向右滑動(dòng)時(shí),P(x+1,y,d)可由之前的計(jì)算結(jié)果得到,有迭代公式: P(x+1,y,d)=P(x,y,d)+[|IL(x+n+1,y)- IR(x+n+1+d,y)|-|IL(x-n,y)- IR(x-n+d,y)|](3) 即在模板滑動(dòng)時(shí),不需要重新計(jì)算整個(gè)窗口的SAD,而只需計(jì)算新的一列SAD。分析可知,改進(jìn)后算法的時(shí)間復(fù)雜度由O(WHdmaxn2)降為O(WHdmaxn),算法實(shí)時(shí)性有了較大提升。
2 雙目立體視覺(jué)區(qū)域局部匹配算法的實(shí)現(xiàn)
2.1 實(shí)驗(yàn)環(huán)境
該研究的實(shí)驗(yàn)主要是通過(guò)計(jì)算機(jī)編程實(shí)現(xiàn)區(qū)域局部匹配算法,并在雙相機(jī)系統(tǒng)上利用標(biāo)準(zhǔn)和實(shí)際場(chǎng)景圖像進(jìn)行驗(yàn)證性實(shí)驗(yàn)的。以VC++ 6.0及OPENCV為編程環(huán)境,完成驗(yàn)證軟件設(shè)計(jì)。
該研究的驗(yàn)證實(shí)驗(yàn)使用了西安交通大學(xué)系統(tǒng)工程所的實(shí)驗(yàn)設(shè)備(如圖2所示)。兩只攝像機(jī)平行放置,其位置姿態(tài)參數(shù)已由標(biāo)定結(jié)果給出,如表2所示。
圖2 試驗(yàn)系統(tǒng)
表2 相機(jī)標(biāo)定參數(shù)表(以像素為單位)
參數(shù)指標(biāo)左相機(jī)右相機(jī)
焦距699.85696.15
相機(jī)中心[392.34 283.94][389.26 308.18]
畸變[-0.270 20 0.454 48][-0.239 75 0.256 22]
旋轉(zhuǎn)角/radα=0.013 77,β=0.001 07,γ=0.000 38
相對(duì)位移/mmt1=87.921,t2=1.205,t3=4.980
攝像機(jī)與處理計(jì)算機(jī)之間通過(guò)雙1394總線連接,計(jì)算機(jī)中配備2塊64位PCI-1394卡,以適應(yīng)攝像機(jī)高速圖像流的要求。攝像機(jī)的主要參數(shù)如表3所示。
表3 攝像機(jī)參數(shù)
攝像機(jī)特性參數(shù)
CCD傳感器Sony Progressive Scan CCDs
CCD最大像素1 624×1 224
像素大小4.4 μm×4.4 μm
支持圖像大小320×240(30),640×480(30),800×600(30),1 600×1 200(15)
快門0.01~66.63 ms
圖像輸出方式雙1394總線輸出
2.2 軟件設(shè)計(jì)流程圖
系統(tǒng)算法流程圖如圖3所示。
圖3 系統(tǒng)算法流程圖
2.3 實(shí)驗(yàn)結(jié)果
部分實(shí)驗(yàn)結(jié)果如圖4所示。
圖4 實(shí)驗(yàn)結(jié)果
由圖4可知[10],實(shí)驗(yàn)得到的圖片較好地完成了對(duì)現(xiàn)實(shí)場(chǎng)景中的匹配,可以較直接地從所得視差圖中獲得物體的深度信息。
同時(shí),圖像邊緣處的匹配精度受到圖像邊界的影響,誤差較大,真實(shí)場(chǎng)景圖片中噪聲較大,導(dǎo)致誤匹配較多。如何減少誤差,提高精度是現(xiàn)在和今后重點(diǎn)考慮的問(wèn)題之一。
3 結(jié) 語(yǔ)
這里對(duì)雙目立體視覺(jué)中的區(qū)域局部匹配算法進(jìn)行討論,對(duì)現(xiàn)有SAD算法進(jìn)行了改進(jìn),較顯著地提高了匹配速度。在實(shí)驗(yàn)平臺(tái)上較好地完成了對(duì)標(biāo)準(zhǔn)圖像及現(xiàn)實(shí)場(chǎng)景圖像的視差圖獲取,驗(yàn)證了算法的有效性和快速性。
參考文獻(xiàn)
[1]章毓晉.圖像工程(下冊(cè))圖像理解[M].2版.北京:清華大學(xué)出版社,2007.
[2]何明一,衛(wèi)保國(guó).數(shù)字圖像處理[M].北京:科學(xué)出版社,2008.
[3]游素亞.立體視覺(jué)研究的現(xiàn)狀與進(jìn)展[J].中國(guó)圖像圖形學(xué)報(bào),1997,2(1):1-2.
[4]Hajar Sadeghi,Payman Moallem,Monadjemi S A.Feature Based Dense Stereo Matching using Dynamic Programming and Color[J].International Journal of Computational Intelligence,2004,4(3):179-186.
[5]高峰,文貢堅(jiān),呂金建.一種準(zhǔn)自動(dòng)高精度圖像配準(zhǔn)算法[J].現(xiàn)代電子技術(shù),2007,30(6):56-59.
[6]Kuk Jin Yoon,In So Kweon.Adaptive Support-Weight Approach for Correspondence Search[A].APRIL[C].2006,28(4):650-655.
[7]徐奕,周軍,周源華.立體視覺(jué)匹配技術(shù)[J].計(jì)算機(jī)工程與應(yīng)用,2003,39(15):388-392.
[8]Cyganek B,Borgosz J.A Comparative Study of Performance and Implementation of Some Area-based Stereo Algorithms[A].CAIP[C].2001,21(24):709-716.
[9]夏永泉.計(jì)算機(jī)視覺(jué)中雙目匹配相關(guān)技術(shù)的研究[D].南京:南京理工大學(xué),2007.
[10]Middlebury College Stereo Vision Research[EB/OL].http://cat.middlebury.edu,2008.