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

1 引言

单木分割在森林资源管理和生态研究中扮演着至关重要的角色，其精确分割对了解森林结构、生物多样性和碳储量具有不可小觑的价值。尽管基于LiDAR的单木分割算法展现出巨大的应用潜力，然而，由于森林环境的复杂性和点云数据的冗余性，传统的分割技术常面临着应用普适性的严峻挑战。

研究挑战:

树种繁多的混交林难以准确识别和界定单个树木的边界
广袤林区单木分割时传统算法效率低下
临近树木易混淆问题
大规模点云数据处理困难

现有的单木分割算法可分为基于栅格和基于点云的两大类方法。基于栅格的方法通过对表示树冠上部轮廓的数字表面模型（Digital Surface Model，DSM）或冠层高度模型（Canopy Height Model，CHM）的栅格数据实现对单个树木的分割。特别是采用CHM的情况下，通常先使用局部最大值滤波器来检测树梢，随后用标记控制的分水岭分割算法或者区域生长算法划分单个树冠。

尽管基于栅格的方法在单木分割方面有其应用，但这类方法面临着一系列挑战，如需解决空间数据完整性、分割精度优化及树木遮挡问题，这些因素共同影响基于栅格单木分割算法的鲁棒性。相对而言，基于点云的分割算法有效解决因三维信息丢失而导致的误差问题。尽管如此，但其也存在需处理数值过大，效率低下等问题。

2 算法原理

本文提出一种结合自适应Mean Shift聚类、Nyström方法和粒子群优化K-means算法的点云单木分割流程，显著提升林区单木分割的效率和准确性。

自适应Mean Shift聚类

采用基于局部近邻距离的自适应带宽设置策略，将带宽的选取和数据的局部密度特征相结合，以便更好地适应不同区域的密度变化。

Nyström方法

通过对整个数据集进行选择性采样，构建一个代表性的样本子集，并使用这些样本来近似整个数据集的谱属性，显著降低计算资源需求。

粒子群优化K-means

通过粒子间的信息共享和协作寻找全局最优解，每个粒子代表一组可能的聚类中心，旨在找到能够最小化聚类内距离的最优中心点集合。

算法流程图

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

2.1 自适应Mean Shift聚类

本文采用的自适应Mean Shift算法通过局部密度量化动态调整带宽：

σ = ρ(1 + α(1 - density(x_c)/density_base)

其中σ表示自适应带宽大小，ρ代表初始搜索半径，α为调节系数。这种动态调整机制允许算法：

在高密度区域使用较小半径捕捉细致结构
在低密度区域使用较大半径增强搜索能力
适应从均匀分布到高度聚集的各种分布类型

图2 Mean Shift聚类示意图

2.2 Nyström谱聚类方法

Nyström方法通过采样机制和低秩近似显著降低计算负担：

W = [A B; B^T C]

其中A为采样样本间相似度矩阵，B为采样与剩余样本间相似度矩阵，C为剩余样本间相似度矩阵。通过KNN构建的高斯相似度函数：

S(i,j) = exp(-∥p_i-p_j∥²/2σ²)

2.3 粒子群优化K-means聚类

粒子位置和速度更新公式：

V_id(t+1) = V_id(t) + k₁r₁(P_id-x_id(t)) + k₂r₂(G_id-x_id(t))

X_id(t+1) = X_id(t) + V_id(t+1)

适应度函数综合考虑簇内紧密度和簇间分离度：

F(C) = ΣI_i - λΣΣS_ij

3 实验与结果分析

3.1 实验区数据与精度评定

实验区域位于阿尔卑斯山区，数据来自NEWFOR项目公开的点云数据，实验区位置介于44°N-48°N，5°E-16°E之间。

表1 样地情况描述
样地	样地位置	林区类型	林区树种	点数/个
低密度林区	Cotolivier (意大利)	单层针叶林	落叶松	16,317
中密度林区	Achenkirch (奥地利)	单层针阔混交林	山毛榉、冷杉、云杉	25,193
高密度林区	Leskova Dolina (斯洛文尼亚)	复层针阔混交林	落叶松、冷杉、云杉、山毛榉	53,567

3.2 算法精度分析

匹配率

71%

平均匹配率，显著优于对比算法

准确率提升

5.3%

相较对比算法准确率提高

效率提升

23倍

处理效率提升倍数

表3 样地精度对比(%)
样地	方法	匹配率	提取率	过分割率	欠分割率
低密度样地	文献[21]	78	104	34	22
	文献[22]	80	105	34	20
	本文算法	79	102	33	21

3.3 算法效率分析

实验在一台装备有10核16线程，主频4.9 GHz的Windows系统上进行，处理时间对比如下：

图3 3种场景下不同算法的处理时长

综合考量精度与计算效率后，本文提出的算法在单木分割任务中表现卓越。即使在数据量成倍增加的情形下，本算法显示出极高的稳定性，处理时间的波动性极小。

4 结论

本文针对现有分割方法在处理大规模、多树种的林区时存在的效率低和精度不高问题，提出一种基于谱聚类和粒子群改进K-means聚类的单木分割的创新方法。

方法优势

自适应Mean Shift算法保持空间信息同时减少数据规模
Nyström方法结合KNN采样优化计算过程
粒子群优化解决初始聚类中心选择问题
准确率平均提高5.3%，处理效率提升23倍

局限性

高度郁闭的混交林中弱势树种的错分和漏分割
树木间空间重叠和遮挡导致边界区分困难

未来研究方向：

针对高度郁闭森林环境中的树木边界识别问题，将结合深度学习技术进一步优化分割精度，特别是在复杂混交林场景下的表现。