毕业设计（论文）-CAD模型局部区域分割与检索技术研究.doc

各专业完整优秀毕业论文设计图纸摘 要有研究表明，新产品中40%的部分可以采用现有的零部件，另有40%的部分可以通过修改已有的零部件来完成，只有20%的部分需要从草图开始进行全新设计。为了寻找合适的参考方案，设计者60%的时间用于查找资料。在制造业中普遍存在着的大量重复设计与制造现象，给企业造成了巨大的资源浪费，其根源是缺乏有效的资源管理工具。三维cad系统的推广应用使得设计资源的主要形式是三维cad模型。由于模型文本记录的信息随着cad系统、设计者和设计时间的变化具有极大的不确定性，并且文本记录的模型结构信息非常有限，导致单纯基于文本的信息检索技术具有严重的局限性。对复杂多样的物体进行具有一定工程语义的局部区域分割，能够在获取突出局部形状特征的同时，有效地降低模型结构的复杂度。因此，这里研究了cad模型的区域分割与检索技术，具体包括以下几个方面：(1) 提出一种cad模型区域分割方法。首先，用面属性邻接图表达cad模型；接着，基于局部区域和图顶点类型的定义，在面属性图中聚类具有明显凸性的面，以及聚类具有混合凸性的面，将b-rep模型初始分割为凸区域、凹区域和平区域的集合；最后，采用区域融合优化方法，将初始分割得到的局部区域优化组合为数量最少、具有一定工程语义的局部区域集合。(2) 提出基于区域分割的cad模型多级形状描述方法。这里用体范围内的面上下文码和区域上下文码、以及局部区域内的面上下文码来对cad模型进行多级形状描述。上下文码由于引入了模型面或局部区域的上下文邻接关系，大大提高了表征模型形状的辨识能力。(3) 提出基于多级形状描述符的cad模型整体与局部形状检索方法。为了满足用户的不同检索需求，这里提出基于上下文码度量和基于区域属性码匹配统计度量的cad模型整体与局部检索方法。前者用体范围内的面上下文码和区域上下文码相似性度量相比较模型的相似性，后者用局部区域内的面上下文码相似性度量相比较模型的相似性。在以上的cad模型区域分割与检索方法的指导下，基于visual c+、acis和hoops应用软件系统开发了一个三维cad模型分割与检索原型系统。该系统能够实现b-rep模型的局部区域分割，实现不同精准程度的cad模型整体和局部形状检索, 同时用实验验证了研究成果的正确性和有效性。关键词：b-rep模型分割，面属性邻接图，上下文码，整体形状检索，局部形状检索 abstractsome researches demonstrate that about 40% of new products can apply the previous design cases directly, about 40% of new products can adapt the existing design cases to meet new requirements, and only 20% of new products need a new design from scratch. to find the reference cases, engineers spend about 60% of their time retrieving the desired information. nevertheless, the repeated design and manufacture have widely existed in the enterprises, which caused a tremendous loss for enterprise. the reason is that they lack an effective design resource management and retrieval tool.the popularity of three-dimensional (3d) cad systems in industry has resulted in a large number of cad models being generated. because the descriptive texts for cad models have huge uncertainty as the variation of cad systems, designers and design dates, which leads to text-based retrieval for cad models with serious limitations. if a complex object is segmented into several local regions with engineering semantics, it will obtain salient shape features and effectively reduce the complexity of a model. this research mainly discusses cad model segmentation and retrieval approaches, which includes the following aspects:(1) a surface segmentation approach for cad models is proposed. first, a cad model is transformed into a face attributed relational graph (farg). second, in a farg, clustering the faces that definitely belong to a cvr or ccr and clustering the faces that have hybrid convexity based on the definitions of local regions and vertex types. thus, a cad model is initially segmented into a set of local convex, concave and planar regions. finally, an optimized procedure is adopted to merge the initial clusters into regions with optimization.(2) a multi-resolution shape description for cad models based model segmentation is proposed. here, face context codes and region context codes in a model, and face context codes in a region are adopted to represent a cad model in details. context code has an advantage that it introduces the context adjacent relations in a model or a region, which obviously improve the precision of shape description.(3) global and partial retrieval approach for cad models based on multi-resolution shape description is proposed. to meet various retrieval requirements, global and partial retrieval approach for cad models based on context code measurement, statistic of region adjacency codes and face context codes are presented. the former uses face context codes and region context codes in a model to measure the similarity between two models, and the latter adopts statistic of region adjacency codes in a model and face context codes in a region to evaluate the similarity between two models.based on the methodologies mentioned above, a prototype system is developed using visual c+6.0, geometry engine acis and display engine hoops. the system supports cad model segmentation, globe and partial retrieval for cad models. meanwhile, some experimental results show their correctness and effectiveness.keywords: b-rep model segmentation, face attributed relational graph, context code, global shape retrieval, partial shape retrieval1 绪论1.1研究背景和意义cad / pdm / plm系统在产品设计和制造中的推广和应用，产生了大量的产品设计和制造资源，这些资源被存储在工程数据库中。如何对这些资源进行存档、分析和重用，已经成为了一个开放性的难题。在当今激烈竞争的全球市场环境中，提高产品设计与制造的质量、效率和可预知性，是增加产品竞争力的重要手段。而设计与制造资源的重用，是实现这些目标的最好方法之一1。在机械工程领域，产品的大多数零部件是通用机械零部件，同类产品中的零部件大多是相同或相似的。在制造业中普遍存在着的大量重复设计与制造现象，给企业造成了巨大的资源浪费，其根源是缺乏有效的资源管理工具。为了寻找合适的参考方案，设计者60%的时间用于查找资料 2。对于一些典型的强经验、弱理论产品设计，其设计的合理性主要依赖于设计者的相关设计经验。有研究表明，工业中超过75%的产品设计是基于案例的设计或适应性设计，设计活动是重用以前的设计与制造知识来解决新的设计问题3；新产品中40%的部分可以采用现有的零部件，另有40%的部分可以通过修改已有的零部件来完成，只有20%的部分需要从草图开始进行全新设计4。 重用现有的产品设计方案，使用已经被实践证明了的正确零部件或装配模型，可以有效地改进产品质量；重用现有的产品设计方案，可以减少大量的重复性设计工作，提高产品设计的效率；参考已有产品开发的时间、成本以及各种工艺参数值，可以消除产品设计、制造和装配过程中的大部分不确定性因素，提高产品设计与制造的可预知性。 虽然文本检索技术已经非常成熟，但是将其应用于三维模型检索时，需要对所有的模型进行文本形式的语义标注或注释。而模型文本记录的信息往往随着cad系统、设计者和设计时间的变化而变化，不具有唯一性；对于形状复杂的三维模型，文本记录的模型结构信息非常有限。另外，用户可能有时找不到合适的文本关键字来概括检索目标模型的名称、类型和功能。因此，基于形状比较的cad模型检索技术已成为cad领域的热点研究问题之一5-13。有研究表明，人类对于物体形状的认识，部分地基于物体的局部分割14,15。复杂多样的物体通常被认为是由一些简单的基本体或基本元素通过叠加或切割组合而成，并且突出的局部形状特征屏蔽了其它形状不突出的部分。对物体进行具有一定工程语义的局部区域分割，是获取突出局部形状特征的一种重要途径。三维实体模型分割在特征识别、csg(constructive solid geometry)树重构和三维模型检索等领域得到了广泛的应用。对于形状复杂的三维模型检索，其形状描述符的生成以及形状描述符比较的计算复杂度较高。一个重要原因是网格作为网格模型的基本元素，其粒度太小，网格的数量太多。同样地，像多边形面或圆柱面作为b-rep(boundary representation)模型的基本元素，其粒度也不够大，模型面的数量太多。因此，我们需要模型分割，将模型划分为一些具有工程语义的局部区域，来替代网格模型中的网格或b-rep模型中的模型面，作为模型的基本元素，使得模型基本元素的数量大为减少，以降低模型检索过程中的计算复杂度。基于以上分析，本研究工作将研究cad模型的区域分割与检索技术。1.2 三维模型分割国内外研究现状1.2.1 三维网格模型分割三维网格模型既可方便地在不同建模系统中产生，也能通过物体扫描生成。网格的表达方式较为简洁，仅有三角形的几何信息被存储，没有存储任何拓扑信息，缺乏许多应用必需的结构或层次信息。网格分割是按照一定的分割准则将原始三角模型分解为不同的部件或曲面片。它最早来源于图像分割、有限元网格划分和非监督机器学习等领域。网格分割是网格参数化、纹理映射、形状匹配、变形、多分辨率建模、网格编辑、压缩和网格动画等应用问题的预处理步骤。不同的应用需求对网格分割有不同的要求，像网格动画或变形要求被分割的区域是有意义的刚性部件，网格参数化中要求分割的曲面区域比较平坦。因此，三维网格分割的应用领域和分割目的决定了网格分割所采取的方法。根据网格分割的不同应用目标，可以将三维网格分割分类为体类型(part-type)分割方法和表面类型(surface-type)分割方法。前者是将网格模型分割成有意义的体部件。这些体部件的粒度通常较大，主要应用于人体骨架或动物骨架的形状分析、基于网格分割的形状检索、网格动画的骨架提取以及关节体变形等场合。后者将网格模型分割为具有一定几何意义的曲面区域，这些曲面区域通常由平面、球面、柱面或多项式曲面等组成，适合于纹理映射、参数化、网格简化、网格压缩、多分辨率网格模型等应用场合。另外，逆向工程中经常需要将网格模型分割为简单的二次曲面来精确地描述cad模型。图1.1给出了一个动物网格模型的体类型分割和表面类型分割实例，可以明显地观察到这两类分割方法的分割结果的差异性。典型的网格分割方法有区域生长法、分水岭法、reeb 图法、基于模型的方法、聚类法以及谱分析法等。 (a) 体类型分割方法16 (b)表面类型分割方法17图1.1 两种不同类型分割方法的分割结果实例（1）区域生长法区域生长分割方法较早出现在图像分割领域。典型的区域生长有两种方式，一种是先在分割对象内给定一个种子点(seed point)，接着按照一定的规则将种子点周围的像素点加入到该种子区域内，最终将符合生长规则的所有像素点合并成一个局部区域；另一种方式是先将图像分割成许多的小区域，要求同一个小区域内的像素点具有相同的区域属性（如灰度值相同），接着按照一定的生长规则将小区域合并成较大的区域。对于区域生长方法，种子点的选取、区域生长准则和终止条件这三个方面的因素决定了区域生长结果的好坏。区域生长法的优点是：分割思想比较简单，能够将具有相同属性的联通区域分割出来，同时分割得到的结果区域的边界信息比较完整。在没有先验知识时，该方法可以得到比较好的区域分割结果。但是，区域生长法是一种迭代的方法，分割过程比较费时。当噪声和灰度等属性值不一致时，可能会造成空洞和过分割，并且对图像中的阴影处理效果通常不佳。 besl等18用区域生长法对距离图像（range images）进行分割。首先，他们将平均曲率和高斯曲率作为分割属性对数据点进行标号，实现图像的初始粗分割；其次，将可能生长的粗分割结果区域作为种子区域；接着，对种子区域进行变阶曲面拟合，并将与拟合相容的近邻数据点添加到生长区域，直到区域不能再生长为止。后来vieira等19将该方法推广到3d网格分割。lavou等20和guillaume等21 提出了基于曲率张量分析和曲率值分类的区域生长方法。首先，他们采用基于主曲率向量的k-means聚类方法将模型粗分割为曲率值近似为常数的局部区域；其次，基于顶点-三角形混合的方法对区域进行生长；接着，根据曲率的相似性、区域的大小和直径等准则对区域进行合并；最后，依据边界打分和正确边界的跟踪，沿着曲率张量的方向对区域边界进行光顺修正，以消除人工痕迹和不连续性。由于聚类法容易陷入局部最优，使得曲率聚类的结果影响后续的区域生长结果。张等22提出了一种基于高斯曲率的区域生长方法。该方法首先依据高斯曲率对顶点进行标号，与设定的曲率阈值相比较，将具有较大高斯曲率负值的顶点标记为边界点。接着在非边界点中随机选择顶点作为种子点进行区域生长，生长准则是近邻的边界点和那些已经添加到区域的顶点不能生长。该方法的优点是执行过程非常简单，缺点是生长结果在很大程度上依赖于用户定义的曲率阈值。zuckerberger等23采用对偶图的方法取出分割区域。该方法的分割思想是用深度优先或宽度优先搜索的方法从一个种子节点开始遍历对偶图，通过遍历的方法聚类能够形成凸区域的面来实现区域生长，直到新加入的面使得区域的凸性改变为止。如果区域凸性改变，则选择一个未遍历的点作为新的种子点，以相同的方式进行区域生长。该方法的主要问题是容易出现过分割，产生的区域数量通常比所希望的要多。他们对付这个问题的方法是采用一定的融合规则由较大的区域融合近邻的小区域。考虑到曲面区域通常具有一致的凸性，同时其边界处具有与曲面区域不同的凸性，董等24提出了一种基于凸性和特征检测的网格分割方法。首先，依据顶点的凸性和曲率，将区域中的顶点分类为平点、凸点、凹点和特征点，并采用类似图像处理的膨胀处理技术消除孤立的分类点；其次，应用基于拓扑距离的快速dijkstra算法确定种子区域；接着，按照先平种子点生长、再凸种子点生长和后凹种子点生长的顺序进行区域生长；最后，根据顶点和边界边的光滑度进行区域竞争生长。由于顶点的凸性计算过程较为简单，dijkstra算法复杂度较低，该方法可以快速地进行网格分割。另外，由于该方法能较好地保持网格特征,特别适用于cad模型的分割。（2）分水岭法分水岭分割是一种基于拓扑理论的数学分割方法，起源于二维图像分割。其分割思想是把图像作为测地学上的拓扑地貌，图像中每个像素点的灰度值表示该点的海拔高度，亮度比较强的地区像素值较大，而比较暗的地区像素值比较小。每个局部极小值及其影响区域被定义为集水盆，由集水盆的边界形成分水岭。通过寻找图像中的“集水盆地”和“分水岭界限”，对图像进行分割。如果图像中的目标物体是连在一起的，则图像分割的难度通常较大。分水岭分割方法通常处理这类问题的效果较好。分水岭分割方法对微弱边缘具有良好的响应，能够到封闭连续的边缘。但是，图像中的噪声、物体表面灰度的微小变化，都可能会使图像分割产生过分割现象。为消除分水岭算法产生的过度分割，通常有两种方法可以解决过分割问题，一是用先验知识排除无关的边缘信息；二是修改梯度函数，使集水盆只响应探测目标信息。vincent等25首先应用分水岭算法解决三维网格曲面分割的问题。mangan等26提出的分水岭网格曲面分割方法使用曲面的高斯曲率作为区域边界的索引来实现曲面分割。网格曲面被分割成面片区域，每个面片区域具有相对一致的曲率。其具体方法是先由网格顶点曲率确定局部最小值顶点、平坦高地和凹地，并对他们进行标号，实现初始粗分割。接着，采用从上到下或从下到上的合并方法，将分水岭深度小于设定阈值的区域进行合并，得到最终的网格曲面分割结果。marty 27用分水岭算法实现人脑皮层网格曲面的分割，以曲率作为分水岭算法的高度函数。page等28用快速分水岭算法实现基于认知的三维网格分割。基于最小值规则，他们采用局部主曲率来定义方向高度图，考虑模型上每个顶点的主方向和主曲率，由最小曲率等高线确定的区域，即为初始的粗分割。接着，在模型上创建分水岭方法所需要的标识集，使用分水岭方法实现标识区域的生长，完成网格模型的分割。rettmann等29提出了一种用分水岭算法分割人脑皮层网格曲面的方法。不同于以前的人脑皮层网格曲面分割方法主要关注皮层折叠之间的沟特征取出及其特征描述，他们在测地距离中引入了一个后处理算法，解决了分水岭算法存在着的过分割问题。钱等30提出了一种基于拟合曲面的曲面误差估计方法，以解决曲率计算过程中存在着网格噪声敏感问题。该方法能够动态地调整拟合曲面的顶点个数，既提高了曲率计算的精度，又增强了基于曲率的分水岭算法的噪声鲁棒性。（3）基于聚类的方法聚类是把相似的对象通过静态分类的方法分成不同的组别或者更多的子集（subset），并且同一个子集中的成员对象都有相同的或相似的属性。聚类分析以相似性为基础，在一个聚类中的模式之间比不在同一聚类中的模式之间具有更多的相似性。将数据库中的对象进行聚类是聚类分析的基本操作，其准则是使同一类中个体之间的距离尽可能小，并且不同类中个体之间的距离尽可能大。典型的聚类算法有k-means方法、k-medoids方法、clarans方法和birch方法等。基于聚类的模型分割方法是运用聚类算法，对网格模型中的网格单元，依据距离函数度量将距离聚类中心最近的单元进行归类，从而实现模型分割。从现有的相关文献分析，用于网格分割的聚类算法主要有分层聚类和迭代聚类两种算法。分层聚类法就是对给定数据对象的集合进行层次分解，将每一个对象作为一个类，然后根据某种度量将这些类合并为较大的类；或者将所有的对象置于一个类中，然后根据某种度量逐渐细分为较小的类。合并点或者分裂点的选择是分层聚类法的一个关键步骤。由于后一步的工作是在前一步已经被合并或者分裂对象的基础上进行的，前一步的不恰当合并或者分裂，不能在后面的步骤取消撤销，并且类之间不能交换对象。因此，不合适的合并或者分裂决定，可能出现不恰当的聚类结果。另外，分层聚类算法的可伸缩性不强，在决定合并或者分裂之前，需要对大量的对象和类进行检查和估算。garland等31针对原始曲面模型，提出了一种基于层次聚类的网格模型分割方法。他们首先构造网格面的对偶图（如图1.2），对偶图顶点代表的每个面都是一个聚类，用反映平坦性的二次误差来度量对偶图边代表的网格区域平坦性。通过不断地对对偶图最平坦的边执行边收缩操作，实现区域的聚类合并。整个聚类过程中，由二次误差的阈值来控制区域的聚类合并。该方法简单、健壮、效率高，可以快速有效地对网格模型进行多分辨率分割。inoue等32采用了类似的边压缩方法对cad模型进行分割简化。该方法用与网格单元面积相关的区域面积要足够大、区域的边界应该尽可能光滑和区域应该尽可能平坦这三个准则指导对偶图的边收缩。其缺点在于约束过于复杂，并且参数的设置也比较麻烦。attene等33采用与文献31相同的分层聚类方法，将网格模型分割聚类为与平面、球面和柱面近似的层状区域。该方法从平面、球面和柱面这三类面中，选择与对偶边拟合误差最小的面进行区域合并，合并的终止条件是分割结果区域数量达到了用户指定的数量。该方法可以有效地取出平面、球面和柱面，特别适合于cad模型的曲面分割。图1.2 一个对偶图实例迭代式聚类法是将网格模型的网格单元依据距离函数度量，将距离聚类中心最近的单元进行归类，从而达到分割的目的。由于其聚类中心通过最小函数计算后在不断发生更新，一般可以得到较合理的聚类中心以及分割结果。kmeans聚类算法是模型分割应用最为广泛的用迭代聚类算法，它是典型的基于原型目标函数聚类的方法，优化目标函数是数据点与原型之间的距离，迭代运算的调整规则是函数求极值。kmeans算法以欧式距离作为相似度测度，寻找对应某一初始聚类中心向量v的最优分类，该分类能够使评价指标j最小。它采用误差平方和准则函数作为聚类准则函数。kmeans聚类算法的优点是：当聚类是密集的，并且类与类之间的区别明显时，聚类效果较好；对于大数据集聚类，该算法高效且具有可伸缩性。shlafman等34用基于kmeans聚类的体类型网格分割方法对网格曲面进行变形操作。他们提出的kmeans聚类分割过程如下：(a)计算每个网格对之间的距离；(b)计算出网格单元的初始聚类中心；(c)对所有网格单元，计算它们与最近聚类中心之间的距离；(d)通过使网格单元与其聚类中心之间的距离为最小来更新聚类中心；(e) 重复步骤(a)至(d)，直到聚类中心不再发生变化为止。类似于shlafman等34提出的基于kmeans聚类网格分割方法，katz等35提出了一种基于分层模糊kmeans算法的网格模型分割方法。该方法的距离函数是重心的测地距离权和以及网格之间角度。在二叉树分割时，网格被分割为两个细分区域和一个模糊区域。由最小割算法将模糊区域切割归类到两个细分区域，两个细分区域被较深的凹面分离。分层模糊kmeans算法的优点是模型被分割为有意义的组成部分，并且深度凹面符合极小值规则；缺点是分割边界没有被凹面包围，最小切割不是总能找到最优分割边界。1.2.2 三维实体模型分割工程应用中的三维模型大多是参数化的cad实体模型，主要有csg和b-rep两种表达方式。前者通过原始体素的布尔运算生成实体模型，表达方式比较直观，容易理解，但存在着csg描述的不唯一性问题。b-rep表达包含有模型的几何和拓扑信息，实体与模型之间是一一对应关系。但是几何和拓扑信息以私有的数据格式存储，在不同的cad系统之间转换时，存在着数据丢失的情况。实体模型分割是将形状复杂的物体分解为简单的体元素。现有的体分割相关研究主要集中在加工特征识别领域，常用的体分解方法有凸分解36,37和基于壳的分解38,39。凸分解方法递归地将初始体模型分解为凸壳、以及凸壳与原来形体之间的毛坯去除体。体方法通常用二叉树描述初始体模型，由布尔运算的并集和差集运算来实现模型体的分解。然而，由于很难定义曲面的凸壳，凸分解方法不能应用于具有曲面形状的形体分割。此外，一些在初始形体中不存在的虚构面，在形体分解过程中被产生，这些虚构的面可能使初始形体的特征失真。基于壳的分解方法将初始体模型分解为不包含凹边的最大体元素。首先，初始体模型被分解为具有简单形状的壳元素；接着，一些壳元素被合并，以便能够找到最大体元素。该方法中，初始体模型分解仅由布尔并运算来完成，并且能够分割具有二次曲面的体模型。然而，由于体分解过程中仅仅应用了布尔并运算，很难得到理想的分解结果。另外，合并壳元素的过程中寻找最大体元素所需要的时间，与壳元素的数量存在着指数级的关系。shah等40使用半空划分将实体模型分割成最大凸体，由模型表面的半空间交叉实现模型的半空间划分。然而，使用弯曲表面分割实体模型时不是总能找到半空间划分操作。sakurai等41将实体模型分解为一组单元体，然后将相关的单元体优化组合形成最大体单元，从而实现实体模型分割。当面壳的数量较多时，该方法在合并单元体时计算效率较低。woo等42通过递归二等分实体模型和组合二分体单元的最大体单元来改善最大体分解的扩展性。该方法在分割过程中，有时产生大量的不合理的细小特征，并且计算时间是指数级的。马等43使用切割环收缩的方法分解实体模型，通过选择特殊的切割环决定面壳的表面划分，将实体模型分割为体单元。上述各种方法存在的问题是在模型分解过程中，往往会强行切割模型中原本不需要分割的部分而得到不合理的分割体，同时也使分割体失去了原本的设计意图。dong等44通过面延伸重构体特征的方法来实现多面体模型分割。首先，通过特征面与其邻接面延伸求交，生成新的顶点和边；接着，依据新生成的顶点和边、以及模型中原有的顶点和边，构造一个线框模型；最后，依据面信息将线框模型转化为实体模型。这里的特征面是指模型中具有加工特征痕迹的平面。sandiford等45和sashikumar等46在dong方法的基础上，提出了一种基于面延伸和边延伸的体重构方法。该方法能够分割具有二次曲面的模型。li等47提出的基于面延伸和边延伸的体重构分割方法，对延伸面和延伸边进行了更为细致的分析，进一步推广了该类方法的应用范围。基于延伸面或延伸边方法的局限性在于，延伸面和延伸边的选择对模型分割结果有直接影响。不合理的延伸面或延伸边选择，会导致模型无法封闭。1.3 三维模型整体检索国内外研究现状cad模型检索是信息检索的一个重要应用。传统的cad模型手工检索分类，主要依赖于人的认知对机械零件进行分类。成组技术是最为经典的机械零件手工分类方法。众所周知，手工分类方法是费时和易于出现错误的，并且手工分类的方法难以在企业级对数以万计的机械零件模型进行分类。近年来，基于内容的cad模型自动检索已经出现48。形状描述是实现cad模型自动检索时最为重要的任务。形状描述符是用简洁的数学方法对三维模型的形状进行抽象描述，以实现模型的形状检索。一般地，每一种整体形状检索方法，都有自己独特的形状描述符，用于表达cad模型的整体形状相似性。大多数模型的整体形状描述符可以分类为以下三种类型：数学描述符、基于视图的描述符和基于知识的描述符。1.3.1整体形状数学描述符 (1) 整体特征形状描述符基于整体特征的形状描述符是用整体几何属性的特征向量表征三维模型的整体形状。paquet等49首次提出用边界盒表征二维视图形状，并且使用基于弦的向量集、基于小波变换的体积占有率等整体特征比较三维形状。paquet等50和zhang等51提出的三维形状匹配方法使用矩作为三维实体的特征描述符。lou等52提出的方法采用不变的主惯量评估三维形状的相似性。zhang等53通过引入表面积比率、不变矩和傅里叶变换系数，对基于整体特征的三维形状描述符进行了进一步的扩展。sun等54使用离散小波变换描述曲面区域的曲率和曲面边界的径向距离。kazhdan等55提出了一种基于反射对称性的三维模型形状描述符，它具有良好的噪音鲁棒性和采样分辨率。基于整体特征的形状描述符的一个普遍缺陷是一类特征向量仅仅表征几何属性的一个方面（如不变矩、表面积比率等）。因此，基于单一特征向量的描述符并不能全面地反映模型的形状内容。基于数学变换的形状描述符将三维模型的空域信息通过数学变换方法变换为频域信息，用变换系数表征模型的形状特征。球面调和函数是典型的数学变换的形状描述符，它用出色的调和系数近似地表征三维形状，因而能够更为全面地表征模型的形状内容。现有的大部分相关工作是用基于球面调和的方法评估三维模型之间的几何属性的相似性56,57。vranic等56提出了一种基于球面调和函数的三维形状描述符。球面调和函数主要描述模型的整体特征向量。首先使用球面傅里叶系数从已经正交化预处理的模型中取出特征向量，接着通过比较球面调和特征向量得到相比较模型的形状相似度。类似地，saupe等57同时采用矩和球面调和函数评估三维模型的几何属性相似性。morris等58将球面调和推广到生物高分子领域，用于判定蛋白质结构是否具有可以利用的生化特性。他们用球面调和系数表征蛋白质的结合口袋形状，并且用系数空间的几何距离评估结合口袋之间的相似度。papadakis等59 提出的三维形状描述符用球面调和函数表征分析模型的缩放和轴翻转不变性，并且用连续的主元分析法表征分析模型的旋转不变性。基于数学变换的形状描述符能够对三维模型进行从粗到精的多分辨率形状表征，与其它形状描述符有着良好的互补效果。但该方法要求在数学变换前，需要对三维模型进行规范化的预处理，计算过程比较复杂。(2) 基于统计的形状描述符基于统计的形状描述符是利用统计学的思想，通过对三维形体进行采样测量，统计具有一定形状辨识能力、并能反映模型本质内容的形状特征出现频率，以统计分布曲线或统计直方图来表征三维模型的形状。osada等60较早用整体形状的概率分布表征三维模型的形状。概率分布是使用几何函数a3和d2等在模型表面进行随机采样，统计几何函数数值出现的次数。这里a3是测量模型表面3个随机点之间形成的角度，d2是测量模型表面任意2个随机点之间的距离。通过评估两个相比较模型的概率分布，得到相比较模型的相似度。ip等61通过将d2函数细分为in、out和mixed三种类型，将初始的形状分布统计方法推广到cad模型形状检索。in是指连接模型上2个点的线段完全在实体模型内；out是指连接模型上2个点的线段完全在模型外；mixed是指连接模型上2个点的线段穿过模型。由d2、in、out和mixed的加权和来度量相比较cad模型的相似度。该方法在检索cad实体模型时，具有一定的精度。其缺点是需要将每条线段与三维模型求交，以判定其类型。概率分布方法的优点是几何函数简单，描述符生成过程中不需要姿态调整和模型配准等预处理步骤。另一类基于统计的形状描述符是形状直方图。它最早来源于检索二维多边形的截面编码技术，其基本思想是将模型进行三维分割，并用编码的方式对分割形成的部分进行描述。最基本的分割技术是ankerst等62提出的同心球分割、扇形分割以及同心球与扇形相结合的空间分割方法。模型中每个分割形成的部分，在空间占据的比例被编码成一个向量，作为模型形状比较的对象。同心球分割得到的形状直方图具有旋转不变性；扇形分割得到的形状直方图具有比例不变性；同心球与扇形相结合的分割方法得到的形状直方图的形状辨识能力较强，但不具备旋转不变性和比例不变性。kriegel等63提出了一种基于体素化模型的形状直方图描述符。由于该方法需要考虑的体素驻留哪在一个分区比较明确，导致计算的复杂度比较低。其它类型的基于统计的描述符有基于弦的测量64、标量函数分布65、球映射信号66和基于密度的描述符67等。总的来说，形状直方图表征三维模型的形状比较直观，但这类方法需要在分割前对模型进行姿势规范化的预处理，并且对于某些形状复杂的三维模型，由于它们的形状直方图近似于钟形曲线，导致形状直方图比较相似的两个复杂模型，它们的实际形状可能很不相似，图1.3给出这样一个实例。在图1.3中，三维模型heat_exchanger1的d2形状分布直方图与grip的d2形状分布直方图更为相似，而实际的模型是heat_exchanger1与heat_exchanger2更为相似。图1.3 形状直方图对某些复杂模型形状辨识能力不足的实例681.3.2基于视图的整体形状描述符与1.3.1中的整体形状数学描述符不同，基于视图的整体形状描述符是人类使用不同的感知来评估三维模型的相似性。基于人的感知，如果两个物体从每个视角看起来都相似，或者从三维视角观察到两个物体具有很强的相似性，我们认为这两个三维物体是相似的。（1）二维视图形状描述符近二十多年来，基于内容的图像检索技术已经成为了一个活跃的研究主题。这些图像检索方法大多将从图像中取出的颜色、纹理或二维轮廓等作为形状描述符来评估二维图像之间的相似度，其中的大部分方法能够推广应用到三维模型的形状检索。基于二维视图的三维模型检索的理论依据是：两个三维模型如果是相似的，那么从任意视角看它们都应该是相似的。一些不同的二维视图描述符被用于表征模型的形状，并且被作为模型形状比较的间接比较对象。funkhouser等69和garca等70使用模型的二维轮廓（silhouettes）视图作为图像形状描述符。与人们常用三个二维视图表征模型的形状不同，funkhouser等69用从十三个视角方向投影获得的二维视图表征模型形状，这十三个视角方向分别对应于模型所在立方体的三个侧面、四个顶点和六条边。chen等71提出的扩展二维轮廓视图描述符使用光场投影得到的十个二维轮廓视图表征模型的形状。具体方法是选择十个均匀分布的光场进行投影，每个光场由一个半球里的十二面体的二十个顶点发光，投影得到十张二维轮廓视图。光场描述符能够有效地过滤高频率的噪声，具有旋转不变性。vranic等56用视平面与物体之间的距离作为模型的形状描述符。他们认为，在正交三维模型的图像中，较暗的像素显示视平面与物体之间的距离较大。barton等72提出的机械零件模型检索方法用正交投影轮廓表征三维模型的形状。为了准确地表征cad模型的形状，pu等73 提出的基于图样（drawing）的二维视图形状描述符，同时考虑了二维视图的轮廓信息和内部信息。hou 等74为了比较可变形模型的形状，采用分而治之的方法匹配特征点对应的二维轮廓。二维视图形状描述符用比较简单的二维轮廓视图描述复杂的三维模型，使问题的复杂度大为降低，并且该方法与人类的视觉特征比较符合。但二维轮廓视图生成过程的计算量较大。通常情况下，表征模型形状的视图数量越多，模型的形状表征越准确。然而，随着视图数量的增加，视图匹配的复杂度将以几何级数方式增长。（2）拓扑图形状描述符拓扑结构反映了模型的空间架构、以及模型内部局部区域之间的连接关系，它是三维模型的一种本质属性。由于三维模型内部的某些拓扑关系并不满足树形结构，用图描述三维模型的拓扑关系是一种自然的选择。基于图的三维模型描述符主要有三种类型：属性邻接图7579、reeb图8083和骨架（skeletal）图8479。ei-mehalawi等75较早用面属性邻接图表征三维cad模型。面属性邻接图表达的几何属性包括模型的面属性和邻接边属性。面属性主要考虑了面的几何类型，邻接边属性包含了边的几何类型、边与x轴之间的相对方位角和边与z轴之间的相对方位角。陶等76提出的面属性邻接图考虑的面几何属性更多，包括面的几何类型和凸性，以及边的几何类型、凸性、边角、边开始角和边终点角等信息，用码头header 描述面的几何类型和凸性，用外环边上下文码c描述外环边的所有几何属性。外环边上下文码的引入，明显地提高了模型面的形状辨识能力。王等80提出的面属性图考虑的面属性包括面的几何类型、法矢、曲率和面积以及共边、平行、垂直和共面等面关系。面属性邻接图的优点是易于应用b-rep边界生成，但是当模型的面数量较多时，图的规模可能过大。reeb图是用高度函数、曲率函数和测地距离函数描述三维模型的拓扑信息。hilaga等81提出了一种基于测地距离函数的多分辨率reeb图描述符。该描述符定义测地距离为模型中两个顶点在模型表面的最短距离，用reeb图顶点描述区域的连通部分，由连通部分的邻接关系决定图顶点是否相连。reeb图中的连通区域越多，函数值的密度越大，相应的reeb图分辨率越高。由于创建reeb图的函数是连续的，该描述符不能有效地辨识存在分离结构的模型。chen等82提出了一种改进的多分辨率reeb图描述符。该方法在生成reeb图前，引入了预处理步骤，将大的三角形面片分割为较小的三角形面片，有效地提高了reeb图表征实际工程模型形状的分辨率。bespalov等83通过大量的工程模型形状比较实验发现，多分辨率reeb图在某些特定的分辨率下，实际形状非常相似的两个模型，它们的reeb图差异性非常明显。tung等84为了提高reeb图描述符的精准程度，在reeb图顶点属性中引入了体积和曲率等属性，对多分辨率reeb图进行了改进。iyer等85和lou等86较早提出了骨架图描述符。骨架图的基本元素包括顶点、边和环，图的边与独立的几何实体相对应，图的环与模型的孔洞相对应。生成骨架图时，首先需要将三维模型体素化，接着将它们细化为细小的骨架，最后运用骨架行进算法将细小的骨架转换为骨架图。如果模型有微小的形状变化，其骨架图一般不发生变化。kim等87 提出了一种基于中轴变换和扩张的骨架图描述符。首先，将网格模型初始体素化；接着，采用基于模型体元排列的方法生成模型骨架；最后，由顶点的联合和扩张形成骨架图。该骨架图存在的问题是图的规模过大。gao等88提出了一种基于层次递阶中面的骨架图描述符。该骨架图描述符通过选取合适的蔓延单元，对中轴骨架提取方法进行了改进，既保留了其具有仿射不变性和可重构性的优点，又改进了其不稳定的缺点。然而，当模型比较复杂时，层次递阶中面骨架提取法存在着数据量大和拓扑结构不直观的问题。骨架图描述符比较直观，同时支持模型的整体和局部形状匹配，特别适合具有关节的模型形状描述。1.3.3基于知识的整体形状描述符在cad模型检索领域，为了弥补纯几何形状描述符缺少领域知识的缺陷，一些考虑了机械工程领域知识的cad模型形状描述符被相继提出。ramesh等89较早提出了一种基于加工特征的机械零件形状描述符。该描述符考虑的加工特征信息包括存在的加工特征类型、加工特征类型的数量、特征加工需要的安装次数、需要的加工工具数量、在同一工位能够加工的操作次数、能够使用同一工具加工的次数以及加工需要的装备数量等七个方面。cardone等90,91为了评估新零件的加工费用，提出了一种基于加工特征的cad模型形状描述符。针对使用三轴加工中心加工的零件，他们考虑的加工特征信息包括加工特征的进给方向、加工特征的类型、加工特征的体积、加工特征的尺寸公差和特征组基数等。对于加工成本比较接近的cad模型形状比较，该描述符具有较高的精准程度。基于加工特征的形状描述符存在着加工特征识别的不唯一性问题。由于表征机械零件形状的成组编码存在着与应用背景密切相关的问题，srinivas等92提出了一种基于形状特征和内部特征关系的机械零件描述符。形状特征包含形状、公差、材料和装配等方面的信息。tsai等93提出了一种基于产品几何信息和工艺属性的形状描述符。几何信息由csg构建的各类基本设计单元数量来描述，共有穿孔、盲孔、台阶、斜面、t形槽、倒角和肋板等十五种类型的基本设计单元。工艺属性由零件的原材料体积、材料硬度、耐腐蚀性、最小表面粗糙度和最小尺寸公差等属性来描述。zhang等94提出了一种基于产品信息、管理信息、功能信息和加工信息的机械零件形状描述符。产品信息包含管理、功能、几何、特征、加工和用户等方面的信息；管理信息包含产品类型、装配工艺和设计版本等方面的信息；功能信息包含顾客需求、设计意图、以及产品功能和行为等方面的信息；加工信息包含加工方法、零件材料和零件最大边界尺寸等方面的信息。以上形状描述符存在着的主要问题是：除模型以外的其它许多信息需要手工输入