上海理工大学学报  2019, Vol. 41 Issue (4): 381-387   PDF    
基于广义变换矩阵的机械零件三维模型骨架匹配
朱文博, 杨超, 甘屹, 陈龙     
上海理工大学 机械工程学院,上海 200093
摘要: 提出了一种基于广义变换矩阵的机械零件三维模型骨架匹配方法。骨架中两骨架点间的连线称为骨架枝,借鉴机器人学中广义连杆之间关系的表示方法,将骨架枝看成若干个连杆,在骨架点处建立固定坐标系及骨架枝坐标系,采用广义变换矩阵表示骨架枝。将广义变换矩阵转化成向量,引用统计学中的相关性度量方法,通过计算2个向量的皮尔逊相关系数得到2个广义变换矩阵的相似度,即得到2个骨架枝的相似度。搜索相匹配的骨架枝并计算整个骨架的相似度。通过实例验证和实验分析,表明该算法具有较快的检索速度和较高的准确度。
关键词: 机械零件     三维模型     骨架     广义变换矩阵     皮尔逊相关系数     相似度    
3D Model Skeleton Matching of Mechanical Parts Based on Generalized Transform Matrix
ZHU Wenbo, YANG Chao, GAN Yi, CHEN Long     
School of Mechanical Engineering, University of Shanghai for Science and Technology, Shanghai 200093, China
Abstract: A skeleton matching method for 3D models of mechanical parts based on generalized transformation matrix was proposed. The connection line between the two skeleton points is called the skeleton branch. Referring to the representation method of the relationship between the generalized connecting rods in the robotics, the skeleton branches are regarded as a number of connecting rods. A fixed coordinate system and a skeleton coordinate system are established at the skeleton point. The skeleton branch is represented by the generalized transformation matrix. The generalized transformation matrix is transformed into a vector. Referring to the method of correlation measurement in statistics, the similarity degree of the two generalized transformation matrices was obtained by calculating the Pearson correlation coefficients of two vectors, that is, the similarity degree of the two skeleton branches. Search the matching skeleton branches and calculate the similarity of the whole skeleton. Through the example verification and experimental analysis, the algorithm has a fast retrieval speed and good accuracy.
Key words: mechanical parts     3D model     skeleton     generalized transformation matrix     Pearson correlation coefficient     similarity degree    

设计零件时可以参考与之相似的零件,因此,如何在众多零件中准确快速检索到类似零件是一个重要命题。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}}$ 矩阵。

骨架由若干个骨架点( ${G_0}$ ${G_1}$ ${G_2}$ ,··· , ${G_n}$ )构成,设模型的质心为 $O$ 点,将最靠近 $O$ 点的骨架点记为 ${G_0}$ ,与 ${G_0}$ 相邻的骨架点记为 ${G_1}$ (与 ${G_0}$ 相邻的骨架点,可能不止一个,任意指定其中之一为 ${G_1}$ 点,只要 ${G_0}$ ${G_1}$ 的连线 $\overline {{G_0}{G_1}} $ 是骨架枝即可)。首先建立固定坐标系,记为 $\left\{ {\rm{0}} \right\}$ ,建立的方法为:以 ${G_0}$ 为原点建立笛卡尔直角坐标系,模型的最小包络长方体的最大边长与 ${y_0}$ 轴平行,最小边长与 ${z_0}$ 轴平行,中间大小的边长与 ${x_0}$ 轴平行,如果零件的最小包络长方体某两条,甚至三条边长度相等,则任选其中一条边与坐标轴平行。建立骨架枝 $\overline {{G_0}{G_1}} $ 的坐标系 $\left\{ {\rm{1}} \right\}$ ,建立的方法为:仍然以 ${G_0}$ 为原点,即坐标系 $\left\{ {\rm{0}} \right\}$ $\left\{ {\rm{1}} \right\}$ 原点相同,骨架枝 $\overline {{G_0}{G_1}} $ ${x_{\rm{1}}}$ 轴,方向由 ${G_0}$ 指向 ${G_1}$ ,根据右手直角坐标系法则确定 ${y_1}$ 轴的方向和 ${z_{\rm{1}}}$ 轴的方向。再以 ${G_1}$ 点为原点建立骨架枝 $\overline {{G_1}{G_2}} $ 的坐标系 $\left\{ 2 \right\}$ ,骨架枝 $\overline {{G_1}{G_2}} $ ${x_2}$ 轴,方向由 ${G_1}$ 指向 ${G_2}$ ,根据右手直角坐标系法则确定 ${y_2}$ 轴的方向和 ${z_2}$ 轴的方向。依此类推,在每个骨架点处建立一个坐标系,也就是对每个骨架枝建立了一个坐标系。一个骨架枝坐标系相对于下一个骨架枝坐标系间相对关系的广义变换 ${{ A}_i}$ 矩阵[10]

${{{A}}_i} = \left[ {\begin{array}{*{20}{c}} {\cos\; {\theta _i}}&{ - \sin\; {\theta _i}}&0&{{b_{i - 1}}} \\ {\sin\; {\theta _i}\cos\; {\alpha _{i - 1}}}&{\cos\; {\theta _i}\cos\; {\alpha _{i - 1}}}&{ - \sin\; {\alpha _{i - 1}}}&{ - {d_i}\sin\; {\alpha _{i - 1}}} \\ {\sin\; {\theta _i}\sin\; {\alpha _{i - 1}}}&{\cos\; {\theta _i}\sin\; {\alpha _{i - 1}}}&{\cos\; {\alpha _{i - 1}}}&{{d_i}\cos\; {\alpha _{i - 1}}} \\ 0&0&0&1 \end{array}} \right]$ (1)

式中: $i = 1,2, \cdots ,m$ $m$ 为骨架枝数; ${b_{i - 1}}$ 表示沿着 ${x_{i - 1}}$ 轴,从 ${z_{i - 1}}$ 轴移动到 ${z_i}$ 轴的距离; ${\alpha _{i - 1}}$ 表示绕着 ${x_{i - 1}}$ 轴,从 ${z_{i - 1}}$ 轴旋转到 ${z_i}$ 轴的角度; ${d_i}$ 表示沿着 ${z_i}$ 轴,从 ${x_{i - 1}}$ 轴移动到 ${x_i}$ 轴的距离; ${\theta _i}$ 表示绕着 ${z_i}$ 轴,从 ${x_{i - 1}}$ 轴旋转到 ${x_i}$ 的角度。

${{{A}}_1}$ 矩阵表示骨架枝 $\overline {{G_0}{G_1}} $ 的坐标系 $\left\{ {\rm{1}} \right\}$ 相对于固定坐标系 $\left\{ {\rm{0}} \right\}$ 的位姿, ${{{A}}_2}$ 矩阵表示骨架枝 $\overline {{G_1}{G_2}} $ 的坐标系 $\left\{ 2 \right\}$ 相对于坐标系 $\left\{ {\rm{1}} \right\}$ 的位姿,那么,坐标系 $\left\{ 2 \right\}$ 相对于固定坐标系 $\left\{ {\rm{0}} \right\}$ 的位姿可用 ${{{A}}_1}$ ${{{A}}_2}$ 的乘积,用 ${{{T}}_2}$ 来表示。

${{{T}}_2} = {{{A}}_1}{{{A}}_2}$ (2)

同理, ${{{A}}_3}$ 矩阵表示坐标系 $\left\{ 3 \right\}$ 相对于 $\left\{ 2 \right\}$ 的位姿,则 $\left\{ 3 \right\}$ 相对于 $\left\{ {\rm{0}} \right\}$ 的位姿为

${{{T}}_3} = {{{A}}_1}{{{A}}_2}{{{A}}_3} = {{{T}}_2}{{{A}}_3}$ (3)

依此类推,建立每一个骨架枝相对于固定坐标系 $\left\{ {\rm{0}} \right\}$ ${{T}}$ 矩阵。

图2图1所示模型1的骨架和坐标系图。 ${G_0}$ 点是最靠近质心的骨架点,其他各点依次标注为 ${G_1}$ ${G_2}$ ,···, ${G_{12}}$ ,共13个骨架点; $\overline {{G_0}{G_1}} $ $\overline {{G_1}{G_2}} $ ,···, $\overline {{G_{11}}{G_{12}}} $ ,共13个骨架枝。以 ${G_0}$ 为原点建立固定坐标系 $\left\{ {\rm{0}} \right\}$ ,模型1的最小包络长方体的最大边长与 ${y_0}$ 轴平行,最小边长与 ${z_0}$ 轴平行( ${z_0}$ 轴垂直纸面向外),中间大小的边长与 ${x_0}$ 轴平行。建立骨架枝 $\overline {{G_0}{G_1}} $ 的坐标系 $\left\{ {\rm{1}} \right\}$ ,仍然以 ${G_0}$ 为原点,骨架枝 $\overline {{G_0}{G_1}} $ ${x_{\rm{1}}}$ 轴,方向由 ${G_0}$ 指向 ${G_1}$ ,根据右手直角坐标系法则确定 ${y_1}$ 轴的方向和 ${z_{\rm{1}}}$ 轴的方向。再以 ${G_1}$ 点为原点建立骨架枝 $\overline {{G_1}{G_2}} $ 的坐标系 $\left\{ 2 \right\}$ ,骨架枝 $\overline {{G_1}{G_2}} $ ${x_2}$ 轴,方向由 ${G_1}$ 指向 ${G_2}$ ,根据右手直角坐标系法则确定 ${y_2}$ 轴的方向和 ${z_2}$ 轴的方向。所有 $z$ 轴均垂直纸面向外,为简化图形,未画出。依次类推,在每个骨架点处建立坐标系,也就是对每个骨架枝建立了一个坐标系。


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

根据式(1)计算 ${{{A}}_1}$ 矩阵。 ${b_0}$ 是沿着 ${x_0}$ 轴,从 ${z_0}$ 轴移动到 ${z_1}$ 轴的距离,为0; ${\alpha _0}$ 是绕着 ${x_0}$ 轴,从 ${z_0}$ 轴旋转到 ${z_1}$ 轴的角度,为0; ${d_1}$ 表示沿着 ${z_1}$ 轴,从 ${x_0}$ 轴移动到 ${x_1}$ 轴的距离,为0; ${\theta _{\rm{1}}}$ 表示绕着 ${z_1}$ 轴,从 ${x_0}$ 轴旋转到 ${x_1}$ 的角度,为75.000 °。将这些数值代入式(1)中,得到式(4)。

$\qquad\quad{{{A}}_1} = \left[ {\begin{array}{*{20}{c}} {{\rm{0}}{\rm{.259}}}&{{\rm{ - 0}}{\rm{.966}}}&{\rm{0}}&{\rm{0}} \\ {{\rm{0}}{\rm{.966}}}&\;\;\;{{\rm{0}}{\rm{.259}}}&{\rm{0}}&{\rm{0}} \\ {\rm{0}}&{\rm{0}}&{{\rm{1}}{\rm{.000}}}&{\rm{0}} \\ {\rm{0}}&{\rm{0}}&{\rm{0}}&{{\rm{1}}{\rm{.000}}} \end{array}} \right]$ (4)

因为, ${{{A}}_1}$ 矩阵表示骨架枝 $\overline {{G_0}{G_1}} $ 的坐标系 $\left\{ {\rm{1}} \right\}$ 相对于固定坐标系 $\left\{ {\rm{0}} \right\}$ 的位姿,所以, ${{{A}}_1} = {{{T}}_1}$

根据式(1)计算 ${{{A}}_2}$ 矩阵。 ${b_1}$ 是沿着 ${x_1}$ 轴,从 ${z_1}$ 轴移动到 ${z_2}$ 轴的距离,为12.000; ${\alpha _1}$ 是绕着 ${x_1}$ 轴,从 ${z_1}$ 轴旋转到 ${z_2}$ 轴的角度,为0; ${d_2}$ 表示沿着 ${z_2}$ 轴,从 ${x_1}$ 轴移动到 ${x_2}$ 轴的距离,为0; ${\theta _{\rm{2}}}$ 表示绕着 ${z_2}$ 轴,从 ${x_1}$ 轴旋转到 ${x_2}$ 的角度,为–11.300 °。将这些数值代入式(1)中,得到式(5)。

$\qquad\;\;{{{A}}_{\rm{2}}} = \left[ {\begin{array}{*{20}{c}} {{\rm{0}}{\rm{.982}}}&{{\rm{ - 0}}{\rm{.191}}}&{\rm{0}}&{{\rm{12}}{\rm{.000}}} \\ {{\rm{0}}{\rm{.191}}}&\;\;\;{{\rm{0}}{\rm{.982}}}&{\rm{0}}&{\rm{0}} \\ {\rm{0}}&{\rm{0}}&{{\rm{1}}{\rm{.000}}}&{\rm{0}} \\ {\rm{0}}&{\rm{0}}&{\rm{0}}&\;\;\,{{\rm{1}}{\rm{.000}}} \end{array}} \right]$ (5)

${{{A}}_2}$ 矩阵表示骨架枝 $\overline {{G_1}{G_2}} $ 的坐标系 $\left\{ 2 \right\}$ 相对于骨架枝 $\overline {{G_0}{G_1}} $ 坐标系 $\left\{ {\rm{1}} \right\}$ 的位姿,所以,坐标系 $\left\{ 2 \right\}$ 相对于固定坐标系 $\left\{ {\rm{0}} \right\}$ 的位姿按式(2)计算。

${{{T}}_2} = {{{A}}_1}{{{A}}_2} = \left[ {\begin{array}{*{20}{c}} {0.070}&{{\rm{ - 0}}{\rm{.998}}}&{\rm{0}}&{{\rm{3}}{\rm{.108}}} \\ {{\rm{0}}{\rm{.998}}}&\;\;\;{{\rm{0}}{\rm{.070}}}&{\rm{0}}&\!\!\!{11.592} \\ {\rm{0}}&{\rm{0}}&{{\rm{1}}{\rm{.000}}}&{\rm{0}} \\ {\rm{0}}&{\rm{0}}&{\rm{0}}&{{\rm{1}}{\rm{.000}}} \end{array}} \right]\!\!\!\!\!\!\!\!$ (6)

同理,计算 ${{{A}}_3}$ ${{{T}}_3}$ ${{{A}}_4}$ ${{{T}}_4}$ ,···, ${ A}_{13}$ ${{{T}}_{13}}$ ,完成每一个骨架枝的 ${{T}}$ 矩阵计算。需要说明的是,若骨架枝回到原点时如何处理的问题。如图2所示,骨架枝 $\overline {{G_7}{G_0}} $ 回到 ${G_0}$ 点,则 ${{{A}}_8}$ 矩阵表示骨架枝 $\overline {{G_7}{G_0}} $ 的坐标系 $\left\{ 8 \right\}$ 相对于骨架枝 $\overline {{G_6}{G_7}} $ 坐标系 $\left\{ 7 \right\}$ 的位姿, ${{{T}}_8} = {{{A}}_1}{{{A}}_2}{{{A}}_3}{{{A}}_4}{{{A}}_5}{{{A}}_6}{{{A}}_7}{{{A}}_8} = {{{T}}_7}{{{A}}_8}$ 表示坐标系 $\left\{ 8 \right\}$ 相对于固定坐标系 $\left\{ {\rm{0}} \right\}$ 的位姿。而骨架枝 $\overline {{G_0}{G_8}} $ 构建 ${{ A}_9}$ 矩阵时要相对于固定坐标系 $\left\{ {\rm{0}} \right\}$ ,即 ${{ A}_9}$ 矩阵表示骨架枝 $\overline {{G_0}{G_8}} $ 的坐标系 $\left\{ 9 \right\}$ 相对于 $\left\{ {\rm{0}} \right\}$ 的位姿,所以, ${{{A}}_9} = {{{T}}_9}$

2.2 计算 ${{T}}$ 矩阵的相似度

为了计算 ${{T}}$ 矩阵的相似度,将 $4 \times 4$ ${{T}}$ 矩阵转化成一个16维的向量,记为 ${ T}_{\rm R}$ ,可采用Matlab中的reshape函数 ${\rm {reshape}}\;({{T}},1,16)$ 来实现[12],即 ${ T}_{\rm R}$ ${{T}}$ 矩阵的列依次取数据生成,如式(7)所示。设

$ {{{T}} = \left[ {\begin{array}{*{20}{c}} {{t_1}}&{{t_2}}&{{t_3}}&{{t_4}}\\ {{t_5}}&{{t_6}}&{{t_7}}&{{t_8}}\\ {{t_9}}&{{t_{10}}}&{{t_{11}}}&{{t_{12}}}\\ {{t_{13}}}&{{t_{14}}}&{{t_{15}}}&{{t_{16}}} \end{array}} \right]} $

$ { T}_{\rm R} = \left[ {{t_1},{t_5},{t_9},{t_{13}},{t_2},{t_6}, \cdots ,{t_{16}}} \right] $ (7)

${{T}}$ 矩阵转化为向量 ${ T}_{\rm R}$ 后,引用统计学中的相关性度量方法,通过计算2个向量的皮尔逊相关系数[13]就可以得到2个 ${{T}}$ 矩阵的相似度 $sim({{ T}_n},{{ T}_m})$

$sim({{{T}}_n},{{{T}}_m}) \!=\! \frac{{\displaystyle\sum\limits_{i = 1}^{16} {(T_{\rm{Rni}} - \overline {T}_{\rm{Rn}} )(T_{\rm{Rmi}} - \overline {T}_{\rm{Rm}} )} }}{{\sqrt {\displaystyle\sum\limits_{i = 1}^{16} {{{(T_{\rm{Rni}}\!\! -\!\! \overline {T}_{\rm{Rn}} )}^2}} }\!\!\!\! \sqrt {\displaystyle\sum\limits_{i = 1}^{16} {{{(T_{\rm{Rmi}} \!\!-\!\! \overline {T}_{\rm{Rm}} )}^2}} } }}\!\!\!\!\!\!\!\!\!\!\!$ (8)

式中: ${{{T}}_n}$ ${{{T}}_m}$ 表示2个 ${{T}}$ 矩阵; ${{T}}_{\rm{Rn}}$ 是由 ${{{T}}_n}$ 矩阵按式(7)生成的一维向量: $\overline {{{T}}}_{\rm{Rn}} $ ${{{T}}_n}$ 生成向量中所有元素的平均值; ${{T}}_{\rm{Rm}}$ 是由 ${{{T}}_m}$ 生成的向量; $\overline {{{T}}}_{\rm{Rm}} $ ${{{T}}_m}$ 生成向量中所有元素的平均值; ${ T}_{\rm{Rni}} $ ${ T}_{\rm{Rn}} $ 的一个元素; ${ T}_{\rm{Rmi}} $ ${ T}_{\rm{Rm}} $ 的一个元素。

2.3 搜索匹配 ${{T}}$ 矩阵

设骨架 $P$ $p$ 个骨架枝,则构建了 $p$ ${{T}}$ 矩阵,按照式(7)生成了相应的 $p$ ${{T}}_{\rm{R}}$ 向量。同理,另一骨架 $Q$ $q$ 个骨架枝,则构建了 $q$ ${{T}}$ 矩阵,生成了相应的 $q$ ${{T}}_{\rm{R}}$ 向量, $p$ ${{T}}_{\rm{R}}$ 向量和 $q$ ${{T}}_{\rm{R}}$ 向量两两间根据式(8)进行计算,得到 $p \times q$ 对相似度值,搜索得到 $\min \left( {p,q} \right)$ 对匹配向量,即找到 $\min \left( {p,q} \right)$ 对匹配的 ${{T}}$ 矩阵。搜索方法的步骤:

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


表 1 临时数据表 Table 1 Temporary data table

步骤2  取表1中第一行,即找到一对匹配 ${{T}}$ 矩阵 $({{T}}_n,{{T}}_m)$ ,放在一张新表中(结构同表1);然后删除表1中所有包含 ${{T}}_n$ ${{T}}_m$ 的行。

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

图3为模型2的骨架及其坐标系,共有7个骨架枝,每一骨架枝构建一个 ${{T}}$ 矩阵,分别为 ${{{T}}'_{\rm{1}}}$ ${{{T}}'_{\rm{2}}}$ ,··· , ${{T}}_7'$


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

将模型1和模型2的 ${{T}}$ 矩阵两两进行相似度计算,搜索匹配对。例如,模型1的骨架枝 $\overline {{G_0}{G_8}} $ 和模型2的骨架枝 $\overline {G_0'G_3'} $ 构建的矩阵 ${{{T}}_9}$ ${{{T}}'_{\rm{3}}}$ 分别为

$\begin{array}{l} {{{T}}_9} = \left[ {\begin{array}{*{20}{c}} \;\;\;{0.588}&{0.809}&0&0\\ { - 0.809}&{0.588}&0&0\\ 0&0&{1.000}&0\\ 0&0&0&{1.000} \end{array}} \right]\\ {{{{T}}'}_3} = \left[ {\begin{array}{*{20}{c}} \;\;\;{{\rm{0}}.{\rm{643}}}&{{\rm{0}}.{\rm{766}}}&{\rm{0}}&{\rm{0}}\\ {{\rm{ - 0}}.{\rm{766}}}&{{\rm{0}}.{\rm{634}}}&{\rm{0}}&{\rm{0}}\\ {\rm{0}}&{\rm{0}}&{{\rm{1}}.{\rm{000}}}&{\rm{0}}\\ {\rm{0}}&{\rm{0}}&{\rm{0}}&{{\rm{1}}.{\rm{000}}} \end{array}} \right] \end{array}$

根据式(7),

  ${{T}}_{{\rm{R}}9} = \left[ {0.588, - 0.809,0,0,0.809,\cdots,1.000} \right]$

  ${{T}}_{{\rm{R}}3}' = \left[ {0.643, - 0.766,0,0,0.766,\cdots,1.000} \right]$

代入式(8),计算得

$\begin{split} &\!\!\quad sim({{T}}_n,{{T}}_m) \!=\! \frac{{\displaystyle\sum\limits_{i = 1}^n {({{{T}}_{{\rm{Rni}}}} \!-\! \overline {{T}}_{{\rm{Rn}}} )({{{T}}_{{\rm{Rmi}}}} \!-\! \overline {{T}}_{{\rm{Rm}}} )} }}{{\sqrt {\displaystyle\sum\limits_{i = 1}^n {{{({{{T}}_{{\rm{Rni}}}} \!-\! \overline {{T}}_{{\rm{Rn}}} )}^2}} } \sqrt {\displaystyle\sum\limits_{i = 1}^n {{{({{{T}}_{{\rm{Rmi}}}} \!-\! \overline {{T}}_{{\rm{Rm}}} )}^2}} } }} =\qquad\qquad\qquad\\ &\!\! \qquad \frac{{{\rm{3}}.{\rm{138}}}}{{{\rm{1}}.{\rm{896}} \times {\rm{1}}.{\rm{896}}}} \!= {\rm{0}}.{\rm{873}} \end{split} $

同理,计算其他 ${{T}}$ 矩阵的相似性,一共算出 $13 \times 7 = 91$ 对相似度值,并按3个步骤搜索出7对匹配对: ${{{T}}_{\rm{7}}}$ ${{{T}}'_{\rm{1}}}$ ${{{T}}_{\rm{2}}}$ ${{{T}}'_{\rm{2}}}$ ${{{T}}_9}$ ${{T}}_3'$ ${{{T}}_{10}}$ ${{T}}_4'$ ${{{T}}_{11}}$ ${{T}}_5'$ ${{{T}}_{12}}$ ${{T}}_6'$ ${{{T}}_{13}}$ ${{T}}_7'$ 的相似度分别为0.754,0.672,0.873,0.964,0.935,0.986,1.000。

2.4 计算骨架相似度

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

$sim(P,Q) = \frac{{\displaystyle\sum\limits_{i = 1}^{\min (p,q)} {sim\left( {{T}}_n,{{T}}_m \right)} {\text{·}} \left( {{L_n} + {L_m}} \right)}}{{{L_P} + {L_Q}}}$ (9)

式中: ${{ T}_n}$ ${{ T}_m}$ 代表上面计算出的相匹配的 ${{T}}$ 矩阵对; $sim({{{T}}_n},{{{T}}_m})$ 是其相似度值; ${L_n}$ ${L_m}$ 代表各自的骨架枝长度,共有 $\min \left( {p,q} \right)$ 对; ${L_P}$ 表示骨架 $P$ 所有骨架枝的长度总和; ${L_Q}$ 表示骨架 $Q$ 所有骨架枝的长度总和。

图2图3中模型1骨架和模型2骨架的骨架枝总长分别为257,184。相匹配的骨架枝长度分别为: ${L_{\rm{7}}} = {\rm{20}}$ ${L_{1'}} = 10$ ${L_2} = 10$ ${L_{2'}} = 29$ ${L_9} = 33$ ${L_{3'}} = 29$ ${L_{10}} = 31$ ${L_{4'}} = 34$ ${L_{11}} = 43$ ${L_{5'}} = 37$ ${L_{12}} = 34$ ${L_{6'}} = 38$ ${L_{13}} = 7$ ${L_{7'}} = 7$ 。代入式(9)中,可得两骨架相似度

$sim = \frac{{0.754 \times (20 + {\rm{10}}) + {\rm{0}}{\rm{.672}} \times (10 + 29) + \cdots + 1.000 \times \left( {7 + {\rm{7}}} \right)}}{{{\rm{257}} + {\rm{184}}}} = {\rm{0}}{\rm{.760}}$
3 实例验证

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


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

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

4 实验分析

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

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


表 3 检索相似零件耗时量 Table 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 \times 4$ ${{T}}$ 矩阵转化成16维的向量,通过计算2个向量的皮尔逊相关系数得到2个 ${{T}}$ 矩阵的相似度,即得到2个骨架枝的相似度;搜索到相匹配的骨架枝后,计算整个骨架的相似度。

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

参考文献
[1]
YOU C F, TSAI Y L. 3D solid model retrieval for engineering reuse based on local feature correspondence[J]. The International Journal of Advanced Manufacturing Technology, 2010, 46(5/8): 649-661.
[2]
CHENG H C, LO C H, CHU C H, et al. Shape similarity measurement for 3D mechanical part using D2 shape distribution and negative feature decomposition[J]. Computers in Industry, 2011, 62(3): 269-280. DOI:10.1016/j.compind.2010.09.001
[3]
徐敬华, 张树有. 基于递归分割的机械零件三维形状结构检索方法[J]. 机械工程学报, 2009, 45(11): 176-183.
[4]
董雁, 徐静. 基于装配结构相似的零件三维模型检索方法[J]. 机械工程学报, 2009, 45(4): 273-280.
[5]
EI-MEHALAWI M, MILLER R A. A database system of mechanical components based on geometric and topological similarity. Part Ⅱ: indexing, retrieval, matching, and similarity assessment[J]. Computer-Aided Design, 2003, 35(1): 95-105. DOI:10.1016/S0010-4485(01)00178-6
[6]
白静. 基于扩展特征树的三维CAD模型相似评价[J]. 计算机集成制造系统, 2014, 20(2): 267-275.
[7]
HAJIJ M, DEY T, LI X. Segmenting a surface mesh into pants using Morse theory[J]. Graphical Models, 2016, 88(6): 12-21. DOI:10.1016/j.gmod.2016.09.003
[8]
李雷, 徐盼盼, 王文成. 构建中值图以快速生成高质量的三维模型骨架[J]. 计算机辅助设计与图形学学报, 2017, 29(7): 1195-1202. DOI:10.3969/j.issn.1003-9775.2017.07.005
[9]
朱文博, 戚丽杰, 陈龙. 基于骨架和灰色关联分析相结合的机械零件三维模型检索[J]. 中国机械工程, 2015, 26(14): 1926-1931. DOI:10.3969/j.issn.1004-132X.2015.14.015
[10]
蔡自兴. 机器人学[M]. 北京: 清华大学出版社, 2000.
[11]
李瑞峰. 工业机器人设计与应用[M]. 哈尔滨: 哈尔滨工业大学出版社, 2017.
[12]
刘浩, 韩晶. MATLAB R2016a完全自学一本通[M]. 北京: 电子工业出版社, 2016.
[13]
贾俊平. 统计学[M]. 6版. 北京: 中国人民大学出版社, 2016.