基于核線性分類分析的三維模型檢索算法*

黃　驥，許威威，劉復(fù)昌

(杭州師范大學(xué) 杭州國(guó)際服務(wù)工程學(xué)院，浙江 杭州 311121)

?

基于核線性分類分析的三維模型檢索算法*

黃驥，許威威，劉復(fù)昌

(杭州師范大學(xué) 杭州國(guó)際服務(wù)工程學(xué)院，浙江 杭州 311121)

為提高檢索精確度，提出了一種利用核線性分類分析來對(duì)模型特征進(jìn)行優(yōu)化的新方法。其主要思想是通過滿足Mercer條件的非線性映射將低維空間下線性不可分的樣本映射到高維空間，在高維空間中利用線性分類分析將原有的三維模型特征投影到特定的子空間。該方法能夠在保持類間距離基礎(chǔ)上得到具有鑒別信息的低維特征用于三維模型檢索。實(shí)驗(yàn)結(jié)果表明，核線性分類分析方法速度較快，可在秒級(jí)完成三維特征優(yōu)化，同時(shí)優(yōu)化特征在本文測(cè)試數(shù)據(jù)集上可平均提高搜索準(zhǔn)確度15%。

三維模型檢索；特征優(yōu)化；線性分類分析；核線性分類分析；形狀分布；形狀直徑函數(shù)

0　引言

三維模型是應(yīng)用廣泛的多媒體數(shù)據(jù)類型。隨著三維建模技術(shù)的發(fā)展，三維模型的數(shù)量快速增長(zhǎng)，形成了較大規(guī)模的三維模型庫(kù)。因此，三維模型檢索，即如何在三維模型庫(kù)中高效地檢索所需模型，已成為當(dāng)今多媒體等領(lǐng)域中研究的熱點(diǎn)問題之一[1-3]。

三維模型檢索算法主要基于特征的匹配，即利用特征相似度來排序庫(kù)中的模型。研究人員已設(shè)計(jì)大量三維模型的全局特征，如形狀分布、形狀直徑函數(shù)(ShapeDiameterFunction,SDF)等[4-5]，在三維模型檢索系統(tǒng)應(yīng)用較早。同時(shí)三維模型的局部特征(如熱核等)也已應(yīng)用于解決部分模型檢索的問題[6]。雖然由現(xiàn)有的特征能得到較滿意的檢索結(jié)果，但因三維模型的客觀性，手工設(shè)計(jì)的特征的識(shí)別能力總有其局限性，查詢結(jié)果的質(zhì)量仍有提升空間。

圖1　本文算法流程

本文的主要思想是優(yōu)化現(xiàn)有的三維模型特征以提高搜索質(zhì)量，其算法流程如圖1所示。特征優(yōu)化算法以有監(jiān)督方式進(jìn)行，利用核線性分類分析(KernelFisherDiscriminantAnalysis,KFD)將三維模型特征映射到高維空間后降維，使降維的特征向量保持類間間距以提高搜索質(zhì)量。

1　核線性分類分析

圖2　LDA(實(shí)線)與PCA(虛線)的投影方向及分類邊界

設(shè)有觀察數(shù)據(jù)集X，由多個(gè)n維向量構(gòu)成，共分c個(gè)類。線性分類分析(LinearDiscriminantAnalysis,LDA)的目標(biāo)是計(jì)算投影矩陣，使投影后的數(shù)據(jù)在子空間能有效保持原有空間的距離特征。由于投影空間的維度通常遠(yuǎn)小于原空間，用投影數(shù)據(jù)可加速分類，并有效抑制數(shù)據(jù)噪聲[7-8]。圖2所示為L(zhǎng)DA與PCA投影方向和分類邊界。LDA對(duì)類內(nèi)方差Sw和類間方差Sb的優(yōu)化可尋找到更恰當(dāng)?shù)姆诸愡吔纭?/p>

為保持距離特征，LDA需在投影的特征空間中最小化Sw的跡并最大化Sb的跡。因此原有高維空間的數(shù)據(jù)的投影即可有效保持分類的距離特征。Sw和Sb定義如下，其中mk、m分別為第k類和所有樣本的平均點(diǎn)。

(1)

(2)

為實(shí)現(xiàn)數(shù)據(jù)降維，需要尋找一投影矩陣A使目標(biāo)函數(shù)J(A)最大化，讓同類數(shù)據(jù)點(diǎn)的投影聚在類平均點(diǎn)投影的周圍，并讓不同類數(shù)據(jù)點(diǎn)在投影后盡量分開。

(3)

(4)

然而當(dāng)F的維數(shù)很高甚至是無窮維時(shí)，難以直接求解式(4)。為此KFD用點(diǎn)積代替映射(使計(jì)算量與高維空間維度無關(guān))解決最大化問題。點(diǎn)積運(yùn)算可通過Mercer核實(shí)現(xiàn)：用核函數(shù)K(x,y)計(jì)算在F中x與y的點(diǎn)積。由再生核理論，任何第i類的投影向量Wi∈F必位于所有樣本在F的張集，故Wi可展開為如下形式：

(5)

(6)

(7)

此時(shí)，分別考慮式(4)的分子及分母：

(8)

(9)

式(8)和式(9)中M和R分別定義如下：

(10)

(11)

其中，E為單位陣，Q中所有元素為1/cj，Kj為第j類核矩陣，其第p行第q列的元素為K(Xp,Xq)。

將式(8)和(9)代入式(4)，可得：

(12)

式(12)的優(yōu)化方法類似于式(3)。

2　三維模型特征選取

2.1形狀分布

由于三維模型形狀的客觀性，為實(shí)現(xiàn)對(duì)其相似性進(jìn)行簡(jiǎn)單有效的度量，參考文獻(xiàn)[5]提出了形狀分布算法。該算法采用形狀函數(shù)來度量，即以模型表面采樣點(diǎn)間幾何屬性(如角度、距離等)的概率分布為比較依據(jù)，通過計(jì)算概率分布間的函數(shù)距離進(jìn)行相似性判定。

常見的形狀函數(shù)有A3、D1、D2等?？紤]實(shí)現(xiàn)的難易程度，本文采用D2函數(shù)。D2函數(shù)采樣過程如下：在L次采樣中，每次在兩個(gè)隨機(jī)選取的面內(nèi)隨機(jī)各取一點(diǎn)，計(jì)算這兩點(diǎn)的距離，由此可得L個(gè)距離樣本d。

為了統(tǒng)計(jì)距離的分布情況，統(tǒng)計(jì)出在區(qū)間[k*p,(k+1)*p)中樣本的個(gè)數(shù)，其中0≤k

圖3　三維模型形狀分布

獲取到形狀分布后，可以用PDFLN或CDFLN算法[5]來計(jì)算兩個(gè)三維模型形狀分布的相似度。

2.2形狀直徑函數(shù)

形狀直徑函數(shù)首先由SHAPIRAL[4]等人提出，并在模型分割與骨架提取算法的應(yīng)用中取得不錯(cuò)的實(shí)驗(yàn)效果。SDF是對(duì)三維模型表面上的點(diǎn)與周圍體素圍成的子模型的直徑的度量，用來比較模型的局部相似性。

圖4　三維模型的SDF特征

如圖4所示，在三維模型表面任意一點(diǎn)處，作一個(gè)以該點(diǎn)為圓錐頂點(diǎn)、該頂點(diǎn)法向量的反向?yàn)殚_口方向的圓錐。在圓錐范圍內(nèi)從頂點(diǎn)處引出若干射線與周圍三角面相交，去掉與頂點(diǎn)法向量同向的射線，取剩下的射線作加權(quán)平均，即得到該點(diǎn)處的SDF值。

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

本文算法中高維特征采用形狀分布及SDF[4-5]。算法測(cè)試了普林斯頓大學(xué)提供的benchmark庫(kù)和網(wǎng)上共享三維模型數(shù)據(jù)庫(kù)，共500個(gè)模型，25個(gè)小類。經(jīng)投影后子空間的維度為20維。本文算法已在PC上實(shí)現(xiàn)并實(shí)驗(yàn)驗(yàn)證。

由于KFD起源于LDA，并較好地完善了LDA無法處理線性不可分樣本分類問題的不足，所以為驗(yàn)證本文算法的優(yōu)劣，本實(shí)驗(yàn)對(duì)同一個(gè)三維模型數(shù)據(jù)庫(kù)進(jìn)行搜索，再將搜索結(jié)果分別進(jìn)行LDA、KFD計(jì)算。

圖5為實(shí)驗(yàn)所得到的準(zhǔn)確率—查全率曲線。查全率為檢索出的相關(guān)文件與系統(tǒng)中的所有相關(guān)文件之比，準(zhǔn)確率為檢索出的相關(guān)文件與系統(tǒng)中所有檢索到的文件之比。準(zhǔn)確率—查全率曲線廣泛用于評(píng)價(jià)三維模型的檢索質(zhì)量，反映了準(zhǔn)確率與查全率之間的關(guān)系。一般前者高則后者低。該曲線越靠上說明準(zhǔn)確性越高。如圖5，查全率相同時(shí)，基于多特征(SD+SDF)的搜索準(zhǔn)確率高于基于單特征(SD)；使用KFD優(yōu)化(SD+SDF+KFD、SD+KFD)的搜索準(zhǔn)確率高出未優(yōu)化特征15%(在SD+SDF+KFD和SD+SDF中，查全率約0.6～0.7時(shí)，前者準(zhǔn)確率約0.9～0.92，后者約0.6～0.7)，而使用LDA優(yōu)化 (SD+SDF+LDA、SD+LDA)的搜索準(zhǔn)確率反而低于未優(yōu)化的特征。

圖5　準(zhǔn)確率—查全率曲線

圖6　部分樣本LDA投影結(jié)果分布

圖7　部分樣本KFD投影結(jié)果分布

如圖6，LDA能解決低維空間中線性可分的分類問題，卻不能解決線性不可分的分類問題。此時(shí)用LDA優(yōu)化特征的搜索準(zhǔn)確率將低于未優(yōu)化的特征。如圖7，KFD使在低維空間中線性不可分的樣本在高維空間中線性可分。在用Fisher準(zhǔn)則設(shè)計(jì)線性分類的總體優(yōu)化目標(biāo)函數(shù)時(shí)，可得到與LDA線性投影類似的結(jié)果：在高維空間中線性可分的樣本能通過線性投影實(shí)現(xiàn)類與類之間的最優(yōu)分離。因此KFD不僅能使搜索準(zhǔn)確率優(yōu)于未優(yōu)化的形狀特征的搜索準(zhǔn)確率，還更優(yōu)于LDA得到的搜索準(zhǔn)確率。

[9]采用深度信念網(wǎng)絡(luò)進(jìn)行三維模型檢索，其結(jié)果評(píng)價(jià)采用準(zhǔn)確率—查全率。當(dāng)查全率在0.6～0.7時(shí)，相應(yīng)的準(zhǔn)確率為0.96～0.98，高于本文算法，其學(xué)習(xí)時(shí)間為120s，遠(yuǎn)高于本文KFD的2.5s。

圖8～12給出了部分檢索結(jié)果實(shí)例，圖中每?jī)尚袨橐粋€(gè)模型的檢索結(jié)果，第一行為優(yōu)化前的搜索結(jié)果，第二行為使用KFD優(yōu)化特征后的搜索結(jié)果。檢索采用基于實(shí)例的方法，算法輸入一個(gè)三維模型的特征向量，用此特征向量與模型庫(kù)中的模型比較。計(jì)算出模型庫(kù)中的模型與查詢實(shí)例的相似性，根據(jù)相似性從高到低進(jìn)行排列。以圖8為例，本文將圖中第1個(gè)三維模型作為檢索模型，比較了未優(yōu)化特征和優(yōu)化特征的效果。從圖8第1行得知：第1個(gè)模型與第2、3、5、6、8個(gè)模型同類，與第4、7個(gè)模型不同類，而第4、7個(gè)模型卻分別排在第5、8個(gè)模型之前，顯然該檢索效果欠佳；從圖8第2行得知：未優(yōu)化特征檢索結(jié)果得到優(yōu)化，使得與檢索模型同類的模型排名靠前，與檢索模型不同類的模型排名靠后，顯然該檢索效果較好。

4　結(jié)論

本文提出并實(shí)現(xiàn)了一種利用KFD對(duì)高維三維模型特征進(jìn)行降維和優(yōu)化的算法。首先，計(jì)算出數(shù)據(jù)庫(kù)中三維模型的高維特征向量，由形狀分布和形狀直徑函數(shù)組成，然后，將所有三維模型的高維特征向量進(jìn)行核函數(shù)計(jì)算，接著利用線性分類分析對(duì)計(jì)算出的高維特征進(jìn)行降維優(yōu)化，利用投影過后的特征進(jìn)行三維模型匹配。實(shí)驗(yàn)結(jié)果表明，經(jīng)過特征優(yōu)化后，那些與要查找模型相關(guān)聯(lián)較小模型的排序?qū)⒂行陆?。未來工作是進(jìn)一步尋找更加有效的優(yōu)化算法，如加快樣本在高維空間的非線性映射，進(jìn)一步提高三維模型檢索的質(zhì)量。

圖8　實(shí)驗(yàn)1(SD)結(jié)果

圖9　實(shí)驗(yàn)2(SD)結(jié)果

圖10　實(shí)驗(yàn)3(SD+SDF)結(jié)果

圖11　實(shí)驗(yàn)4(SD+SDF)結(jié)果

圖12　實(shí)驗(yàn)5(SD+SDF)結(jié)果

[1] 潘翔,葉修梓. 三維模型形狀分析和檢索[D].杭州: 浙江大學(xué), 2005.

[2] 楊育彬,林琿,朱慶.基于內(nèi)容的三維模型檢索綜述[J].計(jì)算機(jī)學(xué)報(bào), 2004,27(10): 1297-1310.

[3] 鄭伯川,彭維,張引,等.3D模型檢索技術(shù)綜述[J].計(jì)算機(jī)

輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2004,16(7): 873-881.

[4]SHAPIRAL,SHAMIRA,COHEN-ORD.Consistentmeshpartitioningandskeletonisationusingtheshapediameterfunction[J].TheVisualComputer, 2008, 24(4): 249-259.

[5]OSADAR,FUNKHOUSERT,CHAZELLEB,etal.Shapedistributions[J].ACMTransactionsonGraphics(TOG), 2002, 21(4): 807-832.

[6]BRONSTEINAM,BRONSTEINMM,GUIBASLJ,etal.ShapeGoogle:geometricwordsandexpressionsforinvariantshaperetrieval[J].ACMTransactionsonGraphics, 2011, 30(1): 623-636.

[7]BISHOPCM.Patternrecognitionandmachinelearning[M].NewYork:Springer, 2006.

[8]LiJianyuan,XiaYingjie,ShanZhenyu,etal.Scalableconstrainedspectralclustering[J].IEEETransactionsonKnowledgeandDataEngineering, 2015, 27(2): 589-593.

[9]BuShuhui,LiuZhenbao,

HanJunwei,etal.Learninghigh-levelfeaturebydeepbeliefnetworksfor3-Dmodelretrievalandrecognition[J].Multimedia,IEEETransactionson, 2014, 16(8): 2154-2167.

Optimized 3D shape retrieval using kernel fisher discriminant analysis

HuangJi，XuWeiwei，LiuFuchang

(CollegeofHangzhouInternationalInstitudeofServiceEngineering,HangzhouNormalUniversity,Hangzhou311121,China)

Inthispaper,kernelfisherdiscriminantanalysiswasadoptedtooptimizestate-of-the-art3Dshapefeatures,suchasshapedistributionandshapediameterfunction,toimprovetheprecisionofthequeryresults.Themainideawastomapthefeaturesintohigh-dimensionalspaceusingkernelmethodandthenexploittheabilityoflineardiscriminantanalysistomaintainclassseparationsoastoprojectthehighdimensional3Dshapefeaturestoasubspacethatcanbetterseparateclassestoimprovethediscriminativepoweroffeatures.Experimentalresultsshowthattheoptimizationof3Dshapedescriptorusingkernelfisherdiscriminantanalysiscanbecompletedwithinasecondandcanimprovethequeryprecisionby15%onaverageovershapedistribution.

3Dshaperetrieval;featureoptimization;lineardiscriminantanalysis(LDA);kernelfisherdiscriminantanalysis(KFD);shapedistribution;shapediameterfunction(SDF)

國(guó)家自然科學(xué)基金(61272392，61502133)；浙江省自然科學(xué)基金一般項(xiàng)目(LY16F020029)

TP18;TP391ADOI： 10.19358/j.issn.1674- 7720.2016.15.007

2016-04-14)

黃驥(1991-)，通信作者，男，碩士研究生，主要研究方向：三維幾何數(shù)字處理。E-mail: 332497012@qq.com。

許威威(1975-)，男，博士，浙江大學(xué)百人計(jì)劃特聘研究員，主要研究方向：計(jì)算機(jī)圖形圖像處理。

劉復(fù)昌(1982-)，男，博士，講師，主要研究方向：計(jì)算機(jī)圖形圖像處理。

引用格式：黃驥，許威威，劉復(fù)昌. 基于核線性分類分析的三維模型檢索算法[J].微型機(jī)與應(yīng)用，2016,35(15)：24-27.