基于聚類分析的三維模型檢索綜述

毛瑞，唐雁

（西南大學 計算機與信息科學學院，重慶400715）

隨著多媒體技術和虛擬現實等技術的不斷提高，三維模型在醫學、機械工程、計算機輔助設計(CAD)和娛樂等眾多領域都有廣泛應用，并在高度關注中不斷發展。

描述三維模型需要的信息量龐大，形成數據庫時模型間形狀和其他性質的相似性關系復雜，使得合理地組織三維模型數據庫非常困難。同時，為了充分利用已有的模型資源，迅速找到需要的三維模型，對三維模型數據庫的構建和三維模型的檢索都有極高的要求。

1 三維模型檢索

對于龐大、復雜的三維模型數據庫，三維模型檢索的目的是要快速準確地搜索出所需模型。在此檢索過程中，模型特征的選取以及相似度的確定就顯得尤為重要。一般來說，一個完整的模型檢索系統包括以下幾個部分：

(1)特征描述符提取。在計算機中存儲和顯示三維模型時，往往只記錄模型的頂點坐標、拓撲連接等幾何屬性以及頂點顏色、紋理等外觀屬性，但這些在模型匹配計算中不僅數據量大，而且可能會隨模型形變等因素改變，因此效率和準確性都不高。特征描述符SD(Shape Descriptor)是根據模型基本點、線、面特點計算出的特征，能夠盡量表達模型信息，容易被計算機應用。因此,如何提取更好的特征描述符成為三維模型檢索中首先要解決的問題。一個理想的特征描述符應具備一些特點[1]：易于表達和計算；不占用太多的存儲空間；適合進行相似性匹配；具有幾何不變性，即對模型的平移、旋轉和縮放等具有不變性；具有拓撲不變性，即當相同模型有多個拓撲表示時，SD應是穩定的；SD對模型的絕大多數處理(如子分、模型簡化、噪聲增減和變形等)是魯棒的；SD必須具有唯一性，即不同類型的模型對應的特征表示應該不相同。

(2)特征匹配。特征匹配的目的是得到模型間的相似程度，其匹配結果作為輸出檢索結果的依據。選取合適的算法，對提取的特征描述符進行相似性度量，也是一個重要的問題。

(3)模型分類。三維模型資源龐大，需要建立一個分類數據庫以便提高模型查找效率，該分類數據庫必須適合高級語義描述。近年來的資料表明，將聚類分析用于對模型的分類，能夠提高檢索速度、查全率和查準率。

(4)搜索方法的研究。有了已分類的模型數據庫作基礎，好的搜索方法則會使三維模型檢索更加高效。

(5)查詢接口的設計。一個成熟的三維模型檢索系統應具有良好的交互性能，擁有友好的界面，方便用戶進行查詢。

2 基于聚類分析的三維模型檢索算法

聚類分析可以在沒有任何先驗知識的情況下對三維模型檢索過程進行處理，如對特征描述符聚類或是對模型間相似性關系聚類，最終達到將相似性高的模型聚為一簇(一組)，即對三維模型進行高效分類，提高三維模型檢索速度和準確性。

2.1 基于K-Means和Mean Shift的三維模型檢索算法

基于K-Means和Mean Shift算法的三維模型檢索算法[2]是將聚類分析運用于模型對稱特性的提取上，將得到的模型對稱信息作為模型特征描述符。

K-Means算法是一種基于劃分的聚類方法，該算法是一種經典聚類算法，后續的很多基于劃分的方法都是在其基礎上進行的改進。算法的具體過程如下：

(1)選擇k值，確定分類數目，即將目標對象分為k類。

(2)在目標對象中隨機選取k個初始聚類中心。初始中心的選取很重要，不僅決定了以后的迭代次數，也影響著分類的準確性。

(3)計算所有其他數據與聚類中心的距離，將其歸入離它最近的聚類中心所屬的類別。

(4)計算各個類中數據的平均值，以此作為此類的中心值。

(5)當每個分類的中心值收斂時，停止聚類；否則，重復步驟(3)～(5)。

Mean Shift算法又稱均值漂移算法,是一種基于密度的聚類方法。該方法通過反復迭代搜索數據集中數據點最密集的區間，聚類的中點沿著數據點密度增加的方向“漂移”到局部密度極大點。Mean Shift方法不需要預先指定數據集的分類個數，它是根據數據集中數據分布的密度對數據進行分類的，通過設定閾值b來控制最終得到的分類數目，使之處在一定范圍之內。

根據參考文獻[2]中所提到的方法，算法的實現過程如下：

(1)數據樣本準備。獲取模型表面信息，包括頂點信息、面片信息、計算中心點以及三角面片面積等，并進行模型標準化處理，使之位于標準坐標系內。

(2)特征選擇。對三維模型表面進行采樣，利用隨機采樣點產生算法在模型表面均勻采樣,得到N個采樣點。

(3)特征提取。計算每兩個采樣點之間的對稱平面，得到N×(N-1)/2個對稱平面組成的集合P。每個平面使用4個數據表示，包括原點到平面的距離以及平面單位法向量的3個分量。

(4)聚類。在該算法中，聚類分析用在對特征描述符的進一步提取上。分別使用K-Means和Mean Shift兩種聚類算法對集合P中的數據進行聚類，得到模型的堆成平面 P′。用K-Means算法獲得的 P′是一個 K行 4列的矩陣。而對于Mean Shift算法，由于無法事先確定對稱平面個數，因此獲得的P′是一個任意行4列的矩陣。這就是最終得到的模型的特征描述符。

(5)分組。模型分類的方式很多，仍舊可以選用聚類方法。但這里所得到的特征描述符已經是一個低維數據，直接使用距離算法簡單易行。采用歐幾里得距離計算2個模型特征矩陣之間的距離，表示它們之間的相似程度。

[2]中的實驗結果表明，基于K-Means和Mean Shift算法的三維模型檢索算法的查全率和查準率比傳統算法有顯著提高。因此，將聚類算法用在對特征描述符的處理上，是一種切實可行的聚類檢索算法。

2.2 基于人工免疫聚類的三維模型檢索算法

基于人工免疫聚類的三維模型檢索算法同樣是將聚類分析運用于模型對稱特性的提取上，將得到的模型對稱信息作為模型特征描述符。但不同的是，采用人工免疫和K-Means混合算法進行聚類分析，提取特征描述符，避免了K-Means算法對初始聚類中心極其敏感的不足，增強檢索穩定性。

生物免疫系統中的克隆選擇原理[3]描述了免疫系統對抗原激勵做出免疫響應的基本特性。在基于克隆選擇原理的免疫算法中，抗原對應于問題的目標函數，抗體對應于目標函數的優化解。首先根據抗體的適應值對解進行評價和選擇，然后通過記憶細胞保留局部最優解以保持解的多樣性，再用類似于抗體的親和度來逐步改善優化過程，最終得到問題的全局最優解。這種算法提高局部解空間的搜索效率，并能避免局部最優解的干擾。

將人工免疫和K-Means混合算法用于三維模型檢索中，其方法與2.1節中對模型表面隨機采樣、提取特征平面一樣，得到一個對稱平面組成的集合P。2.1節中將對稱平面P的處理運用了K-Means和Mean Shift兩種聚類算法，而在本試驗中，將采取人工免疫和KMeans混合算法得到最終的模型特征描述符。

具體聚類過程如下：

(1)選擇k值，確定分類數目，即將目標對象分為 k類。

(2)產生k個抗體。從P中(假設P中包含 N個對稱平面)隨機抽取k個元素作為初始抗體，即初始第0次迭代的聚類中心。

(3)抗體分組。采用歐幾里得距離作為測量指標，根據N個元素與k個聚類中心間的距離，將其劃分到最近的簇。

(4)計算每一組包含的元素個數c，對該組的聚類中心克隆c個副本，對這c個克隆抗體進行變異，變異速率和親和力相關，分別計算這c個克隆抗體中的每一個和c的抗原的親和力之和，選出親和力最大的抗體作為該次迭代的最佳抗體，即下次迭代的聚類中心。

(5)如果抗體（即聚類中心）滿足最優條件，則終止聚類，否則，反復執行步驟(3)～(5)繼續迭代。

至此就完成了對初始對稱平面集合P的聚類，得到模型的對稱平面集合 P′(P′是一個 k行 4列的矩陣)，以此作為該模型的特征描述符,最后采用距離函數度量模型間的相似程度。

本算法利用人工免疫和K-Means混合算法對三維模型表面任意兩個采樣點的對稱平面數據集進行處理，得到更加優化的對稱平面矩陣作為特征描述符。參考文獻[3]中的實驗結果表明，該算法比單純使用K-Means算法進行檢索的效率更高。

2.3 基于FCM算法的三維模型檢索算法

形狀分布算法(Shape Distribution)是一種簡單有效的三維物體相似性度量算法。其主要思想是測量模型表面隨機采樣點之間的幾何距離，將其概率分布繪制成直方圖，作為模型間相似度比較的基礎。其主要步驟為：首先將模型信息輸入，提取特征點，即進行隨機采樣；再計算采樣點之間的距離；最后繪制成直方圖，這個直方圖也就是該模型的特征描述符。

模糊均值聚類(FCM)算法是K-Means算法的改進。K-Means算法能對大型數據進行高效分類，但通常會在獲得一個局部最優值時終止，其性能依賴于聚類中心的初始位置。解決的辦法可以是利用其他算法先求出好的初始聚類中心，也可以是每次用不同的初始聚類中心計算多次求最好的結果。而FCM算法把N個向量分成C個模糊組，并求每組的聚類中心，這樣就可使非相似性指標[4]的價值函數達到最小。K-Means算法是一種硬聚類算法，把每個樣本嚴格地劃分到某一類中，但實際的模型對象不具有嚴格的所屬群組劃分特性。而FCM算法采用模糊劃分，用0～1間的隸屬度來確定其所屬各個類群的程度，它是一種軟劃分，尤其對于模型分割效果很理想。

根據參考文獻[5]中所提到的方法，具體檢索算法的實現過程如下：

(1)數據樣本準備，對模型進行特征標準化。

(2)特征提取。利用隨機采樣算法對模型表面進行隨機點的選取，統計采樣點之間的距離信息，生成模型的形狀分布直方圖。該直方圖就是該模型的特征描述符。

(3)特征匹配。利用FCM算法對模型的直方圖進行模糊聚類劃分。將模型劃分為若干類，確定初始聚類中心，并開始迭代計算目標函數。當目標函數最小時，聚類結束。

(4)分組。利用聚類進行相似性度量后，即完成了模型較好的分類。當進行檢索時，只需輸出所有這一類模型作為檢索結果即可。

參考文獻[5]中的實驗結果表明，單純采用形狀分布算法，即直接使用距離函數進行相似性度量的檢索精度比較低。而本實驗采用聚類分析方法進行相似性度量，能夠克服距離函數的不足，提高查全率和查準率。

上述幾種基于聚類分析的三維模型檢索算法，分別將K-Means算法或其改進算法應用于三維模型的特征提取和特征匹配過程中。實驗結果表明，上述算法增強了特征描述符的魯棒性，減少了對于模型幾何形變和邊緣值的影響，抗干擾能力強，檢索結果查全率和查準率都有顯著提高。

目前的三維模型檢索系統檢索效率和效果都不是很理想，各種研究中不斷對特征描述符的提取和特征匹配方法進行改進。聚類分析技術具有獨特的優點，在圖像領域也有著很好的應用。將聚類分析運用于基于內容的三維模型檢索是一個新的思路，能夠提高檢索效率，具有廣闊的應用前景。

參考文獻

[1]崔晨旸,石教英.三維模型檢索中的特征提取技術綜述[J].計算機輔助設計與圖形學學報，2004，16(7):882-889.

[2]徐鵬捷,葉志偉,史川.基于聚類的三維模型檢索算法[J].現代計算機,2009(10):71-74.

[3]呂洋,劉平,唐奇峰.一種基于人工免疫聚類的三維模型檢索算法[J].現代計算機,2011(2):57-59.

[4]劉金春,蔣先剛,詹學峰.均值聚類在三維重構圖像預處理中的應用[J].微計算機信息,2007,24(5-3):303-305.

[5]景暉,黃美發,鐘艷如.基于模糊 C均值聚類算法的三維模型檢索[C].中國儀器儀表學會第九屆青年學術會議,2007:449-452.