一種改進(jìn)的基于特征點(diǎn)求解的骨架提取算法

宮法明，陳依心，李廣麗

0 引言

隨著計(jì)算機(jī)圖形學(xué)的迅速發(fā)展，對(duì)三維模型的研究日益深入。骨架作為形狀表示的一種有效形式，在三維模型的各個(gè)研究領(lǐng)域中被廣泛采用。Blum 1967年給出了骨架的最初定義[1]：骨架(中軸)是模型內(nèi)部各個(gè)最大內(nèi)切球中心的集合。它還有一個(gè)grassfire的模擬定義[2]，從模型表面開始點(diǎn)火，各個(gè)方向上的火的相遇點(diǎn)所構(gòu)成的集合。因?yàn)槟Ｐ偷墓羌芎芎玫谋Ａ袅四Ｐ偷耐負(fù)溥B接性及其形態(tài)，所以經(jīng)常被用于碰撞檢測(cè)、三維動(dòng)畫、模型渲染、模型表面重建、模型檢索等應(yīng)用中，也有研究人員采用骨架為模型的分解做校正[3]。

模型骨架的提取方法很多，有些是源于對(duì)二維圖像的擴(kuò)展，有些是針對(duì)三維模型提出的，大體上來說，有如下幾類：(1)基于拓?fù)浼?xì)化技術(shù)[4]。該類算法主要應(yīng)用于采用體表示的模型上，通過不斷地進(jìn)行不改變模型拓?fù)涮匦缘捏w元素的削減來實(shí)現(xiàn)骨架抽取，因?yàn)槟Ｐ偷捏w表示數(shù)據(jù)量巨大，所以整個(gè)過程比較耗時(shí)。Gong等人提出過一種并行細(xì)化算法，通過先定義模型的簡(jiǎn)單頂點(diǎn)、刪除謂詞和兩個(gè)細(xì)化元操作，在抽取算法中不斷迭代兩個(gè)元操作進(jìn)行模型細(xì)化；(2)基于距離矩陣[5]。它一般的計(jì)算對(duì)象要求也必須是體表示的模型，通過計(jì)算每個(gè)體元素的距離來求取模型的脊點(diǎn)。Sundar等人提出過基于該思想的一個(gè)算法思路，通過計(jì)算每個(gè)體元素到邊界的最小距離來得到骨架點(diǎn)，Sundar采用該算法創(chuàng)建了一個(gè)模型檢索系統(tǒng)；(3)亦有學(xué)者將二維圖像領(lǐng)域中的Voronoi圖技術(shù)引入到三維骨架抽取中，Dey等人提出過一種利用Voronoi圖直接近似中軸的算法[6]。因?yàn)閷?duì)三維模型而言只有部分Voronoi頂點(diǎn)能夠匯聚成骨架，所以他通過定義角度和比例這兩個(gè)與大小、比重都無關(guān)的篩選標(biāo)準(zhǔn)來實(shí)現(xiàn)它的中軸近似算法，并證明該方法能夠保證收斂；(4)基于Reeb圖思想[7]。該類算法首先在模型上定義一個(gè)連續(xù)函數(shù)，計(jì)算每個(gè)模型頂點(diǎn)的函數(shù)值，將具有相同函數(shù)值的頂點(diǎn)聚合成一個(gè)頂點(diǎn)，得到模型的骨架，其中著名的有 Hilaga等人提出的MRG，Hilaga定義的連續(xù)函數(shù)為頂點(diǎn)到整個(gè)模型表面所有頂點(diǎn)的最短距離與面積之積的和。Julien Tierny等人使用了更加合理的標(biāo)量函數(shù)計(jì)算方法。(5)基于模型分解[8]。Lien等人觀察到對(duì)于保存模型連接性的分解過程就是一個(gè)骨架抽取的過程，所以提出了基于模型近似凸面體分解的骨架抽取算法，通過計(jì)算模型表面的橋識(shí)別模型表面的凹地，計(jì)算每個(gè)頂點(diǎn)的凹陷性，并對(duì)模型按照凹陷性進(jìn)行分解，不斷迭代該過程創(chuàng)建骨架。(6)其它類。Ma等人提出過基于可見互斥力的骨架抽取算法[9]，它應(yīng)用了物理學(xué)上的互斥力的概念來計(jì)算模型上的平衡點(diǎn)，最終得到模型的骨架。

1 特征點(diǎn)的提取

特征點(diǎn)是指三維模型中顯著部分處于極端位置的頂點(diǎn)，它反映了模型的整體空間結(jié)構(gòu)及分支情況，對(duì)3D模型的骨架提取有重要作用，每個(gè)特征點(diǎn)對(duì)應(yīng)于一個(gè)分支，提取特征點(diǎn)即得到模型的分支，將分支的另一端點(diǎn)——骨架點(diǎn)與特征點(diǎn)連接，得到分支部分的骨架，最后，依據(jù)骨架點(diǎn)攜帶的拓?fù)湫畔ⅲ瑢⒕哂型負(fù)湎嚓P(guān)性的骨架點(diǎn)連接起來，得到3D模型拓?fù)涔羌堋?/p>

1.1 計(jì)算vs1和vs2。

vs1和vs2是三角網(wǎng)格模型中測(cè)地線距離最遠(yuǎn)的兩個(gè)頂點(diǎn)的索引。首先使用最短距離Floyd算法計(jì)算三角網(wǎng)格中所有頂點(diǎn)間的測(cè)地線距離，然后找到測(cè)地線距離最大的兩個(gè)頂點(diǎn)索引即為vs1和vs2。

1.2 對(duì)每個(gè)頂點(diǎn)計(jì)算fg1和fg2。

基于測(cè)地線距離換算的函數(shù)fg1和fg2定義如下：

fg1(v)=δ(v,vs1) ?v∈T，vs1∈T，fg1(v)表示T上任意一個(gè)頂點(diǎn)v到vs1的測(cè)地線距離。

fg2(v)=δ(v,vs2) ?v∈T，vs2∈T，fg2(v)表示T上任意一個(gè)頂點(diǎn)v到vs2的測(cè)地線距離。

T為模型的三角網(wǎng)格。

1.3 計(jì)算fg1和fg2的局部最值集合E1和E1。

局部最值定義如下（圖1）：

圖1 局部最值

1)局部最大值：v為局部最大值，當(dāng)且僅當(dāng)所有與v相鄰的結(jié)點(diǎn)的f值都小于f(v)。

2)局部最小值：v為局部最小值，當(dāng)且僅當(dāng)所有與v相鄰的結(jié)點(diǎn)的f值都大于f(v)。

3)其它：與v相鄰的結(jié)點(diǎn)的f值既有大于f(v)的又有小于f(v)的。

根據(jù)局部最值的概念，定義E1為fg1局部最值的集合；E2為fg2局部最值的集合。計(jì)算fg1(v)局部最值E1步驟如下：

Step1：判斷三角網(wǎng)格T所有頂點(diǎn)是否都處理，是則結(jié)束，否則取一個(gè)沒有處理的頂點(diǎn)v，轉(zhuǎn)到Step2。

Step2：找到v的所有鄰居點(diǎn)，比較它們對(duì)應(yīng)的fg1值，如果fg1(v)都大于或都小于v的所有鄰接點(diǎn)vi的fg1(vi)的值，則將頂點(diǎn)v加入到E1的集合，否則，轉(zhuǎn)到Step1。

兩步迭代就可以得到集合E1，E2計(jì)算方法相同。

1.4 計(jì)算特征點(diǎn)的集合F。

特征點(diǎn)集合即E1與E2的交集F=E1∩E2。由于兩個(gè)映射函數(shù)的特征點(diǎn)對(duì)于同一個(gè)顯著部分并不是準(zhǔn)確地定位在同一個(gè)點(diǎn)上，應(yīng)用以下規(guī)則進(jìn)行交集的模糊運(yùn)算：

2 骨架的提取

骨架提取包括兩個(gè)步驟，①骨架點(diǎn)的提取；②骨架點(diǎn)和骨架點(diǎn)、骨架點(diǎn)與特征點(diǎn)之間的連接。

在滿足拓?fù)洳蛔兒蛶缀渭s束條件下，通過重復(fù)剝離3D模型邊界點(diǎn)直至得到一個(gè)連通點(diǎn)集，該連通點(diǎn)集中的點(diǎn)即為骨架點(diǎn)。本文采用了一種基于拓?fù)浞椒ㄌ崛」羌茳c(diǎn)的方法，首先提取模型的分支點(diǎn)，將分支點(diǎn)聚合得到骨架點(diǎn)。算法步驟如下：

Step1：取T的一個(gè)頂點(diǎn)v，設(shè)置v的堆棧stack，v進(jìn)棧。如果所有頂點(diǎn)都已處理，則結(jié)束，否則轉(zhuǎn)Step2。

Step2：如果stack不為空，轉(zhuǎn)Step3。否則，轉(zhuǎn)Step1。

Step3：把棧最底端的頂點(diǎn)Vsi出棧，同時(shí)對(duì)頂點(diǎn)Vsi的所有鄰接點(diǎn)Vi進(jìn)行特征點(diǎn)的比較，如果Vsi與所有的鄰接點(diǎn)Vi的特征點(diǎn)相同，則Vsi不是分支點(diǎn)，轉(zhuǎn)Step1繼續(xù)處理，如果不同，轉(zhuǎn)Step4。

Step4：把Vsi添加到v的分支點(diǎn)的數(shù)組，然后，對(duì)v的所有鄰接點(diǎn)進(jìn)行遍歷，查找所有與Vsi的特征點(diǎn)的索引相同的鄰接點(diǎn)，加入到stack中，轉(zhuǎn)Step2。

將骨架點(diǎn)和特征點(diǎn)進(jìn)行連接得到分支的骨架；根據(jù)骨架點(diǎn)之間的拓?fù)潢P(guān)系連接各骨架點(diǎn)得到拓?fù)涔羌堋?/p>

3 算法分析與改進(jìn)

特征點(diǎn)提取是整個(gè)骨架提取算法的基礎(chǔ)。對(duì)于一個(gè)有n個(gè)頂點(diǎn)三角網(wǎng)格T，F(xiàn)loyd算法時(shí)間復(fù)雜度為O(n3)，成為影響特征點(diǎn)提取算法效率的瓶頸。本文提出了基于距離模型中心最近（遠(yuǎn)）點(diǎn)提取 VS的策略，得到了時(shí)間復(fù)雜度為O(n×log(n))改進(jìn)算法。其基本思想為：計(jì)算三角網(wǎng)格的中心點(diǎn)Vo，找到距離該頂點(diǎn)最近（最遠(yuǎn)）的頂點(diǎn)V′，使用oDijkstra算法計(jì)算V′到T上任一點(diǎn)測(cè)地線距離，取測(cè)地線距o離最大的頂點(diǎn)Vtemp，用相同的方法迭代計(jì)算Vtemp，直到兩次得到的測(cè)地線距離相差不大，即可確定VS。

4 結(jié)論

本文基于特征點(diǎn)求解和Reeb圖思想實(shí)現(xiàn)了一種新的骨架提取算法。首先求取模型特征點(diǎn)集，以特征點(diǎn)為計(jì)算依據(jù)，根據(jù)三角網(wǎng)格中每個(gè)頂點(diǎn)與特征點(diǎn)的不同對(duì)應(yīng)關(guān)系得到網(wǎng)格分支點(diǎn)，聚合成一系列骨架點(diǎn)，依據(jù)骨架點(diǎn)攜帶的拓?fù)湫畔?，連接拓?fù)湎噜彽墓羌茳c(diǎn)得到模型骨架。采用了改進(jìn)的特征點(diǎn)提取算法，其時(shí)間復(fù)雜度由O（n3）提高到了O（n2log（n）），使用Moore-Dijkstra算法計(jì)算映射函數(shù)fg1和fg2，時(shí)間復(fù)雜度為O（nlog（n）），采用棧結(jié)構(gòu)實(shí)現(xiàn)骨架點(diǎn)的搜索，實(shí)驗(yàn)表明算法能夠快速提取骨架，針對(duì)一般模型的骨架提取效果令人滿意。對(duì)于極少數(shù)特殊模型，提取特征點(diǎn)存在不足或者過多的問題。

圖2 實(shí)驗(yàn)效果圖

[1]Attene M, Biasotti S , and Spagnuolo M . Shape understanding by contour-driven retiling. The Visual Computer,19:127–138, 2003.

[2]Biasotti S, Marini S, Mortara M, and Patan`e G. An overview on properties and efficacy of topological skeletons in shape modelling. In Shape Modeling International, pages 245–254, 2003.

[3]Blum H and Nagel R N. Shape description using weighted symmetric axis features. Pattern Recognition, 10:167–180,1978.

[4]Bremer P T, Edelsbrunner H, Hamann B, and Pascucci V.Topological hierarchy for functions on triangulated surfaces.IEEE Transactions on Visualization and Computer Graphics, 10:385–396, 2004.

[5]Carr H, Snoeyink J, and M V. de Panne. Simplifying flexible isosurfaces using local geometric measures. In IEEE Visualization, pages 497–504, 2004.

[6]Cole K -McLaughlin, Edelsbrunner H, Harer J, Natarajan V,and Pascucci V. Loops in Reeb graphs of 2-manifolds.In Symposium on Computational Geometry,pages 344–350,2003.

[7]Edelsbrunner H and M¨ucke E P.Simulation of simplicity:a technique to cope with degenerate cases in geometric algorithms.ACM Transactions on Graphics, 9:66–104,1990.

[8]H′etroy F. Constriction computation using surface curvature.In Eurographics, pages 1–4, 2005.

[9]H′etroy F and Attali D. From a closed piecewise geodesic to a constriction on a closed triangulated surface.In Pacific Graphics, pages 394–398, 2003.