基于结构特征的海量三维模型管理方法

陈充泽， 蔡鸿明， 姜丽红

(上海交通大学软件学院，上海 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