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

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

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

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

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

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

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

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

0 引言

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

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

1 方法實現(xiàn)

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

1.1 預處理操作

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

圖1 方法整體思路

1.2 粒子群算法原理

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

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

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

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

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

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

1）粒子編碼方案

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

2）適應度函數(shù)

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

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

3）算法流程描述

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

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

輸入：候選特征的類別標簽集合{k}；模型訓練集的相似度矩陣集合{Matk}，集合成員與候選特征類別相對應。

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

1）Begin；

2）初始化粒子群；

3）Do；

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

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

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

7）Return{s}；

8）End。

1.4 最優(yōu)特征權重的計算

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

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

1）粒子編碼方案

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

2）適應度函數(shù)

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

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

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

3）算法流程描述

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

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

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

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

1）Begin；

2）初始化粒子群；

3）Do；

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

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

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

7）Return {ws*}；

8）End。

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

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

2 方法驗證與討論

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

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

圖2 部分實驗模型展示

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

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

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

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

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

3 結束語

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

[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] 萬麗莉,劉美琴.基于評價指標組合特征的三維模型檢索方法[J].計算機輔助設計與圖形學學報.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].系統(tǒng)仿真學報,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模型自動語義標注算法[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

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

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