劉 研，張吉慶，張旭堂

（1.哈爾濱工業(yè)大學(xué) 理學(xué)院，黑龍江 哈爾濱150001；2.中國(guó)國(guó)際工程咨詢(xún)公司，北京100048；3.哈爾濱工業(yè)大學(xué) 機(jī)電學(xué)院，黑龍江 哈爾濱150001）

0 引 言

合理地重用三維模型有助于企業(yè)提高新產(chǎn)品開(kāi)發(fā)速度，提升競(jìng)爭(zhēng)力［1］，因此設(shè)計(jì)人員迫切需要一種有效的三維模型檢索方法，快速、準(zhǔn)確地從模型庫(kù)中找到與檢索模型相似的三維模型?；谖谋娟P(guān)鍵字的檢索方法被最先用來(lái)查找相似模型。這種方法通過(guò)在模型標(biāo)注信息和用戶(hù)輸入的關(guān)鍵字之間進(jìn)行匹配來(lái)實(shí)現(xiàn)檢索，這種方法存在以下幾方面缺陷：①有限的人力無(wú)法做到對(duì)所有模型進(jìn)行標(biāo)注；②不同的人對(duì)同一模型的標(biāo)注可能是不同的，模型的標(biāo)注信息隨著時(shí)間的推移可能發(fā)生變化；③關(guān)鍵字不準(zhǔn)確時(shí)無(wú)法檢索到相似模型。隨著研究的深入，基于文本關(guān)鍵字的檢索方法被基于模型內(nèi)容特征的檢索方法淘汰?；趦?nèi)容的檢索方法核心思想是通過(guò)三維模型的內(nèi)容特征來(lái)表征三維模型，將三維模型轉(zhuǎn)化為特征空間中的特征向量，通過(guò)計(jì)算特征向量之間的距離來(lái)判斷對(duì)應(yīng)模型之間的相似度?；趦?nèi)容的檢索利用模型自身攜帶的信息，檢索性能優(yōu)于文本關(guān)鍵字方式，逐漸成為模型檢索問(wèn)題的研究重點(diǎn)［2－7］。Osada等［8］提出了一種適合任意三維模型的形狀描述計(jì)算方法。該方法通過(guò)采樣確定某種形狀函數(shù)在模型上的分布情況，通過(guò)形狀分布對(duì)模型進(jìn)行描述。Osada提出了5種形狀函數(shù)，如圖1所示，實(shí)驗(yàn)顯示在5種形狀函數(shù)中，D2的檢索效果最好。

圖1 Osada提出的5種形狀函數(shù)［9］

蔣立軍等［9］提出一種基于網(wǎng)格模型面積分布的檢索算法。該算法通過(guò)對(duì)網(wǎng)格模型各頂點(diǎn)進(jìn)行分析建立模型的面積分布序列。為了實(shí)現(xiàn)相似度計(jì)算對(duì)面積分布序列的歸一化操作和傅立葉變換，兩個(gè)模型之間的相似度等于兩個(gè)分布序列的L2距離。

侯鑫等［10］提出了一種與計(jì)算機(jī)輔助設(shè)計(jì)系統(tǒng)無(wú)關(guān)的基于網(wǎng)格特征臨界點(diǎn)的三維工程模型檢索算法。該算法根據(jù)Morse理論，采用網(wǎng)格頂點(diǎn)處的離散平均曲率作為光滑實(shí)值函數(shù)，計(jì)算網(wǎng)格特征臨界點(diǎn)，采用兩臨界點(diǎn)之間的測(cè)地線距離和頂點(diǎn)法矢夾角余弦值作為聯(lián)合形狀函數(shù)，按照極大值點(diǎn)和鞍點(diǎn)，分別計(jì)算同類(lèi)臨界點(diǎn)間的聯(lián)合形狀函數(shù)得到形狀分布，從而將模型的比較映射為形狀分布矩陣的比較。通過(guò)在ESB庫(kù)上的驗(yàn)證，算法明顯提高了基于圖形分布檢索算法的有效性。

基于內(nèi)容的檢索算法在檢索性能上有較大提升，但是也存在一些問(wèn)題：①單一特征對(duì)模型的描述能力有限。文獻(xiàn) ［11］的實(shí)驗(yàn)結(jié)果表明，不同的特征具有各自的優(yōu)缺點(diǎn)，不存在適用于所有模型的特征。所以，使用單一特征很難在所有模型類(lèi)別中取得滿意的檢索效果；② “語(yǔ)義鴻溝”問(wèn)題［12］。人對(duì)模型相似性的判斷除了模型內(nèi)容，還結(jié)合了模型視覺(jué)特征和語(yǔ)義信息，并以語(yǔ)義信息為重?；谔卣鞯臋z索算法完全依賴(lài)模型底層特征來(lái)計(jì)算模型的相似性，并未考慮到模型的語(yǔ)義信息，而模型的底層特征和語(yǔ)義之間不存在直接關(guān)系，所以模型內(nèi)容的相似不代表語(yǔ)義的相似。為了解決“語(yǔ)義鴻溝”問(wèn)題，有些研究人員將相關(guān)反饋技術(shù)應(yīng)用到了三維模型檢索問(wèn)題上［13］。在用戶(hù)的反饋信息的幫助下，檢索算法可以更加準(zhǔn)確地捕捉到用戶(hù)的檢索意圖。

本文提出三維工程模型檢索算法針對(duì)上述兩方面缺陷做出了如下改進(jìn)：①通過(guò)多個(gè)內(nèi)容特征的組合增強(qiáng)算法的檢索能力；②根據(jù)用戶(hù)的反饋信息獲取用戶(hù)的檢索需求，通過(guò)粒子群算法優(yōu)化動(dòng)態(tài)選擇每個(gè)特征算子在相似性計(jì)算過(guò)程中的權(quán)重，使得檢索結(jié)果更加靠近用戶(hù)的檢索需求，在一定程度上縮小高層語(yǔ)義與模型底層特征信息之間的差距。

1 算法說(shuō)明

1.1 相似度計(jì)算

用Q 表示檢索模型，用Oi表示模型庫(kù)中的任意一個(gè)模型。用F 來(lái)表示選用的特征算子集合，單個(gè)特征算子fi用表示，S（Ofii）表示在使用fi的情況下，Oi和Q 之間的相似度。其中wi表示特征算子fi對(duì)應(yīng)的權(quán)重。用S（Oi）表示Oi和Q 之間的綜合相似距離，S（Oi）是由S（Ofii）線性組合得到的，S（Oi）的計(jì)算公式見(jiàn)式 （1）S（Oi）越小說(shuō)明Oi和Q 越 相 似

1.2 特征算子權(quán)重動(dòng)態(tài)更新

1.2.1 粒子群算優(yōu)化法

粒子群優(yōu)化算法 （particle swarm optimization，PSO）源于對(duì)鳥(niǎo)群捕食行為的研究，是近年來(lái)發(fā)展起來(lái)的一種進(jìn)化算法［14］。PSO 求解優(yōu)化問(wèn)題時(shí)首先隨機(jī)生成若干個(gè)粒子（particle），每個(gè)粒子對(duì)應(yīng)搜索空間中的一個(gè)解。每個(gè)粒子具備位置和速度兩個(gè)屬性，由適應(yīng)度函數(shù)決定粒子對(duì)待優(yōu)化問(wèn)題的優(yōu)劣程度。粒子的初始狀態(tài)隨機(jī)確定后，算法進(jìn)入迭代求解過(guò)程。在迭代過(guò)程中，粒子利用兩個(gè)極值來(lái)更新自己，一個(gè)稱(chēng)為pbest（當(dāng)前粒子在進(jìn)化過(guò)程中出現(xiàn)的最優(yōu)位置），一個(gè)稱(chēng)為gbest （整個(gè)種群在進(jìn)化過(guò)程中出現(xiàn)的最優(yōu)位置）。式 （2）、式 （3）為粒子的速度與位置更新公式。迭代終止條件為預(yù)先確定的最大迭代次數(shù)或者為對(duì)優(yōu)化結(jié)果的精度要求。假設(shè)粒子在D 維空間搜索問(wèn)題最優(yōu)解，第i個(gè)粒子的位置信息可表示為：Xi＝（xi1，xi2，…，xiD），速度信息 可 表 示 為：Vi＝（Vi1，Vi2，…，ViD）。式 （2）和 式（3）為PSO 在第t＋1次迭代時(shí)的粒子速度和位置更新公式，式 （2）中的pbesti表示第i個(gè)粒子在第t 次迭代時(shí)的個(gè)體極值點(diǎn)，gbest表示粒子種群當(dāng)前的全局極值點(diǎn)，w 為慣性權(quán)重，c1和c2為學(xué)習(xí)因子，r1和r2為0到1之間的隨機(jī)數(shù)。式 （4）為PSO 的適應(yīng)度函數(shù)，適應(yīng)度函數(shù)以粒子的位置信息為輸入，fitnessi表示第i 個(gè)粒子對(duì)待優(yōu)化問(wèn)題的優(yōu)劣程度。每個(gè)粒子完成一次迭代后根據(jù)適應(yīng)度大小更新自己的局部極值點(diǎn) （pbest），粒子種群完成一次迭代后根據(jù)適應(yīng)度大小更新全局極值點(diǎn) （gbest）

1.2.2 權(quán)重優(yōu)化過(guò)程

初次檢索結(jié)束后，將每個(gè)特征算子前K 個(gè)檢索結(jié)果返回給用戶(hù)供其標(biāo)記，所以供用戶(hù)標(biāo)記的模型總數(shù)為×K 個(gè)。用戶(hù)可將返回的模型標(biāo)記為 “相關(guān)”、 “不相關(guān)”和“一般”3類(lèi)。用R （relevant）來(lái)表示被用戶(hù)標(biāo)記為 “相關(guān)”的模型集合，用R（Ofii）來(lái)表示特征算子fi的前K 個(gè)相似模型中屬于被標(biāo)記為“相似”的模型；用IR （irrelevant）來(lái)表示被標(biāo)記為“不相關(guān)”的模型集合，用IR（Ofii）表示不相關(guān)模型中被fi檢索到的模型；用M （middle）來(lái)表示被標(biāo)記為“一般”的模型集合，用M（Ofii）表示 “一般”模型中被fi檢索到的模型。以上信息確認(rèn)完畢后，使用粒子群算法優(yōu)化fi的權(quán)重，權(quán)重優(yōu)化過(guò)程中循序以下幾條規(guī)則：

R（Qfii）中的模型個(gè)數(shù)越多fi的權(quán)重越大；

IR（Qfii）中的模型個(gè)數(shù)越多fi的權(quán)重越小；

如果特征算子的相關(guān)模型個(gè)數(shù)一樣多，則考察其相關(guān)模型的排名之和，和越小fi的權(quán)重越大。

根據(jù)上述幾條原則構(gòu)建粒子適應(yīng)度計(jì)算公式，見(jiàn)式（5）。其中Fitness（pi）表示粒子第i個(gè)粒子的適應(yīng)度，其值越大表明粒子狀態(tài)越優(yōu)化

1.3 算法流程

權(quán)重更新完畢后，使用式 （1）重新計(jì)算模型Oi和Q之間的綜合相似度。算法將按照綜合相似度對(duì)模型庫(kù)中的模型進(jìn)行排序，并返回前F ×K 個(gè)模型供用戶(hù)標(biāo)注，用戶(hù)標(biāo)記完畢后開(kāi)始下一輪權(quán)重優(yōu)化，照此循環(huán)直至用戶(hù)主動(dòng)結(jié)束檢索過(guò)程。算法流程如下文所述，流程如圖2所示。

（1）初始化所有特征算子的權(quán)重；

（2）分別使用各個(gè)特征算子計(jì)算相似度R（Ofii）；

（4）用戶(hù)對(duì)模型進(jìn)行相關(guān)性標(biāo)注；

（5）PSO 更新所有特征描算子的權(quán)重；

（6）按照式 （1）計(jì)算綜合相似度S（Oi）；

（7）根據(jù)S（Oi）對(duì)數(shù)據(jù)庫(kù)中的所有模型排序，返回前×K 個(gè)模型供用戶(hù)標(biāo)注；

（8）如果用戶(hù)對(duì)結(jié)果滿意，結(jié)束；否則返回第（4）步，開(kāi)始下一輪反饋。

圖2 基于相關(guān)反饋的多特征融合算法流程

2 實(shí)驗(yàn)討論

以Visual C＋＋6.0 為集成開(kāi)發(fā)環(huán)境，結(jié)合Matlab R2011b實(shí)現(xiàn)了本文提出的算法。在實(shí)驗(yàn)環(huán)節(jié)實(shí)現(xiàn)的算法聯(lián)合了上文中介紹的3種特征算子，分別是：D2［8］，臨界特征點(diǎn)［10］和測(cè)地線連接圖［15］。PSO 的參數(shù)選擇如下：粒子 規(guī)模50，慣性權(quán)重w＝1，學(xué)習(xí)因子c1＝c2＝1，迭代50次。使用普渡大學(xué)建立的工程標(biāo)準(zhǔn)模型庫(kù)ESB （engineering shape benchmark）對(duì)本文算法進(jìn)行了驗(yàn)證。ESB 庫(kù)中包含866個(gè)模型，被分為3個(gè)大類(lèi)，45個(gè)小類(lèi)［16］。表1為部分檢索實(shí)驗(yàn)的前10個(gè)檢索結(jié)果，3個(gè)檢索模型分別來(lái)自ESB庫(kù)的3個(gè)大類(lèi)，表格中圖片下方文字為模型名稱(chēng)。

表1 部分檢索實(shí)驗(yàn)結(jié)果

圖3為參與組合的3種檢索算法以及本文算法在ESB庫(kù)上的平均查全率－查準(zhǔn)率曲線。由圖3可知，本文算法的PR 曲線優(yōu)于參與的組合的3種檢索算法。

圖3 查全率－查準(zhǔn)率曲線

3 結(jié)束語(yǔ)

針對(duì)三維模型檢索領(lǐng)域存在的 “語(yǔ)義鴻溝”和單特征檢索能力有限的問(wèn)題，提出一種基于相關(guān)反饋和多特征組合的三維工程網(wǎng)格模型檢索算法。該算法以網(wǎng)格模型為對(duì)象，通過(guò)多特征聯(lián)合增強(qiáng)算法的檢索能力；在用戶(hù)相關(guān)反饋信息的指導(dǎo)下使用PSO 算法動(dòng)態(tài)更新各特征算子在相似度計(jì)算過(guò)程中的權(quán)重，提高了檢索結(jié)果的語(yǔ)義相關(guān)性。實(shí)驗(yàn)結(jié)果表明，本文提出的算法可有效提高檢索效率。

在未來(lái)的研究中可從以下幾方面對(duì)算法進(jìn)行改進(jìn)：①選取更優(yōu)的特征算子參與組合以便提高組合算法的檢索能力；②改善粒子群算法適應(yīng)度函數(shù)，更加合理的適應(yīng)度函數(shù)有助于找到更能體現(xiàn)用戶(hù)檢索意圖的權(quán)重分配方案。

［1］ZHANG Kaixing，ZHANG Shusheng，WANG Hongshen，et al.Content－based 3Dmodel retrieval and its application to CAD／CAM［J］.Mechanical Science and Technology for Aerospace Engineering，2009，28 （7）：847－850（in Chinese）.［張開(kāi)興，張樹(shù)生，王洪申，等.基于內(nèi)容的3D 模型檢索及其在CAD／CAM 中的應(yīng)用［J］.機(jī)械科學(xué)與技術(shù)，2009，28 （7）：847－850.］

［2］Takahiko F，Ryutarou O.Dense sampling and fast encoding for 3dmodel retrieval using bag－of－visual features［C］／／Proceeding of the ACM International Conference on Image and Video Retrieval，2009：192－199.

［3］Apostolos A，Georgios L，Petros D.3D model retrieval using accurate pose estimation and view－based similarity ［C］／／Proceeding of The 1st ACM International Conference Multimedia Retrieval，2011：17－20.

［4］Yi Y，Nie F P，Xu D，et al.A multimedia retrieval framework based on semi－supervised ranking and relevance feedback［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34 （4）：723－742.

［5］Li J B，Sun W H，Tang L L.3Dmodel classification based on nonparametric discriminate analysis with kernels ［J］.Neural Computing and Applications，2013，22 （3－4）：771－781.

［6］Tangelder J W H，Veltkamp R C.A survey of content based 3Dshape retrieval methods［J］.Multimed Tools Appl，2008，39 （3）：441－471.

［7］Jayanti S，Kalyanaraman Y，Ramani K.Shape－based clustering for 3DCAD objects：A comparative study of effectiveness［J］.Computer－Aided Design，2009，41 （12）：999－1007.

［8］WANG Hongshen，ZHANG Shusheng，BAI Xiaoliang，et al.3DCAD surface model retrieval algorithm based on distance and curvature distributions［J］.Journal of Computer－Aided Design＆Computer Graphics，2010，22 （5）：762－770 （in Chinese）.［王洪申，張樹(shù)生，白曉亮，等.三維CAD 曲面模型距離－曲率形狀分布檢索算法 ［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2012，22 （5）：762－770.］

［9］JIANG Lijun，ZHANG Xutang，ZHANG Guangyu.3Dmodel retrieval method based on area distributions［J］.Computer Engineering and Applications，2012，48 （12）：6－13（in Chinese）.［蔣立軍，張旭堂，張廣玉.基于面積分布算子的三維模型檢索算法［J］.計(jì)算機(jī)工程與應(yīng)用，2012，48 （12）：6－13.］

［10］HOU Xin，ZHANG Xutang，JIN Tianguo，et al.3Dengineering models retrieval algorithm based on mesh salient critical［J］.Computer Integrated Manufacturing System，2009，15 （1）：72－81 （in Chinese）.［侯鑫，張旭堂，金天國(guó)，等.基于網(wǎng)格臨界點(diǎn)的三維工程模型檢索算法 ［J］.計(jì)算機(jī)集成制造系統(tǒng)，2009，15 （1）：72－81.］

［11］Leng B.A powerful relevance feedback mechanism for content－based 3D model retrieval ［J］.Multimed Tools Appl，2008，40 （1）：135－150.

［12］Havemann S，F(xiàn)ellner D.Seven research challenges of generalized 3Ddocuments［J］.IEEE Computer Graphics and Applications，2007，27 （3）：70－76.

［13］Yang Yi，Nie Feiping，Xu dong，et al.A multimedia retrieval framework based on semi－supervised ranking and relevance feedback ［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34 （4）：723－742.

［14］Hu B K，Liu Y S，Gao S M.Parallel relevance feedback for 3D model retrieval based on fast weighted－center particle swarm optimization ［J］.Pattern Recognition，2010，43（8）：2950－2961.

［15］Zhang X T，Chen X F，Yang P Y，et al.Geodesic connected Graph representation of 3Dprismatic CAD models［C］／／Proceeding of International Conference on Digital Manufacturing and Automation，2010：776－779.

［16］Li B，Johan H.3D model retrieval using hybrid features and class information ［J］.Multimedia Tools and Applications，2013，62 （3）：1－26.