基于結構特征的海量三維模型管理方法

陳充澤， 蔡鴻明， 姜麗紅

(上海交通大學軟件學院，上海 200240)

基于結構特征的海量三維模型管理方法

陳充澤， 蔡鴻明， 姜麗紅

(上海交通大學軟件學院，上海 200240)

虛擬現實和 3D可視化技術的發展帶來三維模型的海量增長，傳統方法采用關鍵字匹配方式檢索和管理海量模型數據，不能滿足語義級別的模型檢索和管理要求。提出一種基于結構特征的海量三維模型管理方法。使用該方法的思路框架，分析海量模型實例，通過聚類與分類的方法進行概念發現，構建管理特定領域的本體庫，基于本體庫設計并實現基于結構特征的三維模型管理系統，最后對系統進行應用和驗證。結果表明該方法很好地解決了傳統三維模型管理從單一維度管理模型的低效、冗余和難以重用，實現了三維模型的多維度高效檢索和管理。

虛擬現實；三維模型；本體；語義

虛擬現實和3D可視化技術的飛速發展，促進了三維模型的廣泛應用。由此帶來的海量模型管理成為一個比較大的難題。傳統方法是通過基于關鍵字或者模型簡單幾何特征的方式進行管理，都存在一定的局限性。但通過領域本體模型可以很好的從多個維度描述一個模型，實現語義層次的檢索，使得模型數據管理的性能有很大地提高。另一方面，越來越多的虛擬現實環境也對三維技術與其他技術產生了需求，比如三維形體的語義檢索，三維物體的結構信息表述，三維物體的重用等。如果沒有良好的軟件支持，將極大地限制三維模型在設計和應用中所起到的作用。因此，針對海量三維模型的管理對底層的軟件提出了更高的需求。

目前基于內容和關鍵字的模型管理研究，在學術界和產業界的應用已較為成熟。普林斯頓大學形狀檢索與分析小組開發的三維模型搜索引擎 3D Model Search Engine和谷歌公司開發的基于三維建模軟件 SketchUp的模型檢索和管理系統 3D Warehouse采取傳統的關鍵字匹配方法，由于不同用戶對關鍵字的理解不相同，所以這種方法存在耗時費力，結果不準確等諸多問題。由于關鍵字很難描述三維形體表示出來的所有信息，因此很難保證查準率和查全率[1-2]。國內的一些研究已經在嘗試使用本體語義規則來進行三維模型的檢索和管理，但對于幾何結構特征的分析還不完全。翁承志[3]在其論文中提出了一種方法：利用本體給三維形體添加語義信息，利用本體的推理功能，最后調用相關程序，利用現有模型引導出相關的三維場景動畫，并在計算機上顯示出來，以滿足初學者實現三維場景的智能交互的功能需求。該方法的不足在于必須事先構建相關領域的本體庫，并且所實現的檢索主要是內容和關鍵字檢索。阮佳彬等[4]提出了基于本體詞匯的三維模型語義檢索的方法。首先對一個三維模型庫的詞匯進行語義上擴充，然后基于關鍵詞進行檢索，而不是做簡單的文字匹配。能有效地將一個分類不夠豐富的模型庫的詞匯做較大的擴充，使其覆蓋的范圍擴大，同時保證擴充的詞匯和原有詞匯在語義上的相關性，從而提高基于語義關鍵詞檢索三維模型的有效性。不足在于沒有挖掘自身結構方面的語義關系，導致檢索能力不強。

本文將基于 X3D模型技術——專為萬維網而設計的三維圖像標記語言，提出一種利用本體技術基于結構特征來進行三維模型管理的方法(a massive three-dimensional model management approach based on structural features, 提出TMMA框架)，輸入海量模型文件生成實例，通過分析實例的結構特征進行聚類和分類并提取結構間關系，通過概念發現算法生成相關領域本體庫，基于本體庫設計三維模型管理系統，很好地解決了傳統三維模型管理從單一維度管理模型的低效、冗余和難以重用，實現三維模型的多維度高效檢索和管理。這一問題的解決將給三維模型應用環境提供極大的便利。

1 語義本體的構建與進化

在知識管理領域，本體的研究具有重要的意義，本體論的出發點在于知識的共享和重用[5-6]。為了讓計算機能理解本體，通常采用具有推理能力的形式化描述語言來表示本體。本文將采用基于語義網絡的本體描述語言OWL。OWL建立在XML/RDF等已有標準的基礎上，通過添加大量的語義描述元語支持本體的描述和使用。

本體的構建(ontology building)[7]主要有以下三種方式。人工構建本體(主要有普林斯頓大學開發的WordNet[8]，斯坦福大學開發的Protégé[9])，半自動本體構建和自動本體構建。人工構建并開發本體的方法費時、費力、成本很高，導致本體的構建成為一項艱巨的任務。半自動和自動化本體構建中的數據源大多來自領域文檔，或者來自于互聯網信息，利用機器學習和統計等技術，從這些文檔和互聯網信息中將相關領域概念中抽取出來，再根據聚類、分類等方法建立起概念之間的關系，獲取期望的本體。本文通過對海量三維模型進行聚類與分類，對機器學習獲取的概念進行定義(賦予名稱)，以準自動化的方式完成本體構建。

本體進化(ontology evolution)，又稱作本體演化，就是在現有領域本體基礎上，依據一定的理論、方法和標準，根據應用的需要，對本體概念結構、概念及關系不斷進行豐富、完善、改進、更新和評估的過程與方法[10-11]。這一界定主要強調兩點：①本體概念的不斷豐富；②本體概念的更新。本文運用本體進化技術，處理可能出現的新模型類帶來的本體概念更新以及舊模型類的淘汰。

2 基于結構特征的三維模型管理

本文的研究主要圍繞基于結構特征的三維模型管理方法(three-dimensional model management approach，TMMA)的框架研究。通過初期的海量X3D三維模型輸入，建立和完善初始本體；本體建立后，后期的模型輸入，可使用本體推理自動分類管理，并在模型輸入過程中繼續完善和進化本體。通過本體管理三維模型，可以提高檢索效率，消除二義性，提高一致性。研究框架如圖1所示。

圖1 三維模型管理方法框架

本文將以家具領域 X3D模型管理為例，介紹TMMA框架的實現思路。系統的關鍵算法(X3D模型→模型實例→初始本體)為：首先，模型按照基本形狀，形狀間拼接形式，通用屬性等進行實例化；然后對實例化后的大量模型進行概念發現(如聚類、分類算法等)；最后在有監督的學習過程中進行本體概念生成，生成初始本體庫。利用初始本體庫進行模型管理，利用本體進化維護概念的更新和完善。

3 基于結構特征的模型管理算法

3.1 模型“骨架”抽取

模型文件分析與預處理：家具正常擺放在地面上，從機器的角度說就是相對于地面沒有經過任何角度的旋轉和倒置。在計算機驗證碼圖像識別技術中，顧翼和武妍[12]提到的基于細化的算法先用基于點像素的細化算法獲得字符骨架，然后檢查叉點，再將叉點間的線段提取出來，最后根據一些預定義規則將這些線段進行合并。借鑒這種處理思路，可以將三維模型進行扁平化處理，將空間體轉化為線和面，提取三維模型的主要結構特征，即“骨架”。處理過程中將涉及的主要類型是空間體→面，空間體→線，空間面→線等。

“骨架”抽取的主要規則涉及以下情況：

(1) 長方體→面或線

步驟 1. 給定長方體的邊長集合為 B = {l, d, h}，其中三條邊不完全相等。

步驟2. 取邊長集合中最短邊 s ={l, d, h}min，其中min表示取集合中最小數即最短邊。

步驟 3. 消去邊長集合B中的最短邊s得到新集合B′ = {l - s, d - s, h - s}，此時新邊長集合B′中有一條邊被消去，即邊長為0，得到面；有兩條邊被消去時，得到線；特殊情況處理：產生面時，若剩余的兩邊比例(短邊∶長邊)小于設定閾值0.2，則將短邊消去，歸約為線。圖2(a)為長方體到線的歸約。

(2) 圓柱體→長方體

步驟 1. 給定圓柱體參數集合 C = {r, h}，其中r為圓柱體底面半徑，h為圓柱體側面高度。

步驟 2. 作圓柱體底面圓的外切正方形，邊長d = 2× r，側面高度h保持不變，與底面正方形一起作一個長方體。

步驟 3. 得到長方體之后使用(1)的歸約方法。由于底面是正方形，故通常最終被歸約為線，見圖2(b)。

(3) 復雜情形

如圖2(c)為某家具的背，由幾條縱橫交錯的柱體組成。分析思路是將所有柱面歸約為平面長方體，再使用(1)的歸約方法。分析步驟如下。

步驟 1. 假設組成背面的柱體集合為V，得到集合中的任意柱體 vi∈ V, i = 1,2,… ,n 。

步驟 2. 對于V中任意三個平行柱體 vi, vj, vk∈V，其中vi∥ vj∥ vk，與 va∈ V均相交，可以判斷這四個柱體共面。

步驟 3. 由步驟(2)證得所有柱體共面，將V中柱面歸約為輪廓組成的最小包圍長方體M，見圖2(c)。

圖2 “骨架”抽取的主要規則

定義如表1，若將三維模型“骨架”與地面H做參照。其中與地面H水平的面叫做面(plane，P)，每一個面都有長邊(long edge，LE)與短邊(short edge，SE)，與地面垂直的面叫做背(back，B)，與地面垂直的線叫做腿(leg，L)。

表1 “骨架”參數定義

同時將“骨架”分層處理，按幾何結構分層，一個(組)B，P，L為一層。分層的基準按照拼接方式的改變，此處的改變主要為垂直拼接(真實環境中碰到分層的接口處，需用螺絲等加以固定，分層的核心就是找出這些螺絲固定處)。由下至上，如圖3(a)常見的椅子層次結構為椅子腿，椅子面，椅子背三層結構。

圖3 椅子的分層結構

3.2 “模型→實例”映射

經過抽取得到模型“骨架”后，將模型文件實例化，映射集M定義如下：

其中，T是三維模型“骨架”集，D是映射后的模型實例集，P是模型結構間對應的屬性關系集。實例di∈ D對應結構連通圖 Fi。

算法1. 模型實例的批量映射

輸入：模型“骨架”集 T={t1, t2, t3, … , tn}

屬性關系集合 P={ p1, p2, p3, … , pn}

輸出：模型實例集合 D={d1,d2, d3, … , dn}

FOREACH ti∈ T DO

FOR由下至上遍歷“骨架”結構

IF發現結構拼接點 THEN

掃描當前所在層結構形狀作連通圖 Fi頂點；

END IF

若頂點中有面，計算邊長比 r = l/ s；

END FOR

連接 di連通圖 Fi的頂點間屬性關系 pj∈ P；

END FOREACH

以圖 3(a)中椅子模型“骨架”ta為例分析層次結構，得到各層的拼接關系，生成結構連通圖 Fa為實例 ia，如圖3(b)。

3.3 本體概念發現過程

得到模型實例后，進入領域本體構建階段，概念發現集B定義如下：

其中，D是算法1中得到的實例集，C是本體概念集。經過三維模型到實例的映射之后，需輸入大量實例，可達數百個以上的規模，被稱為訓練集，對相似實例進行聚類和分類，完成監督學習過程，識別出各個簇的家具概念，如，沙發、桌子、櫥柜、椅子、床等，構建初始的家具本體庫。

算法2. 模型概念發現

輸入：模型實例訓練集 D={d1, d2, d3, … , dn}

輸出：領域本體概念集合 C={c1, c2, c3, … , cn}

FOREACH di∈ D DO

LET 層次數相同的連通圖 Fi聚集，得到簇集K END FOREACH

FOREACH ki∈ K DO

匹配 Fij頂點，完全匹配的再次細分簇集 K1END FOREACH

FOREACH k1i∈ K1DO

IF F1ij有邊長比 r = l/ s THEN

根據r的范圍[1,1.5) ∩ [1.5,+ ∞)細分概念集C END IF

END FOREACH

由此算法可以得到構建的初始家具本體樣例如圖4所示。

圖4 家具本體樣例

三維模型實例中還包含一些通用屬性，如顏色(color)，紋理(texture)，材質(material)等，而這些屬性往往無法反應在結構特征中，需要單獨提取出這些屬性特征。首先創建本體中相應的通用屬性概念color，texture，material，然后提取模型的通用屬性。需要注意的是，模型的通用屬性不影響模型結構特征和模型本質，即不影響概念發現過程。

3.4 實例自動匹配過程

按照本體語義網中所定義的本體類和屬性，建立類的實例，這一過程稱為語義標注[13]。可以直接以手工的方式定義類實例，也可以通過信息抽取的方法自動、批量地從數據庫和其他數據源中獲取實例數據。若仍以手工方式進行語義標注，則失去了研究的意義，因此本文給出了一種自動化實例匹配的方案。在原始的家具本體建立之后，根據TMMA框架，新的三維模型文件可以由本體推理自動匹配進行歸類。自動匹配的過程以圖5為例。

步驟 1. 給定未知模型實例家具a和原始家具本體庫C={c1, c2, c3, … , cn}。

步驟 2. 分析家具a結構可知家具a“有”面a，且面a“垂直拼接”腿a。

步驟3. 遍歷本體庫 C={c1,c2, c3, … , cn}中概念，找到概念 ci∈ C為桌子， ci“有”桌面，且桌面“垂直拼接”桌腿，腿a是桌腿是一個實例，面a是桌面的一個實例，且實例內部關系匹配概念 ci內部關系，由此得到推理結果家具a屬于概念 ci，即桌子類。

圖5 本體推理家具a屬于桌子類

若自動匹配的過程中找不到合適的本體概念進行歸類，那么原始家具本體語義網絡將進行進化。進化的原因可能是科學技術的進步導致出現新型家具，因此該過程往往需要人工參與，識別新型家具類型并定義與之相關的本體概念。

4 三維模型管理系統的設計

4.1 系統概要設計

本文設計的三維模型管理系統采用現今流行的B/S架構。前臺用bootstrap+jquery+x3dom實現交互，其中x3dom是一個開源項目，對瀏覽器中的WebGL接口進行了封裝，供用戶調用顯示 x3d文件。服務器端主要使用java語言進行編寫，后臺采用SSH2框架，數據庫采用輕量級的MySql。本體部分使用OWL本體語言和jena API。

4.2 系統體系結構

針對海量三維模型管理的需求，本文設計開發了一種基于結構特征的海量 X3D模型管理系統，以支持對X3D模型文件的語義檢索與管理的支持。為方便協作和開發，系統采用三層架構，從人-機交互開始，依次為界面層、應用層和后臺服務層，其體系結構如圖6所示。

圖6 系統體系結構圖

(1) 界面層。用戶通過設計良好的人-機交互界面，包括上傳模型，檢索與管理模型等接口。上傳界面支持選中多文件批量上傳處理。檢索與管理界面提供基于關鍵字與語義的檢索。

(2) 應用層。系統的核心設計層，主要包括模型解析模塊和模型管理模塊。模型解析模塊對用戶批量上傳的大量模型文件進行實例化和“骨架”抽取，獲得模型的結構特征。通過概念發現算法，構建三維模型基礎本體庫。本體管理模塊主要包括模型的檢索、模型實例的語義標注、實例不匹配現有本體庫時進行本體進化。

(3) 服務層。系統的底層技術基礎，包括所運行的環境，應用的模型解析工具、網絡通信協議和數據庫技術等。

5 三維模型管理系統的應用

隨著社會進步，人類生活水平的提高，對于家裝的要求也越來越高。虛擬現實的應用使得人們可以足不出戶，就看到各種以現實生活家具為原型的三維立體模型。這樣的變化無論對于業內專家、設計人員和客戶來說都是全新的體驗。隨著三維模型的增加，模型數據變得更加臃腫，帶來的問題是模型數據的檢索與管理越來越困難。本文以家具的設計和展示為例對基于結構特征的三維模型管理系統進行應用和驗證。家具管理本體和系統的建立流程如圖7所示。

圖7 家具領域本體和管理系統的建立流程

5.1 模型分析

這個過程往往需要業內專家和系統管理員參與，對于導入的海量家具三維模型進行分析，提取模型的結構化信息。如圖8，家具A具有3層結構由上至下分別為B、P、L三層結構，且面的長寬比(AspectRatio)為 1.00。在右邊窗體可看到模型的可視化信息以及三維模型的源碼信息。

圖8 家具A模型分析示例

5.2 模型檢索

系統提供了兩種檢索的模式，一種是傳統的基于名稱的檢索模型，輸入名稱并搜索模型；另一種則是語義檢索模式，用戶可以根據條件檢索，例如有靠背的家具，藍色的家具等等。圖9是一種有腿家具(hasLeg)的檢索結果。

5.3 模型重用

用戶在檢索模型的同時，可以根據需要獲取所需模型進行重用。所有的模型實例都將存儲于實例數據庫中，方便存儲與管理。

圖9 “有腿的”家具檢索結果

5.4 與現有其他系統的比較

表2列舉了從初始本體依賴、本體建立的自動性和可進化性、物體關系抽取、查詢接口、模型規模以及模型重用等多個方面對本文系統與第2節中提到的另外兩個同樣基于本體技術，與本文系統功能接近的三維模型檢索與管理系統的比較。

表2 三種基于本體的模型管理系統比較

相比翁承志[3]和阮佳彬[4]的系統，本文系統的優勢有：無需事先召集業內專家與技術人員共同構建初始本體；支持海量模型的輸入，通過模型“骨架”抽取，基于模型的幾何特征進行聚類和分類；分析過程中系統自動學習與構建本體，且具備本體進化的能力；檢索模型時，系統可以進行實例自動匹配；能支持模型重用，具有良好的適應性和可擴展性。

6 結論與展望

虛擬現實和3D可視化技術的飛速發展，三維模型大規模應用，針對海量三維模型管理難題，提出一種基于結構特征的模型管理方法。將海量的三維模型進行實例化，通過概念發現與機器學習的方法建立相關領域的管理本體，設計并實現基于該方法的模型檢索與管理系統，并以家具領域為例進行系統的應用。在本體語義網的幫助下，可以實現語義級別的檢索與管理，以彌補傳統方法簡單的基于關鍵字搜索的不足。給設計人員和普通用戶帶來極大的便利和啟發。后續的研究將在模型重用部分再進行擴展，希望可以進行同類型模型的重組，例如模型A的部分模塊和模型B的部分模塊組成模型C。另外，本體庫的建立也將繼續優化和完善，以支持更通用和更復雜領域的模型管理。

[1]Li Zongmin, Wu Zijian, Kuang Zhenzhong, et al. Evidence-based SVM fusion for 3D model retrieval [J]. Multimedia Tools and Applications, 2013, 72： 1-19.

[2]Gao Yanli, Hu Bailin, Jia Yonghua. 3D GIS model building based on sketchUp [J]. Applied Mechanics and Materials, 2013, 353： 3507-3510.

[3]翁承志. 基于本體的三維場景智能交互應用研究[D].汕頭： 汕頭大學, 2010.

[4]阮佳彬, 楊育彬, 林金杰, 等. 基于本體詞匯的三維模型語義檢索[J]. 計算機科學, 2009, 36(2)： 152-154.

[5]Alves H, Santanche A. Folksonomized ontology and the 3E steps technique to support ontology evolvement [J]. Web Semantics： Science, Services and Agents on the World Wide Web, 2013, 18(1)： 19-30.

[6]Nardi J C, Almeida Falbo R D, Almeida J P A, et al. Towards a commitment-based reference ontology for services [C]//Enterprise Distributed Object Computing Conference (EDOC) of 17th IEEE International, 2013：175-184.

[7]Ludovici V, Smith F, Taglino F. Collaborative ontology building in virtual innovation factories [C]//Collaboration Technologies and Systems (CTS), International Conference on. IEEE, 2013： 443-450.

[8]Fellbaum C. Wordnet [M]//Roberto P, Healy M, Kameas A. Theory and applications of ontology： computer applications. Springer Netherlands, 2010： 231-243.

[9]Zhao Huiqun, Zhang Shikan, Zhao Junbao. Research of using protégé to build ontology [C]//Proceedings of the IEEE/ACIS 11th International Conference on Computer and Information Science. IEEE Computer Society, 2012：697-700.

[10]Hartung M, Terwilliger J, Rahm E. Recent advances in schema and ontology evolution [M]//Bellahsene Z, Bonifati A, Rahm E. Schema matching and mapping. Springer Berlin Heidelberg, 2011： 149-190.

[11]Rodríguez-García M á, Valencia-García R, García-Sánchez F, et al. Creating a semantically-enhanced cloud services environment through ontology evolution [J]. Future Generation Computer Systems, 2014, 32： 295-306.

[12]顧 翼, 武 妍. 基于結構知識的手寫體漢字合成方法[J]. 計算機工程, 2011, 37(3)： 266-268.

[13]Shi Mengwei, Cai Hongming, Jiang Lihong. An approach to semi-automatic semantic annotation on Web3D scenes based on an ontology framework [C]//Intelligent Systems Design and Applications (ISDA) of 12th International Conference on, 2012： 574-579.

A Massive 3D Model Management Approach Based on Structural Features

Chen Chongze, Cai Hongming, Jiang Lihong
(School of Software, Shanghai Jiao Tong University, Shanghai 200240, China)

The development of virtual reality and 3D virtualization technology leads to massive growth of 3D models, and the traditional method focuses on keyword matching to retrieve and manage models, which cannot meet the requirement of semantic retrieval and management of 3D models. To solve this problem, a massive 3D model management approach is proposed based on structural features. According to the core framework of the method, the massive model instances for concept discovery is analyzed by clustering and classification, the ontology is built in any specific field, and a 3D model management system design and implemented based on structural features, the system applied and validated at last. The experiment results show that the proposed method can solve the problems of inefficiency, redundancy, difficult to reuse in traditional method, and achieve the goal of multi-dimension retrieval and management of 3D models.

virtual reality; 3D models; ontology; semantics

TP 391

A

2095-302X(2015)01-0095-07

2014-08-11；定稿日期：2014-08-20

國家自然科學基金資助項目(61373030，71171132)

陳充澤(1988-)，男，浙江平陽人，碩士研究生。主要研究方向為信息可視化技術、協同建模。E-mail：ccz217@sjtu.edu.cn

蔡鴻明(1975-)，男，貴州盤縣人，副教授，博士。主要研究方向為CAD/CG、信息集成技術。E-mail：hmcai@sjtu.edu.cn