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

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

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

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

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

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

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

0 引言

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

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

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

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

1.1 預(yù)處理操作

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

圖1 方法整體思路

1.2 粒子群算法原理

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

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

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

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

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

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

1）粒子編碼方案

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

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

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

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

3）算法流程描述

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

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

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

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

1）Begin；

2）初始化粒子群；

3）Do；

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

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

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

7）Return{s}；

8）End。

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

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

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

1）粒子編碼方案

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

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

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

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

考慮到如果不使用懲罰函數(shù)，而只是待算法迭代結(jié)束時(shí)對(duì)輸出向量ox乘以進(jìn)行規(guī)整，也可使其向量成員滿(mǎn)足約束條件但如此一來(lái)可能會(huì)引發(fā)粒子在解空間對(duì)重復(fù)解的搜索，比如對(duì)于[0.1 0.2 0.3]T和[0.2 0.4 0.6]T，顯然這兩者在實(shí)質(zhì)上是同一個(gè)解。為了避免這一問(wèn)題的出現(xiàn)，可以在算法的迭代過(guò)程中，通過(guò)對(duì)粒子pi的當(dāng)前位置和種群中各粒子（包括pi）的歷史位置進(jìn)行規(guī)整，然后將規(guī)整后的當(dāng)前位置與歷史位置進(jìn)行比較，進(jìn)而實(shí)現(xiàn)對(duì)重復(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)特征的類(lèi)別標(biāo)簽集合{s}；模型訓(xùn)練集的相似度矩陣集合{Mats}，集合成員與最優(yōu)特征類(lèi)別相對(duì)應(yīng)。

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

1）Begin；

2）初始化粒子群；

3）Do；

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

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

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

7）Return {ws*}；

8）End。

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

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

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

為了驗(yàn)證所提出的多特征最優(yōu)融合方法在三維模型檢索中的可行性和有效性，在實(shí)驗(yàn)中基于4種特征提取方法，并通過(guò)參數(shù)調(diào)整獲得8種不同的候選模型特征，分別是：1）基于復(fù)眼視覺(jué)算法[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）基于光場(chǎng)算法[4]得到傅立葉變換特征（FR）和Zernike矩特征（ZK）。實(shí)驗(yàn)?zāi)Ｐ腿∽悦绹?guó)普渡大學(xué)的Engineering Shape Benchmark（ESB）模型數(shù)據(jù)庫(kù)[15]。

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

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

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

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

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

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

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

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

本文提出了一種三維模型的多特征最優(yōu)融合方法，以提升在不同場(chǎng)景下對(duì)三維模型的檢索效果。該方法采用監(jiān)督學(xué)習(xí)的模式，利用粒子群算法從候選特征中依次完成最優(yōu)特征組合的尋找和最優(yōu)特征權(quán)重的計(jì)算，進(jìn)而針對(duì)指定檢索場(chǎng)景確定出最優(yōu)的特征融合方案。實(shí)驗(yàn)結(jié)果表明，該方法能夠充分迎合不同檢索場(chǎng)景的特點(diǎn)，檢索效果優(yōu)于現(xiàn)有其他同類(lèi)方法，能夠更好地滿(mǎ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] 萬(wàn)麗莉,劉美琴.基于評(píng)價(jià)指標(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] 李亮, 張樹(shù)生,白曉亮,黃瑞.一種三維CAD模型自動(dòng)語(yǔ)義標(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

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

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