一種改進的中軸骨架三維模型檢索算法

1、    一種改進的中軸骨架三維模型檢索算法        張學鋒 時間:2008年07月03日     字 體: 大 中 小        關(guān)鍵詞:        ? 摘 要：關(guān)鍵詞： 三維模型檢索,特征變換,中軸骨架,骨架二叉樹?1，不需要通過模型進行標準化處理，因此計算較為簡

2、單，具有良好的不變性。但是，這些特征描述模型之間相似性的能力普遍不夠強，對三維模型本身內(nèi)容的描述也不夠充分。? 基于函數(shù)投影的方法首先是將原始的三維模型投影至一個標準函數(shù)模型中2，然后再計算特征向量。其優(yōu)點在于其將三維模型投影為一系列不同視角的二維圖像，從而大大減低了匹配的復雜度。但在函數(shù)投影過程中容易丟失一些重要的三維結(jié)構(gòu)信息，因此檢索的準確性不夠理想。? 基于模型拓撲結(jié)構(gòu)特征的方法主要是根據(jù)模型的幾何信息和拓撲結(jié)構(gòu)獲取模型的特征描述。Hilaga等人提出一種使用多分辨率Reeb圖MRG(Multiresolution Reeb Graph)結(jié)構(gòu)表示三維模型的方法3。而Sundar利用模型骨

3、架描述三維模型的特征4，該類方法能很好地描述模型本身的特征，可以獲得較高的檢索準確率，但該方法計算量較大。? 基于幾何結(jié)構(gòu)分析的形狀特征的方法由于能較好地描述模型的高層結(jié)構(gòu)信息而受到廣泛關(guān)注。Vranic等人5基于三維離散傅立葉變換的方法提取三維模型的特征。當三維模型可以被分割為一組規(guī)范化的特征集合并且特征之間的對應關(guān)系明確時，該方法具有很好的效果。然而，對于廣義的三維多邊形模型而言，實現(xiàn)上述條件是非常困難的。? 因此，如何提高三維模型的檢索性能，就成了十分突出的問題。本文提出一種基于整數(shù)中軸骨架的三維模型檢索算法，該算法的關(guān)鍵思想是將三維模型的拓撲特征和統(tǒng)計特征相結(jié)合。首先，對待匹配的三維模

4、型進行預處理；然后改進Hesselink提出的整數(shù)中軸算法61 模型預處理? 對于同一種檢索算法，處于不同坐標系下的三維模型應該具有相同的相似度。因此,檢索算法在計算三維模型幾何特征之前，應該對三維模型進行姿態(tài)調(diào)整，使其坐標系一致。? 本文采用主元分析法PCA(Principal Component Analysis)對模型進行姿態(tài)調(diào)整7。該方法首先根據(jù)三維模型點集合的協(xié)方差矩陣計算出相應的特征值1>2>3，其對應的特征矢量為(I1，I2，I3)，以(I1，I2，I3)為新的坐標系統(tǒng)，對三維模型進行坐標變換，得到變換后的坐標值。處理結(jié)果如圖1所示。2 骨架提取? 設r是三維模型表面

5、上的點，由Hesselink的整數(shù)中軸算法可得：? 若eE，(E=eI3|e|=1)，I3為模型內(nèi)部的一個體素網(wǎng)格點，則當m=r+1/2e時：? |m-ft(r+e)|=|m-ft(r)|? (1)式中，m為整數(shù)中軸骨架上的一個骨架點，ft(r)為點r的特征變換函數(shù)。? 為了記錄以骨架點m為球心的內(nèi)接球的半徑，對整數(shù)中軸骨架進行改進，定義一元函數(shù)：? m=|m-ft(r)|?(2)式中，m為骨架點m的權(quán)值。? 由Hesselink整數(shù)中軸算法得到的骨架是一些比較散亂的骨架點，如圖2所示。而一個好的中軸骨架應具有以下三個特性：相鄰性、一致性和簡潔性2。因此，本文對獲得的骨架點進行以下優(yōu)化。? 如

6、果q為三維模型表面上的一個網(wǎng)格點，B是一個網(wǎng)格點的集合，則可以在中軸骨架上找到一個點p，使得p=IMAS(q)(IMAS(q)表示對點q進行整數(shù)中軸骨架變換)。同樣對于任意一個中軸骨架點p，對其進行整數(shù)中軸骨架變換的逆變換IMAS-1(p)，就會得到一個與其相對應的三維模型表面網(wǎng)格點的集合。設qB，p=IMAS(q)，點q和p之間的距離定義為dis(q)。定義一個輔助函數(shù)Average(dis(q)，其函數(shù)值為dis(q)(qIMAS-1(p)的平均值。所有的中軸骨架點應該滿足：? 將所有優(yōu)化后的骨架點連接起來形成加權(quán)骨架H，如圖3所示。?3 模型匹配3.1 生成骨架二叉樹? 設max(ni)

7、和min(ni)分別為骨架二叉樹節(jié)點ni對應的中軸骨架區(qū)域Zi的Z軸坐標最大值和最小值。在進行更高一級細節(jié)層次劃分時，按下面的公式計算每個區(qū)域的Z軸坐標最大值和最小值，骨架區(qū)域劃分示意圖如圖4所示。? ? 將區(qū)域Ci視為二叉樹節(jié)點ai，其權(quán)值Wai為：? 3.2 匹配骨架二叉樹? 設ai和bi(0in)為三維模型P、Q對應的骨架二叉樹中的節(jié)點，則它們的相似度函數(shù)為：? ? 設三維模型P、Q的相似度函數(shù)為：? ? 但是，在匹配過程中，由于模型的不同部分對模型整體的相似性的影響不同，因此對不同的sim(ai，bi)賦予不同的權(quán)值xi，對相似度函數(shù)加以改進，加入權(quán)值因子xi，改進的相似度函數(shù)為：?

8、式中，f(ai)為對應節(jié)點ai的區(qū)域大小，f(ao)為整個區(qū)域的大小。? 具體的匹配步驟如下：? (1)定義域值區(qū)間g=0，R；生成兩個骨架二叉樹的根節(jié)點ao、bo，若sim(ao，bo)g，則繼續(xù)以下步驟；否則匹配結(jié)束，兩個模型不相似。? (2)若ai、bi為非葉子節(jié)點，則生成ai、bi的左孩子節(jié)點a2i+1和b2i+1，若sim(a2i+1，b2i+1)g，則繼續(xù)以下步驟；否則匹配結(jié)束，兩個模型不相似。? (3)若ai、bi為葉子節(jié)點，sim(ai，bi)g，則該分支的匹配結(jié)束，向上回溯到其父親節(jié)點，進行另一分支的匹配；若sim(ai，bi)g，則匹配結(jié)束，兩個模型不相似。? (4)生成a

9、i和bi的右孩子節(jié)點a2i+2和b2i+2，若sim(a2i+2，b2i+2)g，則繼續(xù)以下步驟；否則匹配結(jié)束，兩個模型不相似。? (5)若二叉樹的任意節(jié)點ai和bi都滿足：sim(ai，bi)g，(0in)，則兩模型相似。? (6)重復執(zhí)行(2)(5)。4 實驗結(jié)果與分析? 為了測試算法的效果，對本文方法、中軸骨架方法和形狀分析方法的檢索性能進行了實驗和比較。實驗在Windows平臺上用VC+6.0語言實現(xiàn)，三維模型數(shù)據(jù)庫采用普林斯頓大學形狀分析小組提供的標準測試數(shù)據(jù)庫8，總共含有1 800個模型，采用典型的Precision-Recall曲線來度量不同方法的檢索性能，三種方法的檢索性能曲線

10、如圖5所示。由圖可以看出，本文方法由于在拓撲結(jié)構(gòu)的基礎上融入了統(tǒng)計特征，因此在檢索性能上有明顯提高。? 對于三維模型檢索，另一個值得注意的問題是檢索效率。如果檢索時間過長，將導致實時性差，即使檢索準確率有了明顯的改進，其實用性也不強。本文采用改進的中軸骨架提取方法，它與傳統(tǒng)的中軸骨架方法相比降低了算法的復雜度，但與形狀分布方法相比在算法復雜度上有所增加，比形狀分布方法需要更多的檢索時間。但是，這種檢索時間的差異很小，不會被用戶察覺。對三種模型檢索的具體實驗驗證環(huán)境是：CPU：Pentium 4 2.4GHz，內(nèi)存512MB。對一批模型數(shù)據(jù)(40個模型)進行批處理，得到總檢索時間和平均檢索時間(

11、檢索時間包括打開文件讀取模型數(shù)據(jù)的時間)如表1所示，檢索結(jié)果示例如圖6所示。? 三維模型檢索技術(shù)是近年來隨著三維模型獲取手段的增強、增多以及互聯(lián)網(wǎng)的發(fā)展而興起的計算機圖形學領域內(nèi)的一個重要課題。針對三維模型檢索性能較低的問題，本文將三維模型的統(tǒng)計特征和拓撲特征相結(jié)合，提出了一種基于增強的中軸骨架三維模型檢索算法。通過對本文方法的檢索性能、檢索時間進行測試，結(jié)果表明，該算法可以得到較好的檢索性能。參考文獻1 TANGELDER J W H，VEHKAMP R C.Polyhedral model?retrieval using weighted point sets.Journal of Ima

12、ge 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

13、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 multi

14、media 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 transformA.ISMM2005C.Paris，F(xiàn)rance，2005：259268.7 VRANIC D，AAUPE D.3D shape descriptor based on 3D?fourier transformA.EURASIP conference on digital signal?processing for multimedia communications a