基于骨架和灰色关联分析相结合的机械零件三维模型检索

朱文博　戚丽杰　陈　龙

上海理工大学，上海，200093



基于骨架和灰色关联分析相结合的机械零件三维模型检索

朱文博戚丽杰陈龙

上海理工大学，上海，200093

提出了一种将模型骨架和灰色关联分析相结合的机械零件三维模型检索方法。首先简化机械零件三维模型，忽略倒圆、倒角、孔等附加特征，得到无中空结构的连贯模型;然后基于电场法提取简化后的机械零件三维模型的骨架，所提取的骨架表达了零件模型的形状和拓扑结构特征，并将骨架转换成特征曲线；最后运用灰色关联分析方法计算特征曲线的相似关联度，从而得到机械零件三维模型的相似度。实例验证和实验分析表明，该方法能准确地检索出相似的机械零件三维模型。

机械零件;三维模型检索;骨架提取;灰色关联分析;相似度

0　引言

企业不断发展,积累了大量的机械零件三维模型，怎样从大量的模型中检索出所需要的相似零件，重用已有的企业资源,避免重复劳动,是目前比较热门的一个研究课题。针对机械零件三维模型的相似性,文献[1]研究了基于几何和拓扑相似性的三维机械零件模型的匹配以及检索方法,该方法将零件模型转换为STEP格式提取零件的结构数据,构造零件模型图,基于模型图进行零件相似性比较,但计算量大,实际应用有一定困难。文献[2-3]结合D2形状分布图和NFD树结构方法,先把模型分解成几何基本体的树结构,然后分层次地评定两模型的相似性，对于较复杂的零件模型,不同的分解生成不同的树结构,得出的相似性存在较大的误差。Chuang等[4]用广义势场法提取简单的规则多面体的骨架,以物体凸起的角点作为种子点，在力的引导下生成不同的骨架段,处理对象不涉及曲面,不能完全适用于机械零件的检索。王飞等[5]提出了拓扑和形状特征相结合的三维模型检索方法，从整体和局部相结合两方面比较模型的相似性，但并未给出提取骨架实际可行的方案，且其相似性算法较复杂，难于实现。王家乐等[6]提出利用模型表面面片的法向量方向分布特征构建具有旋转不变性的N2形状描述符来比较模型的相似性,两种模型的相似性距离计算使用的权值估计算法较繁杂,实现起来有一定的困难。

本文用电场法提取机械零件三维模型的骨架，并将骨架转换成特征曲线，运用灰色关联分析方法计算特征曲线的相似关联度，从而得到机械零件三维模型的相似度。本文方法能快速地获得零件的骨架，应用灰色关联分析进行相似度计算，算法准确且简单，易于实际应用。骨架和灰色关联分析的结合能准确快速地检索出相似的机械零件三维模型。

1　机械零件三维模型的简化

零件的特征建模过程,由特征按照一定的顺序叠加而成，这种叠加以交、并、差布尔运算的形式进行。其中机械零件上的一些附加特征，也称为辅特征，如键槽、内外螺纹、倒角、倒圆、孔等，这些特征都是在零件已有的特征或实体上添加的具有特定工艺属性的结构，主要是对零件局部进行修饰,它们的存在与否并不影响模型的整体拓扑结构。模型的相似性主要取决于它们的主干结构,故在提取模型骨架前计算机先自动识别提取这些附加特征并把它们过滤。过滤简化后尽可能得到一个无中空结构的连贯实体模型,这样有利于后续骨架的提取过程。

图1a所示零件,模型中的倒圆、倒角、孔等附加特征的存在与否没有影响模型的整体结构分布，简化时被过滤,得到的无中空结构的连贯模型如图1b所示。

(a)简化前

(b)简化后图1　模型简化前后

2　骨架的提取

线性骨架是物体的一种降维表示,它通常由一组曲线段相互连接构成,每一条曲线段一般只有一个像素点的宽度，因而它是物体的一种直观的、简洁的表示，提取出的模型骨架在很大程度上保留了三维模型的形状特征和拓扑结构特征，有良好的稳定性，被广泛应用于三维实体建模、计算机动画、医学可视化、形状分类和识别等领域[7]。本节针对机械零件的三维模型研究骨架的提取。

2.1骨架起始点的确定

模型简化后,对其主干结构进行骨架提取,将机械零件转换成既包含形状特征又包含拓扑特征的骨架。

机械零件模型的顶点对于模型的空间形状分布具有非常重要的作用,它决定了模型的结构分布，进而决定了骨架的空间分布。简化后的机械零件模型表面主要由平面和曲面构成，且曲面通常由圆柱面、圆锥面和球面等规则曲面拟合而成。当表面为平面时，模型上的顶点很容易选择，如图2中的A、B、C、D点，都是由平面相交构成的顶点；当模型上某一边界表面为曲面时，本文将曲面的转向轮廓线的端点定义为顶点，如图2中的E、F、G点是模型的顶点。本文选择无限接近模型顶点的内部点作为骨架起始点，选择的原因见下文。

图2　骨架起始点的确定

2.2运用电场法提取骨架

假设简化后零件模型边界表面上均匀分布着正电荷，这些电荷在模型内部产生了一个稳定的电场，电场方向垂直于边界表面且指向模型内部。若某表面为平面，则电场方向垂直该平面且指向模型内部；若为曲面，则电场方向垂直于曲面上某点的切面且指向模型内部。根据物理静电力学知识，沿着电场线方向电势(位势)降低,即位势随着模型内部点到边界点距离的增大而减小，取边界表面处的位势为无穷大，可知在模型内部某点存在最小位势点。最小位势点是获得模型骨架的关键点。

2.1节中选择无限接近模型顶点的内部点作为骨架起始点，而不直接选择模型顶点作为起始点,是因为在边界处电势存在突变,起始点在边界处的受力难以控制，计算进程难以进行。起始点在电场中受到电场斥力的作用，其合力的方向取决于所有通过该点且与边界面垂直的各个电场斥力的矢量和。

定义模型内P点的斥力计算公式为

(1)

其中,P为起始点沿着合力方向前进的某一点;Bi为通过P点的电场力的方向线与边界表面的交点,即电场线与边界面(切面)的垂直点；R为点Bi与点P之间的距离;n为P点的受力个数;m为力的阶数;分力的大小为1/Rm,与Rm成反比。根据式(1),力的阶数m不同,斥力FP的衰减程度就不同,起始点受到的合力方向就会有所不同，获得的最小位势点就会与理想情况下的点有所偏差。m在一定范围内取得越大,外界对力的影响就越小[8],获得的骨架就越理想。经过多次实验计算,当m=6时计算速度较m<6时降低10%,而查准率-查全率提高30%;m=6时较m>6时,速度提高20%,查准率-查全率降低3%;因此综合考虑,当m=6时获得的实验效果最好，所以本文取m=6。

各个分力的大小和方向都已确定,内部某点所受合力为各个分力的矢量和，模型内部的合力方向即可确定。例如,取无限接近图2中顶点A的内部点P作为起始点，对该点进行受力分析,如图3所示。

图3　模型内部点受力分析

图3中B1为通过P点的电场力方向线与模型的上表面的交点;力Fi(i=1,2,…,6)分别为模型边界面上对应点对P点的电场斥力。图3中P点受六个分力的作用，其大小和方向根据式(1)来计算,Fi对应式(1)中的各分力FBiP,FP为各分力合成的合力,合力的方向代表起始点下一步前进的方向。得到合力的方向后，起始点按照步长前进，在下一点同样进行电场受力分析，如此重复计算，直到到达最小位势点。

起始点的受力作用使用式(1)表示的各个分力来合成计算，根据力的跟踪法，沿着合力的方向按一定步长逐步移动，直到移动到最小位势点，起始点移动的轨迹构成模型骨架的一个分支。步长的选择要保证骨架的连续性和光滑性，若步长选择过小，则计算量过大;若步长选择过大，则无法保证得到连续的骨架,本文选择模型最大长度的1/100作为一步长。起始点在到达最小位势点之前，沿着合力的方向一步一步地往前移动；如果移动后导致力的方向相反(当前后两个力的方向超过90°时,则认为这两个力的方向是相反的),则认为最小位势点找到了，即可停止该方向上的计算。

如果起始点在到达最小位势点之前到达已生成的骨架分支则停止该起始点沿力的方向的计算进程，该起始点接下来的沿力方向前进的计算合并到已生成骨架分支上，直到到达最小位势点，这样可以减少重复计算，减少总体计算时间。图4a是图4b的局部放大图，图4a中A、B、C、D几个起始点在到达最小位势点之前发生骨架分支合并,相交于M点。然后A、B、C、D几个起始点的计算进程合并到M点,只需计算从M点沿力方向的进程，直到到达最小位势点。

如果两个最小位势点的连线没有和物体边界或已经生成的骨架分支有交叉点,则认为这两个点均是最小位势邻接点。获得模型骨架的最小位势点后，将最小位势邻接点连接起来，和起始点路径形成的骨架分支结合起来即获得完整模型骨架。模型获得的完整骨架如图4b所示。

(a)骨架分支点的合并

(b)完整的模型骨架图4　骨架提取过程

2.3骨架生成特征曲线图

提取出的骨架是由一组空间直线、曲线组成的,其中组成骨架的每一条线段或曲线段都是骨架的一个分支。要比较模型骨架的相似性，就要先将模型骨架信息转换成便于比较计算的计算机能识别的符号数据。本文将每一骨架分支看作空间中的一个向量,向量的大小用向量的模来表示，向量的方向用向量与坐标平面xoy的夹角表示(方向角)。向量的模描述了骨架分支的形状特征，向量与坐标平面的夹角描述了骨架分支的拓扑结构特征，用这两个量能准确地表达骨架。当骨架分支为曲线时，曲线的长度即向量的模,曲线两端点切线的角度变化值作为向量的方向角。将向量的模和向量方向角的余弦值这两个数据组合写成点的形式，这样每一骨架分支就对应一个点数据,这个点数据就是骨架的特征点。

以向量的模和方向角余弦值分别作为直角坐标系的横坐标和纵坐标，在坐标系中将各骨架分支对应的特征点标出，然后平滑连接成曲线。连接形成的曲线包含了骨架的长度和方向性两方面的特征，是骨架的特征曲线。

由图4b零件骨架的特征数据绘制出的骨架特征曲线如图5所示。

图5　零件骨架特征曲线

3　基于灰色理论的骨架相似度计算

灰色关联分析是灰色系统理论中十分活跃的一个分支，其基本思想是根据序列曲线几何形状的相似程度来判断其联系是否紧密。曲线越接近，相应序列之间的关联度就越大,即相似性越大,反之就越小[9]。本文运用基于相似性和接近性视角的灰色关联度模型[9]来进行骨架特征曲线的相似性比较，从而得到机械零件三维模型的相似度。

设系统行为序列

Xi=(xi(1),xi(2),…,xi(n))

(2)

Xj=(xj(1),xj(2),…,xj(n))

(3)

的始点零化像分别为

(xi(1)-xi(1),xi(2)-xi(1),…,xi(n)-xi(1))

(4)

(xj(1)-xj(1),xj(2)-xj(1),…,xj(n)-xj(1))

(5)

设序列Xi与Xj长度相同,则两序列的基于相似性视角的灰色关联度(简称相似关联度)为

(6)

(7)

需检索零件的特征曲线为参考曲线,对应序列为参考序列Xi,待检索零件的特征曲线为比较曲线,对应序列为比较序列Xj,特征曲线的相似关联度为εi j。

灰色相似关联度εi j具有的性质如下：①0<εi j≤1;②εi j仅与Xi和Xj的几何形状有关，而与其空间相对位置无关,或者说,平移变换不改变相似关联度的值;③Xi与Xj在几何形状上越相似,εi j越大,反之就越小;④εi i=1[9]。

获得骨架的特征曲线后，在曲线对应点上取出序列，特别要取曲线转折点对应的数据,因为曲线的转折点是表征特征曲线形状的关键点,它包含曲线几何形状的更多信息，如图5中特征曲线上的A、B、C、D、E等点都是特征曲线的关键点。取图5中特征曲线的序列为X0=(x0(1),x0(2),…,x0(n))=(0.62,0.55,0.48,0.54,0.54,0.75,0.84,0.67,0.65,0.45,0.00,0.45,0.37,0.44,0.50,0.57,0.70,0.85,0.87,1.00)。图5所示特征曲线对应的序列为参考序列，而其他机械零件特征曲线对应点上取出的序列作为比较序列Xj,参考序列和比较序列根据式(2)～式(7)计算曲线的相似关联度，进而获得骨架的相似度。系统根据计算出来的相似度值的大小按照从大到小次序排列,用户设置相似度阈值或输入需要返回的相似模型数目，系统返回与待检索模型最相似的若干模型。

4　实例应用

以图6a所示的零件为例说明上述相似性比较过程。首先简化机械零件三维模型，将不影响零件整体拓扑结构分布的一些附加特征简化,如简化模型中的倒圆、倒角、孔等,简化得到的连贯实体如图6b所示。假设简化模型表面均匀分布着正电荷，在模型内部产生了稳定的电场，选取模型的顶点作为起始点，由于电场的作用，起始点受到电场斥力的作用按照给定的步长沿着合力的方向前进，直到到达最小位势点，起始点的移动轨迹构成骨架的一个分支,最后将最小位势邻接点连接起来，形成完整的骨架，零件生成的骨架如图6c所示。

(a)示例零件　(b)简化模型(c)模型骨架图6　示例零件骨架提取

生成骨架后,计算骨架各分支对应的向量的模和向量的方向角余弦值，数值统计成特征点的形式，然后根据特征点数据绘制骨架特征曲线；最后运用灰色关联分析计算比较骨架特征曲线的相似关联度。

根据图6c所示骨架计算得到的点数据绘制的骨架特征曲线如图7所示。

采用同样方法绘制的图8a所示零件的骨架特征曲线如图8b所示。

图7　骨架特征曲线图

(a)比较零件模型

(b)比较零件的骨架特征曲线图8　实例库中的某一比较零件

运用灰色关联分析计算比较图7和图8b两骨架特征曲线的相似关联度。在两个特征曲线上取相同长度的序列X1,X2。

将以上数据代入式(7)得|s1-s2|=0.205,代入式(6)得两骨架特征曲线的相似关联度ε12=0.830，即两个零件的相似度为0.830。

采用本文方法计算得到零件库中部分零件与图6a所示零件的相似度见表1。

表1　模型库中部分零件与示例零件相似度值

从表1可以看出,运用本文方法计算得到的结果与人类认知相符合,零件的主体拓扑结构越相似，得到的相似度值越大。

若用户设置相似度阈值为0.8,则系统返回与示例零件相似度大于或等于0.8的模型,表1中前3个零件为与示例零件相似的机械零件；若用户设置需要返回的模型数目为5,则系统返回表1中前5个零件作为与示例零件相似的机械零件。

5　实验分析

实验主要从计算量和查准率-查全率曲线(P-r曲线)两方面验证本文方法的可行性与准确性。将本文方法与D2形状分布算法、N2形状描述符算法、球面调和描述符[10]三种算法进行对比。

从计算量上看,单一考虑形状特征的D2形状分布算法只需要计算模型表面随机采样点间的距离，计算复杂度不高，计算量最小；本文的骨架提取算法，斥力计算公式和灰色关联度计算复杂度都不高，计算量稍大于D2算法;N2算法是在D2算法的基础上，增加计算每对采样点所在的两个多边形面片的法向量夹角余弦值，计算复杂度稍高于前两种算法；球面调和算法需要先对网格模型进行体素化预处理，然后计算体素模型和球面的相交图像，复杂度高，计算量大。本文使用ESB(engineering shape benchmark)[11]作为测试数据库,在同一台计算机上采用4种算法检索同一个相似零件模型,所用的计算时间见表2。

表2　检索相似零件计算时间　min

从表2可以看出，本文算法计算复杂度不高，计算耗时仅次于D2算法，远短于球面调和算法。

查准率-查全率曲线是分析检索系统准确性高低的重要评价手段,本文仍然使用ESB作为测试数据库。图9所示为4种算法的P-r曲线,可以看出,查准率和查全率之间存在制约关系：随着查全率的提高,查准率会下降。查全率为0.4时，D2算法的查准率只有0.15,N2算法查准率为0.18,本文算法为0.27,球面调和描述符算法为0.38;而当查全率为0.6时，D2算法查准率下降到0.11,N2算法为0.12，本文算法为0.18,球面调和描述符算法为0.25。由图9可以看出,本文方法的检索准确性要优于D2形状分布算法和N2形状描述符算法，仅次于球面调和算法。

图9　查准率-查全率曲线图

综合考虑计算量和查准率-查全率两方面可以看出，球面调和描述符算法准确性虽然高于本文算法，但其计算过程复杂，系统实现困难,本文检索方法的综合性能优于球面调和描述符算法、D2算法及N2算法。

6　结语

本文提出的机械零件三维模型检索方法首先简化模型，忽略倒圆、倒角、孔等附加特征，得到无中空结构的连贯模型，实验证明，模型虽然被简化，但是保留了三维模型的形状特征和拓扑结构特征，不影响检索的查准率和查全率，而且提高了生成骨架的速度，即提高了检索的速度。在简化模型的基础上应用电场法提取三维模型的骨架，起始点的选取以及斥力计算简单清晰，便于最小位势点的获取，生成骨架快速准确。将生成的骨架转化成便于比较的数据，生成特征曲线，采用灰色关联度分析比较特征曲线的相似关联度，从而得到机械零件三维模型的相似度，将灰色理论应用于机械零件检索，尤其在实例库为小样本时，具有极高的准确性和有效性。

本文所阐述的模型骨架提取方法特别适用于有明显空间结构分布的机械零件,目前已在自行开发的检索原型系统中得到应用,实例库有近500个零件。然而,对于另外一些零件,如中空薄壁类零件，若简化为无中空结构，零件的结构会发生较大变化,影响检索的查准率，因此，本文的骨架提取对该类零件不适用，对于该类零件的相似性比较正在进一步研究改进中。

[1]El-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].Journal of Computer-Aided Design,2003,35:95-105.[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:269-280.

[3]Chu C H,Cheng H C,Wang E,et al.ANN-based 3D Part Search with Different Levels of Detail(LOD) in Negative Feature Decomposition[J].Expert Systems with Applications,2009,36:10905-10913.

[4]Chuang J,Tsa I C,Ko M C.Skeletonization of Three-dimensional Object Using Generalized Potential Field[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2000,22(11):1241-1251.

[5]王飞,张树生.拓扑和形状特征相结合的三维模型检索[J].计算机辅助设计与图形学学报,2008,20(1):99-103.

Wang Fei,Zhang Shusheng.3D Model Retrieval Based on Both the Topology and Shape Features[J].Journal of Computer-Aided Design & Computer Graphics,2008,20(1):99-103.

[6]王家乐,姜波.一种基于形状的机械零件模型检索方法[J].中国机械工程,2010,21(6):707-710.

Wang Jiale,Jiang Bo.A Shape-based Method for Retrieving 3D Models of Mechanical Parts[J].China Mechanical Engineering,2010,21(6):707-710.

[7]邓军国.三维模型检索中几种特征提取方法实现研究[D].西安:西北大学,2009.

[8]Ahuja N,Chuang J.Shape Representation Using a Generalized Potential Field Model[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1997,19(2):169-176.

[9]刘思峰,党耀国,方志耕,等.灰色系统理论及其应用[M].5版.北京:科学出版社,2010.

[10]Kazhdan M,Funkhouser T,Rusinkiewicz S.Rotation Invariant Spherical Harmonic Representation of 3D Shape Descriptors[C]//Proceedings of Symposium on Geometry Processing.Aachen,2003:156-164.

[11]Jayanti S,Kalyanaraman Y,Iyer N,et al.Developing an Engineering Shape Benchmark for CAD Models[J].Computer-Aided Design,2006,38(9):939-953.

(编辑陈勇)

3D Model Retrieval of Mechanical Parts Based on Skeleton and Grey Correlation Analysis

Zhu WenboQi LijieChen Long

University of Shanghai for Science and Technology,Shanghai,200093

A 3D model retrieval method of mechanical parts was proposed combined skeleton and grey correlation analysis.Firstly,3D model of mechanical parts was simplified to get a coherence model without hollow structure by ignoring additional features of model,such as fillet,chamfer and hole etc.Then the skeleton was extracted,which expressed shape and topology features of the parts model from simplified 3D model of mechanical parts based on the electric field method;and the skeleton was converted into characteristic curve.Finally,calculating the similarity degrees among characteristic curves and grey correlation analysis method was used to obtain similarity degrees of parts.Through the example verification and experimental analyses,the method can accurately retrieve the similar 3D model of mechanical parts.

mechanical part;3D model retrieval;skeleton extraction;grey correlation analysis;similarity degree

2015-01-13

国家自然科学基金资助项目(51475309);上海市教育委员会科研创新一般项目(13YZ071)

TH128;TP391DOI：10.3969/j.issn.1004-132X.2015.14.015

朱文博,女,1973年生。上海理工大学机械工程学院副教授、博士。主要研究方向为基于知识的工程。戚丽杰,女,1989年生。上海理工大学机械工程学院硕士研究生。陈龙,男,1978年生。上海理工大学机械工程学院讲师、博士。