一種改進(jìn)的中軸骨架三維模型檢索算法

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

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

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

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

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

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

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

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

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

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

11、檢索時(shí)間包括打開文件讀取模型數(shù)據(jù)的時(shí)間)如表1所示，檢索結(jié)果示例如圖6所示。? 三維模型檢索技術(shù)是近年來(lái)隨著三維模型獲取手段的增強(qiáng)、增多以及互聯(lián)網(wǎng)的發(fā)展而興起的計(jì)算機(jī)圖形學(xué)領(lǐng)域內(nèi)的一個(gè)重要課題。針對(duì)三維模型檢索性能較低的問(wèn)題，本文將三維模型的統(tǒng)計(jì)特征和拓?fù)涮卣飨嘟Y(jié)合，提出了一種基于增強(qiáng)的中軸骨架三維模型檢索算法。通過(guò)對(duì)本文方法的檢索性能、檢索時(shí)間進(jìn)行測(cè)試，結(jié)果表明，該算法可以得到較好的檢索性能。參考文獻(xiàn)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.中國(guó)圖像圖形學(xué)報(bào)，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