面向三维CAD模型的加权谱聚类算法研究

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

(沈阳航空航天大学计算机学院 辽宁 沈阳 110136) (辽宁省知识工程与人机交互工程技术研究中心 辽宁 沈阳 110136)

0 引 言

随着CAD/CAM技术的发展和广泛应用，企业积累的产品三维CAD模型数量急速增长，其凝聚了企业的设计成果与智慧结晶，已成为企业核心竞争力的重要智力资源。基于数字化模型的产品设计与制造已经成为目前主流的制造模式。研究及统计表明：新产品研发中，只有约20%是完全新的设计，而剩余约80%都是重用已有的部件设计或是对其做微小的修改[1]。因此，三维CAD模型聚类问题的重要性日益凸显。目前国内外对该方面的研究依然少见，国外有在三维网格模型基础上获取其图像，也有通过点云技术对模型进行特征获取。但这些方法都不适用于获取三维CAD模型的关键特征，即局部区域特征。

基于局部区域特征对CAD模型的类别区分影响较强，因此基于B-rep形式表示的方法通用于三维CAD模型的表示，以便于对局部结构的分析。计算机中经常使用图等非线性结构来表征CAD模型的拓扑结构，此时图中的结点属性信息与边属性信息便可代表模型的几何属性信息。因此，模型间的相似评价可转换为图的匹配问题，典型工作有：基于属性邻接图[2-3]、Reed图[4]、骨架图[5-6]及扩展特征树[7]的三维CAD模型相似评价算法。传统聚类方法受限于对特征描述符线性化的要求，因此无法对以上表达方法形成有效聚类。基于视图的三维CAD模型描述，特别是Chen等[8]提出的光场描述子(LFD)在三维CAD模型的研究领域取得了较好的效果。基于局部的模型特征描述方法近年来备受关注。Tao等[9-10]提出基于区域分割的局部特征描述的方法。Li等[11]提出一种基于几何推理的CAD模型层次表征方法。这些方法虽然可以增强模型局部细节的区别能力，但在进行相似性比较时需要进行大量的局部结构的匹配与计算，效率较低。

聚类分析方法在数学领域发展中较为成熟，但由于三维CAD模型自身的特殊性，因此研究方法不多。现有方法也都是借鉴了传统的聚类方法。文献[12-14]分别依据不同的特征描述子，采用K-means算法实现CAD模型聚类。这些基于K-means聚类算法的模型库划分方法简单、易于实现，但其聚类结果对初始聚类中心的选择较为敏感，且易陷入局部最优，因此划分效果并不理想。文献[15]在层次聚类算法的基础上，提出了一种自动终止及融合离群点识别的模型库聚类方法，在模型库离群数据的识别处理及自动终止条件方面进行了改进。有学者提出采用神经网络的方法来完成模型聚类，如:基于自组织特征映射网络的机械三维CAD模型的聚类方法[16-17]；李山等[18]提出的基于ART2网络的三维模型聚类方法。这些方法降低了聚类结果对模型数据维数、数据规模及输入模型数据顺序的敏感度，但其网络收敛时间通常较长，效率较低，且聚类效果受网络的参数影响较大，而目前参数的选取还没有普适的理论依据和方法[18]。

为了使得模型能够准确聚类，需从两方面考虑，一是增强三维CAD模型的表达能力;二是面向三维CAD模型特征表达的聚类算法。而在模型表达方面，拓扑结构、几何形状是三维CAD模型最为本质的2种属性，分别反映了模型内各个子部分之间的结构关系及模型的形状信息，要完整而准确地表征三维CAD模型，两者缺一不可。

针对现有聚类算法未能适应于CAD模型局部区域的重要程度不同对模型类别的影响，本文提出计算模型的局部区域权重，并结合严重依赖权重信息的加权谱聚类算法(Weighted Spectra Clustering,WSC)对CAD模型聚类，该方法首先为出现频次较低但对模型区分能力强的局部区域赋予较大权重，对常见局部区域给予较小权重，促使严重依赖权重信息的加权谱聚类算法性能提高。从最终聚类效果上看，本文所提出的加权谱聚类算法可以使得具有相同工程意义的模型正确聚类数目增加，为三维CAD模型聚类研究工作做出了突破性贡献。

1 算法概述

利用基于STEP文件为三维CAD模型的存储格式，对该文件进行拓扑与几何关系分析后，以B-Rep[19]形式实现对模型进行表达。根据模型中边的凹凸属性将模型分割为若干局部区域，利用谱图理论对模型的局部区域进行向量化表示。本文提出对现有的局部区域特征信息实现扩展，即统计边类型属性信息作为重要特征以增强局部区域的区别能力。借鉴图像领域思想，将若干局部区域特征形成词袋[19](Bag-of-word,BoW)，即相似的局部区域用同一描述符表示。最后利用基于局部区域特征构成的词袋进行三维CAD模型重组。为解决现有的方法所得到的聚类结果服从模型间共有多个局部区域则相似度大的问题，本文提出基于局部区域的加权谱聚类算法。该算法增大了含有强区分度的局部区域的模型间相似度，使得加权谱聚类算法性能得以提升。本文算法的整体框架如图1所示。

图1 算法总体框架图

2 局部区域特征表示

2.1 基本概念

本文将三维CAD模型统一表示为属性邻接矩阵形式。对模型进行特征提取过程中，为了对比模型间表征，属性邻接矩阵与属性邻接图概念间相互转化，下面给出了本文用到的一些名词基本定义。

定义1属性邻接矩阵。属性邻接矩阵是三维CAD模型中面与面间连接与否所形成的特殊结构。其中，矩阵的对角线部分为面的所属类型名称，矩阵的上下三角部分为面与面间相交所成边的类型属性值。如三维CAD模型垫片可转化为邻接矩阵Z，其垫片的第i平面可表示为Zii=10，其中，1表示该面类型为平面，0表示该面为内表面。第i个平面与第j个圆柱面所形成的圆形边可表示为Zij=20，其中，2表示为该相交边为圆形边，0表示该边为凹边。对于属性邻接图，图的节点代表模型的面，图的边代表面与面相交所成边。

定义3词汇本。词汇本可以映射为由局部特征描述子所组成的字典(借鉴BoW思想)。如：词汇本={A：[1，10，5，42，…]，B：[2，6，8，11，25，60，…]，C：[3，4，16，18，…]，…} ，其中，字典中的值列表表示相似的局部区域特征组成的集合，字典中的键(描述符)A、B、C、…表示相似局部区域特征集合的统一表征。最终的CAD模型将利用词汇本中的描述符重组表示。

定义4单元项。局部特征描述子中的每元特征属性称为“单元项”，例如面总数就是一个单元项。

2.2 模型分割获得局部区域

以B-Rep表示形式的三维CAD模型为信息输入源，通过对模型的面类型、边类型数据进行分析与整理，可以获得目前可计算的面类型信息包括:平面、圆柱面、圆锥面、球面、其他曲面等，对应面与面相交所成的边类型信息都包括直线、圆弧、椭圆、圆、双曲线、抛物线、其他曲线等。具体地，两个同样的面以不同形式相交可以形成不同的边类型，例如：平面与圆柱面既可以相交为直线，也可以相交为圆、圆弧等。根据相交成不同的边类型，并结合面与面间的几何运算判断其凹凸性，给予最终定义值。例如：平面与圆柱面相交所成直线为凹性，其值定义为10，若所交直线为凸性，其值定义为11;若所交曲线为凹性圆，其值定义为20，若为凸性圆，其值定义为21。依据该定义原则，最终所有的模型都将转化为属性邻接矩阵表示形式。

图2 CAD模型分割

2.3 局部区域特征提取及词汇本构建

借鉴文献[19]中的词汇本构建方法，本文在其局部特征描述子基础上进行了属性扩展，即融合边属性作为又一重要特征加入其中，使得局部区域间区别能力增强。

边类型信息统计方法与面类型统计方法相同，其中面类型频次直方图首先获知子图中每个节点的类型。统计后，形成向量形式(1-平面，2-圆柱面，3-球面，4-圆锥面，5-其他曲面)；统计边类型频次直方图时依然如此，由18种边类型信息得到18维向量，表示为B。

最终得到的扩展局部特征描述子表示形式如下：

由于前述模型分割得到的是面面相互邻接、具有一定工程意义的局部区域。因此词汇本中各描述符将代表CAD模型的各典型局部区域集合，较现有基于基点[23]和基于局部视图[24]的三维模型词袋表征方式，其描述的意义更为明确。

3 面向三维CAD模型的加权谱聚类

3.1 三维CAD模型局部区域加权

为增强BoW表征对局部区域拓扑关系的敏感性，文献[19]提出融合空间邻接关系的CAD模型表示方法。此方法虽然简单、易表示，但忽视了高区分度局部区域对模型的类别归属影响较大。如图3所示，在将模型a、b、c分割后会形成1号、2号、3号、4号局部区域，原有的算法在将模型重组后，模型a、b共同具有1号与2号两个局部区域，模型a与c共同具有2号、3号和4号三个局部区域。当采用传统的模型表达方法将模型聚成两类时，则会将模型a与模型c聚成一类,而实则应将模型a与模型b聚成一类。

图3 基于局部区域加权的三维CAD模型

针对该问题，本文提出基于局部区域加权的表示方法，将模型a与b中具有高区分度的1号局部区域给予较大的权重，同时给予较为常见的2、3、4号局部区域较小的权重，最终进行重组后便会得到模型a与b的相似度较大，与模型c的相似度较小。依然借鉴图谱理论实现由无向图Gi的节点总数v、边总数e、最大度dmax、最小度dmin、节点类型直方图h(长度根据词汇本大小而定)、模型的局部区域权重信息之和q乘以模型的几何形状属性信息,以及代表拓扑结构信息的谱向量p以形成该模型的向量化表示形式：

式中：qi为第i个局部区域的影响因子(即权重)，局部区域的权重计算依赖词汇本中每个值列表数量所占总局部区域数量的比例，从大到小排列，局部区域数量占据总数量所得的最小比例的描述符将被赋予最大比例值。相反，占据最大比例的描述符将被给予最小比例值。以此类推，保证权重总和为1。

3.2 加权谱聚类算法

传统聚类算法[26-28]在处理相对简单、表示形式单一的数据集时都会取得不错的聚类效果。但对三维CAD模型进行聚类时，若某一单元项带有噪声，就会引起聚类中心的偏移，最终影响数据集中部分模型所聚类别模糊或错误。谱聚类算法[29]在面对维度大、单位项较多的CAD模型时表现效果相对较好，且强烈依赖无向图中边的权重(即数据间相似度)。该算法默认计算所有数据与数据间的相似度，并利用Ncut算法对相似度较小的数据进行分割，最终形成若干子数据集，其中的任一子数据集内部权重值之和保证全局最大，避免了传统算法由于类中心的偏差给数据集造成聚类类别错误情况。

由谱聚类算法可知，在聚类过程中其主要注意点为相似矩阵的生成方式，以及切图的方式。而WSC方法将针对CAD模型数据集在切图环节给予全局调优，使得聚类结果收敛于全局最优解。

(1)

(2)

(3)

图4 模型加权演示

4 实 验

本文实验所用数据集来自制造云网站，共包含371个常见且具有代表性三维CAD模型，经分割得到1 949个局部区域。同时根据已有数据集标准设定最终的聚类类别为61类。初步聚类部分类别效果，如图5所示。由可视化效果发现对三维CAD模型局部区域的研究对模型最终的类别归属尤为重要。

图5 聚类效果图

4.1 评价标准

评判聚类结果的好坏需要从多个方面考虑，本文选用针对三维CAD模型聚类方法中较为权威的两个评价指标作为本文数据集聚类效果的评价标准。

标准化互信息(NMI)：指两个随机变量间关联程度，收敛于[0,1]之间。

(4)

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

(5)

式中：h表示同质性；c表示完整性。

4.2 实验内容及分析

本文在聚类方法的选择上做了大量实验对比，其中，数据表中算法名称已经进行了简化，如：k-means、模糊均值聚类、层次聚类、谱聚类已分别简写为K、FCM、HC、SC。且在对首次聚类以形成词汇本中，局部区域集合的描述符个数K进行迭代实验之前，所选取的K值均为5。

对于分割后的局部特征描述子表示已经对其进行属性信息的扩展，即加入特征边属性以得到更有区别度的局部区域。以下的实验均在融合边属性信息描述子基础上获得。

4.2.1相似度计算方法的选择

在得到融合边信息的局部特征描述子之后，需要选择一种较优的相似度计算方法实现距离计算，以便生成细粒度高的词汇本。三种相似度计算方法实验效果对比如表1所示。

表1 相似度计算方法对比

可以看出，选择欧氏距离作为相似度计算方法相对较好，且在运行过程中效率最高。其主要原因在于，融合边信息的局部特征描述子表示形式维度一致，对模型的多种角度分析较为全面。余弦距离与皮尔逊距离计算方法就很不适合本文的模型表示形式。对于余弦距离来讲，维度即使不一致，甚至两者的直线距离可以无穷大，但只要在空间上与圆心坐标轴的夹角一样，其相似度就为1，很明显这对于本文实验对象是不合理的。而皮尔逊距离对本文数据集的表示形式影响偏差很大，该算法不考虑两个向量间重叠的评分项数量对相似度的影响，故而忽视了本文模型从多角度考虑将局部区域表达得更完备、更全面，最终导致结果不佳。而欧氏距离计算方法相对更直观一些，在本文特征描述子维度一致的基础上，直接计算其距离，其距离大小便是特征描述子的相似度大小，且计算速度快，面对多维度的特征描述子计算复杂度低。

4.2.2词汇本构建方法的选择

文献[2]中提到，利用凝聚层次聚类对非线性局部特征结构进行聚类效果较好。因此本节对比k-means与凝聚层次聚类对词汇本构建的影响，实验效果如表2所示。

表2 词汇本构建方法对比

从数据表可以看出，k-means算法对局部特征描述子进行首次聚类以构建词汇本，在最终对CAD模型进行聚类无论选用哪种聚类方法，效果均要好于层次聚类。

结合层次聚类与k-means算法的原理及本文的CAD模型表示形式分析：在处理表达形式单一的数据时，k-means算法要依赖于k个中心值的选择，如果k的分布相对平均，在计算类中心与每个模型的相似度之后，默认将相似度大的模型划分到与之最近的类当中，且每迭代一次类别中心点都将优化。但该算法对k的选择还是极为敏感的，若在最初k的选择上分布不均，就会导致最后的聚类效果只能达到局部最优，且一些类为空类。

而层次聚类在处理表达形式单一的数据时相对要简单一些，且看起来更加合理，默认每个数据就是一类，将最相似的类之间合并为一个新类，直到达到阈值(最终类别数)。但该算法在处理多元化向量数据时，其每一单元项的信息差别较大，最终会导致聚类效果不理想，且所形成的聚类结果无法改变。而采用k-means算法具有的自动调优功能会将其结果进一步优化，达到相对较好的效果。

词汇本的构建形式不同，会对模型重组影响很大，所以不仅要对第一次聚类方法的选择作对比，还要对聚类类别的数量做好分析实验，迭代出最优的k值，方可得到更加细粒度的词汇本。经过对k值的迭代(k取5、10、15、20、25、30)所得到的NMI值如图6所示。

图6 迭代k类别收敛效果图

可以看出，随着k的取值增大，基于该词汇本所构成的三维CAD模型对于不同的聚类方法得到的效果差异较大。大部分聚类方法表现为k的取值越大，效果越好，对应所构建的词汇本细粒度越高，最终对模型的聚类效果越好。但当k值>25时,其结果开始下降，且实验过程中出现效率降低现象。因此本文取k=20时，词汇本的构建达到相对较优，用于支持下一步实验。

4.2.3三维CAD模型重组并聚类

利用词汇本中各代表性描述符，对三维CAD模型进行重组，提出面向局部区域的加权谱聚类算法对其进行聚类，各项参数设置将采取上述实验中所得到的相对最优方法以支持本节实验，结果如表3所示。实验结果表明，本文提出的WSC方法在解决模型类别归属问题上得到了改进，最后得到NMI值、V-measure值对比其他聚类方法中的最优值分别提升了3.4百分点、3.7百分点。结果证明，利用CAD模型的局部区域重要程度不同作为关键特征，能够促使加权谱聚类算法性能得到进一步提升，聚类结果得到改善。

表3 不同聚类算法对比

5 结 语

现有的聚类算法未能利用CAD模型关键特征进行聚类，即CAD模型的局部区域对模型类别归属影响程度不同，本文提出基于局部区域的加权谱聚类算法对由局部区域重组的三维CAD模型进行聚类。该方法对不常见但区分能力强的局部区域赋予较大权重，对常见但对模型类别影响低的局部区域给予较小权重。从聚类结果上看，本文方法明显好于传统方法，具有相同工程意义的模型聚到同一类别数量明显提高，可有效支持工程设计人员对CAD模型重用的效率，同时可以证明三维CAD模型的各局部区域类型出现的频次不能作为聚类的标准，相对更应该注重CAD模型的局部区域对其影响程度。

由于部分模型间虽含有不同工程意义的局部区域特征，但其局部区域都不常见，导致模型间局部区域的权重相差不大，错聚成一类。下一步将重点针对此问题展开研究，考虑局部区域间的连接边信息对整体模型的影响，争取将不同工程意义的不常见局部区域进一步区分开。