面向三維CAD模型的加權(quán)譜聚類算法研究

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

(沈陽(yáng)航空航天大學(xué)計(jì)算機(jī)學(xué)院 遼寧 沈陽(yáng) 110136) (遼寧省知識(shí)工程與人機(jī)交互工程技術(shù)研究中心 遼寧 沈陽(yáng) 110136)

0 引 言

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

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

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

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

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

1 算法概述

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

圖1 算法總體框架圖

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

2.1 基本概念

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

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

定義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單元項(xiàng)。局部特征描述子中的每元特征屬性稱為“單元項(xiàng)”，例如面總數(shù)就是一個(gè)單元項(xiàng)。

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

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

圖2 CAD模型分割

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

(2)

(3)

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

4 實(shí) 驗(yàn)

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

圖5 聚類效果圖

4.1 評(píng)價(jià)標(biāo)準(zhǔn)

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

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

(4)

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

(5)

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

4.2 實(shí)驗(yàn)內(nèi)容及分析

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

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

4.2.1相似度計(jì)算方法的選擇

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

表1 相似度計(jì)算方法對(duì)比

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

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

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

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

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

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

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

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

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

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

4.2.3三維CAD模型重組并聚類

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

表3 不同聚類算法對(duì)比

5 結(jié) 語(yǔ)

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

由于部分模型間雖含有不同工程意義的局部區(qū)域特征，但其局部區(qū)域都不常見(jiàn)，導(dǎo)致模型間局部區(qū)域的權(quán)重相差不大，錯(cuò)聚成一類。下一步將重點(diǎn)針對(duì)此問(wèn)題展開(kāi)研究，考慮局部區(qū)域間的連接邊信息對(duì)整體模型的影響，爭(zhēng)取將不同工程意義的不常見(jiàn)局部區(qū)域進(jìn)一步區(qū)分開(kāi)。