半自動點云模型線性骨架提取技術

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

關鍵詞：點云;點云法向量;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? 引? 言

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

1? 研究背景及意義

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

2? 點云數據的預處理

2.1? 基于KD-樹的k鄰域

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

2.2? 點云法向量

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

3? 半自動線性骨架提取系統

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

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

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

3.2? 骨架提取算法的實現

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

3.2.1? 骨架結點定義

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

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

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

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

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

3.2.2? 最佳切割平面

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

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

（3）

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

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

3.2.3? 計算骨架結點位置

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

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

3.2.4? 骨架連接關系位置的提取

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

3.3? 實驗結果

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

4? 結? 論

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

參考文獻：

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

[4] 張紹廣，李鳳亭，馬惠敏.一種基于權值的骨架算法 [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] 王剛，高新波，姬紅兵，等.基于區域增長技術的樹狀器官的骨架提取算法 [J].西安電子科技大學學報，2003，30（5）：594-597.

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

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