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

黃　驥，許威威，劉復昌

(杭州師范大學 杭州國際服務工程學院，浙江 杭州 311121)

?

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

黃驥，許威威，劉復昌

(杭州師范大學 杭州國際服務工程學院，浙江 杭州 311121)

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

三維模型檢索；特征優化；線性分類分析；核線性分類分析；形狀分布；形狀直徑函數

0　引言

三維模型是應用廣泛的多媒體數據類型。隨著三維建模技術的發展，三維模型的數量快速增長，形成了較大規模的三維模型庫。因此，三維模型檢索，即如何在三維模型庫中高效地檢索所需模型，已成為當今多媒體等領域中研究的熱點問題之一[1-3]。

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

圖1　本文算法流程

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

1　核線性分類分析

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

設有觀察數據集X，由多個n維向量構成，共分c個類。線性分類分析(LinearDiscriminantAnalysis,LDA)的目標是計算投影矩陣，使投影后的數據在子空間能有效保持原有空間的距離特征。由于投影空間的維度通常遠小于原空間，用投影數據可加速分類，并有效抑制數據噪聲[7-8]。圖2所示為LDA與PCA投影方向和分類邊界。LDA對類內方差Sw和類間方差Sb的優化可尋找到更恰當的分類邊界。

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

(1)

(2)

為實現數據降維，需要尋找一投影矩陣A使目標函數J(A)最大化，讓同類數據點的投影聚在類平均點投影的周圍，并讓不同類數據點在投影后盡量分開。

(3)

(4)

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

(5)

(6)

(7)

此時，分別考慮式(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)的優化方法類似于式(3)。

2　三維模型特征選取

2.1形狀分布

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

常見的形狀函數有A3、D1、D2等?？紤]實現的難易程度，本文采用D2函數。D2函數采樣過程如下：在L次采樣中，每次在兩個隨機選取的面內隨機各取一點，計算這兩點的距離，由此可得L個距離樣本d。

為了統計距離的分布情況，統計出在區間[k*p,(k+1)*p)中樣本的個數，其中0≤k

圖3　三維模型形狀分布

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

2.2形狀直徑函數

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

圖4　三維模型的SDF特征

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

3　實驗分析

本文算法中高維特征采用形狀分布及SDF[4-5]。算法測試了普林斯頓大學提供的benchmark庫和網上共享三維模型數據庫，共500個模型，25個小類。經投影后子空間的維度為20維。本文算法已在PC上實現并實驗驗證。

由于KFD起源于LDA，并較好地完善了LDA無法處理線性不可分樣本分類問題的不足，所以為驗證本文算法的優劣，本實驗對同一個三維模型數據庫進行搜索，再將搜索結果分別進行LDA、KFD計算。

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

圖5　準確率—查全率曲線

圖6　部分樣本LDA投影結果分布

圖7　部分樣本KFD投影結果分布

如圖6，LDA能解決低維空間中線性可分的分類問題，卻不能解決線性不可分的分類問題。此時用LDA優化特征的搜索準確率將低于未優化的特征。如圖7，KFD使在低維空間中線性不可分的樣本在高維空間中線性可分。在用Fisher準則設計線性分類的總體優化目標函數時，可得到與LDA線性投影類似的結果：在高維空間中線性可分的樣本能通過線性投影實現類與類之間的最優分離。因此KFD不僅能使搜索準確率優于未優化的形狀特征的搜索準確率，還更優于LDA得到的搜索準確率。

[9]采用深度信念網絡進行三維模型檢索，其結果評價采用準確率—查全率。當查全率在0.6～0.7時，相應的準確率為0.96～0.98，高于本文算法，其學習時間為120s，遠高于本文KFD的2.5s。

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

4　結論

本文提出并實現了一種利用KFD對高維三維模型特征進行降維和優化的算法。首先，計算出數據庫中三維模型的高維特征向量，由形狀分布和形狀直徑函數組成，然后，將所有三維模型的高維特征向量進行核函數計算，接著利用線性分類分析對計算出的高維特征進行降維優化，利用投影過后的特征進行三維模型匹配。實驗結果表明，經過特征優化后，那些與要查找模型相關聯較小模型的排序將有效下降。未來工作是進一步尋找更加有效的優化算法，如加快樣本在高維空間的非線性映射，進一步提高三維模型檢索的質量。

圖8　實驗1(SD)結果

圖9　實驗2(SD)結果

圖10　實驗3(SD+SDF)結果

圖11　實驗4(SD+SDF)結果

圖12　實驗5(SD+SDF)結果

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

[2] 楊育彬,林琿,朱慶.基于內容的三維模型檢索綜述[J].計算機學報, 2004,27(10): 1297-1310.

[3] 鄭伯川,彭維,張引,等.3D模型檢索技術綜述[J].計算機

輔助設計與圖形學學報,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)

國家自然科學基金(61272392，61502133)；浙江省自然科學基金一般項目(LY16F020029)

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

2016-04-14)

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

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

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

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