融合权重信息的三维CAD模型聚类研究

汪大涵，王裴岩，张桂平，马伟芳

(沈阳航空航天大学人机智能研究中心，沈阳110136)

1 引 言

数字化模型产品作为现代制造业的刚需，对其设计的精度与效率的提升已经成为加快工业生产力、促进企业效益的重要环节.研究及统计表明，对于数字化模型新产品研发时，需要完全从新设计的比例占有大约20%的比例，而剩余约80%都是重用已有的模型产品或是在已有的模型上做微小的修改［1］.通过人工进行标签分类最先应用到模型类别划分工作，但由于不同企业的零件标准不同，人工分类的结果常出现不一致问题.同时，随着零件的日益复杂化和零件数量的不断增长，基于人工的分类方式也变得难以使用.因此，对三维CAD 模型聚类问题展开研究的重要性显得日益突出.

目前国内外对该方面得研究至今依然少见，国外有在三维网格模型基础上获取其图像，又有通过点云技术［2］对模型进行特征获取，但这些途经都不适用获取三维CAD 模型的局部关键特征，即局部区域特征.相对而言国内通过对三维CAD 模型的STEP 存储格式进行数据挖掘，可更好的分析模型的关键特征.

针对这部分研究，现主要集中于两个方面，面向聚类的三维CAD 模型的特征表达以及基于特征表达的聚类算法.由于三维CAD 模型是由基本面线构成，因此能表达复杂关系的树与图等结构被用来表达三维CAD 模型中面线的连接与相交等关系.目前有提出将模型表达成属性邻接图［3，4］、Reed图［5］、骨架图［6，7］，也有借助扩展特征树［8］的表达方法.但由于聚类方法［9-11］的局限性，难以实现对非线性特征描述符进行相似度计算，因此基于图的三维CAD 模型库未能形成有效聚类;又有提出基于视图的三维CAD 模型表达方法，白等人［12］提出基于多局部显著视图角度，特别是 Chen 等［13］提出的光场描述子(LFD)在三维CAD 模型的研究领域取得了较好的效果.而对于该表达方法在相似匹配阶段需要在相似评价［14］过程中寻找两模型视图间的最佳匹配，且不能获得有效的特征向量，故现有的聚类方法依然难以完成对模型库的聚类工作.另外，模型的局部区域角度成为了探索三维CAD 模型的重要入口，其更能进一步描述三维模型的细粒度属性.典型工作有 Tao 等［15，16］提出根据 CAD 模型中边的凹凸属性对其进行分割，再对分割后的局部区域统计其属性特征，编码后作为对局部区域的描述.Li 等［17］提出一种基于几何推理的CAD 模型层次表征方法，首先对CAD 模型进行递归分割，再以层次分区图的形式描述模型从整体到局部的特征.屠等人［18］提出基于曲度的局部特征表示方法.这些以局部区域特征来对模型进行描述的方法，虽然其对模型局部细节的区别能力增强，但局限于当时对这部分问题的分析工作不够全面，大量的局部区域特征匹配与计算导致效率极低.最近皇甫等人［19］对局部区域特征方面的研究较好的解决了前述问题，提出基于六元组的表示方法对局部区域进行表达，该方法借鉴谱图理论综合考虑了现有的对模型局部区域进行有效区别的几何形状信息，同时计算出局部区域的拓扑结构信息存入六元组当中，并基于该六元组所构建的词汇本，提出融合空间关系的三维CAD 模型表达方法实现了对模型的重新组合.该种方法解决了传统方法中模型的局部区域间相似度计算困难问题，又保留了模型局部区域的拓扑信息.但基于六元组的描述子对局部区域特征的表达仍不能满足所有零件的特征信息不丢失，导致局部区域间的区别仍然存在问题.

基于上述问题，本文的主要贡献有两点:

1.针对现有的对CAD 模型的向量化局部区域特征描述不全面，本文提出对能够有效区分局部区域的特征进行扩展，记录模型的边属性信息作为又一重要特征描述符加入到局部特征描述子当中，使得对局部区域表达的准确程度得以提升，区别能力增强.

2.经过对三维CAD 模型的分析与研究，发现模型的可重用局部区域对模型的功能影响程度不同，现有的CAD 模型表达方法忽略了模型间虽然共有较少的可重用局部区域，但这些局部区域区分度高且对模型的类别归属影响较强.因此本文提出采用局部区域加权的模型表达方法，该方法强调对三维CAD 模型出现频次较低、区分度高的局部区域赋予较大权重，对常见的局部区域给予较小权重.从最终聚类效果上看，本文所提出的表达方法可以使得模型正确聚类性能提高，为三维CAD 模型聚类研究工作提出了新的思路.

2 本文算法概述

利用基于STEP 文件为三维CAD 模型的存储格式，在对该格式文件进行拓扑与几何关系分析后，将三维CAD 模型用属性邻接图(AAG)来表示［19］，其中模型面、边的属性分别作为AAG 节点和连线的属性.依据AAG 节点与连线的凸凹连续性将AAG 分割为若干子图，各子图对应CAD 模型的局部区域.结合谱图理论统计每个局部区域的几何形状信息与拓扑结构信息，形成向量化局部区域特征描述，其中本文提出对文献［19］的局部区域特征描述信息进一步扩展，既更大程度上保证了模型局部区域几何形状信息不丢失，又保留了模型的拓扑结构.采用此方法得到的若干局部特征描述子映射至词汇本，即相似的局部区域用同一“关键词”表示(如:相似的局部区域1、10、14、30…等用关键词 A 统一表示).统计每个CAD 模型中各关键词出现的频次及结合邻接关系实现对三维CAD 模型重组.为解决部分模型未能按照其局部区域的重要程度不同而进行聚类，本文提出一种基于局部区域加权的模型表达方法，该方法使得模型的最终聚类结果得到进一步提高.图1 所示为本文算法的整体框架.

图1 算法总体框架图Fig.1 Overall framework of algorithm

3 CAD 模型分割及局部区域特征扩展

3.1 CAD 模型分割

图2 CAD 模型分割Fig.2 CAD model segmentation

以B-Rep 表示形式的三维CAD 模型为信息输入源，通过对模型的面类型、边类型数据进行分析与整理，可以获得目前可计算的面类型信息都包括平面、圆柱面、圆锥面、球面、其他曲面等，对应面与面相交所成的边类型信息都包括直线、圆弧、椭圆、圆、双曲线、抛物线、其他曲线等.具体地，两个面以不同形式相交可以形成不同的边类型，例如:平面与圆柱面既可以相交为直线，又可以相交为圆、圆弧等，再根据面与面间的夹角判断边的凹凸性［20］，最终所有的三维模型都将表示为属性邻接矩阵形式，其通过判断模型的面与面间连接与否进行构建，同时记录每个CAD 模型的面属性信息与连接边的属性信息.但由于现有的研究(包括文献［20］)都未能通过几何关系计算出所有的边类型属性，对于未能计算出属性信息的边，本文采用对面与面相交形成的罕见边属性信息自定义值，该值将独一无二的代表此两面相交得到的边属性信息，依据该方法统计得到16 种边属性信息.借鉴文献［20，21］中模型的面与面所相交边的凹凸属性对模型进行分割.据此方法分割所得到的局部区域库中，从数据结果可以看出部分模型被分割成若干可重用局部区域，部分模型未被分割，其本身就为一个独立可重用区域.S=(G'i|i=1，2，…，n)，其中 G'i为局部区域库中第i 个局部区域，S 为若干局部区域组成的集合.分割所得结果如图2 所示.

3.2 基于扩展局部区域特征的词汇本构建

为实现局部区域特征间的快速比较及聚类，以构建词汇本，文献［19］中提出，向量化局部区域特征得到六元组，但依然存在图3 问题.

图3 挡圈问题分析图Fig.3 Problem analysis of“retaining ring”

如模型3.1、3.2 所示，在对模型的面类型信息定义时，面1 统称为平面，面2 统称为圆柱面.文献［19］中对模型的局部区域表示为六元组，其中包括面总数、边总数、最大度、最小度、面类型频次直方图、谱向量.而以上两个模型的区别只是在面总数与边总数上有略微的区别，最大度、最小度以及面类型直方图上会保持一致，在这样的情况下，两个模型的区分度并不高，特征不够明显，两个模型会被错误的聚到同一类.

因此本文提出对局部区域特征实现扩展，即基于扩展的局部特征描述子将考虑边属性信息作为重要描述符加入特征描述子当中，使得模型的局部区域间区分相对明显.例如模型3.1 中面1 与面2 相交所得边既有圆也有圆弧，模型3.2 中面1 与面2 相交所得边只有圆，并没有圆弧.本文将基于边信息的特征直方图融入到局部特征描述子当中，可有效区分两个模型来自于两个类别.

基于扩展的局部特征描述子的具体定义为:将每个局部区域首先抽象为子图G'i，对应将每个子图以七元组形式G'i=＜Vc，Ec，Dmax，Dmin，H，B，A＞进行表示，其中 Vc与 Ec表示子图的节点数和连接边数;Dmax与Dmin分别表示子图节点的最大度与最小度;H 为子图节点类型直方图，通过统计模型的局部区域中每种面所出现的频次，构成5 维向量，其中第1 维表示“平面”，2-圆柱面，3-球面，4-圆锥面，5-其他曲面);B 为子图边类型直方图，统计局部区域中面与面相交所得到的每条边类型出现的频次得到16 维向量，其构建方法与H 相同;A为子图G'i的谱向量［22］，其能够以向量形式描述子图的拓扑结构信息.谱向量的维度依据子图的节点数而不同，计算方法借鉴文献［19］.而描述子中的每个特征单元称为一个“单元项”，例如子图节点总数Vc就是一个单元项.

在对局部区域进行上述方法表示之后，将会得到由若干局部特征描述子组成的集合.因此采用k-means 算法对其进行聚类，以构建由有限(k 个)描述符而映射至k 个类别形成的词汇本.其中，相似度计算方法分别对比了皮尔逊距离、余弦距离、以及欧氏距离，最终采用欧式距离方法.自此词汇本中各描述符将代表三维CAD 模型的各典型局部区域，模型库中的三维CAD 模型将按照其所含有的局部区域对应到词汇本中的描述符进行重组表示.

4 基于局部区域加权的三维CAD 模型聚类

为增强BoW［23］表征对局部区域拓扑关系的敏感性，文献［19］提出融合空间邻接关系的CAD 模型表达方法(CMSBoWs)，此方法虽然简单、易表示，但忽视了一些区别能力强的局部区域对模型类别归属的影响较大.如图4 所示，对模型(a)、(b)、(c)进行分割后会形成 1 号、2 号、3 号、4 号这样的局部区域，其中模型(a)与模型(b)共同具有1 号与2 号两个局部区域，模型(a)与模型(c)共同具有2 号、3 号与4 号三个局部区域，利用CMSBoWs 表达方法将模型聚成两类时，则会将模型(a)与模型(c)聚成一类，而实则应将模型(a)与模型(b)聚成一类.

图4 基于局部区域加权的三维CAD 模型Fig.4 3D CAD model based on local area weighting

针对该问题，本文提出基于局部区域加权的模型表达方法，将模型(a)与模型(b)中出现频次低且具有代表性的1 号局部区域给予较大的权重，同时给予相对常见的2 号、3 号、4号局部区域较小的权重.对模型进行重组后便会得到模型(a)与模型(b)的相似度较大，与模型(c)的相似度较小.依然利用谱图理论实现由无向图Gi的节点总数v、边总数e、最大度/最小度dmax/dmin、加权的节点类型直方图h(长度根据词汇本大小而定)、模型的局部区域权重信息之和q 以及代表拓扑结构信息的谱向量p 组合得到该模型的向量化表示作为CAD 模型的特征描述子:

其中x 为模型i 的某局部区域，TFx 为局部区域x 在该模型中出现的频次;IDFx 为局部区域x 的影响因子(即权重)，其计算方法依据词频-逆文本频率［24］(Term Frequency-Inverse Document Frequency，TF-IDF)原理而得，公式为:

N 为模型总数，N(x)为含有该局部区域x 的模型总数.

5 实验结果与分析

实验中所用模型采集于制造云网站上的三维CAD 模型库，共包含来自61 个模型类别、371 个常见且具有代表性的三维CAD 模型，经分割，得到1949 个局部区域.同时根据已有数据集标准设定最终的聚类类别为61 类，模型聚类的有效性可通过将聚类结果与预先定义好的分类结构进行比较来评定.

5.1 评价标准

本文选用针对三维CAD 模型聚类方法中相对权威的两个评价指标(NMI、V-measure、Purity)做为本文数据集聚类效果的评价标准.

标准化互信息(NMI):常在聚类中，度量两个聚类结果的相近程度，取值范围为［0，1］之间，最接近状态值为1:

其中n 为数据集中样本的类别数.

同质性与完整性的调和平均数(V-measure):

其中h 表示同质性，c 表示完整性.

纯度(purity):正确聚类的数据数量占总数据量的比例，收敛于［0，1］，其值越高效果越好:

其中，Ω={ω1，ω2，…，ωk}，ωk代表第 k 个聚类簇，N 代表总数据数，C={c1，c2，…，cj}是总数据量集合，cj 表示第 j类中的数据.

5.2 实验结果及分析

本节将设置词汇本构建方法对比实验及模型的表达方法对比实验，而在构建词汇本时经过实验迭代k-means 中k 值取 5、10、15、20、25、30 等，并选择相对最优值 k=25 时作为词汇本关键词数量(即局部区域数量)以支持下一步实验.对每种表达方法得到的聚类结果进行分析，论述本文方法对比文献［19］方法所做出的贡献.

5.2.1 词汇本构建方法对比

词汇本构建方法对比实验比较本文所提出的基于扩展的局部特征描述子(baseline+边)与文献［19］的六元组表示法(baseline)所获得的词汇本对模型聚类效果的影响.此部分实验，局部区域采用文献［19］的非加权方法表达，聚类算法分别采用k-means(K)、模糊均值聚类(FCM)、层次聚类(HC)与谱聚类(SC)，并对四种聚类算法各迭代30 次，分别统计两种表达方法在每种聚类算法上得到的相对最优聚类效果，实验结果如表1 所示.

表1 词汇本构建方法对比实验Table 1 Comparative experiment of vocabulary construction methods

经过四种聚类算法所得到NMI 值、V-measure 值、Purity值可以看出，基于本文提出的方法在k-means、FCM、HC 三种聚类算法上所得到的三项指标值均好于baseline 方法.而经过SC 聚类算法得到的NMI 值、Purity 值对比baseline 方法均有所提高，V-measure 值有所下降，该结果表示当聚类数量较多时，对类别数敏感的SC 算法所得的聚类结果的同质性与完整性受到影响，即每个类别参杂其他类别的模型数量有所增加，且给定类的所有模型经过SC 算法后模型类别分布相对分散.即使如此，NMI 值与Purity 值依然分别提升了0.04、0.02，表示数据分布的吻合程度相对乐观.在仔细观察模型的聚类效果后发现，本文方法得到的聚类结果更满足工程设计人员对模型的重用需求，对“挡圈”模型与“垫圈”模型实现了有效区分，如图5 所示.综上可以证明本文提出基于扩展的局部特征描述子对模型的局部区域表达相比优于baseline 方法.

图5 “挡圈”模型与“垫圈”模型Fig.5 Retaining ring”model and“washer”model

5.2.2 基于局部区域加权的三维CAD 模型聚类实验

模型的表达方法对比实验比较本文所提出的局部区域加权方法与文献［19］的未加权方法.为了说明本文提出的方法对模型表达能力增强，此部分实验共对比了三种描述子构建方法，即文献［19］方法所得描述子(baseline)、文献［19］结合本文提出的局部区域加权法(baseline+权重)、融合文献［19］+本文提出的词汇本构建方法+本文提出的局部区域加权法(baseline+边+权重).聚类算法分别采用k-means(K)、模糊均值聚类(FCM)、层次聚类(HC)与谱聚类(SC)，对四种算法各迭代30 次，分别记录两种表达方法在每种聚类算法上得到的相对最优聚类效果.

通过观察经SC 算法所得到的聚类结果，本文提出的方法在解决部分模型划分类别错误问题上得到了改善，使得功能相同的模型正确划分到同一类别数量明显增加，大大减少了由于模型的共有局部区域较多而被错误聚类的数量.在四种典型聚类算法上得到的三项指标值对比baseline 方法所得到的聚类结果均略有提升.其中，本文提出的baseline+边+权重方法在K-means 算法、FCM 算法、HC 算法上表现的效果较好，NMI 值对比 baseline 分别提高了 0.01、0.05、0.02，Purity 值分别提高了 0.05、0.09、0.04;本文提出的 baseline+权重方法在SC 算法上表现效果较好，其NMI 值对比baseline 提高了0.06，Purity 值提高了0.03.更具体地，本文所提出的方法得到的聚类结果中，将带有不常见但对类别划分区别能力强的局部区域如锯齿状局部区域、螺钉状局部区域、螺母状局部区域等的CAD 模型正确聚类数目提高.

可以证明，CAD 模型的聚类研究有必要考虑局部区域的重要程度不同，给予CAD 模型的局部区域相应的权重，可以有效增强模型间区分度.实验结果如表2 所示.

而本文提出的baseline+权重方法在SC 算法上得到的三项指标高于baseline+边+权重方法，主要由于baseline+边方法所得到的词汇本细粒度变高，词汇本中各个关键词对应的相似局部区域集合数量更均匀，因此当采用此方法获得的词汇本中的关键词对CAD 模型进行重组，计算重组后的模型中各个关键词对应的权重值相差幅度较小.而未加边属性信息所获得的词汇本中各关键词对应的权重值相差较大.SC算法忽略了词汇本细粒度增强的优势，它首先将CAD 模型库构建全连接相似度矩阵(即图结构)，再利用Ncut 算法对该全连接图进行切分得到各个簇，其Ncut 算法严重依赖全连接图边的权重信息，因此baseline+权重方法在SC 算法上得到的聚类结果相比baseline+边+权重方法更优.

表2 模型表达方法对比实验Table 2 Model expression method comparison experiment

5.3 聚类结果对比分析

图6 为文献［19］提出的模型表达方法经过SC 聚类算法得到的部分聚类结果实例;图7 为本文提出的方法(baseline+边+权重)经过SC 聚类算法得到的部分聚类结果实例.

图6 文献［17］方法所得部分聚类结果Fig.6 Partial clustering results of literature［17］

图7 本文方法所得部分聚类结果Fig.7 Clustering results of the method in this paper

由可视化的聚类结果可知，本文方法所得到的聚类结果更注重局部区域的重要性不同对模型类别归属的影响.从文献［19］得到的聚类结果可以看出，簇1 与簇3 主要为“专用螺母”与“组合件用螺母”，但每个类别仍然参杂着其他类别中的模型，如带有红框模型便为不属于该类别的模型.而本文的方法所得到的聚类结果可有效将“专用螺母”与“不脱出螺钉”正确区分到簇1 与簇2 两个类别;正确区分“螺钉组合件”与“组合件用螺母”到簇3 与簇4.同时本文方法所得到的聚类结果簇5 对比文献［19］的簇4，充分证明了本文提出的方法提高了模型间的区分度，使得聚类结果有所提高.对于工程应用方面也增加了工程设计人员对该类模型重用时的可选择项，即本文方法得到的聚类结果更符合工程设计人员的要求.

6 总 结

本文对三维CAD 模型聚类问题的研究主要将重心放在了模型的表达上.而模型的局部区域的区分又是正确识别模型类别的关键，针对现有的对局部区域向量化表示不完整、一些由于边属性信息未能识别，从而导致模型的局部区域间区别能力有限，本文提出对局部区域特征进行扩展，即记录特征边属性信息与传统局部特征描述子相融合，使得对局部区域的表达得到完善.又为了解决一些含有高区分度局部区域的模型未能实现正确聚类，本文提出了基于局部区域加权的模型表达方法，该方法强调对模型的出现频次较少、区分度高的局部区域赋予较大权重，对常见的局部区域给予较小权重.从多种聚类算法所得结果上看，本文提出的方法明显好于已有方法，具有相同功能的模型被聚到同一类别数量明显增加，证明了本文的方法有效区分CAD 模型的关键特征的重要程度，可提高工程设计领域对三维CAD 模型重用的效率.