超体素约简和谱聚类结合的机载LiDAR点云单木分割

王伟伟; 庞勇; 杜黎明; 张钟军; 梁晓军

doi:10.11834/jrs.20220189

遥感技术方法 | 浏览量 : 0 下载量: 1100 CSCD: 4

R-PDF
PDF
导出
分享
收藏
专辑

超体素约简和谱聚类结合的机载LiDAR点云单木分割
Individual tree segmentation for airborne LiDAR point cloud data using spectral clustering and supervoxel-based algorithm
2022年26卷第8期页码：1650-1661
收稿：2020-06-04，

纸质出版：2022-08-07
DOI： 10.11834/jrs.20220189
稿件说明：

移动端阅览

王伟伟，庞勇，杜黎明，张钟军，梁晓军.2022.超体素约简和谱聚类结合的机载LiDAR点云单木分割.遥感学报，26（8）： 1650-1661 DOI： 10.11834/jrs.20220189.

Wang W W，Pang Y，Du L M，Zhang Z J and Liang X J. 2022. Individual tree segmentation for airborne LiDAR point cloud data using spectral clustering and supervoxel-based algorithm. National Remote Sensing Bulletin， 26（8）：1650-1661 DOI： 10.11834/jrs.20220189.

摘要

为提高机载LiDAR点云数据的单木分割精度和效率，本文提出了一种基于Nyström的谱聚类算法。该算法基于谱聚类方法，同时引入了mean shift体素化和Nyström方法，在保持谱聚类算法优越表现的同时，大幅降低了谱聚类算法的空间和时间复杂度。首先，用mean shift方法将点云数据转换到体素空间以合理压缩数据量，使用带有体素权重的高斯相似度函数在体素空间中构造相似图。然后，使用Nyström方法计算相似度矩阵的近似特征向量和特征值。接下来，使用K-means方法在特征空间中进行聚类，并将结果映射回原始点集以获得单木的聚类点。最后，直接从单木聚类中获取单木参数。在黑龙江省孟家岗林场的实验结果表明：本算法有效改进了谱聚类算法，以牺牲5%的分割精度为代价将分割效率提升了约96倍；与K-means方法相比，本算法在分割精度和计算效率方面均表现更优；从分割结果中提取的树高参数具有较高的精度，

http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=35277251&type=

http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=35277248&type=

2.96333337

2.53999996

和RMSE值分别为0.86和1.62 m。本文提出的基于Nyström的谱聚类算法是一种有效的机载LiDAR点云分割方法，可以用来进行单木点云分割和单木因子提取。

Abstract

Light Detection And Ranging (LiDAR) has been increasingly used in forestry research. Individual tree segmentation algorithm for airborne LiDAR point cloud data is greatly important for tree growth monitoring and forest management planning. In this study

a Nystrӧm-based spectral clustering algorithm was proposed to improve the accuracy and efficiency of individual tree segmentation for airborne LiDAR point cloud data.

The proposed method is based on spectral clustering algorithm

and the mean shift voxelization and Nystrӧm method was introduced to maintain the good segmentation performance while improving the computational efficiency. First

the mean shift method was used to transform the point cloud dataset into a voxel space for efficient calculation. Second

a Gaussian similarity function with voxel weights was used to construct a similarity graph in the voxel space. Third

the approximation of the eigenvectors and eigenvalues of the similarity matrix was calculated using the Nystrӧm method. Fourth

the K-means clustering method was performed in the eigenspace

and the segmentation results were mapped back to the original point cloud to obtain the clusters of individual trees. Finally

individual tree parameters were obtained directly from the point cloud of each tree cluster.

Assessed with field measurements

the overall matching rate of the proposed algorithm is 65% for the segmentation of airborne LiDAR point cloud data in the study area. For different stem density plots

the matching rates increased from 61% to 72% as the density decreased. The matching rates for the height layer of 20—25 m and

25 m reached 77% and 78%

respectively. Based on segmented trees

tree heights were extracted in high accuracy with the

value of 0.86 and the Root Mean Square Error (RMSE) of 1.62 m. Compared with other methods

the proposed algorithm produced satisfactory results in segmentation accuracy with the matching rate slightly worse than the spectral clustering algorithm but better than the K-means algorithm. In terms of computing time

the proposed algorithm achieved the highest computational efficiency

which was about 96 times that of the spectral clustering algorithm and three times that of the K-means algorithm.

The proposed Nystrӧm-based spectral clustering algorithm achieved good performance in both segmentation accuracy and computational efficiency. The voxelization method based on mean shift reasonably compressed the volume of LiDAR point cloud and effectively reduced the computational burden of subsequent processes. The Nystrӧm method optimized the eigen-decomposition efficiency of the similarity matrix. Overall

the Nystrӧm-based spectral clustering algorithm can provide feasible individual tree segmentation for airborne LiDAR point cloud data

and key tree parameters can be obtained from the segmentation results.

关键词

Keywords

references

Ayrey E , Fraver S , Kershaw J A , Kenefic L S , Hayes D , Weiskittel A R and Roth B E . 2017 . Layer stacking: a novel algorithm for individual forest tree segmentation from LiDAR point clouds . Canadian Journal of Remote Sensing , 43 ( 1 ): 16 - 27 [ DOI: 10.1080/07038992.2017.1252907 http://dx.doi.org/10.1080/07038992.2017.1252907 ]

Bouneffouf D and Birol I . 2015 . Sampling with minimum sum of squared similarities for Nyström-based large scale spectral clustering // Proceedings of the 24th International Conference on Artificial Intelligence . Buenos Aires : AAAI Press: 2313 - 2319

Bouneffouf D and Birol I . 2016 . Theoretical analysis of the Minimum Sum of Squared Similarities sampling for Nyström-based spectral clustering // 2016 International Joint Conference on Neural Networks (IJCNN) . Vancouver, BC : IEEE: 3856 - 3862 [ DOI: 10.1109/IJCNN.2016.7727698 http://dx.doi.org/10.1109/IJCNN.2016.7727698 ]

Brandtberg T . 2007 . Classifying individual tree species under leaf-off and leaf-on conditions using airborne lidar . ISPRS Journal of Photogrammetry and Remote Sensing , 61 ( 5 ): 325 - 340 [ DOI: 10.1016/j.isprsjprs.2006.10.006 http://dx.doi.org/10.1016/j.isprsjprs.2006.10.006 ]

Chen Q , Baldocchi D , Gong P and Kelly M . 2006 . Isolating individual trees in a savanna woodland using small footprint lidar data . Photogrammetric Engineering and Remote Sensing , 72 ( 8 ): 923 - 932 [ DOI: 10.14358/PERS.72.8.923 http://dx.doi.org/10.14358/PERS.72.8.923 ]

Chen Q , Gong P , Baldocchi D and Tian Y Q . 2007 . Estimating basal area and stem volume for individual trees from lidar data . Photogrammetric Engineering and Remote Sensing , 73 ( 12 ): 1355 - 1365 [DOI 10.14358/PERS.73.12.1355 http://dx.doi.org/10.14358/PERS.73.12.1355 ]

Cohen M B , Lee Y T , Musco C , Musco C , Peng R and Sidford A . 2015 . Uniform sampling for matrix approximation // Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science . Rehovot : ACM: 181 - 190 [ DOI: 10.1145/2688073.2688113 http://dx.doi.org/10.1145/2688073.2688113 ]

Eysn L , Hollaus M , Lindberg E , Berger F , Monnet J M , Dalponte M , Kobal M , Pellegrini M , Lingua E , Mongus D and Pfeifer N . 2015 . A benchmark of lidar-based single tree detection methods using heterogeneous forest data from the alpine space . Forests , 6 ( 5 ): 1721 - 1747 [ DOI: 10.3390/f6051721 http://dx.doi.org/10.3390/f6051721 ]

Fowlkes C , Belongie S , Chung F and Malik J . 2004 . Spectral grouping using the Nystrom method . IEEE Transactions on Pattern Analysis and Machine Intelligence , 26 ( 2 ): 214 - 225 [ DOI: 10.1109/TPAMI.2004.1262185 http://dx.doi.org/10.1109/TPAMI.2004.1262185 ]

Gupta S , Weinacker H and Koch B . 2010 . Comparative analysis of clustering-based approaches for 3-D single tree detection using airborne fullwave lidar data . Remote Sensing , 2 ( 4 ): 968 - 989 [ DOI: 10.3390/rs2040968 http://dx.doi.org/10.3390/rs2040968 ]

Hyyppä J , Hyyppä H , Leckie D , Gougeon F , Yu X and Maltamo M . 2008 . Review of methods of small‐footprint airborne laser scanning for extracting forest inventory data in boreal forests . International Journal of Remote Sensing , 29 ( 5 ): 1339 - 1366 [ DOI: 10.1080/01431160701736489 http://dx.doi.org/10.1080/01431160701736489 ]

Lee H , Slatton K C , Roth B E and Cropper W P . 2010 . Adaptive clustering of airborne LiDAR data to segment individual tree crowns in managed pine forests . International Journal of Remote Sensing , 31 ( 1 ): 117 - 139 [ DOI: 10.1080/01431160902882561 http://dx.doi.org/10.1080/01431160902882561 ]

Li P H , Shen X , Dai J S and Cao L . 2018 . Comparisons and accuracy assessments of LiDAR-based tree segmentation approaches in planted forests . Scientia Silvae Sinicae , 54 ( 12 ): 127 - 136

李平昊 , 申鑫 , 代劲松 , 曹林 . 2018 . 机载激光雷达人工林单木分割方法比较和精度分析 . 林业科学 , 54 ( 12 ): 127 - 136 [ DOI: 10.11707/j.1001-7488.20181214 http://dx.doi.org/10.11707/j.1001-7488.20181214 ]

Li W , Niu Z , Wang C , Gao S , Feng Q and Chen H Y . 2015 . Forest above-ground biomass estimation at plot and tree levels using airborne LiDAR data . Journal of Remote Sensing , 19 ( 4 ): 669 - 679

李旺 , 牛铮 , 王成 , 高帅 , 冯琦 , 陈瀚阅 . 2015 . 机载LiDAR数据估算样地和单木尺度森林地上生物量 . 遥感学报 , 19 ( 4 ): 669 - 679 [ DOI: 10.11834/jrs.20154116 http://dx.doi.org/10.11834/jrs.20154116 ]

Li W K , Guo Q H , Jakubowski M K and Kelly M . 2012 . A new method for segmenting individual trees from the lidar point cloud . Photogrammetric Engineering and Remote Sensing , 78 ( 1 ): 75 - 84 [ DOI: 10.14358/PERS.78.1.75 http://dx.doi.org/10.14358/PERS.78.1.75 ]

Li Z Y , Liu Q W and Pang Y . 2016 . Review on forest parameters inversion using LiDAR . Journal of Remote Sensing , 20 ( 5 ): 1138 - 1150

李增元 , 刘清旺 , 庞勇 . 2016 . 激光雷达森林参数反演研究进展 . 遥感学报 , 20 ( 5 ): 1138 - 1150 [ DOI: 10.11834/jrs.20165130 http://dx.doi.org/10.11834/jrs.20165130 ]

Lindberg E and Holmgren J . 2017 . Individual tree crown methods for 3D data from remote sensing . Current Forestry Reports , 3 ( 1 ): 19 - 31 [ DOI: 10.1007/s40725-017-0051-6 http://dx.doi.org/10.1007/s40725-017-0051-6 ]

Morsdorf F , Meier E , Kötz B , Itten K I , Dobbertin M and Allgöwer B . 2004 . LIDAR-based geometric reconstruction of boreal type forest stands at single tree level for forest and wildland fire management . Remote Sensing of Environment , 92 ( 3 ): 353 - 362 [ DOI: 10.1016/j.rse.2004.05.013 http://dx.doi.org/10.1016/j.rse.2004.05.013 ]

Pang Y. , Lefsky M. , Andersen H. , Miller M. , & Sherrill K . 2008 . Automatic tree crown delineation using discrete return LiDAR data and its application in ICEsat vegetation product validation . Canadian Journal of Remote Sensing , 34 , 471 - 484 . [ DOI: 10.5589/m08-074 http://dx.doi.org/10.5589/m08-074 ]

Pang Y , Li Z Y , Ju H B , Lu H , Jia W , Si L , Guo Y , Liu Q W , Li S M , Liu L X , Xie B B , Tan B X and Dian Y . 2016 . LiCHy: the CAF’s LiDAR, CCD and hyperspectral integrated airborne observation system . Remote Sensing , 8 ( 5 ): 398 [ DOI: 10.3390/rs8050398 http://dx.doi.org/10.3390/rs8050398 ]

Popescu S C , Wynne R H and Nelson R F . 2002 . Estimating plot-level tree heights with lidar: local filtering with a canopy-height based variable window size . Computers and Electronics in Agriculture , 37 ( 1/3 ): 71 - 95 [ DOI: 10.1016/S0168-1699(02)00121-7 http://dx.doi.org/10.1016/S0168-1699(02)00121-7 ]

Reitberger J , Schnörr C , Krzystek P and Stilla U . 2009 . 3D segmentation of single trees exploiting full waveform LIDAR data . ISPRS Journal of Photogrammetry and Remote Sensing , 64 ( 6 ): 561 - 574 [ DOI: 10.1016/j.isprsjprs.2009.04.002 http://dx.doi.org/10.1016/j.isprsjprs.2009.04.002 ]

Sačkov I , Hlásny T , Bucha T and Juriš M . 2017 . Integration of tree allometry rules to treetops detection and tree crowns delineation using airborne lidar data . iForest-Biogeosciences and Forestry , 10 ( 2 ): 459 - 467 [ DOI: 10.3832/ifor2093-010 http://dx.doi.org/10.3832/ifor2093-010 ]

Shi J B and Malik J . 2000 . Normalized cuts and image segmentation . IEEE Transactions on Pattern Analysis and Machine Intelligence , 22 ( 8 ): 888 - 905 [ DOI: 10.1109/34.868688 http://dx.doi.org/10.1109/34.868688 ]

Solberg S , Naesset E and Bollandsas O M . 2006 . Single tree segmentation using airborne laser scanner data in a structurally heterogeneous spruce forest . Photogrammetric Engineering and Remote Sensing , 72 ( 12 ): 1369 - 1378 [DOI 10.14358/PERS.72.12.1369 http://dx.doi.org/10.14358/PERS.72.12.1369 ]

Von Luxburg U . 2007 . A tutorial on spectral clustering . Statistics and Computing , 17 ( 4 ): 395 - 416 [ DOI: 10.1007/s11222-007-9033-z http://dx.doi.org/10.1007/s11222-007-9033-z ]

Wang P , Xing Y Q , Wang C and Xi X H . 2019 . A graph cut-based approach for individual tree detection using airborne LiDAR data . Journal of University of Chinese Academy of Sciences , 36 ( 3 ): 385 - 391

王濮 , 邢艳秋 , 王成 , 习晓环 . 2019 . 一种基于图割的机载LiDAR单木识别方法 . 中国科学院大学学报 , 36 ( 3 ): 385 - 391 [ DOI: 10.7523/j.issn.2095-6134.2019.03.012 http://dx.doi.org/10.7523/j.issn.2095-6134.2019.03.012 ]

Wang Y S , Hyyppä J , Liang X L , Kaartinen H , Yu X W , Lindberg E , Holmgren J , Qin Y C , Mallet C , Ferraz A , Torabzadeh H , Morsdorf F , Zhu L L , Liu J B and Alho P . 2016 . International benchmarking of the individual tree detection methods for modeling 3-D canopy structure for silviculture and forest ecology using airborne laser scanning . IEEE Transactions on Geoscience and Remote Sensing , 54 ( 9 ): 5011 - 5027 [ DOI: 10.1109/TGRS.2016.2543225 http://dx.doi.org/10.1109/TGRS.2016.2543225 ]

Williams J , Schönlieb C B , Swinfield T , Lee J , Cai X H , Qie L and Coomes D A . 2020 . 3D segmentation of trees through a flexible multiclass graph cut algorithm . IEEE Transactions on Geoscience and Remote Sensing , 58 ( 2 ): 754 - 776 [DOI 10.1109/TGRS.2019.2940146 http://dx.doi.org/10.1109/TGRS.2019.2940146 ]

Zeng Z C , Zhu M , Yu H and Ma H L . 2014 . Minimum similarity sampling scheme for Nyström based spectral clustering on large scale high-dimensional data // 27th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems . Springer , Cham : 260 - 269 [ DOI: 10.1007/978-3-319-07467-2_28 http://dx.doi.org/10.1007/978-3-319-07467-2_28 ]

Zhang X C and You Q Z . 2011 . Clusterability analysis and incremental sampling for Nyström extension based spectral clustering // 2011 IEEE 11th International Conference on Data Mining . Vancouver, BC : IEEE: 942 - 951 [ DOI: 10.1109/ICDM.2011.35 http://dx.doi.org/10.1109/ICDM.2011.35 ]

Zhao D , Pang Y , Li Z Y and Liu L J . 2014 . Isolating individual trees in a closed coniferous forest using small footprint lidar data . International Journal of Remote Sensing , 35 ( 20 ): 7199 - 7218 [ DOI: 10.1080/01431161.2014.967886 http://dx.doi.org/10.1080/01431161.2014.967886 ]

Zhen Z , Quackenbush L J , Stehman S V and Zhang L J . 2015 . Agent-based region growing for individual tree crown delineation from airborne laser scanning (ALS) data . International Journal of Remote Sensing , 36 ( 7 ): 1965 - 1993 [DOI 10.1080/01431161.2015.1030043 http://dx.doi.org/10.1080/01431161.2015.1030043 ]

Zimble D A , Evans D L , Carlson G C , Parker R C , Grado S C and Gerard P D . 2003 . Characterizing vertical forest structure using small-footprint airborne LiDAR . Remote sensing of Environment , 87 ( 2/3 ): 171 - 182 [ DOI: 10.1016/S0034-4257(03)00139-1 http://dx.doi.org/10.1016/S0034-4257(03)00139-1 ]

文章被引用时，请邮件提醒。

提交

邻域特征参数融合的点云轮廓特征点提取

全波形机载激光雷达绝对辐射定标与不确定性分析

自适应无监督分类的PolSAR图像机场跑道区域快速检测

基于树顶点多约束的地基点云热带红树林单木分割

融合LT-1升降轨地表形变观测的泸定9·5地震灾后滑坡易发性评价