基于特征提取的三维模型检索技术研究

俞晓妮

沈阳职业技术学院，辽宁沈阳110045

0 引言

随着信息技术的发展，计算机信息检索的对象己经从文本、声音、图像和视频等多媒体数据类型，扩展到真实丰富的三维模型。三维模型广泛应用于机械产品设计、建筑工业设计、虚拟现实、3D 游戏、影视动画等领域。对三维模型检索技术的研究不仅有重要的理论意义和实用价值。

三维模型检索系统可以分为通用领域和专业领域的三维模型检索系统。目前己经出现了基于WEB 的通用领域的三维模型检索系统，用户可以通过网络使用这些检索系统来检索自己需要的模型，但检索还有一定的局限性。近年来专业领域的三维模型检索系统得到了广泛的应用，比如生物分子、机械零件、地形匹配等。这些检索与通用领域的三维模型检索系统具有较大的相似性，但也具有自身的特点。通常而言，专业领域的三维模型检索系统可以利用专业领域模型的特点、需求等信息，快速地检索出所需模型。具有如下特点：1）专业领域信息强。在各自的领域可能需求的精确性不高，这样可以缩短检索的时间;2）模型结构复杂度较低，也比较有规则，如机械零件模型、工程动画中的常见模型等，这样在特征提取方面较容易实现。

1 三维模型检索简介

近些年来，针对文本信息的检索技术日臻完善，针对二维图像以及影视资料的检索技术迅速投入应用，Google 和百度等著名搜索引擎的出现已经改变了人们查找信息的固有方式。相比文字和二维影像的检索，对于三维模型的检索更具有其复杂性和特殊性。尽管也有数量不多的机构提供模型检索服务，然而无论是从检索的效率还是结果的准确性等因素上来考虑，现有的模型检索技术距离高质量的商用水平仍有很大的提升空间。广阔的应用前景吸引了世界各地的研究人员投入大量的时间和精力从事模型检索相关领域的研究和推广，并逐渐形成了相对统一的三维模型检索的系统架构。如图1 所示。

图1 三维模型检索系统架构

一个完整的三维模型搜索引擎通常包括离线和在线两个并行的部分，分为数据获取、数据分析与检索匹配三大模块。

离线部分由数据的获取和数据的分析组成，具体的流程包括：

1）通过“网络爬行器”等途径获取三维模型；

2）提取三维模型的特征；

3）根据特征建立索引等。

在线部分即检索匹配，具体的流程包括：

1）用户通过交互界面选择查询方式提交查询；

2）根据查询方式进入相应的特征提取模块提取相应的特征；

3）进入匹配模块和索引模块，返回特征最相近的结果。

这三个功能模块都在模型检索系统中发挥着重要作用，算法设计的优劣关乎系统整体的检索性能、精确度和有效性。作为检索三维模型文件的界面要能够易于普通用户快速地学习和使用，使得用户在短暂的时间内能够充分表达清楚自己的检索诉求。检索系统在获得用户提供的特征描述后，要能迅速从中提取有效信息并与数据库中现存的特征进行比对。

模型检索系统应该对相关的模型提取出相近的特征描述，同时能够有效地区分不相关的模型。在交互系统中，特征提取和匹配的计算过程应在较短的时间内完成，不应使用户感到明显的延迟。寻求更高效准确的特征描述和匹配算法一直是科研人员不断追求的目标和研究的重点。随着三维模型文件数量的急剧扩张，从超大容量的数据库中快速地提取出查询结果也已成为模型检索中函待解决的问题。因此如何建立高效的索引结构以满足用户对检索效率日益提高的需求也逐渐引起了学术界与产业界的高度重视。

三维模型检索系统研究尽管取得了一定的进展，但还处于初期阶段，很多技术稳定性还不够，三维模型检索技术还有待于进一步的研究。三维模型检索系统发展趋势主要集中在以下几个方面：

1）现有检索技术一般针对整体特征进行检索，未来的检索技术应该具备整体和局部检索的功能，不仅能从同类物体中检索对象，还要能从异类物体中检索对象;不仅能从几何特征检索，还可根据物体的颜色，材质，粗糙度等属性进行检索；

2）从检索效果来看，现有技术还不能满足用户的需要，开发与三维模型输入格式无关、与模型局部坐标系无关的检索技术成为一个重要的研究方向；

3）建立一个合理的、权威的、统一的评价体系；

4）现有检索界面不能满足某些人群的需要，开发适合通用、专业领域的界面成为一个重要研究方向。

2 三维模型特征提取方法比较

2.1 基于轮廓形状的特征提取

计算并比较三维模型的轮廓特征，从而获得三维模型的几何相似性，是基于轮廓形状的几何特征提取算法实现的思想。其中，三维模型轮廓特征主要包括了顶点以及网格的分布特征。

Osada 提出了通过随机采样来获得三维模型的几何特征的形状分布方法。对于从三维模型表面上随即采样到的两个点，可得到它们之间的欧氏距离(DZ 距离)，统计通过以上方法而得到的大量的欧氏距离，可获得三维模型的形状分布曲线。

形状分布直方图算法可以简要概述为：首先使用几何函数来计算三维模型顶点的形状特征，从而获得形状特征分布直方图，然后比较直方图的相似距离以获得三维模型的几何相似性。

2.2 基于拓扑形状的特征提取

通过比较三维模型的拓扑结构来获得三维模型相似性，这是基于拓扑形状的三维模型相似性比较算法的核心思想。其中，最常使用的拓扑结构信息包括三维模型的分支与连通性等。模型的Reeb 图是从连通区域的角度来计算三维模型的拓扑结构。在该方法中首先将三维模型投影到二值图像，从而作出二值图像的Reeb 图，然后计算Reeb 图的基本元素，包括圆环的个数Nuln(R)、向上分支个数Num 口B)、向下分支个数Num 侧B)、每个分支的枝权数量Sum。最后，根据Reeb 图的这些基本元素，计算出Reeb 图的特征，

采用基于多分辨率Reeb 图的骨架提取方法，不仅可以描述三维模型的特征，同时还具备了描述模型的空间拓扑关系的能力。对于局部匹配乃至全局匹配该方法都是较为适用的。

在描述三维模型拓扑结构的方法中，除了Reeb 图以外，还有中轴线方法。从三维模型骨架的角度来计算三维模型的拓扑结构是中轴线方法的思路。

2.3 基于视觉形状的特征提取

在基于视觉的三维模型相似性比较算法中，通过比较三维模型在各个方向的视觉图像的形状相似性可以获得三维模型的相似性。

基于视觉相似的特征提取方法的提出是基于这样一个事实：从任意视角来观察两个相似的物体，它们都应该具有相似性。通过比较三维模型在多个方向的视觉图像的形状相似性来获得三维模型的相似性是基于视觉形状的特征提取方法的基本思想。在该方法中，首先将三维模型投影到二维视图上，再从不同模型对应的二维视图提取特征进行相似性匹配计算。在这种算法中，基于二维轮廓图的比较和基于视觉相似的检索技术是较为典型的例子。

Lomer 在预处理阶段，采用以一组二进制表达的二维图像来对三维模型的特征进行描述的方法，然后在对应的二维图像之间进行后续的相似性匹配计算，并且应用了图像检索中关于特征提取的方法。

在基于透视投影的三维模型几何相似性比较算法中，先将三维模型用正二十面体包围，而后选取若干个视点对三维模型进行投影，由此可以画出二值图像的Reeb 图，再通过计算Reeb 图的特征从而求出投影图像的拓扑相似距离，最后可得到三维模型的相似距离。

基于3D 模型的ZD 轮廓图的比较方法中，从三维模型正视、俯视和侧视三个固定方向提取出模型的轮廓图，首先找到这样一个圆，该圆恰好包括了轮廓图，将该圆等分成固定数量的圆环，构成圆环函数，然后对每个圆环进一步分解，使其由一系列三角函数的和构成;根据旋转不变频率的振幅，可计算出每个圆环的特征向量，最后，利用所有的圆环特征向量构成模型轮廓图的二维特征向量。

3 三维模型检索系统的设计与实现

3.1 系统硬件和软件配置

本系统采用了普林斯顿大学的标准三维模型数据库，特征计算使用了OFF 文件，三维模型的显示使用了 FLT 文件。

机器配置 ：2.0 Intel P4、512 RAM、Geforce4 显卡。

开发工具 ：Visual studio 2003、Open Scene Graph 2.4。

3.2 三维模型数据库的获取及文件组织结构

普林斯顿大学的三维形状检索和分析研究小组构建了一个三维标准数据库用于检索性能测试。这些三维模型被转化成为统一的文件形式。经过筛选和手工分类，从中选择出比较有代表性的1814 个三维模型用于构造标准三维模型数据库。

这些模型被分为两个集合，称为训练集(Training)和测试集(Testing)，其中训练集和测试集中各包括 907 个三维模型。训练集用于算法不稳定时测试算法，测试集是算法稳定时与不同算法进行比较时采用的集合。为了对不同算法试验使用一个统一的数据库，以便于对不同算法的检索效果进行比较。本检索系统采用的三维模型库是从普林斯顿大学形状分析实验室网站上下载的标准数据库。

本系统的数据库共有1110 个模型，分为 64 类，每个类别中从0 开始顺序编号。三维模型是以文件的形式存放，对于每个三维模型一共包含 4 个文件：三维模型文件(.off)、三维模型的描述文件(.txt)、三维模型的二维缩略图文件(.jpg)、用于三维显示的文件(.flt)，将其分别存放在不同的目录中。

3.3 三维模型检索系统结构设计

三维模型检索系统主要包括用户检索界面、特征提取、特征匹配、特征向量数据库以及三维模型文件的二维和三维展示的管理，如图所示。用户使用检索界面进行三维模型检索，在检索界面中，本系统采用的是示例查询模式，在用户选中一个示例模型后，该模型的相应信息被自动传送到特征匹配模块，特征匹配模块将接收到的三维模型与三维模型特征向量和索引数据库中的特征信息进行匹配，从而得出检索的结果，并将结果返回到用户检索界面，供用户挑选需要的三维模型。特征匹配模块主要是圆环分割的方法和图像矩的方法。特征匹配模块将接收到的三维模型与三维模型特征向量和索引数据库中的特征信息进行匹配，从而得出检索的结果，并将结果返回到用户检索界面。特征提取模块主要是实现在正交主平面的基础上进行特征提取的方法，从三维模型库中提取三维模型的圆环分割信息和矩信息，并将这些特征信息保存到三维模型特征向量和索引数据库中。如图2 所示。

3.4 三维模型检索系统界面的设计

在检索系统界面中，左侧显示模型的分类树形结构，右侧为显示模型的三维窗口。根据数据的组织形式，用户从“类别”中选择用于匹配的索引三维模型种类，然后从“模型”下拉菜单中选择需要查找的三维模型。选完之后索引三维模型就会在右侧三维显示，用户可以与其交互。

为了使模型的显示更加直观，系统对模型进行了三维展示。首先将OFF 文件通过软件 Deep Exploration 将模型转换为 flt 格式 ，然后用开源的 Open Scene Graph 和 Visual studio 2003 编写 ActiveX 控件用于模型的三维展示。

在检索界面的左侧树形目录中显示了所有的 64 个分类的模型文件名，点击树形目录中的任意模型文件名称，在右侧的 ActiveX 控件窗口中可以方便的从各个角度浏览三维模型。通过鼠标的操作实现对模型的旋转、平移、缩放操作，并在模型的下方显示模型文件的名称和大小信息。

图2 三维模型检索系统示意图

3.5 三维模型检索结果显示设计

三维模型检索系统采用了示例查询的检索方式。用户可以通过树型目录在三维控件中浏览系统提供的所有的三维模型，并且从浏览的三维模型中选择一个三维模型进行检索。当检索一个模型时，在浏览界面中浏览三维模型确定检索目标，然后将检索结果在结果界面中显示。具体过程是用户点击检索按钮，系统就会首先对模型进行预处理，然后自动计算用户选择的三维模型的特征向量，最后根据计算出的特征向量搜寻特征向量数据库，计算模型之间的特征距离，按照距离由小到大的顺序在检索结果显示界面中列出最佳匹配模型的缩略图。用户可以点击缩略图，在右侧的三维显示窗口中从各个角度观看所选中的三维模型，并在下侧显示模型的大小信息，用户可以点击模型的二维缩略图，然后点击 Download 按钮来下载所需要的模型。

4 结论

本文设计的三维模型检索系统，主要从三维模型检索系统的文件组织形式、系统的结构、界面的设计、模型的三维展示等方面进行了介绍，对提出的特征提取方法进行了实验验证。检索系统通过示例三维展示的方式进行三维模型检索，即用户通过选择数据库中存在的三维模型进行三维浏览然后查询。系统中的三维模型、三维模型的二维缩略图以及三维模型信息采用文件方式存放，依靠操作系统的文件管理功能进行管理。此三维模型检索系统的具有简单易操作的特点，检索结果虽然还有不足的地方，但总的来看还是比较理想的，为进一步研究建立了很好的实验平台。