李 亮，白曉亮，衛(wèi)青延

（1.中國空空導(dǎo)彈研究院，洛陽 471009；2.西北工業(yè)大學(xué) 現(xiàn)代設(shè)計(jì)與集成制造技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，西安 710072）

一種面向檢索的三維模型多特征最優(yōu)融合方法

李 亮1，白曉亮2，衛(wèi)青延1

（1.中國空空導(dǎo)彈研究院，洛陽 471009；2.西北工業(yè)大學(xué) 現(xiàn)代設(shè)計(jì)與集成制造技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，西安 710072）

針對不同檢索場景下三維模型的多特征融合問題，提出一種三維模型的多特征最優(yōu)融合方法，該方法利用粒子群算法，采用監(jiān)督學(xué)習(xí)模式在不同場景下依次完成最合適特征的挑選并計(jì)算最合理的權(quán)重，進(jìn)而確定出針對指定檢索場景的最優(yōu)特征融合方案。實(shí)驗(yàn)結(jié)果顯示，該方法能夠充分迎合不同檢索場景的特點(diǎn)，與現(xiàn)有同類方法相比，能更有效地發(fā)揮多特征融合在用于三維模型檢索時的優(yōu)勢和效果。

三維模型檢索；多特征融合；粒子群算法

0 引言

隨著三維模型已成為產(chǎn)品研制過程越來越不可獲取的基礎(chǔ)信息載體，為了應(yīng)對愈加復(fù)雜和不確定的市場需求環(huán)境，如何有效地檢索并重用企業(yè)已有的三維模型資源，進(jìn)而縮短新產(chǎn)品的研制周期，已成為研究熱點(diǎn)之一[1,2]。在目前對三維模型檢索技術(shù)的研究中，如何描述模型對象進(jìn)而準(zhǔn)確衡量不同模型的相似性是其中的核心問題[3]。迄今為止，雖然已有眾多的三維模型特征提取方法被學(xué)者們提出，例如著名的光場算法[4]、球面調(diào)和算法[5]等，然而不同方法由于受觀察和處理三維模型的角度等因素制約，所提取的模型特征實(shí)質(zhì)上都只是對三維模型某一特定方面的內(nèi)容描述，以致尚未有一種方法能夠完全適用所有模型對象。將多種模型特征按一定規(guī)則融合被認(rèn)為是一種能夠有效解決上述問題的處理方式，其目的在于對這些特征優(yōu)勢互補(bǔ)，從而更加完備地描述三維模型的內(nèi)容信息以提升檢索精度[3]。

由于三維模型檢索技術(shù)的實(shí)際應(yīng)用場景存在多樣化的特點(diǎn)，例如根據(jù)企業(yè)需求的不同，用戶所面對的檢索對象往往分布于不同的模型數(shù)據(jù)庫（例如回轉(zhuǎn)體類模型庫、棱柱類模型庫，或是由多類模型所組成的混合類模型庫等），因此，在進(jìn)行多特征融合時，必須充分考慮不同檢索場景下目標(biāo)模型的特點(diǎn)。針對不同場景，是否選取到最合適的模型特征，以及是否對這些特征在檢索目標(biāo)模型時所起作用進(jìn)行了最合理的權(quán)重分配，是保障多特征的融合效果，進(jìn)而充分提升檢索效果的重要影響因素。然而，現(xiàn)有三維模型多特征融合方法的設(shè)計(jì)主要是通過經(jīng)驗(yàn)、或者某些簡單的指標(biāo)來對候選特征搭配取舍，如均值法[6]、單值評價指標(biāo)法[7]等。這些工作雖然能夠改善僅使用單一模型特征檢索時的效果局限，但由于所給出的多特征融合方案并不能保證最優(yōu)，限制了檢索效果的提升空間。基于此，本文利用粒子群算法設(shè)計(jì)了一種三維模型的多特征最優(yōu)融合方法，通過監(jiān)督學(xué)習(xí)及啟發(fā)式求解的策略確定出最優(yōu)的特征融合方案，以期充分迎合不同檢索場景的特點(diǎn)并提升最終的檢索效果。

1 方法實(shí)現(xiàn)

本文方法的整體思路如圖1所示，首先在訓(xùn)練階段，針對不同檢索場景下的三維模型訓(xùn)練集，根據(jù)候選特征的種類選擇相應(yīng)的特征提取方法對集合中的模型進(jìn)行處理，并計(jì)算這些模型關(guān)于這些候選特征的相似度矩陣；在此基礎(chǔ)上，利用粒子群算法尋找最適合進(jìn)行融合的候選特征類別（即最優(yōu)特征組合），并計(jì)算這些特征的對應(yīng)權(quán)重（即最優(yōu)特征權(quán)重），從而組成最優(yōu)的特征融合方案；在測試階段，根據(jù)上述融合方案對測試模型進(jìn)行多特征的融合，進(jìn)而據(jù)此獲得不同模型之間的相似性評價。

1.1 預(yù)處理操作

為了獲取三維模型多特征的最優(yōu)融合方案，首先需要根據(jù)不同種類的特征分別計(jì)算不同模型間的相似度。由于不同特征的方法來源差異，導(dǎo)致模型相似度的計(jì)算結(jié)果在取值范圍上也大相徑庭，為了保證最終的融合效果，還需對其進(jìn)行歸一化處理。對于給定的由n個三維模型組成的模型訓(xùn)練集T={Mi}，i=1,2,…,n，設(shè)k=1,2,…,K為候選特征的類別標(biāo)簽，為對T中的模型采用特征k所獲得的模型相似度矩陣；其中，表示兩個三維模型Mi和Mj之間的相似度（在本文實(shí)驗(yàn)中以模型間的特征距離度量）。在此之后，采用最小-最大規(guī)范化方法[8]，將T中成員逐一處理以統(tǒng)一歸化至[0,1]區(qū)間。

圖1 方法整體思路

1.2 粒子群算法原理

粒子群算法源自對鳥群覓食行為的研究，是一種基于種群的模擬進(jìn)化算法。與遺傳算法、蟻群算法等其他進(jìn)化算法相比，粒子群算法具有實(shí)施簡單、調(diào)制參數(shù)較少等優(yōu)點(diǎn)[9]。設(shè)集合為D維求解空間中一個由n個粒子（即可行解）所組成的種群，粒子群算法通過跟蹤P中各粒子的位置和變化速度，以適應(yīng)度值來評估當(dāng)前粒子信息的優(yōu)劣，并據(jù)此更新粒子自身的各體極值點(diǎn)PBesti以及整個種群的群體極值點(diǎn)GBest，進(jìn)而指導(dǎo)各粒子不斷調(diào)整自身速度和位置，逐步向著解空間中擁有全局最優(yōu)適應(yīng)度值的位置，即問題對象的最優(yōu)解靠近。根據(jù)待處理對象的不同，粒子群算法又可進(jìn)一步分為連續(xù)粒子群算法和離散粒子群算法。其中，前者主要針對解空間呈連續(xù)性的優(yōu)化問題，通常按照如下規(guī)則[10]對粒子的速度和位置進(jìn)行更新：

式中，k為算法當(dāng)前的迭代次數(shù)；c1和c2為學(xué)習(xí)因子，分別用來控制粒子自身和整個種群對粒子運(yùn)動的影響，通常取c1=c2=2；r1和r2為分布于[0,1]區(qū)間的隨機(jī)數(shù)；ω為慣性權(quán)重，用來調(diào)節(jié)粒子速度的變化趨勢。后者則用于求解0-1變量的離散優(yōu)化問題，相應(yīng)粒子速度和位置的更新規(guī)則可根據(jù)文獻(xiàn)[11]設(shè)定為：

式中，xi,d和vi,d分別為粒子位置xi及速度vi在維度d上的分量；表示對xd的取反操作表示對同維度的兩個粒子位置分量的比較操作；ρ為一個分布于0-1區(qū)間的隨機(jī)數(shù)。

1.3 最優(yōu)特征組合的尋找

對于如何從若干不同類別候選特征中選出最合適對象進(jìn)行組合的問題，通過引入0-1變量ck（k=1,2,…,K）為候選特征的類別標(biāo)簽），并令：

可將該問題的數(shù)學(xué)模型表示為：

1）粒子編碼方案

編碼的目的是為了將粒子群算法中的粒子種群與實(shí)際問題建立聯(lián)系。針對本小節(jié)的待解問題，假設(shè)存在K種三維模型候選特征，將每一套潛在的特征組合方案表示為一個粒子，則每個粒子Pi的編碼為，其中xi,k的取值為0或1，用來描述各候選特征的入選情況。例如，當(dāng)K=5，表示候選特征集合中的第1種和第5種候選特征入選參與組合。

2）適應(yīng)度函數(shù)

本文以平均查準(zhǔn)率[12]作為粒子適應(yīng)度值的評價指標(biāo)，以考察粒子對應(yīng)的特征組合方案在檢索中的使用效果，即：

式中，APP(.)為平均查準(zhǔn)率計(jì)算函數(shù)；Prec為訓(xùn)練集T中的模型預(yù)分類信息。

3）算法流程描述

尋找三維模型最優(yōu)特征組合的算法流程如算法1所示，其中，以算法執(zhí)行至最大迭代次數(shù)作為算法的終止條件。

算法1：三維模型最優(yōu)特征組合的尋找

輸入：候選特征的類別標(biāo)簽集合{k}；模型訓(xùn)練集的相似度矩陣集合{Matk}，集合成員與候選特征類別相對應(yīng)。

輸出：最優(yōu)特征的類別標(biāo)簽集合{s}。

1）Begin；

2）初始化粒子群；

3）Do；

4）按照式(1)和式(2)分別計(jì)算粒子的位置和速度；

5）按照式(9)計(jì)算適應(yīng)度，更新粒子個體極值和群體極值；

6）While未達(dá)到最大迭代次數(shù)；

7）Return{s}；

8）End。

1.4 最優(yōu)特征權(quán)重的計(jì)算

在獲取三維模型的最優(yōu)特征組合之后，對于如何為這一組合中的成員配置最優(yōu)權(quán)重的問題，可將該問題的數(shù)學(xué)模型表示為：

式中，performance(.)為檢索結(jié)果的評價函數(shù)；s=1,2,…,S為最優(yōu)特征的類別標(biāo)簽；ws為特征s的權(quán)重；為與特征s對應(yīng)的模型訓(xùn)練集T的相似度矩陣。由上式可以看出，上述問題的實(shí)質(zhì)是一個連續(xù)變量的約束極值問題，屬于連續(xù)優(yōu)化問題的范疇，因此采用連續(xù)粒子群算法進(jìn)行求解。

1）粒子編碼方案

針對此前獲取的S種最優(yōu)特征，將每一套潛在的權(quán)重配置方案表示為一個粒子，則每個粒子pi的編碼為一個S維向量其中，向量成員xi,s的取值區(qū)間設(shè)為[0,1]。

2）適應(yīng)度函數(shù)

結(jié)合本小節(jié)待求解問題的目標(biāo)函數(shù)與約束條件，一般來講，適應(yīng)度函數(shù)可按如下方案設(shè)計(jì)：

式中，APR(.)與Prec的定義與前一小節(jié)相同，此處不再贅述；Pe(.)為懲罰函數(shù)，用以限制粒子的取值以滿足約束條件分別為懲罰因子和誤差項(xiàng)。但是，該設(shè)計(jì)的主要缺點(diǎn)在于合適的懲罰因子和誤差項(xiàng)通常很難找到，而不恰當(dāng)?shù)娜≈捣炊鴷璧K粒子對可行解的搜索。

考慮到如果不使用懲罰函數(shù)，而只是待算法迭代結(jié)束時對輸出向量ox乘以進(jìn)行規(guī)整，也可使其向量成員滿足約束條件但如此一來可能會引發(fā)粒子在解空間對重復(fù)解的搜索，比如對于[0.1 0.2 0.3]T和[0.2 0.4 0.6]T，顯然這兩者在實(shí)質(zhì)上是同一個解。為了避免這一問題的出現(xiàn)，可以在算法的迭代過程中，通過對粒子pi的當(dāng)前位置和種群中各粒子（包括pi）的歷史位置進(jìn)行規(guī)整，然后將規(guī)整后的當(dāng)前位置與歷史位置進(jìn)行比較，進(jìn)而實(shí)現(xiàn)對重復(fù)解的區(qū)分；基于此，本文在實(shí)驗(yàn)中采用了如下的適應(yīng)度函數(shù)設(shè)計(jì)方案：

3）算法流程描述

尋找三維模型最優(yōu)特征權(quán)重的算法流程如算法2所示，其中，以算法執(zhí)行至最大迭代次數(shù)作為算法的終止條件。

算法2：三維模型最優(yōu)特征權(quán)重的計(jì)算

輸入：最優(yōu)特征的類別標(biāo)簽集合{s}；模型訓(xùn)練集的相似度矩陣集合{Mats}，集合成員與最優(yōu)特征類別相對應(yīng)。

輸出：最優(yōu)特征權(quán)重集合{ws*}。

1）Begin；

2）初始化粒子群；

3）Do；

4）按照式(3)和式(6)分別計(jì)算粒子的位置和速度；

5）按照式(12)計(jì)算適應(yīng)度，更新粒子個體極值和群體極值；

6）While未達(dá)到最大迭代次數(shù)；

7）Return {ws*}；

8）End。

1.5 最優(yōu)特征融合方案的使用

在查詢階段，對于給定的查詢模型MQ和數(shù)據(jù)庫中的候選模型MC，根據(jù)此前獲取的最優(yōu)特征融合方案選出相應(yīng)的S種模型特征，并在此基礎(chǔ)上按照加法規(guī)則[8]進(jìn)行融合，則兩個模型之間的相似度可表示為：

2 方法驗(yàn)證與討論

為了驗(yàn)證所提出的多特征最優(yōu)融合方法在三維模型檢索中的可行性和有效性，在實(shí)驗(yàn)中基于4種特征提取方法，并通過參數(shù)調(diào)整獲得8種不同的候選模型特征，分別是：1）基于復(fù)眼視覺算法[13]得到的SIFT特征（SSIFT）；2）基于局部形狀分布算法[14]得到的LSD-r0.2、LSD-r0.3、LSD-r0.5和LSD-r0.7特征（r表示算法中采樣點(diǎn)的鄰域半徑）；3）基于球面調(diào)和算法[5]得到的球面諧波特征（SPH）；4）基于光場算法[4]得到傅立葉變換特征（FR）和Zernike矩特征（ZK）。實(shí)驗(yàn)?zāi)Ｐ腿∽悦绹斩纱髮W(xué)的Engineering Shape Benchmark（ESB）模型數(shù)據(jù)庫[15]。

實(shí)驗(yàn)基于4個不同的檢索場景展開，包括：1）棱柱類模型庫——來自原數(shù)據(jù)庫中的長方體-棱柱類模型；2）回轉(zhuǎn)體類模型庫——來自原數(shù)據(jù)庫中的回轉(zhuǎn)體類模型；3）自選類別模型庫——來自原數(shù)據(jù)庫中的齒輪、螺栓、連桿、搖桿、滑輪5個子類的模型；4）混合類模型庫——來自原數(shù)據(jù)庫中的模型全體。對于每一類模型資源，從中隨機(jī)抽取一半模型作為訓(xùn)練集。

圖2 部分實(shí)驗(yàn)?zāi)Ｐ驼故?/p>

表1列出了針對各檢索場景利用本文方法所得到的最優(yōu)特征組合及其權(quán)重，其中“-”表示該單元格對應(yīng)的候選特征未有入選?？梢钥闯?，檢索場景的差異導(dǎo)致所適用的模型特征及其相應(yīng)的權(quán)重都不盡相同，這一結(jié)果驗(yàn)證了在實(shí)施特征融合之前，需要首先對候選特征進(jìn)行篩選，并針對性計(jì)算特征權(quán)重的必要性。值得注意的是，針對混合類三維模型的檢索，8種候選特征都被選中融合，這是因?yàn)樵擃悪z索場景需要同時兼顧更多類別模型的特點(diǎn)，因此所需模型特征也相應(yīng)增多。

表1 針對不同檢索場景的最優(yōu)特征組合及權(quán)重

為了充分驗(yàn)證本文方法在三維模型檢索中的有效性，使用信息檢索領(lǐng)域普遍采用的查全率-查準(zhǔn)率曲線（P-R Curve）[12]作為檢索結(jié)果的評價指標(biāo)，將其與另外兩種多特征融合方法-基于均等權(quán)重的方法（AW）[6]和基于單值評價指標(biāo)的方法（EIW）[7]進(jìn)行比較。其中，AW方法對所有參與融合的模型特征都賦予相同的權(quán)重，可以看作是最大熵原理的一個應(yīng)用。EIW方法借助First-tier、Second-tier等指標(biāo)來設(shè)置不同特征的權(quán)重，其中使用First-tier的效果最好；相應(yīng)的，本文在重復(fù)該方法時也采用了First-tier指標(biāo)。需要說明的是，由于AW方法和EIW方法只針對特征權(quán)重的分配，并未涉及候選特征的篩選，因此為了確保對比的公正性，本文在重復(fù)這兩種方法時都是以本文方法所選出的最優(yōu)特征組合作為實(shí)驗(yàn)輸入。

從圖3中的實(shí)驗(yàn)結(jié)果可以看出，針對不同的檢索場景，即使已給出了最適合融合的特征組合，AW方法和EIW方法仍無法在此基礎(chǔ)上獲得最好的檢索結(jié)果；而由于無論是在對候選特征的篩選還是特征權(quán)重的分配上，本文方法都能做到更加合理的實(shí)施，從而與其他兩種方法相比，本文方法在用于檢索三維模型時的準(zhǔn)確性表現(xiàn)更優(yōu)。

圖3 三種方法針對不同檢索場景的查準(zhǔn)率-查全率表現(xiàn)

3 結(jié)束語

本文提出了一種三維模型的多特征最優(yōu)融合方法，以提升在不同場景下對三維模型的檢索效果。該方法采用監(jiān)督學(xué)習(xí)的模式，利用粒子群算法從候選特征中依次完成最優(yōu)特征組合的尋找和最優(yōu)特征權(quán)重的計(jì)算，進(jìn)而針對指定檢索場景確定出最優(yōu)的特征融合方案。實(shí)驗(yàn)結(jié)果表明，該方法能夠充分迎合不同檢索場景的特點(diǎn)，檢索效果優(yōu)于現(xiàn)有其他同類方法，能夠更好地滿足三維模型檢索的應(yīng)用需求。

[1] Johan W. H. Tangelder and Remco C. Veltkamp.A survey of content based 3D shape retrieval methods[J].Multimedia Tools and Applications,2008,39(3):441-471.

[2] Li B, Lu Y, Li C, et al. SHREC’14 Track Large Scale Comprehensive 3D Shape Retrieval[C].Eurographics Workshop on 3D Object Retrieval,Strasbourg, France,2014:131-140.

[3] Axenopoulos A, Daras P.3D Object Retrieval: Challenges and Research Directions[J].E-LETTER,2011,6(11):17-21.

[4] Chen D Y, Tian X P, Shen Y T, et al. On visual similarity based 3D model retrieval[J].Computer graphics forum,2003,22(3):223-232.

[5] Papadakis P, Pratikakis I,Perantonis S, et al. Efficient 3D shape matching and retrieval u sing a concrete radialized spherical projection representation[J].Pattern Recognition,2007,40(9): 2437-2452.

[6] Li B, Johan H. 3D model retrieval using hybrid features an d class information[J].Multimedia tools and applications.2013,62(3):821-846.

[7] 萬麗莉,劉美琴.基于評價指標(biāo)組合特征的三維模型檢索方法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào).2009,21(11):1563-1568.

[8] He M, Horng S, Fan P, et al. Performance evaluation of score level fusion in multimodal biometric systems[J].Pattern Recognition. 2010,43(5):1789-1850.

[9] Elbeltagi E, Hegazy T,Grierson D.Comparison among five evolutionary-based optimization algorithms[J].Advanc ed engineering informatics,2005,19(1):43-53.

[10] Blum C,Merkle D.Swarm intelligence: introduction and applications[M].Springer Berlin Heidelberg,2008:59-64.

[11] 許金友,李文立,王建軍.離散粒子群算法的發(fā)散性分析及其改進(jìn)研究[J].系統(tǒng)仿真學(xué)報(bào),2009,21(15):4676-4681.

[12] Manning, Christopher D., Prabhakar Raghavan, and Hinrich Schütze. Introduction to information retrieval[M].Cambridge university press,2009:160-161.

[13] Li L, Zhang S, Bai X and Shao Li. Retrieving 3D models using compo u nd-eye visual representations[C].in Proceedings of 13th IEEE International Conference on Computer-Aided Design and Computer Graphics,2013:172-179.

[14] 李亮, 張樹生,白曉亮,黃瑞.一種三維CAD模型自動語義標(biāo)注算法[J].計(jì)算機(jī)集成制造系統(tǒng),2013,19(7):1484-1489.

[15] Shapelab.ecn.purdue.edu[DB].

3D model retrieval using a multi-feature fusion method

LI liang1, BAI Xiao-liang2, WEI Qing-yan1

TP391

：A

1009-0134(2017)03-0005-06

2016-11-13

中國空空導(dǎo)彈院青年創(chuàng)新基金資助項(xiàng)目（CQKJJ00-2016-18）；西北工業(yè)大學(xué)民口重大項(xiàng)目培育資助項(xiàng)目（3102015BJ(II)MYZ21）；國家自然科學(xué)基金資助項(xiàng)目（51175434）

李亮（1983 -），男，山東濟(jì)南人，工程師，博士，主要從事三維模型檢索技術(shù)和智能制造技術(shù)研究。