一种树枝点云的骨架提取方法*

赵艳妮　郭华磊

(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