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

Individual tree segmentation for airborne Li DAR point cloud data using spectral clustering and supervoxel-based algorithm

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

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 R2 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.