[發明專利]一種基于渲染的快速體數據骨架提取方法

有效

• 申請號: 201410363994.3
• 申請日: 2014-07-28
• 公開（公告）號: CN104156997B
• 公開（公告）日: 2017-02-01
• 發明（設計）人: 王莉莉;戚慶林;侯飛;李帥;郝愛民
• 申請（專利權）人: 北京航空航天大學
• 主分類號: G06T15/00
• 分類號: G06T15/00;G06T7/00
• 代理公司: 北京科迪生專利代理有限責任公司11251
• 代理人: 楊學明,顧煒

技術領域

本發明屬于骨架提取及體繪制技術領域，具體涉及基于渲染的快速體數據骨架提取方法。

背景技術

骨架作為形狀表示的一種有效形式在三維模型的各個研究領域中被廣泛采用。Blum1967年給出了骨架的最初定義：骨架(中軸)是模型內部各個最大內切球中心的集合。它還有一個grassfire的模擬定義，從模型表面開始點火，各個方向上的火的相遇點所構成的集合。因為模型的骨架很好的保留了模型的拓撲連接性及其幾何形狀信息，所以經常被用于碰撞檢測、三維動畫、模型渲染、模型表面重建、模型檢索、三維形狀識別與檢索、模型編輯、簡化以及三維分割等應用中，也有研究人員采用骨架為模型的分解做矯正。不同的應用，對于骨架應該保存的信息要求不完全相同，故而抽取思路也不完全相同。

對三維模型骨架的研究由來已久，出現過很多方法，有的是源于對二維圖像的擴展，有的是針對三維模型提出的，大體上來說，面向三維網格模型或者三維體素模型的骨架提取方法主要包括：細化、距離變換、分解等。

提取三維體素模型骨架的拓撲細化方法的基本思想是：由外向內，層層剝離不改變模型拓撲特性的體素來實現骨架抽取，它檢測物體數據的拓撲相關性，而不是形狀的幾何特征。這種方法在保持物體拓撲性質的同時，在離散域中反復的逐層剝離去物體的表面，其中判斷一個體素是否需要剝離的檢測過程比較耗時，這種發方法需要完全分割好的、緊湊的并且相互連接的物體模型。Bertrand提出一種簡單的并行細化方法抽取骨架。Ju采用邊細化邊去除冗余體素的方法抽取骨架。Melada提出結合歐式距離測度與細化過程的骨架抽取方法。但這些方法產生的骨架包含雜枝，甚至破壞了骨架的連續性。

基于距離變換的骨架提取方法：它一般的計算對象要求也必須是體素表示的模型，通過計算每個體素的距離來求取模型的脊點。Zhou提出了邊界距離變換和種子點距離變換，采用體素編碼的方式抽取并優化骨架結構，但骨架在分支處的中心性較差。Wan的方法采用精確的邊界距離變換，建立極小擴張樹提取骨架，從而使得到的骨架點盡量不偏離中心，但會出現中心線的“擾動”現象?；贚evel?Set的骨架提取方法穩定性較好，也具有較高的拓撲無關性，能夠有效消除尖點、骨架斷裂等問題，但是即便采用了Fast?Marching?Method策略，其計算復雜度依然很高。Fan引入snake模型調整骨架點的位置，改善了骨架點的中心性，但復雜度也同時增大。

相對于基于細化和距離變換兩種方法而言，基于形狀分解或者分割的三維骨架提取方法將骨架提取和形狀分割結合起來，骨架提取與形狀分解二者相輔相成具有顯著優勢。基于拓撲連接信息，先行對三維模型進行分解；基于分解結果可以降低骨架提取的復雜度、提高骨架的精確度。按照拓撲結構，正確分解三維模型能夠保證快速準確地獲取骨架，反之，骨架作為拓撲結構的參考能夠保證模型分解的準確性。基于分解的方法源于對形體的認識，Hoffman和Richards把形體自然分解成基本部件，把分解用于分類。Rom等提出利用中軸逐步分解二維形體的方法，先分解形體，在提取分解區域的中軸，而中軸是二維形體的自然表示，但是這些方法難以提取中心良好的三維立體形體的分級骨架。Minimal?Rule?Lien等提出基于模型近似圖面體分解，通過計算三維模型頂點的凹凸性展開分解，并通過迭代生成骨架，但得到的骨架中心性較差，也難以建立層次關系。

基于Reeb圖思想。該類算法首先在模型上定義一個連續函數，計算每個模型頂點的函數值，將具有相同函數值的頂點聚合成一個頂點，得到模型的骨架。Hilaga等人提出了基于Reeb圖思想的多分辨率Reeb圖(MRG)，將Reeb圖用于骨架提取，并將映射函數定義為頂點到整個模型表面所有頂點的最短距離與面積之乘積的和。Julien?Tierny等人使用了更加合理的標量函數計算方法。

亦有學者將二維圖像領域中的Voronoi圖技術引入到三維骨架抽取中，Dey等人提出過一種利用Voronoi圖直接近似中軸的算法。因為對三維模型而言只有部分Voronoi頂點能夠匯聚成骨架，所以他通過定義角度和比例這兩個與大小、比重都無關的篩選標準來實現它的中軸近似算法，并證明該方法能夠保證收斂。Voronoi圖方法對于復雜的三維模型，理論上可以實現，但計算量龐大。Voronoi圖方法多用于生成多尺度骨架，但對于邊界噪聲非常敏感，導致Voronoi圖過于稠密，需要額外進行剪枝處理，而且規則復雜，導致該方法實用性不光。