陳俊英， 王羨慧， 方亞萍

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

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

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

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

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

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

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

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

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

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

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

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

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

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

輸入：原始訓(xùn)練集

單個(gè)神經(jīng)網(wǎng)絡(luò)訓(xùn)練算法PSO-RBF；

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

初始化：神經(jīng)網(wǎng)絡(luò)集合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算法訓(xùn)練單個(gè)神經(jīng)網(wǎng)絡(luò)，將神經(jīng)網(wǎng)絡(luò)ht加入E，即E=E∪ht，根據(jù)在訓(xùn)練集上的結(jié)果返回ht:X×Y→ [0,1]；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 三維模型分類實(shí)驗(yàn)

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

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

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

表1 幾種分類方法的實(shí)驗(yàn)結(jié)果比較

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

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

3.2 三維模型檢索實(shí)驗(yàn)

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

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

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

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

4 總 結(jié)

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

[1]楊育彬, 林 琿, 朱 慶. 基于內(nèi)容的三維模型檢索綜述[J]. 計(jì)算機(jī)學(xué)報(bào), 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ìn)展[J]. 計(jì)算機(jī)學(xué)報(bào), 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.