劉 研，張吉慶，張旭堂

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

0 引 言

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

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

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

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

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

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

1 算法說明

1.1 相似度計(jì)算

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

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

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

粒子群優(yōu)化算法 （particle swarm optimization，PSO）源于對鳥群捕食行為的研究，是近年來發(fā)展起來的一種進(jìn)化算法［14］。PSO 求解優(yōu)化問題時(shí)首先隨機(jī)生成若干個(gè)粒子（particle），每個(gè)粒子對應(yīng)搜索空間中的一個(gè)解。每個(gè)粒子具備位置和速度兩個(gè)屬性，由適應(yīng)度函數(shù)決定粒子對待優(yōu)化問題的優(yōu)劣程度。粒子的初始狀態(tài)隨機(jī)確定后，算法進(jìn)入迭代求解過程。在迭代過程中，粒子利用兩個(gè)極值來更新自己，一個(gè)稱為pbest（當(dāng)前粒子在進(jìn)化過程中出現(xiàn)的最優(yōu)位置），一個(gè)稱為gbest （整個(gè)種群在進(jìn)化過程中出現(xiàn)的最優(yōu)位置）。式 （2）、式 （3）為粒子的速度與位置更新公式。迭代終止條件為預(yù)先確定的最大迭代次數(shù)或者為對優(yōu)化結(jié)果的精度要求。假設(shè)粒子在D 維空間搜索問題最優(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è)粒子對待優(yōu)化問題的優(yōu)劣程度。每個(gè)粒子完成一次迭代后根據(jù)適應(yīng)度大小更新自己的局部極值點(diǎn) （pbest），粒子種群完成一次迭代后根據(jù)適應(yīng)度大小更新全局極值點(diǎn) （gbest）

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

初次檢索結(jié)束后，將每個(gè)特征算子前K 個(gè)檢索結(jié)果返回給用戶供其標(biāo)記，所以供用戶標(biāo)記的模型總數(shù)為×K 個(gè)。用戶可將返回的模型標(biāo)記為 “相關(guān)”、 “不相關(guān)”和“一般”3類。用R （relevant）來表示被用戶標(biāo)記為 “相關(guān)”的模型集合，用R（Ofii）來表示特征算子fi的前K 個(gè)相似模型中屬于被標(biāo)記為“相似”的模型；用IR （irrelevant）來表示被標(biāo)記為“不相關(guān)”的模型集合，用IR（Ofii）表示不相關(guān)模型中被fi檢索到的模型；用M （middle）來表示被標(biāo)記為“一般”的模型集合，用M（Ofii）表示 “一般”模型中被fi檢索到的模型。以上信息確認(rèn)完畢后，使用粒子群算法優(yōu)化fi的權(quán)重，權(quán)重優(yōu)化過程中循序以下幾條規(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ì)算公式，見式（5）。其中Fitness（pi）表示粒子第i個(gè)粒子的適應(yīng)度，其值越大表明粒子狀態(tài)越優(yōu)化

1.3 算法流程

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

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

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

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

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

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

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

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

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

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

以Visual C＋＋6.0 為集成開發(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］和測地線連接圖［15］。PSO 的參數(shù)選擇如下：粒子 規(guī)模50，慣性權(quán)重w＝1，學(xué)習(xí)因子c1＝c2＝1，迭代50次。使用普渡大學(xué)建立的工程標(biāo)準(zhǔn)模型庫ESB （engineering shape benchmark）對本文算法進(jìn)行了驗(yàn)證。ESB 庫中包含866個(gè)模型，被分為3個(gè)大類，45個(gè)小類［16］。表1為部分檢索實(shí)驗(yàn)的前10個(gè)檢索結(jié)果，3個(gè)檢索模型分別來自ESB庫的3個(gè)大類，表格中圖片下方文字為模型名稱。

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

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

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

3 結(jié)束語

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

在未來的研究中可從以下幾方面對算法進(jìn)行改進(jìn)：①選取更優(yōu)的特征算子參與組合以便提高組合算法的檢索能力；②改善粒子群算法適應(yīng)度函數(shù)，更加合理的適應(yīng)度函數(shù)有助于找到更能體現(xiàn)用戶檢索意圖的權(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）.［張開興，張樹生，王洪申，等.基于內(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）.［王洪申，張樹生，白曉亮，等.三維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）.［侯鑫，張旭堂，金天國，等.基于網(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.