多特征融合的非剛性三維模型匹配算法研究

賴　龍,　李海生,　蔡　強(qiáng),　毛典輝,　曹　健

(1.北京工商大學(xué) 計(jì)算機(jī)與信息工程學(xué)院,北京　100048;

2.北京工商大學(xué) 食品安全大數(shù)據(jù)技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室,北京　100048)

?

多特征融合的非剛性三維模型匹配算法研究

賴龍1,2,李海生1,2,蔡強(qiáng)1,2,毛典輝1,2,曹健1,2

(1.北京工商大學(xué) 計(jì)算機(jī)與信息工程學(xué)院,北京100048;

2.北京工商大學(xué) 食品安全大數(shù)據(jù)技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室,北京100048)

摘要：特征描述符是影響非剛性三維模型匹配結(jié)果的關(guān)鍵因素,而單一特征只能描述三維模型某一方面的信息.為了克服單一特征在模型匹配時的局限性,進(jìn)一步提高模型匹配的精確度,通過引入信息論中信息熵的概念,結(jié)合各單一特征匹配時的結(jié)果,計(jì)算得到各特征的權(quán)值,對多種特征(如熱核特征(HKS)、能量分布特征(WKS)和模型表面積特征等)進(jìn)行融合,作為非剛性三維模型匹配的特征.最后在SHREC’2014提供的標(biāo)準(zhǔn)測試數(shù)據(jù)集上進(jìn)行試驗(yàn),并與單一特征描述符的結(jié)果進(jìn)行對比,驗(yàn)證了多特征融合得到的特征描述符要優(yōu)于任一單一特征描述符,可以應(yīng)用于非剛性三維模型檢索系統(tǒng)中.

關(guān)鍵詞：非剛性; 信息熵; 多特征

三維模型是指在計(jì)算機(jī)中存儲的具有三維幾何信息的模型數(shù)據(jù),一般用網(wǎng)格或點(diǎn)云進(jìn)行表示.隨著各種三維建模軟件的廣泛使用,三維模型的數(shù)量呈指數(shù)級增長,獲取三維模型的方式也越來越多.如何提高現(xiàn)有的三維模型的復(fù)用率,幫助設(shè)計(jì)者在海量的三維模型中找到需要的三維模型,是一項(xiàng)非常有挑戰(zhàn)的任務(wù).目前比較著名的三維模型檢索系統(tǒng)有美國普林斯頓大學(xué)的形狀檢索與分析實(shí)驗(yàn)室研發(fā)的3D Model Search Engine,中國臺灣大學(xué)實(shí)現(xiàn)的基于光場描述符的3D Model檢索系統(tǒng)等.

三維模型主要分為剛性三維模型和非剛性三維模型.在理論上,若模型在發(fā)生形變時保持等距不變性、拉伸不變性、關(guān)節(jié)變形不變性、拓?fù)洳蛔冃缘?如人手模型姿態(tài)的變化[1]),該模型可被視為非剛性三維模型.常見的檢索系統(tǒng)大多針對剛性三維模型,剛性三維模型的處理分析方法更多關(guān)注平移、旋轉(zhuǎn)及縮放的不變性[2-3],不適用于非剛性的模型.目前已經(jīng)有一些學(xué)者提出了處理非剛性三維模型的方法,常見的有譜分解方法[4-5]和基于幾何特征的方法[6]等.其中,熱核特征(heat kernel signature,HKS)[7]和能量分布特征(wave kernel signature,WKS)[8]是譜分解方法中效果較好的特征.測地距離[9-10]和模型表面積屬于模型幾何特征[6],但是每種特征都存在一定的缺點(diǎn),如HKS只能保留模型低頻部分的信息,而導(dǎo)致模型高頻部分信息的缺失.WKS和模型表面積特征側(cè)重于模型宏觀上的整體信息;同時,在譜分解方法中,當(dāng)?shù)玫降奶卣髦捣浅＝咏鼤r,各特征值對應(yīng)的特征向量會對最終的特征描述符造成一定的影響.

傳統(tǒng)的單一特征描述符難以全面描述模型信息,Ortega等[11]證明對多種單一特征,通過加權(quán)融合后再進(jìn)行檢索可以得到更好的結(jié)果.國內(nèi)已有學(xué)者嘗試使用多特征融合去提高三維模型檢索的效率[12],但是他們的算法中特征融合的權(quán)值是基于用戶反饋的,算法流程相對復(fù)雜.本文提出的多特征融合的非剛性三維模型匹配算法,根據(jù)單一特征匹配的結(jié)果以及已知的分類信息分別計(jì)算每種算法的熵值,根據(jù)熵值得到該算法對應(yīng)的權(quán)值.最后在單一特征匹配結(jié)果的基礎(chǔ)上,得到最終的多特征融合的匹配結(jié)果.

1非剛性三維模型特征提取方法

通過綜合分析各種非剛性三維模型特征的特點(diǎn),本文將對HKS,WKS和模型表面積特征進(jìn)行融合.

1.1HKS特征提取

熱核特征反映了熱量在模型表面?zhèn)鬟f的過程,通過對不同時刻下,模型表面的熱量分布狀況來描述模型的表面及特征.熱核具有等距等容不變性的特點(diǎn),非常適合作為非剛性三維模型的特征描述符.對于一般的黎曼流形,構(gòu)造其Laplace-Beltrami算子是求得模型熱核的關(guān)鍵.在圖形圖像領(lǐng)域,通常用余切法去構(gòu)造Laplace-Beltrami算子.本文將采用Belkin等[13]提出的一種對余切法的改進(jìn)方法去近似表示該算子,這種方法可以克服原始的余切法在一般情況下不收斂的缺點(diǎn).

圖1　xi和xj之間的權(quán)值的確定

基于Laplace-Beltrami算子的特性,Sun等[7]提出了HKS特征的定義.對于模型上的任一點(diǎn)x在t時刻的HKS被定義為

(1)

1.2WKS特征提取

WKS特征反映了模型上各頂點(diǎn)在被作為不同能量等級的量子粒子情況下的概率分布.由于粒子的能量與其頻率有關(guān),WKS可以被視為是在一定時間條件下,模型上各點(diǎn)的頻率信息.模型表面各頂點(diǎn)關(guān)于時間的能量函數(shù)是Schr?dinger方程的解,如式(2)所示.

(2)

與HKS特征提取類似,根據(jù)模型的頂點(diǎn)信息使用改進(jìn)的余切法構(gòu)造其Laplace-Beltrami算子L.對L進(jìn)行特征分解,并只保留其最小的100～300個特征值及其對應(yīng)的特征向量.與HKS特征提取不同的是,對于t=0的時刻,模型將被設(shè)置一個初始能量E.根據(jù)一定規(guī)則,可以得到一個基于模型頂點(diǎn)能量的期望為E的概率分布.假設(shè)L的特征值不重復(fù),能量函數(shù)可以表示為

(3)

WKS作為平均的概率值,被定義為

(4)

由于eiEkt是正交的,WKS可以進(jìn)一步改寫為

(5)

從式(5)中可以看到,與HKS相比,這里不再有時間參數(shù),而有一個與初始能量E有關(guān)的函數(shù),初始能量E又與L的特征值有關(guān),這樣便避免了人為設(shè)置的時間t對模型特征的影響.

根據(jù)上面對于WKS的理論分析,在實(shí)際的實(shí)驗(yàn)中,模型上各點(diǎn)的WKS值被定義為

(6)

WKS(x,ζ)便是該模型的各點(diǎn)對應(yīng)的WKS特征.

1.3模型表面積特征提取

在各種基于幾何特征的方法中,基于模型表面積的特征提取是簡單高效的特征提取算法之一.模型表面積特征就是直接計(jì)算模型的表面積作為該模型的特征.這種方法雖然對模型的尺度敏感,且會忽略模型的局部細(xì)節(jié),但便于計(jì)算,對于存在非剛性形變的三維模型有很好的效果.Pickup等[6]的實(shí)驗(yàn)結(jié)果表明,這種算法的效果在一定程度上比某些復(fù)雜的算法(如HKS特征提取)更優(yōu)秀.

2非剛性三維模型多特征融合匹配算法實(shí)現(xiàn)

2.1基于信息熵的多特征權(quán)值分配

為了彌補(bǔ)單一特征在描述三維模型時的局限性,本文引入了多特征融合的方法.通過多個特征進(jìn)行融合可以更加全面地描述模型,根據(jù)所處理的模型庫的特點(diǎn),實(shí)現(xiàn)各個特征之間的取長補(bǔ)短,使各特征的優(yōu)勢最大化.

由于各種特征描述符對模型的描述能力不同,在進(jìn)行特征融合時,特征的權(quán)值是關(guān)鍵參數(shù).最簡單的處理方式是給各種特征賦相同的權(quán)值,但這種權(quán)值設(shè)定下進(jìn)行的實(shí)驗(yàn)結(jié)果很不理想.為了優(yōu)化權(quán)值分配,本文將信息論中信息熵的思想引入進(jìn)來,通過計(jì)算每種特征的信息熵去進(jìn)一步確定該特征對應(yīng)的權(quán)值.

對于有n個模型的數(shù)據(jù)集D,將f1,f2和f3這3種算法進(jìn)行融合,其權(quán)值分配方法如下:

(7)

(8)

c. 根據(jù)信息熵的定義,特征fi對應(yīng)的信息熵可表示為

(9)

進(jìn)而,計(jì)算出各特征的權(quán)值為

(10)

F1,F2和F3分別是f1,f2和f3的權(quán)值.

2.2多特征融合匹配算法實(shí)現(xiàn)流程

在得到各特征對應(yīng)的權(quán)值之后,可以對f1,f2和f3這3種算法進(jìn)行融合,提高匹配的精確度,其流程如下:

(11)

c. 模型l與其余模型在不同特征條件下計(jì)算的相似度進(jìn)行融合,如計(jì)算模型l與模型j在多特征融合后的相似度為

(12)

Sim是最終的相似度.通過該相似度,可以組成相似度矩陣,其中記錄了所處理的數(shù)據(jù)集中任兩個模型之間的相似度,對該矩陣中內(nèi)容進(jìn)行評估可以量化當(dāng)前匹配算法的優(yōu)劣.

3實(shí)驗(yàn)

3.1實(shí)驗(yàn)數(shù)據(jù)集

三維模型檢索競賽(3D SHape REtrieval Contest,簡稱SHREC)[14]是Eurographics舉辦的每年一屆的三維模型檢索大賽,幾乎每屆SHREC競賽都會提出新的非剛性三維模型的數(shù)據(jù)集,本文采用SHREC’2014提供的非剛性三維模型數(shù)據(jù)集[6]進(jìn)行試驗(yàn).SHREC’2014非剛性三維模型的數(shù)據(jù)集共有兩個子集,Real數(shù)據(jù)集和Synthetic數(shù)據(jù)集.Real數(shù)據(jù)集中的模型是直接掃描真實(shí)的人體構(gòu)建的,該數(shù)據(jù)集共包含400個姿態(tài)各異的模型.其中,每個模型的頂點(diǎn)數(shù)范圍為14 996～15 000,面片數(shù)范圍為29 968～29 996.Synthetic數(shù)據(jù)集中的模型則是用三維模型建模軟件生成的,該數(shù)據(jù)集的模型數(shù)量為300個,其中每個模型的頂點(diǎn)數(shù)范圍為60 086～60 277,面片數(shù)范圍為120 080～120 451.圖2是SHREC’2014提供的2個非剛性數(shù)據(jù)集示例.

圖2　SHREC’2014非剛性三維模型數(shù)據(jù)集示例

3.2性能評估標(biāo)準(zhǔn)

評估標(biāo)準(zhǔn)為國際上通用的由普林斯頓大學(xué)提出的評估標(biāo)準(zhǔn)[15],該標(biāo)準(zhǔn)主要評估基于某種特征的相似度矩陣,包括最近鄰方法(nearest neighbor,簡稱NN)、 第一層級(first-tier,簡稱1-T)和第二層級(second-tier,簡稱2-T)、E-度量(E-Measure,簡稱2-M )、折扣的累積結(jié)果(discounted cumulative gain,簡稱DCG).

a. 最近鄰方法:表示與待查詢模型同屬于一類的模型所占返回的檢索結(jié)果的比例,比例越低,則說明檢索出的相似結(jié)果越少.

b. 第一層級和第二層級:對于返回結(jié)果保存最相似的前K個模型 (K的大小與待查詢模型所在類的規(guī)模有關(guān)),第一層級和第二層級表示出現(xiàn)在前K個模型中,與輸入模型屬于同一類的模型所占的比例,該比例越低,說明檢索出的相似結(jié)果越少.對于待查詢模型的類別,可定義該類別包含模型數(shù)G,則對于第一層級來說,K=G,對于第二層級,K=2G.

c. E-度量:是一種改進(jìn)的Precision- Recall評價(jià)標(biāo)準(zhǔn).對于檢索結(jié)果,用戶更感興趣的應(yīng)該是前面頁面的檢索結(jié)果而不是后面頁面的檢索結(jié)果,因此E-Measure只考慮前32個檢索結(jié)果并計(jì)算Precision-Recall.其最大值為1.0,數(shù)值越大則檢索結(jié)果越好.

d. 折扣的累積結(jié)果:加權(quán)的正確結(jié)果的列表,其中越靠前權(quán)重越大.

3.3實(shí)驗(yàn)流程

本文實(shí)驗(yàn)是在內(nèi)存為2 GB,CPU為Intel 2.6 GHz雙核的PC機(jī)和Windows 8環(huán)境下完成的.

3.4實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)對比結(jié)果如表1和表2所示.

表1　Real數(shù)據(jù)集實(shí)驗(yàn)結(jié)果性能評估

表2　Synthetic數(shù)據(jù)集實(shí)驗(yàn)結(jié)果性能評估

同時,本文也將幾種單一特征描述符與多特征描述符的結(jié)果進(jìn)行了可視化對比,如圖3所示.縱坐標(biāo)表示各特征描述符采用5種不同的評估標(biāo)準(zhǔn)進(jìn)行評估時所對應(yīng)的結(jié)果,最大值為1.

從圖3中的直方圖可以明顯看到,無論是針對Real數(shù)據(jù)集還是Synthetic數(shù)據(jù)集,在單一特征的條件下,使用WKS特征和Surface特征的評估得分更高.而多特征融合的表現(xiàn)要明顯優(yōu)于單特征,在對Real數(shù)據(jù)集進(jìn)行處理時,多特征融合比效果最好的單一特征(WKS)提高了10%.對于在單特征條件下評分已經(jīng)很高的Synthetic數(shù)據(jù)集,多特征融合的評分依然高于任一單特征.

圖3　算法評估結(jié)果對比圖

為了直觀地觀察多特征融合之后的效果,本文分別隨機(jī)選取了Real數(shù)據(jù)集和Synthetic數(shù)據(jù)集中的一個模型作為輸入,計(jì)算它們與相應(yīng)數(shù)據(jù)集中的其余模型之間的相似度,對最相似的10個模型進(jìn)行可視化輸出,位置越靠左表示相似程度越高，結(jié)果如圖4所示(見下頁).模型①為Real數(shù)據(jù)集中的模型,模型②為Synthetic數(shù)據(jù)集中的模型,虛線框標(biāo)示的是錯誤的檢索結(jié)果.從圖4中的兩組結(jié)果可以看到,本文實(shí)驗(yàn)中所實(shí)現(xiàn)的4種方法,使用了多特征融合的檢索效果最好.

圖4　輸入模型查詢示例

4結(jié)論與展望

HKS,WKS等譜分解方法提取的特征是當(dāng)前針對非剛性三維模型的一類優(yōu)秀的特征.但是單一特征有一定的局限性,恰當(dāng)?shù)厝诤喜煌男螤钐卣骺墒顾鼈儍?yōu)勢互補(bǔ),更好地描述非剛性三維模型.本文提出了一種多特征融合的非剛性三維模型匹配算法,先計(jì)算待融合特征的信息熵,將該信息熵轉(zhuǎn)化成權(quán)值,對單一特征下的模型間相似度進(jìn)行加權(quán)融合,得到的相似度作為新的模型間相似度.通過使用普林斯頓大學(xué)的評估標(biāo)準(zhǔn)進(jìn)行評估以及進(jìn)行了模擬三維模型檢索的可視化展示可以看到,使用多特征融合可以在一定程度上提高模型匹配的效果.

在以后工作中,將繼續(xù)探索新的非剛性三維模型的特征描述符,并嘗試將本文中算法引入到實(shí)際的應(yīng)用中.

參考文獻(xiàn)：

[1]劉敏娟,崔建昆.手指可達(dá)工作空間的三維建模[J].上海理工大學(xué)學(xué)報(bào),2006,28(1):95-98.

[2]Li B,Lu Y J,Godil A,et al.A comparison of methods for sketch-based 3D shape retrieval[J].Computer Vision and Image Understanding,2014,119:57-80.

[3]Yang Y B,Lin H,Zhang Y.Content-based 3D model retrieval:a survey[J].IEEE Transactions on Systems,Man,and Cybernetics,Part C:Applications and Reviews,2007,37(6):1081-1098.

[4]Li C Y,Hamza A B.Spatially aggregating spectral descriptors for nonrigid 3D shape retrieval:a comparative survey[J].Multimedia Systems,2014,20(3):253-281.

[5]Litman R,Bronstein A M.Learning spectral descriptors for deformable shape correspondence[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2014,36(1):171-180.

[6]Pickup D,Sun X F,Rosin P L,et al.SHREC’14 track:shape retrieval of non-rigid 3D human models[C]∥Eurographics Workshop on 3D Object Retrieval.Strasbourg:The Eurographics Association,2014:101-110.

[7]Sun J,Ovsjanikov M,Guibas L.A concise and provably informative multi-scale signature based on heat diffusion[J].Computer Graphics Forum,2009,28(5):1383-1392.

[8]Aubry M,Schlickewei U,Cremers D.The wave kernel signature:a quantum mechanical approach to shape analysis[C]∥Proceedings of IEEE International Conference on Computer Vision Workshops (ICCV Workshops).Barcelona:IEEE,2011:1626-1633.

[9]Xin S Q,Wang G J.Improving Chen and Han’s algorithm on the discrete geodesic problem[J].ACM Transactions on Graphics (TOG),2009,28(4):104.

[10]Raviv D,Bronstein A M,Bronstein M M,et al.Affine-invariant geodesic geometry of deformable 3D shapes[J].Computers & Graphics,2011,35(3):692-697.

[11]Ortega M,Rui Y,Chakrabarti K,et al.Supporting similarity queries in MARS[C]∥Proceedings of the Fifth ACM International Conference on Multimedia.New York:ACM,1997:403-413.

[12]楊萌.基于多特征和相關(guān)反饋的三維模型檢索系統(tǒng)研究與實(shí)現(xiàn)[D].西安:西北大學(xué),2009.

[13]Belkin M,Sun J,Wang Y S.Discrete Laplace operator on meshed surfaces[C]∥Proceedings of the Twenty-Fourth Annual Symposium on Computational Geometry.New York:ACM,2008:278-287.

[14]Vandeborre J P,Tabia H.The seventh Eurographics workshop on 3D object retrieval[DB/OL].[2014-04-06].http:∥3dor2014.ensea.fr/People.html.

[15]Shilane P,Min P,Kazhdan M,et al.The princeton shape benchmark[C]∥ Proceedings of Shape Modeling Applications.New York:IEEE,2004:167-178.

(編輯:丁紅藝)

Non-rigid 3D Models Matching with Multi-feature Fusion

LAI Long1,2,LI Haisheng1,2,CAI Qiang1,2,MAO Dianhui1,2,CAO Jian1,2

(1.School of Computer and Information Engineering,Beijing Technology and Business University,Beijing 100048,China;2.Beijing Key Laboratory of Big Data Technology for Food Safety,Beijing 100048,China)

Abstract：Feature descriptors are the key factors influencing the result of non-rigid 3D model correspondence.But a single feature descriptor only contains one aspect of information of a 3D model.In order to overcome the limitation of single feature and further improve the accuracy of model correspondence,the entropy was introduced to calculate the weight of each single feature according to its correspondence results.The features of HKS(heat kernel signature),WKS(wave kernel signature) and surface area were fused with these weights.The effectiveness of the approach was evaluated by using the SHREC’2014 non-rigid 3D human models benchmark.In addition,the results outperform those of any state-of-the-art single feature descriptor,and can be used for non-rigid 3D model retrieval.

Keywords：non-rigid; entropy; multi-feature

中圖分類號：TP 391

文獻(xiàn)標(biāo)志碼：A

通信作者：李海生(1974-),男,教授.研究方向:計(jì)算機(jī)圖形學(xué)、科學(xué)可視化等.E-mail:lihsh@th.btbu.edu.cn

基金項(xiàng)目：國家重點(diǎn)實(shí)驗(yàn)室開放基金資助項(xiàng)目(BUAA-VR-14KF-04);北京市自然科學(xué)基金資助項(xiàng)目(4162019);北京市重點(diǎn)實(shí)驗(yàn)室專項(xiàng)基金資助項(xiàng)目(19008001069);北京市教委科研計(jì)劃一般項(xiàng)目(201610011010)

收稿日期：2014-12-23

DOI：10.13255/j.cnki.jusst.2016.01.014

文章編號：1007-6735(2016)01-0081-06

第一作者： 賴龍(1988-),男,碩士研究生.研究方向:三維模型檢索.E-mail:lailong@163.com