基于體元分析的三維建筑物模型結構化分割方法

孫 軒,楊必勝,李清泉,

1.武漢大學遙感信息工程學院,湖北武漢430079;2.武漢大學測繪遙感信息工程國家重點實驗室湖北武漢430079

1 引 言

近幾年來,建筑物的多尺度(levels of detail, LOD)三維建模逐漸成為了地理信息科學領域探討的一個新熱點[1]。文獻[2]提出有效的結構分析有利于在三維多尺度建模中保持建筑物的主要形態特征,但目前卻很少有專門針對三維建筑物模型的基本結構和組成進行深入分析和探討的研究。模型分割作為拓撲關系建立和結構分析最常用的方法[3-4],一直是計算機圖形學等相關領域研究的熱點[5]。研究有效的建筑物模型結構化分割算法對于建筑物結構分析和提高LOD建模質量具有十分重要的意義。

現有常見的三維模型分割方法主要包括基于曲率特征的方法[6-8]、基于表面元素的方法[9-10]以及面向對象的方法[11-12]三類。然而采用以上方法對建筑物這類結構復雜、細節特征較多的非流形表面對象進行分割,卻難以得到理想的結構化分割結果,如圖1所示。

針對現有三維模型分割方法在建筑物基本結構特征識別方面存在的不足,本文主要針對建筑物不規則三角網表面模型,從模型內部對其結構組成進行分析,提出了一種基于體元分析的建筑物結構化分割方法。

圖1 不同算法對建筑物模型分割結果比較Fig.1 Segmentations for 3D building model using different algorithms

2 體元分析與結構化分割

體元分析,是一種將三維對象的表面模型轉化為體元模型,并以模型內部各體元的特征參數為基礎進行空間分析的方法。該方法不僅可以從三維模型內部對其空間范圍進行有效描述,同時能夠降低模型表面細節對其整體形狀的影響。

考慮到體元分析方法在三維模型分析方面所具有的獨特優勢,應用提出的結構化分割方法首先對建筑物模型進行體元化,計算所有內部體元與邊界體元間的最短距離作為體元特征參數,在三維空間內構建距離場;然后使用局部極值判別方法在距離場內搜索對建筑物結構形狀分布具有代表意義的中心體元;按照特定規則依次對中心體元和內、外部體元進行聚類,找到建筑物在空間組成上相互獨立的結構單元;最后通過表面投影方式,將體元分析結果擴展到原始模型,得到最終的結構化表面分割結果。算法流程如圖2所示。

圖2 建筑物模型結構化分割流程Fig.2 Flow chart of structural segmentation of building models

3 分割算法

3.1 距離場計算

由于三維模型的內部距離分布能夠有效地反映模型在空間中的形體變化[13-14],選擇采用內部距離作為體元分析的基本特征參數,在三維空間中構建基于距離的標量場,簡稱距離場。

為了滿足體元分析需要,采用分層方式分別獨立計算各層的水平距離場。其具體步驟如下:

(1)對建筑物模型進行體元化[15],得到模型內部空間的離散化表示,如圖3(a)所示。

(2)按照鄰域判別方法,對建筑物體元進行基礎分類,區分內、外部體元。

(3)依次計算各內部體元到同層所有外部體元間的最短距離,作為該體元的特征參數,并最終形成分層距離場,如圖3(b)所示。

圖3 建筑物內部分層距離場構建Fig.3 Distance field construction by level in building model

3.2 中心體元提取

為了識別建筑物的基本結構,必須首先提取出對建筑物形狀分布具有代表意義的中心體元。

對距離場進行深入分析后發現:距離模型表面較近的體元場值較小,而模型中部體元場值較大。因此在中心體元提取過程中采用了鄰域極值判別方法:將當前體元距離參數與其周圍二階鄰域內同層體元進行比較,得到局部范圍內距離參數最大的體元,作為當前水平體元層的中心體元。如圖4所示,灰色方框代表該水平體元層的中心體元。

圖4 建筑物水平體元層內中心體元提取結果Fig.4 Midvoxel extraction from horizontal level of building voxels

3.3 體元聚類

體元聚類是建筑物結構化分割的關鍵。按照算法執行順序,該過程分為中心體元聚類、內部體元聚類和外部體元聚類三個步驟。

3.3.1 中心體元聚類

中心體元聚類過程包括同層中心體元聚類和不同層中心體元聚合兩個步驟。

同層中心體元聚類過程中,一方面對其鄰接關系進行考察,另一方面對相鄰中心體元的距離場值大小進行比較:由于在各水平體元層中以中心體元為圓心,以距離場值大小為半徑的圓形范圍反映了建筑物在水平方向上局部區域的大小,從形體變化連續性角度考慮,相互鄰接且距離場值變化不大的中心體元被歸于建筑物的同一結構單元。如圖5(a)所示,不同灰度的方框分別代表了屬于不同結構單元的中心體元。

不同層中心體元聚合過程中,本文將相互鄰接且距離場值變化具有一定連續性(大小相等、連續遞減、連讀遞增)的上下層中心體元歸為同一結構單元。如圖5(b)所示,不同顏色方框代表在垂直方向上相互鄰接而屬于不同結構單元的中心體元,它們依據距離場值變化被聚合為兩類。

綜合水平聚類與垂直聚類,得到建筑物中心體元的最終聚類結果,如圖5(c)所示。

圖5 中心體元聚類過程Fig.5 Clustering of midvoxels

3.3.2 內部體元聚類

內部體元聚類的實質是依據中心體元聚類結果,將各水平體元層中的內部體元劃歸到中心體元所屬的不同結構單元中。

以中心體元為參照,距離越近的內部體元越有可能與該中心體元屬于同一結構單元。但考慮到建筑物各組成部分本身的形狀變化,各內部體元的聚類結果還與其周邊中心體元的距離場值大小有關:距離場值越大的中心體元代表了覆蓋范圍越大的結構單元,屬于該結構單元的內部體元可以距離中心體元更遠。綜合以上兩方面因素影響,本文針對內部體元聚類定義了一個影響力參數,用于反映特定中心體元對某內部體元聚類的影響力大小,其計算公式為

式中,v表示內部體元;midt表示類別為 t的某中心體元;Inf(v,midt)表示中心體元 midt對v的影響力;F(midt)表示中心體元 midt的距離場大小;Dist(v,midt)則表示中心體元 midt到 v的水平距離。

按照該公式依次計算各內部體元受到周圍所有中心體元影響力的大小,并將其歸類到對其影響力最大的中心體元所屬類別中,即可得到建筑物內部體元的粗聚類結果,如圖6(a)所示。

從內部體元的粗聚類結果來看,雖然大部分內部體元被歸入了正確的結構單元,但不同結構單元之間的分類邊界并不準確。為了得到準確的內部體元分類結果,通過鄰域搜索方法尋找不同結構單元間一定范圍內最短的分割直線,并將其作為修正分類邊界,對原始聚類結果進行調整,如圖6(b)所示,白色線為修正分類邊界。

圖6 內部體元聚類Fig.6 Clustering of inner voxels

3.3.3 外部體元聚類

外部體元聚類過程主要依據鄰域擴張原理,通過對其鄰域中內部體元的類別進行判斷來實現。

按照從大到小的順序對外部體元周圍水平方向鄰接4鄰域,水平方向對角4鄰域和垂直方向鄰接2鄰域分別賦予不同的權重(如4、2、1)。通過比較外部體元鄰域中各類別的加權和,將其歸類到加權和最大的類別中,得到最終建筑物外部體元聚類結果,如圖7所示。

圖7 外部體元聚類Fig.7 Clustering of outer voxels

3.4 表面分割

表面分割是建筑物模型結構化分割的最終環節,其關鍵在于將體元聚類結果投影到原始建筑物表面模型。

對于建筑物的不規則三角網表面模型而言,其表面分割過程首先需要依據鄰域判別方法提取出各結構單元間的表面分界線;然后將被分界線穿越的三角形面片分解為較小的面片[16],以解決同一三角形面片屬于多個的結構單元的問題;最后通過環分割方法[9]將原始建筑物表面模型劃分為相互獨立的結構單元,如圖8所示。

圖8 基于分類邊界的三角形面片分解Fig.8 Subdivision of triangular plane place piece based on clustering edge

4 試驗與分析

本文選取了一些具有明顯時代和地域特征的建筑物進行試驗,其模型分割結果如圖9所示。從試驗結果來看,該算法能夠對不同風格建筑物水平和垂直分布的主要結構單元進行有效分割,具有很強的穩健性;另一方面,可看出基于體元分析的結構化分割方法無法對建筑物模型局部的細小結構和表面特征進行有效識別和區分,如歐式建筑屋頂的尖塔、羅馬建筑底部的立柱、東方建筑飛檐的紋理等。

圖9 各類建筑物結構分割結果Fig.9 Structuralsegmentations ofdifferent styles of buildings

試驗基于主頻2.0G Intel雙核處理器,2G內存的微型計算機平臺,對以上各建筑物模型復雜度和分割所用的時間進行統計,得到表1。從表1可以看出,中心提取與體元聚類所需時間與模型復雜度無直接聯系,而總分割時間卻與模型復雜度正相關。因此隨著模型復雜度的提高,模型分割的大多數時間將被用于體元化和表面分割。但由于復雜模型分割所需的整體耗時仍然不大,可見算法運行效率較高。

表1 建筑物模型復雜度與分割時間表Tab.1 Complexity of building models and time costs for segmentation

最后,由于該算法不依賴于模型表面構網方式,在試驗中還嘗試將其應用于建筑物的點云數據分割(點云數據的表面分割參見文獻[17]),也取得了很好的效果,如圖10(a)所示。但由于本文體元分析方法的核心在于通過體元聚類對建筑物模型內部空間分布進行有效分析,因此無論何種建筑物模型,都必須具有封閉的外表面;否則將無法確定其內部空間的準確范圍,進而產生無效的分割結果,如圖10(b)所示。

圖10 建筑物點云數據分割Fig.10 Segmentation of point clouds of buildings

5 結 語

本文提出的基于體元分析的建筑物模型結構化分割方法能夠對建筑物中具有獨立意義的主要結構單元進行有效分割,提取出建筑物最基本的形態結構。通過試驗驗證,該方法與模型表面的構網方式無關,適用于不同風格、不同數據類型三維建筑物模型的分割,具有極強的穩健性,運算效率較高。該方法的不足之處在于無法對建筑物模型局部的細小結構和表面特征進行識別和分割,并要求建筑物模型具有封閉的外表面。

進一步將研究建筑物三維模型的多尺度結構化分割,并基于建筑物結構化分割結果,探討在包括建筑物LOD建模在內的各類建筑物三維數據處理過程中保持建筑物基本結構特征的有效方法。

[1] ZHU Qing,HU Mingyuan.Semantics-based LOD Models of 3D House Property[J].Acta Geodaetica et Cartographica Sinica,2008,37(4):514-520.(朱慶,胡明遠.基于語義的多細節層次3維房產模型[J].測繪學報,2008,37(4): 514-520.)

[2] MENG Liqiu,FORBERG A.3D Building Generalization [C]∥Challenges in the Portrayal of Geographic Information:Issues of Generalisation and Multi Scale Representation.Amsterdam:Elsevier Science,2007:211-232.

[3] HOFFMAN D D,RICHARDS W A.Parts of Recognition [J].Cognition,1984,18(3):65-96.

[4] AL EKSEY G,THOMAS F.Randomized Cuts for 3D Mesh Analysis[C]∥Proceedings of ACM SIGGRAPH Asia’08.New York:ACM,2008:145-156.

[5] SHAMIR A.A Survey on Mesh Segmentation Techniques [J].Computer Graphics Forum,2008,27(6):1539-1556.

[6] LAVOUE G,DUPONT F,BASKURT A.A New CAD Mesh Segmentation Method Based on Curvature Tensor Analysis[J].Computer Aided Design,2005,37(10):975-987.

[7] PAGE D,KOSCHAN A,ABIDI M.Perception-based 3D Triangle Mesh Segmentation Using Fast Marching Watersheds[C]∥Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Los Alamos:IEEE Computer Society Press,2003:27-32.

[8] KATZ S,TAL A.Hierarchical Mesh Decomposition Using Fuzzy Clustering and Cuts[C]∥Proceedings of ACM SIGGRAPH.New York:ACM,2003:954-961.

[9] LU Y,GADH R,TAUTGES T J.Feature Based Hex Meshing Methodology:Feature Recognition and Volume Decomposition[J].Computer-Aided Design.2001,33(3): 221-231.

[10] THIEMANN F,SESTER M.Segmentation of Buildings for 3D-Generalisation[C]∥ICA Workshop on Generalisation and Multiple Representation. Leicester: [s. n.],2004.

[11] ATTENE M,FALCIDIENO B,SPAGNUOLO M.Hierarchical Mesh Segmentation Based on Fitting Primitives [J].The Visual Computer,2006,22(3):181-193.

[12] SIMARI P,KALO GERA KIS E,SIN GH K.Folding Meshes:Hierarchical Mesh Segmentation Based on Planar Symmetry[C]∥Proceedings of Eurographics Symposium on Geometry Processing.New York:ACM,2006:111-119.

[13] WADE L,PAREN T R E.Automated Generation of Control Skeletons for Use in Animation[J].The Visual Computer,2002,18(2):97-110.

[14] WANGJiale,HE Yuanjun,TIAN Haishan.Voxel-based Shape Analysis and Search of Mechanical CAD-Models [J]. Forschung im Ingenieurwesen,2007,71(4): 189-195.

[15] FANG Shiaofen,CHEN HongSheng.Hardware Accelerated Voxelization[J].Computers&Graphics.2000,24(3): 433-442.

[16] FOUMIER A,MONTUNO D Y.Triangulating Simple Polygons and Equivalent Problems[J].ACM Transaction on Graphics,1984,3(2):153-174.

[17] ADAN A,HUBER D.Reconstruction of Wall Surfaces under Occlusion and Clutter in 3D Indoor Environments [R].Pittsburgh:Robotics Institute,Carnegie Mellon University,Tech.Rep.CMU-RI-TR-10-12,2010.