基于改进的 K-means 算法估测单木树高

孙拱 辛颖 闫灿

摘 要：为快速提取森林单木树高，提高单木树高的提取精度，本研究提出一种改进的 K-means 聚类算法提取单木树高。即利用内蒙古依根地区的野外实测数据和机载 LiDAR 点云数据，以各单木实测坐标为该算法的聚类中心，对机载 LiDAR 点云数据进行圆柱拟合聚类，将圆柱体内垂直方向最高的点视为该单木树冠最高点，利用提取的樹高与野外实测树高进行相关性分析。分析发现，基于改进的 K-means 算法提取的树高与实测树高相关系数 R2为 0.852。结果说明改进的 K-means 算法能够很好的用于机载 LiDAR 点云数据单木树高的提取，降低了传统测量方法的局限性，挖掘了机载LiDAR点云数据的应用潜力。

关键词：机载 LiDAR;改进 K-means 算法;树高

中图分类号：S758文献标识码：A   文章编号：1006-8023（2019）06-0031-05

Estimating Single Tree Height Based on Improved K-means Algorithm

SUN Gong， XIN Ying*， YAN Can

（College of Engineering and Technology， Northeast Forestry University， Harbin 150040）

Abstract：In order to quickly extract the height of forest single tree and improve the extraction precision of single tree height， this study proposed an improved K-means clustering algorithm to extract single tree height. Using the field observation data and airborne LiDAR point cloud data in the Yigen area of Inner Mongolia， the measured coordinates of each single tree were used as the clustering center of the algorithm， and the cylindrical lie point cloud data was clustered and clustered in the vertical direction. The highest vertical point in the cylinder was regarded as the highest point of the single tree canopy， and the correlation between the extracted tree height and the field measured tree height was analyzed. The analysis found that the correlation coefficient R2 between the tree height and the measured tree based on the improved K-means algorithm was 0.852. The results show that the improved K-means algorithm can be used to extract the single-tree height of airborne LiDAR point cloud data， which reduces the limitations of traditional measurement methods and explores the application potential of airborne LiDAR point cloud data.

Keywords：Airborne LiDAR; improved K-means algorithm; tree height

0 引言

激光雷达（Light Detection and Ranging， LiDAR）是一种主动遥感技术，目前在森林资源调查、数字城市和基础测绘等方面有广泛应用[1]。通过该技术能够直接提取树高，作为估测其他参数的基础数据其在测量中存在难度大、耗时长和精度低等问题，故精确获取单株木的树高对反演其他森林结构参数及减少人工工作量具有现实意义[2-6]，而 LiDAR 作为目前实现对地观测最新技术之一，对高度的探测独具优势[7]。

从机载 LiDAR 数据中提取森林结构参数技术在林业中应用广泛，而如何从大量点云数据中准确提取单木参数信息更是研究的重点[8]。李增元等[9]提出目前单木分割方法主要分为 3 类：点云归一化单木法、体元单木法和冠层高度模型（Canopy Height Model， CHM）单木法; Wang 等[10]介绍了一种基于 LiDAR 点云的全自动三维单树建模的全过程;Brandtberg 等[11]利用机载 LiDAR 点云数据提取出 CHM，基于 CHM 栅格图像采用局部最大值方法确定树冠顶点;Reitberger 等[12]提出的 Normalized Cut-基于图论的分割思想;这些研究表明基于机载 LiDAR 数据可以实现单木树高的提取，进而有利于反演其他森林结构参数并提高森林经营的效益。Morsdorf 等[13]以数字表面模型的局部最大值为聚类中心，通过 K-means 算法聚类实现单木分割，其树高估测精度 RMS=0.600;赵晨阳等[14]采用 K-means 算法以单木树冠顶点作为初始聚类中心，经过 4 次迭代提取单木树高，其估测精度为 R2=0.892;基于 K-means 算法的单木树高估测研究表明，在聚类迭代的过程中机载点云数据量大的特点会导致聚类过程不稳定且速度较慢，同时由于 K-means 算法较适合对密度分布均匀且大致呈球形的数据进行聚类分析，这与机载 LiDAR 数据并不相符，故即使按合适比例将点云相对高程值缩放使其分布大体呈球形，仍会影响聚类的精度。而本研究提出改进的 K-means 算法，即以野外实测坐标（x， y）为聚类中心拟合单木圆柱后进行聚类，将聚类结果限制在圆柱范围内，不需要多次迭代，使聚类速度提高，且由于该聚类过程是投影在二维平面进行，避免了原始 K-means 算法适合于球形空间聚类的缺陷，降低聚类过程中产生的误差。

本研究以内蒙古依根地区为研究区，对机载激光雷达数据进行去噪、高程归一化后，利用改进的K-means算法对机载LiDAR点云进行聚类并提取树高，最后进行相关性分析。以实现避免树高测量过程中的资源浪费和提高机载激光雷达获取单木树高精度的目的。

1 研究区概况

本研究区是位于内蒙古境内北部、内蒙古大草原的上库力农场，经度为 120°36′50.48″～120°52′56.53″E，纬度为 50°21′11.08″～50°24′32.00″N，地处内蒙古自治区呼伦贝尔市额尔古纳市的上库力乡，如图 1 所示。该农场为寒温带大陆性季风气候，海拔为 600～700 m，具有较复杂的山岳地形地貌特征。山脉丘陵阴坡广泛分布着以白桦（Betula platyphylla Suk）为主的天然次生林，混生树种主要包括樟子松（Pinus sylvestris var.mongolica）和落叶松（Larix gmelinii）等，林下灌木层主要由筐柳（Salix linearisipularis）和石棒绣线菊（Spiraea media）等组成。

2 材料与方法

2.1 样地布设及数据获取

2.1.1 激光雷達数据

本研究所用数据是于 2012 年 8 月 26 日进行飞行试验所获取的 22 个东西方向条带数据，所用观测仪器为 Leica RCD105 相机，其镜头为 65 mm，飞行搭载所用雷达系统为机载激光扫描系统 Leica ALS60，飞行的相对高度为 1 300 m，其波长为 1 064 nm，扫描方式是线性扫描，光斑大小为 0.22 m，点云密度为每平方米 2～4 个脉冲，图像分辨率为 20 cm，图像重叠率达 50%以上。研究区数据采集过程如图 2 所示。

2.1.2 地面数据

为验证飞行数据，在 2012 年 8 月，在研究区中均匀布设了 33 个半径为 10 m 的圆形样方，利用 Trimble GeoXT6000GPS 定位仪对各样方中心点，样方各角点及样方内所有单木进行差分定位，并结合基站数据对定位坐标进行差分运算，使差分定位精度在厘米级，满足激光雷达提取单木位置精度要求，不会出现实测树木位置偏离的现象。采用 Vertex IV 超声波树木测高测距仪测量单株树高及枝下高，在 30 cm 范围内其高度分辨率达 0.1 m。此次野外调查共测得单木 1 500 株，其中白桦 1 238 株，落叶松 244 株，樟子松 18 株。表1为地面实测树高的基本统计量。

2.2 数据预处理

2.2.1 机载 LiDAR 点云去噪

机载激光雷达中将数据采集过程中由于飞行物等返射回的极高点信号和低于地面水平的物体（如井壁等）反射回的极低点信号统称为噪声点。本研究采用 Isolated points 算法判断孤立点，即在假定以某点为中心点在其 25 cm 半径内无其他点的前提下可判断该点为噪声点，最后对未能剔除的噪声点采取手工剔除的方法[15]。

2.2.2 机载 LiDAR 点云分类

对去噪后的数据进行点云滤波处理，即分离地面点和非地面点。本研究采用不规则三角网格法（Triangulated Irregular Network，TIN），TIN 是建立数字高程模型（DEM）和数字表面模型（DSM）的重要方法之一， TIN 滤波原理是根据点云间高程差值是否满足临界条件和对满足条件的邻近点进行分类，即首先选择一部分最低点作为种子点建立最初的不规则三角网模型，然后连续加入满足临界条件的点作为种子点，建立新的不规则三角网模型，进行迭代，直到没有新的种子点加入时终止，最终完全分类出地面点和非地面点[16]。

2.2.3 高程归一化

将分类后 LiDAR 地面点云数据按适当比例的单元划分成栅格图像，获取栅格内点云数据的高程均值，并生成数字高程模型（digital elevation model， DEM），然后非地面点云数据的高程减去 DEM 的高程， 得到植被点云数据的高程值，此过程即高程归一化[17]。

2.3 改进的 K-means 算法

原始 K-means 算法是常用的聚类算法之一，是一种基于距离的迭代式算法，但它会出现聚类结果陷入局部最优解及因采用误差平方和准则函数出现的将大聚类簇分割开的情况，且在聚类中心一定的情况下，将该聚类算法用于提取单木树高，并不能体现出多次迭代的优势。

为了改善上述问题并减少迭代次数，提高聚类速度同时降低聚类误差。本研究提出改进的 K-means 算法，利用依根试验区野外实测数据和激光数据进行实验，算法步骤如下：

（1）确定初始聚类中心。即从 n 个样本数据中选取k个特征数据作为中心点，本研究以野外调查中定位仪获取的各单木坐标（x，y）为初始聚类中心。

（2）拟合单木圆柱。将初始聚类中心作为圆柱底面圆的中心点，根据实际树高情况确定圆柱高为 25 m（过低会导致树高被低估，过高则不能避免异常点），经实验比较发现底面圆半径为 r=1.5 m 时树高估测的效果最好，在此基础上拟合单木圆柱。

（3）计算欧式距离并进行聚类。拟合单木圆柱后将所有激光雷达数据投影到底面圆所在的二维平面并计算各个点到底面圆中心点的欧氏距离，距离不大于设定半径的所有点归为一类，按此方法依次聚类出所有单木，并获取聚类后的单木点云数据。其中，欧式距离的计算公式：

D=SQRT （（x1-x2）2 +（y1-y2）2）  。 （1）

式中：D表示欧式距离;x1，x2表示两点的横坐标值;y1，y2是两点的纵坐标值。

（4）提取估测树高。将聚类后各圆柱体内 Z 值最高的点视为单木树冠顶点，其相对高程值视为树高。

2.4 相关性分析

本研究基于改进 K-means 算法得到估测树高后与实测树高进行相关性分析。其中估测树高与实测树高的相关程度用 R2 评价，其值越大，说明相关程度越高[18]。

3 结果与分析

3.1 点云数据预处理结果

对激光点云进行预处理，首先对点云进行去噪处理，本研究采用 Terrosolid 软件对点云进行去噪处理，采用 Isolated points 算法判断孤立点，假设当前点为中心的 25 m 半径的球形空间内没有其它点的情况下，判断当前点为噪声点，最后在软件中手动去噪。去噪后进行分类处理，本研究采用不规则三角网格法，分类出地面点和非地面点。接着对点云进行归一化处理，得到预处理后的点云数据，结果如图 3 所示。

3.2 改进 K-means 算法聚类结果

将预处理后的 las 点云数据按样方导入到 matlab 中运行得到样本数据，将野外实测数据按各样方整理得到聚类中心数据，将样本数据和聚类中心数据分别导入，按照改进的 K-means 算法運行依次得到各单木估测树高和聚类后点云数据，运行过程中生成拟合单木圆柱体，以第 8 个样方为例，结果如图 4 所示。

3.3 相关性分析结果

经改进的 K-means 算法聚类后得到单木估测树高，将实测数据与激光雷达的估测数据进行相关程度分析，将结果记录见表 2。

4 结论与讨论

目前基于机载激光雷达技术获取林分平均树高技术已成熟，但从识别单木到获取森林单木信息仍有很大的进步空间，故本研究基于改进 K-means 算法在已知单木坐标（x，y）前提下进行提取单木树高实验，结合实验过程可得到以下结论。

（1）本研究使用野外数据时要注意将经纬度转化为大地坐标，与点云数据值对应，且野外实测数据中有少数的枯死木和丛生木、树冠枯死木，以及低矮灌木在整理数据的过程中应将其作为噪声点剔除，避免产生较大误差，聚类过程中需拟合单木圆柱，圆柱底面圆半径会影响到树高估测的精度，半径设定较小会使估测结果偏低，半径较大会错误聚类，这些因素都影响到本研究的精度。

（2）本次研究表明估测树高与实测树高相关系数 R2 为 0.852，Morsdorf 等[13]基于 K-means 算法实现单木分割，其树高估测精度 RMSE=0.600;赵晨阳等[13]采用 K-means 算法估测树高精度为 R2=0.892;说明基于改进的 K-means 算法和原始 K-means 算法都适用于单木树高提取，但本研究没有取得较高的精度主要有两个原因，首先半径的设定不灵活，因为天然林分中树木生长不均一，有高大树木的也有低矮的树木，其对应的半径设定也应该有区别，如设定动态半径（高于 10 m 的树木r=1.5，低于 10 m 的 r=1.2）树高估测的精度应有所提高;其次本研究不需要已知的z坐标，只利用 x、y 坐标就可以实现树高的估测，与原始 K-means 算法相比减少了高程参数，提高了聚类速度，精度没有得到较大提高。

（3）目前虽然机载激光雷达技术已经广泛应用于林业的研究，但实验的高成本及人力的大量输出仍是面临的主要问题，本研究可以实现在已知 x、y坐标的情况下较准确的获取树高而不需人力测量，可以避免测量过程中的大量人力输出，同时提高机载激光雷达获取单木树高的精度，且基于单木水平的树高估测相对于整体林分平均树高的估测更符合实际生产意义。

（4）随激光雷达技术的不断发展，大范围获取林分树高的技术已逐渐成熟，但单木分割的相关研究表明，在提取树高的过程中目前的方法都有各自的适用范围，不能够推广，且单木水平的森林结构参数相对于林分更有实用价值，故为了能获取更高的精度，降低成本，提出新的普遍适用的聚类算法应是未来发展的重心。

【参 考 文 献】

[1]吴娇娇，张亚红，杨凯博，等.机载激光雷达在林业中的应用[J].安徽农业科学，2016，44（35）：209-212.

WU J J， ZHANG Y H， YANG K B， et al. Application of airborn LiDAR in forestry[J]. Journal of Anhui Agricultural Sciences， 2016， 44（35）： 209-212.

[2]邢艳秋，姚松涛，李梦颖，等.基于机载全波形LiDAR数据的森林地上生物量估测算法研究[J].森林工程，2017，33（4）：21-26.

XING Y Q， YAO S T， LI M Y， et al. Estimation algorithm of forest aboveground biomass based on airborne full-waveform LiDAR data[J]. Forest Engineering， 2017， 33（4）：21-26.

[3]王晓林，郭斌.柞树树高与胸径相关关系的研究[J].森林工程，2012，28（6）：18-21.

WANG X L， GUO B. Study on the correlation between height and diameter at breast height for Quercus mongolica[J]. Forest Engineering， 2012， 28（6）：18-21.

[4]李善尧.樟子松天然林树高-胸径模型及胸径分布规律分析[J].林业科技，2018，43（2）：10-13.

LI S R. Analysis of height-diameter relationship and diameter distribution of pinus sylvestris var. mongolica nature forest[J].Forestry Science & Technology，2018，43（2）：10-13.

[5]尤号田，邢艳秋，王萌，等.小光斑激光雷达数据估测森林生物量研究进展[J].森林工程，2014，30（3）：39-42.

YOU H T， XING Y Q， WANG M， et al. The progress on estimating forest biomass using small footprint LiDAR data[J]. Forest Engineering， 2014， 30（3）：39-42.

[6]邢艳秋，尤号田，霍达，等.小光斑激光雷达数据估测森林树高研究进展[J].世界林业研究，2014，27（2）：29-34.

XING Y Q， YOU H T， HUO D， et al. Research progress in estimating forest tree height using small footprint lidar data[J]. World Forestry Research， 2014，27 （2）： 29-34.

[7]周淑芳.基于机载LiDAR与航空像片的单木树高提取研究[D].哈尔滨：东北林业大学，2007.

ZHOU S F. Research on single tree height extraction based on airborne LiDAR and aerial photograph[D]. Harbin： Northeast Forestry University， 2007.

[8]刘群.基于小光斑机载LiDAR数据的单木三维分割[D].北京：北京林业大学，2016.

LIU Q. Single tree 3D segmentation based on small spot airborne LiDAR data[D]. Beijing： Beijing Forestry University， 2016.

[9]李增元，刘清旺，庞勇.激光雷达森林参数反演研究进展[J].遥感学报，2016，20（5）：1138-1150.

LI Z Y， LIU Q W， PANG Y. Review on forest parameters inversion using LiDAR[J]. Journal of Remote Sensing， 2016， 20（5）： 1138-1150.

[10]WANG Y S， WEINACKER H， KOCH B， et al. Lidar point cloud based fully automatic 3D single tree modelling in forest and evaluations of the procedure[J]. The International Archives of the Photogrammetry， Remote Sensing and Spatial Information Sciences， 2008：45-52.

[11]BRANDTBERG T， WARNER T A， LANDENBERGER R E， et al. Detection and analysis of individual leaf-off tree crowns in small footprint， high sampling density lidar data from the eastern deciduous forest in North America[J]. Remote Sensing of Environment， 2003， 85（3）： 290-303.

[12]REITBERGER J， SCHNORR C， KRZYSTEK P， et al. 3D segmentation of single trees exploiting full waveform LIDAR data[J]. Isprs Journal of Photogrammetry & Remote Sensing， 2009， 64（6）： 561-574.

[13]MORSDORF F， MEIER E， ALLGOWER B， et al. Clustering in airborne laser scanning raw data for segmentation of single trees[J]. International Archives of the Photogrammetry Remote Sensing & Spatial Information Sciences， 2003： 27-33.

[14]赵晨阳，邢艳秋，霍达，等.基于机载LiDAR落叶松树冠几何形状三维重建关键技术研究[J].西北林学院学报，2015，30（2）：186-190.

ZHAO C Y， XING Y Q， HUO D， et al. Key technologies of three-dimensional geometric reconstruction of larch crown shape based on LiDAR data[J]. Journal of Northwest Forestry University， 2015， 30（2）： 186-190.

[15]WANG H， ZHANG Y， LI P， et al. A method of deriving DEM from airborne LiDAR points cloud data[C]. Proceedings of the Urban Remote Sensing Event， 2013：13-16.

[16]毛建华，何挺，曾齐红，等.基于TIN的LIDAR点云过滤算法[J].激光杂志，2007，28（6）：36-38.

MAO J H， HE T， ZENG Q H， et al. A filtering algorithm for LIDAR point cloud with TIN[J]. Laser Journal， 2007， 28（6）： 36-38.

[17]焦義涛，邢艳秋，霍达，等.基于机载LiDAR点云估测林分的平均树高[J].西北林学院学报，2015，30（3）：170-174.

JIAO Y T， XING Y Q， HUO D， et al. Study on mean canopy height estimation from airborne LiDAR point cloud data[J]. Journal of Northwest Forestry University， 2015， 30（3）： 170-174.

[18]CHATTERJEE S， PRICE B. Regression analysis by example[M]. New York： J. Wiley， 2003.