雙目立體視覺區(qū)域局部匹配算法的改進(jìn)及其實現(xiàn)

何人杰

摘 要:匹配算法是雙目立體視覺中關(guān)鍵技術(shù)之一。這里討論雙目立體視覺區(qū)域局部匹配的相似性測度函數(shù)、局部相關(guān)匹配算法,并分析其復(fù)雜度,進(jìn)而提出模板滑動的匹配算法。在VC++平臺上,通過雙相機實驗系統(tǒng)的標(biāo)準(zhǔn)測試圖及實際場景圖對所提方法進(jìn)行驗證。分析和實驗結(jié)果都表明了該改進(jìn)算法的有效性和快速性。

關(guān)鍵詞:雙目立體視覺;區(qū)域相關(guān);立體匹配;標(biāo)準(zhǔn)測試圖

中圖分類號:TP391文獻(xiàn)標(biāo)識碼:A

文章編號: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 引 言

立體視覺是計算機視覺的一個重要分支,主要研究如何借助成像技術(shù)從圖像中獲取場景中物體的三維信息[1-3] 。立體視覺的基本方法是從兩個或者多個視點去觀察同一場景,獲得在不同視角下的一組圖像;然后通過三角測量原理獲得不同圖像中對應(yīng)像素間的視差,并從中獲得深度信息,進(jìn)而與平面信息整合形成立體圖像。立體匹配是立體視覺算法中最重要也是最困難的部分。

根據(jù)匹配基元的不同,現(xiàn)有的立體匹配方法可大致分為三類:基于特征的匹配[4,5],基于區(qū)域的匹配[6]和基于相位的匹配[7]。

本文重點研究雙目視覺立體匹配中基于區(qū)域的局部匹配算法,對基于SAD(Sum of Absolute Difference)的區(qū)域匹配算法通過模板滑動進(jìn)行了改進(jìn)。經(jīng)分析和多次實驗結(jié)果表明,該改進(jìn)算法具有有效性和快速性。

1 雙目立體視覺區(qū)域局部匹配的理論基礎(chǔ)

1.1 相似性測度函數(shù)

匹配算法的實質(zhì)就是估計待匹配點和候選匹配點之間的相似性程度,評價這種相似性程度度量方法有多種。由于單個像素點所包含的信息太少,因而只依據(jù)單個像素點是的信息建立度量方法可靠性較差。為了提高相似性度量方法的可靠性,一般需要在匹配點上的一個小鄰域內(nèi)的像素點集合中進(jìn)行。

表1列出了目前幾種主要的相似性測度函數(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相似性測度函數(shù)在時間以及匹配質(zhì)量方面較其他測度函數(shù)更具有優(yōu)勢,且實現(xiàn)較簡單[8]。這里研究選擇SAD作為局部相關(guān)匹配算法的相似性測度函數(shù)。

1.2 局部相關(guān)匹配算法原理

局部相關(guān)匹配算法是以基準(zhǔn)圖像中待匹配點為中心像素來創(chuàng)建一個大小為n×n的矩形窗,由該窗口內(nèi)的像素灰度分布來表征該像素。在第二幅圖像中,沿極線在視差范圍內(nèi)取出與基準(zhǔn)點鄰域同樣大小為n×n的像素鄰域,依次與匹配點的窗口進(jìn)行比較,最大相似性對應(yīng)的點就是最佳匹配。整個匹配過程如圖1所示。

表1 幾種相似性測度函數(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)匹配算法的時間復(fù)雜度

在圖1(a)中坐標(biāo)為(x,y)的像素點,算法要計算圖1(b)中所有相關(guān)像素的相似性。根據(jù)極線約束以及視差約束,在圖1(b)中只需計算同一極線上,視差范圍內(nèi)的像素相似性即可,需要的計算量為:

T(x,y)=dmaxn2(1)

式中:n為正方形窗口邊長;dmax為最大視差。設(shè)W為圖像的寬度;H為圖像的高度,對于整幅圖片,全部相似性的計算量為:

T=∑0≤i

易知,局部相關(guān)匹配算法的時間復(fù)雜度為O(WHdmaxn2)。

1.4 局部相關(guān)匹配算法的改進(jìn)

若假設(shè)匹配窗口的邊長為2n+1,對于每行像素,其相似性測度函數(shù)為P(x,y,d)=∑ni=-n|IL(x+i,y)-IR(x+i+d,y)|;在模板向右滑動時,P(x+1,y,d)可由之前的計算結(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)

即在模板滑動時,不需要重新計算整個窗口的SAD,而只需計算新的一列SAD。分析可知,改進(jìn)后算法的時間復(fù)雜度由O(WHdmaxn2)降為O(WHdmaxn),算法實時性有了較大提升。

2 雙目立體視覺區(qū)域局部匹配算法的實現(xiàn)

2.1 實驗環(huán)境

該研究的實驗主要是通過計算機編程實現(xiàn)區(qū)域局部匹配算法,并在雙相機系統(tǒng)上利用標(biāo)準(zhǔn)和實際場景圖像進(jìn)行驗證性實驗的。以VC++ 6.0及OPENCV為編程環(huán)境,完成驗證軟件設(shè)計。

該研究的驗證實驗使用了西安交通大學(xué)系統(tǒng)工程所的實驗設(shè)備(如圖2所示)。兩只攝像機平行放置,其位置姿態(tài)參數(shù)已由標(biāo)定結(jié)果給出,如表2所示。

圖2 試驗系統(tǒng)

表2 相機標(biāo)定參數(shù)表(以像素為單位)

參數(shù)指標(biāo)左相機右相機

焦距699.85696.15

相機中心[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

相對位移/mmt1=87.921,t2=1.205,t3=4.980

攝像機與處理計算機之間通過雙1394總線連接,計算機中配備2塊64位PCI-1394卡,以適應(yīng)攝像機高速圖像流的要求。攝像機的主要參數(shù)如表3所示。

表3 攝像機參數(shù)

攝像機特性參數(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è)計流程圖

系統(tǒng)算法流程圖如圖3所示。

圖3 系統(tǒng)算法流程圖

2.3 實驗結(jié)果

部分實驗結(jié)果如圖4所示。

圖4 實驗結(jié)果

由圖4可知[10],實驗得到的圖片較好地完成了對現(xiàn)實場景中的匹配,可以較直接地從所得視差圖中獲得物體的深度信息。

同時,圖像邊緣處的匹配精度受到圖像邊界的影響,誤差較大,真實場景圖片中噪聲較大,導(dǎo)致誤匹配較多。如何減少誤差,提高精度是現(xiàn)在和今后重點考慮的問題之一。

3 結(jié) 語

這里對雙目立體視覺中的區(qū)域局部匹配算法進(jìn)行討論,對現(xiàn)有SAD算法進(jìn)行了改進(jìn),較顯著地提高了匹配速度。在實驗平臺上較好地完成了對標(biāo)準(zhǔn)圖像及現(xiàn)實場景圖像的視差圖獲取,驗證了算法的有效性和快速性。

參考文獻(xiàn)

[1]章毓晉.圖像工程(下冊)圖像理解[M].2版.北京:清華大學(xué)出版社,2007.

[2]何明一,衛(wèi)保國.數(shù)字圖像處理[M].北京:科學(xué)出版社,2008.

[3]游素亞.立體視覺研究的現(xiàn)狀與進(jìn)展[J].中國圖像圖形學(xué)報,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]高峰,文貢堅,呂金建.一種準(zhǔn)自動高精度圖像配準(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]徐奕,周軍,周源華.立體視覺匹配技術(shù)[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]夏永泉.計算機視覺中雙目匹配相關(guān)技術(shù)的研究[D].南京:南京理工大學(xué),2007.

[10]Middlebury College Stereo Vision Research[EB/OL].http://cat.middlebury.edu,2008.