基于二维信息集的CAD模型相似度评价方法研究

丁淑辉，周 鑫，曾庆良，夏 群

（1.山东科技大学机电学院，山东 青岛 266590；2.新泰市科学技术局，山东 泰安 271200）

1 引言

随着数据库和云平台技术的发展，很多企业为了管理现有模型建立了模型数据库以及模型云平台，机械产品的开发大多是在现有模型的信息重用基础上完成的，因此在模型库中准确地检索到相似度高的模型，对缩短研发周期、提高研发效率有着重要意义。

基于内容的模型检索［1］是当前主流的检索方法，文献［2］最早提出使用属性邻接图（Attributed Adjacency Graph，AAG）来表达模型的拓扑结构，后经学者对基于AAG的方法的不断研究，目前基于图的特征识别与模型相似度评价方法已成为主流［3］。文献［4］对模型的骨架建立坐标系，然后使用广义变换矩阵表示模型骨架，将模型的相似度转化为矩阵相似度比较。以模型的整体结构作为相似度评价依据，可以较好的比较两模型间的整体结构，但模型的部分重要局部结构不能得到充分比较。文献［5］将模型进行区域分割，通过比较不同模型间最具有代表性的局部特征得到模型相似度。此方法能够充分考虑模型细节，但只有对用途相近的同种类模型进行比较时，才能较好的体现。通过引入高效的算法提高模型检索效率，文献［6］使用粒子群算法对所建立的相似度矩阵进行搜索；文献［7］用加权图逼近方法找到不同模型对应的最大公共子图，以得到模型的相似度；文献［8］构建了零件加工面扩展AAG，将模型边与面的形状因素包括进来进行特征识别；文献［9］将模型中同种类型的面进行匹配，通过计算所有类型的面的最优匹配方案，并加权求解模型间的相似性。

当前方法多数以模型拓扑结构作为主要评价依据，而AAG作为一种模型的表示方式并不能完全反应模型的实际情况，从而导致所得到的相似度结果与实际情况不符。AAG在计算机内部表示为AAM［10］，传统的AAM仅包含模型结构信息及基本属性信息，如模型表面邻接关系、模型元素基本属性等，虽然可以较好地表达模型本身的拓扑结构及基本形状，但并不能有效反映模型间的差别，如图1 所示。图1（a）、图1（b）两图所示A、B两模型的AAG相同，如图1（c）所示；因其表面形状、交线的凹凸性等基本性质相同，两图的AAM也相同。由此可见，传统AAG、AAM并不能完整、准确的反映模型基本形状。

图1 不同模型及其AAGFig.1 Models and Their Corresponding AAG

基于上述问题，通过提取模型拓扑与尺寸信息，创新性的构建了基于AAM的模型信息集，提出了基于模型信息集的模型相似度评价方法。以模型信息集作为信息来源，以模型表面作为顶点独立集，以模型间每对表面间相似度为权重，建立赋值完全偶图。使用Kuhn-Munkres算法（以下简称KM算法）得到其最优匹配作为两模型的最相似匹配，并评价其相似度。

2 基于AAM的二维信息集的建立

模型信息的提取是模型相似性比较的基础和关键，在研究模型信息需求及提取方法的基础上，建立了基于AAM的二维信息集，为模型相似度评价提供数据支持。

2.1 模型B-rep模式信息提取与表示方法

在三维模型的基于图的表达中，以图的节点表示模型表面、以节点连线表示两个面的交线，以模型表面和交线的拓扑结构、基本形状等作为基本属性，构建AAG用于三维模型的抽象表达。在原有AAM的基础上增加了模型表面、交线等元素的尺寸信息，连同原有AAM所表达的拓扑结构信息，组成模型二维信息集，完整表达模型的拓扑结构与几何信息。

模型信息的自动提取是构建模型信息集的前提，现存三维模型由多款建模软件完成，由于建模方法和数据结构的差异，各类软件无法通过统一的方法直接读取模型信息。不过，各软件模型的表达模式是相对稳定的，当前多数建模软件均支持边界表示（Boundary Representation，B-rep）模型表示。实验中相似度评价所用的模型信息均来自于模型的B-rep表达模式。

模型B-rep表达模式中数据信息的提取，主要有两种方法：基于STEP 中性格式的数据提取和基于模型开发软件的二次开发。采用后者进行模型数据读取，利用软件开发商提供的二次开发函数访问模型，获取模型数据。以Creo软件的Creo Toolkit二次开发工具包为例，其常用二次开发函数，如表1所示。

表1 Creo Toolkit常用函数Tab.1 Commonly Used Functions in Creo Toolkit

2.2 几何元素凹凸性判断方法

几何元素的凹凸性可通过ProGeomitemdataGet 函数获得，结合说明其判断方法，如图2所示。

图2 凹凸性判断模型Fig.2 The Model for Concavity Judgment

模型中的边分为直线、圆弧和一般曲线三类，其凹凸性的判断方法如下：当两面交线为直线时，使用两相交面的夹角判断其凹凸性。在实体侧，若两面夹角小于180°，此交线为凸边，如图中的边d；若两面夹角大于180°，则此交线为凹边，如图中的边c。当两个面交线为圆弧时，若圆弧是凸圆柱面的边，则为凸边，如图中的边a；若圆弧为凹圆柱面的边，则为凹边，如图中的边b。除直线与圆弧之外的交线均视为一般曲线。

模型中的面分为平面、圆柱面和一般曲面三类，其凹凸性判断方法如下：当平面与所有相邻表面的交线均为凸边时，该平面为凸面，如图中的面3；否则为凹面，如图中的面1。当圆柱面的法向量方向指向轴线时，该圆柱面为凹面，如图中的圆柱面4；当圆柱面的法向量方向指向轴线反方向时，该圆柱面为凹面，如图中的圆柱面2。除平面与圆柱面之外的面均视为一般曲面。

2.3 模型拓扑结构矩阵的建立

模型拓扑结构反映了模型面与面之间的位置关系，以及模型中面和交线的主要形状，是首先要表达的模型要素。设模型由k个面组成，其编号依次为1至k，使用AAM表达模型拓扑结构，其对角线元素表示模型的面，非对角线元素表示模型面与面的交线，建立模型拓扑结构矩阵TM如下所示。

式中：元素TMij—模型面（i=j时）或两个面的交线（i≠j时）的几何属性，其取值规则如下：

（1）当i≠j时，TMij(i，j= 1，2，…，k)表示编号为i和j的面的交线的属性，其值取决于线的凹凸性以及交线类型两方面，如式（2）所示。

式中：TM1—交线的凹凸性，其取值，如式（3）所示。

TM2交线的类型，其取值，如式（4）所示。

（2）当i=j时，TMij(i，j= 1，2，…，n)表示TMii(i= 1，2，…，n)，表示编号为i的模型表面的属性值。

当表面为平面时，其值如下所示。

若该面与所有相邻面的交线都是凸边，即式（1）中该面元素所在的行和列均为正数，则TMii=+1；否则TMii=- 1。

当面为曲面时，模型表面的属性值取决于表面的凹凸性和类型，其值如式（6）所示。

式中：TM3—面的凹凸性，其取值如式（7）所示；TM4—面的类型，其取值，如式（8）所示。

2.4 模型尺寸矩阵的建立

模型尺寸反映了模型的次要的几何形状，是模型相似性精确比较过程中不可或缺的因素。与模型拓扑矩阵类似，模型尺寸矩阵采用AAM来表达尺寸参数，对角线元素反映模型表面尺寸属性，非对角线元素反映表面交线尺寸属性，如下所示。

式中：主对角线元素SMii(i= 1，2，…，k)表示模型中编号为i的表面面积，非主对角线元素SMij(i，j= 1，2，…，k，i≠j)表示模型中编号为i和j的面的交线长度，k—模型中表面的数量。

2.5 模型二维信息集

为全面表示模型拓扑结构和尺寸信息，结合前述模型拓扑结构矩阵和尺寸矩阵，建立模型二维信息集如下所示。

式中：TM—模型几何矩阵，其定义如式（1）所示；SM—模型尺寸矩阵，其定义如式（9）所示。采用基于B-rep模式的模型信息提取方法遍历模型得到式（10），其基本流程如下：首先提取模型表面信息，包括ID、面积、凹凸性等基本属性；遍历模型表面得到模型所有轮廓线，从而得到模型所有边的集合；识别边所在的两个面，得到边在AAM 中的位置；最后提取模型边的凹凸性、类型及其尺寸等信息生成二维信息集。

3 基于二维信息集的模型相似度评价

基于上述方法，对将要进行相似度评价的源模型和目标模型分别建立二维信息集：InfSetS={TMS，SMS}和InfSetT={TMT，SMT}，完成基础数据信息的提取；分别以两个模型的表面作为顶点独立集，以两顶点独立集之间每对顶点间的相似度作为其权重，构建赋权完全偶图。使用KM算法计算源模型和目标模型间的最优匹配，并评价其相似度。

3.1 源模型与目标模型表面的最优匹配

对源模型和目标模型进行相似度评价，首先要尽可能多的找到两模型间拓扑结构相同或最相似的表面，并建立这些表面间的一一对应关系，即：以最相似为评价标准，对两模型的表面进行最优匹配。将其抽象为赋权完全偶图的最优匹配问题，即：分别以源模型和目标模型的表面作为顶点独立集VS和VT，并以两独立集间每对表面间的相似度为权值建立赋权完全偶图，求其最优匹配，使得匹配中各边的权值和最大。

考虑到两模型存在面的数量不相等的情况，向数量少的顶点独立集添加补充面，以保证偶图中两个独立集中顶点的数量相等，才可能使得偶图中两顶点独立集的匹配为完美匹配。假定源模型的表面数量为m，目标模型的表面数量为n，且m＜n，分别以源模型和目标模型的表面作为顶点独立集建立偶图时，应向目标模型添加n-m个补充面。此时，源模型的顶点独立集，如式（11）所示，目标模型顶点独立集，如式（12）所示。

式中：FSi—源模型的第i个表面；FSm+i—目标模型的第i个补充

表面；FTi—目标模型的第i个表面。

在向模型添加补充面后，添加补充面属性信息并更新其信息集。例如，源模型添加补充面后，其拓扑结构矩阵TMS由式（1）更新至式（13）。

式中：当i≤m且j≤m时，矩阵中元素TMij与矩阵原有元素相同位置不变；当i＞m或j＞m时，矩阵中元素TMij为补充面属性信息，此处TMij= 0。

以模型表面的类型、表面面积、表面临面数以及边数作为参考依据计算源模型表面i和目标模型表面j之间的相似度，其计算公式如下：

式中：ω0—模型表面的类型权值，当表面i与j为同种类型时，ω0=1，反之ω0= 0，模型表面的类型见式（5）～式（8）；ω1—模型表面的面积权值，ω2—邻面数权值，ω3—边数权值，且ω1+ω2+ω3= 1，按照各项因素对模型相似性的影响并结合实验得出当ω1= 0.7，ω2= 0.2，ω3=0.1 时效果较好。Sar—面i与面j的面积相似度，其计算公式，如式（15）所示；Sns—两个面的邻面数相似度，其计算公式，如式（16）所示；Sne—两个面的边数相似度，其计算公式，如式（17）所示。

式中：Ai和Aj—源模型中的第i个面和目标模型中第j个面的面积，其值可通过式（9）中的主对角线元素SMii获得；同理，Vi和Vj、Ei和Ej—源模型中的第i个面和目标模型中第j个面临面数量和边数量，可通过AAG每个顶点的度、式（1）所示模型几何尺寸矩阵第i（j）行中非零的非主对角线元素的个数获得。根据以上构造的两个顶点独立集VS和VT，以及两独立集中各顶点对间的相似度权值，构造赋权完全偶图如下：

式中：VS和VT—由源模型和目标模型构建的顶点独立集，|VS| =|VT|；E(s，t) —两顶点独立集间每对顶点间的边集，其权值ω(st)由式（14）确定。

偶图最优匹配问题通常使用KM算法求解，通过引入可行顶点标号的方法，将偶图最优匹配问题转化为偶图完美匹配下的最大加权匹配。计算由源模型和目标模型构成的赋值完全偶图G=(VS，VT，E(s，t) )的最优匹配的具体实施步骤如下：（1）确定图中各顶点的可行顶点标号（以下简称顶标）。其初始值取值如下：

式中：VS、VT—偶图的两个独立集；ω(s，t)—源模型中的表面s和目标模型中的表面t的相似度权值，满足条件：l(s)+l(t)≥

（2）确定相等子图Gl，并在Gl上任取一匹配M作为初始匹配。相等子图是以El为边集的G的生成子图，满足条件：El={(s，t) ∈E|l(s)+l(t)=ω(s，t)}。

（3）判断：若M饱和VS的每个顶点，则M为最优匹配，输出最优匹配结果；否则在VS中任取一M不饱和顶点u，令顶点u为顶点集S，并建立顶点集W，W←∅。

（4）若NGl（S）=W，更新VS、VT的顶标，其取值，如式（20）～式（21）所示。更新之后以l'代替l，以Gl'代替Gl。

式中：s∈S，t∉W—s从独立集VS已匹配点找，t从独立集VT未匹配点找。

其中，只更新独立集VS已匹配点与独立集VT已匹配点的顶标。

（5）选取t∈NGl(S)W，若t为M饱和的，则说明t已经被匹配，设此t在M中的匹配为(s)，t，将此t加入顶点集W，将与此t匹配的s加入顶点集S，并转到步（4）；若t为M不饱和的，则说明此t可作为可扩路的起点，令P为Gl中的M可扩（u，t）路M←MΔE(P) ，转到（3）。经过以上计算，得到偶图中两顶点独立集FS和FT的最优匹配M，设M中源模型与目标模型的对应关系为：

根据式（22）中的此匹配结果调整目标模型信息集InfSet中两个矩阵中元素的位置，使其每个顶点元素与源模型中相匹配的面具有相同的位置，变换位置后的目标模型信息集如下：

式中：TMT'、SMT'—变换位置后的目标模型几何矩阵和尺寸矩阵。

3.2 两模型总体相似度评价

上文中两模型间表面的最优匹配仅考虑了表面元素的相似度，模型总体相似度的计算将边元素相关信息也考虑进来。

以最优匹配结果所对应的调整后的模型信息集为例说明相似度评价方法，其计算公式如下所示。

式中：Sim—源模型和目标模型的总体相似度；S1—拓扑结构相似度；S2—几何尺寸相似度，ω4、ω5为权值，ω4+ω5= 1，按照各项因素对模型相似性的影响并结合实验得出当ω4= 0.75，ω2= 0.25时效果较好。

拓扑结构相似度S1表示两模型同种几何元素的比例，即一一比较TMS'与TMt'对应位置的元素，若TMS'与TMT'相同位置元素值相同，则表面两模型当前几何元素种类相同。

由于在模型几何矩阵中关于交线的元素重复出现，所以在计算拓扑结构相似度时只考虑所有主对角线元素以及主对角线以上的元素，此时可将模型几何矩阵视为上三角矩阵，拓扑结构相似度S1计算公式，如下所示。

式中：N1—源模型和目标模型几何矩阵的上三角矩阵中相同位置的非零等值元素的个数；N2—目标模型几何矩阵上三角矩阵中非零元素个数。

几何尺寸相似度S2计算相同种类几何元素所对应的尺寸的相似度。仍然将模型尺寸矩阵视为上三角矩阵进行使用，几何尺寸相似度S2的计算公式，如式（26）所示。

式中：n—两模型相同种类几何元素个数，其计算公式，如式（27）所示。LSi—两信息集中相同位置的一组相同类型元素在源模型中的尺寸属性，当元素是面时，尺寸属性为其面积；当元素是边时，尺寸属性为其长度。LTi—表示两信息集中相同位置的一组相同类型元素在目标模型中的尺寸属性，取值同上。

式中：nlS、nlT—源模型与目标模型的直线边的数量；naS、naT—源模型与目标模型的圆弧边的数量；npS、npT—源模型与目标模型的平面的数量；ncS、ncT—源模型与目标模型的圆柱面的数量。

4 实验验证及算法性能比较

为验证算法的有效性，以Creo Toolkit 二次开发包为工具、Microsoft Visual Studio 2015为集成开发环境，基于Creo 4.0平台进行二次开发，提取模型拓扑结构与尺寸信息并评价其相似度。本例使用的源模型与目标模型，如图3所示。以源模型与目标模型A为例详细说明相似度评价方法。

图3 实例模型Fig.3 Case Models

提取源模型原始信息并建立其拓扑结构矩阵与尺寸矩阵，模型原始信息，如图4所示。其矩阵，如式（28）、式（29）所示。同理提取目标模型原始信息并建立其矩阵。

图4 源模型信息提取Fig.4 Source Model Information Extraction

源模型和目标模型的表面数量分别为8和9，故应向源模型添加1个补充面，添加补充面信息后源模型的拓扑结构矩阵与尺寸矩阵，如式（30）、式（31）所示。

分别以源模型和目标模型的表面作为顶点建立偶图，由式（14）计算出两顶点独立集之间每对顶点间的边的权值ω(st) ，计算结果以矩阵形式表示，如式（32）所示。

以上结果表明，偶图的最优匹配为：

FS1↔FT1；FS2↔FT6；FS3↔FT3；FS4↔FT4；

FS5↔FT2；FS6↔FT5；FS7↔FT7；

FS8↔FT8；FS9↔FT9

应对目标模型拓扑结构矩阵和尺寸矩阵中的第2行（列）与第5 行（列）、第5 行（列）与第6 行（列）进行行列交换，结果如式（33）、（34）所示。

根据式（24）求得源模型与目标模型A的相似度为0.71。以同样方法求得其他模型间的相似度，如表2所示。

表2 相似度求解结果Tab.2 Model Similarity

为验证文中算法的性能，使用文中算法与文献［9］提出的方法进行对比，评价模型的相似度。采用工作站Intel（R）Xeon（R）CPU E5-2630 v3@2.40GHz（64.0GB内存）作为本算法实验平台，筛选了1000个常见Creo模型作为测试模型库，选取其中一个模型作为源模型，以文中前述的相似度评价方法求解模型库中其余模型与源模型的相似度。在耗时量方面，文中算法为两部分：模型信息预处理耗时与相似度计算耗时。其中，模型信息预处理包括文件读取、模型数据读取、信息集矩阵建立等运算，其耗时量占比较大。

文中算法为每个模型创建信息集，信息集完成后，后续可对其多次使用，而无需每次使用时重新处理模型；文献［9］所述方法由于缺少信息储存介质，每次使用模型时都需要重新提取模型信息。不同算法的耗时量比较，可以看出文中算法在未进行模型信息预处理时耗时量较大，而在完成模型预处理后运算耗时量明显减小，如表3所示。

表3 不同算法的耗时量比较Tab.3 Comparison of Time Consumption

用查准率-查全率曲线对两种算法进行对比，其实验结果，如图5所示。可以看出在查全率较低的情况下文中算法与对比算法的查准率差距不大，当查全率高于0.5时文中算法的查准率较对比算法有较明显提升，这是因为文中算法综合考虑了模型表面和边的形状以及几何因素对其相似度的影响，提升了模型表面间相似性计算的准确性。综合考虑运算时间与查准率-查全率曲线，文中算法虽然在未建立信息集时的运算时间较长，但在数据的重复利用方面文中算法有一定的优势，在查全率较高的时候文中算法的查准率也有所提升。

图5 RP曲线Fig.5 RP Curve

5 结论

通过建立二维信息集完成对CAD模型的拓扑结构与几何尺寸的表达，分别以两个模型的表面建立顶点独立集，并以每对表面的相似度作为权重，构建赋权完全偶图，通过使用KM算法得到图的最优匹配，以得到两模型相似度最高的面的对应关系，然后再考虑两模型的边对相似度结果的影响，最终评价两模型整体相似度。与传统的CAD模型相似度评价方法相比较，文中方法做出了以下改进：

（1）在模型信息提取的基础上，创建了一种模型信息集，在传统AAG只能表达模型拓扑结构信息的基础之上，通过模型拓扑结构矩阵和模型尺寸矩阵完善了模型信息的表达，实现了CAD模型特征的准确识别与相似度评价，推动了从单纯几何形状检索向基于模型语义的模型相似度评价的转换。

（2）应用图论中有关匹配问题的相关算法，通过添加补充面，建立了模型的相似度评价算法，可完成差异较大的模型间的评价，降低了对参与评价的源模型与目标模型之间的适用性要求，提高了模型相似度评价的普适性。