- 相关推荐
基于网格特征临界点的三维工程模型检索算法
摘要：随着计算机辅助设计(Computer Aided Design，CAD)技术和三维图形硬件的不断发展，专业化CAD软件在工业中得到了广泛使用。三维工程模型已成为工程分析和生产制造的基础，是现代工程企业产品数据事实上的标准，为工程信息的构建、分析和重用提供了新的手段，大大提高了设计和制造的效率。由于产品结构越来越复杂，产品类型不断增加，需要设计的模型越来越多，造成工程三维模型爆炸式的增长。统计显示，在产品设计中只有20%的零部件是需要全新设计的，40%可以从现有设计中直接得到，剩下的40%可以从现有设计中修改得到;75%的新设计都需要参考已有的设计和知识口]。
现今许多企业正在建立企业内部的三维工程模型数据库，方便了产品开发人员及时有效地获得所需的三维模型，加快了产品开发的步伐。在客户需求多样化的今天，有效检索并重用已有的三维模型及相关设计知识已成为实现产品快速研发、提高企业竞争力的重要手段。
传统的检索方式是将CAD模型中附带的文件名、零部件数量或内容等信息作为关键词进行检索，这种方法相对简单易行，但已不能满足日益增长的检索需求 [z]。许多学者采用基于图(graph)的方法对模型进行检索[3q]，并将其应用于基于实例的产品设计中。他们将零件本身的结构特征(如几何、加工精度特征等)、工艺特征(如外圆、内孔、平面、槽等)及其相互间的关系提取出来用有向图表示，进而通过子图同构来检索需要的模型。这种方法有效地利用了零件自身的信息，与领域知识关联紧密。但前提是必须对模型进行特征识别，才能准确提取出模型的特征信息。由于不同商业CAD系统内部三维模型表示方法以及建模方式不同，阻碍了CAD系统问的产品数据交换和模型共享。目前的通用加工特征识别算法不稳定，特征识别只能针对某种CAD系统单独进行二次开发，工作量大，且缺乏通用性和一般性。况且子图同构算法是NP难问题，一旦零件复杂，对应的有向图急剧膨胀，检索效率将大大降低。
为此，本文提出一种与CAD系统无关的基于网格特征临界点的三维工程模型检索算法。该算法以三维模型的网格化表示作为检索输入，通过对网格模型的分析，找出表征网格形状的关键点，即特征临界点，以这些点为基础计算三维模型的形状度量，通过相似性比较，从模型数据库中检索出与输入模型相似的模型。
1、原理与方法
1.1 Morse理论和网格特征临界点
1934年，美国数学家M.Morse提出用分析方法研究空间拓扑性质，即Morse理论[5]，成为微分拓扑学的一个重要分支。空间是几何研究的对象，而函数是分析研究的对象。因此，定义于空间上的函数与空间的形状有着紧密的联系。Morse理论正是研究空间上的函数与空间关系的，它特别关注的是函数的临界点，并从临界点的信息中获取空间形状的信息，即研究流形上光滑函数的临界点与流形本身拓扑结构之间的关系。本文以Morse理论作为理论基础，将网格模型映射为Morse临界点的集合。
设MCR“为行维空间下的紧致流形，函数，：
M—R为作用在M上的一个光滑实值函数，在点P(越)∈M处建立局部坐标系，“=(U。，?，U。)，则：①如果函数厂在点P的梯度为零，即 3f/aU。一0，i∈[1，咒]，则P是函数，的临界点。②如果P是函数，的临界点，且，在P点处的Hessian矩阵日(，)(P;32，越)5(蠢女)非奇异，则P是Morse。$i界-A。
本文只考虑M是三角网格、函数厂是分段线性实值函数、且作用在网格M的顶点上的情况，三角面片内部的函数值可由顶点处的函数值插值得到。
假设对任意的边<夕，Pz>∈M，均有厂(P，)≠厂(Pz)，可推知在任意三角面片内部，梯度都是恒定的非零实数，且I临界点只出现在网格的顶点上[5]。
对于二维流形，Morse临界点分为极大值点、极小值点和鞍点三类。若P为极小值点，则厂在P的/J,lI台i域的各个方向均上升;若P为鞍点，则P 为厂在P的小临域内上升下降转换的过渡点;若P为极大值点，则厂在P的小临域的各个方向均下降。图1表示了网格顶点P的分类情况，其中圆圈表示与P相连的顶点可i，0表示f(v。)>厂(p)，e表示厂(让)<厂(夕)。
1.2网格特征区域
Chang Ha Lee等人于2005年提出了网格特征区域(mesh saliency)的概念[6]。网格特征区域是对网格模型局部区域重要性的一种度量，即该网格模型局部区域能否体现网格形状特点，其基本思想是函数，将模型表示为采样点处函数值的概率分布。
计算网格顶点的平均曲率，并对其进行高斯加权平该方法易于理解，实现简单，计算效率高，对网格退均(Gaussian-weighted average)，然后计算顶点的化的情况鲁棒性好，但存在以下不足：
特征因子，以此对顶点进行滤波，找出能体现网格模(1)由于该方法中采样点的数量是一定的，不能型外形特点的区域。根据模型的形状与复杂程度自适应地产生采样点，本文结合网格特征区域和Morse理论，找出网特别针对工程模型，一些很重要的局部几何特征(如格上表征网格局部形状的特征临界点，并以基于这槽、凸台)很难被充分采样，而对于平面特征往往被些临界点之间的距离和角度值的统计规律作为形状过采样，因此采样点不能很好地体现工程模型的形描述子，对网格进行形状比较。状特点。
1.3基于形状分布的图形检索算法
普林斯顿大学Robert Osada等人提出的基于形状分布的方法(D2)E73是图形检索领域中十分重要的算法，其基本思想是：首先对模型进行采样，生成一系列的采样点，然后通过作用在模型上的形状(2)此算法采用单一形状分布函数，即任意两采样点间的欧氏距离，虽然计算简单，但没有充分利用模型的其他几何信息，如三角面片和网格顶点处的法矢和曲率信息，所以单一的形状分布函数很难充分反映出模型的外形特点，检索结果差强人意。图2所示为三个模型的比较结果，可以看出，虽然三个模型的外形差异很大，但通过此算法得到的形状分布曲线是相似的。可见该方法并不能很好地区分这三种模型，此算法有待改进和增强。
C.Y.IP等人根据任意两点的连线与模型的位置关系，将距离分为In distances，Out distances和Mixed distances，改进了D2算法，并用于比较CAD模型[8]，改进方法较传统的形状分布算法有效，但计算过程复杂，计算量过大，实时性有待加强，且不能避免传统形状分布算法不足对检索结果的影响。
2、基于特征临界点的形状检索算法
为了克服传统基于形状分布检索算法的不足，本文提出了基于特征临界点的检索算法。其基本思想是以三维工程网格模型作为输入，通过分析网格顶点的离散法矢和平均曲率，找出表征其结构的特征临界点，然后计算临界点间的形状函数值，并对其进行概率统计，给出形状分布图，通过计算形状分布相对于传统算法，该算法的优势在于：
(1)用网格模型的特征临界点代替传统的采样点进行形状函数计算，避免了采样不足对算法造成的影响。根据Morse理论，特征临界点反映了空间模型的拓扑几何信息，且其对模型中有重要工程意义的结构敏感，因此比随机生成的采样点更能体现模型的结构特点，更具针对性。
(2)取网格益面上两点间近似测地线距离与两点处法矢夹角的余弦值作为联合形状函数，对函数值进行概率统计，给出二维形状函数分布图。较之单一的形状函数D2，近似测地距离更能表征模型表面形状的变化，法矢夹角余弦反映了模型局部区域内形状的分布，因此联合形状函数在两个方面综合考虑了模型的结构，更全面地反映出模型的外形特点。
(3)不计算任意两点间的联合形状函数值，而是根据Morse理论，将II缶界点分为极大值点、极小值点和鞍点，针对每类临界点计算联合形状函数值，模型的整体描述由三者加权平均得到。这样提高了计算效率，使统计结果更具可比性，能够更合理地描述模型结构。
2.1 网格微分量的计算
三角网格模型是一种离散曲面表示形式。法矢和曲率作为重要的微分几何特性。描述了三角网格模型的局部几何特征。由于离散形式的曲面是一种分片线性曲面，没有连续的法矢和曲率，通常只考虑顶点处的法矢和曲率，其余各点的几何特性可通过对顶点进行线性插值获得。近几年来，众多学者提出了一系列估算离散曲面微分量的新方法。浙江大学方惠兰等人对国际上提出的三角网格曲面上估算平均曲率的七种方法和估算高斯曲率的四种方法进行了总结和比较，指出2002年 Meyer等人提出的Voronoi方法对高斯曲率和平均曲率估算最优砷]，因此本文将该方法扩展到顶点法矢的计算，并用其计算网格顶点的离散曲率。
Voronoi方法的基本思想是把光滑曲面看作是一族网格的极限或者线性逼近，把三角网格每个顶点的微分量看作是此三角网格在此顶点一个小邻域的平均度量。与一般算法等同看待小邻域内所有三角形不同，该算法根据小邻域内三角形的不同类型(锐角、直角和钝角三角形)，分别采用不同的面积计算方法，更好地体现了面片上的微分量对顶点处微分量的影响。具体过程可参考文献[10]。
图4表示按照Voronoi方法计算得到的三个工程模型顶点处的离散曲率分布，颜色越深代表此处的曲率越大。2.2网格特征临界点的计算根据 Morse理论，笔者首先取作用在网格模型上的实值函数厂为网格顶点p处的离散平均曲率H(p)与该点影响因子的代数和，则函数，的Morse临界点体现了网格模型的空间拓扑几何结构。
Morse临界点的计算如下‘11。：
步骤1对每个顶点户∈M，采用Voronoi方法计算其平均曲率H(p)。
步骤2计算顶点P对局部形状的影响因子。
根据顶点P的邻域对H(户)进行加权平均，以此将顶点处的曲率与顶点的邻域联系起来，通过计算邻域顶点间对局部形状影响的差异，体现该顶点对局部形状的重要性。采用双向平滑算子(bilateralsmoothing operation)对H(户)进行邻域相关的加权平均。影响因子的计算如下：
B(H(户)，口)一[Σ(H(z)一H(夕))J∈F‘p·2a)W。(fI z—p J)w。(I H(z)一H(夕)1)]/[Σz∈F(p·2a)Wc(1l z—P 11)Ws(1 H(z)一H(户)})]。(1)其中，F(p，盯)为距离顶点户在盯范围内的顶点的集合;Wc(z)=exp[-一z2/(2口冬)]为标准高斯滤波函数，W。(z)=exp[一，/(2盯§)]为特征保持加权函数。
步骤3根据B(H(p)，盯)更新函数厂的值。
步骤4控制计算的迭代次数，控制最终得到的特征临界点的数量。迭代次数越多，生成的特征临界点的数量越少。
步骤5根据Morse临界点的分类，将得到的临界点分为极大值点、极小值点和鞍点。
上述过程的伪代码如下：Procedure SalientCriticalPoints(M，d，iteration)输入：M为三角网格模型，d为顶点邻域半径，iteration为迭代次数。
输出：Sc为特征临界点集合。
局部变量：N为M中顶点的数量，Pl为M中的第i个顶点，f(pi)为顶点pl处的实值函数值，a，为顶点Pl的影响因子。
Begin集合{P1)=M的所有顶点;N一集合{Pl}的势;for(j=1 to iteration)计算顶点P，处的平均曲率H(pO，令f(pi)=H(pi)lfor(i一1 to N)计算顶点pl的影响因子ai(M，f(pi)，d);更新f(Pi)+一8i;endend将得到的实值函数值{f(P1)}，利用Morse临界点的定义判断Pi的类型，return网格特征临界点集合Sc，end图5是对3个零件网格模型进行临界点计算的结果，其中第一列是模型所有的临界点，第二列是极大值点，第三列是极小值点，第四列是鞍点，图片下方的数字表示此类临界点的数量。
2.3形状函数
形状函数定义了能够表征模型形状的几何特征，通过计算临界点处的函数值来反映模型的结构特点，因此形状函数的选择对提高算法的性能至关重要。传统的 D2距离虽然计算简单，但并不足以反映模型的外形特点，因此检索结果不理想。本文采用两点间近似测地距离和两点处法矢夹角余弦作为联合形状函数，近似测地距离反映了整个模型表面形状的变化，法矢夹角余弦体现了模型局部区域形状的分布。
(1)近似测地距离函数测地线在微分几何中有着严格的定义，即曲面上的一条曲线，如果它的每一点处的测地曲率为零，则称为测地线，在工程中可将其直观理解为曲面上连接两点的最短路径。由于精确计算测地线算法复杂、时间复杂度较高，本文采用近似测地线，网格上组成近似测地线的所有小线段的欧式距离和即为近似测地距离。
本文采用Takashi Kanai等人提出的算法，计算网格上两顶点间的近似测地路径，其思想是首先将网格的顶点看作图的节点，网格顶点间的连接看作图的边，采用计算图最短路径的Dijkstra算法获得初始最短路径，然后对此路径所在的局部邻域进行网格细分，再对细分后的区域采用Dijkstra算法计算最短路径，以此迭代，直至近似最短路径的长度变化小于预先设定的阈值。具体实现细节可参考文献[12]。为了更快速地计算，本文采用最短路径快速算法(Shortest Path Faster Algorithm，SPFA)代替Dijkstra算法[131。
由近似测地距离的定义可知，此形状函数是平移、旋转不变的，但因距离是对模型大小的一种度量，故是缩放可变的。图6表示了从模型中某一临界点到其余同类临界点间的近似测地路径。
极大值点极小值点鞍点图6网格模型l司类临界点同的近似测地路径(2)顶点法矢夹角余弦定义NA为法矢夹角余弦，设临界点p;，p，处的单位法矢分别为露，。和n，。，则由向量内积可得n以·n声，==I刀以I×I n户;I×cosL(力以，n声，)=》NA=cosL(肛p，np)一np·np。(2)因为在区间[o，丌]内余弦值是单调下降的，所以可以用来唯一度量两矢量的夹角。由定义可知此形状函数是平移、旋转和缩放不变的。
2.4形状分布矩阵
根据特征临界点的类型，分别计算每类临界点(即极大值点、极小值点和鞍点)中两两顶点之间的联合分布函数。因为特征点的类型不同，其所表征的网格上局部区域的凸凹性不同，所以分类型计算联合分布函数使得到的形状分布矩阵更具可比性，并且把计算联合分布函数局限到每一类中，比传统的计算任意两点间的形状函数的计算量大大减少，效率更高。这样做虽然忽略了两组l临界点间的拓扑关系，但因为本检索算法本质上是基于概率统计的，并且每类临界点的分布并没有局限到某一区域，而是在模型整体上分布的，所以只要有足够的临界点，足够的临界点间形状函数值，该模型的形状特点就能通过概率统计反映出来。绝大多数情况下不同组内的函数值加权得到的统计规律已能很好地表现出模型的形状分布规律。
计算每类临界点两两之间的测地线距离和法矢夹角余弦值。由于近似测地线距离函数是缩放可变的，要对其进行归一化处理，常用的方法有最大值归一和平均值归一。考虑到最大值归一易受噪声数据影响，故采用平均值归一化：设每一类中计算得到近似测地距离的最大值为D……，平均值为D……，需要将距离 [o，D……]平均划分为L个单元，则将[o，n。]和[D……，D……]分别等分为L。/2个单元，即得到平均值归一化的分布。NA值域为[一 1，1]，设需要将其平分为L，个单元。对每对临界点的联合形状函数值进行统计，可生成形状分布矩阵MD=(z州)，×L√z。为近似测地距离￡属于单元 i且NA属于单元。『的临界点对总数占所有临界点对总数的比例。将P，NA，l：值分别对应z，Y，z轴，可得到联合形状函数的二维概率分布图。
分别对三类临界点进行上述计算得到三个矩阵，则一个网格模型即可抽象为三个联合形状分布矩阵的线性组合，即M=谢DIn。;+凸 MDmi。+7，MDs“。(3)其中：M为网格模型的形状分布矩阵;MD加剃MDm"M腑a分别表示与极大值点、极小值点和鞍点对应的形状分布矩阵;a，J9，y分别表示三类矩阵的系数，且满足归一化条件口+口+y=1。设N。，N。t。，N州分别表示模型中极大值点、极小值点和鞍点的数量，本文取口5瓦i可吒而N’?卢一—Nma --1-N—minN-。}I_n-N,.a’
(4)图7表示按照本算法得到的归一化后的模型形状分布。其中三维柱形图分别表示了一个模型总体在极大值点集、极小值点集和鞍点集层次上的形状分布。从图中可以看出，分属不同类别的两个模型，其形状分布具有较大差异，因此本算法具有较好的区分能力。
图7也比较了统一计算任意两临界点的形状函数值和按组计算形状函数值得到的模型形状分布的差异。前者因用于统计的函数值大大增加，统计结果较分组计算的结果分布稍均匀一些，但最后得出的统计规律与分组计算形状函数值并无本质区别。平面着色图反映了在一个柱形图中单元数值的分布情况，单元的颜色越亮，数值越大，可见同一模型的三个柱形图内部数值分布规律并不相同，说明了将特征临界点分为三类分别进行计算的合理性。在工程模型中存在大量的相互之间成直角的面，形状分布矩阵中的非零值会集中在表示180。，90。，o。的三行中(Y轴度量的是夹角的余弦值，分别对应Y轴的0，10，20)，针对该情况笔者进行了专门的实验。图8说明了分布在上述三行中的存在大量互成直角面的模型的形状分布特点，它与存在其他分布特点的模型并无本质不同。实验证明，此类模型的形状函数值虽然主要分布在这三行中，但每一行的具体分布规律因模型不同而有所不同，因此本算法也能较好地区分其间的差别。
图8大量存在互成直角面的模型及其形状分布2.5形状比较经上述处理，模型的比较转化为形状分布矩阵的比较。本文仍然采用L。范数，即欧式距离计算两矩阵间的距离。令MA=(m。)I，xL，B=(m6)f。×L。v M分别为模型A，B对应的形状分布矩阵，则模型A，B间的距离为D(A，B)=D(MA，MB)一
3、算法复杂度分析
由算法过程可知，提取网格特征临界点和计算近似测地距离是时间复杂度较高的两个步骤。
3.1提取网格特征临界点的时间复杂度
(1)网格微分量计算需计算每个三角面片的面积，最坏情况下，即每个三角面片为锐角三角形时，按照Voroini方法，一个三角面片的面积需计算三次(三次面积各不相同)。由于面积计算仅是单独的乘法，与其他步骤相比，可认为此步骤的时间复杂度为常数。
(2)顶点影响因子计算最耗时部分为搜索任意顶点在某邻域内的所有顶点。本文将顶点数据存入k-d树来加速此过程。设网格顶点数为N，计算临界点时的循环次数为艴，文献[-14]中已证明，在一棵肛d树中插入和搜索节点的平均时间复杂度为0(109：N)，故此步骤最终的时间复杂度为 o(nN·l092N)。
3.2计算近似测地距离的时间复杂度
本文采用SPFA算法计算从任意顶点到其余顶点的近似最短路径。设网格模型的边数为E，求得的所有临界点数量为Nc，文献E13]已证明，计算从任意点出发到所有顶点的近似最短距离的时间复杂度为0(E)，故此步骤最终的时间复杂度为o(Nc·E)。
4、算法验证与讨论
以Visual C++6.0为集成开发环境，结合Matlab 6.5实现了本文提出的算法，并在普渡大学建立的工程标准模型库ESB(engineering shapebenchmark)‘153上进行了验证。实验采用PC机，AMD 2500+CPU，512 M内存。
ESB中包含866个STL格式的工程模型，笔者以其中任意一个模型作为输入，欲检索出模型库中相似的模型，并与传统图形分布算法(D2 shape distribution)和增强图形分布算法[16](D-IA shape distributionwith simplification)进行了对比。本文描述的算法以模型的STL格式作为检索输入，实验中的参数为L，=64，L，=20;根据实验结果，取盯=0.24%￡，￡为网格模型包围盒对角线的长度，并取UC一如一口，iteration一10。图9列出了前五个检索结果，其中的数字表示检索到的模型与输入模型的距离。从图中可以看出，基于特征临界点的算法能够比另外两种方法检索出更多有效的模型，这是因为特征临界点本身就是模型的顶点，由 Morse理论可知，临界点表征了模型的空间拓扑结构和几何结构，因此比基于采样点的方法更能反映模型自身的特点;且本算法采用的近似测地距离代替传统的 D2距离，测地线本身就是对模型表面形状的反映，其长度亦体现了模型局部形状的变化，用于做形状函数效果较好，但其计算比D2距离要复杂。因此，鉴于对时间复杂度的考虑，近似测地距离是一种较好的折衷。
现对不同检索输入的检索时间和有效性进行统计，可得到算法的平均性能。针对ESB库中的三大类模型，即薄壁件、棱柱类零件和旋转件分别统计，将其综合得到算法在整体ESB库上的平均性能，做出查准率一查全率(Precision—Recall，PR)曲线，并与其他形状检索算法(表面积与体积描述 [151、角度分布直方图[17‘、3D球谐描述子[18]、2D形状直方图[1?、光场描述子[20])进行了比较，如图10所示。
从PR曲线可以看出，本方法虽然目前还达不到光场描述子的效果，但它有效提高了传统D2形状分布算法的检索性能，在计算复杂度和检索效果之间找到了一种平衡。
对图10的实验数据进行综合，表1定量地比较了D2形状分布、带网格简化的D-IA形状分布和本文算法的检索精度和效率，FT，ST，NN的含义见参考文献E16]。从中可以看出，基于特征临界点的方法虽然总的检索时间有所增加(主要是计算近似测地距离需时较多)，但仍在可接受的范围内，且其检索结果要明显优于另外两种方法。
5、结束语
针对传统基于形状分布检索算法的不足，提出了基于特征临界点的检索算法。该算法以三维工程网格模型作为输入，以Morse临界点理论为依据，用网格模型的特征临界点代替传统的采样点进行形状函数计算，避免了采样不足对算法造成的影响;取网格曲面上两临界点问近似测地线距离与两点处法矢夹角的余弦值作为联合形状函数，更好地表征了模型整体表面和局部区域的变化;分别针对极大值点、极小值点和鞍点计算联合形状函数值，模型的整体描述由三者加权平均得到。实验结果表明，本算法客观反映了工程模型的相似程度，明显提高了传统图形分布方法检索的有效性。
以下几项工作在未来研究中应该着重加强：①本文算法的时间效率虽然可以接受，但还有很大的提升余地来找到效率更高的近似测地距离算法。②采用欧拉距离计算两矩阵间的距离存在缺点。形状矩阵中的每一列(行)代表一形状度量向量，不同度量向量对于区分形状有着不同的重要性，而欧拉距离将矩阵不同列(行)之问的差别等同看待，因此最终的距离只反映了平均综合的结果，不能表示出某一形状度最向量对总体差异的影响。这样导致了两矩阵即使距离较近，但其代表的图形可能并不相似。
因此可以尝试其他的度量方法，从而不仅反映矩阵间的距离，而且能体现矩阵自身的分布。③由于特征临界点体现了模型局部的形状信息，可以考虑将其用于局部形状检索。
【基于网格特征临界点的三维工程模型检索算法】相关文章：
基于遗忘理论的英语移动学习模型探究的论文05-20
基于运筹学运输问题模型的电煤采购决策论文04-25
简论控制算法理论和网络图计算机算法显示05-04
游戏模型毕业论文06-05
论文写作中文献资料检索04-14
基于新预算法行政事业机构财务管理的困境与解决策略论文09-03
基于有限元分析工程机械结构问题思考论文05-04
基于有限元分析工程机械结构问题的探讨论文05-07
基于体育教学中教与学的互动分析06-10