有色金属材料与工程  2017, Vol. 38 Issue (4): 234-238   PDF    
基于机械零件三维模型骨架相似性度量算法
张祥, 刘阳阳, 阳鼎     
上理海工大学 机械工程学院, 上海 200093
摘要:提出了一种基于机械零件模型骨架的检索方法.将零件库中提取的机械零件进行预处理去倒角、圆角以及圆孔等,保证处理之后得到无中空结构的零件模型;运用电场法对预处理后的零件模型骨架提取,得到完整的骨架模型;利用骨架树匹配计算出零件模型相似度.试验证明该方法能够快速实现零件模型骨架检索.
关键词机械零件    预处理    电场法    骨架树    骨架提取    
Three-dimensional Model Based on Mechanical Parts Skeleton Similarity Measure Algorithm
ZHANG Xiang, LIU Yangyang, YANG Ding     
School of Mechanical Engineering, University of Shanghai for Science and Technology, Shanghai 200093, China
Abstract: A method of skeleton retrieval based on machinery parts model is proposed.The mechanical parts extracted from the parts library are pretreated, such as chamfering, fillet and round hole, to ensure that the parts are not hollow after processing.The skeleton model is obtained by using the electric field method to extract the part model after the pretreatment.The similarity degree of the part model is calculated by using the skeleton tree matching test.The test proves that the method can quickly realize the skeleton retrieval of the part model.
Key words: mechanical parts     pretreatment     electric field method     skeleton tree     skeleton extraction    

机械零件骨架可以形象地表示出其拓扑结构特征, 作为零件三维模型几何和拓扑结构的简化表示[1], 被广泛应用于机械设计、医疗机械等行业[2].目前关于骨架提取的方法越来越多[3-5].本文基于物理学知识, 沿着电场线方向电势降低, 即随着零件模型内部点到边界点距离的增大电势而降低, 采用电场法实现对零件模型骨架的提取, 提取骨架之后利用骨架的特征完成骨架的相似度计算[6].

1 机械零件三维模型预处理

根据三维软件建模过程的特性, 零件模型的特征是逐渐叠加形成, 其中包括基准特征, 辅助特征以及附加特征等.附加特征包括倒角、圆孔、键槽等特征, 附加特征是在不改变零件模型基本特征主要形状的前提下, 对已有特征进行局部修饰的建模特征, 而零件模型的骨架主要取决于零件的主干部位, 因此它的存在并不影响零件模型的结构工艺以及整体拓扑结构.

图 1(a)中的零件预处理之后, 得到的模型均为无中空结构零件模型, 如图 1(b)所示.

图 1 零件预处理前后模型 Fig. 1 Part preprocessing model before and after
2 骨架提取

零件骨架的提取在一定程度上保留了零件原有的拓扑关系以及零件的稳定性.骨架的直观性、简洁性、连通性以及中心性更能使复杂的零件模型简单化, 所以骨架的提取算法被广泛应用.

2.1 机械零件起始点的选择

机械零件经过预处理之后得到零件模型的主干部分.骨架起始点的选择是保证骨架能顺利进行的前提.每个零件都有顶点, 顶点是面与面、线与线之间的交点.其作用不仅决定了零件模型的外形结构特征, 也影响零件模型的三维立体空间的分布.经过预处理之后的机械零件模型的外形表面通常是由平面、圆柱面、球面、球面圆、锥面以及各种曲率不同的曲面拟合组成.对于平面而言, 零件骨架的起始点选择相对容易; 对于规则或者不规则的曲面而言, 零件骨架的起始点选择原则是选择无限接近零件顶点的内部模型点, 而不直接选择零件模型的顶点, 是由于根据物理电学知识, 零件模型表面到模型内部电势随着距离的减小而增大, 因此可知零件表面的电势无穷大, 而零件内部必然存在电势较低的点.顶点属于表面一部分, 电势无穷大, 当顶点向内部方向移动时, 会发生势能的突变, 受力程度难以控制, 所以零件骨架的起始点应选择模型内部, 但无限靠近顶点.如图 2所示.

图 2 机械零件模型 Fig. 2 Mechanical parts model
2.2 机械零件模型骨架的提取

任何一个机械零件表面外形均带有正电荷, 而由于这些正电荷形成一个相对稳定的电场, 电场线的方向总是垂直于机械零件模型的表面且由外向内, 根据物理电学知识, 零件模型表面到模型内部电势随着距离的减小而增大.因此可知零件表面的电势无穷大, 而零件内部必然存在电势较低的点.

定义机械零件内任意点P的排斥力为:

$F_P = \sum\limits_{i=1}^n B_i P = \sum\limits_{i=1}^n \frac{B_i P}{R^m}$ (1)

式中:P为零件内沿着受力方向前进的一点; BiP点的电场线方向与边界表面的交点; R为点BiP点之间的距离; nP点的受力个数; m为力的阶数, 受力的大小分别为1/Rm.

由式(1) 可知, 随着力的阶数m的变化, 电场力FP也随着变化, 根据文献[7], m=6时, 试验效果最佳.对于零件模型的一点, 受到排斥力的作用, 其合力方向即该点与相邻面垂直方向电场排斥力的矢向量和.

零件模型点的方向和大小均已确定, 如图 3所示.其中A为零件模型表面的顶点, 对零件模型内无限接近顶点A的骨架起始点P进行受力分析.

图 3 零件模型受力分析 Fig. 3 Part model force analysis

图 3Fi(i=1, 2, 3, …, 6) 分别对应零件模型边界对起始点P的6个方向的电场斥力, 6个力的方向和大小由式(1) 可得, B1为零件模型表面边界与电场线方向的交点, Fp为6个力的合力方向.因此设定单位步长并沿着合力方向移动, 必然得到下一个点的目标.以此方法进行, 最后得到电势最小的点.以此方法得到骨架的路径, 生成骨架.如图 4(a)中从A, D, E, H各个骨架起始点出发至电势最低处之前发生融合, 到O1处, 因此只需从O1处沿合力方向移动.如果两个最小电势点与已生成的骨架分枝或者零件模型没有交叉点, 则认为两个点均为电势最低点, 因此可以将两个电势最低点相连, 与起始点开始的骨架路径组成一套完整的机械零件骨架, 如图 4所示.

图 4 零件各分点合并及模型骨架图 Fig. 4 Model of skeleton points are merged and part model skeleton map
3 骨架形状相似性

计算骨架相似首先建立模型骨架树, 完成对骨架枝的匹配寻找, 其次计算骨架枝间的相似度[8].

3.1 骨架树的建立

为了准确描述骨架的拓扑结构特征, 将零件模型的骨架映射到二维树结构中, 形成骨架树结构.

零件模型骨架存在任意两个或者两个以上线段相连的点, 称为骨架树的节点.只有一个邻接点的骨架称为端点.任意两个以上的邻接点称为分支点.以任何一个分支点为球心做出与零件模型表面相切的最大内切球, 靠近零件模型重心或者具有最大球半径的分支点称为根节点.其余分支点称为根节点的子节点.

图 5为机械零件模型的骨架, 图 6为模型骨架树.

图 5 模型骨架 Fig. 5 Model skeleton

图 6 模型骨架树 Fig. 6 Model skeleton tree
3.2 骨架的相似度

由上述提取骨架方法可知, 骨架起始点沿着合力方向按照一定步长得到骨架枝, 然而得到的骨架枝是无数个离散曲线或直线的点.构成骨架枝的点的集合为P={Pi}, i=1, 2, …, m.P是由三维m个数据点组成, 因此对于模型骨架的比较, 近似转换为多个数据点集的匹配问题.

模型中存在两个骨架枝A, B.曲率可通过集合的形式表示骨架枝.为了实现两个骨架枝的相似度, 首先将骨架枝的步长同时扩大$X=\frac{\max (f_i,f_j)}{\min (f_i,f_j)}$倍(其中fifj为步长), 但由于骨架生长步长不同, 所以骨架曲率不可相比.然后求得骨架枝A的各数据点的曲率Ki(i=1, 2, 3, …, m), 骨架枝B各数据点的曲率Kj(j=1, 2, 3, …, m).两个骨架枝相似度的计算方法分两种情况:第一, 当骨架枝曲率均为零或非零常数时, 得到的是空间曲线和环状骨架枝; 第二, 当其中一组为零, 另一组不为零时, 则一个骨架枝为空间直线, 另一个骨架枝为空间曲线.在对曲线各个数据点曲率计算相似度之前, 要对离散的点进行匹配, 判别离散点是否匹配, 如式(2) 所示:

图 7 骨架枝SiSj Fig. 7 Skeleton branchesSiSj
$|K_i - K_j|\le \varepsilon$ (2)

式中, ε为阈值, 可采用式(3) 计算阈值大小:

$\varepsilon = \eta \frac{[(K_{i_\rm{max}} - K_{i_\rm{min}}) + (K_{j_\rm{max}} - K_{j_\rm{min}})]}{2}$ (3)

式中:Kimax, Kimin, Kjmax, Kjmin分别为骨架枝A, B上数据点的曲率最大值和最小值, η太小无法建立模型多骨架枝间的匹配关系, 太大会出现相似度计算误差太大, 经实例验证, 本文取η=0.35.

曲线数据点匹配之后对骨架枝的相似度计算如式(4) 所示:

$M(A,B) = \frac{\min (f_i \times m, f_j \times n)}{\max (f_i \times m, f_j \times n)}$ (4)

式中:fifj分别为骨架枝AB的步长; mn分别为两个骨架枝的三维数据点集的数量.

对于上述第一种情况, 采用差分法比较其相似度.由微分几何学中相关理论可知, 空间离散曲线可以分为函数拟合法和差分法, 函数法难以通过函数表示生成骨架枝的多样性和复杂性, 故不采用.所以本文利用电场法生成步长相等的骨架枝的特性, 因此采用差分法.

求出骨架枝每个数据点的曲率和弗朗内特标架, 计算骨架枝上点的曲率和弗朗内特标架值来表示骨架枝之间的相似度大小.曲率和弗朗内特标架计算如式(5) 所示[9]:

$t = \dot{p}, b = \frac{\dot{p} \times {\ddot p}}{|\dot{p} \times {\ddot p}|} ,n = b\times t, k=|\dot{p} \times {\ddot p}|$ (5)

式中:p为矢量点; t为切向矢量; b为副法向矢量; n为曲率矢量; k为曲率.{t, n, b}构成弗朗内特标架.存在A为固定点骨架枝的云曲线, B为可移动点骨架枝的云曲线, 骨架枝A上的固定点Pi的弗朗内特标架为{ti1, ni1, b11}, 骨架枝BPj点的弗朗内特标架为{tj2, nj2, bj2}, 解矩阵方程R·{tj2, nj2, bj2}T={ti1, ni1, bi1}算出旋转矩阵R, 满足ki1-kj+12≤0.35, 则对Pj+12的弗朗内特标架{tj+12, nj+12, bj+12}进行旋转(R·{tj+12, nj+12, bj+12})得{tj+12, nj+12, bj+12}, 如果矩阵{tj+12, nj+12, bj+12}T·{tj+12, nj+12, bj+12}满足弗朗内特标架对骨架枝的空间曲线数据点的判定条件, 则PiPj建立相应的匹配关系; 然后依次计算骨架枝上其他点Pi+kPj+k, k=2, 3, 4…的匹配情况, 结束匹配统计并记录骨架枝AB各个数据点的情况.对骨架枝间的相似度M(A, B)进行计算:

$M(A,B) = \frac{(f_i+f_j) \cdot \mu}{f_i \cdot m +f_j \cdot n}$ (6)

式中:fi, fj分别为骨架枝AB的步长; mn分别为骨架枝AB的三维数据点数; μ为骨架枝中参与匹配点的数目.

模型骨架相似度的计算:

$Sim(T_1,T_2) = \frac{\sum M(A,B) \cdot (L_A + L_B)}{L_{T_1}+L_{T_2}}$ (7)

式中:M(A, B)为两个模型骨架树T1T2中的一对已匹配的骨架枝A, B的相似度; LALB分别为该匹配对骨架枝AB的长度, LT1LT2为两个骨架树各自骨架枝长度之和.如模型一和模型二骨架枝的步长分别是1.42 mm和1.33 mm.再骨架树中, 骨架树T1中同一子树的不同分支的所有骨架枝都是空间曲线, 长度11.25 mm, 周长25.20 mm; O0O1, O0O4, O0O5, 同为空间长度相等的曲线, 其长度5.70 mm.同理, 在T2Ts1Ts2的所有骨架枝都为空间直线且长度均相等, 其长度10.42 mm; 环状骨架枝S15S16S17S18相等, 其周长31.43 mm; S4S15, S4S16, S4S17, S4S18也均为空间直线且长度相等, 其长度为7.10 mm.骨架枝S0S3S0S4均为空间曲线且相互匹配, O0O1数据点13个, S0S4数据点16个, 匹配点数量为10, 相似度$M(S_0 S_3,S'_0S'_4) = \frac{(1.42+1.33)\times 10}{1.42 \times 13 + 1.33 \times 16} = 0.70$.

骨架树T1中余下的骨架枝, 其长度均为2.80 mm, 骨架树T2中余下的S3S13S3S14的长度均为3.90 mm.将该数值代入式(7) 中, 得到相似度:

$Sim(T_1,T_2) = \frac{\sum M(A,B)\cdot (L_A+L_B)}{L_{T_1}+L_{T_2}} = \\ \frac{{\frac{{10.42}}{{11.25}} \times (8 \times 10.42 + 8 \times 11.25) + \frac{{25.20}}{{31.43}}(2 \times 25.20 + 2 \times 31.43) + 0.70(1.42 \times 13 + 1.33 \times 16)}}{{(8 \times 10.42 + 8 \times 11.25) + (2 \times 25.20 + 2 \times 31.43) + (1.42 \times 13 + 1.33 \times 16) + 2 \times 2.80 + 2 \times 3.90}} = 0.817$

计算可得, 模型一与模型二的相似度为0.817.

4 结论

本文提出了基于机械零件骨架相似度算法, 通过两个阶段完成.第一阶段通过电场法生成模型骨架并转换成骨架树.第二阶段通过匹配骨架枝进而计算整个骨架形状相似度.主要采用空间离散曲线的曲率和弗朗内特标架进行空间曲线相似性计算.将骨架枝相似度匹配转化成易于计算的点云空间曲线, 具有较高的准确性和有效性.

参考文献
[1] AUO C K, TAI C L, CHU H K, et al. Skeleton extraction by mesh contraction[J]. ACM Transactions on Graphics, 2008, 27(3): 441–449.
[2] LIVESU M, SCATENI R. Extracting curve-skeletons from digital shapes ussing occluding contours[J]. The Visual Computer, 2013, 29(9): 907–916. DOI:10.1007/s00371-013-0855-8
[3] AURENHAMMER F. Voronoi diagrams a survey of a fundanmental geometric data structure[J]. ACM Com-putering Surveys, 1991, 23(3): 345–405. DOI:10.1145/116873.116880
[4] XIE W J, THOMPSON R P, PERUCCHIO R. A topology preserving parallel 3D thinning algorithm for extracting the curveskeletons[J]. Pattern Recognition, 2003, 36(7): 1529–1544. DOI:10.1016/S0031-3203(02)00348-5
[5] NIBLACK C W, Gibbons P B, Capson D W. Generating skeletons and centerlines from the distance transform[J]. Graphical Models and Image Processing, 1992, 54(5): 420–437. DOI:10.1016/1049-9652(92)90026-T
[6] 王桂平, 王衍, 任嘉辰. 图论算法理论, 实现及应用[M]. 北京: 北京大学出版社, 2011.
[7] AHUJA N, CHUANG J H. Shape representation using a generalized potential field model[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1997, 19(2): 169–176. DOI:10.1109/34.574801
[8] 朱文博, 耿国庆, 刘阳阳, 等. 基于骨架树的机械零件三维模型检索方法[J]. 机械工程学报, 2016, 52(13): 204–212.
[9] 马国庆, 陶萍萍, 杨周旺. 点云空间曲线的微分信息计算及匹配的方法[J]. 计算机工程与应用, 2010, 46(1): 164–168.