基于旋轉(zhuǎn)對(duì)稱(chēng)軸的從不完全點(diǎn)云提取骨架的算法研究

段紅娟 （湛江師范學(xué)院基礎(chǔ)教育學(xué)院，廣東 湛江524037）

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

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

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

1．1 三維模型曲線(xiàn)骨架

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

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

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

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

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

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

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

2 從不完全點(diǎn)云提取三維柱狀模型曲線(xiàn)骨架

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

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

2．1 切割平面

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

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

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

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

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

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

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

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

3 結(jié) 語(yǔ)

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

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

［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ī)交互技術(shù)研究進(jìn)展 ［J］．計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2005，17（9）：1889-1899．