基于广义变换矩阵的机械零件三维模型骨架匹配

（上海理工大学 机械工程学院，上海 200093）

设计零件时可以参考与之相似的零件，因此，如何在众多零件中准确快速检索到类似零件是一个重要命题。You等[1]基于边界表示法构建模型的属性图，表达模型的形状和拓扑结构，然后根据属性图找出模型之间的最大公共子图，提出了针对局部特征的三维模型检索方法。Cheng等[2]在模型表面计算随机两点间的距离获得三维模型几何特征的D2形状分布图，通过比较形状分布曲线的相似度得到模型的相似度，但随着计算的随机采样点达到一定数目时，外形特征不相似的模型也可能有大致相同的形状分布曲线。徐敬华等[3]提出了基于递归分割的机械零件三维形状结构检索方法，首先将机械零件归一化处理，然后递归实体分割建立有序的满二叉树，通过计算非根节点实体构建特征矢量之间的相似度，得到零件之间的相似度。董雁等[4]基于装配结构相似提出了一种零件检索方法，通过功能面邻接图和定性几何约束图定义零件装配结构定性模型，用符号对装配结构进行编码，利用装配结构码实现相似结构零件检索，这种方法侧重于机械零件之间的功能相似性。EI-Mehalawi等[5]提出了一种基于几何和拓扑相似度的三维机械零件检索方法，将零件模型转化为STEP格式，根据零件的结构数据来构造零件模型图，通过比较模型图的相似度来得到零件相似度，这种方法计算量较大。白静[6]提出基于扩展特征树的三维CAD模型相似评价方法，以三维CAD模型的边界表示为输入，通过交互定义设计特征及自动识别特征间关系的方法建立其扩展特征树，并通过非精确的树匹配算法及一种自适应的权重分配方案实现三维CAD模型间的相似评价。由于很难统一标准的特征树，因此，这种检索方法具有一定的局限性和主观性。Hajij等[7]基于Reeb图理论，将三维网格化的模型分割成若干个裤子结构，这种裤子结构的特点是：分割后的每个模型具有3个边界亏格为零且为可定向的表面。由于机械零件的三维模型很难分割成裤子结构，因此，这种方法很难应用于零件检索。李雷等[8]针对现有的曲线骨架提取方法不是很理想的现状，提出了一种新的曲线骨架提取方法。运用经典集合覆盖问题模型，对中值面进行优化形成中值图，根据中值图以收缩的方式生成曲线骨架，但这种方法只适用于类似于人体具有管状结构的模型。

针对机械零件模型骨架，借鉴机器人学中描述广义连杆之间关系的理论方法，本文提出一种基于广义变换矩阵的机械零件三维模型骨架匹配方法。对骨架枝建立广义变换矩阵，通过计算匹配矩阵的相似度得到骨架的相似度，进而得到机械零件三维模型的相似度。

1 机械零件模型骨架

要实现机械零件三维模型检索，首先需要将零件模型以一定方式进行表示，线性骨架是物体的一种降维表示，可以直观简洁地表示出机械零件三维模型的形状和拓扑结构。由于常见的机械零件模型表面主要由平面和相对规则的曲面组成，因此，所提取出的骨架可以看成由若干骨架点相连构成。本文将针对由骨架点构成的机械零件三维模型骨架，研究骨架的匹配计算。机械零件模型骨架可以根据文献[9]中所述的电场法来生成。首先对零件模型进行预处理，过滤掉零件模型上的一些附加特征，如螺纹、倒角及键槽等，然后假设模型表面均匀分布正电荷，根据物理静电学知识可知模型内部某点存在最小电势点，最小电势点的位置即为零件骨架的骨架点，连接相邻骨架点形成完整模型骨架。图1为根据文献[9]的方法所生成的模型骨架。

图1 提取模型 1 的骨架Fig.1 Extracting the skeleton of model one

2 骨架相似度计算

骨架体现零件模型的整体特征。本文将2个骨架点之间的连线称为骨架枝，整个骨架是由若干段骨架枝构成的。工业机器人学[10]中的机械手是由一系列的连杆组成的，骨架枝可以看成连杆，运用机械手的相关知识，相邻坐标间及其相应连杆可以用广义变换矩阵来表示。因此，骨架枝也可以通过广义变换矩阵来表示，通过计算广义变换矩阵的相似度得到骨架枝的相似度，从而找到相匹配的骨架枝，进而得到整个骨架的相似度。

2.1 构建骨架枝的 T 矩阵

建立机器人运动模型常用D-H（Denavit-Hartenberg）参数法[11]，这种方法能很好地表示出机械手连杆之间的位置形状信息。根据机械手连杆的相关知识，为每一个连杆建立一个坐标系，描述一个连杆坐标系与下一个连杆坐标系间相对关系的齐次变换矩阵称为A矩阵，2个或2个以上的A矩阵的乘积，表示连杆相对于固定坐标系位姿，称为T矩阵。将这一理论运用到骨架枝相互关系的建立上，构建骨架枝的T矩阵。

骨架由若干个骨架点（G0，G1，G2，···，Gn）构成，设模型的质心为O点 ，将最靠近O点的骨架点记为G0，与G0相邻的骨架点记为G1（与G0相邻的骨架点，可能不止一个，任意指定其中之一为G1点，只要G0和G1的连线是骨架枝即可）。首先建立固定坐标系，记为{0}，建立的方法为：以G0为原点建立笛卡尔直角坐标系，模型的最小包络长方体的最大边长与y0轴平行，最小边长与z0轴平行，中间大小的边长与x0轴平行，如果零件的最小包络长方体某两条，甚至三条边长度相等，则任选其中一条边与坐标轴平行。建立骨架枝的坐标系{1}，建立的方法为：仍然以G0为原点，即坐标系{0}和{1}原点相同，骨架枝为x1轴，方向由G0指向G1，根据右手直角坐标系法则确定y1轴的方向和z1轴的方向。再以G1点为原点建立骨架枝的坐标系{2}，骨架枝为x2轴，方向由G1指向G2，根据右手直角坐标系法则确定y2轴的方向和z2轴的方向。依此类推，在每个骨架点处建立一个坐标系，也就是对每个骨架枝建立了一个坐标系。一个骨架枝坐标系相对于下一个骨架枝坐标系间相对关系的广义变换Ai矩阵[10]为

式中：i=1,2,···,m，m为 骨架枝数；bi-1表示沿着xi-1轴，从zi-1轴移动到zi轴的距离；αi-1表示绕着xi-1轴，从zi-1轴旋转到zi轴的角度；di表示沿着zi轴，从xi-1轴移动到xi轴的距离；θi表示绕着zi轴，从xi-1轴旋转到xi的角度。

A1矩阵表示骨架枝的坐标系{1}相对于固定坐标系{0}的位姿，A2矩阵表示骨架枝的坐标系{2}相对于坐标系{1}的位姿，那么，坐标系{2}相对于固定坐标系{0}的位姿可用A1和A2的乘积，用T2来表示。

同理，A3矩阵表示坐标系{3}相对于{2}的位姿，则{3}相对于{0}的位姿为

依此类推，建立每一个骨架枝相对于固定坐标系{0}的T矩阵。

图2是图1所示模型1的骨架和坐标系图。G0点是最靠近质心的骨架点，其他各点依次标注为G1，G2，···，G12，共13个骨架点；，共13个骨架枝。以G0为原点建立固定坐标系{0}，模型1的最小包络长方体的最大边长与y0轴平行，最小边长与z0轴平行（z0轴垂直纸面向外），中间大小的边长与x0轴平行。建立骨架枝的坐标系{1}，仍然以G0为原点，骨架枝为x1轴，方向由G0指向G1，根据右手直角坐标系法则确定y1轴的方向和z1轴的方向。再以G1点为原点建立骨架枝的坐标系{2}，骨架枝为x2轴，方向由G1指向G2，根据右手直角坐标系法则确定y2轴的方向和z2轴的方向。所有z轴均垂直纸面向外，为简化图形，未画出。依次类推，在每个骨架点处建立坐标系，也就是对每个骨架枝建立了一个坐标系。

图2 模型 1 的骨架及坐标系Fig.2 Skeleton and coordinate system of model one

根据式（1）计算A1矩阵。b0是沿着x0轴，从z0轴移动到z1轴的距离，为0；α0是绕着x0轴，从z0轴旋转到z1轴的角度，为0；d1表示沿着z1轴，从x0轴移动到x1轴的距离，为0；θ1表示绕着z1轴，从x0轴旋转到x1的角度，为75.000°。将这些数值代入式（1）中，得到式（4）。

因为，A1矩阵表示骨架枝的坐标系{1}相对于固定坐标系{0}的位姿，所以，A1=T1。

根据式（1）计算A2矩阵。b1是沿着x1轴，从z1轴移动到z2轴的距离，为12.000；α1是绕着x1轴，从z1轴旋转到z2轴的角度，为0；d2表示沿着z2轴，从x1轴移动到x2轴的距离，为0；θ2表示绕着z2轴，从x1轴旋转到x2的角度，为-11.300°。将这些数值代入式（1）中，得到式（5）。

A2矩阵表示骨架枝的坐标系{2}相对于骨架枝坐标系{1}的位姿，所以，坐标系{2}相对于固定坐标系{0}的位姿按式（2）计算。

同理，计算A3和T3，A4和T4，···，A13和T13，完成每一个骨架枝的T矩阵计算。需要说明的是，若骨架枝回到原点时如何处理的问题。如图2所示，骨架枝回到G0点，则A8矩阵表示骨架枝的坐标系{8}相对于骨架枝坐标系{7}的位姿，T8=A1A2A3A4A5A6A7A8=T7A8表示坐标系{8}相对于固定坐标系{0}的位姿。而骨架枝构建A9矩阵时要相对于固定坐标系{0}，即A9矩阵表示骨架枝的坐标系{9}相对于{0}的位姿，所以，A9=T9。

2.2 计算 T矩阵的相似度

为了计算T矩阵的相似度，将4×4的T矩阵转化成一个16维的向量，记为TR，可采用Matlab中的reshape函数reshape(T,1,16)来实现[12]，即TR按T矩阵的列依次取数据生成，如式（7）所示。设

将T矩阵转化为向量TR后，引用统计学中的相关性度量方法，通过计算2个向量的皮尔逊相关系数[13]就可以得到2个T矩阵的相似度sim(Tn,Tm)。

式中：Tn和Tm表示2个T矩阵；TRn是由Tn矩阵按式（7）生成的一维向量：Rn是Tn生成向量中所有元素的平均值；TRm是由Tm生成的向量；Rm是Tm生成向量中所有元素的平均值；TRni为TRn的一个元素；TRmi为TRm的一个元素。

2.3 搜索匹配 T矩阵

设骨架P有p个骨架枝，则构建了p个T矩阵，按照式（7）生成了相应的p个TR向量。同理，另一骨架Q有q个 骨架枝，则构建了q个T矩阵，生成了相应的q个TR向 量，p个TR向 量和q个TR向量两两间根据式（8）进行计算，得到p×q对相似度值，搜索得到min(p,q)对匹配向量，即找到min(p,q)对匹配的T矩阵。搜索方法的步骤：

步骤1将p×q对相似度值从高到低排列，存放在临时数据表1中。

表1 临时数据表Tab.1 Temporary data table

步骤2取表1中第一行，即找到一对匹配T矩阵(Tn,Tm)，放在一张新表中（结构同表1）；然后删除表1中所有包含Tn和Tm的行。

步骤3重复步骤2，直到表1为空。这样就找到了min(p,q)对匹配T矩阵，并被记录在新表中。

图3为模型2的骨架及其坐标系，共有7个骨架枝，每一骨架枝构建一个T矩阵，分别为。

图3 模型 2 的骨架及其坐标系Fig.3 Skeleton of model two and its coordinate system

将模型1和模型2的T矩阵两两进行相似度计算，搜索匹配对。例如，模型1的骨架枝和模型2的骨架枝构建的矩阵T9和分别为

根据式（7），

2.4 计算骨架相似度

找到相匹配的T矩阵，就是找到了匹配的骨架枝，2个骨架P和Q的相似度sim(P,Q)为：分子是相匹配的2个骨架枝T矩阵的相似度乘以该对骨架枝的长度，并计算所有匹配对的乘积之和，分母为个骨架所有骨架枝的长度总和，如式（9）所示。

式中：Tn和Tm代表上面计算出的相匹配的T矩阵对；sim(Tn,Tm)是其相似度值；Ln和Lm代表各自的骨架枝长度，共有min(p,q)对；LP表示骨架P所有骨架枝的长度总和；LQ表示骨架Q所有骨架枝的长度总和。

图2和图3中模型1骨架和模型2骨架的骨架枝总长分别为257，184。相匹配的骨架枝长度分别为：L7=20，L1′=10，L2=10，L2′=29，L9=33，L3′=29，L10=31，L4′=34，L11=43，L5′=37，L12=34，L6′=38，L13=7，L7′=7。代入式（9）中，可得两骨架相似度

3 实例验证

为了验证本文算法的可行性和准确性，将图1示例零件与自行开发的检索系统中的机械零件进行匹配。测试数据库已按照轴套类、轮盘盖类、叉架类、箱体类这4大类零件分类。图1示例零件属于叉架类，故在叉架类零件子集中进行匹配。表2为相似度数值从大到小排列的前20个机械零件。

根据检索结果可知，表2中0056号机械零件与图1示例模型1的相似度最高，此零件与图1模型1在结构和功能上有很大的相似性，因此，模型1在加工制造等方面完全可以借鉴0056号机械零件相应的制造工艺。从表2中也可以看出，0326号正是图3模型2，它与图1所示模型1相似度为0.760。

表2 图1 示例零件的检索结果Tab.2 Retrieval results for the sample part of figure 1

4 实验分析

为了验证本文算法的有效性和检索效率，将本文算法、D2形状分布算法[2]和基于递归分割算法[3]从计算量和查准率-查全率曲线（P-R曲线）两方面进行对比。本算法的实验平台为Inte(R)Core(TM)i5-8250UCPU@1.60GHz1.80GHz，内存 8GB的华为 PC 机以及 Visual Studio 2010，SolidWorks 2016软件环境，以前面所述的机械零件库作为测试数据库。

在计算量上，由于大多数机械零件形状相对规则，骨架枝的数量并不多，因此，计算骨架枝所对应的T矩阵相似度的计算量较小。基于递归分割算法首先将零件实体分割，然后建立有序的满二叉树，比较非根节点实体的相似度，得到零件的相似度，计算量明显较大。本文算法的计算量小于基于递归分割算法。D2形状分布算法只考虑单一特征的表面随机样点间的距离，计算量最小。在本文所述实验平台的基础上，采用上述3种算法检索同一个机械零件模型所需时间如表3所示。

表3 检索相似零件耗时量Tab.3 Time-consuming of retrieving similar parts

查准率-查全率曲线是评判检索系统准确性的重要手段。图4是上述3种算法的P-R曲线，可以看出，在查全率为0.3时，本文算法的查准率为0.63，基于递归分割算法的查准率为0.69，D2形状分布算法的查准率只有0.25。当查全率上升到0.7时，本文算法的查准率为0.36，基于递归分割算法的查准率为0.32，D2算法的查准率只有0.08。可以看出，本文算法的查准率-查全率均优于D2形状分布算法；当查全率低于0.55时，本文算法的查准率略低于基于递归分割算法，但是，当查全率高于0.55时，本文算法的查准率略高于基于递归分割算法。

图4 查准率-查全率曲线图Fig.4 Accuracy-recall curve

综合考虑计算量和查准率-查全率两个方面可以看出，本文算法在机械零件检索方面有一定优势。虽然计算速度略低于D2形状分布算法，但是，P-R曲线性能明显好于D2形状分布算法；本文算法与基于递归分割算法的P-R曲线有交叉，各自在某一范围有一定的优势，但是，本文算法的计算速度明显优于基于递归分割算法。综上所述，本文算法具有较好的实用性。

5 结 论

a.借鉴机器人学中描述广义连杆之间关系的理论方法，将机械零件骨架枝看成连杆，在骨架点处建立固定坐标系及骨架枝坐标系，构建骨架枝的广义变换T矩阵。

b.将4×4的T矩阵转化成16维的向量，通过计算2个向量的皮尔逊相关系数得到2个T矩阵的相似度，即得到2个骨架枝的相似度；搜索到相匹配的骨架枝后，计算整个骨架的相似度。

c.本文提出的匹配算法不仅适用于基于电场法建立的骨架，而且对其他方式建立的骨架，只要存在骨架点和骨架枝都具有适用性。通过实例验证和实验分析，综合考虑计算量和查准率-查全率两方面，本文算法高效、准确，综合性能优于D2形状分布算法和基于递归分割算法。