歡迎登錄中國視覺網!
學術論文頻道
ACADEMIC PAPERS
位置導航:首頁 >> 學術論文 >> 技術前沿 >> 三維網格模型的線狀骨架化算法

三維網格模型的線狀骨架化算法

發布時間:2018-07-24     來源:中國視覺網       訪問次數:6667


摘要:研究了一種高效、魯棒的三維網格模型的線狀骨架化算法,包括基于距離變換的網格模型的拓撲結構標記提取、基于路徑規劃算法的初始骨架線構造、基于Snake模型的骨架中心化算法,以及一種全局噪聲消除方法等內容;實驗表明該方法對于不規則的復雜線狀物體骨架提取,具有較好的效果。
關鍵詞:線狀骨架化算法;距離變換;路徑規劃算法;Snake模型


   1  引  言
    基于三維激光掃描建模方法的數字幾何處理技術,被稱為第四代數字媒體技術 [1]已成為圖形學領域的一個新興分支和研究熱點。
    三維網格模型的骨架在數字幾何處理研究的以下方面有著重要作用:①三維網格模型的拓撲結構分析[2,3] ; ②基于拓撲信息的網格分割[3,4,5];③三維網格模型檢索[5];④網格模型動畫與幾何變形[6,7];⑤網格模型的碰撞檢測[8];⑥網格模型運動合成[9]等。
    三維網格模型的線狀骨架定義為位于模型內部的、連通的、且與模型拓撲結構一致的中心線。具有以下特性:拓撲結構同倫性、骨架表示相對簡單、易于模式匹配與幾何變形等。
    目前三維網格模型通常討論的骨架是由面和線構成的中軸面[10-12]。盡管中軸面骨架有許多良好的性質如可重建性等,但在上述數字幾何處理領域,線狀骨架的應用更為明顯,尤其對于具有分支拓撲結構的管狀三維網格模型,如人體模型、植物模型、醫學上的血管模型等。而目前線狀骨架的研究較為罕見。
   2  網格模型的分支端點提取
    線狀骨架主要應用于具有分支拓撲結構的三維網格模型,對于這類網格模型,其分支端點(End Point)是模型拓撲結構的重要標記。因此,要獲得拓撲結構同倫的線狀骨架,首先要準確提取分支端點。這里借鑒三維圖象骨架化中基于某個參考點的距離變換方法[13]  ,即先計算網格模型上的每個頂點到參考點(Seed Point)的距離,然后選取距離極大值的頂點作為分支端點。與文獻[13]不同的是,計算三維圖象中體素點之間距離時,通常得到的是近似的歐式距離,在網格模型中可精確計算兩點歐式距離,因而,結果更為準確。
    具體計算步驟如下:
  (1)在網格模型上,選取一個參考點 Ps;
  (2)將參考點的距離值定義為零,將其它頂點的距離值初始化預先定義的極大值,即:
                   (1)
  (3)從參考點的鄰接頂點開始,采取廣度優先算法,依次計算網格上每個頂點的距離值,計算方法:
    對于頂點Pi,假定Pj是其所有鄰接頂點中距離值最小的頂點,則
    (2)
  (4)重復步驟(3),直到所有頂點的距離值不再改變或改變量小于給定的閾值為止;
  (5)根據上一步得到的網格頂點的距離值,選取所有距離值為局部極大的頂點作為求得分支端點Pe(e=1,2, …, N)。
    參考點Ps的選擇,對于分支端點提取有重要影響。這里采用人機交互方式選取某一明顯分支頂點作為Ps。
   3 初始骨架線構造
    獲取Ps與Pe點后,在模型表面將Ps與Pe連接起來,就可得到初始骨架線。
    具體步驟:
    (1)將求得的Pe(e=1,2, …, N)按距離值從大到小排序,得到Pe,(e=1,2, …, N);
    (2)令e=1,借鑒路徑規劃方法,在模型表面將Pe,與Ps連接起來,即:在模型表面尋找一條從Pe,到Ps的最短路徑,就可得到一條初始骨架線。具體實現方法是采用基于距離值的最陡下降法;
    (3)e=e+1, 重復(2)中操作,直到e>N;
    (4)在步驟(2)中,除第一條初始骨架線外,其它骨架線都可能與已求得的初始骨架線相交和重疊。因此,要對相交和重疊部分的初始骨架線進行處理。

   4 初始骨架線中心化

    將上一步得到的每條初始骨架線作為初始Snake: ,在內力(包括拉伸力和彎曲力)和特征力的作用下,使其逐步收斂于網格模型的中心位置。
    算法暫不考慮內力的作用,因此,特征力的計算是問題的關鍵,特征力通常由模型內部能量決定。
    網格模型內部能量的計算無法直接采用圖像處理中方法,為此這里采用一種彈簧模型。對于Snake上的點 ,假定與一定鄰域內網格頂點 之間均用同樣彈性系數的彈簧連接,則 的特征力表示為:

    求得 后, 即可按如下公式不斷向網格模型中心移動  ,直至Snake穩定為止。
    系數及鄰域內網格頂點 的選取,是根據實驗結果不斷進行調整與優化。
    完成所有初始骨架線中心化后,仍可能出現骨架線相交和重疊問題,同樣要進行相應處理等。
    5  抗噪聲處理
    在上述三個步驟中均要考慮噪聲消除:
    a. 拓撲結構標記提取過程中,為防止錯誤地將噪聲作為分支端點提取,除考慮頂點的距離值外,還可增加的曲率、頂點附近距離值變化等參數。
    b. 初始骨架線構造方面,在從EP點向RP點回縮過程中,可根據給定閾值參數,刪除短的噪聲分支。
    c. 中心化過程中,如果只考慮較少網格頂點對骨架點的外力作用,則可能由于模型局部畸變導致局部某個方向外力較大,從而使骨架也發生畸變。為此,通過增加每個骨架點受到外力作用的網格頂點數量,可平滑局部畸變導致的某個方向外力過大現象,從而減少噪聲帶來的骨架畸變。

 


   6   實驗結果及結論
    采用文中提出的方法對人工合成和實際三維掃描重建的網格模型骨架提取結果如圖1-3所示。圖中分別給出了原始網格模型、距離變換結果及所求的骨架。其中,距離變換圖示中顔色越深表示距離值越小。由圖示可以看出,文中提出的骨架化方法得到了較好的實驗結果。
進一步的工作有以下幾個方面:(1)分支結構中的分叉點在算法中沒有考慮,因此,在分叉點處骨架有一定的變形。因此,算法改進過程中除提取分支端點外,還要將分叉點提取出來。(2)尋求一種自動確定參考點的方法。

參 考 文 獻
[1] Schroder P, Sweldens W. Digital geometry processing[A]. In: Computer Graphics Processings, Annual, Conference Series, ACM SIGGRAPH[C], Los Angeles, California, 2001. Couse Notes #50
[2] Li X, Woon T W, Tan T S, et al. Decomposing polygon meshes for interactive application[A]. In: Proceedings of the ACM Symposium on Interacive 3D Graphics[C], Research Triangle Park, North Carolina, 2001. 35~42
[3] Leymarie F, Kimia B. The shock scaffold for representing 3D shape[A]. In: Proceedings of the 4th International Workshop on Visual Form[C], Capri, 2001. 216~228
[4] Rossl C, Koobbelt L, Seidel H P. Extraction of feature lines on triangulated surface using morphological operators[A]. In: Proceedings of the AAAI Symposium on Smart Graphics[C], Stanford, California, 2000. 71~75
[5] Page D L, Koschan A F, Abidi M A. Perception-based 3D trangle mesh segmentation using fast marching Watersheds[A]. In: Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition[C], Madison, 2003.27~32
[6] Chaudhuri P, Kalra P, Banerjee S. A system for view-dependent animation[J]. Eurographics, 2004,23(3):411~420
[7] Blanding R L, Tuikiyyah G M, Storti D W, et al. Skeleton-based three-dimentional geometric morphing[J]. Computational Geometry, 2000, 15:129~148

[8] Kavan L, Zara J. Fast collision detection for skeletally deformable models[J]. Eurographics, 2005,24(3):364~372
[9] Urtasun R, Glardon P, Roulic R, et al. Style-based motion synthesis[J]. Computer Graphics Forum, 2004, 23(4):799~812
[10]Etzion M, Rappoport A. Computing Voronoi skeletons of a 3d-polyhedron by space subdivision[J]. Computational Geometry, 2002, 21:87~120
[11]Ramanathan M, Gurumoorthy B. Constructing medial axis transform of extruded and resolved 3D objects with free form boundaries[J]. Computer-Aided Design, 2005, 37:1370~1387
[12]Attali A, Lachand H O. Delaunay conforming iso-surface, skeleton extraction amd noise removal[J]. Computational Geometry, 2001, 19 175~189
[13]Maddah M. Soltanian-Zadeh H. and Afzali-Kusha A. Snake modeling and distance transform approach to vascular centerline extraction and quantification[J]. Computerized Medical Imaging and Graphics, 2003, 27:503~512.