《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 其他 > 設(shè)計(jì)應(yīng)用 > 基于聚類分析的三維模型檢索綜述
基于聚類分析的三維模型檢索綜述
來源:微型機(jī)與應(yīng)用2012年第10期
毛 瑞, 唐 雁
(西南大學(xué) 計(jì)算機(jī)與信息科學(xué)學(xué)院, 重慶400715)
摘要: 為提高三維模型的檢索性能,將聚類分析用于特征描述符的提取以及模型間相似性關(guān)系劃分等方面,能夠?qū)θS模型進(jìn)行較為合理的分類,對(duì)較大規(guī)模三維模型數(shù)據(jù)庫的索引和組織進(jìn)行完善,提高三維模型檢索效率。針對(duì)當(dāng)前主流的基于聚類的三維模型檢索算法進(jìn)行分析,比較幾種聚類算法的優(yōu)勢與不足,在其基礎(chǔ)上進(jìn)行改進(jìn),并繼續(xù)應(yīng)用于三維模型的檢索中。
Abstract:
Key words :

摘  要: 為提高三維模型的檢索性能,將聚類分析用于特征描述符的提取以及模型間相似性關(guān)系劃分等方面,能夠?qū)θS模型進(jìn)行較為合理的分類,對(duì)較大規(guī)模三維模型數(shù)據(jù)庫的索引和組織進(jìn)行完善,提高三維模型檢索效率。針對(duì)當(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í),為了充分利用已有的模型資源,迅速找到需要的三維模型,對(duì)三維模型數(shù)據(jù)庫的構(gòu)建和三維模型的檢索都有極高的要求。
1 三維模型檢索
    對(duì)于龐大、復(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)行相似性匹配;具有幾何不變性,即對(duì)模型的平移、旋轉(zhuǎn)和縮放等具有不變性;具有拓?fù)洳蛔冃裕串?dāng)相同模型有多個(gè)拓?fù)浔硎緯r(shí),SD應(yīng)是穩(wěn)定的;SD對(duì)模型的絕大多數(shù)處理(如子分、模型簡化、噪聲增減和變形等)是魯棒的;SD必須具有唯一性,即不同類型的模型對(duì)應(yīng)的特征表示應(yīng)該不相同。
    (2)特征匹配。特征匹配的目的是得到模型間的相似程度,其匹配結(jié)果作為輸出檢索結(jié)果的依據(jù)。選取合適的算法,對(duì)提取的特征描述符進(jìn)行相似性度量,也是一個(gè)重要的問題。
    (3)模型分類。三維模型資源龐大,需要建立一個(gè)分類數(shù)據(jù)庫以便提高模型查找效率,該分類數(shù)據(jù)庫必須適合高級(jí)語義描述。近年來的資料表明,將聚類分析用于對(duì)模型的分類,能夠提高檢索速度、查全率和查準(zhǔn)率。
    (4)搜索方法的研究。有了已分類的模型數(shù)據(jù)庫作基礎(chǔ),好的搜索方法則會(huì)使三維模型檢索更加高效。
    (5)查詢接口的設(shè)計(jì)。一個(gè)成熟的三維模型檢索系統(tǒng)應(yīng)具有良好的交互性能,擁有友好的界面,方便用戶進(jìn)行查詢。
2 基于聚類分析的三維模型檢索算法
    聚類分析可以在沒有任何先驗(yàn)知識(shí)的情況下對(duì)三維模型檢索過程進(jìn)行處理,如對(duì)特征描述符聚類或是對(duì)模型間相似性關(guān)系聚類,最終達(dá)到將相似性高的模型聚為一簇(一組),即對(duì)三維模型進(jìn)行高效分類,提高三維模型檢索速度和準(zhǔn)確性。
2.1 基于K-Means和Mean Shift的三維模型檢索算法
    基于K-Means和Mean Shift算法的三維模型檢索算法[2]是將聚類分析運(yùn)用于模型對(duì)稱特性的提取上,將得到的模型對(duì)稱信息作為模型特征描述符。
     K-Means算法是一種基于劃分的聚類方法,該算法是一種經(jīng)典聚類算法,后續(xù)的很多基于劃分的方法都是在其基礎(chǔ)上進(jìn)行的改進(jìn)。算法的具體過程如下:
    (1)選擇k值,確定分類數(shù)目,即將目標(biāo)對(duì)象分為k類。
    (2)在目標(biāo)對(duì)象中隨機(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ù)分布的密度對(duì)數(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)特征選擇。對(duì)三維模型表面進(jìn)行采樣,利用隨機(jī)采樣點(diǎn)產(chǎn)生算法在模型表面均勻采樣,得到N個(gè)采樣點(diǎn)。
    (3)特征提取。計(jì)算每兩個(gè)采樣點(diǎn)之間的對(duì)稱平面,得到N×(N-1)/2個(gè)對(duì)稱平面組成的集合P。每個(gè)平面使用4個(gè)數(shù)據(jù)表示,包括原點(diǎn)到平面的距離以及平面單位法向量的3個(gè)分量。
    (4)聚類。在該算法中,聚類分析用在對(duì)特征描述符的進(jìn)一步提取上。分別使用K-Means和Mean Shift兩種聚類算法對(duì)集合P中的數(shù)據(jù)進(jìn)行聚類,得到模型的堆成平面P′。用K-Means算法獲得的P′是一個(gè)K行4列的矩陣。而對(duì)于Mean Shift算法,由于無法事先確定對(duì)稱平面?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)算法有顯著提高。因此,將聚類算法用在對(duì)特征描述符的處理上,是一種切實(shí)可行的聚類檢索算法。
2.2 基于人工免疫聚類的三維模型檢索算法
    基于人工免疫聚類的三維模型檢索算法同樣是將聚類分析運(yùn)用于模型對(duì)稱特性的提取上,將得到的模型對(duì)稱信息作為模型特征描述符。但不同的是,采用人工免疫和K-Means混合算法進(jìn)行聚類分析,提取特征描述符,避免了K-Means算法對(duì)初始聚類中心極其敏感的不足,增強(qiáng)檢索穩(wěn)定性。
    生物免疫系統(tǒng)中的克隆選擇原理[3]描述了免疫系統(tǒng)對(duì)抗原激勵(lì)做出免疫響應(yīng)的基本特性。在基于克隆選擇原理的免疫算法中,抗原對(duì)應(yīng)于問題的目標(biāo)函數(shù),抗體對(duì)應(yīng)于目標(biāo)函數(shù)的優(yōu)化解。首先根據(jù)抗體的適應(yīng)值對(duì)解進(jìn)行評(píng)價(jià)和選擇,然后通過記憶細(xì)胞保留局部最優(yōu)解以保持解的多樣性,再用類似于抗體的親和度來逐步改善優(yōu)化過程,最終得到問題的全局最優(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兩種聚類算法,而在本試驗(yàn)中,將采取人工免疫和K-Means混合算法得到最終的模型特征描述符。
    具體聚類過程如下:
    (1)選擇k值,確定分類數(shù)目,即將目標(biāo)對(duì)象分為k類。
    (2)產(chǎn)生k個(gè)抗體。從P中(假設(shè)P中包含N個(gè)對(duì)稱平面)隨機(jī)抽取k個(gè)元素作為初始抗體,即初始第0次迭代的聚類中心。
    (3)抗體分組。采用歐幾里得距離作為測量指標(biāo),根據(jù)N個(gè)元素與k個(gè)聚類中心間的距離,將其劃分到最近的簇。
    (4)計(jì)算每一組包含的元素個(gè)數(shù)c,對(duì)該組的聚類中心克隆c個(gè)副本,對(duì)這c個(gè)克隆抗體進(jìn)行變異,變異速率和親和力相關(guān),分別計(jì)算這c個(gè)克隆抗體中的每一個(gè)和c的抗原的親和力之和,選出親和力最大的抗體作為該次迭代的最佳抗體,即下次迭代的聚類中心。
    (5)如果抗體(即聚類中心)滿足最優(yōu)條件,則終止聚類,否則,反復(fù)執(zhí)行步驟(3)~(5)繼續(xù)迭代。
    至此就完成了對(duì)初始對(duì)稱平面集合P的聚類,得到模型的對(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)是一種簡單有效的三維物體相似性度量算法。其主要思想是測量模型表面隨機(jī)采樣點(diǎn)之間的幾何距離,將其概率分布繪制成直方圖,作為模型間相似度比較的基礎(chǔ)。其主要步驟為:首先將模型信息輸入,提取特征點(diǎn),即進(jìn)行隨機(jī)采樣;再計(jì)算采樣點(diǎn)之間的距離;最后繪制成直方圖,這個(gè)直方圖也就是該模型的特征描述符。
     模糊均值聚類(FCM)算法是K-Means算法的改進(jìn)。K-Means算法能對(duì)大型數(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í)際的模型對(duì)象不具有嚴(yán)格的所屬群組劃分特性。而FCM算法采用模糊劃分,用0~1間的隸屬度來確定其所屬各個(gè)類群的程度,它是一種軟劃分,尤其對(duì)于模型分割效果很理想。
     根據(jù)參考文獻(xiàn)[5]中所提到的方法,具體檢索算法的實(shí)現(xiàn)過程如下:
    (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)行模糊聚類劃分。將模型劃分為若干類,確定初始聚類中心,并開始迭代計(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)了特征描述符的魯棒性,減少了對(duì)于模型幾何形變和邊緣值的影響,抗干擾能力強(qiáng),檢索結(jié)果查全率和查準(zhǔn)率都有顯著提高。
    目前的三維模型檢索系統(tǒng)檢索效率和效果都不是很理想,各種研究中不斷對(duì)特征描述符的提取和特征匹配方法進(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ì)議,

此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載。