面向三維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模型的局部區域對其影響程度。

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