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

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. © 2022 National Remote Sensing Bulletin. All rights reserved.