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

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