??? 摘 要： 針對三維模型" title="三維模型">三維模型檢索算法性能較低的問題，提出了一種改進的中軸骨架三維模型檢索" title="三維模型檢索">三維模型檢索算法。
??? 關鍵詞： 三維模型檢索,特征變換,中軸骨架,骨架二叉樹
?
??? 隨著激光掃描技術的發展以及計算機性能的提高，三維模型在很多應用領域中扮演著非常重要的角色，如工業產品的模型設計、虛擬現實系統、游戲設計、逆向工程以及仿真等，但是，要想構造一個真實感較強的模型其工作量巨大。目前在因特網和特定領域的數據庫中存在著數以兆計的模型，且還在源源不斷地增加。如果能夠重復利用已有模型，就可大大減小模型設計的工作量。因此，對三維模型檢索技術的研究已變得越來越緊迫和重要。
??? 目前，三維模型檢索主要采用基于內容的檢索方法。根據特征提取方法的不同，可將檢索方法大致分為四類：統計特征、函數投影、拓撲結構" title="拓撲結構">拓撲結構特征和基于幾何結構分析。
??? 基于統計特征的三維模型描述方法[1]，不需要通過模型進行標準化處理，因此計算較為簡單，具有良好的不變性。但是，這些特征描述模型之間相似性的能力普遍不夠強，對三維模型本身內容的描述也不夠充分。
??? 基于函數投影的方法首先是將原始的三維模型投影至一個標準函數模型中[2]，然后再計算特征向量。其優點在于其將三維模型投影為一系列不同視角的二維圖像，從而大大減低了匹配的復雜度。但在函數投影過程中容易丟失一些重要的三維結構信息，因此檢索的準確性不夠理想。
??? 基于模型拓撲結構特征的方法主要是根據模型的幾何信息和拓撲結構獲取模型的特征描述。Hilaga等人提出一種使用多分辨率Reeb圖MRG(Multiresolution Reeb Graph)結構表示三維模型的方法[3]。而Sundar利用模型骨架描述三維模型的特征[4]，該類方法能很好地描述模型本身的特征，可以獲得較高的檢索準確率，但該方法計算量較大。
??? 基于幾何結構分析的形狀特征的方法由于能較好地描述模型的高層結構信息而受到廣泛關注。Vranic等人[5]基于三維離散傅立葉變換的方法提取三維模型的特征。當三維模型可以被分割為一組規范化的特征集合并且特征之間的對應關系明確時，該方法具有很好的效果。然而，對于廣義的三維多邊形模型而言，實現上述條件是非常困難的。
??? 因此，如何提高三維模型的檢索性能，就成了十分突出的問題。本文提出一種基于整數中軸骨架的三維模型檢索算法，該算法的關鍵思想是將三維模型的拓撲特征和統計特征相結合。首先，對待匹配的三維模型進行預處理；然后改進Hesselink提出的整數中軸算法[6]，得到模型的中軸骨架，對骨架按區域劃分，構造骨架二叉樹" title="骨架二叉樹">骨架二叉樹，同時根據區域的大小定義節點的特征權值" title="權值">權值，用于衡量其對三維模型整體相似性的影響程度；最后，通過計算兩個骨架二叉樹的相似度，獲得兩個三維模型的相似度，在匹配過程中，采用由粗到細逐步淘汰的策略，不斷縮減待匹配模型的范圍，從而降低了模型匹配的時間。實驗結果表明，該算法可以得到較好的檢索性能。
1 模型預處理
??? 對于同一種檢索算法，處于不同坐標系下的三維模型應該具有相同的相似度。因此,檢索算法在計算三維模型幾何特征之前，應該對三維模型進行姿態調整，使其坐標系一致。
??? 本文采用主元分析法PCA(Principal Component Analysis)對模型進行姿態調整[7]。該方法首先根據三維模型點集合的協方差矩陣計算出相應的特征值λ1>λ2>λ3，其對應的特征矢量為(I1，I2，I3)，以(I1，I2，I3)為新的坐標系統，對三維模型進行坐標變換，得到變換后的坐標值。處理結果如圖1所示。
2 骨架提取
??? 設r是三維模型表面上的點，由Hesselink的整數中軸算法可得：
??? 若e∈E，(E={e∈I3||e||=1})，I3為模型內部的一個體素網格點，則當m=r+1/2e時：
??? ||m-ft(r+e)||=||m-ft(r)||????????????????? (1)
式中，m為整數中軸骨架上的一個骨架點，ft(r)為點r的特征變換函數。
??? 為了記錄以骨架點m為球心的內接球的半徑，對整數中軸骨架進行改進，定義一元函數：
??? σm=||m-ft(r)||????????????????????????????(2)
式中，σm為骨架點m的權值。
??? 由Hesselink整數中軸算法得到的骨架是一些比較散亂的骨架點，如圖2所示。而一個好的中軸骨架應具有以下三個特性：相鄰性、一致性和簡潔性[2]。因此，本文對獲得的骨架點進行以下優化。
?
??? 如果q為三維模型表面上的一個網格點，B是一個網格點的集合，則可以在中軸骨架上找到一個點p，使得p=IMAS(q)(IMAS(q)表示對點q進行整數中軸骨架變換)。同樣對于任意一個中軸骨架點p，對其進行整數中軸骨架變換的逆變換IMAS-1(p)，就會得到一個與其相對應的三維模型表面網格點的集合。設q∈B，p=IMAS(q)，點q和p之間的距離定義為dis(q)。定義一個輔助函數Average(dis(q))，其函數值為dis(q)(q∈IMAS-1(p))的平均值。所有的中軸骨架點應該滿足：
??? 
將所有優化后的骨架點連接起來形成加權骨架H，如圖3所示。
?
3 模型匹配
3.1 生成骨架二叉樹
??? 設δmax(ni)和δmin(ni)分別為骨架二叉樹節點ni對應的中軸骨架區域Zi的Z軸坐標最大值和最小值。在進行更高一級細節層次劃分時，按下面的公式計算每個區域的Z軸坐標最大值和最小值，骨架區域劃分示意圖如圖4所示。
??? 
??? 將區域Ci視為二叉樹節點ai，其權值Wai為：
??? 
3.2 匹配骨架二叉樹
??? 設ai和bi(0≤i≤n)為三維模型P、Q對應的骨架二叉樹中的節點，則它們的相似度函數為：
??? 
??? 設三維模型P、Q的相似度函數為：
??? 
??? 但是，在匹配過程中，由于模型的不同部分對模型整體的相似性的影響不同，因此對不同的sim(ai，bi)賦予不同的權值xi，對相似度函數加以改進，加入權值因子xi，改進的相似度函數為：
??? 
式中，
f(ai)為對應節點ai的區域大小，f(ao)為整個區域的大小。
??? 具體的匹配步驟如下：
??? (1)定義域值區間g=[0，β]，β∈R；生成兩個骨架二叉樹的根節點ao、bo，若sim(ao，bo)∈g，則繼續以下步驟；否則匹配結束，兩個模型不相似。
??? (2)若ai、bi為非葉子節點，則生成ai、bi的左孩子節點a2i+1和b2i+1，若sim(a2i+1，b2i+1)∈g，則繼續以下步驟；否則匹配結束，兩個模型不相似。
??? (3)若ai、bi為葉子節點，sim(ai，bi)∈g，則該分支的匹配結束，向上回溯到其父親節點，進行另一分支的匹配；若sim(ai，bi)∈g，則匹配結束，兩個模型不相似。
??? (4)生成ai和bi的右孩子節點a2i+2和b2i+2，若sim(a2i+2，b2i+2)∈g，則繼續以下步驟；否則匹配結束，兩個模型不相似。
??? (5)若二叉樹的任意節點ai和bi都滿足：sim(ai，bi)∈g，(0≤i≤n)，則兩模型相似。
??? (6)重復執行(2)～(5)。
4 實驗結果與分析
??? 為了測試算法的效果，對本文方法、中軸骨架方法和形狀分析方法的檢索性能進行了實驗和比較。實驗在Windows平臺上用VC++6.0語言實現，三維模型數據庫采用普林斯頓大學形狀分析小組提供的標準測試數據庫[8]，總共含有1 800個模型，采用典型的Precision-Recall曲線來度量不同方法的檢索性能，三種方法的檢索性能曲線如圖5所示。由圖可以看出，本文方法由于在拓撲結構的基礎上融入了統計特征，因此在檢索性能上有明顯提高。
??? 對于三維模型檢索，另一個值得注意的問題是檢索效率。如果檢索時間過長，將導致實時性差，即使檢索準確率有了明顯的改進，其實用性也不強。本文采用改進的中軸骨架提取方法，它與傳統的中軸骨架方法相比降低了算法的復雜度，但與形狀分布方法相比在算法復雜度上有所增加，比形狀分布方法需要更多的檢索時間。但是，這種檢索時間的差異很小，不會被用戶察覺。對三種模型檢索的具體實驗驗證環境是：CPU：Pentium 4 2.4GHz，內存512MB。對一批模型數據(40個模型)進行批處理，得到總檢索時間和平均檢索時間(檢索時間包括打開文件讀取模型數據的時間)如表1所示，檢索結果示例如圖6所示。
?
??? 三維模型檢索技術是近年來隨著三維模型獲取手段的增強、增多以及互聯網的發展而興起的計算機圖形學領域內的一個重要課題。針對三維模型檢索性能較低的問題，本文將三維模型的統計特征和拓撲特征相結合，提出了一種基于增強的中軸骨架三維模型檢索算法。通過對本文方法的檢索性能、檢索時間進行測試，結果表明，該算法可以得到較好的檢索性能。
參考文獻
[1] TANGELDER J W H，VEHKAMP R C.Polyhedral model?retrieval using weighted point sets.Journal of Image and?Graphics，2003，3(1)：209-229.
[2] 普建濤，劉一，辛谷雨，等.一種基于二維多邊形集相似性的三維模型檢索方法[J].中國圖像圖形學報，2004，9(12)：1437-1442.
[3] HILAGA M，SHINAGAWA Y，KOHMURA T，et a1.Topology matching for fully automatic similarity estimation of 3d?shapes proceedings of ACM SIGGRAPH.Los Angeles，USA，2001：203-212.
[4] SUNDAR H，SILVER D，GAGVANI N，et al.Skeleton based shape matching and retrieval? proceedings of international?conference on shape modeling and applications.Seoul，Korea，2003：207-216.
[5] VRANIC D，SAUPE D.3d shape descriptor based on 3d?Fourier transform? proceedings of IEEE EURASIP conference on digital signal processing for multimedia communications?and services.Budapest, Hungary，2001：271-274.
[6] HESSELLINK W H，VISSER M，ROERDINK J B T M.Euclidean skeletons of 3D data sets in linear time by the?integer medial axis transform[A].ISMM′2005[C].Paris，France，2005：259~268.
[7] VRANIC D，AAUPE D.3D shape descriptor based on 3D?fourier transform[A].EURASIP conference on digital signal?processing for multimedia communications and services[C].Budapest，Hungary：EURASIP，2001：271~274.
[8] SHILANE P，MICHAEL K，PATRICK M，et al．The princeton shape benchmark．In：Proc of the intern ational conference on shape modeling．Genova，Italy，2004：167-178.?
?