半自動點云模型線性骨架提取技術(shù)

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

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

中圖分類號：TP391.41 ? ? ?文獻標識碼：A 文章編號：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? 引? 言

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

1? 研究背景及意義

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

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

2.1? 基于KD-樹的k鄰域

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

2.2? 點云法向量

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

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

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

3.1? 半自動骨架提取實驗平臺

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

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

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

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

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

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

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

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

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

3.2.2? 最佳切割平面

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

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

（3）

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

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

3.2.3? 計算骨架結(jié)點位置

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

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

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

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

3.3? 實驗結(jié)果

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

4? 結(jié)? 論

本文分析了基于ROSA的骨架提取算法的思路和優(yōu)勢，系統(tǒng)地分析了半自動可視化點云模型骨架提取的實驗平臺，詳述了各功能模塊的作用，能夠為想了解三維點云模型骨架提取技術(shù)的人提供一定參考。點云骨架提取領(lǐng)域仍然有許多未知有待探索。

參考文獻：

[1] 李義琛.點云模型骨架提取算法的研究與實現(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] 車武軍，楊勛年，汪國昭.動態(tài)骨架算法 [J].軟件學(xué)報，2003，14（4）：818-823

[4] 張紹廣，李鳳亭，馬惠敏.一種基于權(quán)值的骨架算法 [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é)報，2003，30（5）：594-597.

[7] 鄒萬紅，陳志楊，葉修梓，等.一種新的點云數(shù)據(jù)特征骨架提取方法 [J].浙江大學(xué)學(xué)報（工學(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] 段紅娟.點云圖像交互式曲線骨架提取技術(shù)及其應(yīng)用 [D].成都：西南交通大學(xué)，2015.

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