一種樹枝點云的骨架提取方法*

趙艷妮　郭華磊

(1.陜西職業技術學院計算機科學系　西安　710100)(2.西安通信學院信息服務系　西安　710106)

?

一種樹枝點云的骨架提取方法*

趙艷妮1郭華磊2

(1.陜西職業技術學院計算機科學系西安710100)(2.西安通信學院信息服務系西安710106)

摘要針對目前點云的樹枝建模方法僅僅是使得樹桿的骨架線與真實樹枝的伸張形狀相似，忽略了樹桿局部細節層次的幾何形狀的展現的問題，論文提出一種樹枝點云骨架點的提取方法。首先對能夠表征真實樹枝的骨架點的幾何參數進行詳細分析，然后對3D激光掃描儀采集的樹枝的單側點云數據中所蘊含的骨架點的幾何參數進行了深入研究，得出了描述其幾何特性的數學模型；接著通過求取樹枝局部最優切分點集的主方向來描述骨架點的軸方向；最后通過運用LS-Method方法來擬合逼近樹枝橫截面圓的位置和半徑兩個幾何參數，從而從樹枝點云中準確的提取出了樹枝骨架點位置、半徑和軸方向三個幾何參數。實驗證明，該方法提取的樹枝骨架點逼近了原始點云所蘊含的真實樹枝的中軸線，有一定的實用價值。

關鍵詞點云; 骨架建模; 局部最優切分

Class NumberTP301.6

1引言

隨著虛擬現實技術的快速發展，景區場景模擬、城市數字化景觀、3D電影和3D游戲等應用迅速普及。三維激光掃描儀能夠非接觸的、直接獲取物體表面高精度的3D點云數據。樹木是自然場景的重要元素之一，其形態模擬的逼真程度直接決定著場景模擬的成功。由于樹木拓撲結構十分復雜，最初，人們對樹木的3D點云數據理解不深入，從圖像處理角度理解點云數據，樹木建模僅僅實現樹木整體形狀與真實樹木相似，細節效果不逼真[1]。

本文以樹木的點云數據為研究對象，以復雜幾何信息(如拓撲結構、曲率和法向量等)為出發點，每段樹木的中軸線有序連接是樹木骨架逼真模擬的必要條件，樹木骨架點的位置坐標逼近樹枝局部最優切分點集的隱含橫截面的幾何中心是樹木骨架點成功提取的關鍵。

2樹木骨架點的提取

樹木的骨架線是一組復雜的連續曲線，可以逐步細分成許多微線段，只要能確定微線段切分點的坐標，就能把樹木骨架線完整還原。關鍵是從樹木點云數據中計算出微線段的切分點，即骨架線的骨架點，就能繪制出樹木骨架線[2]。

2.1樹木的局部最優切分

樹枝在三維坐標中的生長方向分為沿三個坐標軸和非沿三個坐標軸兩種方式[3]，如圖1所示。對于沿著三個坐標軸生長的樹枝可以采用垂直于坐標軸的平面來切分，但采用垂直于坐標軸的平面切分斜著生長的樹枝效果不理想，所得到的局部點集(圖1(a)中透明圓圈部分)來計算骨架點位置、軸方向和切面半徑等幾何參數誤差較大，為了提高精度盡可能逼真描述真實樹枝的幾何特征，采用圖1(b)垂直樹枝的局部最優切分方式。

圖1　垂直于坐標軸的平面切分與最優平面切分

由于樹木隨機生長，樹枝局部垂直切面法向量準確捕捉困難，最優切面難以構造，本文采用K-Means聚類算法來代替最優切分平面的構造，進而獲取樹枝的局部最優切分點集[4]。該算法隨機的將一個點集任意劃分為k個類，而這個類中的個中心點構成了一個中心點集Z。V(z)是距離其中的一個中心點z∈Z最近鄰的點的集合。每一次迭代都將中心點z向V(z)的質心點移動，接著通過計算V(z)中每一個點到距離它最近的新的中心點之間的距離來更新V(z)，然后進行下一次迭代直到符合一定收斂條件算法才結束。圖2給出了采用聚類算法對樹木點云數據進行最優切分的結果。其中，圖2(a)是原始的樹木點云數據，圖2(b)是應用聚類算法獲取的樹枝局部最優切分點集，不同的顏色分別表示不同的最優切分點集。由圖2(b)的切分結果可以看出，聚類算法不僅對沿坐標軸方向生長的樹枝的切分結果滿足了最優切分的要求，而且對于不沿坐標軸生長的樹枝(斜著生長的樹枝)的切分也取得了較好的效果，即使在樹枝有細微的傾斜的位置，它也能夠較好地適應。

圖2　樹木點云數據的最優切分

2.2樹枝骨架點的幾何參數

在樹木的逼真建模中，樹木骨架線描繪樹枝的自然形態，處于樹枝的中軸線上，由骨架點有序連接而成。樹枝骨架點的提取必須能夠反映真實樹木的基本幾何特征。

自然世界的大部分樹木的局部橫截面近似圓形，本文的建模方法采用這個自然規律，如圖3所示。為了滿足骨架線位于樹枝中軸線的特性，骨架線必須穿過樹枝橫截面的圓心，采用橫截面的圓心坐標p(x,y,z)描述骨架點的位置。骨架點的坐標信息是一組離散的點集，但是無法描述樹枝生長趨勢的幾何信息，無法準確繪制樹枝骨架線，橫截面的法向量(軸方向)a描述樹枝的生長趨勢。完整的樹木模型還需要樹皮模型，關鍵要計算樹枝橫截面的半徑。總之，逼真的樹木骨架模型由骨架點位置、法向量和橫截面半徑三個幾何參數共同確定[5]，如式(1)所示。

Skeleton(p(x,y,z),a,r)

(1)

3D激光掃描儀采集的點云數據是單側樹木，僅僅包含樹皮的部分信息，如圖4所示，因而，如何從這些數據中發現樹枝骨架點的幾何參數信息就是關鍵。一種簡單的方法就是將最優切分點集的質心點作為骨架點，但是這種方法所得到的骨架點的位置貼近于樹皮表面，由它們所繪制的骨架線雖然能夠將樹枝的生長趨勢描述出來，但它卻不能滿足骨架線穿過樹枝橫截面中心點這一特征。

圖3　樹木骨架點的三個基本參數

圖4　樹枝的單側點云數據

深入分析單側樹枝的點云數據，樹枝骨架點的三個幾何參數應符合以下條件，如圖5所示。

圖5　點云數據骨架點的幾何特性

1) 樹枝局部橫截面上的骨架點p(x,y,z)與橫截面邊界點的法向量距離和最小，如式(2)所示；

p(x,y,z)=argmin∑pi∈N‖(p-pi)×n(pi)‖

(2)

2) 樹枝局部橫截面邊界點的法向量與骨架點的軸方向a夾角和最小，如式(3)所示；

a=argmin∑pi∈Ncos-1(a×n(pi))

(3)

3) 到樹枝局部橫截面邊界點的最小距離就是樹枝橫截面的半徑r，如式(4)所示。

r=min∑pi∈N{‖p-pi‖}

(4)

其中，pi為樹枝局部橫截面的點，n(pi)則為點pi的法向量，N為所有pi組成的集合。

2.3樹枝橫截面的構造

3D激光掃描儀采集的樹枝點云信息僅僅包含很少一部分的樹皮，自然界中絕大部分樹枝橫截面近似為圓形，點覆蓋了樹枝橫截面邊界的部分圓弧，仍然隱含著樹枝圓形的幾何特征，樹枝局部橫截面圓的圓心就是樹枝骨架點位置，通過擬合空間圓的方式，采用LS-Method(最小二乘擬合算法)算法計算樹枝骨架點位置p(x,y,z)和半徑r。因而，樹枝骨架點提取的關鍵就是構造樹枝的局部橫截面[6]。

樹枝的局部橫截面是垂直于樹枝中軸線的平面，也就是說，它的方向就是表征樹枝的局部生長趨勢的軸方向，這恰好就是最優切分平面的幾何特征，那么樹枝局部橫截面就隱含在最優切分點集中。對于空間平面的構造，根據它的幾何定義，對它起決定作用的幾何參數為表征它的空間方位的點和表征它的空間傾角的法向量。因而，構造樹枝的局部橫截面的關鍵就是由樹枝的局部最優切分點集來求解這兩個幾何參數。

樹枝的局部最優切分點集合囊括了真實樹枝在該位置處的所有關于骨架點的幾何信息。為了使從其中所提取的骨架點能夠逼近真實樹枝的幾何參數，樹枝的局部橫截面就是過該點集的質心點的平面。而表征樹枝局部橫截面的空間傾角的法向量就是局部最優切分點集的主方向，可以通過求解該點集所構造的協方差矩陣C(如式5所示)的最大特征值對應的特征向量來近似估計[7]。

(5)

(6)

其中，pk為樹枝局部最優切分點集合的點，n為樹枝局部最優切分點集合數量。

在式(5)中，協方差矩陣C是一個3×3的矩陣，本文利用SVD分解(奇異值分解)計算矩陣的特征值[8]。根據線性代數SVD分解定義，存在正交矩陣U和V滿足式(7)。

C=UWVT

(7)

其中，正交矩陣U、V均為3×3的矩陣。W是對角陣，對角元素是矩陣C的特征值λ0、λ1和λ2。假設λ0≤λ1≤λ2，λ0、λ1對應的特征向量e0、e1定義了樹枝局部橫截面，而最大的特征值λ2所對應的特征向量e1則就是該平面的法向量，如圖6所示。

圖6　樹枝局部橫截面的構造規則

構造一段樹枝點云局部橫截面的過程如圖7所示，圖7(a)是樹枝原始點云，圖7(b)是樹枝點云的最優切分點集，圖7(c)是局部橫截面的構造結果。其中圖7(c)灰色的點表示原始點云，虛線圓表示樹枝局部橫截面，垂直虛線圓的線段表示樹枝局部橫截面的法方向，描述樹枝的局部生長方向。

圖7　樹枝局部橫截面的構造實例

2.4骨架點幾何參數的計算

由于自然界中大部分樹木的樹枝局部橫截面近似為圓，采用LS-Method(最小二乘擬合法)逼近求解骨架點位置p(x,y,z)和半徑r。原理如下：將樹枝局部最優切分點集投影到對應橫截面上，然后對這些投影點進行3D空間的圓擬合，采用LS-Method逼近方法計算圓心坐標(骨架點的位置)和半徑(樹枝橫截面的半徑)，如圖8所示。

圖8　LS-Method求解骨架點的幾何參數

擬合3D空間圓將3D空間的擬合點映射到2D平面，采用2D平面圓擬合的方法解決3D空間圓擬合問題[9]。本文采用樹枝局部橫截面作為2D圓擬合平面，求解骨架點位置p(x,y,z)和樹枝半徑的步驟如下：

這里以我國某地綠色建筑設計的實際案例為主，分析一下綠色建筑設計的應用。該建筑是高層民用住宅，大概有25000m2左右，建筑共25層，其中地下停車場占據兩層的空間。設計師主要以居民的健康為重點，去考慮設計過程中的各項環節，建筑設計得非常人性化，主要是應用了立體功能疊加的方式進行設計，為建筑設計了不同的功能模塊，建筑的外圍部分均應用了圍護結構。同時，設計師應用了互聯網技術，通過網絡系統輸入通風、噪音等指標，從而構建出具體的建筑模型，使得建筑和設計更加的科學，目前建筑已經竣工兩年，建筑的設計取得業內人士和居住居民的一致認可。

1) 利用樹枝局部最優切分點集合構造樹枝局部橫截面；

2) 旋轉樹枝局部橫截面的法向量與Z軸方向重合，同時樹枝局部橫截面與XOY平面重合；

3) 將樹枝局部最優切分點集合映射到XOY平面上；

4) 采用最小二乘法在XOY平面上構造2D圓擬合，使得距離方程d(xi,yi)最小，其中，(xi,yi)為樹枝局部最優切分點集合點pi映射到X-Y平面的坐標，(x,y)為圓心坐標,r為半徑，如式(8)所示；

(8)

5) 以上步驟都是在局部坐標系下實現的，還需平移變換矩陣T(如式(9)所示)把2D擬合圓坐標和半徑轉換到全局坐標系中，最后計算3D空間圓坐標(x,y,z)(樹皮點云位置)p(x,y,z)和半徑r(樹枝半徑r)。式(8)中(xc,yc,zc)是樹枝局部橫截面位置；

(9)

6) 將擬合的3D空間圓法向量由坐標軸旋轉到初始方向，與樹枝局部中軸線保持垂直。

在以上操作中，步驟2)和步驟3)在局部坐標系下變換采用以下四個步驟進行[10]。

1) 如圖9(a)所示，是樹枝局部橫截面法向量與平面上投影與坐標軸夾角，將繞坐標軸旋轉角到平面，定義旋轉矩陣如式(10)所示：

(10)

(11)

3) 在步驟1)和步驟2)的基礎上，定義將法向量旋轉Z坐標軸方向的旋轉矩陣Rxy如式(12)所示：

Rxy=Rx×Ry

(12)

4) 由步驟3)可以得到局部最優切分點集合映射到XOY平面的點集合，計算過程如式(13)所示，其中P為樹枝局部最優切分點集合矩陣，P′為映射后的點集合矩陣。

P′=P×Rxy

(13)

圖9　局部橫截面法向量旋轉到Z方向的變換原理

通過上述步驟可以擬合3D空間圓的圓心位置坐標、圓半徑和圓所在平面的法向量。由于采用LS-Method逼近法，得到結果與實際誤差較大，本文將上述結果作為高斯最小二乘法曲線擬合的初始值，通過迭代計算3D空間圓的幾何參數，從而得到樹枝骨架點的幾何參數，使樹枝局部幾何特性更加逼真。

3實驗驗證

實驗硬件環境：德國FARO公司的Faro S-PHOTON80脈沖式3D激光掃描儀(掃描距離80m，掃描速度120000點/秒，水平掃描角度360°，垂直掃描角度320°，掃描誤差7mm)；聯想筆記本G460(內存4GB，CPU為Intel Core(TM) i3 M 370，主頻2.4GHz，獨立顯卡Nvidia Geforce，顯存512MB)。實驗軟件環境：Microsoft Visual C++ 9.0和OpenGL 3.7圖形庫。

本文方法對樹枝骨架點提取結果如圖10所示，圖10(a)表示樹枝原始點云，圖10(b)不同顏色的點表示該最優切分點集提取的骨架點的位置p(x,y,z)，圖10(c)骨架點上的線段表示該骨架點處的軸方向a，圖10(d)表示根據本文方法獲取樹枝骨架點的位置坐標、樹枝半徑和樹枝軸方向三個幾何參數繪制的樹枝骨架。可以看出，該方法所提取的骨架點的三個幾何參數較好的逼近了原始點云所蘊含的真實樹枝的中軸線的三個幾何參數。

圖10　樹枝骨架點進行提取圖

4結語

針對樹枝點云數據不完整，數據量大，提取的樹枝骨架點誤差大的問題，本文提出了一種樹枝點云骨架點的提取方法，首先分析了能夠真實描述樹枝的三個幾何參數：骨架點坐標、樹枝半徑和骨架點軸方向，建立描述樹枝幾何特性的數學模型；接著，通過計算樹枝局部最優切分點集合平面法向量，該法向量表示骨架點軸方向；最后，利用LS-Method逼近方法擬合逼近樹枝橫截面圓心坐標(骨架點坐標)和圓半徑(樹枝半徑)。實驗驗證，該樹枝骨架點提取方法快速準確，具有一定實用價值。

參 考 文 獻

[1] Tagliasacchi A, Zhang H, Cohen-Or D. Curve skeleton extraction from incomplete point cloud[C]//ACM Transactions on Graphics(TOG). ACM,2009,28(3):71.

[2] Huang H, Wu S, Cohen-Or D, et al. L1-medial skeleton of point cloud[J]. ACM Trans. Graph.,2013,32(4):65.

[3] 黃洪宇,陳崇成,鄒杰,等.基于地面激光雷達點云數據的單木三維建模綜述[J].林業科學,2013,49(4):123-130.

HUANG Hongyu, CHEN Chongcheng, ZOU Jie, et al. Tree Geometrical 3D Modeling from Terrestrial Laser Scanned Point Clouds: A Review[J]. Scientia Silvae Sinicae,2013,49(4):123-130.

[4] 高士增,張懷清,劉閩,等.基于點云的樹木枝干形態參數提取技術[J].東北林業大學學報,2014,42(4):109-114.

GAO Shizeng, ZHANG Huaiqing, LIU Min, et al. Morphological Parameters Extraction of Tree Branches Based on Point Cloud[J]. Journal of Northeast Forestry University,2014,42(4):109-114.

[5] 陳卓,馬洪超,鄔建偉.基于機載LiDAR數據的三維樹木建模方法[J].計算機工程,2012,38(4):1-3.

CEHN Zhuo, MA Hongchao, WU Jianwei. 3D Tree-modeling Approach Based on Airborne LiDAR Data[J]. Computer Engineering,2012,38(4):1-3.

[6] Rusu R B, Blodow N, Marton Z C, et al. Close-range scene segmentation and reconstruction of 3D point cloud maps for mobile manipulation in domestic environments[C]//Intelligent Robots and Systems, 2009. IROS 2009.IEEE/RSJ International Conference on. IEEE,2009:1-6.

[7] Lou L, Liu Y, Shen M, et al. Estimation of Branch Angle from 3D Point Cloud of Plants[C]//3D Vision(3DV), 2015 International Conference on. IEEE,2015:554-561.

[8] 周廣宇,徐毅,陳楠,等.基于點云數據構建樹木骨架的方法[J].測繪與空間地理信息,2015,38(9):174-176.

ZHOU Guangyu, XU Yi, CHEN Nan, et al. Method for Constructing Tree Skeleton Based on Point Cloud Data[J]. Geomatics & Spatial Information Technology,2015,38(9):174-176.

[9] Huang H, Tang L, Chen C. A 3D individual tree modeling technique based on terrestrial LiDAR point cloud data[C]//Spatial Data Mining and Geographical Knowledge Services(ICSDM), 2015 2nd IEEE International Conference on. IEEE,2015:152-156.

[10] Lu X, Guo Q, Li W, et al. A bottom-up approach to segment individual deciduous trees using leaf-off lidar point cloud data[J]. ISPRS Journal of Photogrammetry and Remote Sensing,2014,94:1-12.

收稿日期:2016年1月3日,修回日期:2016年2月19日

基金項目:陜西省科技廳自然科學基金(編號:2014JM8354);陜西省教育廳重點實驗室科技項目(編號:13JS083)資助。

作者簡介:趙艷妮,女,碩士,講師,研究方向:虛擬現實、模式識別。郭華磊,男,碩士,講師,研究方向:圖像處理。

中圖分類號TP301.6

DOI:10.3969/j.issn.1672-9722.2016.07.031

A Tree Branch Skeleton Extraction Approach Based on Point Cloud

ZHAO Yanni1GUO Hualei2

(1. Department of Computer Science, Shannxi Vocational & Technical College, Xi’an710100)(2. Department of Information Service, Xi’an Communications Institute, Xi’an710106)

AbstractAiming at the branch point cloud modeling method is only done so that the shape of the skeleton Trunk line similar to the real branches, ignoring the geometry Trunk show details of local level issues, this paper presents a point cloud branch skeleton points extraction approach. First, we are able to characterize the real point of the branches of the skeleton detailed analysis of the geometric parameters, and then 3D laser scanners capture branches of unilateral point cloud data inherent in the geometrical parameters skeleton point depth study, obtained describe geometric characteristics of the mathematical model. then strike the branches by local optimal cut points set to describe the main direction of the skeleton point axis direction, and finally to fit the approximate cross-section of the branches circle position and radius of two methods by using LS-Method geometric parameters to accurately extracted from a branch point cloud branch skeleton position, radius and three-axis geometry. The experimental results show that the proposed approach has a certain practical value to approximate the axis of the real tree branches contained in the original point cloud.

Key Wordspoint cloud, skeleton modeling, local optimal cutting