基于體元分析的三維建筑物模型結(jié)構(gòu)化分割方法

孫 軒,楊必勝,李清泉,

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

1 引 言

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

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

針對現(xiàn)有三維模型分割方法在建筑物基本結(jié)構(gòu)特征識別方面存在的不足,本文主要針對建筑物不規(guī)則三角網(wǎng)表面模型,從模型內(nèi)部對其結(jié)構(gòu)組成進行分析,提出了一種基于體元分析的建筑物結(jié)構(gòu)化分割方法。

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

2 體元分析與結(jié)構(gòu)化分割

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

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

圖2 建筑物模型結(jié)構(gòu)化分割流程Fig.2 Flow chart of structural segmentation of building models

3 分割算法

3.1 距離場計算

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

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

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

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

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

圖3 建筑物內(nèi)部分層距離場構(gòu)建Fig.3 Distance field construction by level in building model

3.2 中心體元提取

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

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

圖4 建筑物水平體元層內(nèi)中心體元提取結(jié)果Fig.4 Midvoxel extraction from horizontal level of building voxels

3.3 體元聚類

體元聚類是建筑物結(jié)構(gòu)化分割的關(guān)鍵。按照算法執(zhí)行順序,該過程分為中心體元聚類、內(nèi)部體元聚類和外部體元聚類三個步驟。

3.3.1 中心體元聚類

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

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

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

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

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

3.3.2 內(nèi)部體元聚類

內(nèi)部體元聚類的實質(zhì)是依據(jù)中心體元聚類結(jié)果,將各水平體元層中的內(nèi)部體元劃歸到中心體元所屬的不同結(jié)構(gòu)單元中。

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

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

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

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

圖6 內(nèi)部體元聚類Fig.6 Clustering of inner voxels

3.3.3 外部體元聚類

外部體元聚類過程主要依據(jù)鄰域擴張原理,通過對其鄰域中內(nèi)部體元的類別進行判斷來實現(xiàn)。

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

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

3.4 表面分割

表面分割是建筑物模型結(jié)構(gòu)化分割的最終環(huán)節(jié),其關(guān)鍵在于將體元聚類結(jié)果投影到原始建筑物表面模型。

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

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

4 試驗與分析

本文選取了一些具有明顯時代和地域特征的建筑物進行試驗,其模型分割結(jié)果如圖9所示。從試驗結(jié)果來看,該算法能夠?qū)Σ煌L格建筑物水平和垂直分布的主要結(jié)構(gòu)單元進行有效分割,具有很強的穩(wěn)健性;另一方面,可看出基于體元分析的結(jié)構(gòu)化分割方法無法對建筑物模型局部的細小結(jié)構(gòu)和表面特征進行有效識別和區(qū)分,如歐式建筑屋頂?shù)募馑?、羅馬建筑底部的立柱、東方建筑飛檐的紋理等。

圖9 各類建筑物結(jié)構(gòu)分割結(jié)果Fig.9 Structuralsegmentations ofdifferent styles of buildings

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

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

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

圖10 建筑物點云數(shù)據(jù)分割Fig.10 Segmentation of point clouds of buildings

5 結(jié) 語

本文提出的基于體元分析的建筑物模型結(jié)構(gòu)化分割方法能夠?qū)ㄖ镏芯哂歇毩⒁饬x的主要結(jié)構(gòu)單元進行有效分割,提取出建筑物最基本的形態(tài)結(jié)構(gòu)。通過試驗驗證,該方法與模型表面的構(gòu)網(wǎng)方式無關(guān),適用于不同風格、不同數(shù)據(jù)類型三維建筑物模型的分割,具有極強的穩(wěn)健性,運算效率較高。該方法的不足之處在于無法對建筑物模型局部的細小結(jié)構(gòu)和表面特征進行識別和分割,并要求建筑物模型具有封閉的外表面。

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

[1] ZHU Qing,HU Mingyuan.Semantics-based LOD Models of 3D House Property[J].Acta Geodaetica et Cartographica Sinica,2008,37(4):514-520.(朱慶,胡明遠.基于語義的多細節(jié)層次3維房產(chǎn)模型[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.