汪大涵 王裴巖 張桂平 馬偉芳

(沈陽航空航天大學計算機學院 遼寧 沈陽 110136) (遼寧省知識工程與人機交互工程技術(shù)研究中心 遼寧 沈陽 110136)

0 引 言

隨著CAD/CAM技術(shù)的發(fā)展和廣泛應(yīng)用，企業(yè)積累的產(chǎn)品三維CAD模型數(shù)量急速增長，其凝聚了企業(yè)的設(shè)計成果與智慧結(jié)晶，已成為企業(yè)核心競爭力的重要智力資源?；跀?shù)字化模型的產(chǎn)品設(shè)計與制造已經(jīng)成為目前主流的制造模式。研究及統(tǒng)計表明：新產(chǎn)品研發(fā)中，只有約20%是完全新的設(shè)計，而剩余約80%都是重用已有的部件設(shè)計或是對其做微小的修改[1]。因此，三維CAD模型聚類問題的重要性日益凸顯。目前國內(nèi)外對該方面的研究依然少見，國外有在三維網(wǎng)格模型基礎(chǔ)上獲取其圖像，也有通過點云技術(shù)對模型進行特征獲取。但這些方法都不適用于獲取三維CAD模型的關(guān)鍵特征，即局部區(qū)域特征。

基于局部區(qū)域特征對CAD模型的類別區(qū)分影響較強，因此基于B-rep形式表示的方法通用于三維CAD模型的表示，以便于對局部結(jié)構(gòu)的分析。計算機中經(jīng)常使用圖等非線性結(jié)構(gòu)來表征CAD模型的拓撲結(jié)構(gòu)，此時圖中的結(jié)點屬性信息與邊屬性信息便可代表模型的幾何屬性信息。因此，模型間的相似評價可轉(zhuǎn)換為圖的匹配問題，典型工作有：基于屬性鄰接圖[2-3]、Reed圖[4]、骨架圖[5-6]及擴展特征樹[7]的三維CAD模型相似評價算法。傳統(tǒng)聚類方法受限于對特征描述符線性化的要求，因此無法對以上表達方法形成有效聚類?；谝晥D的三維CAD模型描述，特別是Chen等[8]提出的光場描述子(LFD)在三維CAD模型的研究領(lǐng)域取得了較好的效果。基于局部的模型特征描述方法近年來備受關(guān)注。Tao等[9-10]提出基于區(qū)域分割的局部特征描述的方法。Li等[11]提出一種基于幾何推理的CAD模型層次表征方法。這些方法雖然可以增強模型局部細節(jié)的區(qū)別能力，但在進行相似性比較時需要進行大量的局部結(jié)構(gòu)的匹配與計算，效率較低。

聚類分析方法在數(shù)學領(lǐng)域發(fā)展中較為成熟，但由于三維CAD模型自身的特殊性，因此研究方法不多。現(xiàn)有方法也都是借鑒了傳統(tǒng)的聚類方法。文獻[12-14]分別依據(jù)不同的特征描述子，采用K-means算法實現(xiàn)CAD模型聚類。這些基于K-means聚類算法的模型庫劃分方法簡單、易于實現(xiàn)，但其聚類結(jié)果對初始聚類中心的選擇較為敏感，且易陷入局部最優(yōu)，因此劃分效果并不理想。文獻[15]在層次聚類算法的基礎(chǔ)上，提出了一種自動終止及融合離群點識別的模型庫聚類方法，在模型庫離群數(shù)據(jù)的識別處理及自動終止條件方面進行了改進。有學者提出采用神經(jīng)網(wǎng)絡(luò)的方法來完成模型聚類，如:基于自組織特征映射網(wǎng)絡(luò)的機械三維CAD模型的聚類方法[16-17]；李山等[18]提出的基于ART2網(wǎng)絡(luò)的三維模型聚類方法。這些方法降低了聚類結(jié)果對模型數(shù)據(jù)維數(shù)、數(shù)據(jù)規(guī)模及輸入模型數(shù)據(jù)順序的敏感度，但其網(wǎng)絡(luò)收斂時間通常較長，效率較低，且聚類效果受網(wǎng)絡(luò)的參數(shù)影響較大，而目前參數(shù)的選取還沒有普適的理論依據(jù)和方法[18]。

為了使得模型能夠準確聚類，需從兩方面考慮，一是增強三維CAD模型的表達能力;二是面向三維CAD模型特征表達的聚類算法。而在模型表達方面，拓撲結(jié)構(gòu)、幾何形狀是三維CAD模型最為本質(zhì)的2種屬性，分別反映了模型內(nèi)各個子部分之間的結(jié)構(gòu)關(guān)系及模型的形狀信息，要完整而準確地表征三維CAD模型，兩者缺一不可。

針對現(xiàn)有聚類算法未能適應(yīng)于CAD模型局部區(qū)域的重要程度不同對模型類別的影響，本文提出計算模型的局部區(qū)域權(quán)重，并結(jié)合嚴重依賴權(quán)重信息的加權(quán)譜聚類算法(Weighted Spectra Clustering,WSC)對CAD模型聚類，該方法首先為出現(xiàn)頻次較低但對模型區(qū)分能力強的局部區(qū)域賦予較大權(quán)重，對常見局部區(qū)域給予較小權(quán)重，促使嚴重依賴權(quán)重信息的加權(quán)譜聚類算法性能提高。從最終聚類效果上看，本文所提出的加權(quán)譜聚類算法可以使得具有相同工程意義的模型正確聚類數(shù)目增加，為三維CAD模型聚類研究工作做出了突破性貢獻。

1 算法概述

利用基于STEP文件為三維CAD模型的存儲格式，對該文件進行拓撲與幾何關(guān)系分析后，以B-Rep[19]形式實現(xiàn)對模型進行表達。根據(jù)模型中邊的凹凸屬性將模型分割為若干局部區(qū)域，利用譜圖理論對模型的局部區(qū)域進行向量化表示。本文提出對現(xiàn)有的局部區(qū)域特征信息實現(xiàn)擴展，即統(tǒng)計邊類型屬性信息作為重要特征以增強局部區(qū)域的區(qū)別能力。借鑒圖像領(lǐng)域思想，將若干局部區(qū)域特征形成詞袋[19](Bag-of-word,BoW)，即相似的局部區(qū)域用同一描述符表示。最后利用基于局部區(qū)域特征構(gòu)成的詞袋進行三維CAD模型重組。為解決現(xiàn)有的方法所得到的聚類結(jié)果服從模型間共有多個局部區(qū)域則相似度大的問題，本文提出基于局部區(qū)域的加權(quán)譜聚類算法。該算法增大了含有強區(qū)分度的局部區(qū)域的模型間相似度，使得加權(quán)譜聚類算法性能得以提升。本文算法的整體框架如圖1所示。

圖1 算法總體框架圖

2 局部區(qū)域特征表示

2.1 基本概念

本文將三維CAD模型統(tǒng)一表示為屬性鄰接矩陣形式。對模型進行特征提取過程中，為了對比模型間表征，屬性鄰接矩陣與屬性鄰接圖概念間相互轉(zhuǎn)化，下面給出了本文用到的一些名詞基本定義。

定義1屬性鄰接矩陣。屬性鄰接矩陣是三維CAD模型中面與面間連接與否所形成的特殊結(jié)構(gòu)。其中，矩陣的對角線部分為面的所屬類型名稱，矩陣的上下三角部分為面與面間相交所成邊的類型屬性值。如三維CAD模型墊片可轉(zhuǎn)化為鄰接矩陣Z，其墊片的第i平面可表示為Zii=10，其中，1表示該面類型為平面，0表示該面為內(nèi)表面。第i個平面與第j個圓柱面所形成的圓形邊可表示為Zij=20，其中，2表示為該相交邊為圓形邊，0表示該邊為凹邊。對于屬性鄰接圖，圖的節(jié)點代表模型的面，圖的邊代表面與面相交所成邊。

定義3詞匯本。詞匯本可以映射為由局部特征描述子所組成的字典(借鑒BoW思想)。如：詞匯本={A：[1，10，5，42，…]，B：[2，6，8，11，25，60，…]，C：[3，4，16，18，…]，…} ，其中，字典中的值列表表示相似的局部區(qū)域特征組成的集合，字典中的鍵(描述符)A、B、C、…表示相似局部區(qū)域特征集合的統(tǒng)一表征。最終的CAD模型將利用詞匯本中的描述符重組表示。

定義4單元項。局部特征描述子中的每元特征屬性稱為“單元項”，例如面總數(shù)就是一個單元項。

2.2 模型分割獲得局部區(qū)域

以B-Rep表示形式的三維CAD模型為信息輸入源，通過對模型的面類型、邊類型數(shù)據(jù)進行分析與整理，可以獲得目前可計算的面類型信息包括:平面、圓柱面、圓錐面、球面、其他曲面等，對應(yīng)面與面相交所成的邊類型信息都包括直線、圓弧、橢圓、圓、雙曲線、拋物線、其他曲線等。具體地，兩個同樣的面以不同形式相交可以形成不同的邊類型，例如：平面與圓柱面既可以相交為直線，也可以相交為圓、圓弧等。根據(jù)相交成不同的邊類型，并結(jié)合面與面間的幾何運算判斷其凹凸性，給予最終定義值。例如：平面與圓柱面相交所成直線為凹性，其值定義為10，若所交直線為凸性，其值定義為11;若所交曲線為凹性圓，其值定義為20，若為凸性圓，其值定義為21。依據(jù)該定義原則，最終所有的模型都將轉(zhuǎn)化為屬性鄰接矩陣表示形式。

圖2 CAD模型分割

2.3 局部區(qū)域特征提取及詞匯本構(gòu)建

借鑒文獻[19]中的詞匯本構(gòu)建方法，本文在其局部特征描述子基礎(chǔ)上進行了屬性擴展，即融合邊屬性作為又一重要特征加入其中，使得局部區(qū)域間區(qū)別能力增強。

邊類型信息統(tǒng)計方法與面類型統(tǒng)計方法相同，其中面類型頻次直方圖首先獲知子圖中每個節(jié)點的類型。統(tǒng)計后，形成向量形式(1-平面，2-圓柱面，3-球面，4-圓錐面，5-其他曲面)；統(tǒng)計邊類型頻次直方圖時依然如此，由18種邊類型信息得到18維向量，表示為B。

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

由于前述模型分割得到的是面面相互鄰接、具有一定工程意義的局部區(qū)域。因此詞匯本中各描述符將代表CAD模型的各典型局部區(qū)域集合，較現(xiàn)有基于基點[23]和基于局部視圖[24]的三維模型詞袋表征方式，其描述的意義更為明確。

3 面向三維CAD模型的加權(quán)譜聚類

3.1 三維CAD模型局部區(qū)域加權(quán)

為增強BoW表征對局部區(qū)域拓撲關(guān)系的敏感性，文獻[19]提出融合空間鄰接關(guān)系的CAD模型表示方法。此方法雖然簡單、易表示，但忽視了高區(qū)分度局部區(qū)域?qū)δＰ偷念悇e歸屬影響較大。如圖3所示，在將模型a、b、c分割后會形成1號、2號、3號、4號局部區(qū)域，原有的算法在將模型重組后，模型a、b共同具有1號與2號兩個局部區(qū)域，模型a與c共同具有2號、3號和4號三個局部區(qū)域。當采用傳統(tǒng)的模型表達方法將模型聚成兩類時，則會將模型a與模型c聚成一類,而實則應(yīng)將模型a與模型b聚成一類。

圖3 基于局部區(qū)域加權(quán)的三維CAD模型

針對該問題，本文提出基于局部區(qū)域加權(quán)的表示方法，將模型a與b中具有高區(qū)分度的1號局部區(qū)域給予較大的權(quán)重，同時給予較為常見的2、3、4號局部區(qū)域較小的權(quán)重，最終進行重組后便會得到模型a與b的相似度較大，與模型c的相似度較小。依然借鑒圖譜理論實現(xiàn)由無向圖Gi的節(jié)點總數(shù)v、邊總數(shù)e、最大度dmax、最小度dmin、節(jié)點類型直方圖h(長度根據(jù)詞匯本大小而定)、模型的局部區(qū)域權(quán)重信息之和q乘以模型的幾何形狀屬性信息,以及代表拓撲結(jié)構(gòu)信息的譜向量p以形成該模型的向量化表示形式：

式中：qi為第i個局部區(qū)域的影響因子(即權(quán)重)，局部區(qū)域的權(quán)重計算依賴詞匯本中每個值列表數(shù)量所占總局部區(qū)域數(shù)量的比例，從大到小排列，局部區(qū)域數(shù)量占據(jù)總數(shù)量所得的最小比例的描述符將被賦予最大比例值。相反，占據(jù)最大比例的描述符將被給予最小比例值。以此類推，保證權(quán)重總和為1。

3.2 加權(quán)譜聚類算法

傳統(tǒng)聚類算法[26-28]在處理相對簡單、表示形式單一的數(shù)據(jù)集時都會取得不錯的聚類效果。但對三維CAD模型進行聚類時，若某一單元項帶有噪聲，就會引起聚類中心的偏移，最終影響數(shù)據(jù)集中部分模型所聚類別模糊或錯誤。譜聚類算法[29]在面對維度大、單位項較多的CAD模型時表現(xiàn)效果相對較好，且強烈依賴無向圖中邊的權(quán)重(即數(shù)據(jù)間相似度)。該算法默認計算所有數(shù)據(jù)與數(shù)據(jù)間的相似度，并利用Ncut算法對相似度較小的數(shù)據(jù)進行分割，最終形成若干子數(shù)據(jù)集，其中的任一子數(shù)據(jù)集內(nèi)部權(quán)重值之和保證全局最大，避免了傳統(tǒng)算法由于類中心的偏差給數(shù)據(jù)集造成聚類類別錯誤情況。

由譜聚類算法可知，在聚類過程中其主要注意點為相似矩陣的生成方式，以及切圖的方式。而WSC方法將針對CAD模型數(shù)據(jù)集在切圖環(huán)節(jié)給予全局調(diào)優(yōu)，使得聚類結(jié)果收斂于全局最優(yōu)解。

(1)

(2)

(3)

圖4 模型加權(quán)演示

4 實 驗

本文實驗所用數(shù)據(jù)集來自制造云網(wǎng)站，共包含371個常見且具有代表性三維CAD模型，經(jīng)分割得到1 949個局部區(qū)域。同時根據(jù)已有數(shù)據(jù)集標準設(shè)定最終的聚類類別為61類。初步聚類部分類別效果，如圖5所示。由可視化效果發(fā)現(xiàn)對三維CAD模型局部區(qū)域的研究對模型最終的類別歸屬尤為重要。

圖5 聚類效果圖

4.1 評價標準

評判聚類結(jié)果的好壞需要從多個方面考慮，本文選用針對三維CAD模型聚類方法中較為權(quán)威的兩個評價指標作為本文數(shù)據(jù)集聚類效果的評價標準。

標準化互信息(NMI)：指兩個隨機變量間關(guān)聯(lián)程度，收斂于[0,1]之間。

(4)

同質(zhì)性與完整性的調(diào)和平均數(shù)(V-measure)：

(5)

式中：h表示同質(zhì)性；c表示完整性。

4.2 實驗內(nèi)容及分析

本文在聚類方法的選擇上做了大量實驗對比，其中，數(shù)據(jù)表中算法名稱已經(jīng)進行了簡化，如：k-means、模糊均值聚類、層次聚類、譜聚類已分別簡寫為K、FCM、HC、SC。且在對首次聚類以形成詞匯本中，局部區(qū)域集合的描述符個數(shù)K進行迭代實驗之前，所選取的K值均為5。

對于分割后的局部特征描述子表示已經(jīng)對其進行屬性信息的擴展，即加入特征邊屬性以得到更有區(qū)別度的局部區(qū)域。以下的實驗均在融合邊屬性信息描述子基礎(chǔ)上獲得。

4.2.1相似度計算方法的選擇

在得到融合邊信息的局部特征描述子之后，需要選擇一種較優(yōu)的相似度計算方法實現(xiàn)距離計算，以便生成細粒度高的詞匯本。三種相似度計算方法實驗效果對比如表1所示。

表1 相似度計算方法對比

可以看出，選擇歐氏距離作為相似度計算方法相對較好，且在運行過程中效率最高。其主要原因在于，融合邊信息的局部特征描述子表示形式維度一致，對模型的多種角度分析較為全面。余弦距離與皮爾遜距離計算方法就很不適合本文的模型表示形式。對于余弦距離來講，維度即使不一致，甚至兩者的直線距離可以無窮大，但只要在空間上與圓心坐標軸的夾角一樣，其相似度就為1，很明顯這對于本文實驗對象是不合理的。而皮爾遜距離對本文數(shù)據(jù)集的表示形式影響偏差很大，該算法不考慮兩個向量間重疊的評分項數(shù)量對相似度的影響，故而忽視了本文模型從多角度考慮將局部區(qū)域表達得更完備、更全面，最終導致結(jié)果不佳。而歐氏距離計算方法相對更直觀一些，在本文特征描述子維度一致的基礎(chǔ)上，直接計算其距離，其距離大小便是特征描述子的相似度大小，且計算速度快，面對多維度的特征描述子計算復(fù)雜度低。

4.2.2詞匯本構(gòu)建方法的選擇

文獻[2]中提到，利用凝聚層次聚類對非線性局部特征結(jié)構(gòu)進行聚類效果較好。因此本節(jié)對比k-means與凝聚層次聚類對詞匯本構(gòu)建的影響，實驗效果如表2所示。

表2 詞匯本構(gòu)建方法對比

從數(shù)據(jù)表可以看出，k-means算法對局部特征描述子進行首次聚類以構(gòu)建詞匯本，在最終對CAD模型進行聚類無論選用哪種聚類方法，效果均要好于層次聚類。

結(jié)合層次聚類與k-means算法的原理及本文的CAD模型表示形式分析：在處理表達形式單一的數(shù)據(jù)時，k-means算法要依賴于k個中心值的選擇，如果k的分布相對平均，在計算類中心與每個模型的相似度之后，默認將相似度大的模型劃分到與之最近的類當中，且每迭代一次類別中心點都將優(yōu)化。但該算法對k的選擇還是極為敏感的，若在最初k的選擇上分布不均，就會導致最后的聚類效果只能達到局部最優(yōu)，且一些類為空類。

而層次聚類在處理表達形式單一的數(shù)據(jù)時相對要簡單一些，且看起來更加合理，默認每個數(shù)據(jù)就是一類，將最相似的類之間合并為一個新類，直到達到閾值(最終類別數(shù))。但該算法在處理多元化向量數(shù)據(jù)時，其每一單元項的信息差別較大，最終會導致聚類效果不理想，且所形成的聚類結(jié)果無法改變。而采用k-means算法具有的自動調(diào)優(yōu)功能會將其結(jié)果進一步優(yōu)化，達到相對較好的效果。

詞匯本的構(gòu)建形式不同，會對模型重組影響很大，所以不僅要對第一次聚類方法的選擇作對比，還要對聚類類別的數(shù)量做好分析實驗，迭代出最優(yōu)的k值，方可得到更加細粒度的詞匯本。經(jīng)過對k值的迭代(k取5、10、15、20、25、30)所得到的NMI值如圖6所示。

圖6 迭代k類別收斂效果圖

可以看出，隨著k的取值增大，基于該詞匯本所構(gòu)成的三維CAD模型對于不同的聚類方法得到的效果差異較大。大部分聚類方法表現(xiàn)為k的取值越大，效果越好，對應(yīng)所構(gòu)建的詞匯本細粒度越高，最終對模型的聚類效果越好。但當k值>25時,其結(jié)果開始下降，且實驗過程中出現(xiàn)效率降低現(xiàn)象。因此本文取k=20時，詞匯本的構(gòu)建達到相對較優(yōu)，用于支持下一步實驗。

4.2.3三維CAD模型重組并聚類

利用詞匯本中各代表性描述符，對三維CAD模型進行重組，提出面向局部區(qū)域的加權(quán)譜聚類算法對其進行聚類，各項參數(shù)設(shè)置將采取上述實驗中所得到的相對最優(yōu)方法以支持本節(jié)實驗，結(jié)果如表3所示。實驗結(jié)果表明，本文提出的WSC方法在解決模型類別歸屬問題上得到了改進，最后得到NMI值、V-measure值對比其他聚類方法中的最優(yōu)值分別提升了3.4百分點、3.7百分點。結(jié)果證明，利用CAD模型的局部區(qū)域重要程度不同作為關(guān)鍵特征，能夠促使加權(quán)譜聚類算法性能得到進一步提升，聚類結(jié)果得到改善。

表3 不同聚類算法對比

5 結(jié) 語

現(xiàn)有的聚類算法未能利用CAD模型關(guān)鍵特征進行聚類，即CAD模型的局部區(qū)域?qū)δＰ皖悇e歸屬影響程度不同，本文提出基于局部區(qū)域的加權(quán)譜聚類算法對由局部區(qū)域重組的三維CAD模型進行聚類。該方法對不常見但區(qū)分能力強的局部區(qū)域賦予較大權(quán)重，對常見但對模型類別影響低的局部區(qū)域給予較小權(quán)重。從聚類結(jié)果上看，本文方法明顯好于傳統(tǒng)方法，具有相同工程意義的模型聚到同一類別數(shù)量明顯提高，可有效支持工程設(shè)計人員對CAD模型重用的效率，同時可以證明三維CAD模型的各局部區(qū)域類型出現(xiàn)的頻次不能作為聚類的標準，相對更應(yīng)該注重CAD模型的局部區(qū)域?qū)ζ溆绊懗潭取?/p>

由于部分模型間雖含有不同工程意義的局部區(qū)域特征，但其局部區(qū)域都不常見，導致模型間局部區(qū)域的權(quán)重相差不大，錯聚成一類。下一步將重點針對此問題展開研究，考慮局部區(qū)域間的連接邊信息對整體模型的影響，爭取將不同工程意義的不常見局部區(qū)域進一步區(qū)分開。