结合谱聚类和粒子群改进K-means聚类的机载LiDAR点云单木分割方法

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

单木分割的精准度对林木资源的调查有重要意义。但是,传统的单木分割算法在处理大规模点云数据时存在临近树木易混淆、算法运算效率低等问题,针对上述问题,本文提出改进谱聚类和粒子群改进K-means聚类的单木分割算法。首先,通过Mean Shift算法对点云数据进行体素化,在该过程中采用自适应带宽和高斯核函数来计算体素间的相似度,以构建出反映体素特性的高斯相似图。然后应用Nyström方法处理高斯相似图,采用K最近邻搜索采样,以选取代表性样本,降低谱聚类在处理大规模数据时的计算负担,同时保持数据的核心特性。通过Nyström近似,得到相似图的近似特征向量,实现从高维空间到低维特征空间的有效映射。最后引入粒子群算法对K-means聚类进行优化。该优化先随机初始化一群粒子,每个粒子代表一组潜在的聚类中心,在每一次迭代中,粒子根据个体历史最佳位置和群体历史最佳位置更新其速度和位置,并调整聚类中心以最小化内部聚类距离。这种策略能够平衡全局搜索与局部搜索,避免陷入局部最优。本文选取NEWFOR公开的点云数据进行实验。实验结果表明,本文算法获得的分割结果相较对比算法准确率提高5.3%,处理效率提升23倍。

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