《基于骨架树的机械零件三维模型检索方法-朱文博.pdf》由会员分享，可在线阅读，更多相关《基于骨架树的机械零件三维模型检索方法-朱文博.pdf（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 第 52 卷第 13 期 2016 年 7 月 机 械 工 程 学 报 JOURNAL OF MECHANICAL ENGINEERING Vol.52 No.13 Jul. 2016 DOI： 10.3901/JME.2016.13.204 基于骨架树的机械零件三维模型检索方法*朱文博 耿国庆 刘阳阳 张 祥 阳 鼎(上海理工大学机械工程学院 上海 200093) 摘要： 提出了一种基于骨架树进行机械零件三维模型检索的方法。检索分为两个阶段。第一阶段首先提取机械零件三维模型骨架，然后将骨架转换成骨架树并用邻接矩阵来描述骨架树的拓扑结构特征，通过比较邻接矩阵特征值之和迅速完成零件拓扑结构匹配
2、，实现零件的初步筛选。将大量与待匹配模型拓扑结构差异较大的模型过滤掉，极大地减少了第二阶段的匹配计算量。第二阶段首先寻找匹配的骨架子树，其次在匹配子树的基础上搜索骨架枝匹配对，进而采用空间离散曲线的曲率和弗朗内特标架进行空间曲线相似性计算，得到整个骨架形状相似度。通过实例验证与试验分析，该方法快速有效，具有较高的准确性和良好的鲁棒性。 关键词 ： 机械零件；三维模型检索；骨架树；拓扑结构；邻接矩阵；弗朗内特标架 中图分类号 ： TH128 3D Model Retrieval Method of Mechanical Parts Based on Skeleton Tree ZHU Wenbo
3、 GENG Guoqing LIU Yangyang ZHANG Xiang YANG Ding(School of Mechanical Engineering, University of Shanghai for Science and Technology, Shanghai 200093) Abstract： A method for 3D model retrieval of mechanical parts based on skeleton tree is put forward. Retrieval is divided into two stages. The first
4、stage is to extract the 3D model skeleton of mechanical parts, and then convert the skeleton into a skeleton tree. Using the adjacency matrix to describe the topological structure of the skeleton tree, the initial selection of mechanical parts is realized by comparing the sum of eigenvalues of the a
5、djacent matrix. A large number of models which have a big difference with the matching model in topological structure are filtered out, which greatly reduces the matching computation of the second stage. The second stage, find the matched skeleton subtree firstly, search matched skeleton branches ba
6、sed on the matched subtree secondly, and then using the curvature and Frenet frame of space discrete curves to calculate the skeleton branches similarity, and then get the whole skeleton tree shape similarity. Through example analysis with the experiment, this method is effective and has high accura
7、cy and good robustness. Key words： mechanical parts； 3D model retrieval； skeleton tree； topological structure； adjacent matrix； Frenet frame 0 前言*在进行产品设计时，可以从大量的实际案例中找到与之类似的案列进行复用设计，因此，如何快速的从大量的案例中检索出所需要的相似案例成为急需解决的问题。针对机械零件三维模型的检索，AONO 等1提出了一种三维零件描述符，对于具有孔和表面粗糙度的机械零件，通过计算三维模型不同投影的傅里叶谱来检索模型的相似度，然而，对
8、于模型表面复杂度较高的零件此方法实现起来较*上海市教育委员会科研创新 (13YZ071)和国家自然科学基金 (51375314)资助项目。 20151026 收到初稿， 20160412 收到修改稿 难。 HU 等2提出基于典型面匹配的机械零件检索方法，利用特定几何形状的分布函数进行实体模型的检索， 该方法可以检索到具有局部相似特征的零件，但无法满足对模型整体形状和拓扑特征相似性的检索。 IYER 等3将模型形状转化为特征矢量和一个独特的骨架图，利用其组合距离提供一种间接衡量模型相似性的方法。该方法适用的零件相对简单。ALIZADEH 等4提出了一种基于视图的形状特征，并利用二维泊松方程的搜索
9、来检索三维物体。CHEN 等5提出了一种基于三维点的三维模型匹配与检索的方法，选择测地线距离直径和形状函数构造特征点的双向特征，从数据库找到最相似的模型月 2016 年 7 月 朱文博等：基于骨架树的机械零件三维模型检索方法 205 形状。韩丽等6通过构建模型的拓扑结构树，并融合局部突起的几何特征，提出一种基于图结构和几何细节的模型相似性匹配方法。徐敬华等7提出基于递归分割的机械零件三维形状结构检索方法，将实体进行分割，建立有序的满二叉树，通过比较非根结点实体的相似度，获得零件三维模型相似度，该算法可以准确反映零件整体和局部特征，但是算法较为复杂。 HOMEM 等8用广义势场法推导出二维规则多
10、边形的骨架，然而只针对平面图形，对于三维模型未涉及，不能适用于机械零件的检索。关华等9提出一种人体三维 Reeb 计算方法， 给出基于Reeb 图的一般人体骨架结构表示， 该方法简单有效地表达了人体模型的拓扑结构，但是并不能表达模型表面形状特征，对于机械零件并不适用。中轴变换法和广义势场法原理类似，提取的骨架都是一维线性结构，能很好的表达模型的拓扑和形状。但是中轴法不能保证骨架的连通性和单像素性，而且中轴容易受到边界噪声的干扰，容易出现毛刺10。马锐等11-13提出了一种构建 3D 模型多层次骨架的算法，通过在模型边界均匀分布同种点电荷，生成广义势场，选取不同种子点，在力的引导下生成模型的骨架
11、。广义势场法提取的骨架可以有效排除边界噪声，具有良好的连通性，本文生成骨架的方法就是建立在广义势场法的基础上。 本文首先生成机械零件骨架，随后匹配骨架的相似性，整个匹配过程分为两个阶段。第一阶段比较骨架拓扑结构相似性，并设定阈值，淘汰掉拓扑结构差异较大的零件，缩小检索范围。第二阶段通过匹配骨架子树和骨架枝，计算整个骨架的形状相似度，从而得到机械零件三维模型的相似度。 1 提取机械零件模型骨架 本文提取骨架的算法是根据文献 14中所述方法完成的。以图 1a 零件一为例，简述该零件骨架的生成。首先对零件进行预处理，得到零件的模型如图 1b 所示。 图 1 零件一及其预处理模型一 预处理后，模型无中
12、空结构。依据文献 14，假设简化后零件模型表面均匀分布着正电荷，这些电荷在模型内部产生了一个稳定的电场，使得模型内部某一点的电场力方向是一定的，模型内部起始点受到电场合力的作用，起始点沿着合力的方向按照一定的步长前进，直到到达最小位势点。起始点的移动轨迹构成骨架的分支，最终连接相邻最小位势点形成完整的骨架。图 1 所示零件模型的骨架提取如图 2 所示。 图 2 模型一的骨架提取 2 骨架树拓扑结构相似性 常见机械零件模型表面主要由平面和回转面组成，提取出的骨架是由若干彼此相连的空间直线段和空间曲线段构成，骨架体现了零件模型的形状特征和拓扑特征。如果骨架为空间直线段或空间曲线段，称之为非环状骨架
13、枝；如果骨架为一个圆周，则称之为环状骨架枝。零件的形状特征主要由骨架枝的形状和空间位置来确定，骨架枝之间的匹配将在第 3 节中论述。零件的拓扑结构特征由各个骨架枝之间的连接和层次关系来确定。本节将零件的拓扑结构特征转换为骨架树，并用邻接矩阵来描述骨架树，通过比较邻接矩阵特征值之和从而得到零件拓扑结构的相似性。 2.1 生成骨架树 为了描述骨架的拓扑结构特征，将骨架转化成一种树状结构称之为骨架树。 将骨架的所有起始点、具有两个及两个以上线段的连接点称为骨架树的节点。其中，骨架的所有起始点为骨架树端点；具有两个及两个以上线段的连接点为骨架树分叉点。以各分叉点为球心做与模型表面相切的最大内切球，取具
14、有最大球半径或靠近零件重心的分叉点为骨架树的根节点，其余各节点为根节点的子节点。除根节点外的分叉点衍生出的骨架树为整体骨架树的子树，该分叉点为子树根节点，以各子树根节点衍生出来的节点均为该子树根节点的子节点。 图 3 为模型一的骨架。根据定义，0S ，1S ， ， 机 械 工 程 学 报 第 52 卷第 13 期 期 206 17S 为骨架树的节点，其中，0S 、1S 、2S 、3S 、12S 、13S 为骨架树分叉点，其余各点为骨架树的端点。经测量选取0S 点为骨架树根节点，其余各节点称为骨架树根节点的子节点。以1S 、2S 、3S 、12S 、13S 为各子树根节点，各子树根节点衍生出来的
15、节点为该子树根节点的子节点。 例如：1S 是子树根节点，4S 、5S 、6S 、7S 是1S 的子节点。由于骨架枝14 15SS 和16 17SS 均为圆周，则14 15SS和16 17SS 为环状骨架枝，14S 与15S 、16S 与17S 均互为子节点。其余骨架枝均为非环状骨架枝。由图 3 所示骨架生成的骨架树如图 4 所示。 图 3 模型一的骨架 图 4 模型一的骨架树 2.2 邻接矩阵表示骨架树 邻接矩阵可以准确表达骨架树的拓扑结构特征15。在对零件进行匹配时，可以通过比较各个零件骨架树所对应的邻接矩阵的相似度来判断零件拓扑结构的相似性。由图论16中关于邻接矩阵的知识，将模型的骨架树映
16、射到与之对应的邻接矩阵 G=(V， E)中，该矩阵为 N 阶 0,1方阵。其中 V 为该树的节点集， E为骨架树中骨架枝的集合。该邻接矩阵满足公 式 (1)()1,0ijijvvA i j n=其他E(1) 由此方法得到的模型一骨架树 T1 对应的邻接矩阵1TA 为式 (2) 012 1516170121151617011 0 0 0100 0 0 0100 0 0 0000 0 0 0000 001000 0 1 0TSSS S S SSSSSSS= A(2) 2.3 计算邻接矩阵特征值之和 根据矩阵的性质，由同一节点引出的子节点之间的不同排列顺序不会对矩阵特征值计算结果产生任何影响。由于
17、0,1邻接矩阵的迹为 0，即其对于0,1对称矩阵其特征值之和为 0，所以在计算 0,1对称矩阵特征值之和时忽略负特征值，即邻接矩阵特征值之和为所有正特征值之和。 经计算1TA 的特征值 (1TA )为 2.578 1、 2、1.853 6、 1、 1、 1、 0.326 9、 0、 0、 0、 0、 0、0、 0.857 5、 2、 2、 2.270 5、 2.630 6，忽略负特征值之后， T1 的邻接矩阵特征值之和为()1TA =9.758 6。 2.4 骨架树的拓扑结构匹配 两个零件相似程度越高，它们的拓扑结构相似程度也越高，所以在进行零件检索时，可以通过比较零件拓扑结构的相似性，进行初
18、步检索。零件骨架树的拓扑结构特征与其邻接矩阵的特征值之和是相对应的，因此可以通过计算矩阵特征值之和来比较骨架树拓扑结构相似性。两邻接矩阵特征值之和相差越小，表示两个骨架树的拓扑结构越相似。 图 5 所示为零件二及其预处理模型二，用文献14的方法生成骨架，如图 6 所示；模型二骨架对应的骨架树如图 7 所示；由模型二骨架树生成的邻接矩阵如式 (3)所示。 图 5 零件二及其预处理模型二 月 2016 年 7 月 朱文博等：基于骨架树的机械零件三维模型检索方法 207 图 6 模型二的骨架 图 7 模型二的骨架树 0 1 2 1617180122161718011 000100 000100 00
19、0000 000000 001000 010TSSS SSSSSSASSS = (3) 记模型二的骨架树为 T2， 它对应的邻接矩阵为2TA ，该矩阵的特征值 (2TA )为 2.629 2、 2.093 1、 2、 1.100 8、 1、 1、 0、 0、 0、 0、 0、 0、 0、0、 1、 1.496 6、 2、 2.478 4、 2.848 2。忽略负特征值之后， T2 的邻接矩阵特征值之和()2TA =9.823 2。如 2.3 节所述，模型一的骨架树 T1 的邻接矩阵特征值之和为 ( )1TA =9.758 6，1TA 和2TA 的特征值之和相差 0.064 6，说明零件一和零件
20、二拓扑结构的相似程度是非常高的。 由此，比较零件拓扑结构相似性的方法为：首先生成待匹配零件和零件库中已有零件的骨架、骨架树及相应的邻接矩阵，然后逐一计算邻接矩阵特征值之和，将待匹配零件与已有零件邻接矩阵特征值之和的差的绝对值从小到大排列，排序越前，则该零件与待匹配零件的拓扑结构越相似，至此完成零件第一阶段的检索。设定阈值，便可得到部分与待匹配零件拓扑结构相似的零件，淘汰掉拓扑结构差异较大的零件， 缩小第二阶段搜索范围。 阈值的设定是用户根据第一阶段的检索结果，人为指定一个值，也可以直接设定从第一阶段的检索结果中提取前多少个零件参与第二阶段检索。 3 骨架形状相似性 第二阶段比较骨架的形状特征相
21、似度，首先寻找匹配的骨架子树，其次在匹配子树的基础上搜索骨架枝匹配对，通过计算骨架枝之间的相似度来计算整个骨架的形状相似度。 3.1 建立子树匹配关系 骨架树的整体拓扑结构匹配可以通过计算整个骨架树对应的邻接矩阵的特征值之和确定， 同理，骨架树中任意一个子树对应着整体邻接矩阵的一个子矩阵，两个子树对应的子矩阵的特征值之和相差越小也反映这两个子树的拓扑结构越相似。 计算两个骨架树中各子树的邻接矩阵特征值之和，通过计算特征值之和的差找出各子树的最优匹配，直到其中一个骨架树中的所有子树均建立了匹配关系。含有环状骨架枝的子树和不含环状骨架枝的子树进行分类匹配。 如图 4 所示，骨架树 T1 共有五个子
22、树，分别为： 以1S 为根节点的子树1Ts (1S 4S 、5S 、6S 、7S )；以2S 为根节点的子树2Ts (2S 8S 、9S 、10S 、11S )；以3S 为根节点的子树3Ts (3S 12S 、13S 、14S 、15S 、16S 、17S )；以12S 为根节点的子树12Ts (12S 14S 、15S )；以13S 为根节点的子树13Ts (13S 16S 、17S )。 由零件模型的对称性可知，子树1Ts 和2Ts 的结构是完全相同的，它们对应的邻接矩阵均为式 (4) 1/ 20111110000100001000010000Ts Ts=A (4) 其特征值为 2、 0、
23、 0、 0、 2，忽略负特征值，该矩阵特征值之和为 2。同理，12Ts 和13Ts 的结构也是完全相同的，它们对应的邻接矩阵均为式 (5)。 机 械 工 程 学 报 第 52 卷第 13 期 期 208 12/ 13011101110Ts Ts=A(5) 其特征值为 1、 1、 2，忽略负特征值，该矩阵特征值之和为 2。3Ts 对应的邻接矩阵为式 (6)。 30110000100110010000110100100010100000100010010010Ts=A(6) 其特征值为 1.813 6、 1、 1、 1、 0.470 7、 2、2.342 9，忽略负特征值，特征值之和为 4.813
24、 6。 由于12Ts 和13Ts 都含有环状骨架枝，它们的特征值之和与1Ts 和2Ts 的特征值之和相等，但是两对骨架枝的拓扑结构完全不同，所以，在进行子树匹配时，首先要把子树分为环状子树和非环状子树两类，匹配需在同类子树间进行。 如图 7 所示，骨架树 T2 中存在五个子树，分别为115678()Ts S S S S S - 、 ；2Ts (29SS- 、10 11 12SSS、 )；3Ts(34SS- 、13S 、14S 、15S 、16S 、17S 、18S )；41Ts (4S-15S 、16S )；42Ts (4S-17S 、18S )(由于在骨架提取中，当圆柱体的高与直径相等时，含
25、有两个环状骨架的子树的根节点重合，故将4S 作为两个具有环状骨架枝子树的公共根节点 )。其中，1Ts和2Ts 完全相同，它们对应的邻接矩阵的特征值均为 2、 0、 0、 0、 2，忽略负特征值，特征值之和为 2；3Ts 对应的邻接矩阵的特征值为2.124 9、 1、 1、 1、 0、 1、 1.363 3、 2.761 6，忽略负特征值，特征值之和为 5.124 9；41Ts 和42Ts对应的邻接矩阵的特征值均为 1、 1、 2，忽略负特征值，特征值之和为 2。 两个骨架树 TI 和 T2， T1 的子树1Ts 和2Ts 与 T2的子树1Ts和2Ts 的特征值之和均为 2，且为非环状骨架枝子树
26、， 则1Ts 与1Ts、2Ts 与2Ts 相匹配或者1Ts与2Ts 、2Ts 与1Ts相匹配。12Ts 和13Ts 为含有环状骨架枝的子树，41Ts 和42Ts 为含有环状骨架枝的子树。将环状骨架枝单独匹配，即12Ts 与41Ts 、13Ts 与42Ts 相匹配或者12Ts 与42Ts 、13Ts 与41Ts 相匹配。子树匹配完成， 仅剩余部分骨架枝未参与匹配。3Ts中剩余骨架枝为312SS 和313SS ，3Ts中剩余骨架枝为313SS和314SS。未匹配的骨架枝不参与骨架枝相似度计算，仅需要计算其长度，在第 3.4 节骨架整体形状匹配时作为分母的一部分。 3.2 匹配骨架枝 匹配骨架枝仅在
27、已匹配的两个子树的基础上搜索，不匹配的子树间不进行搜索骨架枝匹配对。 若以iS 和jS为根节点的子树建立了匹配关系，那么它们与各自父节点之间的骨架枝也建立匹配关系。例如 T1 的子树1Ts 和 T2 的子树1Ts建立了匹配关系，则它们与各自父节点之间的骨架枝01SS与01SS建立匹配关系。在两个建立匹配关系的子树中，若为非环状骨架枝的子树，对于与端点相连 (最末端的 )的骨架枝， 依次对两个子树的骨架枝进行遍历匹配，根据第 3.3 节所述方法计算出两两骨架枝相似度值， 找到各自的最佳匹配。 例如子树1Ts 和1Ts为匹配子树，将1Ts 中任一骨架枝如14SS 与1Ts 中15 16 17 18
28、SS SS SS SS 、 这四个骨架枝逐一按照第3.3 节所述方法计算出两两骨架枝相似度值， 求得与14SS 最佳匹配的骨架枝为15SS， 然后再将1Ts 中的剩余骨架枝与1Ts剩余的骨架枝逐个匹配建立匹配关系，直到其中一个骨架树的骨架枝全部匹配完成。 若为含有环状骨架枝的子树，则环状骨架枝之间直接建立匹配关系。例如在骨架树 T1 与 T2 中，3Ts 与3Ts均含有环状骨架枝，则环状骨架枝14 15SS与15 16SS、17 18SS逐一按照第 3.3 节所述方法计算出两两骨架枝相似度值，求得与14 15SS 最佳匹配的骨架枝为15 16SS，然后计算16 17SS与17 18SS相似度值
29、。 3.3 计算骨架枝相似度值 根据第 1 节所述的骨架提取方法，得到的骨架枝是从骨架起始点按一定步长沿合力的方向生成的。任意两个步长之间都存在连接点，且这些连接点之间距离都是相同的，即得到的骨架枝是一条条空间离散曲线或直线。图 8 为骨架枝03SS，构成骨架枝数据点集为 P=Pi， i=1， 2， ， m，是由一列m个三维数据点集连接而成。比较两个骨架枝的相似性就转换成计算它们所对应的空间离散曲线或直线的相似度。 图 8 骨架枝03SS 设一对匹配骨架枝 A 和 B 用数据点表示分别为月 2016 年 7 月 朱文博等：基于骨架树的机械零件三维模型检索方法 209 11 112,mA PP
30、P= ， 22 212,nBPP P= 。由于骨架生成时的步长不同， 两个骨架的曲率不具有可比性。为了对两个骨架枝进行比较，需要先将步长较小的骨架枝的步长放大max( , )min( , )ijijf ff f倍 (if 和jf分别表示骨架枝 A 和 B 的步长 )，然后求出骨架枝 A 各数据点的曲率为1(1,2,)iki m= ，骨架枝 B 各数据点的曲率为2(1,2,)jkj n= 。两骨架枝相似度的计算方法如下。 若12ijkk、，均为零或常数时，即两个骨架枝均为空间直线或为环状骨架枝； 以及12ijkk、一个为零，另一个不为零时，即一个骨架枝为空间直线，另一个骨架枝为空间曲线，则该对骨
31、架枝的相似度(,)M AB如式 (7)所示 min( , )(,)max( , )ijijf mf nMABf mf n=(7) 式中，if 和jf分别表示骨架枝 A 和 B 的步长，m和n分别为骨架枝 A 和 B 的三维数据点数。 若12ijkk、均不为零且不为常数，即两个骨架枝均为空间离散曲线时， 采用差分法进行相似度比较。根据微分几何学中关于曲线论的知识17，描述空间离散曲线主要有两种方法：一种为函数拟合法，另一种为差分法。函数拟合法适用于可以表达为函数的空间曲线，由于电场法生成的部分骨架枝很难用函数表达，故此方法不适用。采用电场法生成的骨架枝是由步长相等的点阵构成，满足差分法的适用条件
32、。求出待匹配骨架枝每个数据点的曲率和弗朗内特标架，通过比较每个骨架枝上点的曲率和弗朗内特标架值来计算骨架枝相似度值。计算曲率和弗朗内特标架的公式如式 (8)所示18 = tp=ppbpp=nbt k =pp(8) 式中 ，p为矢量点， t 为切矢， b 为副法矢， n 为曲率矢， k 为曲率。 ,tnb构成弗朗内特标架。 设骨架枝 A 为固定点云空间曲线，骨架枝 B 为可移动点云空间曲线， 其相似度的算法分两步进行： 第一步， 将骨架枝 A 的数据点1iP 曲率1ik 与骨架枝 B 的数据点2jP曲率2jk逐个进行匹配，当满足12ijkk -时，则对1iP 与2jP进行第二步的弗朗内特标架计算
33、。 其中为设定的阈值， ( )0,1，值太小会导致较多骨架枝无法建立匹配关系，太大则会出现相似度计算误差太大，经大量实例验证，本文设=0.3。当12ijkk -时，则对1iP 曲率1ik 与21jP+的曲率21jk+进行匹配，当满足121ijkk +-时，则对1iP 与21jP+进行第二步的弗朗内特标架计算，直到其中一条骨架枝所有点完成匹配。 第二步， 记骨架枝 A 的点1iP 的弗朗内特标架为 111,iiitnb，骨架枝 B 的点2jP的弗朗内特标架为 222,j jjtnb；计算出满足 T222 111, ,j jj iii=R tnb tnb的旋转矩阵 R，若满足1211ijkk +-
34、，对21jP+的弗朗内特标架 222111,jjj+tnb进行旋转 ()222111,jjj+Rt n b得出 222111,jjj+tnb，若矩阵 T222 222111 111, ,jjj jjj+ +tnb tnb对角线数据绝对值满足弗朗内特判定条件，则1iP 与2jP建立匹配关系，记录骨架枝 A 与 B 中匹配点的数量 (),1Nij=；然后依次计算点1ikP+与2j kP+， k=2,3,的匹配情况，最后记录骨架枝 A 与 B 中所有匹配点的数量(),Nij = ，则该对骨架枝的相似度 ( ),M AB 如式(9)所示 ()(),ijijffMABf mfn+=+(9) 式中，if
35、、jf分别表示骨架枝 A、 B 的步长，m和n分别为骨架枝 A 和 B 的三维数据点数，为匹配点数量。 3.4 骨架形状相似度计算 两个骨架树 T1、 T2 形状相似度为两个骨架树中所有匹配对的两骨架枝的长度乘以该对骨架枝的相似度乘积之和，再除以两个骨架树所有骨架枝的长度总和，如式 (10)所示 12(,)( )Sim( 1, 2)ABTTM AB L LTTLL +=+(10) 式中，(,)M AB为两个骨架树 T1、 T2 的一对已匹配的骨架枝 A， B 的相似度，AL 和BL 分别为该匹配对骨架枝 A， B 的长度，12TTLL、 为两个骨架树的各自骨架枝长度总和。 如图 3 和图 6
36、所示模型一和模型二骨架的步长分别为 1.4 mm 和 1.3 mm。 在骨架树 T1 中子树1Ts 和2Ts 的所有骨架枝均为空间直线且相等，长度为11.20；环状骨架枝14 15SS 和16 17SS 相等，其周长为25.12；12 14 12 15 13 16 13 17SS SS SS SS、 均为空间直线且相等，长度为 5.66。同理， T2 中1Ts和2Ts 的所有骨 机 械 工 程 学 报 第 52 卷第 13 期 期 210 架枝均为空间直线且相等，长度为 10.40；环状骨架枝15 16SS与17 18SS相等，其周长为 31.40 ；415 416 417 418SS SS
37、SS SS 、 均为空间直线且相等，长度为 7.07。骨架枝03SS与04SS均为空间曲线且匹配，03SS的数据点为 14 个，04SS的数据点为 17 个，匹配点的数量为 11 ，则相似度为()()03 041.4 1.3 11,0.711.4 14 1.3 17MSSSS+=+。 在骨架树 T1 中剩余的312SS 和313SS ，长 度 均 为2.80；在骨架树 T2 中剩余的313SS和314SS长度均为3.90。 将以上数值代入式 (10)中，得到式 (11)12(,)( )Sim( 1, 2)10.4 25.12(8 10.4 8 11.2) (2 25.12 2 31.40) 0
38、.71(1.4 14 1.3 17)11.2 31.400.820(8 10.4 8 11.2) (2 25.12 2 31.40) (1.4 14 1.3 17 2 2.80 2 3.90ABTTMAB L LTTLL +=+ + + + + + =+ + + +）(11) 由式 (11)计算可知，模型一和模型二的形状相似度为 0.820。 4 实例验证 为验证本文算法的可行性，将模型一与自行开发的机械零件检索系统零件库中的零件进行相似性检索。检索分为两个阶段。第一阶段，将模型一与零件库中所有的零件 (近 500 个 )一一进行模型骨架拓扑结构相似性比较，即计算模型一与零件库中所有零件的邻接
39、矩阵特征值之和相差的数据 (简称拓扑误差 )， 将拓扑误差值从小到大排列后部分数据如表 1 所示。 表 1 第一阶段匹配结果 零件编号 0018 0034 0036 0176 0069 零件模型 模型骨架 拓扑误差 0.064 6 0.071 8 0.077 0 0.235 8 0.241 0 零件编号 0008 0013 0211 0410 0337 零件模型 模型骨架 拓扑误差 0.372 0 0.612 7 0.660 1 1.030 0 1.280 2 零件编号 0286 0119 0019 0038 0087 零件模型 (续 ) 模型骨架拓扑误差1.420 5 1.502 3 1.6
40、73 4 3.267 5 4.789 0 零件编号0445 0092 0124 0008 0096 零件模型模型骨架拓扑误差4.864 1 5.436 3 5.893 0 5.989 2 6.245 2 零件编号0476 0079 0450 0278 0369 零件模型模型骨架拓扑误差6.365 3 6.823 0 6.976 1 7.128 0 7.342 1 根据第一阶段的检索结果，零件库中零件编号为 0018、 0034、 0036、 0176、 0069 等与模型一在拓扑结构上相似程度较高；其他零件差距较大。若取前 10 个零件进行第二阶段检索， 则通过第一阶段检索淘汰掉大多数零件。表
41、 2 为第二阶段检索结果。 表 2 第二阶段匹配结果 零件编号 0018 0034 0036 0176 0069 零件模型 相似度 0.820 0.841 0.753 0.750 0.821 月 2016 年 7 月 朱文博等：基于骨架树的机械零件三维模型检索方法 211 (续 ) 零件编号 0008 0013 0211 0410 0337 零件模型 相似度 0.725 0.523 0.604 0.633 0.506 根据第二阶段检索的结果可知零件编号为0034 的零件在形状相似性上与模型一有最高的相似性，可借鉴 0034 号零件的设计成果。 5 试验分析 试验分析是将本文方法与基于典型面匹配
42、法2和基于递归分割法7从计算量和查准率 -查全率曲线 (P-R 曲线 )两方面进行对比。 计算量方面，本文算法分成两个阶段，第一阶段通过计算模型骨架树对应的邻接矩阵特征值之和来比较模型拓扑特征相似性，计算简洁，速度快。通过第一阶段的检索过滤掉大量与待匹配模型拓扑特征相差较大的模型，大大缩小了第二阶段的检索范围。第二阶段对形状特征进行匹配，由于机械零件多为规则图形，所生成骨架枝多由直线段、圆和圆弧组成，这些骨架枝的匹配算法简单有效，对于空间曲线骨架枝通过比较其上点的曲率和弗朗内特标架值来计算相似度值，虽然计算量较大，但是空间曲线骨架枝数量较少，因此本文算法总的计算耗时低。基于典型面匹配的机械零件
43、检索方法利用特定几何形状的分布函数进行实体模型的检索，该算法复杂程度不高，计算耗时比本文算法略高。基于递归分割法将实体进行分割， 建立有序的满二叉树，通过比较非根结点实体的相似度，获得零件三维模型相似度，复杂程度较高，计算耗时明显高于本文算法。本文使用第 4 节中所述自行开发的零件库近500 个零件作为测试数据库，在同一台计算机上采用 3 种算法检索同一个相似零件模型，所用的计算时间如表 3 所示。 表 3 检索相似零件计算时间 算法名称 本文算法 基于典型面匹配法 基于递归分割法耗时 /min 1.41 1.48 2.14 从表 3 中可以看出，本文算法计算量不大，计算耗时略低于基于典型面匹
44、配法，远低于基于递归分割法。 图 9 为本文算法与基于典型面匹配法和基于递归分割法的 P-R 曲线。由曲线图可以得出，综合考虑查准率和查全率，本文算法优于基于典型面匹配法，略低于基于递归分割法。在查全率为 0.2 时，基于典型面匹配法的查准率为 0.78，本文算法为0.80，基于递归分割法为 0.83。在查全率为 0.8 时，基于典型面匹配法的查准率仅为 0.22，本文算法为0.30，基于递归分割法为 0.29。 图 9 查准率 -查全率曲线图 考虑算法的计算耗时以及查准率和查全率两个方面，本文的算法计算量较低于基于典型面匹配法，查准率和查全率较优于基于典型面匹配法；基于递归分割法的查准率和查
45、全率优于本文算法，但其计算量较大，算法复杂程度较高。综合两个方面来说，本文算法具有较好的实用性。 6 结论 (1) 本文提出了一种基于骨架树的机械零件三维模型相似度算法，通过两个阶段完成零件模型检索。首先生成零件模型骨架，并转换成骨架树，根据骨架树构建邻接矩阵，邻接矩阵将零件模型骨架拓扑结构特征数值化，通过比较邻接矩阵特征值之和迅速完成零件拓扑结构匹配，实现零件的初步筛选。将大量与待匹配模型拓扑特征相差较大的模型过滤掉，极大地减少了第二阶段的匹配计算量。 (2) 第二阶段通过匹配骨架子树，进而匹配骨架枝来计算整个骨架的形状相似度。对于形状为空间曲线的骨架枝的匹配，采用空间离散曲线的曲率和弗朗内
46、特标架进行空间曲线相似性计算。将骨架枝相似度匹配转化成便于计算的点云空间曲线，无须求得骨架枝的曲线表达函数，对于任意形状的空间曲线均可使用，具有较高的准确性和有效性。 (3) 本算法第一阶段计算量小，方便快捷，第二阶段本身的计算量虽大， 但是仅在小范围内进行。通过实例验证和试验分析，综合考虑计算量和查准率 -查全率两方面， 本文的算法综合性能优于基于典型面匹配法和基于递归分割法。 机 械 工 程 学 报 第 52 卷第 13 期 期 212 参 考 文 献 1 AONO M， KOYANAGI H， TATSUMA A. 3D shape retrieval focused on holes
47、and surface roughnessC/ Proceedings of IEEE Signal and Information Processing Association Annual Summit and Conference (APSIPA)，2013： 1-8. 2 HU K， WANG B， GAO Y， et al. A face-based shape matching method for IGES surface modelC/ Proceedings of IEEE Shape Modeling International Conference (SMI)， 2010： 216-220. 3 IYER N， JAYANTI S， LOU K， et al. Shape-based searching for product lifecycle applications