Improved K-means Clustering Method Based on Spectral Clustering and Particle Swarm Optimization for Individual Tree Segmentation of Airborne LiDAR Point Clouds

The precision of individual tree segmentation is important for survey of forest resources. However, traditional individual tree segmentation algorithms suffer from issues such as near tree confusion and low computational efficiency when processing large-scale point cloud data. To address these issues, this paper introduces an improved K-means clustering method that combines spectral clustering and particle swarm optimization for individual tree segmentation of airborne LiDAR point clouds. The proposed method is designed to overcome the limitations of conventional methods by increasing the accuracy of tree segmentation and optimizing the processing of large and complex point cloud data. By combining advanced techniques in spectral clustering and particle swarm optimization, the proposed method significantly improves the precision and efficiency of individual tree segmentation. Firstly, the voxelization of the point cloud data is performed using the Mean Shift algorithm, where the adaptive bandwidth and Gaussian kernel function compute the similarity between voxels, resulting a Gaussian similarity graph reflecting the properties of voxels. This graph not only encapsulates the space structure of the forest but also improves the accuracy of the subsequent data analysis and processing. After voxelization, the Nyström method is applied to efficiently manage the Gaussian similarity graph. This method uses K-nearest neighbor search to select representative samples, effectively reducing the computational burden associated with spectral clustering when dealing with large-scale datasets. By selecting representative samples, the algorithm ensures that the main features of the data are retained, facilitating a more manageable and accurate clustering process. This method optimizes the processing of large amounts of point cloud data by balancing computational efficiency with the requirement to maintain data integrity and accuracy, thus providing a robust foundation for accurate tree segmentation. Using the Nyström approximation, approximate eigenvectors of the similarity graph are obtained, facilitating an effective mapping from the high-dimensional space to a low-dimensional feature space. Finally, the particle swarm optimization algorithm is introduced to enhance the K-means clustering process. This optimization algorithm first randomly initializes a set of particles, each representing a set of potential cluster centers. In each iteration, the particles update their clustering speed and position based on the best historical position of the individual and the best historical position of the group, adjusting the clustering centers to minimize the internal cluster distance. In this paper, publicly available point cloud data from NEWFOR is selected for experiments. The experimental results show that the segmentation results obtained by the proposed algorithm are 5.3% higher in accuracy and 23 times more efficient than the comparison algorithm. © 2024 China Ship Scientific Research Center. All rights reserved.