基于二维投影的三维模型检索方法研究.doc

摘要3D数据获取技术、图形硬件、三维数据模型和可视化技术的发展，致使3D模型的增多。三维扫描技术与造型工具的日益普及，扩展了可供使用的三维模型数据库：互联网络的扩张增强了人们获取分散存储的三维模型的能力，并为有效传播高质量模型创造了条件，因此研究一种自动的、对用户友好的三维模型的检索技术成为一个重要的课题。对于基于内容的3D模型检索系统，最根本的问题是选取恰当的特征来区别不同的形状，以用来有效的索引相似的文件数据。3D模型检索方法可大致的分为3类：基于外形的低层方法；基于结构的高层方法；基于视角的方法。基于外形的低层方法尝试通过几何和拓扑的属性描述3D模型的形状，外形可以是由单独向量组成的一些外形参数的固定数值或一系列外形参数的分布范围；基于结构的高层方法尝试把3D模型分解成一系列关键部分，并提炼出这些部分的几何关系；基于视角的方法通过一系列从不同角度的二维投影来得出三维模型的外观。在对已有三维模型检索技术的进行系统研究的基础上，本篇论文提出了一种基于二维投影的三维模型检索方法，用以3D模型检索。此方法是以常量去转化并评价3D模型，并且它对于旋转是稳定的。实验数据显示，对于一些类型的三维模型，提出的基于二维投影的方法有着良好的查全率和查准率，是行之有效的方法之一。关键词：三维模型检索；基于二维投影；特征提取；相似度计算第一章绪论11研究的背景及意义我们处在一个三维世界里，一切被我们感知的物体都以三维的形式存在，人类的视觉不仅能够感知二维平面的信息，且具有立体三维的特性。与二维图像相比，三维的模型所提供的视觉感知细节更多、更丰富，能够给人们带来更加详细的信息。三维模型的研究成为了一个热点话题，是因为：(1)随着三维数据获取，如数字摄像机、扫描仪、核磁共振和3D激光扫描仪设备的功能越来越强，使用越来越方便，技术手段不断进步和成熟，使三维信息获取和表达变得越来越容易；(2)众多三维建模软件和工具(如3DMax，AutoCAD，Poser，Core3D等)使得三维模型的设计变得简单；(3)三维模型建模的专业需求越来越强，分子工程、地貌气象分析、工业产品设计、医学建模、虚拟军事行动等，都广泛使用了三维技术。构建数字化模型，可帮助科研人员更加直观、精确地处理各自领域问题；(4)在娱乐领域，游戏、电影产业的发展，使人们已经不满足于二维画面，传统的制作方法已经成为历史，精美绚丽的三维动画随处可见。而三维建模本身，也成为了一门艺术门派；(5)计算机图形学技术发展迅速，三维图形处理硬件和CPU的速度已足够快，而且价格便宜，使得三维数据能在微机上快速处理和显示；(6)蓬勃发展的互联网技术也使人们对信息共享和处理的方式发生了根本性的改变，网络已经成为人们获取信息的重要途径。互联网的普及，使三维模型被更广泛地转播和共享。(7)各软件，各版本的三维数据兼容化、共享化趋势，加速了模型的标准化进程。三维模型已成为继声音、图像和视频之后的第四种多媒体数据类型。目前有数以兆计的三维模型存在，而且每天都有大量的三维模型产生和传播，可以预见，在不久的将来，人们可以像使用二维图像一样使用三维模型。因此，为了从浩如烟海的信息中快速准确地找到需要的内容，人们存在着对三维模型进行检索的迫切需求。12三维模型检索系统的发展作为新兴的领域，三维检索有重要的学术意义及应用价值。如，目前在我国，知识产权保护工作越来越受到重视，而知识产权保护的相关工作量也越来越大。在各种专利尤其是外观设计的申请的核准、审查和批复的过程中，都需要对各种三维模型进行比较。在工业设计过程中，三维数据可以完全提供产品的几何信息，为了实现给料、加工、质检的自动化，需要反复快速地检索、匹配标准零件模型库，在一个大型数据库中找到适合的三维模型。数字化地球战略的推行，数字农业，生态环境保护，风险预警，路径规划应用中需要检索海量的三维模型标本。分子生物学基因技术中，蛋白质三维结构与功能的关系，是当前的重大科学问题，蛋变质三维结构相似性比较则是探索生命科学奥秘的重要手段，从计算机图形和视觉的角度来审视蛋白质三维空间结构的相似性检索，有着广阔的应用前景。互联网上也出现了大量的三维模型库，许多网站也将三维模型作为一种数字化商品提供给使用者。相对于二维多媒体信息的获取，三维模型的建模更加复杂。显然，搜索、共享大量的三维模型数据；在现有的模型基础上进行分类、比较、改进；把互联网，数据库技术与三维模型建模技术相结合显然更加节约成本。如今，人们的问题已经由“如何建造模型”转换为“如何检索所需要的现有模型。要在一个大型数据库中找到适合的多媒体信息，检索是一种必要的技术手段。三维模型检索的思想起源于三维模型识别，三维模型匹配以及基于内容的模型检索。在基于内容的三维模型检索领域，国外开展得比较早19971998年，加拿大国家研究院(National Research Council)的Paquet等最早对基于内容的三维模型检索技术进行了理论和算法的研究H1。自1999年以后，美国，德国，日本等国的研究人员相继投身于这个研究，如美国的普林斯顿大学(Princeton University)、华盛顿大学(Washington University)、布朗大学(Brown University)、卡耐基梅隆大学(Carbegie Mellon University)，德国的慕尼黑大学(Munich University)、波恩大学(Bonn University)，日本的IBM东京研究所，陆续提出了一些基于内容的领域三维模型检索系统，使三维模型检索成为比较活跃的研究领域。但是，总的来说，目前对三维模型检索同其他的多媒体数据检索系统一样，可以分为基于文本的检索和基于内容的检索。大多数的商用多媒体检索系统使用基于文本的关键词搜索来帮助用户寻找想得到的多媒体文件信息。为了促进搜索的准确性，多媒体数据库的管理人员需主要凭经验给多媒体数据注释易挑选的关键词。如果数据库非常庞大，则费时费力却难以完成任务。此外，恰当的关键词因人而异。通常最普遍的方法是从文件名、标题、上下文中提取关键词(如WwWgo091ecom，wWWbaiducom检索系统)。然而，当文件名不知所云(如abcdbmp，ni0001avi)，或毫无特点(如backgroldwav)时，这种方法显然无效，因此，开发基于多媒体数据内容自动而有效的检索系统已经成为一个重要的需求。基于形状的三维模型检索是指直接根据描述对象的形状特征进行检索，它能从数据库中查找到具有指定特征或含有特定内容的三维数据。面对日渐迫切的需要，已经有一些网站提供对三维模型的检索与下载服务，但由于主要应用的是文本关键字检索和目录浏览等手段，难以对复杂的模型进行充分描述，在这种情况下，对于三维模型进行有效检索方面的研究越来越受到人们的重视，很多研究机构开始对基于内容的三维模型检索系统进行研究，并取得了一定的进展。目前已经开发出一些实验性的三维模型检索系统。13论文组成部分介绍在下面章节，在第二章对三维模型检索技术的形成与发展做了概述。在第三章讨论了目前较常用的一些三维模型特征提取技术。在第四章，介绍了提出的一种三维模型特征提取方法，此方法称为基于二维投影的三维模型检索方法，并对实验结果做出了分析比较。第二章三维模型检索技术概述21二维图像检索物体之间形状相似性的比较，可以追溯到早期基于形状的图像检索：提取图像中感兴趣物体的轮廓或区域，采用不同方法描述其形状特征，将问题简化为形状特征的比较。借助于计算机视觉技术，人们可以定义多种二维形状表示方法和相似性度量。二维形状表示大致分为三类：特征向量法、变换形状方法与关系方法。具体选择哪一种表示方法取决于应用的要求，如目标形状的特征点，是否允许遮挡与形变的存在，噪声强弱，以及索引难易程度等。上述形状描述方法无法直接扩展应用在三维模型上，主要原因是他们要求为连续曲线(或平面上区域的边界)存在标准参数化表示。对于任意三维曲面，需要根据具体应用，恢复成一致曲面或流形曲面，得到相应曲面的参数，这样才能采取扩展的三维形状描述。在重建过程中，需要引入人工干预，以消除模型二义性。基于形状的图像检索系统用多维特征空间距离来衡量形状相似性。在特征维数不是很高的前提下，用索引结构组织特征向量，将加速数据库的访问。但是，由于人类的感知相似性并不等价于物体的拓扑相似性，单一特征无法完整描述物体的形状。因而需要提取多种形状特征，给出尽可能详尽的表示。为了满足创建索引结构的要求，需要将多特征进行降维处理。22三维模型检索如何在浩如烟海的三维模型数据库和网格中快速有效的搜索有用的、同主题的模型，构成了三维模型检索的主要目标。与二维图像相比，三维模型有其独特的性质。首先，三维模型空间中一个简单的物体，即可以用多边形面片、也可以用点、线和体素，还可以由基元物体的几何操作和布尔操作表示。任意的三维曲面不存在类似二维空间上弧长公式的直接参数化方法，因此无法对物体空间定义规则的、标准的类似二维图像的采样方式。这种内在的不规则采样和三维表面存在任意的拓扑关系，使得经典的信号处理技术，无法直接扩展应用到三维。其次，空间维数大小直接影响模型特征对应、参数匹配，分类其构造，优化路径搜索等问题，其复杂度与处理时间随之显著增加。可能的模型退化现象使得常用的几何形状特征，如面积、体积、曲率等难以计算。另一方面，三维模型检索与相机配置、光源设置和场景语义无关，且不包含反射、阴影、遮挡、透射等效果，不需要考虑环境光照条件、相机参数、镜头校准、自遮挡等现象，极大地简化了匹配相似物体的过程，或因为投影到地面变为两个人，或者由于周围场景的迷惑性而凭空消失。综上所述，三维模型特征的选取，需要考虑以下三个方面：第一，特征要能够反映物体的内在基本特性。第二，三维模型在空间中的位置、朝向和大小是任意的，因此，所提取的特征应该与模型的平移、旋转、放缩等刚体变换无关。第三，即便对于退化的三维模型，特征也必须是确定的。221三维模型检索系统基于内容的三维模型目前对模型匹配的研究主要集中在对三维模型的空间几何形状的相似性度量，有少数关于拓扑相似性匹配的研究，基于纹理或材质等属性的相似性研究国内外尚比较少见。基于内容的三维模型检索主要分为两部分：一是离线处理，二是在线处理，如图21所示。离线部分主要是对三维模型数据库中的数据进行特征提取，建立特征描述符和相应的特征数据库，并建立合适的索引结构。在线部分主要是用户在线提交查询意图并进行特征提取、相似性度量和索引、查询结果可视化等。图21基于内容的三维模型检索系统框架以下对三维模型检索系统中涉及到的几个关键技术作简单的介绍：三维模型检索首先从模型数据中自动计算并提取三维模型的特征，如形状空间关系、材质的颜色及纹理等，建立三维模型的多维信息索引，然后在多维特征空间中计算待查询模型与目标模型之间的相似程度，实现对三维模型数据库的浏览和检索畸，。三维模型检索系统就是试图利用反映三维模型视觉特征的内容信息自动建立特征索引，达到检索三维模型的目的。三维模型检索技术通过对视觉特征的相似性匹配来查找用户所要求的三维模型，这更贴近于人们在现实生活中靠直觉印象使用信息的方式。因此，一个完整的模型检索系统包括如下几个方面：(1)三维模型的特征提取由于绝大多数的三维模型是用于可视化，因此表达三维模型的文件中往往只包含模型的几何属性(顶点坐标、法向矢量、拓扑连接等)和外观属性(顶点颜色、纹理等)，很少有适合自动匹配的高级语义特征的描述。如何合理地描述三维模型(即特征提取)成为三维模型检索课题首先要解决的问题，它也是三维模型检索的难点。一个理想的特征描述符必须满足以下几点：易于表达和计算；不占用太多的存储空间；适合进行相似性匹配；具有几何不变性，即对模型的平移、旋转、缩放等具有不变性；具有拓扑不变性，即相同模型有多个拓扑表示时，特征描述符应是稳定；对模型的退化鲁棒；对噪音不敏感；该特征必须具有唯一性，即不同类型的模型对应的特征表示应该不相同。(2)相似性度量检索的目的是找出与所给模型相似的模型集合，因而对提取得到的特征如何进行相似性匹配是检索课题中要解决的第二个问题，选择的度量方法必须适合匹配计算。当前的研究中所采用的相似性匹配方法主要借鉴了基于内容检索的一些相似距离度量。(3)模型分类由于三维模型资源庞大，因此需要建立一个分类数据库以便提高模型查找效率，该分类数据库必须适合用高级语义描述。当然，对这个问题与相似性度量方法的研究有交叉的地方。(4)搜索方法的研究尽管有了分类作基础，在三维模型检索系统中，模型的检索转化成了对高维特征矢量数据库的检索问题，因此，特征数据库中索引结构的设计对提高检索效率非常重要，好的索引机制可以帮助检索系统在时间和存储空间上同时得到提高。面对仍然庞大的数据库，如何快速、有效地查找出相似的模型，在人工智能和数据库领域中仍然是一个值得探讨的问题。(5)查询接口的设计。作为一个成熟的检索系统，应该拥有良好的交互性能，提供给用户方便的查询手段。通常，查询输入可以通过文本与模型相结合的方法进行。对于查询模型的输入主要有两种途径：将已知的模型作为查询输入，通知系统检索出相似的模型，该方法的检索结果比较理想，但是要求用户必须预先拥有某种模型的范例，因此实际使用中不够灵活，有一定的局限性：提供给用户一个绘图接口允许用户绘制所需查询模型的二维视图，由系统根据视图自动生成三维模型。对于普通用户而言，准确地绘制一个拓扑复杂、有洞或有许多分支的模型是比较困难的。实验表明，目前该系统在这方面的性能不是非常理想。显然，查询接口的设计也直接影响了系统的检索性能，因此设计一个理想的查询接口在检索系统中非常重要。(6)检索性能的判断对于三维模型的检索性能的判断，主要从查全、查准、时间、资源消费等几个方面来衡量。目前的研究主要是用查全率和查准率两个参数来对检索性能进行评判。总之，如何提取模型的特征是三维模型检索首先需要解决的关键技术，也是目前研究比较多的一个方面。222三维模型预处理要真正实现基于内容的三维模型检索，非常关键的一点就是要求所提取的三维模型特征描述具有针对平移、旋转、尺度大小以及方位变换的不变性和鲁棒性。目前，实现特征描述不变性的方法主要有三种(1)使用主成分分析印方法对三维模型坐标进行标准化，计算其标准化的坐标框架然后，在此标准化坐标系内提取相应的特征：(2)将所有待比较的三维模型两两之间进行坐标对齐。这种方法由于极为费时而很少被采用；(3)定义并提取本身具有不变特性的特征描述。但实际上，这些特征描述所具有的不变性往往是不全面的，例如，Suzuki等人提出的形状特征只对绕坐标轴90度的变换保持不变性01。提出的反射对称特征描述只具有平移和尺度不变性1。而且，大多数这类特征的计算有时也需要在一个归一化的坐标系内完成。因此，为了进一步提高检索的准确性，往往也需要进行模型坐标标准化。223三维模型特征提取3D模型检索技术的关键是提取特征，在提取特征时有如下一些基本要求：(1)平移不变在平移变换前后，3D模型的特征要保证不变；(2)旋转不变在旋转变换前后，3D模型的特征要保证不变；(3)缩放不变在缩放变换前后，3D模型的特征要保证不变；(4)对噪声具有鲁棒性(噪声包括模型裂缝、插入三角面片、移去三角面片等)。在有噪声的情况下，3D模型的特征要保证相似；(5)对重采样和简化具有鲁棒性，在重采样和简化变换前后，3D模型的特征要保证相似。从计算机图形学发展的初期开始，多边形网格就是通用的三维模型的表示方法。尽管后来出现了更多的描述方法，但由于多边形具有形状简单、便于计算和处理等特点，使得三维模型检索的研究者们更多以多边形网格模型作为研究对象。目前，三维模型特征提取方法主要分为三大类：基于外形的低层方法；基于结构的高层方法；基于视角的方法。在下章中，将详细讨论特征提取方面的研究。224相似性度量模式识别、分类、聚类、检索等常常被应用在计算机视觉、机械工程、分子生物学等领域，特征提取和相似性度量是完成这些任务的关键技术保证。如前所述，好的特征提取方法可以保证得到精确的形状描述符，它是模型检索的关键前提，相似性度量则是使得精确的形状描述得到正确应用的进一步保证。相似性度量的任务就是在多维特征空间中，计算用户的三维模型查询请求与三维模型库中的模型之问的相似性距离，距离越小，说明两个模型的相似性程度越高，反之，距离越大，说明匹配或度量的两个模型之间的相似程度越小，最终系统根据相似性度量的距离大小返回查询结果，从而实现基于内容的模型检索，或者通过构建特定的分类器，得出模型之间的相似程度。因此，选择合适的相似性度量方法是对进行精确匹配的进一步保证。相对于三维检索形状算子的研究而言，相似度比较方法在图像检索领域已有了比较成熟的研究。在基于内容的三维模型检索系统中，针对不同形式的特征空间，有时需要采用不同的适合的度量函数。目前在基于内容的三维模型检索中，主要借鉴了基于内容的二维图像检索中所采用的一些距离度量算法，以下作一个简单的介绍。设U为特征空间，z，少为特征向量，并且有zU，yU度量函数为(x，力，理想的度量函数必须易于计算，符合人类的形状感知，并满足以下特征：正定性(possessiveness)Vx，yU，d(x，y)0对称性Vx，yU，d(x，y)=d(y，x)自反性VxU，d(x，x)=0严格的正定Vx，yU，xy=d(x，y)0三角不等式Vx，y，zU，d(x，y)ad(x，z)+bd(z，y)+c常用于三维模型检索领域的主要有Euclidean距离、Manhattan距离、马氏距离以及Hausdorff距离等。设三维模型的特征空间为U=Rn，任意两个三维模型的特征向量X，Y，分别表示为：X=x1，x2，xn，Y =y1，y2，yn，上述常用的经典的距离公式分别为：(1)欧几里德距离该距离适用于任何维数的特征空间，而且计算简单，在很多文献中都被使用。但是这个距离的计算有一个前提，它假设了在同一特征空间的两个特征分量xi，xj彼此是独立的，这就可能导致错误的或者不够准确的匹配。为了弥补传统的欧几里德距离的缺陷，Ankerst提出了一种经过改进的度量方法，用一个相似矩阵A表示特征空间各个分量的相关性，如下述公式所示： (2)Manhattan距离(3)Hausdorff距离Hausdorff距离通常用来比较不同大小的两个点集之间的相似性，其定义为：其中，表示两个特征点集中任意两点之间的距离，如Euclidean距离等，max()为取最大值函数，min()为取最小值函数。(4)马氏距离(Mahalanobis Distance)马氏距离首先根据已有的特征向量集合估计出协方差矩阵，然后定义如下的对称距离：其中，A是根据已有的特征矢量集估计出来的NN的相似矩阵。225相关反馈相关反馈是检索研究中的热点之一。由于没有一种形状特征能够完整地描述模型的特性，也没有一种相似度量可以很好地模拟人的视觉感知，已有的分类器只能在给定样本的情况下给出最佳分类结果,因此，如何让系统在各种检索条件下都能够给出较好的结果，是一般的检索系统需要考虑的问题。相关反馈利用机器学习理论，在系统与用户的交互过程中，主动学习用户的判断，使系统逐步走向稳定与准确。Chen等人用主动学习(Active Learning)与隐藏标注(Hidden Annotations)相结合的技术，由用户对系统选择的具有最大知识获取的模型进行标注。经过一段时间的学习，系统展现了良好的可扩展性。文献(18)础允许用户对检索结果做出评价，用类似支持向量的思想，将问题归结为一个具有线性约束的最小二次优化，缩短用户指定为相关的模型之间的距离，同时增加不相关模型的空间距离。与相似度比较类似，相关反馈也不是三维模型检索领域所独有的。在图像检索中，它被用于缩小高层语义与底层特征之间的差异，以及弥补人类视觉感知的主观性。（备注19）226界面设计由于三维模型中所包含的内容信息比图像等二维媒体更加丰富，因此，基于内容的三维模型检索系统一般具有多种检索方式（备注20），主要有：(1)直接提供三维模型实例作为检索请求，该模型可以是用户上载至检索服务器的新模型文件，也可以是某次检索结果集中的任一幅三维模型使用文件上载方式时，用户只需直接提交三维模型的文件名或URL地址：而使用服务器上的三维模型实例检索时，用户可以通过缩略图浏览的方式在界面上交互选取。(2)使用用户交互绘制的二维形状草图，如Min等人设计了一个基于用户交互的二维草图绘制界面，由用户绘制n个不同角度的二维草图作为查询请求在检索时则使用三维模型在不同视角下的二维投影分别进行相似性匹配。(3)使用用户交互绘制的三维草图，如Igarashi等人设计的三维草图绘制工具Teddy（备注21）。但相对于二维草图绘制而言，三维草图的绘制难度较大，限制较多，而且只能绘制相对简单的三维模型。(4)基于文本关键字的检索界面。其中，文本关键字可分为两类：一类是不具有语义属性的文本，如模型文件名称等附加信息：另一类是语义关键字，可以通过直接输入语义文本或者目录浏览的方式提交检索请求。此外，检索界面还负责将检索结果以可视化的方式显示给用户，以进行浏览或下一步的检索过程。一些三维检索系统中还引入了用户相关反馈的机制，为用户提供一个交互式的评价界面，作为引入用户主观评价的手段，以提高检索精度，并实现个性化的、结合用户主观性认知的检索。如Elad等人（备注18）提出基于学习的检索机制以自动适应不同用户的检索要求和偏好，在检索结果显示时提供了一个标记“相关和“不相关”，两种评价的用户反馈界面。而Zhang等人（备注22）。则进一步对用户评价界面加以细化，提供了调节“相关和“不相关”程度的反馈界面。227已有系统在基于内容的三维模型检索领域，目前己经实现并发布了一些进行理论和算法研究的原型系统以及架构于web平台上的搜索引擎等。其中，加拿大国家研究院的Paquet等人开发的三维模型检索系统Nefertiti是第一个通用的三维模型检索系统，所提取的特征主要包括形状和颜色两种。目前，比较典型的通用三维模型检索系统和搜索引擎主要有：(1)美国普林斯顿大学形状检索与分析实验室开发的三维模型搜索引擎，提供了二维草图和三维草图的绘制界面，并具有规模最大的三维模型数据库，其中包括31000个通用的三维模型以及多个专业的三维模型子库。(如图22所示)http：shapecsprincetonedusearchhtml图22普林斯顿大学的三维模型系统(2)美国卡耐基梅隆大学AMP(Advanced Multimedia Processing)实验室开发的三维模型检索系统，同时结合了底层形状特征和语义特征进行检索，并提供了用户相关反馈的功能。http：ampececmueduprojects3DmodelRetrieval(3)德国莱比锡大学CGIP(Computer Graphics and Image Processing)实验室的Saupe和Vranic等人开发的基于VRML模型库的在线三维模型检索系统CCCC(Content based C1assification of 3D models by Capturing spatial Characteristics)，允许用户任意选择三维坐标轴X，Y或Z进行模型坐标的标准化，这样能使检索结果更符合用户的要求。该系统基于Web平台设计，用户界面友好。(如图23所示)httD：merkur01infunikonstanzdeCCCC图23莱比锡大学的三维模型检索系统(4)IBM日本东京研究院的“三维web环境研究项目中的三维几何形状检索和分析系统，该系统的开发目的是对三维模型库进行知识管理。http：wwwtrlibmcomprojects3dwebSimSearchehtm(5)希腊ITI学院信息处理实验室开发的基于VRML模型数据库的三维模型检索系统，除了可以在三维模型库中进行检索外，还提供了对三维模型进行两两比较的用户界面和功能。http：3dsearchitigrdefaultphp?page=3dsearch(6)荷兰Utrecht大学的GIVE(Geometry Imagined Virtual Environment)实验室研制开发的三维形状搜索引擎，主要基于高斯曲率等形状特征实现基于模型形状的检索。http：wwwcsuunlcentersgiveimaging3Drecog3Dmatchinghtml(7)日本多媒体教育学院的Suzuki等人开发的基于web的多边形模型检索系统ogden IV，该系统同时使用模型的形状和颜色特征对VRML模型数据库实现检索，以建立三维的网络教学环境。http：wwwnimeacjpmotofumiOgden(8)美国布朗大学的LEMS(Laboratory for Engineering ManMachine System)实验室开发的三维模型检索系统，以二维图像为输入方式，在三维模型库中检索出相似的三维物体模型。http：www1emsbrowneduvisionresearchAreas3DRecogoverviewhtml(9)德国波恩大学Klein和Novotni等人开发的数字图书馆系统RoDA，该系统不对模型进行特征提取，而是通过计算不同模型之间的体积测定误差(V01umetric Error)以及补偿轮廓(Offset Hull)进行检索。http：www1emsbrowneduvisionresearchAreas3DRecogoverviewhtml(10)台湾大学通讯与多媒体实验室研制的三维模型检索系统，该系统使用MPEG一7标准的三维形状描述符和多视图描述符对模型特征进行描述，基于web平台进行三维模型检索。(如图24所示)http：3dcsientuedutwdynamic此外，还有一些用于专业领域的检索系统。如德国慕尼黑大学Ankerst等人研制的三维蛋白质分子模型检索系统http：wwwdbsinformatikunimuenchendeForschungSimilarityDemosprotein以及苏格兰Heriotwatt大学开发的于web的CAD模型搜索引擎ShapeSifter等。http：wwwshapesearchnetecmindexhtml图24中国台湾大学的三维模型检索系统23本章小结三维模型检索被广泛应用于数字化图书馆、数字机和处理、分子生物学、机械工程、医学图像和图形编辑等各个领域，以构建面向三维模型的专业化搜索引擎为目标，有三维模型的获取、特征分析、查询处理和匹配以及用户界面四个部分组成。由于种种原因，这个领域直到近两年才引起足够的重视，并得到了飞速发展。本章就是对三维模型检索研究领域的历史和现状作一个的概述。通过概述，指出了目前存在的主要问题以及进一步研究的重点和必要性。在模型数据库中，强壮的模型特征表达和识别是最根本的问题，此外，我们还需要很好的相似性距离度量方法，接下来的章节就是对这两个问题进行深入的研究。第三章三维模型特征提取的研究31三维模型预处理311模型规范化处理对三维模型规范化的目的是使所有的模型满足(1)平移不变性：(2)旋转不变性：(3)缩放不变性。也就是对于任何三维模型不管进行了什么样的平移变换，旋转变换，缩放变换，只要对其进行规范化预处理后，那么最终的大小，原点坐标，方向都一样，因此不影响特征的提取。本文使用了主成分分析法PCA(Principle Component Analysis)对三维模型进行规范化处理。(1)平移不变为了保证平移不变，首先求出三维模型的重心，将三维模型的重心作为三维模型的新坐标原点，将三维模型平移到新的坐标原点。计算三维模型重心的公式如下。这里w为三角形的面积，P为点的集合，求出c是三维模型的重心，将三维模型的坐标原点移动到c点，形成的点集合如下。 (2)旋转不变为了保证旋转不变性，首先使用公式计算三维模型的相关矩阵M，M是个3木3的矩阵。矩阵M是实对称矩阵，因此特征根是3个不同的正实数。求出特征根，以降序排列3个特征根。然后求出3个特征根对应的特征向量，将每个特征向量变为单位向量，最后3个特征向量组成旋转矩阵R，R同样是3牢3的矩阵。使用旋转矩阵R变换三维模型，计算出新的点集 (3)缩放变换为了统一三维模型的大小，保证缩放不变，需要计算大小变换因子来变换三维模型。其中，最后得到了平移变换响亮c、旋转变换矩阵R、大小变换因子s。将这些变换应用到原三维模型的顶点集合P完成规范化预处理。312三维模型的存储方法(1)三维文件格式介绍A3DS数据结构：3DS文件由许多块组成，每个块首先描述其信息类别，即块是如何组成的。块的信息类别用D来标识，块还包含了下一块的相对位置信息。3DS二进制文件中的数据是按低位在前、高位在后的方式组织的。如，4A 5C组成的整型数，表明5C是高位字节，4A是低位字节：对于长整型数。如：4A 5C 3B 8F表明5C 4A是高位字节，3B 8F是低位字节。下面描述块的具体定义。块的前面两项信息分别是：块的ID和块的长度(也即下一块相对于该块的字节偏移量)，块的ID是一个整型数，而块的长度是一个长整型数。每个块实际上是一个层次结构，不同类型的块，其层次结构也不相同。3DS文件有一个基本块，其ID是4D4D，每一个3DS文件开头都是有这样一个块构成的。BCTS和TD0文件格式CTS和TDO都是我所特有的三维模型文件格式。这些数据是有二维CT图像经过三维重构而来的，之所以要对这些格式支持，是因为三维检索在医学上有很大的应用前景。TDO数据结构：关于：IcTDO文件读写的信息。文件后缀TDO的是”ThreeDimensional 0bject”的简写形式。Struct tagTDOFILEHEADER文件标志字符串，必须是，”3D0bject”，不区分大小写。Char m _chSymbol 9：文件版本号，当前为1。除非对文件格式有较大修改，否则必须为1。UINTm_nVersion：文件头的大小，以字节(Byte)为单位。UINT m_nFi1eHeaderSize：本数据文件的状态：0=原始：1=己进行法兰克福校正；2=己进行分区切分。BYTE m_nState；点数据层数：一1=非分层数据(例如从DXF文件转换的数据)，在文件头后有数据点序列；(=0)=分层数据的层数，在文件头后有若干层数据点序列。Int m_nPointLayerNum；三角形数据层数：一1=非分层数据(例如从DXF文件转换的数据)，在数据点序列后有三角形数据；(=O)=分层数据的层数，在数据点序列后有若干层三角形数据。一般情况下，对于分层数据应有m_nTriangleLayerNum=(m nPointLayerNum-1)的关系。Int m_nTriangleLayerNum：此数据的最大最小坐标：double0=x；double1=y；double2=z。Double m_szMax 3：Double m_szMin 3：保留字。Int m_nReVersedl：Int m_nReversed2：doublem_dReVersedl：doublem_dReVersed2：；CTS数据CTS存储的是由空间点组成的等值线据。文件由两部分组成：第一部分是文件头信息：Struct CTSFILEHEADERUINT nLayerTotal 内层和外层层数的最大值UINT nDataHeight 图象的数据高度UINT nDataWidth 图象的数据宽度double fFactorX 数据在X方向上的比例因子double fFactorY 数据在Y方向上的比例因子double fFactorZ 数据在Z方向上的比例因子第二部分是文件的数据信息其内容如下：层号第n层颅骨等值线个数，(INT型)第m条内等值线点数，(INT型)空间点数据(X，Y，Z)(double型)第n层皮肤等值线个数，第m条内等值线点数，(UINT型)空间点数据(X，Y，Z)(double型)(2)多文件格式的统一存储由于要使不同格式的三维模型能够进行统一的检索，所以我们在模型输入后统一使用C3Dobject类来对其进行操作。此外，由于三维模型可能存在缺陷或噪音，而无法满足算法特征提取的要求时，我们也是通过对C3D0bject类进行标准化来实现的。C3DObject类代表了三维物体模型。计算机图形学中通常采用三角面片的网格来表示一个三维物体，所以该类中一个重要的数据就是三角面片的集合。在对三维模型的编辑过程中，对构成模型的三角面片信息进行遍历和搜索是一个常用的操作。在给出模型表示的数据结构之前，先给出和三角形面片组成的网格有关的几个定义。点的索引：一个点的索引是指该点在顶点数组中的索引，它是一个整数。它唯一确定了一个空间点。点的相关三角形：如果该点为某个空间三角形的一个顶点，我们就说该三角形是该点的相关三角形。点的相关三角形表：是指和该点相关所有的三角形构成的集合。点的度：是指和该点相关的三角形的个数。三角形的法向量：空间三角形的法向量定义为从空间原点出发和该三角形所在平面垂直并指向该平面的单位向量。点的法向量：空间中一点的法向量定义为和该点相关的所有三角形的法向量的平均法向量。如图32所示，在空间网格中，顶点A相关三角形有a，b，c，d，e，f它的度为6。顶点A的法向量就为三角形a，b，c，d，e，f六个三角形的法向量的平均法向量。图32顶点和其相关的三角形示意图从上面的例子可以看出来，在三角形网格中绝大多数顶点的度都是大于1的。如果每个三角形用其三个顶点来表示，每个顶点用三个坐标来表示，那么上图中A顶点的坐标就要被重复保存6次。如果用这种方法来表示含有上万个三角面片的空间网格，那么势必需要大量的存储空间。显然这种把空间一个点重复多次保存是完全没有必要的。系统中采用索引的方式来表示三维空间网格模型。索引方法表示空间三角面片网格的思想如下：把所有构成空间三角面片网格的顶点形成一个集合，并依次对所有顶点从0开始编号，依次类推。这样网格上的每一个顶点都有一个唯一的编号，该编号也唯一确定了网格中的一个顶点，这个编号称为索引号。空间三角面片的表示用构成该三角形的三个顶点的编号来表示，即用三个整数来表示一个空间三角形，这三个整数为构成该空间三角形三个顶点的索引号。每一个空间顶点的所有相关三角形构成其相关三角形表，它和该顶点一一对应。如图33所示。图33三维网格索引法表示示意图采用索引的方式来表示空间网格不仅可以节省大量存储空间，而且对与模型的编辑和修改也带来了很大的方便：这种存储方式每个顶点只需要保存一次，当用户编辑该顶点的时候，如平移，那么只需要修改一次顶点信息，其索引值不变，所以和该顶点相关的三角形数据不发生任何变化，这也保持了数据的完整性。这种存储方式对于查找给定顶点的所有相关三角形是很方便的。如果用户删除了某个顶点，则可以很方便的找到所有和该顶点相关的三角形，然后全部删除这些相关的三角形，也便于计算各个顶点的法向量等。同时，在三维网格简化的时候，需要统计顶点的相关三角形，这种存储方式也给三维网格简化带来了便利。32三维模型特征提取技术的研究对一个三维模型进行参数化是一个很复杂的问题，同时由于三维表面有任意的拓扑，使得一些在二维图像被使用的方法(如傅里叶变换)无法直接应用在三维领域。很多模型虽然满足了视觉效果，但是大多数是退化的、不完整的。对这些模型进行有意义的几何特征和形状信号的计算是很困难的，因此寻找出有意义的特征成了研究人员首先考虑的问题。可以说，对于基于内容的3D模型检索系统，最根本的问题是选取恰当的特征来区别不同的形状，以用来有效的索引相似的文件数据。（备注1）3D模型检索方法可大致的分为3类：基于外形的低层方法；基于结构的高层方法：基于视角的方法。321基于外形的方法基于外形的方法尝试通过几何和拓扑的属性描述3D模型的形状，外形可以是由单独向量组成的一些外形参数的固定数值或系列外形参数的分布范围：基于结构的高层方法尝试把3D模型分解成一系列关键部分，并提炼出这些部分的几何关系；基于视角的方法通过系列从不同角度的二维射影来得出三维模型的外观。在3D模型表述系统中，基于外形的下层方法描述通常3D模型的几何属性，空间属性，形状分布范围。两个模型的相似处可通过比较外形来测量。Zhang和Chen例提出了通过网格描述，来有效计算面积、体积、对称轴傅立叶变幻系数的方法。Paquet等人乜钔使用对称轴来描述三维物体的对称性基于套锁来描述形状信心的细微细节，并用小波变换来描述不透明度分布。这种方法，需要摆好标准化的姿势用于旋转。三维傅立叶变换特征是利用傅立叶变换公式将三维模型分解成不同的频率表示，然后利用其中一些频率系数形成的三维模型特征。首先对三维模型进行规范化和体素化处理，然后对体素单元进行离散的傅立叶变换。设V是三维模型的体素，进行离散的傅立叶变换，把V变换到频域空间，计算特征向量之间的绝对值距离和欧氏距离作为相似度，检索时可以使用不同分辨率的特征向量检索，即可以选择三组特征向量中任何一组进行检索。vranic的测试表明，傅立叶变换检索技术具有较好检索效率，但是计算速度较慢。三维小波特征小波变换同样也可以用于描述三维模型的特征，Paquet等人在检索中使用了小波变换。文中使用了具有二阶消失矩的DAU4小波。这种小波的变换矩阵w如公式所示，将W作用到模型的三个轴向就得到小波系数。先对三维模型进行PCA和体素化处理，然后再在三个轴向上进行小波变换，得到小波系数。一种改进的，不需要摆好姿势的基于球形调和的形状描述法被Funkhouser等人(备注28,27)提出。首先，3D模型通过与其相交的不同半径的同心圆来分解成一系列圆形函数的聚集。每个圆形函数被分解为一系列不同频率的谐波。在每个半径圆上，每个频率部分的范数和组成了形状的表述。这种表述是旋转常量，原因是，旋转一个圆状函数不改变每个频率部分的能量。Novotni和Klein拉引对3D模型运用查涅克矩。无疑，这是基于圆形谐波表述法的延伸。三维查涅克矩是一个通过半径和频率的二维直方图索引。三维查涅克矩的好处在于它旋转常量并且对几何的、拓扑的外来物不敏感。球面调和分析又称单位球面上的二维傅立叶变换。它的正交基函数Z。(p，矽)(球面调和函数)定义如下：其中是规一化常数。是度为l，次为m的联合拉格朗日多项式球面调和函数源自球面上的拉普拉斯方程，它们构成了球面上连续函数空间的一组完备单位正交基。所有度为，的球面调和函数组成球面上一个2L+1维大小的旋转不变子空问，任意定义在球面上的连续信号在子空间上的投影与信号的旋转操作无关。将三维模型与一系列同心球求交，其中球心与物体中心重合，球面调和分析便能够直接应用于在不同半径下计算得到的球面函数网。但是，由于球面函数之间相互独立，旋转某些半径分量下的球面函数，并不影响计算结果，而此时，物体的外在形状却发生改变。(如图34所示)图34度为0，1，2，3的球面图调和函数三维查涅克矩描述符则能够很好地克服球面函数独立性所带来的问题。定义一组三维空间正交基函数，称为三维ZerIlike函数：其中，是球面调和函数，是径向函数，所有径向下标为n，度为l的Zemike函数张成三维空间上一个2l+1维大小的旋转不变子空间。小波变换是傅立叶变换一个自然的扩展，它具有良好的时间空间分辨率，适合层次化的表示与比较。将小波变换应用到三维检索中最主要的困难仍然在于三维模型的表示。当然，高维小波的构造本身便是一个难点，它们通常不具备一维小波那样良好的性质。在简单的应用中，可以选用光滑的、具有有限消失矩的一维小波，例如，DAU4小波与Haar小波等，分别沿三个坐标轴进行变换。Yu等人(备注29)表面穿透对应图，使得光线从球中心穿过表面的数值是可计算的。这种对应图的傅立叶变换已被用于检索或相似性比较。Shih等人（备注36）提出一种新的，被称为网格D2的表述法，来减轻上述问题。在GD2表述法中，3D模型首先分解为三维像素格，相比于随机点，这种随机采样操作只在多边形表面的像素格内。这种轮廓范围表述法（备注37）被用于3D模型检索的MPEG7标准。SSD描述了三维表面的全部点曲率的直方图。SSD的优点是不用事先对准三维物体就便可以比较两个3D模型，并且对于成棋盘形布置得三维多边形模型，是很稳定的。322基于结构的特征提取方法：基于形状的方法之考虑三维模型的几何、拓扑属性。而高层基于结构的方法，描述的是模型各部分问的关系。Hilaga等人（备注38）用多分解Reeb图来描述三维模型的概略结构。(如图35所示) 图35三维模型和对应的Reeb图精确地说，Reeb图被定义为图的商数空间和商数函数。Hilaga等人所用的Reeb图是基于完整的测疑距离所定义的商函数，利用测地距离由i维物体的形状计算出多分辨率Reeb图，然后给出了拓扑图相似度的定义，并依此进行模型相似度的计算。多分辨率Reeb图的基本思想是在物体细节的各个层次上建立一系列Reeb图。为在某一层次上构造Reeb图，物体由