毕业设计(论文)-基于有意义分割理论的三维模型检索算法研究.doc

独创性声明学位论文题目： 基于有意义分割理论的三维模型检索算法研究 本人提交的学位论文是在导师指导下进行的研究工作及取得的研究成果。论文中引用他人已经发表或出版过的研究成果，文中已加了特别标注。对本研究及学位论文撰写曾做出贡献的老师、朋友、同仁在文中作了明确说明并表示衷心感谢。学位论文作者： 签字日期： 年 月 日学位论文版权使用授权书本学位论文作者完全了解西南大学有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权西南大学研究生院（筹）可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。（保密的学位论文在解密后适用本授权书，本论文：不保密，保密期限至 年 月止） 。学位论文作者签名： 导师签名：签字日期： 年 月 日 签字日期： 年 月 日目 录摘 要IABSTRACTII第1章 绪论11.1 研究背景及意义11.2 国内外研究现状21.3 主要研究工作51.4 论文新意51.5 论文结构6第2章 三维模型检索相关理论72.1 三维模型的表示72.2 三维模型检索系统72.3 三维模型标准化预处理92.3.1 平移变换92.3.2 旋转变换102.3.3 缩放变换102.4 三维模型相似性度量112.4.1 几何距离度量方法122.4.2 EMD距离度量方法122.5形状分布算法132.6 三维模型分割理论152.6.1 三维网格分割定义152.6.2 三维网格分割的分类152.6.3 有意义分割162.7 典型的三维网格分割算法172.7.1 基于分水岭的分割算法172.7.2 基于区域增长的分割算法182.7.3 基于聚类的分割算法192.8 本章小结20第3章 基于有意义分割理论的三维模型检索算法213.1 算法框架213.2 模型分割223.2.1改进的分水岭算法233.2.2扩展多阶邻域曲率计算243.3 特征提取253.3.1 全局特征提取263.3.2 拓扑树特征提取273.4 相似度计算293.4.1 全局特征相似度计算293.4.2 拓扑树的相似度计算303.4.3 综合相似度计算313.5 总体算法描述323.6 本章小结32第4章 实验344.1 实验目的344.2 实验环境344.3 实验数据344.4 算法评价标准354.5 实验一 改进的三维网格模型分割算法354.6 实验二 基于有意义分割的三维模型检索算法374.6.1 检索准确性对比374.6.2 检索时间比较404.7 实验结论41第5章 总结与展望425.1 总结425.2 未来工作展望42参考文献43致 谢47攻读硕士学位期间公开发表的论文48ii西南大学硕士学位论文摘要基于有意义分割理论的三维模型检索算法研究计算机软件与理论专业 硕士研究生 甘圆超指导教师 唐 雁 教授摘 要近年来，三维模型的应用领域日渐广泛。随着三维建模技术和数字扫描技术的发展、计算机网络的扩张，网络中可共享和复用的三维模型数量急剧增长。在现有的条件下，如何对目前已有的三维模型进行有效的管理和检索，如何提高三维模型资源的共享和复用，成为亟待解决的问题。由此，基于内容的三维模型检索技术（CBMR，Content-Based Model Retrieval）应运而生，并逐渐成为计算机图形学领域的研究热点。目前，基于内容的三维模型检索技术的研究重点主要集中在三维模型的特征提取算法上。现有的特征提取算法可以分为四类：（1）基于统计特征的特征提取算法；（2）基于几何变换的特征提取算法；（3）基于二维图像映射的特征提取算法；（4）基于拓扑结构的特征提取算法。这些算法在描述和提取模型形状特征时，主要考虑的是模型的整体形状和拓扑结构，提取的是模型在整体形状方面的特征，在很大程度上忽略了模型的某些显著的局部细节特征，从而导致对复杂的模型以及外部轮廓相似而细节不同的模型的识别能力不足，进而影响了三维模型的检索精度的提高。针对目前已有的三维模型检索算法对模型局部细节描述不足的问题，在研究近年来心理学、心理物理学理论中提出的最小值法则和人类的视觉认知特点的基础上，提出了一种基于有意义分割理论的多特征结合综合计算模型相似度的三维模型检索方法。算法首先利用本文提出的改进的分水岭算法对三维模型进行分割，得到有意义的模型部件集合及其之间的邻接关系，然后将其用于描述模型的整体形状分布特征（全局特征）和局部细节特征（拓扑树特征），再分别利用基于EMD距离的相似度计算方法和基于拓扑树匹配的相似度计算方法来衡量不同模型间的相似程度，最后采用相似度加权求和的方式得到模型间总的相似度。完成模型的整体相似度量到局部相似性匹配，实现检索过程。在Princeton大学提供的PSB模型库上对本文提出的检索算法进行了验证。实验结果表明，本文提出的算法受模型噪音和连通性影响小，提高了检索精度，检索所需时间也在合理的范围内，获得了较理想的检索结果。关键词：有意义分割 三维模型检索 EMD 拓扑树 形状分布算法III西南大学硕士学位论文ABSTRACT3D Model Retrieval Method Based on Meaningful SegmentationMajor: Computer Software TheoryResearch Direction: Web Application Technologies Supervisor: Prof. Yan TangAuthor: Yuanchao Gan (112009321001987)AbstractRecently, 3D model has wide application in many fields. With the development of 3D modeling technology, digital scanning technology and computer network technology, there is a rapid growth in the number of sharing and reusable 3D models. So, how to manage and retrieve effectively the existing 3D models and how to improve the sharing and reuse of the 3D model resource need to be solved immediately. Based on it, the Content-Based 3D Model Retrieval (CBMR) generated, which gradually becomes a hot research field in computer graphics field.At present, the research priorities of CBMR focus mainly on its feature extraction algorithm. Existing feature extraction algorithms can be divided into four categories: (1) feature extraction algorithm based on the statistical characteristics, (2) feature extraction algorithm based on geometric transformation, (3) feature extraction algorithm based on two-dimensional (2D) image maps, (4) feature extraction algorithm based on topology structure. In describing and extracting the model shape characteristics, these algorithms mainly consider the overall shape and topology structure. They can effectively extract the overall shape features, but ignore some significant local minutiae of the models. So for the complex models or some models with similar external contour but different details, these algorithms lack of recognition and will affect the retrieval accuracy of the 3D models.In view of the problem that current 3D model retrieval algorithms describe the local details of the models inadequately, based on the minimum rules and human visual perception characteristics proposed by the psychology and psychophysics theory, this paper proposes a new 3D model retrieval method based on meaningful segmentation theory and the multi-features combined to compute model similarity comprehensively. The algorithm can be described in follows: Firstly, we use the improved watershed algorithm proposed by this paper to do the 3D model segmentation and get the collection of meaningful model components and their adjacent relationship. Secondly, describe the overall shape distribution features of the model called global features and local details features called topology tree features. Thirdly, calculate the degree of similarity between different models by the similarity calculation method based on EMD distance and the similarity calculation method based on topology tree matching. Finally, calculate the total similarity degree between the models by the way of similar degrees of weighted summation. So, we can complete the process from the whole model similarity degree measures to local similarity match, and then realize the retrieval of 3D model.Finally, we conduct experiments in the PSB model library of Princeton University to implement the retrieval algorithms proposed in this paper. The experimental results show the proposed algorithm is lowly affected by the model noise and connectivity. Moreover, the algorithm has improved the retrieval precision and the required retrieval time is reasonable. In a word, the algorithm can get better retrieval results.Key words: Meaningful segmentation; 3D model retrieval; EMD; Topology tree; Shape distribution algorithm西南大学硕士学位论文第1章 绪论第1章 绪论1.1 研究背景及意义人类生活在一个三维世界里，人类视觉感知的对象是三维立体的。相对于二维图像，三维几何模型（简称三维模型）及其组成的三维场景具有比二维图像更多更丰富的视觉感知细节，因而更适用于人类的视觉感知和思维模式1。随着三维数字扫描仪的出现以及计算机软硬件技术的发展，三维模型作为一种新的媒体形式，逐渐进入人们的生产和生活领域并得到广泛应用，其所涉及的领域包括：工业产品设计、文物保护、虚拟现实、影视动画、3D网络游戏、医学、分子生物学等23。三维模型在各领域的广泛应用，使得三维模型数据以指数的形式猛增，同时也标志着以三维几何模型为表现形式的新的数字几何媒体时代已经来临。三维几何模型在各领域的广泛应用，使得越来越多的三维模型数据库应运而生，如工业CAD模型数据库，三维游戏模型数据库，蛋白质分子模型数据库等等4。三维模型数据已得到极大的扩展和膨胀，与此同时，对现有的三维模型进行有效的管理和检索逐渐引起人们的关注，并发展成为一项新的研究课题。在三维模型数据急剧增长的同时，人们使用模型数据的方式也在发生转变。在以往的应用中，人们主要是考虑如何利用三维建模软件和数字扫描工具构建新的三维模型，现在则考虑的是如何对数据库中已有的三维模型实现共享和复用。在传统的三维建模方法中，进行高逼真度的三维建模既费时又费力，如果能对现有的三维模型数据复用，将极大的节省开支，且能够提高产品设计和生产效率。幸运的是，计算机网络的扩张增强了人们获取分散存储的三维模型的能力，也为有效传播高质量模型创造了条件，从而使得三维模型数据的共享和复用成为可能。要实现三维模型的共享和复用，首先需要从网络数据库中数量众多的三维模型中查找出满足用户要求的三维模型，这个查找过程即为三维模型检索的过程。所谓三维模型检索，是指在一个给定的三维模型数据库中，检索出与某一特定模型在一定相似度范围内一致的所有其它模型的过程。三维模型检索旨在为人们提供一种更为方便、快捷的模型获取方式，有助于大量三维数据资源的组织和重用。三维模型检索已成为继声音、图像、视频等多媒体检索领域的又一研究热点。三维模型检索研究也能够推动其它研究领域，如人工智能、计算机视觉以及模型识别等领域的进展，因而具有非常重要的研究价值和应用意义。 快速而有效的三维模型特征提取算法是目前三维模型检索研究的重点。根据所提取特征的对象的不同，三维模型检索可以分为基于文本的检索和基于内容的检索5。基于文本的检索，属于基于关键字匹配的检索，主要通过计算与模型相关的文本信息的相似性来度量模型间的相似性进而实现检索。由于这种检索方式需要人工地为每一个三维模型添加文本注释信息，不仅费时费力，而且所添加的注释信息具有很大的主观性和片面性，可靠性不高，所以这种方式存在着较大的缺陷，实用性不高6。基于内容的三维模型检索主要提取模型的形状特征（如几何形状、拓扑结构等）并进行基于形状特征的相似性匹配从而实现检索过程，人为干预较少，也更符合人们在现实生活中依靠直觉印象使用信息的方式7，具有更高的可靠性和更好的检索效果，因此是目前三维模型检索的研究重点。目前对三维模型检索的研究主要集中在基于内容的三维模型检索技术上。本文后续章节所说的三维模型检索均指的是基于内容的三维模型检索。1.2 国内外研究现状1997-1998年，Paquet等8最早对基于内容的三维模型检索技术进行研究。自1999年以后，许多国家的研究人员开始重视并相继投身到这个研究领域。他们提出了很多典型的三维模型检索技术，并开发了一些可用的在线三维模型检索实验系统。在这些检索系统中，影响较大的有美国Princeton大学的检索系统（http:/www.shape.cs.princeton.edu/search.html）、德国Konstanz大学的检索系统（在基于内容的三维模型检索算法中，对模型形状特征的提取是检索算法的关键。这是因为：一方面，检索算法提取的特征直接影响检索结果的准确性。理想的形状特征应能科学地标识模型，具有一定的唯一性，从而保证相似的模型具有相似的特征，不相似的模型其特征差别很大，也就是如果提取的特征的区分能力越强，检索精度就越高，检索效果也越好；另一方面，特征提取算法直接影响检索的效率，所以特征提取过程应易于计算，提取的特征应易于进行相似性度量，从而获得较好的检索效率。目前对三维模型检索算法的研究主要集中在特征提取方面。根据所提取的特征的不同，近年来比较有代表性的三维模型特征提取算法可以分为4类：（1）基于统计特征的特征提取算法；（2）基于几何变换的特征提取算法；（3）基于拓扑结构特征的特征提取算法；（4）基于二维图像比较的特征提取算法。基于统计特征的特征提取算法是通过统计能够在某一方面标识模型、反映模型形状的特征，得到大量的统计数据后，利用概率分布的思想来描述模型的形状特征。这类算法主要是从模型整体形状上进行比较，忽略细节上的不同，比较接近人的视觉识别，典型的方法有：Ankerst等10采用不同的方式对三维模型进行切分，得到很多的切分单元后统计每个切分单元中点的个数占模型顶点总数的百分比，构成直方图，将直方图作为三维模型的形状特征，该方法非常简单，但模型检索精度低，生成的特征向量维数较大，检索速度慢。Osada等11提出的形状分布算法，首先生成足够多的采样顶点，然后统计任意采样点之间的欧氏距离（D2 Distance），再将最大距离切分成N个距离单元，通过统计落入到每个距离单元的距离个数，形成距离分布直方图，利用距离直方图来表示模型的形状特征，算法能够很好的满足缩放不变、旋转不变以及平移不变和对称不变，并且对噪声、重采样和简化都有良好的鲁棒性，适合对简单模型进行检索和粗分类。Suzuki等12提出的点密度方法，将外包三维模型的立方体切分成个单元，将所有单元分类，分类的方法是围绕轴旋转后，能彼此重叠在一起的单元分为一类，N不同，类的个数也不同，再计算每类单元中三维模型的顶点数，然后除以模型顶点数，构成模型的特征向量。该方法大大减少了特征向量的维数，且计算简单，计算量小，检索效果比较好。与点密度法类似，提出了一种加权点集法13，该方法在对三维模型进行归一化预处理后，将模型的外包围立方体切分成个单元，然后分别采用三种不同的方法提取每个非空单元的突出点，将所有突出点的加权点集作为模型的特征描述。基于几何变换的特征提取算法主要是将三维模型从空域空间变换到频域空间，在频域空间提取模型的几何特征，典型的方法有：Vranic 等14使用傅里叶变换首先对三维模型进行规范化和体素化预处理，然后对体单元进行离散的傅里叶变换。利用傅里叶变换公式将三维模型分解成不同的频率表示 ,最后取一定数量的频率系数作为三维模型的特征。测试表明，傅里叶变换检索技术优于基于射线、点密度和基于约束线的检索技术，但是计算速度较慢。Kazhdan等15提出的球面调和变换算法，首先对模型进行体素化处理，将模型分解成个体素单元，对于位于三维模型表面上的体素单元赋值为1，其它单元赋值为0。然后对采样值进行球面调和分析，将得到的球面调和系数作为模型的特征向量。Paquet等16在检索技术中使用了小波变换来描述三维模型的特征。基于拓扑结构特征的三维模型检索算法通过比较三维模型的拓扑结构来度量三维模型的相似性，其优点是对于具有不同形状但属于同一种类的物体，由于其拓扑结构相同，所以被认为是相似的。对于这类算法，典型的方法有：Hilaga等17提出的Reeb图拓扑比较方法。该方法首先构造多分辨率Reeb图，然后比较Reeb图。除Reeb图外，中轴线方法18是描述三维模型拓扑结构的另一种方法，该方法主要从三维模型骨架的角度来提取三维模型的拓扑结构。基于二维图像特征的特征提取算法通过比较三维模型在各个方向的投影图像的相似性来计算三维模型的相似性。这类方法首先将三维模型投影到二维平面上，得到模型在各方向上的二维图像，再从二维图像中提取特征进行相似性匹配，其典型的方法有：Min的基于二维轮廓图的比较19算法，Chen的基于视觉相似的检索技术20，章志勇的基于透视投影的三维模型几何相似性比较算法21等。表1-1对各类检索算法进行了对比分析，总结了各类算法的主要优点、适用场合以及存在的缺陷。表1-1各类检索算法总结通过对目前已有的算法研究分析可以发现，自上世纪90年代基于内容的三维模型检索技术兴起以来，国内外的研究者已经提出了多种具有代表意义的三维模型的检索算法，有些算法具有较好的检索效果，得到了一定程度的应用。但总的说来，目前的检索算法还存在如下问题：（1）缺乏对模型局部显示性的细节的关注。现有的模型检索算法主要是从模型整体形状上描述和提取特征，衡量模型在整体形状上的相似性，未能充分考虑模型的局部细节信息，因而对外形相似细节不同的模型的区分能力不足。（2）检索精度有待继续提高。三维模型的检索算法虽然一直都在研究中，但是算法的检索效果仍然有待提高，没有一种通用的检索算法能针对所有的模型都具有最佳的检索效果，某些平均检索效果较好的算法针对某些模型的检索效果可能很差。因此，继续寻求新的三维模型检索算法，使得检索算法提取的特征能够更全面、更合理的标识三维模型、得到更好的检索效果，这仍然是一个需要继续深入研究的课题。1.3 主要研究工作针对目前三维模型检索算法中存在的对局部细节特征关注不够的问题，本文提出了一种基于三维模型有意义分割理论的三维模型检索方法。主要包括以下几个方面的研究和实现：（1）提出了一种改进的三维模型分水岭分割算法。基于心理学、心理物理学理论中的最小值法则和人类视觉分割特点，本文提出利用有意义分割的思想来描述和提取模型的形状特征。本文在对目前已有的三维模型分割算法进行充分分析和比较的基础上，采用分水岭算法作为本文的三维模型分割算法，同时针对分水岭算法存在的过分割问题，对其进行改进，得到了较好的模型分割效果。（2）描述模型各部件的形状分布，提取模型的全局特征，采用EMD距离度量不同模型在整体上相似性。本文在对模型进行分割得到有意义部件集合的基础上，提取能够表征模型形状分布的全局特征，以衡量模型在整体外部形状上的相似性。在算法具体实现时，本文将各主要部件的表面积占整个模型表面积的百分比作为各部件的权重因子，同时结合各部件的质心位置组成多维特征向量来描述模型的全局特征，再得用EMD距离来度量全局特征的相似性。（3）提取模型的拓扑结构，采用基于树匹配的方式度量其相似性。由于分割得到的部件之间具有邻接关系，能够构成拓扑图，但由于拓扑图的匹配较为复杂，因此本文在拓扑图的基础上构造拓扑树，以拓扑树的方式来描述模型的拓扑结构。最后采用基于树匹配的方式度量其相似性。（4）对于模型的主要部件，采用D2形状分布算法衡量其相似性。对于各部件相似性的衡量，本文采用D2形状分布算法进行衡量，D2形状分布算法本来只适合模型的整体形状匹配，对具有简单形状的模型的检索效果较好，且具有计算简单，快速的优点，正是利用该算法的这一点，本文将其用于模型部件的匹配，因为经过分割得到的模型部件，具有简单的形状，适合用一种简单的方法来描述模型的形状。1.4 论文新意本文的研究主要有以下3点新意：（1）将处于研究前沿的三维网格有意义分割技术与三维模型检索研究相结合，充分考虑模型的细节特征，以提高模型的检索精度。（2）对原分水岭分割算法进行改进，采用扩展多阶邻域的方式计算模型顶点的离散曲率，减少了模型过分割的情况，得到更有意义的模型部件。（3）根据模型分割后的部件集合及其之间的邻接关系，采用两种不同的特征提取算法，得到模型两种不同的形状特征。1.5 论文结构本文共分为五章，具体内容安排如下：第一章：绪论。主要介绍本文研究背景、三维模型检索技术的研究现状、本文的主要研究内容和论文新意。第二章：介绍三维模型检索与分割领域相关理论。包括三维模型的表示方式、三维模型检索系统框架、三维模型标准化预处理、相似性度量、检索性能评价以及典型的三维模型分割与检索算法。第三章：提出一种基于有意义分割理论的三维模型检索算法。利用改进的三维模型分割算法分割模型，得到有意义的分割部件，根据模型的连通性，分别提取模型不同的特征。第四章：实验部分。设计并实现三维模型检索系统，利用实验验证本文算法的有效性，对实验结果进行对比和分析。第五章：全文总结。总结已完成的工作，并提出未来的工作方向。6西南大学硕士学位论文第2章 三维模型检索相关理论第2章 三维模型检索相关理论2.1 三维模型的表示三维模型有多种表示方式，主要有基于点图形学的点云模型表示、基于面图形学的网格模型表示、隐性曲面表示以及基于体图形学的体素模型表示等22。基于点云表示的三维模型结构简单，能够丰富地表达模型复杂的表面（图2-1 a）；基于网格的表示是目前三维模型最常见表示方式，这种方式具有结构简洁，灵活和显示高效等优点，目前主要采用的是三角形网格，因为其它的多边形网格表示都可以细分为三角形网格表示（图2-1 b）。体素可以理解为二维像素在三维空间中的推广，它们是一组分布在正交网格中心的立方体单元23（如图2-1 d），体素模型对于描述模型内部属性（如密度、材料等）时，具有相当的优势。近年来，随着计算机硬件技术的迅速发展，引发了从矢量图形到光栅图形的变革，计算机图形学的研究重点开始从面图形学向体图形学转变。 a 点云模型 b 网格模型 c 渲染后的模型 d 体素模型24图2-1 三维模型不同表示方法本文研究的三维模型的表示方式是目前使用最广泛的基于三角网格的表示方式。在这里给出三角网格的形式化定义26：定义1 三角网格 对于三维空间中一组给定的三角形集合，沿公共的边及顶点处相接构成的空间网格，称为三角形网格，由三角形集合所组成，每一个三角形又有三个顶点组成，即。2.2 三维模型检索系统基于内容的三维模型检索以一种更贴近人们在现实生活中靠直觉印象使用信息的方式，通过对视觉特征的相似性匹配来查找用户所需要的三维模型。整个检索过程可描述为：首先从模型数据中自动计算并提取三维模型的特征（如形状、空间关系、材质的颜色及纹理等），然后与模型特征库所有模型的特征进行比较，返回与待检索模型最相似的前若干个三维模型 262728。三维模型检索系统就是试图利用反映三维模型形状特征的内容信息自动建立特征索引，达到检索三维模型的目的。图2-2给出了一个典型的基于内容的三维模型检索的系统框架。图2-2三维模型检索系统的基本框架从图2-2中可以看到，一个完整的三维模型检索系统包括三维模型数据库的组织、用户检索界面（查询接口）的呈现、特征提取、相似度计算等方面29。（1）三维模型数据库 三维模型数据库是三维模型检索系统最基本的物质基础。三维模型数据库需要具备一定的规模，才能够满足用户的检索需求，且库中的模型需要具有相同的数据格式，以便于进行统一的处理。另外，对三维模型数据库进行一致而有效的组织，建立高效的索引结构，能提高检索效率。文献30利用R*树组织三维模型数据库，得到了较好的数据库结构模型。（2）用户检索界面 作为一个优秀的检索系统，应提供给用户方便的交互性界面，以便于用户进行查询。目前，检索系统界面主要有四种呈现方式：（I）用户提供关键词。这种方式属于常见的基于文本的检索方式，界面简单，但需要为模型库中的每一个模型添加文本注释信息；（II）手工绘制二维图像。文献31提供给用户一个绘图的接口，允许用户绘制用画笔绘制待检索模型的二维草图，然后由系统根据草图自动生成三维模型。这种方式对用户的操作要求很高，因为对于普通用户而言，要准确地绘制一个拓扑结构复杂、有洞的或有许多分支的模型是很困难的；（III）手工绘制三维模型，这种方式与第二种方式类似，对用户的操作要求也很高，因此实用性不强；（IV）由用户上传待检索模型示例，目前多数检索系统都提供这种方式，示例模型可以来自系统数据库，也可以是用户自己上传的模型文件。文献32将已知的模型作为查询输入，通过检索系统检索得到相似的模型，这种方法的检索结果比较理想，但是要求用户必须预先拥有某种模型的范例。因而也有一定的局限性。（3）三维模型特征提取 在常见的三维模型文件中，通常只包含模型的几何属性（顶点坐标、法向矢量、拓扑连接等）和外观属性（顶点颜色、纹理等），很少有适合自动匹配的高级语义特征的描述。因此如何合理有效地描述三维模型（即提取模型特征）的特征是首要解决的问题，也是三维模型检索的难点。一种理想的特征提取和描述算法，应满足：（1）所提取的模型的形状特征能够科学的标识三维模型，即所提取的形状特征具有惟一性，不同的模型对应的特征表示应该不相同；（2）算法简单，易于计算且时间复杂度和空间复杂度低；（3）所提取的特征具有几何不变性，即对模型的平移、旋转、缩放等操作具有不变性；（4）对于具有不同拓扑结构的同一类模型，其形状特征应是稳定的；（5）所提取的特征就适合进行相似性度量；（6）对模型的简化、噪声、变形等具有鲁棒性。（4）相似性度量 三维模型检索的目的是找出所有与所给模型相似的模型，因而对提取得到的特征如何进行相似性匹配是三维模型检索要解决的第二个问题，选择的度量方法必须能够合理表达不同模型之间的相似程度。目前，在三维模型检索系统以上几个方面中，如何合理有效地描述和提取三维模型的特征，即特征提取算法，是三维模型检索首先需要解决的关键技术，也是目前研究最多的一个方面。2.3 三维模型标准化预处理利用三维建模软件或数字几何扫描设备产生的三维模型，其坐标位置、模型方向和尺度都是任意的，而大多数三维模型特征提取算法对三维模型的方向和尺度都很敏感。因此，为了使提取的特征在不同的情况（不同的坐标位置、大小、坐标系统）下都具有不变性，需要对模型进行标准化预处理，或称为归一化（Normalization）预处理。通过对模型进行归一化预处理，能够将任意待比较的模型统一到同一个坐标系统中，使得任意待比较的模型都具有一致的位置、方向和尺度。预处理步骤主要包括平移变换（Translate Transform）、旋转变换（Rotation Transform）以及缩放变换（Scale Transform）。2.3.1 平移变换所谓平移变换33，是指将模型的重心平移到统一的坐标系统的原点，从而保证待比较的模型的位置一致性。平移变换的公式可表示为：（2.1）其中表示原三维模型的顶点集，表示平移变换后的模型顶点集，表示模型重心，模型重心的计算方法有多种，本文主要采用面积加权的计算公式。 （2.2）上式中，表示三维模型中三角面片的数目，表示第个三角面片的面积，表示第个三角面片的平均质心， 表示整个三维模型表面积。2.3.2 旋转变换经过平移变换以后，模型在坐标系中的位置虽然统一了，但是模型的方向却很可能不一致，即不同的模型可能具有不同的旋转角度。三维模型方向的任意性也将造成特征提取结果上的偏差，因此为使得提取的特征具有旋转不变性，需要进一步对模型进行旋转变换。主成分分析（Principal Component Analysis，PCA）是使用最为广泛的旋转变换方法34，PCA根据给定模型的顶点集合构造协方差矩阵，并计算特征值和特征向量。由于三个特征向量相互正交，可以定义一个新的坐标系统，可以把模型归一化到统一的坐标方向上。PCA归一化过程描述如下：（1）计算三维模型顶点均值（公式2.3）。其中表示三维模型中的顶点的坐标。（2.3）（2）构造方差矩阵，是一个对称矩阵。其计算公式如下。（2.4）上式中，存在3个特征值（）和3个对应的特征向量（），从而满足。设为旋转矩阵，是一个的矩阵，其表达式为，则模型的旋转变换可以描述如下。（2.5）是经过旋转变换后的三维模型顶点集合。2.3.3 缩放变换三维模型的尺度大小也将影响模型特征的提取，因此需要在模型平移变换、旋转变换的基础上进一步归一化三维模型的大小，保证模型在不同缩放比例的情况下特征不变。缩放变换需要计算缩放变换因子，计算公式如下35：（2.6）其中：（2.7）（2.8）（2.9）表示第个面片的质心到平面的距离，与类似。模型缩放变换，可以描述为：，是经过缩放变换后的三维模型顶点集合。 （a）A模型 （b）平移变换 （c）旋转变换（d）缩放变换 （e）B模型 （f）平移变换 （g）旋转变换（h）缩放变换图2-3模型归一化预处理过程图2-3中，图a到图d是模型A归一化预处理的过程；图e到图h是