摘? 要：本文基于ROSA（Rotational Symmetry Axis）和中軸的骨架提取算法，搭建一個(gè)半自動(dòng)的點(diǎn)云模型線性骨架提取實(shí)驗(yàn)平臺(tái)，系統(tǒng)地分析了基于勾畫的交互方式進(jìn)行點(diǎn)云模型骨架提取的實(shí)驗(yàn)平臺(tái)的結(jié)構(gòu)與特點(diǎn)，并闡述了骨架結(jié)點(diǎn)位置提取、骨架連接關(guān)系提取、骨架編輯等各個(gè)功能模塊在實(shí)驗(yàn)平臺(tái)中的具體實(shí)現(xiàn)和功能，最后對(duì)實(shí)驗(yàn)平臺(tái)的開發(fā)工作進(jìn)行了總結(jié)。

關(guān)鍵詞：點(diǎn)云;點(diǎn)云法向量;ROSA;線性骨架提取

中圖分類號(hào)：TP391.41 ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-4706（2019）08-0089-03

Abstract：Based on ROSA（Rotational Symmetry Axis）and mid-axis skeleton extraction algorithm，this paper builds a semi-automatic linear skeleton extraction experimental platform for point cloud model，systematically analyses the structure and characteristics of the experimental platform for point cloud model skeleton extraction based on skeleton-based interactive method，and expounds the skeleton node location extraction，skeleton connection extraction，skeleton editing and other functional modules in the experimental platform. Finally，the development of the experimental platform is summarized.

Keywords：point cloud;point cloud normal vector;ROSA;linear skeleton extraction

0? 引? 言

模型的線性骨架既保持了原始模型的拓?fù)浣Y(jié)構(gòu)，同時(shí)又能夠反映模型的形狀，能夠大幅度減少模型的冗余信息。受點(diǎn)云數(shù)據(jù)獲取技術(shù)的限制，掃描得到的原始點(diǎn)云數(shù)據(jù)中噪聲、外點(diǎn)和孔洞等不可避免，為了讓計(jì)算機(jī)正確理解模型的外觀，從不理想的點(diǎn)云數(shù)據(jù)中準(zhǔn)確提取線性骨架有待進(jìn)一步研究和探討。

1? 研究背景及意義

現(xiàn)存的點(diǎn)云的線性骨架提取算法[1-9]受原始點(diǎn)云數(shù)據(jù)的限制，在自動(dòng)提取線性骨架時(shí)，容易出現(xiàn)理解模型外觀不正確的現(xiàn)象，想要得到正確的點(diǎn)云模型的線性骨架，就需要人工干涉。本文基于ROSA和中軸的骨架提取算法，開發(fā)半自動(dòng)的交互式線性骨架提取實(shí)驗(yàn)平臺(tái)，讓用戶參與并體驗(yàn)骨架提取的過程;同時(shí)，利用本系統(tǒng)人工勾畫輸入，交互式編輯自動(dòng)提取出來的存在誤差的骨架，借助人為干涉修改線性骨架，提高結(jié)果骨架的準(zhǔn)確性。

2? 點(diǎn)云數(shù)據(jù)的預(yù)處理

2.1? 基于KD-樹的k鄰域

本系統(tǒng)先采用KD-樹對(duì)點(diǎn)云在空間上進(jìn)行分割，再查找k鄰域。KD-樹是區(qū)分k維空間中的數(shù)據(jù)點(diǎn)的平衡二叉樹數(shù)據(jù)結(jié)構(gòu)。KD-樹按照一定的規(guī)則，把三維空間分割成多個(gè)空間。利用回溯算法，從樹的底層自底向上擴(kuò)大搜索范圍，使用KD-樹這種平衡二叉樹的數(shù)據(jù)結(jié)構(gòu)，查找最近點(diǎn)的時(shí)間復(fù)雜度約為O（nlogn），大幅度提高了在三維空間中搜索鄰近點(diǎn)的效率。

2.2? 點(diǎn)云法向量

法向量是三維點(diǎn)云數(shù)據(jù)的一個(gè)重要局部特征，其獲取方法主要有：通過光度立體法來獲取，或者通過計(jì)算得到。一般三維掃描獲得的采樣點(diǎn)的信息只是記錄每一個(gè)離散點(diǎn)的空間坐標(biāo)數(shù)據(jù)，并未記錄點(diǎn)間的相互關(guān)系。點(diǎn)的法向量主要通過對(duì)局部點(diǎn)云集合的屬性進(jìn)行分析，采用二次曲面擬合或平面擬合得到采樣點(diǎn)的法向量。

3? 半自動(dòng)線性骨架提取系統(tǒng)

本系統(tǒng)的輸入是三維模型的點(diǎn)云數(shù)據(jù)，用戶借助觸摸屏簡略勾畫，系統(tǒng)根據(jù)切割平面的鄰近關(guān)系計(jì)算出該筆畫在三維空間中對(duì)應(yīng)的點(diǎn)集;然后選擇合適的算法計(jì)算出對(duì)應(yīng)點(diǎn)集的幾何中心，得到新的骨架結(jié)點(diǎn)。選擇骨骼增加功能時(shí)，用戶在屏幕上點(diǎn)擊任意兩個(gè)骨架結(jié)點(diǎn)后，系統(tǒng)自動(dòng)計(jì)算這兩個(gè)結(jié)點(diǎn)的連接關(guān)系，把連接這兩個(gè)結(jié)點(diǎn)的骨骼存入骨架表中;選擇骨骼刪除功能時(shí)，用戶只需單擊對(duì)應(yīng)骨骼即可把該骨骼信息從骨架表中刪除，最終得到新的骨架。

3.1? 半自動(dòng)骨架提取實(shí)驗(yàn)平臺(tái)

近六十年來，模型骨架提取方面出現(xiàn)各種骨架提取算法，然而精準(zhǔn)度高通適性強(qiáng)的骨架提取算法仍未找到。丟失大量重要數(shù)據(jù)的點(diǎn)云模型，更加難以實(shí)現(xiàn)準(zhǔn)確的骨架提取，為此建立本半自動(dòng)骨架提取系統(tǒng)，對(duì)三維離散點(diǎn)云模型展開骨架提取和骨骼編輯操作，得到更準(zhǔn)確的點(diǎn)云模型骨架。系統(tǒng)的核心功能如下：中心點(diǎn)計(jì)算功能、勾畫輸入功能、交互功能、三維顯示功能等。

3.2? 骨架提取算法的實(shí)現(xiàn)

對(duì)點(diǎn)云進(jìn)行立體空間區(qū)域劃分是骨架提取的首要任務(wù)，第二步是通過計(jì)算得到點(diǎn)云法向量的近似值，接下來就是根據(jù)用戶的判斷，選擇相應(yīng)的最佳算法，計(jì)算得到準(zhǔn)確度高的骨架結(jié)點(diǎn)。系統(tǒng)主要提供“中軸點(diǎn)提取法”和“ROSA點(diǎn)提取法”兩種骨架結(jié)點(diǎn)計(jì)算方法。

3.2.1? 骨架結(jié)點(diǎn)定義

（1）中心點(diǎn)的定義。在三維空間中，中心點(diǎn)就是到點(diǎn)集S中的每個(gè)點(diǎn)的距離平方和最小的點(diǎn)。如果切割平面的點(diǎn)集有重大缺失，則計(jì)算出的中心點(diǎn)不在正確中心位置，骨架結(jié)點(diǎn)采用中心點(diǎn)的前提是切割平面的點(diǎn)集相對(duì)完整，數(shù)據(jù)缺失不嚴(yán)重。

（2）ROSA點(diǎn)的定義。Tagliasacchi[2]等人率先提出：到點(diǎn)集S中的每個(gè)點(diǎn)的法線方向所在的直線平方距離和最小的點(diǎn)r就是ROSA點(diǎn)，也就是說，點(diǎn)集S對(duì)應(yīng)的ROSA點(diǎn)r的坐標(biāo)值xr滿足：

其中，點(diǎn)集S中的任意一點(diǎn)表示為pi=（xi，vi）。ROSA點(diǎn)的法線方向vr滿足：

其中，<，>表向量的夾角，vi為點(diǎn)集S中任意一點(diǎn)的法線方向。

利用ROSA點(diǎn)作為骨架結(jié)點(diǎn)的優(yōu)勢在于，利用點(diǎn)集S中所有點(diǎn)的法線方向，可以彌補(bǔ)數(shù)據(jù)大、面積缺失的不足。當(dāng)出現(xiàn)有重大數(shù)據(jù)缺失的不完整點(diǎn)云時(shí)，利用僅存的少量點(diǎn)的法線方向信息可以高效彌補(bǔ)缺失，保持ROSA點(diǎn)的位置和方向的穩(wěn)定。

3.2.2? 最佳切割平面

設(shè)點(diǎn)pi=（xi，vi）是原始模型點(diǎn)云P中的任意點(diǎn)，切割平面為πi過點(diǎn)pi，其法向量為vi，點(diǎn)集Ni距離平面πi的距離小于δ，厚度值δ可變，其初值設(shè)定為整個(gè)點(diǎn)云模型的包圍盒對(duì)角線長度的2%。利用歐幾里得距離和馬哈拉諾比斯距離確定切割平面的鄰點(diǎn)集Ni。以pi為根展開廣度優(yōu)先搜索，遞歸增加切割平面πi附近的點(diǎn)。

利用過點(diǎn)pi的最佳切割平面πi*計(jì)算局部ROSA，關(guān)于點(diǎn)集Ni中的所有點(diǎn)的法向量旋轉(zhuǎn)對(duì)稱性最強(qiáng)的就是最佳切割平面的法向量。使用迭代逼近解決對(duì)應(yīng)非線性的復(fù)雜優(yōu)化問題。初始方向vi0經(jīng)過下列變分問題使方向得到逐步更新：

（3）

Ni（t）是切割平面第t次迭代的鄰點(diǎn)，n（pj）是點(diǎn)pj的單位法向量。當(dāng)其能夠被改寫為最小化二次型vTMv，當(dāng)‖v‖=1且M=時(shí)，式（3）有閉合形式解。

其中，x表示Ni（t）內(nèi)點(diǎn)的法向量的x分量，y表示Ni（t）內(nèi)點(diǎn)的法向量的y分量，z表示Ni（t）內(nèi)點(diǎn)的法向量的z分量， 表示點(diǎn)集Ni（t）的平均值。

3.2.3? 計(jì)算骨架結(jié)點(diǎn)位置

對(duì)于切割平面附近的點(diǎn)云數(shù)據(jù)，當(dāng)其完整時(shí)，可以直接選擇中心作為骨架結(jié)點(diǎn);當(dāng)其存在重大數(shù)據(jù)缺失時(shí)，需要選擇利用ROSA算法，通過勾畫輸入的方式，定位點(diǎn)pi和過點(diǎn)pi的最佳切割平面πi*后，接下來計(jì)算局部旋轉(zhuǎn)對(duì)稱中心，即相應(yīng)的ROSA點(diǎn)ri*，利用約束，定義該骨架結(jié)點(diǎn)的位置為：

Ni*是切割平面相關(guān)鄰點(diǎn)，式（4）是標(biāo)準(zhǔn)的最小化二次型，其閉合形式解可以通過直接微分求出。

3.2.4? 骨架連接關(guān)系位置的提取

在已經(jīng)獲取骨架結(jié)點(diǎn)的前提下，只需在骨骼添加模式下，點(diǎn)擊兩個(gè)骨架結(jié)點(diǎn)，系統(tǒng)通過兩點(diǎn)的坐標(biāo)計(jì)算得到三維空間中兩結(jié)點(diǎn)之間的線性骨骼。為了便于用戶對(duì)骨架進(jìn)行修改，系統(tǒng)還具備交互式骨架編輯功能。用戶可以根據(jù)自己的判斷增刪骨架結(jié)點(diǎn)或骨骼。

3.3? 實(shí)驗(yàn)結(jié)果

使用的點(diǎn)云模型數(shù)據(jù)來自黃惠等人[8]研究點(diǎn)云的L1中值骨架的點(diǎn)云模型數(shù)據(jù)。對(duì)三維點(diǎn)云模型展開骨架提取時(shí)，用戶根據(jù)模型點(diǎn)云數(shù)據(jù)特點(diǎn)，選擇合適的算法計(jì)算相應(yīng)的骨架結(jié)點(diǎn)，然后連接生成骨骼，直到完整的線性骨架提取完畢。借助人工輔助提取得到無誤的骨架。

4? 結(jié)? 論

本文分析了基于ROSA的骨架提取算法的思路和優(yōu)勢，系統(tǒng)地分析了半自動(dòng)可視化點(diǎn)云模型骨架提取的實(shí)驗(yàn)平臺(tái)，詳述了各功能模塊的作用，能夠?yàn)橄肓私馊S點(diǎn)云模型骨架提取技術(shù)的人提供一定參考。點(diǎn)云骨架提取領(lǐng)域仍然有許多未知有待探索。

參考文獻(xiàn)：

[1] 李義琛.點(diǎn)云模型骨架提取算法的研究與實(shí)現(xiàn) [D].南京：南京師范大學(xué)，2012.

[2] Andrea Tagliasacchi，Hao Zhang，Daniel Cohen-Or.Curve skeleton extraction from incomplete point cloud [J].ACM Transactions on Graphics，2009，28（3）：1.

[3] 車武軍，楊勛年，汪國昭.動(dòng)態(tài)骨架算法 [J].軟件學(xué)報(bào)，2003，14（4）：818-823

[4] 張紹廣，李鳳亭，馬惠敏.一種基于權(quán)值的骨架算法 [J].微計(jì)算機(jī)信息，2007，23（6）：255-256.

[5] WU FC，MA WC，et al.Skeleton Extraction of 3D Objects with Visible Repulsive Force [C].Eurographics Symp. On Geometry Processing，2003.

[6] 王剛，高新波，姬紅兵，等.基于區(qū)域增長技術(shù)的樹狀器官的骨架提取算法 [J].西安電子科技大學(xué)學(xué)報(bào)，2003，30（5）：594-597.

[7] 鄒萬紅，陳志楊，葉修梓，等.一種新的點(diǎn)云數(shù)據(jù)特征骨架提取方法 [J].浙江大學(xué)學(xué)報(bào)（工學(xué)版），2008，42（12）：2103-2107.

[8] HUANG Hui，WU Shihao，Daniel Cohen-Or，et al.L1-Medial Skeleton of Point Cloud [J].ACM Transactions on Graphics，2013，32（4）：65.

[9] 段紅娟.點(diǎn)云圖像交互式曲線骨架提取技術(shù)及其應(yīng)用 [D].成都：西南交通大學(xué)，2015.

作者簡介：段紅娟（1982-），女，漢族，湖北宜昌人，計(jì)算機(jī)應(yīng)用講師，碩士，研究方向：數(shù)字圖像處理和模式識(shí)別。