基于粒子群優(yōu)化的三維CAD模型相似性評價*

韓文軍 張 蘇 李達鋒 姚明昇

（1.國網(wǎng)經(jīng)濟技術(shù)研究院有限公司 北京 102209）（2.北京博超時代軟件有限公司 北京 102209）

1 引言

隨著CAD/CAM等數(shù)字化產(chǎn)品發(fā)展，大量三維CAD模型成果得以累積，統(tǒng)計表明，產(chǎn)品結(jié)構(gòu)更新時只有約20%為全新設(shè)計，而80%其他設(shè)計可以通過重用或局部修改來完成［1］，因此，如何從海量產(chǎn)品的模型庫中挖掘并重用典型結(jié)構(gòu)有利于提高開發(fā)效率。

模型典型結(jié)構(gòu)檢索方法提供了全新的技術(shù)方式，已成為近年研究熱點，其主要通過設(shè)計一套有效的匹配算法，在三維CAD模型庫中搜索含有與需求結(jié)構(gòu)具有最優(yōu)相似度的模型用以設(shè)計重用。張?zhí)飼龋?］將推理方法與設(shè)計知識相結(jié)合，提高典型模具的設(shè)計效率和重用率；張開興等［3］利用屬性鄰接圖建立關(guān)聯(lián)圖，通過模擬退火算法檢索關(guān)聯(lián)圖中的最大主團完成相關(guān)結(jié)構(gòu)的挖掘和相似評價；劉志等［4］通過視點集渲染模型的輪廓線視圖，并構(gòu)建Gabor變換響應(yīng)特征庫實現(xiàn)相似模型檢索；白靜等［5］用屬性圖統(tǒng)一表示模型的非線性特征，采用非線性層次聚類算法對屬性圖進行聚類。Kim等［6］以自由草圖進行建模，對分辨率模型進行形狀分布比較來提高模型的形狀檢索精度；Tao等［7］根據(jù)模型面的鄰接關(guān)系將模型分為不同區(qū)域并編碼，通過編碼比較來度量兩模型的相似性；皇甫中民等［8］以B-Re表示中的屬性信息構(gòu)建鄰接圖，并用圖譜方法描述模型的局部特征，采用兩層搜索方法檢索模型的典型結(jié)構(gòu)。

模型重用中，模型相似性計算起著重要的作用，直接關(guān)系到模型中典型結(jié)構(gòu)檢索的效率和可靠性［9］，為此，在前人研究基礎(chǔ)上，文中利用模型面組成邊數(shù)差異，以此構(gòu)建模型的面相似性評價矩陣，然后以粒子群算法來搜索矩陣中的的最優(yōu)面匹配序列，通過最段匹配序列實現(xiàn)對源模型和目標模型的相似性進行評價，為三維CAD模型中主模型結(jié)構(gòu)的智能化檢索和有效重用提供依據(jù)。

2 模型面相似矩陣構(gòu)建

三維CAD模型通常由面元素組成，面元素形狀的差異，形成了模型的千差萬別，因此通過累積兩個模型間的面相似情況，可以得到重用前模型的相似情況［10］。如果組成兩個面的邊的數(shù)目相差較小，則兩模型存在較高的相似度；反之則有較低的相似度。如圖1所示為描述模型的面相似性使用的模型示例，圖中模型A包含u1，u2，…，u7七個面，其中面u1與u5，u6，u2，u7四個面相鄰接，則面u1的組成邊數(shù)為4，同理可以得到，面u2，u3，u4，u5的組成邊數(shù)為4，而面u6，u7的組成邊數(shù)為5。則圖1中兩個示例模型的相似度可以通過式（1）來計算，即

式中，N(u)表示某模型的面u含有的組成邊數(shù)，max(·)表示取最大值。

圖1 模型面相似計算示例

式（1）說明當 S(ui，vj)值越大，說明兩個面的邊數(shù)N(ui)與N(vj)差異越小，兩個面的形狀越相似，使用S(ui，vj)可以構(gòu)造待評價兩模型的面相似度評價矩陣SAB，兩模型的面序列分別為矩陣的行和列。

式中，m和n分別表示待評價的兩模型的面數(shù)，為便于后續(xù)相似性分析，如果兩模型面數(shù)不一致，則當m＞n時，將SAB進行轉(zhuǎn)置處理。

組成兩模型的面的相似度影響著兩個模型的相似性，兩模型之間的面相似度越高，兩模型之間的相似性越高［13］。根據(jù)式（1）和式（2），圖1兩模型中，u1，u2，…，u5與 v1，v2，…，v5分別與另外四個面相鄰接，因此 SAB中其對應(yīng)的相似度值為1，而u6，u7與 v6，v7分別與5個面相鄰接，其與其他面之間相似度值為0.8，從而得到圖1中兩模型的面相似性評介矩陣為

3 基于粒子群算法的模型面匹配

兩模型的組成面相似度越高，則模型相似度也越高［12］，為此以面相似矩陣，通過粒子群算法來匹配兩模型之間的面最優(yōu)匹序列，進而評價相似情況。

設(shè)算法在d維空間進行最優(yōu)匹配搜索，種群規(guī)模為 p，xt為粒子t所在的位置，vt為粒子t的飛行速度，和表示算法經(jīng)過k次迭代后全局和粒子個體的最優(yōu)位置，相應(yīng)的適應(yīng)度函數(shù)分別表示為和。算法在實現(xiàn)過程中通過和不斷迭代更新和實現(xiàn)最優(yōu)匹配序列的搜索，其過程為［13］

式中，k為當前迭代數(shù)，w為慣性因子，c1和c2為算法優(yōu)化的學(xué)習(xí)因子，r1和r2在迭代過程中在[0，1]內(nèi)隨機取值。設(shè)粒子t在SAB中的位置向量為 xt=(j(1)，j(2)，…，j(m))，則其適應(yīng)度函數(shù)計算式為

式中，j(i)為模型A中第i(i=1，2，…，m)個面經(jīng)粒子群算法得到模型中的最優(yōu)匹配面。

4 實驗驗證分析

為驗證文提出算法的有效性，以O(shè)pen CASCADE為平臺構(gòu)造幾何造型，選取普渡大學(xué)的ESB模 型 庫［14］中 的 部 分 模 型 ，在 Inte（R）Core?i5-7400HQ CPU，4G內(nèi)存的計算機硬件下進行實驗。

4.1 算法有效性實驗

如表5所示為以典型盤形結(jié)構(gòu)為實驗源模型，文中算法與基于網(wǎng)絡(luò)本體語言（Wol-Sim）［11］和基于蟻群算法（Acs-Sim）［15］的模型相似性評價算法在ESB模型庫中進行相似性模型搜索實驗結(jié)果，從表中結(jié)果可以看出，相對于基于蟻群算法的相似性評價方法，文中算法通過搜索兩模型的最優(yōu)匹配序列，從而可以搜索到模型庫中含有多層次相似性的模型，其搜索結(jié)果更相似性感知，而基于蟻群算法的模型相似性評價算法的實驗結(jié)果中，第2個和第6個模型并不是期望得到的重用模型，而相對于基于基于網(wǎng)絡(luò)本體語言的模型相似性評價算法，文中算法搜索到的模型數(shù)量更多，且部分具有高復(fù)雜度的模型也被搜索到，便于設(shè)計人員更好地進行模型重用和深度挖掘。

表1 三種算法對盤形結(jié)構(gòu)進行相似性評價實驗結(jié)果

4.2 算法性能比較實驗

為充分驗證文中算法的模型相似性評介性能，選取20個經(jīng)典重用模型結(jié)構(gòu)，以70%的相似度為評價閾值，人通用ESB模型庫中搜索存在經(jīng)典結(jié)構(gòu)的模型，每個經(jīng)典結(jié)構(gòu)進行50次重復(fù)實驗，取平均值，然后20個經(jīng)典結(jié)構(gòu)的實驗結(jié)果再進行平均，得到每個算法的平均查全率和平均查準率，獲得PR曲線如圖2所示，PR曲線的理想結(jié)果為查準率等于的恒定直線，對于實驗結(jié)果，曲線位置越靠近理想曲線，說明算法的相似性評價性能越好，對模型的檢索精度越高，從圖2的PR曲線結(jié)果看出，文中所提算法的重用結(jié)構(gòu)檢索性能優(yōu)于Acs-Sim和Wol-Sim算法。

圖2 實驗結(jié)果平均PR曲線

5 結(jié)語

為實現(xiàn)典型模型結(jié)構(gòu)的高效重用，提出了基于粒子群算法優(yōu)化的CAD模型典型結(jié)構(gòu)相似性評價算法，算法首先由組成模型各面的邊的數(shù)目構(gòu)造相似性評價矩陣，通過粒子群算法搜索兩模型的面最優(yōu)匹配序列，并計算面相似度，整合為模型的相似度。實驗結(jié)果表明，與已有算法相比，所提算法可以更準確地描述三維模型的典型結(jié)構(gòu)相似性。