一種基于立體匹配的建筑物三維重建方法_圖文

1、1引言隨著信息技術(shù)的高速發(fā)展,立體視覺(jué)技術(shù)已經(jīng)廣泛應(yīng)用于醫(yī)學(xué)診斷,工業(yè)檢測(cè),機(jī)器人視覺(jué),航空測(cè)繪等領(lǐng)域中。雙目立體視覺(jué)作為一種被動(dòng)式的三維測(cè)距技術(shù),以其實(shí)現(xiàn)方式靈活、對(duì)環(huán)境要求低、價(jià)格低廉等優(yōu)點(diǎn)而廣受重視,旨在模擬人類雙眼識(shí)別場(chǎng)景三維信息的機(jī)理,從兩個(gè)角度獲取場(chǎng)景的二維圖像,再根據(jù)建立圖像之間的匹配關(guān)系重建三維模型。雙目立體視覺(jué)主要包括攝像機(jī)標(biāo)定,立體匹配,三維重建三個(gè)步驟,其中立體匹配是核心環(huán)節(jié)。立體匹配的目的是找出兩幅圖像中像素點(diǎn)的對(duì)應(yīng)關(guān)系,分為局部算法和全局算法。常用的局部算法有區(qū)域相關(guān)算法,自適應(yīng)窗口算法,區(qū)域增長(zhǎng)算法等1,局部算法以視差連續(xù)性約束為前提,利用像素鄰域窗口內(nèi)的灰度信息計(jì)

2、算待匹配點(diǎn)與候選匹配點(diǎn)的相關(guān)度,在無(wú)紋理和深度不連續(xù)的區(qū)域容易產(chǎn)生誤匹配。全局算法將平滑性代價(jià)加入匹配代價(jià)的計(jì)算中,使匹配轉(zhuǎn)化為能量函數(shù)的全局最優(yōu)過(guò)程,主要包括圖割算法2,置信度傳播算法3和動(dòng)態(tài)規(guī)劃算法4。全局算法可以得到比較理想的匹配結(jié)果,但計(jì)算量龐大,動(dòng)態(tài)規(guī)劃算法是全局算法中實(shí)時(shí)性比較高的一種算法。本文結(jié)合建筑物這一特定的應(yīng)用環(huán)境,提出了一種基于控制點(diǎn)的分段動(dòng)態(tài)規(guī)劃算法,利用控制點(diǎn)的匹配結(jié)果指導(dǎo)稠密匹配,改善了動(dòng)態(tài)規(guī)劃算法應(yīng)用于建筑物三維重建所造成的條狀瑕疵。實(shí)驗(yàn)結(jié)果證明,該算法可以得到光滑逼真的建筑物三維點(diǎn)云模型。2動(dòng)態(tài)規(guī)劃算法局部匹配算法是基于獨(dú)立點(diǎn)的匹配算法,沒(méi)有利用像素之間的視差相

3、關(guān)信息,對(duì)匹配的準(zhǔn)確性有很大的負(fù)面影響。全局最優(yōu)算法引入全局搜索策略,將平滑性約束加入匹配代價(jià)的計(jì)算中,在全局范圍內(nèi)作能量?jī)?yōu)化,能量函數(shù)一般為:(data smoothE d E d E d=+(1一種基于立體匹配的建筑物三維重建方法曹云云1,達(dá)飛鵬1,隋宜桓11.東南大學(xué)自動(dòng)化研究所, 南京210096摘要: 針對(duì)傳統(tǒng)動(dòng)態(tài)規(guī)劃算法固有的條狀瑕疵問(wèn)題,提出了一種改進(jìn)的基于立體匹配的三維建筑物重建方法。該算法利用Canny算子和Harris算子提取建筑物的角點(diǎn)和邊緣點(diǎn)作為稠密匹配的控制點(diǎn)。通過(guò)控制點(diǎn)分段掃描線進(jìn)行動(dòng)態(tài)規(guī)劃,同時(shí)采用歸一化互相關(guān)系數(shù)和一種類似線性插值法相結(jié)合的匹配代價(jià)計(jì)算法,進(jìn)一步

4、提高了算法的實(shí)時(shí)性。實(shí)驗(yàn)結(jié)果證明,本文算法能夠產(chǎn)生光滑逼真的建筑物三維點(diǎn)云模型。關(guān)鍵詞: 三維建筑物重建,立體匹配,動(dòng)態(tài)規(guī)劃,控制點(diǎn)提取A Stereo Matching based 3D Building Reconstruction AlgorithmYunyun Cao1, Feipeng Da1, Yihuan Sui11.Research Institute of Automation, Southeast University, Nanjing 210096, ChinaAbstract: In order to solve the well-known streaking eff

5、ects of dynamic programming, an improved algorithm based on stereo matching technology is proposed to generate 3D building model. This algorithm obtains the feature points of the building by Harris corner detector and Canny edge detector to segment the scan lines of dynamic programming. Moreover, a

6、linearly interpolated dissimilarity measure is introduced into the cost computation which further improves the matching speed. The experimental results show that the proposed algorithm can produce smooth and dense 3D points cloud model of building.Key Words: 3D reconstruction of building, stereo mat

7、ching, dynamic programming, control-points其中,(data E d 是全局匹配代價(jià),而(smooth E d 是相鄰像素點(diǎn)間的平滑代價(jià),根據(jù)像素之間的視差相關(guān)性,對(duì)相鄰像素的不同視差施以懲罰,為權(quán)重系數(shù),用于調(diào)整(data E d 與(smooth E d 之間的權(quán)重比例。 全局最優(yōu)算法按照如圖1a 所示的網(wǎng)格結(jié)構(gòu)計(jì)算像素的平滑代價(jià),很顯然這是一個(gè)復(fù)雜的非線性優(yōu)化問(wèn)題,計(jì)算量很大,很難滿足實(shí)時(shí)性要求,動(dòng)態(tài)規(guī)劃算法將網(wǎng)格結(jié)構(gòu)切割成多個(gè)一維的掃描線,如圖1b所示,在每條獨(dú)立的掃描線上作能量?jī)?yōu)化,得到最優(yōu)的匹配路 徑。 圖1a :網(wǎng)格結(jié)構(gòu) 圖1b :動(dòng)態(tài)規(guī)劃

8、路徑 圖1c :半全局路徑平滑性約束在物體邊緣等深度梯度變化的區(qū)域是不適用的,往往導(dǎo)致動(dòng)態(tài)規(guī)劃算法在一維掃描線內(nèi)的錯(cuò)誤累積,這就是條狀瑕疵現(xiàn)象。對(duì)于該問(wèn)題Hirschmuller提出一種半全局立體匹配方法5,采用局部算法逐點(diǎn)匹配的思想,在待匹配像素多個(gè)方向上作動(dòng)態(tài)規(guī)劃,用多個(gè)一維的平滑約束來(lái)近似該像素二維的平滑約束。該算法改進(jìn)了動(dòng)態(tài)規(guī)劃算法的條狀瑕疵現(xiàn)象,但同時(shí)也增加了計(jì)算的負(fù)擔(dān),對(duì)于大范圍的建筑物匹配具有一定的不適用性,另外建筑物表面紋理不明顯也導(dǎo)致了該算法的匹配準(zhǔn)確度不高,如圖2所示的圖像中待匹配點(diǎn)沒(méi)有一條路徑捕捉到紋理信息,這種情況下,容易受噪聲影響 而導(dǎo)致錯(cuò)誤的匹配結(jié)果。圖2:弱紋理區(qū)

9、域半全局匹配示意圖3 一種基于控制點(diǎn)的分段動(dòng)態(tài)規(guī)劃算法建筑物模型具有棱角明顯,紋理較弱的特性,棱角明顯有助于特征點(diǎn)的提取與匹配,而紋理較弱給大范圍的稠密匹配帶來(lái)了很大的困難。針對(duì)建筑物模型這一特征,本文提出一種基于控制點(diǎn)的分段動(dòng)態(tài)規(guī)劃算法?？刂泣c(diǎn)的思想最早由Bobick 和Intille 6提出,利用控制點(diǎn)的匹配信息指導(dǎo)后續(xù)的稠密匹配。本文主要以約束視差范圍的方式實(shí)現(xiàn)控制點(diǎn)對(duì)稠密匹配的指導(dǎo),主要分為四個(gè)部分:圖像獲取與極線校正,特征點(diǎn)的提取與匹配,基于控制點(diǎn)的稠密匹配和三維重建,流程如圖3所示。其中,特征點(diǎn)的提取采用Canny 算子和Harris 算子,基于控制點(diǎn)的稠密匹配將在本文3.3節(jié)中作

10、詳細(xì)介紹。 圖3:算法流程圖3.1 圖像獲取與極線校正本文利用CCD從兩個(gè)角度拍攝建筑物模型,采用張友正標(biāo)定法7得到標(biāo)定信息。左圖中某像素在右圖像上的匹配像素位于該像素對(duì)應(yīng)的外極線上,這就是外極線約束的主要思想。該約束將匹配從二維的搜索過(guò)程降到了一維,極大地減少了運(yùn)算量,并且是一種明確可靠不存在歧義的約束。當(dāng)兩部?jī)?nèi)參相同的攝像機(jī)平行放置時(shí)就構(gòu)成了平行式立體視覺(jué)模型,平行式立體視覺(jué)模型所有極線平行于兩攝像機(jī)的光心的連線,對(duì)應(yīng)匹配像素具有相同的縱坐標(biāo)。而實(shí)際拍攝時(shí)很難滿足這種模型的要求,我們采用Fusiello 8提出的校正方法通過(guò)強(qiáng)制旋轉(zhuǎn)形成虛擬的平行成像平面,得到平行式的雙目視覺(jué)模型,校正后的

11、圖像準(zhǔn)確度高,誤差控制在1個(gè)像素內(nèi),大大簡(jiǎn)化了后續(xù)匹配的過(guò)程。3.2 特征點(diǎn)的提取與匹配特征點(diǎn)的準(zhǔn)確提取與匹配對(duì)后續(xù)的稠密匹配意義重大,本文采用Harris 算子和Canny 算子提取模型的角點(diǎn)和邊緣點(diǎn)作為特征點(diǎn)。邊緣提取中利用非極大點(diǎn)抑制法細(xì)化邊緣,在垂直于邊緣的方向上比較鄰域的梯度幅值。根據(jù)這一操作去除梯度幅值的非極大點(diǎn),從而達(dá)到細(xì)化邊緣的目的。然后再利用雙閾值算法去除由噪聲和細(xì)紋引起的虛假邊緣。本文采用改進(jìn)的灰度區(qū)域相關(guān)算法匹配特征點(diǎn)。灰度區(qū)域相關(guān)算法通過(guò)比較待匹配點(diǎn)與候選匹配區(qū)域內(nèi)所有像素鄰域窗口內(nèi)的灰度相關(guān)度得到匹配點(diǎn)對(duì),常用的相關(guān)性測(cè)度有灰度差平方(squared differen

12、ce ,灰度互相關(guān)系數(shù)(cross correlation coefficient ,歸一化灰度差平方(normalized squared difference 和歸一化灰度互相關(guān)系數(shù)(normalized cross correlation coefficient 。在這些相似性測(cè)度函數(shù)中,歸一化方式受光照影響較小,但計(jì)算量相對(duì)較大。本文引入Birchfield 和Tomasi 9提出的一種類似線性插值的方法,如圖4所示。(I x ( I y 圖4:匹配代價(jià)計(jì)算示意圖其中,'222211(1(22i i i I I y I y I y =+(2 '222211(122i i

13、 i I I y I y I y +=+=+(3然后定義,min 222min,(i I I I I y += (4 max 222max,(i I I I I y +=(5 則兩點(diǎn)匹配代價(jià)為,1max min 1max0,(,(i i S I x I I I x =(6這種匹配代價(jià)的計(jì)算量非常小,同時(shí)類似線性插值 的方法對(duì)于采樣點(diǎn)和噪聲不敏感,但由于本文所研究的對(duì)象灰度特征不明顯,紋理不豐富,同一待匹配點(diǎn)的候選范圍內(nèi)會(huì)出現(xiàn)多個(gè)匹配代價(jià)最小的點(diǎn),本文先采用這種類似線性插值的方法濾去候選范圍內(nèi)的大部分點(diǎn),再對(duì)剩下的點(diǎn)計(jì)算歸一化互相關(guān)函數(shù)作為第二輪比較的依據(jù),代價(jià)最小的點(diǎn)即為待匹配點(diǎn)的共軛點(diǎn),候選

14、范圍由極線約束和視差范圍約束相交得到。顯然,引入這種類似線性插值法計(jì)算匹配代價(jià)可以加速控制點(diǎn)的匹配。為了進(jìn)一步提高特征點(diǎn)匹配結(jié)果的可靠性,本文采用雙向匹配策略,用從右往左的匹配結(jié)果檢驗(yàn)從左往右的匹配,剔除誤匹配后,最終得到可以指導(dǎo)稠密匹配的高置信度控制點(diǎn)集合。 3.3 基于控制點(diǎn)的稠密匹配由于建筑物模型中有大范圍的無(wú)紋理區(qū)域,稠密匹配相當(dāng)困難,采用基于窗口的灰度區(qū)域相關(guān)算法會(huì)產(chǎn)生很多誤匹配,而動(dòng)態(tài)規(guī)劃算法在整條掃描線上搜索最優(yōu)路徑時(shí),掃描線穿過(guò)視差垂直突變的區(qū)域,條狀瑕疵現(xiàn)象明顯。本文針對(duì)該問(wèn)題,首先用控制點(diǎn)分段掃描線,然后結(jié)合視差連續(xù)性約束,在分段后的掃描線內(nèi)做動(dòng)態(tài)規(guī)劃獲得稠密匹配視差結(jié)果。

15、物體的表面一般是平滑的,因此在深度變化不大的區(qū)域,相鄰的點(diǎn)視差應(yīng)該是連續(xù)的,這就是視差連續(xù)性約束。這個(gè)約束條件是以物體表面平滑為前提的,正是因?yàn)榻ㄖ锬Ｐ筒粷M足該前提條件,才導(dǎo)致了傳統(tǒng)匹配算法對(duì)該模型不適用。因此,問(wèn)題轉(zhuǎn)化成怎樣使模型滿足視差連續(xù)性約束的前提條件,我們?nèi)匀徊捎脛?dòng)態(tài)規(guī)劃算法在一維掃描線內(nèi)規(guī)劃最優(yōu)路徑的思想,利用提取的特征點(diǎn)分段水平掃描線,得到多個(gè)掃描線段,如圖5所示。1l 11(P d 22(P d圖5:掃描線分段示意圖分段掃描線的依據(jù)是前期工作中得到的特征點(diǎn),而這些特征點(diǎn)是基于灰度的梯度提取的,也是深度梯度比較大的區(qū)域,因此對(duì)于分段得到的掃描線段,分別滿足視差連續(xù)性約束,并擁有

16、各自的視差范圍,我們對(duì)這些掃描線段分別做動(dòng)態(tài)規(guī)劃,以掃描線段12PP 為例,該線段端點(diǎn)由特征點(diǎn)提取所得,并且前期匹配得到的視差分別為1d 和2d 12(d d <,我們?cè)诰€段12PP 上應(yīng)用動(dòng)態(tài)規(guī)劃算法計(jì)算匹配代價(jià),得到最優(yōu)的匹配路徑,規(guī)劃過(guò)程中將每個(gè)像素的視差范圍約束在12(,d d 內(nèi),如圖6所示。dd 12d d圖6:掃描線1l 視差分布示意圖該算法將視差范圍由全局視差范圍(,min max d d 縮小到12(,d d ,降低了匹配的歧義性,同時(shí)掃描線的縮短也減少了錯(cuò)誤累積的可能,提高了算法的精度,并且由于搜索范圍的縮小,算法效率也得到進(jìn)一步的提高。 3.4 三維重建本文采用空間

17、交匯法還原出三維點(diǎn)云,計(jì)算一對(duì)匹配點(diǎn)所對(duì)應(yīng)的兩條入射光線的方程,求出其交點(diǎn),即可得到對(duì)應(yīng)物點(diǎn)在世界坐標(biāo)系下的三維空間坐標(biāo)。在實(shí)際計(jì)算過(guò)程中,由于標(biāo)定、匹配、運(yùn)算等各個(gè)過(guò)程中都存在誤差,逆向計(jì)算出的兩條直線很可能不會(huì)正好相交,此時(shí)只需如圖7所示取兩條異面直線的公垂線中點(diǎn)即 可。 圖7:空間交匯法示意圖4 實(shí)驗(yàn)結(jié)果 攝像機(jī)獲取的圖像對(duì)如圖8所示,分辨率為1380×1030,建筑物模型區(qū)域大約為5-6萬(wàn)個(gè)像素,算法在VC+6.0平臺(tái)下編程實(shí)現(xiàn)。極線校正的結(jié)果對(duì)比如圖9所示,從圖中可以看出,校正后極線水平,并且誤差控制在1個(gè)像素內(nèi)。特征點(diǎn)的提取如圖10所示,紅色的點(diǎn)表示角點(diǎn),白色的線條表示邊

18、緣。 圖8:攝像機(jī)獲取的圖像對(duì) 圖9a :校正前的極線 圖9b :校正后的極線圖10:特征點(diǎn)提取結(jié)果圖本文算法的三維建筑物模型重建結(jié)果與其他三種主流算法的對(duì)比如圖11所示,算法耗時(shí)如表1所示?；叶葏^(qū)域相關(guān)算法得到的重建模型誤匹配最高;動(dòng)態(tài)規(guī)劃的條狀瑕疵明顯,但耗時(shí)較少;而半全局算法重建結(jié)果與前兩種算法相比有所改進(jìn),但點(diǎn)云仍不夠光滑,并且算法實(shí)時(shí)性不高。本文算法得到的建筑物三維點(diǎn)云平滑逼真,特別是在邊緣區(qū)域,重建結(jié)果也比較理想,另外,本文算法也是四種算法中耗時(shí)最少的。圖11a :灰度區(qū)域相關(guān)算法 圖11b :動(dòng)態(tài)規(guī)劃算法圖11c :半全局算法 圖11d :本文算法表1.四種立體匹配算法運(yùn)算耗時(shí)對(duì)

19、比匹配算法灰度區(qū)域相關(guān)算法動(dòng)態(tài)規(guī)劃算法半全局算法本章算法耗時(shí)(sec30 19 40 155 結(jié)論本文構(gòu)建了完整的基于立體匹配的建筑物三維重建系統(tǒng),提出一種新的基于控制點(diǎn)的分段動(dòng)態(tài)規(guī)劃算法,首先提取建筑物特征點(diǎn)作為稠密匹配的控制點(diǎn),通過(guò)控制點(diǎn)分段掃描線進(jìn)行動(dòng)態(tài)規(guī)劃,并利用具有高置信度的控制點(diǎn)匹配結(jié)果約束動(dòng)態(tài)規(guī)劃過(guò)程中的視差范圍,引導(dǎo)稠密匹配得到較準(zhǔn)確的結(jié)果。最后根據(jù)匹配結(jié)果恢復(fù)出三維模型,該算法在保證一定實(shí)時(shí)性的前提下,得到光滑逼真的建筑物三維點(diǎn)云,但該算法沒(méi)有利用圖像的顏色信息,今后的研究將把顏色作為輔助信息加入匹配代價(jià)的計(jì)算中。致謝本文受到國(guó)家自然科學(xué)基金(60775025、江蘇省自然科學(xué)

20、基金(BK2007116的資助。參考文獻(xiàn)1 D. Scharstein, R. Szeliski. A taxonomy and evaluation of densetwo-frame stereo correspondence algorithmsJ. Computer Vision, 2002, 47(1: 7-42.2 H. LI, G. CHEN. Segment-based stereo matching using graphcutsC. Proceedings of the IEEE Computer Society Conference on Computer Vision

21、and Pattern Recognition, Washington, DC.IEEE Press, 2004:174-181. 3 P.F. Felzenszwalb, D.P. Huttenlocher. Efficient beliefpropagation for early visionC. Proceedings of the IEEE Computer Society Conference on Computer Vision and PatternRecognition, Washington, DC. IEEE Press, 2004: 1261-1268. 4 J.C.

22、Kim, K.M. Lee. A dense stereo matching using two-passdynamic programming with generalized ground control pointsC. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, SanDiego, CA. Washington: IEEE Press, 2005: 1075- 1082.5 H. Hirschmuller. Accurate and Efficien