基于旋轉對稱軸的從不完全點云提取骨架的算法研究

段紅娟 （湛江師范學院基礎教育學院，廣東 湛江524037）

一個圖形的骨架，特別是像人或者其他帶關節的動物的形狀，給人直覺的和深刻的抽象，能夠方便的理解和控制形狀。最出名的骨骼表示為Blum中心對稱軸［1］，與它相關的變量一起作為通用表示，用來獲取形狀內部的反射對稱。三維模型的中心對稱軸一般是包含二維表單的非流形，難以存儲和熟練操控。另一方面來說，由于其拓撲結構簡單，使得計算效率高并且容易操控，一維曲線骨架在實踐中更有用。

現存的大多數曲線骨架提取算法主要處理用閉合多邊形表示的形狀。雖然從點云數據中估算曲線骨架是可行的，如通過從輸入云 “內部”產生的可變形團，或者依賴于點集的Voronoi圖表。但是迄今沒有一種方法用來處理丟失了大量重要數據的點云。不完整數據大多由激光掃描造成，源于物體的自遮擋或者表面材質不夠理想條件，這類問題在實時捕獲運動對象的時候更加普遍。由于相機取景非常有限，未經加工的點云包含了大量空洞和嚴重欠采樣。為此，筆者提出了基于旋轉對稱軸的從不完全點云中提取曲線骨架的算法。

1 三維模型曲線骨架及提取技術

1．1 三維模型曲線骨架

骨架作為形狀表示的一種有效形式，在幾何分析及相關處理中，有著非常廣泛的應用。骨架能夠代表模型的拓撲結構和關鍵形體特征，是模型的拓撲抽象表示。Blum 1967年給出了骨架的最初定義：骨架 （中軸）是模型內部各個最大內切球中心的集合。它還有一個模擬定義，即從模型表面開始點火，各個方向上的火的相遇點所構成的集合。

在CAD中提取模型的曲線骨架，可以利用已存在的模型，進行再加工編輯和處理，產生新的模型；在計算機動畫制作產業中，提取骨架曲線可使動畫角色在骨架的的控制下完成多種復雜的運動；在海量三維模型庫中搜索時，利用對三維模型的骨架提取，提供低維特征，可快速查找到自己感興趣的模型。

此外，曲線骨架還可以用于形狀分析、表面重建、動作規劃等其他方面，其原理類似三維搜索中給模型生成低維特征。

1．2 現有的骨架提取技術

近年來，針對從三維模型中提取曲線骨架的方法層出不窮。總體來說，這些方法根據處理輸入模型的不同，可以分為2大類型：

1）處理三維網格或體模型 如基于拓撲細化技術［2］、基于距離矩陣和基于Reeb圖思想，其中著名的有Hilaga等提出的MRG［3］以及基于模型分解［4］等方法。

2）處理點云數據 由于點云數據沒有顯式的拓撲連接關系，以及部分數據可能缺失，導致該問題更有挑戰性。目前基于點云的提取曲線骨架的方法假設數據有不同的特性，因而并不能處理通用模型。

2 從不完全點云提取三維柱狀模型曲線骨架

筆者研究的骨架提取算法基于旋轉對稱軸ROSA［5］，該算法要求被處理圖像大體結構上是圓柱形的，如圖1（a）所示。利用平滑切割的迭代算法來計算點云的旋轉對稱軸，然后對非圓柱形連接區域進行特殊處理，這樣可以獲得有中心的、拓撲簡潔并且完整的一維骨架 （見圖1）。這種方法主要用來從大體上是圓柱形的形狀中提取骨架，甚至可以從丟失了大量重要數據的形狀中提取到骨架。

圖1 基于旋轉對稱軸ROSA的骨架提取算法

2．1 切割平面

柱狀模型的旋轉對稱軸上每一點相當于一條狹窄的近似平滑的 “帶”狀形，如圖1（b）所示。這促使把平滑切割應用在輸入點云中，用來局部化搜索形狀骨架上的旋轉對稱軸點。顯然，并不是所有的切割平面都隱含適合的旋轉對稱性。搜索最佳的切割平面，同時錨定在輸入點云中的每一個樣點的搜索。錨定搜索有3個好處：在旋轉對稱軸創建時，錨點能產生對切割平面附近的相關樣本集的搜索；錨定切割平面也就意味著點云和計算骨架的自然對應；錨定搜索可以促使快速搜索最佳切割平面。

2．2 旋轉對稱軸的創建

取代同時優化旋轉對稱軸點的方向和位置，為了實現更高維次的搜索，筆者采取分離這2個組成部分的方法：先優化方向然后定位，這樣每個問題均成為線性問題，可以閉合形式解決。特別是通過點云中的每個樣點，可以找到最佳切割平面，其常規點能最小化與切割平面相近的有關點集的角度差異；通過不斷迭代找到最佳方向。一旦找到最佳切割平面，基于相關有向點集可計算出旋轉對稱軸點的最佳位置。

2．3 旋轉對稱軸與中軸的關聯

圖2（d）顯示，在二維空間中建立旋轉對稱軸，與中軸［6］有密切聯系。事實上，如果迭代趨同，簡單幾何變量顯示最佳旋轉對稱軸點就在形狀邊緣的雙切圓的中心位置。如果雙切圓在形狀的內部，那么這點即位于中軸上。考慮到不限制雙切圓在形狀內部，旋轉對稱軸點一般屬于邊界曲線的對稱點集，邊界曲線也就是雙切圓的的中心點的軌跡。如果把點的方向也加入考慮，旋轉對稱軸點集比完全對稱點集的條件更受限制。迭代旋轉對稱軸的創建和與中軸關聯的二維圖示如圖2所示。

2．4 關節處理及曲線骨架提取

模型的關節處一般不是圓柱形，因而沒有簡單的旋轉對稱軸。筆者利用點云和骨架之間的空間相干性來保證骨架結構上的點能提供分支旋轉對稱軸的平滑連接。由于這一步不強制關節處的結構是一維的或者剛剛好在中心位置，可以利用細化和中心定位法進行后加工。細化程序利用一維最小二乘移動法來創建，這就允許對關節和分支進行有區別的處理，見圖1（d）。結果骨架曲線上的點根據分枝的旋轉對稱軸來確定中心，并且要和關節點的唯一中心一致，這樣才能和附近的分支連接起來。作為結果的結構，要十分接近一維，并能容易地轉化成曲線段集合，如圖1（f）所示。

圖2 迭代旋轉對稱軸的創建和與中軸關聯的二維圖示

3 結 語

針對帶關節的大體為圓柱體的形狀，在現實掃描或者實時捕獲時，會得到包含大量空洞或者嚴重走樣的不完全點云數據。為理解形狀和方便控制圖形，需要有一種健壯的方法從不完全點云中提取曲線骨架。基于這種想法，筆者提出了基于旋轉對稱軸從不完全點云中提取曲線骨架的算法。該算法計算出的曲線骨架是完整的，除了隱含的不完整數據源，它保證是和輸入點云有關聯的一維結構。

針對現有方法不能處理通用模型的現況，未來研究方向可以增加人機交互功能［7］，用戶只需要在屏幕上粗略勾畫，程序會計算對應的曲線骨架結點位置，并判斷這些骨架節點之間的連接關系。后續工作需要解決的關鍵技術主要包括以下幾點：①骨架提取算法的研究。針對不同表示形式的三維模型，選擇最佳的曲線骨架提取算法。②骨架結點位置的定位。用戶勾畫，選取最佳算法，得到正確的骨架結點。③確立骨架結點間的連接關系，并能任意增刪骨架結點或者骨骼。

［1］Blum H．A transformation for extracting new descriptors of shape Models for the perception of speech and visual form ［M］ ．MIT Press，1967：362-380．

［2］Tierny J，Vandeborre J P，Danudi M．3Dmesh skeleton extraction using topological and geometrical analyses［A］．In：Proceedings of Pacific Conference［C］．Taipei，2006：85-94．

［3］Hilaga M，Shinagawa Y，Kohmura T，et al．Topology matching for fully automatic similarity estimation of 3Dshapes［A］．In Proc．of SIGGRAPH ［C］．2001：203-212．

［4］Lien J M，Keyser J，Amato N M．Simultaneous shape decomposition and skeletonization ［A］．Proceedings of the 2006ACM symposium on Solid and physical modeling ［C］．2006：219-228．

［5］Tagliasacchi A，Hao Zhang，Cohen-Or D．Curve skeleton extraction from incomplete point cloud ［J］．ACM Transactions on Graph，2009，28 （3）：71．

［6］Bouix S，Siddiqi K，Tannenbaum A，et al．Medial axis computation and evolution ［M］．Statistics and Analysis of Shapes，2006．

［7］孫正興，馮桂煥，周若鴻 ．基于草圖的人機交互技術研究進展 ［J］．計算機輔助設計與圖形學學報，2005，17（9）：1889-1899．