1、1引言隨著信息技術的高速發展,立體視覺技術已經廣泛應用于醫學診斷,工業檢測,機器人視覺,航空測繪等領域中。雙目立體視覺作為一種被動式的三維測距技術,以其實現方式靈活、對環境要求低、價格低廉等優點而廣受重視,旨在模擬人類雙眼識別場景三維信息的機理,從兩個角度獲取場景的二維圖像,再根據建立圖像之間的匹配關系重建三維模型。雙目立體視覺主要包括攝像機標定,立體匹配,三維重建三個步驟,其中立體匹配是核心環節。立體匹配的目的是找出兩幅圖像中像素點的對應關系,分為局部算法和全局算法。常用的局部算法有區域相關算法,自適應窗口算法,區域增長算法等1,局部算法以視差連續性約束為前提,利用像素鄰域窗口內的灰度信息計

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

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

4、提高了算法的實時性。實驗結果證明,本文算法能夠產生光滑逼真的建筑物三維點云模型。關鍵詞: 三維建筑物重建,立體匹配,動態規劃,控制點提取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 是全局匹配代價,而(smooth E d 是相鄰像素點間的平滑代價,根據像素之間的視差相關性,對相鄰像素的不同視差施以懲罰,為權重系數,用于調整(data E d 與(smooth E d 之間的權重比例。 全局最優算法按照如圖1a 所示的網格結構計算像素的平滑代價,很顯然這是一個復雜的非線性優化問題,計算量很大,很難滿足實時性要求,動態規劃算法將網格結構切割成多個一維的掃描線,如圖1b所示,在每條獨立的掃描線上作能量優化,得到最優的匹配路 徑。 圖1a :網格結構 圖1b :動態規劃

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

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

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

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

12、ce ,灰度互相關系數(cross correlation coefficient ,歸一化灰度差平方(normalized squared difference 和歸一化灰度互相關系數(normalized cross correlation coefficient 。在這些相似性測度函數中,歸一化方式受光照影響較小,但計算量相對較大。本文引入Birchfield 和Tomasi 9提出的一種類似線性插值的方法,如圖4所示。(I x ( I y 圖4:匹配代價計算示意圖其中,'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 則兩點匹配代價為,1max min 1max0,(,(i i S I x I I I x =(6這種匹配代價的計算量非常小,同時類似線性插值 的方法對于采樣點和噪聲不敏感,但由于本文所研究的對象灰度特征不明顯,紋理不豐富,同一待匹配點的候選范圍內會出現多個匹配代價最小的點,本文先采用這種類似線性插值的方法濾去候選范圍內的大部分點,再對剩下的點計算歸一化互相關函數作為第二輪比較的依據,代價最小的點即為待匹配點的共軛點,候選

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

15、物體的表面一般是平滑的,因此在深度變化不大的區域,相鄰的點視差應該是連續的,這就是視差連續性約束。這個約束條件是以物體表面平滑為前提的,正是因為建筑物模型不滿足該前提條件,才導致了傳統匹配算法對該模型不適用。因此,問題轉化成怎樣使模型滿足視差連續性約束的前提條件,我們仍然采用動態規劃算法在一維掃描線內規劃最優路徑的思想,利用提取的特征點分段水平掃描線,得到多個掃描線段,如圖5所示。1l 11(P d 22(P d圖5:掃描線分段示意圖分段掃描線的依據是前期工作中得到的特征點,而這些特征點是基于灰度的梯度提取的,也是深度梯度比較大的區域,因此對于分段得到的掃描線段,分別滿足視差連續性約束,并擁有

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

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

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

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

20、基金(BK2007116的資助。參考文獻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