王鵬飛，舒振宇，于欣

(1.太原科技大學(xué)電子信息工程學(xué)院，太原 030024;

2.浙江大學(xué)寧波理工學(xué)院信息科學(xué)與工程學(xué)院，浙江 寧波 315100)

基于核主成分分析的三維模型分類算法

王鵬飛1，舒振宇2，于欣2

(1.太原科技大學(xué)電子信息工程學(xué)院，太原 030024;

2.浙江大學(xué)寧波理工學(xué)院信息科學(xué)與工程學(xué)院，浙江 寧波 315100)

針對三維模型的分類問題，提出了一種基于核主成分分析(Kernel-Principal Components A-nalysis，K-PCA)的三維模型分類算法。該算法首先選擇形狀直徑函數(shù)(Shape Diameter Function，SDF)作為特征描述符來提取三維模型的特征向量;然后使用核函數(shù)將原始特征向量映射到高維空間中并在該空間上進(jìn)行PCA得到新的特征向量;最后使用KNN算法并計算未知模型與已知類別的k個模型之間的l2范數(shù)以實現(xiàn)模型的分類，確定未知模型的類別。實驗結(jié)果表明，該算法能夠很好的識別三維模型的幾何特征，能準(zhǔn)確的區(qū)分不同類別的三維模型，具有較高的分類準(zhǔn)確率。

核主成分分析;三維模型;K近鄰;分類;形狀直徑函數(shù)

繼數(shù)字聲音、數(shù)字圖像和數(shù)字視頻之后，第四代多媒體數(shù)據(jù)類型——數(shù)字幾何模型已經(jīng)成為數(shù)字媒體技術(shù)的新發(fā)展趨勢。而作為數(shù)字幾何研究主體之一的三維模型正被廣泛應(yīng)用于工業(yè)設(shè)計、影視動畫和分子生物學(xué)等領(lǐng)域。三維模型是指對真實物體的表面進(jìn)行采樣、處理而得到的多邊形幾何數(shù)據(jù)。隨著大量三維模型的出現(xiàn)，對三維模型的相關(guān)研究工作也越來越多，其中三維模型分類就是一個重要問題。

三維模型分類(3D Model Classification)指的是如何根據(jù)離散曲面的內(nèi)在幾何特征和內(nèi)在語義特征，來對未知模型與已知類別的模型之間進(jìn)行相似性度量，從而判斷未知模型的類別。三維模型分類算法對于基于內(nèi)容的模型檢索具有重要的意義，目前國際上大部分三維模型數(shù)據(jù)庫在檢索方面提供的方法仍然是基于人工文本標(biāo)簽的方式，即通過人工的方式，為模型庫中每個模型加上若干個文本標(biāo)簽，用來描述對應(yīng)的模型。然后再由用戶通過搜索這些文本標(biāo)簽來定位到相應(yīng)的網(wǎng)格模型。該方法需要的人工量巨大，因此，急需某種算法能夠自動從曲面本身內(nèi)在特征的角度來進(jìn)行模型的檢索和分類。三維模型分類的關(guān)鍵在于如何選取特征描述符(Feature Descriptor)，該描述符是模型內(nèi)在特征的抽象描述，一般要求其與模型的旋轉(zhuǎn)、平移、縮放無關(guān)?；谔卣髅枋龇?，模型之間相似程度的衡量可以轉(zhuǎn)化為對其相應(yīng)特征描述符的比對。目前，網(wǎng)格模型分類算法［1-7］主要包括基于全局幾何特征的方法，基于局部幾何特征的方法，以及基于圖像特征的方法。如劉斌等［8］將PCA與ICP算法相結(jié)合，利用PCA方法將模型進(jìn)行初始定位，并用ICP進(jìn)行校準(zhǔn)，最后利用差值平方和函數(shù)對模型的相似性進(jìn)行度量。Wang等［9］使用核密度來估計樣本特征空間的分布進(jìn)而對三維模型進(jìn)行分類。馮立穎等［10］將三維模型輪廓上角點(diǎn)的曲率作為模型特征來提取，并使用Hausdorff距離進(jìn)行相似性比較。陳俊英等［11］將多個RBF神經(jīng)網(wǎng)絡(luò)進(jìn)行了集成，得到三維模型的特征信息，進(jìn)而對模型進(jìn)行分類。高思明等［12］提出了一種基于譜特征和深度信任網(wǎng)絡(luò)的模型分類方法。首先通過深度信任網(wǎng)絡(luò)對模型的譜特征進(jìn)行降維，再使用支持向量機(jī)對模型進(jìn)行分類。付小君等［13］提出一種基于統(tǒng)計特征量和Markov模型的分類算法，首先對三維模型進(jìn)行切分并將各分塊的統(tǒng)計特征量作為Markov模型的偽時間序列，進(jìn)而對模型進(jìn)行分類。一些非線性流形學(xué)習(xí)的方法［14-15］也被應(yīng)用到了三維網(wǎng)格模型分類問題上，并取得了一定的效果。

本文提出了一種基于核主成分分析(Kernel-Principal Components Analysis，K-PCA)的三維模型分類算法。針對三維模型姿勢不同對分類效果的影響，本文將具有姿勢不變的形狀直徑函數(shù)(Shape Diameter Function，SDF)作為特征描述符，提取出表現(xiàn)三維模型形狀特征的特征向量。在選擇特征向量的維數(shù)時會出現(xiàn):若維數(shù)選擇過低，特征向量所包含的模型特征信息會很少;若維數(shù)選擇過高，雖然特征向量包含大量特征信息，但由于維數(shù)過高在計算時會出現(xiàn)“維數(shù)災(zāi)難”問題。這都會影響模型分類的效果。為解決以上問題，本文采用核函數(shù)將原始特征向量進(jìn)行非線性高維映射并在高維空間中使用PCA以得到新的特征向量。算法的具體流程如圖1所示。

1 選擇特征描述符

三維模型是由三維空間中的三角面片通過邊和頂點(diǎn)的連接而形成的分片線性曲面，其中每條邊最多只能包含在兩個三角面片中。對于三維模型，可以用M={V}來表示，其中V={Ωi}(i=1，2，，p)，p為三維模型表面頂點(diǎn)的個數(shù)，每個頂點(diǎn)Ωi包含空間坐標(biāo)值(xi，yi，zi).為將三維模型的形狀特征用數(shù)值表現(xiàn)出來，就需要選擇特征描述符對三維模型進(jìn)行特征提取。本文使用形狀直徑函數(shù)(SDF)作為三維模型的特征描述符，提取出表現(xiàn)三維模型形狀特征的特征向量。

形狀直徑函數(shù)(SDF)最初被應(yīng)用在模型分割和骨架提取方面，這一概念是由Shapira［16］等提出的。三維模型可以看作是由多個二維網(wǎng)格表面圍成具有一定體積的特定空間，SDF就是定義在這些網(wǎng)格表面的標(biāo)量函數(shù)，它將三維模型的體積信息映射到其包圍的二維網(wǎng)格表面上，以實現(xiàn)對三維模型形狀特征的數(shù)值描述。使用SDF提取三維模型特征向量的具體步驟如下:

(1)計算三維模型表面三角面片中心點(diǎn)的SDF值

給定三維模型表面三角面片中心的一點(diǎn)?i(i= 1，2，，s)，其中s為三維模型表面三角面片的個數(shù)，在該點(diǎn)法線→n的反方向做一圓錐體，圓錐角的角度一般可選為120°.在圓錐體的內(nèi)部從點(diǎn)?i向模型內(nèi)部做射線段，均勻選擇若干條射線(一般情況下可選30條)并計算這些射線段的長度，將這些射線段長度的加權(quán)平均值作為該點(diǎn)的SDFi值。

(2)提取三維模型的特征向量

給定任意三維模型Mi，j(i=1，2，，n;j=1，2，，m)，其中n為三維模型的類別數(shù)，m為每類模型的個數(shù)。計算三維模型表面三角面片中心點(diǎn)?i(i= 1，2，，s)處的形狀直徑函數(shù)值SDFi和該三角面片的面積fi(i=1，2，，s)，其中s為三維模型表面三角面片的個數(shù)，將所有的SDFi(i=1，2，，s)值進(jìn)行加權(quán)直方圖統(tǒng)計，其中權(quán)值為fi(i=1，2，，s)，將區(qū)間［min(SDFi)，max(SDFi)］平均分成L個子區(qū)間，L即為模型特征向量的維數(shù)。將位于第j(j= 1，2，，L)個子區(qū)間內(nèi)所有SDF值所對應(yīng)的權(quán)值fi進(jìn)行加和，得到每個子區(qū)間的權(quán)重qj(j=1，2，，L)，最后對L個qj做歸一化處理即可得到模型的特征向量wi，j∈RL×1(i=1，2，，n;j=1，2，，m).

2 K-PCA算法描述

主成分分析(Principal Component Analysis，PCA)是對數(shù)據(jù)進(jìn)行特征提取的重要手段。每一個主成分都是數(shù)據(jù)在某一個方向上的投影，在不同的方向上這些數(shù)據(jù)方差的大小由其對應(yīng)的特征值決定。一般會選取較大的幾個特征值所對應(yīng)的特征向量，這些方向上的信息豐富，包含更多重要特征信息。PCA算法已經(jīng)應(yīng)用在二維圖像的識別中并取得較好的識別效果，如張秀琴等［17］將DCT和改進(jìn)的2D2PCA算法相結(jié)合，從而克服了二維主成分分析在魯棒性、識別速率上的不足，并成功應(yīng)用人臉識別中。但PCA的內(nèi)部模型是線性的，這就大大限制了PCA的應(yīng)用范圍。對于所研究對象是非線性的情況下，就需要利用核函數(shù)對PCA進(jìn)行非線性推廣。K-PCA算法首先利用一個非線性映射函數(shù)Φ將數(shù)據(jù)從輸入空間X映射到高維空間F中，然后對映射數(shù)據(jù)在空間F中實現(xiàn)PCA.K-PCA是一種非線性方法，它能有效的提取非線性特征。

2.1 算法原理

設(shè)x，z∈X，X屬于R(n)空間，非線性函數(shù)Φ實現(xiàn)輸入空間X到高維空間F的映射，其中F屬于R(m)，n＜＜m.根據(jù)核函數(shù)技術(shù)有:

其中:＜·＞為內(nèi)積，K(x，z)為核函數(shù)。由式(1)可知，核函數(shù)將m維高維空間的內(nèi)積運(yùn)算轉(zhuǎn)化為n維低維輸入空間的核函數(shù)計算，從而有效地解決了在高維特征空間中確定非線性映射函數(shù)的形式和參數(shù)、特征空間維數(shù)和計算時的“維數(shù)災(zāi)難”等問題。

PCA的算法原理為:假設(shè)有n個樣本X=［x1，x2，，xn］∈Rl×n，PCA的目的就是找到一系列的特征向量，使得樣本數(shù)據(jù)在這些特征向量上的投影方差盡量大。計算樣本的均值為并對樣本數(shù)據(jù)進(jìn)行預(yù)處理di=xi-u(i=1，2，，n)，使得新樣本數(shù)據(jù)的協(xié)方差矩陣為C=Rl×n.求協(xié)方差矩陣C的特征值λ和特征向量v，即Cv=λv.選擇特征值λ1≥λ2≥≥λn的前q個較大特征值對應(yīng)的特征向量V=［v1，v2，，vq］作為樣本的q個投影方向，得到PCA處理之后的樣本數(shù)據(jù)X'=［x1，x2，，xn］∈Rq×n，其中q≤l.

K-PCA是使用核函數(shù)對PCA的非線性推廣，將樣本數(shù)據(jù)X=［x1，x2，，xn］∈Rl×n通過非線性函數(shù)Φ映射到高維空間F中，即xi→Φ(xi)(i=1，2，，n).首先要對樣本數(shù)據(jù)進(jìn)行預(yù)處理，得到di=xiu(i=1，2，，n)，然后使用非線性函數(shù)Φ對數(shù)據(jù)進(jìn)行高維映射di→Φ(di)，計算經(jīng)過核函數(shù)映射的樣本數(shù)據(jù)的協(xié)方差矩陣其中DΦ=［Φ(d1)，Φ(d2)，，Φ(dn)］T.令K=DΦ(DΦ)T，則有:

由于非線性函數(shù)Φ的參數(shù)和形式未知，因而無法直接求取協(xié)方差矩陣CΦ的特征值與特征向量。所以需要先求解KuΦK=λΦKuΦK，其中K已知，λΦK和uΦK分別為矩陣K的特征值和特征向量。通過:

轉(zhuǎn)化即可求CΦvΦ=λΦCvΦ，得到協(xié)方差矩陣CΦ的特征值λΦC與特征向量vΦ，在高維空間F中，樣本數(shù)據(jù)［Φ(d1)，Φ(d2)，，Φ(dn)］在特征向量vΦ上的投影為:

其中(i=1，2，，n)，選擇前q個較大特征值對應(yīng)的特征向量VΦ=［vΦ1，vΦ2，，vΦq］，將樣本數(shù)據(jù)Φ(di)在這q個方向上做投影，得到在高維空間F上的PCA，即XΦ=［xΦ1，xΦ2，，xΦn］∈Rq×n，其中q≤l.

2.2 本文算法

本文首先利用基于姿勢不變的形狀直徑函數(shù)(SDF)來對三維模型進(jìn)行特征提取，提取出表現(xiàn)其形狀特征的特征向量，再利用核函數(shù)對特征向量進(jìn)行高維映射，以克服特征向量的非線性特征對模型分類效果的影響。然后使用主成分分析(PCA)在高維空間中進(jìn)行降維，提取出三維模型的主要特征。最后使用KNN算法對三維模型進(jìn)行分類識別。

算法的詳細(xì)步驟如下:

Step 1:計算三維模型表面三角面片中心點(diǎn)?i的形狀直徑函數(shù)值SDFi，其中(i=1，2，，s)，并進(jìn)行加權(quán)直方圖統(tǒng)計得到模型的特征向量wi，j∈RL×1，其中(i=1，2，，n;j=1，2，，m)，并對特征特征向量處理得到di，j∈RL×1(i=1，2，，n;j=1，2，，m);

Step 2:將所有三維模型的特征向量組成特征向量矩陣W，選擇合適的核函數(shù)對其進(jìn)行高維映射di，j→Φ(di，j);

Step 3:對映射后的矩陣求其協(xié)方差矩陣CΦ的特征值和特征向量，然后選擇協(xié)方差矩陣的前q個較大特征值所對應(yīng)的特征向量VΦ=［vΦ1，vΦ2，，vΦq］作為PCA的q個主方向;

Step 4:將特征向量Φ(di，j)和未知模型的特征向量yΦ在這q個方向上做投影，得到在高維空間F上的PCA，即WΦ=［WΦ1，WΦ2，，WΦn］∈Rq×mn和yΦ∈Rq.

Step 5:使用KNN算法在WΦ中找到距離yΦ∈Rq最近的k個特征向量A=［wΦ1，wΦ2，，wΦk］∈Rq×k，并計算yΦ∈Rq和A之間的l2范數(shù)以實現(xiàn)模型之間的分類，得到未知模型的類別。

3 實驗結(jié)論與討論

本文算法在SHREC'11三維模型數(shù)據(jù)庫［18］上進(jìn)行，該數(shù)據(jù)庫中共有600個非剛體三維模型，根據(jù)內(nèi)容分成30類，每類20個模型。該模型數(shù)據(jù)庫中的部分三維模型如表1所示。

表1 SHREC'11 non-rigid shapes三維模型數(shù)據(jù)庫中的部分模型Tab.1 Parts of the 3D models in SHREC'11 non-rigid shapes database

本實驗利用SHREC'11數(shù)據(jù)庫中的三維模型在MATLAB中進(jìn)行仿真實驗。實驗采用的計算硬件配置為Inter core(TM)i3 2.4 GHZ CPU，4 G內(nèi)存。為測試本文算法分類的準(zhǔn)確率，本文在模型數(shù)據(jù)庫的每類模型中隨機(jī)選擇10個作為測試模型，剩下的模型作為訓(xùn)練模型，因此測試模型和訓(xùn)練模型各有300個。在300個測試模型中任意選擇一個模型，在訓(xùn)練模型中進(jìn)行分類。用測試模型分類的平均準(zhǔn)確率作為算法精確度的評判標(biāo)準(zhǔn)。

3.1 僅使用KNN算法進(jìn)行模型分類

在使用特征描述符SDF對三維模型提取特征向量并進(jìn)行直方圖統(tǒng)計時，需要考慮特征向量的維數(shù)問題，即參數(shù)L的取值問題。對原始特征向量不做任何處理只使用KNN算法對模型進(jìn)行分類，來驗證參數(shù)L對分類效果的影響，其中參數(shù)L取值為25、50、100、200、400.參數(shù)L不同取值時模型分類的平均準(zhǔn)確率如圖2所示。

圖2 參數(shù)L取值不同時的平均準(zhǔn)確率(原始特征向量)Fig.2 The average success rates for the different values of the parameter L(the original feature vectors)

由圖2可知，隨著參數(shù)L的增加模型分類的平均準(zhǔn)確率總體呈下降的趨勢，當(dāng)L=25時，模型分類的平均準(zhǔn)確率為91%，L=400時模型分類的平均準(zhǔn)確率下降到86%.顯然，參數(shù)L選擇過大時，雖然特征向量所包含模型的特征信息很多，但是由于“維數(shù)災(zāi)難”問題，模型的分類效果并不理想。因此需要對原始特征向量進(jìn)行PCA降維，提取出模型主要的特征信息，以減少由于維數(shù)選擇對模型分類效果的影響。

3.2 僅使用PCA算法對原始特征向量進(jìn)行數(shù)據(jù)降維

對原始特征向量進(jìn)行主成分分析(PCA)，參數(shù)q取5，10，20，30，40，50.即將原始特征向量的維數(shù)降為q維，實驗結(jié)果如圖3所示。

圖3 僅使用于PCA算法時不同q值的結(jié)果比較圖Fig.3 The comparison chart of the result for the different value of q when used in the PCA algorithm

由圖3可知，橫軸為原始特征向量的維數(shù)，縱軸為對原始特征向量經(jīng)過PCA之后30類模型分類的平均準(zhǔn)確率。由圖可知，當(dāng)q=10時，模型的分類效果最好。隨著q取值的增加，模型分類的平均準(zhǔn)確率逐漸降低。當(dāng)q=5時，由于經(jīng)過PCA后的特征向量維數(shù)僅為5，新特征向量包含的模型特征信息大量減少，導(dǎo)致模型的分類效果并不理想。因此，在使用PCA算法時，參數(shù)q的取值為10，以保證模型的分類效果達(dá)到最好。

3.3 使用K-PCA算法對原始特征向量進(jìn)行處理

本文使用線性核函數(shù)k(x，xp)=x*xp、多項式核函數(shù)k(x，y)=(a(x·y)+b)d和高斯核函數(shù)k (x，y)=exp(-‖x-y‖/2σ2)來對原始數(shù)據(jù)進(jìn)行高維映射，并比較不同核函數(shù)對模型分類效果的影響，其中K-PCA時的參數(shù)q值選為10.實驗結(jié)果如圖4所示。

圖4 不同核函數(shù)比較結(jié)果圖Fig.4 The comparison results of the different kernel functions

由圖4可知，當(dāng)原始特征向量的維數(shù)L=50時，使用K-PCA算法對其進(jìn)行處理之后，模型分類的準(zhǔn)確率比直接使用KNN算法進(jìn)行分類的效果好。當(dāng)特征向量維數(shù)選擇過低造成的特征信息過少時，需要使用核函數(shù)對低維數(shù)據(jù)進(jìn)行高維映射，再使用PCA算法進(jìn)行降維，就可以解決由于維數(shù)選擇過高或過低而對模型分類的影響，從而提高分類的準(zhǔn)確度。實驗結(jié)果表明，由于數(shù)據(jù)本身是非線性的，單純使用PCA時的分類效果并不理想。因此使用核函數(shù)將原始數(shù)據(jù)映射到高維空間，在高維空間中對數(shù)據(jù)進(jìn)行PCA處理可以得到理想的分類效果。

選定核函數(shù)之后，需要比較單純進(jìn)行PCA和使用K-PCA這兩種情況時的模型分類效果。本文選用高斯核函數(shù)，參數(shù)q=10.僅使用PCA時，q取值為10.實驗結(jié)果如圖5所示。

由圖5可知，如果原始特征向量不經(jīng)過任何處理就進(jìn)行模型分類，隨著參數(shù)L的增加模型分類的準(zhǔn)確率逐漸下降。如果原始特征向量只做PCA處理，由于PCA的內(nèi)部模型是線性的，原始特征向量數(shù)據(jù)本身是非線性的，因此PCA的效果并不理想。如果將原始數(shù)據(jù)使用K-PCA進(jìn)行處理，即使用核函數(shù)將原始特征向量映射到高維空間中并在該空間使用PCA提取主要的特征，能夠得到好的模型分類效果。如圖6所示。

圖5 K-PCA與PCA算法的比較結(jié)果圖Fig.5 The comparison results chart of the PCA and the K-PCA algorithm

圖6 本文算法在各類模型上的平均準(zhǔn)確率Fig.6 The average success rates of our algorithm on every kind of model

由圖6可知，原始特征向量經(jīng)過K-PCA算法處理之后，大部分模型分類的準(zhǔn)確率都在90%以上，30類模型分類的平均準(zhǔn)確率可以達(dá)到96%.

本文還對算法在時間和空間的復(fù)雜度進(jìn)行了分析，隨著模型種類的增加，算法在時間和空間上的復(fù)雜度如圖7所示。

由圖7可知，當(dāng)模型數(shù)量在100時，耗時為0.174 s，占用的存儲空間為0.1 MB.當(dāng)模型數(shù)量增加到600時，耗時增加到0.617 s，占用的存儲空間增加到11 MB.

將本文算法與其他多個三維模型識別算法進(jìn)行比較，如多元支持向量機(jī)(multi-support vector machine，MultiSVM)［19］、K近鄰以及由Bronstein等［20］提出的SHIKS結(jié)合BOF作為特征描述符對三維模型進(jìn)行分類的新方法等。實驗選擇SHREC'11數(shù)據(jù)庫中的300個模型作為訓(xùn)練模型，300個模型作為測試模型。表2列出了所用的四種不同算法的分類準(zhǔn)確率和所用時間。

圖7 算法在時間和空間上復(fù)雜度分析結(jié)果圖Fig.7 The complexity analysis of the algorithm on the timeand the space

表2 不同算法的分類準(zhǔn)確率Tab.2 The average success rates of the different algorithm

實驗結(jié)果表明，本文算法分類準(zhǔn)確率相對較高，所用時間相對較少，更適用于實際應(yīng)用的三維模型分類識別中。

4 結(jié)論

本文提出了一種基于核主成分分析的三維模型分類算法。該算法首先選擇形狀直徑函數(shù)(SDF)作為特征描述符提取三維模型的特征向量。在數(shù)據(jù)本身是非線性的情況下，使用非線性的KPCA算法對三維模型的高維特征向量進(jìn)行主要特征的提取。最后使用KNN算法對三維模型進(jìn)行分類。本文算法具有簡單、準(zhǔn)確率高且易于實現(xiàn)等特點(diǎn)。

［1］ANKERST M，KASTENMüLLER G，KRIEGEL H P，et al.3D shape histograms for similarity search and classification in spatial databases［C］∥Advances in Spatial Databases.Springer Berlin Heidelberg，1999:207-226.

［2］ELAD M，TAL A，AR S.Content based retrieval of VRML objects—an iterative and interactive approach［M］.Springer Vienna，2002，18(3):107-118.

［3］ZHANG C，CHEN T.Efficient feature extraction for 2D/3D objects in mesh representation［C］∥Image Processing，2001.Proceedings of 2001 International Conference on IEEE，2001，3:935-938.

［4］HUBER D，KAPURIA A，DONAMUKKALA R，et al.Parts-based 3d object classification［C］∥Proceedings of the 2004 IEEE Computer Society Conference on IEEE，2004，2:Ⅱ-82-Ⅱ-89.

［5］CHUA C S，JARVIS R.Point signatures:A new representation for 3d object recognition［J］.International Journal of Computer Vision，1997，25(1):63-85.

［6］KAZHDAN M，F(xiàn)UNKHOUSER T，RUSINKIEWICZ S.Rotation invariant spherical harmonic representation of 3 D shape descriptors［C］∥Symposium on geometry processing.2003.

［7］OSADA R，F(xiàn)UNKHOUSER T，CHAZELLE B，et al.Matching 3D models with shape distributions［C］∥Shape Modeling and Applications，SMI 2001 International Conference on IEEE，2001:154-166.

［8］劉斌，上官寧，江開勇.三角網(wǎng)格模型分類分析［J］.華僑大學(xué)學(xué)報:自然科學(xué)版，2009，30(6):606-609.

［9］WANG Y，LU T，GAO R，et al.3D model comparison through kernel density matching［C］∥Pattern Recognition(ICPR)，2010 20th International Conference on IEEE，2010:3159-3162.

［10］馮立穎趙靜楊瑩.基于輪廓特征點(diǎn)的三維模型相似性分類算法［J］.計算機(jī)應(yīng)用，2010，30(4):914-916.

［11］陳俊英，王羨慧，方亞萍.基于RBF神經(jīng)網(wǎng)絡(luò)集成的三維模型分類和檢索［J］.圖學(xué)學(xué)報，2013，34(2):26-30.

［12］高恩陽，劉偉軍，王天然，等.基于譜特征和深度信任網(wǎng)絡(luò)的三維模型分類［J］.機(jī)械設(shè)計與制造，2013(3):250-252.

［13］付小君，郭鵬江，郭競，等.統(tǒng)計特征和Markov模型在三維模型分類中的應(yīng)用［J］.Computer Engineering and Applications，2011，47(4):157-159.

［14］ZHU K P，WONG Y S，LU W F，et al.3D CAD model matching from 2D local invariant features［J］.Computers in industry，2010，61(5):432-439.

［15］CHANG J S，SHIH A C C，LIN H Y，et al.3-D mesh representation and retrieval using Isomap manifold［C］∥Multimedia Signal Processing，2008 IEEE 10th Workshop on IEEE，2008:541-546.

［16］SHAPIRA L，SHAMIR A，COHEN-OR D.Consistent mesh partitioning and skeletonisation using the shape diameter function［J］.The Visual Computer，2008，24(4):249-259.

［17］張秀琴，陳立潮，潘理虎，等.基于DCT和分塊2D2PCA的人臉識別［J］.太原科技大學(xué)學(xué)報，2014，35(5):333-338.

［18］Shape Analysis Research Project.SHREC'11 3D Models Dataset［EB/OL］.［2014-10-09］.http:∥www.itl.nist.gov/iad/vug/ sharp/contest/2011/Non.

［19］LIU Y G，YOU Z S，CAO L P.A novel and quick SVM-based multi-class classifier［J］.Pattern Recognition，2006，39(11): 2258-2264.

［20］BRONSTEIN M M，KOKKINOS I.Scale-invariant heat kernel signatures for non-rigid shape recognition［C］∥Proceedings of 2010 IEEE Conference on Computer Vision and Pattern Recognition(CVPR).Los Alamitos:IEEE Computer Society Press，2010:1704-1711.

3D Model Classification Algorithm Based on Kernel Principal Component Analysis

WANG Peng-fei1，SHU Zhen-yu2，YU Xin2
(1.College of Electronic and Information Engineering，Taiyuan University of Science and Technology，

Taiyuan 030024，China;2.School of Information Science and Engineering，Ningbo Institute of Technology，Zhejiang University，Zhejiang Ningbo 315100，China)

In order to solve the problem of 3D model classification，a new algorithm，which is based on Kernel Principal Component Analysis(K-PCA)，is proposed.The algorithm firstly selects the Shape Diameter Function(SDF) as the feature descriptor to extract the original feature vectors.Then the original feature vectors are mapped to a high-dimensional space，and the PCA is adopted to reduce the dimension of original data for getting the new feature vectors.Finally，the KNN algorithm is applied to find k models in the known 3D model database，and the l2-norm between the unknown 3D model and the k models is calculated to predict the membership of the unknown model.The experimental results show that the algorithm can identify the geometry features of the 3D models and distinguish the difference of the models precisely.Besides，the algorithm is highly accurate.

Kernel-principal component analysis，3D Models，K-Nearest neighbor，classification，shape diameter function

TP391

A

10.3969/j.issn.1673-2057.2015.02.008

1673-2057(2015)02-0118-08

2014-11-06

國家自然科學(xué)基金(11226328，61374096);浙江省自然科學(xué)基金(LY13F020018);寧波市自然科學(xué)基金(2012A610068)

王鵬飛(1989-)，女，碩士研究生，主要研究方向為計算機(jī)圖形學(xué);通訊作者:舒振宇，副教授，E-mail:shuzhenyu@ 163.com