左志強,黃先鋒,楊 沖,張 帆,高云龍
(1. 武漢大學測繪遙感信息工程國家重點實驗室,湖北 武漢 430079; 2. 武漢大學遙感信息工程學院,湖北 武漢 430079)
基于傾斜影像的城市場景隱式曲面重建
左志強1,黃先鋒1,楊 沖2,張 帆1,高云龍1
(1. 武漢大學測繪遙感信息工程國家重點實驗室,湖北 武漢 430079; 2. 武漢大學遙感信息工程學院,湖北 武漢 430079)
在基于傾斜影像的城市場景重建過程中,由于獲取影像時存在場景遮蔽和大視點變化的情況,建筑物立面等區域存在著影像密集匹配點云稀疏甚至空洞的情況,自動化重建難度大,難以反映建筑物的真實形態。本文提出了一種新的基于傾斜影像的城市場景隱式曲面重建方法: 首先,以傾斜影像密集匹配點云為基礎建立Delaunay四面體;然后,對Delaunay四面體進行約束圖割,提取出可視化的三角面,進而更加精確地估計點云的法向信息;最終,結合Screened Poisson曲面重建,實現了城市場景的隱式曲面重建。通過多種隱式曲面重建方法的對比試驗,驗證了本方法的準確性和適用性。
傾斜影像;隱式曲面重建;光線;圖割;Screened Poisson曲面重建
快速、準確地重建物體的表面模型在逆向工程、工業制造、虛擬環境構建等諸多領域具有重要意義[1-3]?;趦A斜影像的曲面重建是曲面重建的方式之一,可以快速獲取地表模型,在地形地貌分析、數字城市建設中得到了廣泛的應用[4-6]。
基于傾斜影像的曲面重建流程可大致分為:①傾斜影像同名點提取;②空中三角測量;③影像密集匹配生成點云;④基于點云的曲面重建。根據曲面重建的表示方式,可將曲面重建方法分為顯式曲面方法、隱式曲面方法[7]。文獻[8—10]使用Voronoi圖和Delaunay三角網來確定點與點之間的連接并最終通過連接相鄰頂點來重建曲面,文獻[11—13]采用參數曲面來表示曲面重建,這些方法均是顯式曲面方法。使用顯式曲面重建的一大優點是可以精確簡潔地表示曲面情況[14],但是顯式曲面方法難以處理點云中的噪聲和孔洞問題,主要是由該方法的自身特性所決定的:①所有的點都被作為三角網的頂點;②點與點是通過最鄰近信息來確定連接關系的,缺乏全局性。除此之外,由于缺乏體積信息,顯式曲面重建方法在處理復雜的拓撲結構時不夠穩定和靈活[14]。
隱式曲面重建方法是通過隱函數擬合數據點,然后在零值面上提取三維網格曲面[7],文獻[15]使用分段二次函數表示模型局部表面形態,文獻[16]使用平滑符號距離函數來重建水密性的模型表面等均屬于隱式曲面重建。隱式曲面重建方法中使用的隱函數典型的有B樣條函數、徑向基函數和多項式函數,而提取三角網格的方法以Marching Cubes[17]多邊形化為主。本文所提出的重建方法中涉及的隱式曲面重建即是以B樣條函數為隱函數的Screened Poisson 曲面重建[18]。隱式曲面重建方法對含噪聲數據有更強的適應性,然而在點云稀疏區域,僅僅以點云的坐標數據,隱式曲面重建方法往往難以準確地反映目標的真實表面模型,以Screened Poisson曲面重建為例,在此情形下,目標點云稀疏區域的重建形態是B樣條曲面形態的反映,而非目標區域的形態。
而在基于傾斜影像的城市場景曲面重建中,由于獲取影像時存在遮蔽和大視點變化的原因,建筑物立面等易遮蔽區域的影像重疊度不高,導致后期此類區域密集匹配點云稀疏甚至出現空洞,曲面重建難度大。目前,文獻[19]提出一種針對大規模場景的表面重建方法,對密集匹配點云進行空間四面體剖分,對四面體進行圖割提取出表面模型,然后利用影像對生成模型進行了變分優化處理,該方法較好地保留了建筑物的原始細節形態。
本文針對城市區域傾斜影像的特點提出了一種新的城市場景重建算法。由于眾多隱式曲面重建方法在重建過程中會使用點云的法向信息,通過擬合平面[20-21]等方法在點云稀疏區域難以獲取準確法向量信息。因此,本文方法在傾斜攝影隱式曲面重建中利用不局限于點云坐標的信息來修正點云的法向信息:首先,以影像密集匹配點云為基礎建立Delaunay四面體;然后,對Delaunay四面體進行基于光線的可視性約束圖割,進而更加精確地估計點云的法向信息;最后,結合Screened Poisson曲面重建,實現城市場景隱式表面重建。
本文提出的基于傾斜影像的城市場景隱式曲面重建流程可大致分為:影像特征點提取、空中三角測量、影像密集匹配生成點云、構建Delaunay四面體并進行約束圖割、點云法向信息計算和Screened Poisson表面重建6個步驟。本文關注由密集匹配點云到曲面生成這一三維構網過程。
通常,基于三維激光點云進行隱式曲面重建時,由于點云密集,并且缺乏更多的信息(如光線信息)來修正點云的法向信息,在計算點云的法向量時采用以下步驟:①利用最鄰近算法取目標點周圍一定范圍內或一定數量的點;②對這些點進行擬合,擬合出一個平面;③計算目標點的法向量。然而,由于傾斜影像密集匹配點云自身的特點:點云分布不均,城市中建筑立面等區域密集匹配點云稀疏,利用上述常規的點云法向計算方法誤差較大。
本文提出的方法較好地解決了上述問題,有效利用了點云的光線信息。首先基于密集匹配點云(包含相機位置)建立Delaunay四面體,并建立特殊的s-t圖,根據四面體的光線可視性等信息對四面體進行標記[22],利用最小割算法[23]最優化標記結果,最終提取出城市場景的三角面,以Delaunay三角網的形式很好地保留了點云稀疏區域的形態特征,可以更加準確地計算出點云的法向量信息。圖1為本文算法的流程。

圖1 基于傾斜影像的城市場景隱式曲面重建流程
利用基于Delaunay四面體的約束圖割方法建立起城市場景的可視化三角面,首先要將Delaunay四面體標記為場景的外部或內部,然后從相鄰的不同標記結果的四面體中提取出所需的三角網。
本文使用最小割算法對全局標記結果進行優化,為此,建立三維空間中的s-t圖[24],如圖2所示。圖2中,與光線相交的三角形在s-t圖中相應有向邊增加權值。δ是偏移距離,用來確定與匯(t)相連的Delaunay四面體。最后一個與光線相交的四面體或包含相機中心的四面體與源(s)相連。Delaunay四面體的對偶——Voronoi多面體中的有向邊和節點對應s-t圖中的有向邊和節點。圖2中(二維平面內),三角形表示Delaunay四面體,淺灰色Voronoi多邊形區域表示Delaunay四面體的對偶圖——Voronoi多面體。
以S表示基于四面體的約束圖割輸出的三角面,S是帶有方向的Delaunay三角形的組合。定義與S相關的能量E(S)
E(S)=Evis(S)+λphotoEphoto(S)+λareaEarea(S)
(1)
式中,λphoto和λarea是正權值。最小化能量E(S)即可以實現Delaunay四面體標記結果的最優化,并得到所需的輸出表面。接下來將介紹每個能量項在s-t圖中的定義,并分析最小化能量E(S)為何能對Delaunay四面體實現最優化標記。

圖2 基于Delaunay四面體中的s-t圖平面示意圖
1.1.1 曲面可視性
基于傾斜影像的密集匹配點云里每個點(物方點)都至少能在兩張影像上找到對應的影像坐標(像方點)。這一信息與能量項Evis(S)相關:Delaunay四面體中的每個頂點對應的影像中的視點分別與該頂點連接成光線并向前延伸一定的長度,這條光線穿過四面體,如果四面體在這個頂點與視點中間,則被標記為外部,相反,如果四面體在這個頂點之后,則標記為內部,根據該光線的標記結果,為s-t圖中相應的有向邊賦予權值λout(外部)或者λin(內部)。
圖2中,E1為與光線相交的Delaunay三角形的對應的Voronoi多邊形的3條有向邊之一,該三角形被標記為外部,則
WeightE1=λout
(2)
δ所在位置的三角形對應的Voronoi多邊形有向邊的權值t-weight為λin,最后與光線相交或包含相機位置的四面體在s-t圖中對應的有向邊被賦予無窮大的權重s-weight。
對四面體中的所有節點重復以上操作,如果s-t圖中的有向邊已經被賦予權重,就把新賦的權重累加到之前已經存在的權重上。
曲面可視性能量項Evis(S)綜合了s-t圖里所有權重邊的信息,利用可視性能量項對每個四面體的標記情況進行全局性“投票”,通過這種全局優化的過程,可以使該方法抵抗多種類的噪聲及誤差。
1.1.2 曲面影像一致性
影像一致性能量項Ephoto(S)表征了曲面和傾斜影像的匹配度,定義如下
(3)
式中,ρ是曲面中包含的任意一個三角形的影像一致性量度。
任意三角形的影像一致性量度是通過該三角形包含的3個頂點在影像中的匹配信息計算出的。由于曲面S里包含的每個三角形是從相鄰的不同標記的四面體中提取出的,因此,曲面的影像一致性能量項要考慮三角形的方向。這里將曲面影像一致性能量項融入特殊圖里的圖割框架中:對任意擁有公共三角面的兩個Delaunay四面體(用特殊圖里的節點p和q表示 ),特殊圖中的邊p→q被賦予權重
ωpq=ρ{∏i|di·n>0}(T)
(4)
式中,di表示了從三角形的中心到第i張影像的相機中心∏i的方向。
1.1.3 曲面平滑度
曲面平滑度能量項Earea(S)被用來最小化曲面的面積,定義如下
(5)
對任意擁有公共三角面的兩個Delaunay四面體(用特殊圖里的節點p和q表示),特殊圖中的邊p→q被賦予權重ωpq=A(T),并且,相反方向的邊q→p被賦予相同的權重ωqp=ωpq。
利用最小割算法找到s-t圖的最小割,對應于能量E(S)的最小化,實現四面體的全局最優化標記。
對Delaunay四面體進行基于光線的可視性約束圖割后,生成一個城市場景的顯式曲面,本節基于此曲面計算傾斜影像密集匹配點云的法向信息。
點p為三角面s1、s2、…、sm的公共頂點,三角面的法向量為:n1、n2、…、nm。設

(6)
s對應的法向為

(7)
則點p的法向量可以表示為
(8)
本文提出的基于傾斜影像的城市場景隱式曲面重建方法是以Kazhdan等提出的隱式曲面重建方法——Screened Poisson曲面重建[18]為例來完成最終的曲面重建。Screened Poisson曲面重建能夠從有向點云中重建出水密性的曲面。
1.3.1 示性函數擬合
Poisson曲面重建方法[25]是基于實體模型表面的法向量和實體模型的示性函數的梯度相等這一原理展開的,基于有向點云數據集可以生成一個水密的表面,但是該算法對示性函數進行修正時使用的是全局性的偏移,使得在所有點的函數值的平均值為0,然而由于誤差的存在使得示性函數難以找到一個合適的全局偏移值,Kazhdan等最終提出了Screened Poisson曲面重建,在示性函數求解時,引入點集位置約束。模型的示性函數用χ表示,χ=0表示模型的表面。
給定向量場V:R3→R3,目的是為了求解示性函數χ:R3→R的最小值

(9)

V(p)定義如下

(10)
式中,s為輸入數據集的一個樣本,包含點坐標s.p和該點法向量s.N;NgbrD(s)為與s.p最鄰近的8個深度為D的節點;αo,s為三線性插值權重;Fo(p) 為基函數。
式(9)可以簡化為
(11)
式中,〈.,.〉[w,S]表示在單位立方體體素中的函數空間的形式,具備雙線性、對稱性、非負性及半正定性,該值是根據函數值的加權和得到的
(12)
式(11)將梯度約束和點云的誤差約束整合進空間域,利用Euler-Lagrange方程,通過求解Poisson方程可以得到χ的最小解

(13)
1.3.2 系統離散化與求解
同Poisson曲面重建一樣,這里對Screened Poisson曲面重建需要對泊松方程進行離散化處理。示性函數χ關于一組基{B1,B2,…,Bn}的系數可以通過求解線性系統Ax=b得到。 其中
(14)
Screened Poisson曲面重建算法引入瀑布型多重網格法對線性系統進行求解,隨著八叉樹的深度發生變化(從淺到深),系統求解從粗糙到精細。求解深度在d′層而約束在d層的矩陣可表示如下
(15)
1.3.3 等值面提取
求解Screened Poisson方程可以得到示性函數的近似解χ,理想情況下,示性函數的零水平集對應著所需的曲面,然而由于存在誤差,需要選擇合適的全局偏移值來修正指示函數χ,然后利用Marching-Cubes方法從函數χ中提取出等值面。
本文中使用的傾斜影像是利用無人機在山西某城市以離地150 m的高度傾斜攝影得到的。利用兩臺相機同時前后擺動,每次擺動角度為60°,一個周期內可以拍攝6張影像,每張影像的像元數為4000×6000,空間分辨率為3~10 cm。圖3顯示了傾斜攝影測量系統獲取影像的過程,圖4是利用該系統在一個周期內獲取的6張傾斜影像。

圖3 無人機傾斜攝影示意圖
試驗中利用半全局匹配算法(SGM)[26]對傾斜影像進行了密集匹配,然后基于計算幾何算法庫(CGAL)[27]建立了Delaunay四面體。在前文中,筆者對Delaunay四面體進行基于光線約束的最小化圖割。

圖4 傾斜影像
在試驗中,筆者將本文方法的城市場景曲面重建精度與Screened Poisson曲面重建[18]、Poisson曲面重建[25]、小波流曲面重建[28]、平滑符號距離重建[16]4種曲面重建精度作比較。筆者將曲面重建中涉及的八叉樹深度(octree depth)統一設置為10。對于Screened Poisson曲面重建算法,筆者將點的權重(pointWeights)設置為4;在小波流曲面重建(Wavelet)中,使用Haar小波來完成曲面重建。
以Screened Poisson曲面重建、Poisson曲面重建、基于Haar小波的流曲面重建(Haar Wavelet)和平滑符號距離曲面重建(SSD)4種隱式曲面重建方法為例,分別將這4種曲面重建方法作為本文算法中的曲面重建方法,完成曲面重建工作,并對應地與這4種算法在相同三維點云數據集(不包含光線信息)下的重建精度作定性與定量比較。如圖5、圖6所示。

圖5 傾斜影像密集匹配點云

圖6 本文算法重建效果(結合Screened Poisson重建)
圖7顯示了本文提出的基于傾斜影像的城市場景隱式曲面重建算法與經典算法的城市場景重建結果,并選取了典型的建筑立面區域(如圖8所示),比較了重建結果的精度。以圖7(a)為例,左圖1為本文方法(結合Screened Poisson曲面重建)的城市場景曲面重建結果,左圖2是從左圖1中拾取的精度對比目標區域;右圖1為Screened Poisson曲面重建在相同點云數據集(不使用光線信息)下的重建結果,右圖2是從右圖1中拾取的精度對比目標區域(與左圖2對應同一建筑立面區域)的重建效果。參考目標區域對應的原始傾斜影像(如圖8所示),可發現在4組對比試驗中,基于本文方法的重建效果優于對應的經典重建方法的重建效果,尤其是在建筑立面區域,本文算法很好地保留了建筑的原始特征。
為了進一步定量檢驗本文算法的有效性,筆者使用Metro[29]程序分別對圖7表示的4組曲面重建結果作比較,表1列出了城市場景曲面重建的曲面精度等信息。
聯合上述定性與定量的試驗分析,可以得出結論:本文提出的基于傾斜影像的城市場景隱式曲面重建算法能夠以很高的精度重建城市場景,尤其在建筑立面等區域,較好地保留了原有的形態。
本文提出了一種新的城市場景三維重建方法:首先基于密集匹配點云集對空間進行三維Delaunay三角剖分;然后,建立空間中的s-t圖,利用最小割算法,對Delaunay四面體進行優化標記,并提取出粗糙的三角面,利用三角面的拓撲關系,進而更加精確地估計點云的法向信息;最終結合隱式曲面重建方法(Screened Poisson曲面重建)對城市三維場景進行重建。試驗表明該方法很好地重建了城市的三維場景,尤其是在城市的建筑立面等區域,比幾種經典的算法都取得了更優的重建結果。然而在點云稀疏、形態較為復雜的區域,如窗臺等,隱式曲面重建方法難以較為規則地重建出目標原始形態,后續研究需要解決城市場景的細節區域的自動化、規則化重建。

圖7 基于傾斜影像的城市場景隱式曲面重建與經典算法重建結果

表1 城市場景曲面重建結果分析

圖8 城市建筑區域傾斜影像
[1] GAO J,CHEN X,YILMAZ O,et al.An Integrated Adaptive Repair Solution for Complex Aerospace Components through Geometry Reconstruction[J].The International Journal of Advanced Manufacturing Technology,2008,36(11-12):1170-1179.
[2] YANG M D,CHAO C F,HUANG K S,et al.Image-Based 3D Scene Reconstruction and Exploration in Augmented Reality[J].Automation in Construction,2013(33):48-60.
[3] WANG J,GU D,YU Z,et al.A Framework for 3D Model Reconstruction in Reverse Engineering[J].Computers & Industrial Engineering,2012,63(4):1189-1200.
[4] JAMES M,ROBSON S.Straightforward Reconstruction of 3D Surfaces and Topography with a Camera:Accuracy and Geoscience Application[J].Journal of Geophysical Research:Earth Surface,2012,117(F3).DOI:10.1029/2011JF002289.
[5] 史文中,曹輝,張劍清.基于高分辨率影像的城市三維建模[J].武漢大學學報(信息科學版),2004,29(9):783-787.
[6] 朱慶,徐冠宇,杜志強,等.傾斜攝影測量技術綜述[J].北京:中國科技論文在線,2012 .
[7] LIM S P,HARON H.Surface Reconstruction Techniques:A Review[J].Artificial Intelligence Review,2014,42(1):59-78.
[8] AMENTA N,BERN M,KAMVYSSELIS M.A New Voronoi-based Surface Reconstruction Algorithm[C]∥Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques.New York:ACM,1998:415-421.
[9] EDELSBRUNNER H.Shape Reconstruction with Delaunay Complex[J].Lecture Notes in Computer Science,1980,1380(1380):119-132.
[10] AMENTA N,BERN M,EPPSTEIN D.The Crust and the β-Skeleton:Combinatorial Curve Reconstruction[J].Graphical Models and Image Processing,1998,60(2):125-135.
[11] DECARLO D,DIMITRI.Blended Deformable Models[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1996,18(4):443-448.
[12] HE Y,QIN H.Surface Reconstruction with Triangular B-splines[C]∥Geometric Modeling and Processing.Beijing:[s.n.],2004:279-287.
[13] MARR D,NISHIHARA H K.Representation and Recognition of the Spatial Organization of Three-dimensional Shapes[J].Proceedings of the Royal Society of London,1978,200(1140):269-294.
[14] LIANG J,PARK F,ZHAO H.Robust and Efficient Implicit Surface Reconstruction for Point Clouds Based on Convexified Image Segmentation[J].Journal of Scientific Computing,2013,54(2-3):577-602.
[15] OHTAKE Y,BELYAEV A,ALEXA M,et al.Multi-level Partition of Unity Implicits[J].ACM Siggraph,2003,22(3):463-470.
[16] CALAKLI F,TAUBIN G.SSD:Smooth Signed Distance Surface Reconstruction[J].Computer Graphics Forum,2011,30(7):1993-2002.
[17] LORENSEN W E,CLINE H E.Marching Cubes:A High Resolution 3D Surface Construction Algorithm[J].ACM Siggraph Computer Graphics,1987,21(4):163-169.
[18] KAZHDAN M,HOPPE H.Screened Poisson Surface Reconstruction[J].ACM Transactions on Graphics (TOG),2013,32(3):1-13.
[19] HIEP V H,KERIVEN R,LABATUT P,et al.Towards High-resolution Large-scale Multi-view Stereo[C]∥IEEE Conference on Computer Vision and Pattern Recognition.[S.l.]:IEEE,2009:1430-1437.
[20] MITRA N J,NGUYEN A.Estimating Surface Normals in Noisy Point Cloud Data[C]∥Proceedings of the 19th Annual Symposium on Computational Geometry.[S.l.]:ACM,2003:322-328.
[21] HOPPE H,DEROSE T,DUCHAMP T,et al.Surface Reconstruction from Unorganized Points[C]∥Proceedings of ACM Siggraph.[S.l.]:ACM,1992.
[22] LABATUT P,PONS J-P,KERIVEN R.Efficient Multi-view Reconstruction of Large-scale Scenes Using Interest Points,Delaunay Triangulation and Graph Cuts[C]∥IEEE 11th International Conference on Computer Vision.[S.l.]:IEEE,2007:1-8.
[23] BOYKOV Y,KOLMOGOROV V.An Experimental Comparison of Min-cut/max-flow Algorithms for Energy Minimization in Vision[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2004,26(9):1124-1137.
[24] BOYKOV Y Y,JOLLY M P.Interactive Graph Cuts for Optimal Boundary & Region Segmentation of Objects in ND Images[C]∥Proceedings of Eighth IEEE International Conference on Computer Vision.Vancouver:IEEE,2001:105-112.
[25] KAZHDAN M,BOLITHO M,HOPPE H.Poisson Surface Reconstruction[C]∥Proceedings of the 4th Eurographics Symposium on Geometry Processing.[S.l.]:[s.n.],2006:61-70 .
[26] HIRSCHM LLER H.Stereo Processing by Semiglobal Matching and Mutual Information[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2008,30(2):328-341.
[27] BOISSONNAT J D,DEVILLERS O,TEILLAUD M,et al.Triangulations in CGAL[C]∥Proceedings of the 16th Annual Symposium on Computational Geometry.[S.l.]:ACM,2000:11-18.
[28] MANSON J,PETROVA G,SCHAEFER S.Streaming Surface Reconstruction Using Wavelets[C]∥Computer Graphics Forum.[S.l.]:[s.n.],2008:1411-1420.
[29] CIGNONI P,ROCCHINI C,SCOPIGNO R.Metro:Measuring Error on Simplified Surfaces[C]∥Computer Graphics Forum.[S.l.]:[s.n.],1998:167-174.
ImplicitSurfaceReconstructionofUrbanScenesBasedonObliqueImages
ZUO Zhiqiang1,HUANG Xianfeng1,YANG Chong2,ZHANG Fan1,GAO Yunlong1
(1. State Key Laboratory of Information Engineering in Surveying,Mapping and Remote Sensing,Wuhan University,Wuhan 430079,China;2. School of Remote Sensing Information Engineering,Wuhan University,Wuhan 430079,China)
In the process of urban scenes reconstruction based on oblique images,due to the scenes occlusion and large view-point changes in oblique imagery acquisition,dense image matching is quite challenging in scenarios like building facades and other vertical objects,leading to a sparse or leaky point cloud and can be hard to reconstruct the urban scenes precisely.A new urban scenes implicit surface reconstruction method is proposed based on oblique images.Firstly,it builds an adaptive tetrahedral decomposition of space by computing 3D Delaunay triangulation of the dense point cloud.Secondly,a triangular mesh is generated using the graph cut algorithm on Delaunay tetrahedron to make a more accurate estimation of the normal information of the point cloud.Finally,combined with Screened Poisson surface reconstruction method,an implicit surface reconstruction is conducted for the urban scenes.Experiments and comparison with other three implicit reconstruction methods show the accuracy and applicability of the proposed method.
oblique images;implicit surface reconstruction;ray;graph cut;Screened Poisson surface reconstruction
2017-03-16
國家自然科學基金(41571437)
左志強(1992—),男,碩士生,主要研究方向為數字幾何處理、三維重建等。E-mail:zzq_star@qq.com
左志強,黃先鋒,楊沖,等.基于傾斜影像的城市場景隱式曲面重建[J].測繪通報,2017(12):21-28.
10.13474/j.cnki.11-2246.2017.0372.
P237
A
0494-0911(2017)12-0021-08