??? 摘 要： 針對(duì)三維模型" title="三維模型">三維模型檢索算法性能較低的問(wèn)題，提出了一種改進(jìn)的中軸骨架三維模型檢索" title="三維模型檢索">三維模型檢索算法。
??? 關(guān)鍵詞： 三維模型檢索,特征變換,中軸骨架,骨架二叉樹(shù)

?

??? 隨著激光掃描技術(shù)的發(fā)展以及計(jì)算機(jī)性能的提高,，三維模型在很多應(yīng)用領(lǐng)域中扮演著非常重要的角色,，如工業(yè)產(chǎn)品的模型設(shè)計(jì),、虛擬現(xiàn)實(shí)系統(tǒng)、游戲設(shè)計(jì)、逆向工程以及仿真等，但是,，要想構(gòu)造一個(gè)真實(shí)感較強(qiáng)的模型其工作量巨大。目前在因特網(wǎng)和特定領(lǐng)域的數(shù)據(jù)庫(kù)中存在著數(shù)以兆計(jì)的模型,，且還在源源不斷地增加,。如果能夠重復(fù)利用已有模型，就可大大減小模型設(shè)計(jì)的工作量,。因此,，對(duì)三維模型檢索技術(shù)的研究已變得越來(lái)越緊迫和重要。
??? 目前,，三維模型檢索主要采用基于內(nèi)容的檢索方法,。根據(jù)特征提取方法的不同，可將檢索方法大致分為四類：統(tǒng)計(jì)特征,、函數(shù)投影,、拓?fù)浣Y(jié)構(gòu)" title="拓?fù)浣Y(jié)構(gòu)">拓?fù)浣Y(jié)構(gòu)特征和基于幾何結(jié)構(gòu)分析。
??? 基于統(tǒng)計(jì)特征的三維模型描述方法^[1],，不需要通過(guò)模型進(jìn)行標(biāo)準(zhǔn)化處理，因此計(jì)算較為簡(jiǎn)單,，具有良好的不變性,。但是，這些特征描述模型之間相似性的能力普遍不夠強(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利用模型骨架描述三維模型的特征^[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ì)待匹配的三維模型進(jìn)行預(yù)處理；然后改進(jìn)Hesselink提出的整數(shù)中軸算法^[6],，得到模型的中軸骨架,，對(duì)骨架按區(qū)域劃分，構(gòu)造骨架二叉樹(shù)" title="骨架二叉樹(shù)">骨架二叉樹(shù),，同時(shí)根據(jù)區(qū)域的大小定義節(jié)點(diǎn)的特征權(quán)值" title="權(quán)值">權(quán)值,，用于衡量其對(duì)三維模型整體相似性的影響程度；最后,，通過(guò)計(jì)算兩個(gè)骨架二叉樹(shù)的相似度,，獲得兩個(gè)三維模型的相似度，在匹配過(guò)程中,，采用由粗到細(xì)逐步淘汰的策略,，不斷縮減待匹配模型的范圍，從而降低了模型匹配的時(shí)間,。實(shí)驗(yàn)結(jié)果表明,，該算法可以得到較好的檢索性能。
1 模型預(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)的特征值λ₁>λ₂>λ₃，其對(duì)應(yīng)的特征矢量為(I₁,，I₂,，I₃)，以(I₁,，I₂,，I₃)為新的坐標(biāo)系統(tǒng)，對(duì)三維模型進(jìn)行坐標(biāo)變換,，得到變換后的坐標(biāo)值,。處理結(jié)果如圖1所示。

2 骨架提取
??? 設(shè)r是三維模型表面上的點(diǎn),，由Hesselink的整數(shù)中軸算法可得：
??? 若e∈E,，(E={e∈I³||e||=1})，I³為模型內(nèi)部的一個(gè)體素網(wǎng)格點(diǎn),，則當(dāng)m=r+1/2e時(shí)：

??? ||m-f_t(r+e)||=||m-f_t(r)||????????????????? (1)

式中,，m為整數(shù)中軸骨架上的一個(gè)骨架點(diǎn)，f_t(r)為點(diǎn)r的特征變換函數(shù),。
??? 為了記錄以骨架點(diǎn)m為球心的內(nèi)接球的半徑,，對(duì)整數(shù)中軸骨架進(jìn)行改進(jìn)，定義一元函數(shù)：
??? σ_m=||m-f_t(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)化,。

?

??? 如果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è)q∈B,，p=IMAS(q)，點(diǎn)q和p之間的距離定義為dis(q),。定義一個(gè)輔助函數(shù)Average(dis(q)),，其函數(shù)值為dis(q)(q∈IMAS^-1(p))的平均值,。所有的中軸骨架點(diǎn)應(yīng)該滿足：

???

將所有優(yōu)化后的骨架點(diǎn)連接起來(lái)形成加權(quán)骨架H，如圖3所示,。

?

3 模型匹配
3.1 生成骨架二叉樹(shù)
??? 設(shè)δmax(n_i)和δmin(n_i)分別為骨架二叉樹(shù)節(jié)點(diǎn)n_i對(duì)應(yīng)的中軸骨架區(qū)域Z_i的Z軸坐標(biāo)最大值和最小值,。在進(jìn)行更高一級(jí)細(xì)節(jié)層次劃分時(shí)，按下面的公式計(jì)算每個(gè)區(qū)域的Z軸坐標(biāo)最大值和最小值,，骨架區(qū)域劃分示意圖如圖4所示,。

???

??? 將區(qū)域C_i視為二叉樹(shù)節(jié)點(diǎn)a_i，其權(quán)值W_ai為：

???

3.2 匹配骨架二叉樹(shù)
??? 設(shè)a_i和b_i(0≤i≤n)為三維模型P,、Q對(duì)應(yīng)的骨架二叉樹(shù)中的節(jié)點(diǎn),，則它們的相似度函數(shù)為：

???

??? 設(shè)三維模型P、Q的相似度函數(shù)為：

???

??? 但是,，在匹配過(guò)程中,，由于模型的不同部分對(duì)模型整體的相似性的影響不同，因此對(duì)不同的sim(a_i,，b_i)賦予不同的權(quán)值x_i,，對(duì)相似度函數(shù)加以改進(jìn)，加入權(quán)值因子x_i,，改進(jìn)的相似度函數(shù)為：

???

式中,，f(a_i)為對(duì)應(yīng)節(jié)點(diǎn)a_i的區(qū)域大小，f(a_o)為整個(gè)區(qū)域的大小,。

??? 具體的匹配步驟如下：
??? (1)定義域值區(qū)間g=[0,，β]，β∈R,；生成兩個(gè)骨架二叉樹(shù)的根節(jié)點(diǎn)a_o,、b_o，若sim(a_o,，b_o)∈g,，則繼續(xù)以下步驟；否則匹配結(jié)束,，兩個(gè)模型不相似,。
??? (2)若a_i、b_i為非葉子節(jié)點(diǎn),，則生成a_i,、b_i的左孩子節(jié)點(diǎn)a_2i+1和b_2i+1，若sim(a_2i+1,，b_2i+1)∈g,，則繼續(xù)以下步驟；否則匹配結(jié)束，兩個(gè)模型不相似,。
??? (3)若a_i,、b_i為葉子節(jié)點(diǎn)，sim(a_i,，b_i)∈g,，則該分支的匹配結(jié)束，向上回溯到其父親節(jié)點(diǎn),，進(jìn)行另一分支的匹配,；若sim(a_i，b_i)∈g,，則匹配結(jié)束,，兩個(gè)模型不相似。
??? (4)生成a_i和b_i的右孩子節(jié)點(diǎn)a_2i+2和b_2i+2,，若sim(a_2i+2,，b_2i+2)∈g，則繼續(xù)以下步驟,；否則匹配結(jié)束,，兩個(gè)模型不相似。
??? (5)若二叉樹(shù)的任意節(jié)點(diǎn)ai和bi都滿足：sim(a_i,，b_i)∈g,，(0≤i≤n)，則兩模型相似,。
??? (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)度量不同方法的檢索性能，三種方法的檢索性能曲線如圖5所示,。由圖可以看出,，本文方法由于在拓?fù)浣Y(jié)構(gòu)的基礎(chǔ)上融入了統(tǒng)計(jì)特征，因此在檢索性能上有明顯提高,。

?

??? 三維模型檢索技術(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 Image 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 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,，F(xiàn)rance，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.?

?