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

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

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

1 三維模型曲線骨架及提取技術(shù)

1．1 三維模型曲線骨架

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

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

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

1．2 現(xiàn)有的骨架提取技術(shù)

近年來，針對從三維模型中提取曲線骨架的方法層出不窮?？傮w來說，這些方法根據(jù)處理輸入模型的不同，可以分為2大類型：

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

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

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

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

圖1 基于旋轉(zhuǎn)對稱軸ROSA的骨架提取算法

2．1 切割平面

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

2．2 旋轉(zhuǎn)對稱軸的創(chuàng)建

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

2．3 旋轉(zhuǎn)對稱軸與中軸的關(guān)聯(lián)

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

2．4 關(guān)節(jié)處理及曲線骨架提取

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

圖2 迭代旋轉(zhuǎn)對稱軸的創(chuàng)建和與中軸關(guān)聯(lián)的二維圖示

3 結(jié) 語

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

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

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