汪大涵 王裴巖 張桂平 馬偉芳
(沈陽航空航天大學(xué)計(jì)算機(jī)學(xué)院 遼寧 沈陽 110136) (遼寧省知識(shí)工程與人機(jī)交互工程技術(shù)研究中心 遼寧 沈陽 110136)
隨著CAD/CAM技術(shù)的發(fā)展和廣泛應(yīng)用,企業(yè)積累的產(chǎn)品三維CAD模型數(shù)量急速增長,其凝聚了企業(yè)的設(shè)計(jì)成果與智慧結(jié)晶,已成為企業(yè)核心競爭力的重要智力資源?;跀?shù)字化模型的產(chǎn)品設(shè)計(jì)與制造已經(jīng)成為目前主流的制造模式。研究及統(tǒng)計(jì)表明:新產(chǎn)品研發(fā)中,只有約20%是完全新的設(shè)計(jì),而剩余約80%都是重用已有的部件設(shè)計(jì)或是對其做微小的修改[1]。因此,三維CAD模型聚類問題的重要性日益凸顯。目前國內(nèi)外對該方面的研究依然少見,國外有在三維網(wǎng)格模型基礎(chǔ)上獲取其圖像,也有通過點(diǎn)云技術(shù)對模型進(jìn)行特征獲取。但這些方法都不適用于獲取三維CAD模型的關(guān)鍵特征,即局部區(qū)域特征。
基于局部區(qū)域特征對CAD模型的類別區(qū)分影響較強(qiáng),因此基于B-rep形式表示的方法通用于三維CAD模型的表示,以便于對局部結(jié)構(gòu)的分析。計(jì)算機(jī)中經(jīng)常使用圖等非線性結(jié)構(gòu)來表征CAD模型的拓?fù)浣Y(jié)構(gòu),此時(shí)圖中的結(jié)點(diǎn)屬性信息與邊屬性信息便可代表模型的幾何屬性信息。因此,模型間的相似評(píng)價(jià)可轉(zhuǎn)換為圖的匹配問題,典型工作有:基于屬性鄰接圖[2-3]、Reed圖[4]、骨架圖[5-6]及擴(kuò)展特征樹[7]的三維CAD模型相似評(píng)價(jià)算法。傳統(tǒng)聚類方法受限于對特征描述符線性化的要求,因此無法對以上表達(dá)方法形成有效聚類。基于視圖的三維CAD模型描述,特別是Chen等[8]提出的光場描述子(LFD)在三維CAD模型的研究領(lǐng)域取得了較好的效果?;诰植康哪P吞卣髅枋龇椒ń陙韨涫荜P(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聚類算法的模型庫劃分方法簡單、易于實(shí)現(xiàn),但其聚類結(jié)果對初始聚類中心的選擇較為敏感,且易陷入局部最優(yōu),因此劃分效果并不理想。文獻(xiàn)[15]在層次聚類算法的基礎(chǔ)上,提出了一種自動(dòng)終止及融合離群點(diǎn)識(shí)別的模型庫聚類方法,在模型庫離群數(shù)據(jù)的識(shí)別處理及自動(dòng)終止條件方面進(jìn)行了改進(jìn)。有學(xué)者提出采用神經(jīng)網(wǎng)絡(luò)的方法來完成模型聚類,如:基于自組織特征映射網(wǎng)絡(luò)的機(jī)械三維CAD模型的聚類方法[16-17];李山等[18]提出的基于ART2網(wǎng)絡(luò)的三維模型聚類方法。這些方法降低了聚類結(jié)果對模型數(shù)據(jù)維數(shù)、數(shù)據(jù)規(guī)模及輸入模型數(shù)據(jù)順序的敏感度,但其網(wǎng)絡(luò)收斂時(shí)間通常較長,效率較低,且聚類效果受網(wǎng)絡(luò)的參數(shù)影響較大,而目前參數(shù)的選取還沒有普適的理論依據(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模型,兩者缺一不可。
針對現(xiàn)有聚類算法未能適應(yīng)于CAD模型局部區(qū)域的重要程度不同對模型類別的影響,本文提出計(jì)算模型的局部區(qū)域權(quán)重,并結(jié)合嚴(yán)重依賴權(quán)重信息的加權(quán)譜聚類算法(Weighted Spectra Clustering,WSC)對CAD模型聚類,該方法首先為出現(xiàn)頻次較低但對模型區(qū)分能力強(qiáng)的局部區(qū)域賦予較大權(quán)重,對常見局部區(qū)域給予較小權(quán)重,促使嚴(yán)重依賴權(quán)重信息的加權(quán)譜聚類算法性能提高。從最終聚類效果上看,本文所提出的加權(quán)譜聚類算法可以使得具有相同工程意義的模型正確聚類數(shù)目增加,為三維CAD模型聚類研究工作做出了突破性貢獻(xiàn)。
利用基于STEP文件為三維CAD模型的存儲(chǔ)格式,對該文件進(jìn)行拓?fù)渑c幾何關(guān)系分析后,以B-Rep[19]形式實(shí)現(xiàn)對模型進(jìn)行表達(dá)。根據(jù)模型中邊的凹凸屬性將模型分割為若干局部區(qū)域,利用譜圖理論對模型的局部區(qū)域進(jìn)行向量化表示。本文提出對現(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ū)域則相似度大的問題,本文提出基于局部區(qū)域的加權(quán)譜聚類算法。該算法增大了含有強(qiáng)區(qū)分度的局部區(qū)域的模型間相似度,使得加權(quán)譜聚類算法性能得以提升。本文算法的整體框架如圖1所示。
圖1 算法總體框架圖
本文將三維CAD模型統(tǒng)一表示為屬性鄰接矩陣形式。對模型進(jìn)行特征提取過程中,為了對比模型間表征,屬性鄰接矩陣與屬性鄰接圖概念間相互轉(zhuǎn)化,下面給出了本文用到的一些名詞基本定義。
定義1屬性鄰接矩陣。屬性鄰接矩陣是三維CAD模型中面與面間連接與否所形成的特殊結(jié)構(gòu)。其中,矩陣的對角線部分為面的所屬類型名稱,矩陣的上下三角部分為面與面間相交所成邊的類型屬性值。如三維CAD模型墊片可轉(zhuǎn)化為鄰接矩陣Z,其墊片的第i平面可表示為Zii=10,其中,1表示該面類型為平面,0表示該面為內(nèi)表面。第i個(gè)平面與第j個(gè)圓柱面所形成的圓形邊可表示為Zij=20,其中,2表示為該相交邊為圓形邊,0表示該邊為凹邊。對于屬性鄰接圖,圖的節(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)。
以B-Rep表示形式的三維CAD模型為信息輸入源,通過對模型的面類型、邊類型數(shù)據(jù)進(jìn)行分析與整理,可以獲得目前可計(jì)算的面類型信息包括:平面、圓柱面、圓錐面、球面、其他曲面等,對應(yīng)面與面相交所成的邊類型信息都包括直線、圓弧、橢圓、圓、雙曲線、拋物線、其他曲線等。具體地,兩個(gè)同樣的面以不同形式相交可以形成不同的邊類型,例如:平面與圓柱面既可以相交為直線,也可以相交為圓、圓弧等。根據(jù)相交成不同的邊類型,并結(jié)合面與面間的幾何運(yùn)算判斷其凹凸性,給予最終定義值。例如:平面與圓柱面相交所成直線為凹性,其值定義為10,若所交直線為凸性,其值定義為11;若所交曲線為凹性圓,其值定義為20,若為凸性圓,其值定義為21。依據(jù)該定義原則,最終所有的模型都將轉(zhuǎn)化為屬性鄰接矩陣表示形式。
圖2 CAD模型分割
借鑒文獻(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]的三維模型詞袋表征方式,其描述的意義更為明確。
為增強(qiáng)BoW表征對局部區(qū)域拓?fù)潢P(guān)系的敏感性,文獻(xiàn)[19]提出融合空間鄰接關(guān)系的CAD模型表示方法。此方法雖然簡單、易表示,但忽視了高區(qū)分度局部區(qū)域?qū)δP偷念悇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模型
針對該問題,本文提出基于局部區(qū)域加權(quán)的表示方法,將模型a與b中具有高區(qū)分度的1號(hào)局部區(qū)域給予較大的權(quán)重,同時(shí)給予較為常見的2、3、4號(hào)局部區(qū)域較小的權(quán)重,最終進(jìn)行重組后便會(huì)得到模型a與b的相似度較大,與模型c的相似度較小。依然借鑒圖譜理論實(shí)現(xiàn)由無向圖Gi的節(jié)點(diǎn)總數(shù)v、邊總數(shù)e、最大度dmax、最小度dmin、節(jié)點(diǎn)類型直方圖h(長度根據(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。
傳統(tǒng)聚類算法[26-28]在處理相對簡單、表示形式單一的數(shù)據(jù)集時(shí)都會(huì)取得不錯(cuò)的聚類效果。但對三維CAD模型進(jìn)行聚類時(shí),若某一單元項(xiàng)帶有噪聲,就會(huì)引起聚類中心的偏移,最終影響數(shù)據(jù)集中部分模型所聚類別模糊或錯(cuò)誤。譜聚類算法[29]在面對維度大、單位項(xiàng)較多的CAD模型時(shí)表現(xiàn)效果相對較好,且強(qiáng)烈依賴無向圖中邊的權(quán)重(即數(shù)據(jù)間相似度)。該算法默認(rèn)計(jì)算所有數(shù)據(jù)與數(shù)據(jù)間的相似度,并利用Ncut算法對相似度較小的數(shù)據(jù)進(jìn)行分割,最終形成若干子數(shù)據(jù)集,其中的任一子數(shù)據(jù)集內(nèi)部權(quán)重值之和保證全局最大,避免了傳統(tǒng)算法由于類中心的偏差給數(shù)據(jù)集造成聚類類別錯(cuò)誤情況。
由譜聚類算法可知,在聚類過程中其主要注意點(diǎn)為相似矩陣的生成方式,以及切圖的方式。而WSC方法將針對CAD模型數(shù)據(jù)集在切圖環(huán)節(jié)給予全局調(diào)優(yōu),使得聚類結(jié)果收斂于全局最優(yōu)解。
(1)
(2)
(3)
圖4 模型加權(quán)演示
本文實(shí)驗(yàn)所用數(shù)據(jù)集來自制造云網(wǎng)站,共包含371個(gè)常見且具有代表性三維CAD模型,經(jīng)分割得到1 949個(gè)局部區(qū)域。同時(shí)根據(jù)已有數(shù)據(jù)集標(biāo)準(zhǔn)設(shè)定最終的聚類類別為61類。初步聚類部分類別效果,如圖5所示。由可視化效果發(fā)現(xiàn)對三維CAD模型局部區(qū)域的研究對模型最終的類別歸屬尤為重要。
圖5 聚類效果圖
評(píng)判聚類結(jié)果的好壞需要從多個(gè)方面考慮,本文選用針對三維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表示完整性。
本文在聚類方法的選擇上做了大量實(shí)驗(yàn)對比,其中,數(shù)據(jù)表中算法名稱已經(jīng)進(jìn)行了簡化,如:k-means、模糊均值聚類、層次聚類、譜聚類已分別簡寫為K、FCM、HC、SC。且在對首次聚類以形成詞匯本中,局部區(qū)域集合的描述符個(gè)數(shù)K進(jìn)行迭代實(shí)驗(yàn)之前,所選取的K值均為5。
對于分割后的局部特征描述子表示已經(jīng)對其進(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)效果對比如表1所示。
表1 相似度計(jì)算方法對比
可以看出,選擇歐氏距離作為相似度計(jì)算方法相對較好,且在運(yùn)行過程中效率最高。其主要原因在于,融合邊信息的局部特征描述子表示形式維度一致,對模型的多種角度分析較為全面。余弦距離與皮爾遜距離計(jì)算方法就很不適合本文的模型表示形式。對于余弦距離來講,維度即使不一致,甚至兩者的直線距離可以無窮大,但只要在空間上與圓心坐標(biāo)軸的夾角一樣,其相似度就為1,很明顯這對于本文實(shí)驗(yàn)對象是不合理的。而皮爾遜距離對本文數(shù)據(jù)集的表示形式影響偏差很大,該算法不考慮兩個(gè)向量間重疊的評(píng)分項(xiàng)數(shù)量對相似度的影響,故而忽視了本文模型從多角度考慮將局部區(qū)域表達(dá)得更完備、更全面,最終導(dǎo)致結(jié)果不佳。而歐氏距離計(jì)算方法相對更直觀一些,在本文特征描述子維度一致的基礎(chǔ)上,直接計(jì)算其距離,其距離大小便是特征描述子的相似度大小,且計(jì)算速度快,面對多維度的特征描述子計(jì)算復(fù)雜度低。
4.2.2詞匯本構(gòu)建方法的選擇
文獻(xiàn)[2]中提到,利用凝聚層次聚類對非線性局部特征結(jié)構(gòu)進(jìn)行聚類效果較好。因此本節(jié)對比k-means與凝聚層次聚類對詞匯本構(gòu)建的影響,實(shí)驗(yàn)效果如表2所示。
表2 詞匯本構(gòu)建方法對比
從數(shù)據(jù)表可以看出,k-means算法對局部特征描述子進(jìn)行首次聚類以構(gòu)建詞匯本,在最終對CAD模型進(jìn)行聚類無論選用哪種聚類方法,效果均要好于層次聚類。
結(jié)合層次聚類與k-means算法的原理及本文的CAD模型表示形式分析:在處理表達(dá)形式單一的數(shù)據(jù)時(shí),k-means算法要依賴于k個(gè)中心值的選擇,如果k的分布相對平均,在計(jì)算類中心與每個(gè)模型的相似度之后,默認(rèn)將相似度大的模型劃分到與之最近的類當(dāng)中,且每迭代一次類別中心點(diǎn)都將優(yōu)化。但該算法對k的選擇還是極為敏感的,若在最初k的選擇上分布不均,就會(huì)導(dǎo)致最后的聚類效果只能達(dá)到局部最優(yōu),且一些類為空類。
而層次聚類在處理表達(dá)形式單一的數(shù)據(jù)時(shí)相對要簡單一些,且看起來更加合理,默認(rèn)每個(gè)數(shù)據(jù)就是一類,將最相似的類之間合并為一個(gè)新類,直到達(dá)到閾值(最終類別數(shù))。但該算法在處理多元化向量數(shù)據(jù)時(shí),其每一單元項(xiàng)的信息差別較大,最終會(huì)導(dǎo)致聚類效果不理想,且所形成的聚類結(jié)果無法改變。而采用k-means算法具有的自動(dòng)調(diào)優(yōu)功能會(huì)將其結(jié)果進(jìn)一步優(yōu)化,達(dá)到相對較好的效果。
詞匯本的構(gòu)建形式不同,會(huì)對模型重組影響很大,所以不僅要對第一次聚類方法的選擇作對比,還要對聚類類別的數(shù)量做好分析實(shí)驗(yàn),迭代出最優(yōu)的k值,方可得到更加細(xì)粒度的詞匯本。經(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)建的詞匯本細(xì)粒度越高,最終對模型的聚類效果越好。但當(dāng)k值>25時(shí),其結(jié)果開始下降,且實(shí)驗(yàn)過程中出現(xiàn)效率降低現(xiàn)象。因此本文取k=20時(shí),詞匯本的構(gòu)建達(dá)到相對較優(yōu),用于支持下一步實(shí)驗(yàn)。
4.2.3三維CAD模型重組并聚類
利用詞匯本中各代表性描述符,對三維CAD模型進(jìn)行重組,提出面向局部區(qū)域的加權(quán)譜聚類算法對其進(jìn)行聚類,各項(xiàng)參數(shù)設(shè)置將采取上述實(shí)驗(yàn)中所得到的相對最優(yōu)方法以支持本節(jié)實(shí)驗(yàn),結(jié)果如表3所示。實(shí)驗(yàn)結(jié)果表明,本文提出的WSC方法在解決模型類別歸屬問題上得到了改進(jìn),最后得到NMI值、V-measure值對比其他聚類方法中的最優(yōu)值分別提升了3.4百分點(diǎn)、3.7百分點(diǎn)。結(jié)果證明,利用CAD模型的局部區(qū)域重要程度不同作為關(guān)鍵特征,能夠促使加權(quán)譜聚類算法性能得到進(jìn)一步提升,聚類結(jié)果得到改善。
表3 不同聚類算法對比
現(xiàn)有的聚類算法未能利用CAD模型關(guān)鍵特征進(jìn)行聚類,即CAD模型的局部區(qū)域?qū)δP皖悇e歸屬影響程度不同,本文提出基于局部區(qū)域的加權(quán)譜聚類算法對由局部區(qū)域重組的三維CAD模型進(jìn)行聚類。該方法對不常見但區(qū)分能力強(qiáng)的局部區(qū)域賦予較大權(quán)重,對常見但對模型類別影響低的局部區(qū)域給予較小權(quán)重。從聚類結(jié)果上看,本文方法明顯好于傳統(tǒng)方法,具有相同工程意義的模型聚到同一類別數(shù)量明顯提高,可有效支持工程設(shè)計(jì)人員對CAD模型重用的效率,同時(shí)可以證明三維CAD模型的各局部區(qū)域類型出現(xiàn)的頻次不能作為聚類的標(biāo)準(zhǔn),相對更應(yīng)該注重CAD模型的局部區(qū)域?qū)ζ溆绊懗潭取?/p>
由于部分模型間雖含有不同工程意義的局部區(qū)域特征,但其局部區(qū)域都不常見,導(dǎo)致模型間局部區(qū)域的權(quán)重相差不大,錯(cuò)聚成一類。下一步將重點(diǎn)針對此問題展開研究,考慮局部區(qū)域間的連接邊信息對整體模型的影響,爭取將不同工程意義的不常見局部區(qū)域進(jìn)一步區(qū)分開。