摘  要： 為提高三維模型的檢索性能,，將聚類分析用于特征描述符的提取以及模型間相似性關(guān)系劃分等方面,，能夠?qū)θS模型進(jìn)行較為合理的分類，對較大規(guī)模三維模型數(shù)據(jù)庫的索引和組織進(jìn)行完善,，提高三維模型檢索效率,。針對當(dāng)前主流的基于聚類的三維模型檢索算法進(jìn)行分析，比較幾種聚類算法的優(yōu)勢與不足,，在其基礎(chǔ)上進(jìn)行改進(jìn),，并繼續(xù)應(yīng)用于三維模型的檢索中。
關(guān)鍵詞： 三維模型檢索,； 聚類,； 特征描述符； K-Means

    隨著多媒體技術(shù)和虛擬現(xiàn)實(shí)等技術(shù)的不斷提高,，三維模型在醫(yī)學(xué),、機(jī)械工程、計(jì)算機(jī)輔助設(shè)計(jì)(CAD)和娛樂等眾多領(lǐng)域都有廣泛應(yīng)用,，并在高度關(guān)注中不斷發(fā)展,。
    描述三維模型需要的信息量龐大，形成數(shù)據(jù)庫時(shí)模型間形狀和其他性質(zhì)的相似性關(guān)系復(fù)雜,，使得合理地組織三維模型數(shù)據(jù)庫非常困難,。同時(shí)，為了充分利用已有的模型資源,，迅速找到需要的三維模型,，對三維模型數(shù)據(jù)庫的構(gòu)建和三維模型的檢索都有極高的要求。
1 三維模型檢索
    對于龐大,、復(fù)雜的三維模型數(shù)據(jù)庫,，三維模型檢索的目的是要快速準(zhǔn)確地搜索出所需模型。在此檢索過程中,，模型特征的選取以及相似度的確定就顯得尤為重要,。一般來說，一個(gè)完整的模型檢索系統(tǒng)包括以下幾個(gè)部分：
    (1)特征描述符提取,。在計(jì)算機(jī)中存儲(chǔ)和顯示三維模型時(shí),，往往只記錄模型的頂點(diǎn)坐標(biāo)、拓?fù)溥B接等幾何屬性以及頂點(diǎn)顏色,、紋理等外觀屬性,，但這些在模型匹配計(jì)算中不僅數(shù)據(jù)量大，而且可能會(huì)隨模型形變等因素改變,，因此效率和準(zhǔn)確性都不高,。特征描述符SD(Shape Descriptor)是根據(jù)模型基本點(diǎn)、線,、面特點(diǎn)計(jì)算出的特征,，能夠盡量表達(dá)模型信息，容易被計(jì)算機(jī)應(yīng)用,。因此,如何提取更好的特征描述符成為三維模型檢索中首先要解決的問題,。一個(gè)理想的特征描述符應(yīng)具備一些特點(diǎn)[1]：易于表達(dá)和計(jì)算；不占用太多的存儲(chǔ)空間,；適合進(jìn)行相似性匹配,；具有幾何不變性，即對模型的平移,、旋轉(zhuǎn)和縮放等具有不變性,；具有拓?fù)洳蛔冃裕串?dāng)相同模型有多個(gè)拓?fù)浔硎緯r(shí),，SD應(yīng)是穩(wěn)定的,；SD對模型的絕大多數(shù)處理(如子分、模型簡化,、噪聲增減和變形等)是魯棒的,；SD必須具有唯一性，即不同類型的模型對應(yīng)的特征表示應(yīng)該不相同,。
    (2)特征匹配,。特征匹配的目的是得到模型間的相似程度，其匹配結(jié)果作為輸出檢索結(jié)果的依據(jù),。選取合適的算法,，對提取的特征描述符進(jìn)行相似性度量，也是一個(gè)重要的問題,。
    (3)模型分類,。三維模型資源龐大，需要建立一個(gè)分類數(shù)據(jù)庫以便提高模型查找效率,，該分類數(shù)據(jù)庫必須適合高級語義描述,。近年來的資料表明，將聚類分析用于對模型的分類,，能夠提高檢索速度,、查全率和查準(zhǔn)率。
    (4)搜索方法的研究,。有了已分類的模型數(shù)據(jù)庫作基礎(chǔ),，好的搜索方法則會(huì)使三維模型檢索更加高效,。
    (5)查詢接口的設(shè)計(jì)。一個(gè)成熟的三維模型檢索系統(tǒng)應(yīng)具有良好的交互性能,，擁有友好的界面,，方便用戶進(jìn)行查詢。
2 基于聚類分析的三維模型檢索算法
    聚類分析可以在沒有任何先驗(yàn)知識的情況下對三維模型檢索過程進(jìn)行處理,，如對特征描述符聚類或是對模型間相似性關(guān)系聚類,，最終達(dá)到將相似性高的模型聚為一簇(一組)，即對三維模型進(jìn)行高效分類,，提高三維模型檢索速度和準(zhǔn)確性,。
2.1 基于K-Means和Mean Shift的三維模型檢索算法
    基于K-Means和Mean Shift算法的三維模型檢索算法[2]是將聚類分析運(yùn)用于模型對稱特性的提取上，將得到的模型對稱信息作為模型特征描述符,。
     K-Means算法是一種基于劃分的聚類方法,，該算法是一種經(jīng)典聚類算法，后續(xù)的很多基于劃分的方法都是在其基礎(chǔ)上進(jìn)行的改進(jìn),。算法的具體過程如下：
    (1)選擇k值,，確定分類數(shù)目，即將目標(biāo)對象分為k類,。
    (2)在目標(biāo)對象中隨機(jī)選取k個(gè)初始聚類中心,。初始中心的選取很重要，不僅決定了以后的迭代次數(shù),，也影響著分類的準(zhǔn)確性,。
    (3)計(jì)算所有其他數(shù)據(jù)與聚類中心的距離，將其歸入離它最近的聚類中心所屬的類別,。
    (4)計(jì)算各個(gè)類中數(shù)據(jù)的平均值,，以此作為此類的中心值。
    (5)當(dāng)每個(gè)分類的中心值收斂時(shí),，停止聚類,；否則，重復(fù)步驟(3)~(5),。
    Mean Shift算法又稱均值漂移算法,是一種基于密度的聚類方法,。該方法通過反復(fù)迭代搜索數(shù)據(jù)集中數(shù)據(jù)點(diǎn)最密集的區(qū)間，聚類的中點(diǎn)沿著數(shù)據(jù)點(diǎn)密度增加的方向“漂移”到局部密度極大點(diǎn),。Mean Shift方法不需要預(yù)先指定數(shù)據(jù)集的分類個(gè)數(shù),，它是根據(jù)數(shù)據(jù)集中數(shù)據(jù)分布的密度對數(shù)據(jù)進(jìn)行分類的，通過設(shè)定閾值b來控制最終得到的分類數(shù)目,，使之處在一定范圍之內(nèi),。
    根據(jù)參考文獻(xiàn)[2]中所提到的方法，算法的實(shí)現(xiàn)過程如下：
    (1)數(shù)據(jù)樣本準(zhǔn)備,。獲取模型表面信息,，包括頂點(diǎn)信息,、面片信息、計(jì)算中心點(diǎn)以及三角面片面積等,，并進(jìn)行模型標(biāo)準(zhǔn)化處理,，使之位于標(biāo)準(zhǔn)坐標(biāo)系內(nèi)。
    (2)特征選擇,。對三維模型表面進(jìn)行采樣，利用隨機(jī)采樣點(diǎn)產(chǎn)生算法在模型表面均勻采樣,得到N個(gè)采樣點(diǎn),。
    (3)特征提取,。計(jì)算每兩個(gè)采樣點(diǎn)之間的對稱平面，得到N×(N-1)/2個(gè)對稱平面組成的集合P,。每個(gè)平面使用4個(gè)數(shù)據(jù)表示,，包括原點(diǎn)到平面的距離以及平面單位法向量的3個(gè)分量。
    (4)聚類,。在該算法中,，聚類分析用在對特征描述符的進(jìn)一步提取上。分別使用K-Means和Mean Shift兩種聚類算法對集合P中的數(shù)據(jù)進(jìn)行聚類,，得到模型的堆成平面P′,。用K-Means算法獲得的P′是一個(gè)K行4列的矩陣。而對于Mean Shift算法,，由于無法事先確定對稱平面?zhèn)€數(shù),，因此獲得的P′是一個(gè)任意行4列的矩陣。這就是最終得到的模型的特征描述符,。
    (5)分組,。模型分類的方式很多，仍舊可以選用聚類方法,。但這里所得到的特征描述符已經(jīng)是一個(gè)低維數(shù)據(jù),，直接使用距離算法簡單易行。采用歐幾里得距離計(jì)算2個(gè)模型特征矩陣之間的距離,，表示它們之間的相似程度,。
    參考文獻(xiàn)[2]中的實(shí)驗(yàn)結(jié)果表明，基于K-Means和Mean Shift算法的三維模型檢索算法的查全率和查準(zhǔn)率比傳統(tǒng)算法有顯著提高,。因此,，將聚類算法用在對特征描述符的處理上，是一種切實(shí)可行的聚類檢索算法,。
2.2 基于人工免疫聚類的三維模型檢索算法
    基于人工免疫聚類的三維模型檢索算法同樣是將聚類分析運(yùn)用于模型對稱特性的提取上,，將得到的模型對稱信息作為模型特征描述符。但不同的是,，采用人工免疫和K-Means混合算法進(jìn)行聚類分析,，提取特征描述符,，避免了K-Means算法對初始聚類中心極其敏感的不足，增強(qiáng)檢索穩(wěn)定性,。
    生物免疫系統(tǒng)中的克隆選擇原理[3]描述了免疫系統(tǒng)對抗原激勵(lì)做出免疫響應(yīng)的基本特性,。在基于克隆選擇原理的免疫算法中，抗原對應(yīng)于問題的目標(biāo)函數(shù),，抗體對應(yīng)于目標(biāo)函數(shù)的優(yōu)化解,。首先根據(jù)抗體的適應(yīng)值對解進(jìn)行評價(jià)和選擇，然后通過記憶細(xì)胞保留局部最優(yōu)解以保持解的多樣性,，再用類似于抗體的親和度來逐步改善優(yōu)化過程,，最終得到問題的全局最優(yōu)解。這種算法提高局部解空間的搜索效率,，并能避免局部最優(yōu)解的干擾,。
    將人工免疫和K-Means混合算法用于三維模型檢索中，其方法與2.1節(jié)中對模型表面隨機(jī)采樣,、提取特征平面一樣,，得到一個(gè)對稱平面組成的集合P。2.1節(jié)中將對稱平面P的處理運(yùn)用了K-Means和Mean Shift兩種聚類算法,，而在本試驗(yàn)中,，將采取人工免疫和K-Means混合算法得到最終的模型特征描述符。
    具體聚類過程如下：
    (1)選擇k值,，確定分類數(shù)目,，即將目標(biāo)對象分為k類。
    (2)產(chǎn)生k個(gè)抗體,。從P中(假設(shè)P中包含N個(gè)對稱平面)隨機(jī)抽取k個(gè)元素作為初始抗體,，即初始第0次迭代的聚類中心。
    (3)抗體分組,。采用歐幾里得距離作為測量指標(biāo),，根據(jù)N個(gè)元素與k個(gè)聚類中心間的距離，將其劃分到最近的簇,。
    (4)計(jì)算每一組包含的元素個(gè)數(shù)c,，對該組的聚類中心克隆c個(gè)副本，對這c個(gè)克隆抗體進(jìn)行變異,，變異速率和親和力相關(guān),，分別計(jì)算這c個(gè)克隆抗體中的每一個(gè)和c的抗原的親和力之和，選出親和力最大的抗體作為該次迭代的最佳抗體,，即下次迭代的聚類中心,。
    (5)如果抗體（即聚類中心）滿足最優(yōu)條件，則終止聚類，否則,，反復(fù)執(zhí)行步驟(3)~(5)繼續(xù)迭代,。
    至此就完成了對初始對稱平面集合P的聚類，得到模型的對稱平面集合P′(P′是一個(gè)k行4列的矩陣),，以此作為該模型的特征描述符,最后采用距離函數(shù)度量模型間的相似程度,。
   本算法利用人工免疫和K-Means混合算法對三維模型表面任意兩個(gè)采樣點(diǎn)的對稱平面數(shù)據(jù)集進(jìn)行處理，得到更加優(yōu)化的對稱平面矩陣作為特征描述符,。參考文獻(xiàn)[3]中的實(shí)驗(yàn)結(jié)果表明,，該算法比單純使用K-Means算法進(jìn)行檢索的效率更高。
2.3 基于FCM算法的三維模型檢索算法
      形狀分布算法(Shape Distribution)是一種簡單有效的三維物體相似性度量算法,。其主要思想是測量模型表面隨機(jī)采樣點(diǎn)之間的幾何距離,，將其概率分布繪制成直方圖，作為模型間相似度比較的基礎(chǔ),。其主要步驟為：首先將模型信息輸入,，提取特征點(diǎn),，即進(jìn)行隨機(jī)采樣,；再計(jì)算采樣點(diǎn)之間的距離；最后繪制成直方圖,，這個(gè)直方圖也就是該模型的特征描述符,。
     模糊均值聚類(FCM)算法是K-Means算法的改進(jìn)。K-Means算法能對大型數(shù)據(jù)進(jìn)行高效分類,，但通常會(huì)在獲得一個(gè)局部最優(yōu)值時(shí)終止,，其性能依賴于聚類中心的初始位置。解決的辦法可以是利用其他算法先求出好的初始聚類中心,，也可以是每次用不同的初始聚類中心計(jì)算多次求最好的結(jié)果,。而FCM算法把N個(gè)向量分成C個(gè)模糊組，并求每組的聚類中心,， 這樣就可使非相似性指標(biāo)[4]的價(jià)值函數(shù)達(dá)到最小,。K-Means算法是一種硬聚類算法，把每個(gè)樣本嚴(yán)格地劃分到某一類中,，但實(shí)際的模型對象不具有嚴(yán)格的所屬群組劃分特性,。而FCM算法采用模糊劃分，用0~1間的隸屬度來確定其所屬各個(gè)類群的程度,，它是一種軟劃分,，尤其對于模型分割效果很理想。
     根據(jù)參考文獻(xiàn)[5]中所提到的方法,，具體檢索算法的實(shí)現(xiàn)過程如下：
    (1)數(shù)據(jù)樣本準(zhǔn)備,，對模型進(jìn)行特征標(biāo)準(zhǔn)化。
    (2)特征提取。利用隨機(jī)采樣算法對模型表面進(jìn)行隨機(jī)點(diǎn)的選取,，統(tǒng)計(jì)采樣點(diǎn)之間的距離信息,，生成模型的形狀分布直方圖。該直方圖就是該模型的特征描述符,。
    (3)特征匹配,。利用FCM算法對模型的直方圖進(jìn)行模糊聚類劃分。將模型劃分為若干類,，確定初始聚類中心,，并開始迭代計(jì)算目標(biāo)函數(shù)。當(dāng)目標(biāo)函數(shù)最小時(shí),，聚類結(jié)束,。
    (4)分組。利用聚類進(jìn)行相似性度量后,，即完成了模型較好的分類,。當(dāng)進(jìn)行檢索時(shí)，只需輸出所有這一類模型作為檢索結(jié)果即可,。
    參考文獻(xiàn)[5]中的實(shí)驗(yàn)結(jié)果表明,，單純采用形狀分布算法，即直接使用距離函數(shù)進(jìn)行相似性度量的檢索精度比較低,。而本實(shí)驗(yàn)采用聚類分析方法進(jìn)行相似性度量,，能夠克服距離函數(shù)的不足，提高查全率和查準(zhǔn)率,。
    上述幾種基于聚類分析的三維模型檢索算法,，分別將K-Means算法或其改進(jìn)算法應(yīng)用于三維模型的特征提取和特征匹配過程中。實(shí)驗(yàn)結(jié)果表明,，上述算法增強(qiáng)了特征描述符的魯棒性,，減少了對于模型幾何形變和邊緣值的影響，抗干擾能力強(qiáng),，檢索結(jié)果查全率和查準(zhǔn)率都有顯著提高,。
    目前的三維模型檢索系統(tǒng)檢索效率和效果都不是很理想，各種研究中不斷對特征描述符的提取和特征匹配方法進(jìn)行改進(jìn),。聚類分析技術(shù)具有獨(dú)特的優(yōu)點(diǎn),，在圖像領(lǐng)域也有著很好的應(yīng)用。將聚類分析運(yùn)用于基于內(nèi)容的三維模型檢索是一個(gè)新的思路,，能夠提高檢索效率,，具有廣闊的應(yīng)用前景。
參考文獻(xiàn)
[1] 崔晨旸,石教英.三維模型檢索中的特征提取技術(shù)綜述[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),，2004,，16(7):882-889.
[2] 徐鵬捷,葉志偉,史川.基于聚類的三維模型檢索算法[J].現(xiàn)代計(jì)算機(jī),2009(10):71-74.
[3] 呂洋,劉平,唐奇峰.一種基于人工免疫聚類的三維模型檢索算法[J].現(xiàn)代計(jì)算機(jī),2011(2):57-59.
[4] 劉金春,蔣先剛,詹學(xué)峰.均值聚類在三維重構(gòu)圖像預(yù)處 理中的應(yīng)用[J].微計(jì)算機(jī)信息,2007,24(5-3):303-305.
[5] 景暉,黃美發(fā),鐘艷如.基于模糊C均值聚類算法的三維模型檢索[C].中國儀器儀表學(xué)會(huì)第九屆青年學(xué)術(shù)會(huì)議,