雙目立體視覺區域局部匹配算法的改進及其實現

何人杰

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

關鍵詞:雙目立體視覺;區域相關;立體匹配;標準測試圖

中圖分類號:TP391文獻標識碼: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 引 言

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

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

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

1 雙目立體視覺區域局部匹配的理論基礎

1.1 相似性測度函數

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

表1列出了目前幾種主要的相似性測度函數[6]。其中,IL(x,y),IR(x,y)分別代表左右圖像中像素坐標(x,y)處的灰度值;IL(x,y),IR(x,y)分別表示左右圖中以坐標(x,y)為中心,在窗口范圍U內像素灰度的平均值。由于SAD相似性測度函數在時間以及匹配質量方面較其他測度函數更具有優勢,且實現較簡單[8]。這里研究選擇SAD作為局部相關匹配算法的相似性測度函數。

1.2 局部相關匹配算法原理

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

表1 幾種相似性測度函數

名稱公式

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 局部相關算法原理示意圖

1.3 局部相關匹配算法的時間復雜度

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

T(x,y)=dmaxn2(1)

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

T=∑0≤i

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

1.4 局部相關匹配算法的改進

若假設匹配窗口的邊長為2n+1,對于每行像素,其相似性測度函數為P(x,y,d)=∑ni=-n|IL(x+i,y)-IR(x+i+d,y)|;在模板向右滑動時,P(x+1,y,d)可由之前的計算結果得到,有迭代公式:

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。分析可知,改進后算法的時間復雜度由O(WHdmaxn2)降為O(WHdmaxn),算法實時性有了較大提升。

2 雙目立體視覺區域局部匹配算法的實現

2.1 實驗環境

該研究的實驗主要是通過計算機編程實現區域局部匹配算法,并在雙相機系統上利用標準和實際場景圖像進行驗證性實驗的。以VC++ 6.0及OPENCV為編程環境,完成驗證軟件設計。

該研究的驗證實驗使用了西安交通大學系統工程所的實驗設備(如圖2所示)。兩只攝像機平行放置,其位置姿態參數已由標定結果給出,如表2所示。

圖2 試驗系統

表2 相機標定參數表(以像素為單位)

參數指標左相機右相機

焦距699.85696.15

相機中心[392.34 283.94][389.26 308.18]

畸變[-0.270 20 0.454 48][-0.239 75 0.256 22]

旋轉角/radα=0.013 77,β=0.001 07,γ=0.000 38

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

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

表3 攝像機參數

攝像機特性參數

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 軟件設計流程圖

系統算法流程圖如圖3所示。

圖3 系統算法流程圖

2.3 實驗結果

部分實驗結果如圖4所示。

圖4 實驗結果

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

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

3 結 語

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

參考文獻

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

[2]何明一,衛保國.數字圖像處理[M].北京:科學出版社,2008.

[3]游素亞.立體視覺研究的現狀與進展[J].中國圖像圖形學報,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]高峰,文貢堅,呂金建.一種準自動高精度圖像配準算法[J].現代電子技術,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]徐奕,周軍,周源華.立體視覺匹配技術[J].計算機工程與應用,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]夏永泉.計算機視覺中雙目匹配相關技術的研究[D].南京:南京理工大學,2007.

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