陳俊英， 王羨慧， 方亞萍

（1. 西安建筑科技大學信息與控制工程學院，陜西 西安710055；2. 新疆大學信息科學與工程學院，新疆 烏魯木齊 830046；3. 中國寰球工程公司，北京100029）

三維模型分類是三維模型檢索領域的一個基礎性的研究課題，它是根據(jù)三維模型本身具有的各種特征參數(shù)判定其所屬的類別。模型分類信息有利于比較各種特征值的優(yōu)劣、組織模型庫、評價檢索效果等。

三維模型檢索是針對給定的查詢模型，檢索出符合用戶查詢意圖的模型集合的過程。為適應當前三維模型數(shù)量爆炸式增長和互連網(wǎng)搜索引擎規(guī)模與復雜性日益增強的形勢，三維模型檢索已從基于文本關(guān)鍵字檢索轉(zhuǎn)變?yōu)榛趦?nèi)容進行檢索[1]。基于內(nèi)容的三維模型檢索首先從模型所包含的內(nèi)容中用特征提取方法自動計算三維模型的特征，然后在特征空間中計算待查詢模型與目標模型之間的相似度，實現(xiàn)對三維模型庫的檢索?；趦?nèi)容的三維模型檢索方法的共同特點就是利用模型本身包含的低層特征，然而人類是以視覺上的高層語義來理解模型內(nèi)容的，這導致基于內(nèi)容的檢索效果并不盡如人意。為了解決“語義間隙”的問題，必須開展基于語義的三維模型檢索研究[2]。目前，從語義概念層次上進行三維模型內(nèi)容的描述和操縱在實現(xiàn)上面臨著巨大困難[3]。

為了縮短“語義間隙”，有些研究工作把模型特征相似性和模型分類信息綜合考慮，一種實現(xiàn)途徑是應用分類學習得到的分類信息，把檢索范圍限定在同類或相近的幾個類中進行，這樣可以使檢索的范圍大幅度縮小，有利于提高檢索的效率和檢索結(jié)果的有效性；另一種實現(xiàn)途徑就是在計算模型之間的相似性時，考慮分類信息的距離和特征向量距離兩部分[4]，這樣可以使檢索結(jié)果更符合用戶的檢索意圖。文獻[4]中每一類模型要用一個神經(jīng)網(wǎng)絡來學習，但只給出了5類模型上的實驗結(jié)果。

為了達到提高三維模型分類性能和借用分類信息提高檢索性能的目的，本文提出用RBF神經(jīng)網(wǎng)絡集成的方法對三維模型分類以解決三維模型分類遇到的維度高、樣本少的問題。然后把模型分類信息和特征信息組合用于三維模型檢索。最后，在普林斯頓模型庫中20類模型集上進行分類和檢索實驗。

1 基于RBF神經(jīng)網(wǎng)絡集成的三維模型分類

RBF網(wǎng)絡是由Broomhead和Lowe[5]通過觀察生物神經(jīng)元的局部反應而引進到神經(jīng)網(wǎng)絡范疇中，是一種可以實現(xiàn)任意非線性映射的前向神經(jīng)網(wǎng)絡。

RBF網(wǎng)絡結(jié)構(gòu)包括3層，分別為輸入層、隱含層和輸出層。每層功能不同，輸入層是源節(jié)點的組合，它把問題變量輸入到隱含層；隱含層由一組徑向基函數(shù)組成，它將輸入層空間非線性映射到隱含層空間。通常徑向基函數(shù)采取如式（1）的高斯函數(shù)形式：

其中，x為輸入向量，ui為第i個隱節(jié)點的中心向量，σi是第i個隱節(jié)點的半徑，φi(x)是第i個隱節(jié)點對應于輸入x的輸出。輸出層將隱含層的輸出進行線性加權(quán)，第j個輸出節(jié)點的值yj計算如式（2）

其中，wji是從第i個隱節(jié)點到第j個輸出節(jié)點的連接權(quán)值，N為隱節(jié)點中心個數(shù)。

三維模型對應的特征空間維度較高，相對于維數(shù)來說，訓練集樣本太少，使用單個神經(jīng)網(wǎng)絡分類存在難于收斂、分類正確率不高等缺陷。1990年，Hansen和Salamon[6]開創(chuàng)性地提出了神經(jīng)網(wǎng)絡集成(Neural Network Ensemble)方法。使用這種方法，可以簡單地通過訓練多個神經(jīng)網(wǎng)絡并將其結(jié)果進行合成，顯著地提高學習系統(tǒng)的泛化能力。在給三維模型分類時，可以先訓練多個弱分類器，然后用神經(jīng)網(wǎng)絡集成的方法給出最終的分類結(jié)果。

本文用粒子群優(yōu)化（Particle Swarm Optimization，簡稱PSO）算法[7]訓練集成中的個體RBF神經(jīng)網(wǎng)絡，該方法不需要預先設定隱節(jié)點個數(shù)，用包含隱節(jié)點個數(shù)、中心參數(shù)信息的粒子來表示一種神經(jīng)網(wǎng)絡配置信息，適應度函數(shù)考慮了分類正確率和隱節(jié)點個數(shù)兩個方面，這樣將RBF神經(jīng)網(wǎng)絡的訓練轉(zhuǎn)化為PSO算法針對適應度函數(shù)的最優(yōu)化問題。為了后續(xù)方便，我們把用PSO訓練RBF神經(jīng)網(wǎng)絡的方法簡稱為PSO-RBF方法[8]。

1.1 個體神經(jīng)網(wǎng)絡的生成

在神經(jīng)網(wǎng)絡集成方面的研究成果表明，要想獲得好的集成結(jié)果就要降低個體神經(jīng)網(wǎng)絡的誤差并增加神經(jīng)網(wǎng)絡間的差異。在生成有差異的個體網(wǎng)絡方面，本文用性能和適應性方面得到了廣泛認可的Boosting.M2算法[9]，基于Boosting.M2和PSO-RBF方法生成個體神經(jīng)網(wǎng)絡的算法如下：

輸入：原始訓練集

單個神經(jīng)網(wǎng)絡訓練算法PSO-RBF；

輸出：神經(jīng)網(wǎng)絡集合E；

初始化：神經(jīng)網(wǎng)絡集合E初始化為空集，權(quán)重向量=D(i) /(C-1)，其中，D(i) = 1N，(i=1,… ,N)，y∈Y-{yi} ；

Step1t= 1,2… ,T循環(huán)：

Step1.1 對i= 1,2… ,N循環(huán)式（3）、式（4）、式（5）：

Step1.2 根據(jù)權(quán)重分布Dt，采用輪盤賭方法抽取樣本，調(diào)用PSO-RBF算法訓練單個神經(jīng)網(wǎng)絡，將神經(jīng)網(wǎng)絡ht加入E，即E=E∪ht，根據(jù)在訓練集上的結(jié)果返回ht:X×Y→ [0,1]；

Step1.3 基于ht根據(jù)式（6）計算εt

Step1.4 設置βt=εt/(1 -εt)；

Step1.5 根據(jù)式（7）更新權(quán)重向量

其中，(i=1,… ,N),y∈Y-{yi}；

Step2 返回神經(jīng)網(wǎng)絡集合E，結(jié)束。

1.2 神經(jīng)網(wǎng)絡集成

在給三維模型分類時，先用boosting方法選取訓練樣本，用PSO-RBF方法在選取的訓練樣本上訓練RBF神經(jīng)網(wǎng)絡，最后用多個RBF神經(jīng)網(wǎng)絡集成的方法對數(shù)據(jù)分類。

神經(jīng)網(wǎng)絡集成的結(jié)果是將個體神經(jīng)網(wǎng)絡的輸出結(jié)果進行組合，用前面的表示方式，個體神經(jīng)網(wǎng)絡的集合為E，容量為T，對于輸入數(shù)據(jù)xi，第t個神經(jīng)網(wǎng)絡對應于第y(y∈Y)類的實際輸出表示為ht(xi,y)，wt為第t個神經(jīng)網(wǎng)絡對應的權(quán)重，則在輸入xi的情況下神經(jīng)網(wǎng)絡集成后的輸出為式（8）

三維模型基于內(nèi)容提取的特征具有多樣性和復雜性，同一類別的模型在特征空間上也可能相差甚遠，用單個神經(jīng)網(wǎng)絡難以有足夠的優(yōu)化能力和泛化能力。用神經(jīng)網(wǎng)絡集成的方法實現(xiàn)對三維模型的分類，有利于利用各個神經(jīng)網(wǎng)絡之間的差異性提高分類系統(tǒng)的優(yōu)化能力和泛化能力。

2 整合分類信息的三維模型檢索

整合分類信息進行檢索是為了減小內(nèi)容特征和高層語義檢索之間的隔閡，在整合形式上和以往不同，本文把分類信息當做計算相似性時的一項參數(shù)，模型之間的相似性度量包括特征距離和分類信息量化后的信息兩部分，兼顧了內(nèi)容特征和語義分類信息兩方面，有利于提高三維模型的檢索性能。

假設三維模型的特征向量空間為RD，類別y∈ { 1,… ,C}，任意兩個模型u和v的特征向量表示為xu=[xu,1, … ,xu,D]T和xv=[xv,1,… ,xv,D]T，將xu作為神經(jīng)網(wǎng)絡集成的輸入，神經(jīng)網(wǎng)絡集成的輸出表示為f(xu,y)，將xv作為神經(jīng)網(wǎng)絡集成的輸入，神經(jīng)網(wǎng)絡集成的輸出表示為f(xv,y)，則u和v的相似性距離δ(u,v)可以用特征向量之間的距離d(xu,xv)和分類信息的加權(quán)和來表示，相似性距離用式（9）計算

d(·,·)表示兩個向量之間的距離，dmax,x表示模型庫中任意兩個模型在特征空間上用d(·,·)計算的最大距離；d(f(xu,y) ,f(xv,y) )表示兩個模型分類結(jié)果用d(·,·)計算的距離，dmax,f表示模型庫中任兩個模型的分類信息用d(·,·)計算的最大距離，λ是平衡兩者所占比重的參數(shù)。

3 實驗分析

3.1 三維模型分類實驗

普林斯頓大學的三維模型檢索和分析研究小組建立了一個標準的實驗數(shù)據(jù)庫PSB。該數(shù)據(jù)庫共包含1814個模型，涵蓋自然界和日常生活常見的各類模型。該數(shù)據(jù)庫劃分成訓練子集和測試子集，每個子集分別包含907個三維模型，訓練子集包括90類，測試子集包括92類。訓練子集用于對檢索算法的初步測試和修改，而測試子集用于評估不同算法的優(yōu)劣。因為訓練子集和測試子集的類別并不完全相同。為了驗證本文方法，我們選取訓練子集和測試子集中同時具有的20個類別作為實驗數(shù)據(jù)，其中訓練集359個模型，測試集360個模型。

基于形狀分布（Shape Distribution，以下簡稱SD）的特征提取算法，其基本思想是統(tǒng)計模型表面上點分布的統(tǒng)計特征。因此，其特征值不依賴標準化過程，克服了標準化過程的不穩(wěn)定，具有較好的魯棒性。Osada R等[10]的研究成果指出在幾種圖形分布方法中D2分布法取得了較好的檢索效果，我們用D2法計算719個模型對應的64維特征集?；谌S模型的特征維數(shù)較高，應先用特征降維的方法來降低特征數(shù)據(jù)集的規(guī)模，減少無關(guān)或冗余特征對神經(jīng)網(wǎng)絡預測結(jié)果的干擾，提高神經(jīng)網(wǎng)絡的預測能力和個體網(wǎng)絡之間的差異度，我們在64維的特征集上應用文獻[11]的特征降維方法，得到15維的SD特征集作為實驗數(shù)據(jù)。

根據(jù)通常的設置，采用20個神經(jīng)網(wǎng)絡集成。實驗共運行10次，其平均結(jié)果作為三維模型分類性能的評價。表1列出了PSO-RBF方法、RBF神經(jīng)網(wǎng)絡集成與k近鄰分類方法的結(jié)果比較。k近鄰分類法是根據(jù)特征集的本質(zhì)屬性（特征向量之間的距離）計算出來的，與k近鄰分類法進行比較，可以看出神經(jīng)網(wǎng)絡集成分類法對特征集本質(zhì)分類能力提高的程度。k近鄰分類法就是計算距查詢模型最近的k個模型中正確分類的模型的比例。在這里，設置變化的k，k設置為模型庫中與查詢模型同類的模型數(shù)目。對所有查詢模型的k近鄰分類結(jié)果取平均作為模型庫上的k近鄰分類性能評價值。

表1 幾種分類方法的實驗結(jié)果比較

從表1中可以看到，個體網(wǎng)絡平均值在訓練集和測試集上分別取得58.02%和53.73%的分類準確率，比k近鄰分類法取得的41.07%和40.80%分別提高41.27%和31.69%。說明了PSO-RBF方法能有效提高三維模型的分類性能，但訓練得到的神經(jīng)網(wǎng)絡仍為弱分類器。

對個體神經(jīng)網(wǎng)絡進行集成后的平均分類性能比個體神經(jīng)網(wǎng)絡的平均分類性能在訓練集上提高65.53%，測試集上提高55.74%，說明采用本文的RBF神經(jīng)網(wǎng)絡集成方法大大提高了分類性能。10次實驗中最好的集成網(wǎng)絡取得了98.33%和85.56%的高分類準確率，最差的集成網(wǎng)絡也取得了93.87%和81.39%的分類準確率。這說明神經(jīng)網(wǎng)絡集成比單個神經(jīng)網(wǎng)絡更適宜于三維模型分類，是一種有效的三維模型分類方法。

3.2 三維模型檢索實驗

本次實驗使用的仍是分類實驗中使用的模型集，以便于利用分類結(jié)果進行下面的檢索實驗。利用最佳集成神經(jīng)網(wǎng)絡給出的分類輸出結(jié)果。然后用式（9）整合分類信息的方法計算模型之間的相似度。

圖1給出了整合分類信息方法和特征方法在測試集上的檢索結(jié)果。結(jié)果主要使用查準率-查全率圖、前50%的平均查準率、平均查準率、R-Precision、BEP和最近鄰檢索性能評估指標（定義見文獻[12]）來描述三維模型的檢索性能。給出的結(jié)果是對測試模型庫中的所有模型進行一次檢索，計算所有檢索結(jié)果的平均值作為檢索性能評價指標值。

圖1 整合分類信息方法和特征方法在測試集上的檢索結(jié)果

從圖1可以看到，整合分類信息方法的查準率-查全率曲線遠位于特征方法的曲線上方，說明整合分類信息方法顯著地提高了檢索性能。整合分類信息方法的5個性能指標值比不包括分類信息方法的5個性能評價指標分別提高62.1%、96.9%、77.8%、95.6%、51.5%。整合分類信息的方法的查準率-查全率曲線和特征方法的曲線在查全率越大的地方相差越大，這說明要求返回的檢索模型數(shù)越大的時候，分類信息所起的作用越大。

4 總 結(jié)

本文主要研究了基于RBF神經(jīng)網(wǎng)絡集成的三維模型分類方法和整合分類信息的三維模型檢索方法。在解決三維模型的分類問題時，針對三維模型特征空間的復雜性問題，用boosting方法集成RBF個體神經(jīng)網(wǎng)絡，個體神經(jīng)網(wǎng)絡訓練采用基于PSO的RBF神經(jīng)網(wǎng)絡自動化設計方法。在20類模型上的實驗結(jié)果表明RBF神經(jīng)網(wǎng)絡集成能大大提高三維模型的分類性能。在整合分類信息進行的檢索中，把分類器輸出結(jié)果之間的距離和特征空間上的距離進行加權(quán)計算，即考慮了模型內(nèi)容特征間的差別，同時通過加入分類信息參數(shù)項，又考慮了模型的語義分類信息。實驗結(jié)果表明整合分類信息的方法大大提高了檢索性能。

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

[2]Gao Boyong, Zheng Herong, Zhang Sanyuan. An overview of semantics processing in content-Based 3D model retrieval [C]//2009 International Conference on Artificial Intelligence and Computational Intelligence, Vol I, 2009: 54-59.

[3]潘 翔, 張三元, 梓 葉. 三維模型語義檢索研究進展[J]. 計算機學報, 2009, 32(6): 1069-1078.

[4]Wei Wei, Yang Yubin, Lin Jinjie, et al. Color-Based 3D model classification using Hopfield neural network [C]//International Conference on Computer Science and Software Engineering (CSSE 2008).Wuhan, Hubei, China, 2008: 883-886.

[5]Broomhead D S, Lowe D. Multivariable functional interpolation and adaptive networks [J]. Complex System, 1988, 2(1): 321-355.

[6]HL K, Neural P S. Network ensembles [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1990, 12(10): 993-1001.

[7]Kennedy J, Eberhart R. Particle swarm optimization [C]//Proceedings of IEEE International Conference on Neural Networks, Piscataway, 1995: 1942-1948.

[8]Qin Zheng, Chen Junying, Liu Yu, et al. Evolving RBF neural networks for pattern classification [C]//International Conference on Computational Intelligence and Security, China, 2005: 957-964.

[9]Freund Y, Robert E S. A decision-theoretic generalization of on-line learning and an application to boosting [J]. Journal of Computer and System Sciences, 1997, 55(1): 119-139.

[10]Osada R, Funkhouser T, Chazelle B, et al. Matching 3D models with shape distributions [C]//Proceedings of the International Conference on Shape Modeling and Applications, Genoa, 2001: 154-156.

[11]Chen Junying, Qin Zheng. Dimensionality reduction for evolving RBF networks with particle swarms [C]//Lecture Notes in Computer Science, Advances in Neural Networks, 2006: 1319-1325.

[12]Vranic D V. 3D model retrieval [D]. University of Leipzig. Germany, 2004.