基于改进聚类算法的目标点云分割

张媛 施卫

摘要：激光雷达作为自动驾驶不可或缺的传感器，非地面点云聚类作为环境感知障礙物的重要环节，对自动驾驶汽车的安全至关重要。针对现有聚类方法出现的聚类不足、过度聚类和实时性差的问题，本文提出了一种从粗到细的聚类策略来平衡聚类的精度和速度。首先提出基于角度和距离判断的聚类方法对点云进行粗处理，然后采用基于断点检测的聚类方法对点云进行细化，实现了目标点云的精确分割。最后在公开的KITTI数据集上对本文提出的方法进行了评估，实验结果表明，其分割准确率达到82.2%，且分割时间较其他传统算法明显缩短，该算法具有良好的鲁棒性。

关键词：激光雷达；点云分割；聚类算法

中图分类号：TP18        文献标识码：A

文章编号：1009-3044（2024）07-0008-04

开放科学（资源服务）标识码（OSID）

0 引言

随着人工智能的发展，自动驾驶逐渐成为热门话题。自动驾驶系统主要由感知、决策和控制三个模块组成，是一个综合性的智能控制系统[1]。其中，环境感知模块是自动驾驶汽车的核心。它通过各种传感器获取汽车周围的环境信息，为后续的信息处理提供数据基础。

激光雷达作为自动驾驶非常重要的传感器之一，它具有不受光干扰、信息丰富等优点，其生成的点云数据具体处理流程如图1所示。1） 点云滤波，去除干扰点云。2） 点云分割[2]：将滤波后的点云划分为地面点和非地面点，再将非地面点云聚类为不同的簇。3） 检测与识别[3]：地面点边界提取，非地面点行人、车辆、建筑物等目标的可行驶区域检测与识别。4） 目标跟踪[4]：通过前后帧的相关性，利用卡尔曼滤波或粒子滤波对同一目标进行跟踪。

分割作为处理原始点云数据的开始，聚类作为分割的一部分，其准确性和时效性直接影响到整个自动驾驶。但在实际调查中，笔者发现由于点云数据量庞大且复杂，密度分布不均匀，实际驾驶场景复杂多变，现有的很多方法容易出现聚类过度和聚类不足的问题。

近年来，基于机器学习和深度学习的有监督平面分割方法深受研究者青睐，Bichen Wu等人[5]利用卷积神经网络对LiDAR点云中的物体进行语义分割，可以获得实时性的结果。Qingyong Hu等人[6]引入了一种高效且轻量级的神经架构，该架构使用随机点采样代替更复杂的点选择方法来推断大规模点云的逐点语义。GndNet[7]是一种新颖的端到端点云处理方法，它使用PointNet和Pillar特征编码网络来学习点特征，实现了对点云的实时语义分割。虽然深度学习方法可以实现较高的分割精度，且大部分都可以实现实时性，但基于深度学习的点云分割仍然存在很多问题，例如数据集的规模小，需要大量清晰的坐标、强度和点云颜色的训练数据，导致无法在非结构化的点云模型组成的场景中进行分割。此外，深度学习的计算成本很高，需要专用的GPU设备实现。相比之下，传统的无监督方法在许多情况下仍然以其易于操作和高可靠性而受到青睐[8]。一般来说，无监督平面分割方法可以分为三大类：区域生长法、基于模型拟合的方法和基于聚类的方法。

基于聚类的方法是不同方法的混合体，这些方法有一个共同的目标：将具有相似几何光谱特征或空间分布的点分组到相同的同质神经模式中。与区域增长和模型拟合不同，这些模式通常不是预定义的，因此基于聚类的算法可以用于不规则目标分割，而且基于聚类的方法比监督方法计算量少。

1 点云预处理

1.1 点云滤波

3D点云数据具有稀疏性、无序性、无结构性和数据量大等特点。在分离障碍物点云之前，首先需要对激光雷达获得的点云进行滤波，去除无效目标点云，降低点云数据的密度，以减少计算量和内存占用[9]。下采样滤波可用于去除点云数据中的冗余信息，提高点云数据的处理速度和效率。传统的体素滤波是通过输入的点云数据创建一个三维体素栅格，然后将每个体素内所有的点都用该体素内的代表点（重心）来近似，这样可以大大减少数据量。体素滤波器旨在实现向下采样，同时不破坏点云本身的几何结构，还可以去除一定程度的噪音点和离群点，但会移动点的位置。

本文采用均匀采样滤波器[10]对原始点云进行下采样。通过构建指定半径为0.01m的球体对点云进行下采样滤波，将每一个球内距离球体中心最近的点作为下采样后的点输出。与体素滤波相比，通过均匀采样滤波器下采样后，点云基本分布均匀，且没有移动点的位置。如图2所示，左图为原始点云数据，右图为滤波后的点云数据。

1.2 去除地面点云

对于滤除后的点云采用平面模型估计：[Ax+By+Cz+D=0]，即表示为[nTx=-d]，其中[n=a，b，cT]，[x=x，y，zT]，通过初始点集的协方差矩阵[c∈R3×3]来求解[n]，从而确定一个平面。笔者采用种子点集[S∈R3]作为初始点集，其协方差矩阵为：

[C=i=1：ssi-ssi-sT]

式中：[s]为所有点的均值，协方差矩阵[C]描述了种子点集的散布情况，其三个奇异向量可以通过奇异值分解（Singular Value Decomposition） 求得，这三个奇异向量描述了点集在三个主要方向的散布情况。由于是平面模型，垂直于平面的法向量n表示具有最小方差的方向，可以通过计算具有最小奇异值的奇异向量来求得，并将n代入平面方程后可求出D，进而得到平面模型[11]。

得到平面模型以后，接着计算点云中每一个点到该平面的正交投影的距离，并且将这个距离与设定的阈值[Th]比较，当高度差小于此阈值，认为该点属于地面，当高度差大于此阈值，则为非地面点。经过分类以后的所有地面点被当作下一次迭代的种子点集，迭代优化，最终得到去除地面点的目标点云数据。

2 改进聚类算法

本文提出了一种由粗到精的聚类策略，以达到准确和实时的聚类结果。具体实施方法是输入非地面点云，首先根据邻域点的角度和距离准则进行粗聚类，然后再通过自适应断点检测进行聚类细化，最终输出精细聚类结果。在这一部分中，主要是对去除地面点后剩下的点云进行处理，将非地面点数学描述为：[Png=Pk=xk，yk，zk，k=1，2，…，n]。这样可以充分发挥距离图像邻域关系清晰、获取方便、计算速度快的优点。

2.1 基于角度和距离判断的粗聚类

首先，使用角度判断非地面点云是否为我们所需要的点云，如图3所示，图像相邻的两个点P1、P2与激光雷达发射原点之间形成夹角，假设两束光束中较长的光束所在直线为y轴，相邻光束之间的夹角为α，α是激光雷达在水平或垂直方向上的角分辨率，这主要是由激光的型号决定的。

其中：OP1与OP2的长度表示相邻点的深度值，分别为d1、d2。H为点P1在OP2线上的投影，角度[β]为P1P2与OP2的夹角，用于判断P1和P2是否属于同一聚类对象， [β]的大小可以用公式计算：

[β=arctanP1HP2H=arctand1sinad2-d1cosα]

通过大量计算图像上任意行或列中P1和P2相邻点对应的[β]，发现相邻点属于不同聚类的[β]值一般较小，相邻点属于同一聚类的[β]值较大。对此方法[12]进行优化，加入距离判断条件，即考虑相邻点之间的距离差，距离差[Δd=d1-d2]。结合上述两个判断条件，预先定义角度阈值参数[θ]和距离阈值参数[dth]，因此，当[β>θ]且[?d

加入深度距离判断之后，在处理点云多平面场景聚类时，有效解决了部分平面过度分割的问题。然而，在目标边缘或多个目标相接近时，仍然容易产生分割过度或者分割不足的情况。因此，在粗聚类的基础上还要对聚类目标进行细化。

2.2 基于自适应断点检测的聚类优化

针对粗聚类会产生一个聚类被分割成多个目标的过分割问题和两个聚类错误聚在一起的欠分割问题，需要在聚类过程中进一步融合满足连通性要求的小聚类。在此过程中，主要使用基于邻域策略的自适应断点检测来改进聚类。

KNN[13]算法因其简单易操作受到广泛的运用，其工作原理可以简单概括为：在一个已知类别的数据集中，对于未知类别的任意一个数据点，根据最近的[k]数据类别进行投票，从而实现对未知数据的分类，通常取[k]为奇数值，以防止判别的模糊性。如图4所示，问号中心点的类别可以根据[k]最近邻点来确定。计算得到的距离值[dx，y]采用欧几里得距离，公式如下：

[dx，y=x，-y12+x2-y22+…+xn-yn2]

[=i=1nxi-yi2]

在KNN算法运行的过程中，需要计算所有邻域点的距离，并预设合适的[k]值，才能获得满意的结果，耗时长且不方便。为了获得快速的计算效率，本文没有使用KNN算法，而是使用了更轻量级的RBNN算法[14]。它通过预定义的半径[r]对未知数据点进行分类，该算法的优点是不需要对每个节点执行最近领域搜索，不涉及图像切割和重新排列图形结构。

在实际操作过程中发现，预设的[r]值难以获得满意的结果，而且部分两点夹角比较小的点云难以准确聚类。可以对[r]值进行相应改进，增加断点检测功能，在聚类过程中可以避免聚类不连续点出现。设置断点标志[kbn]，如果点[Pn]是断点，那么标志[kbn]和[kbn-1]都应该设置为TRUE，可表述為：if[ pn-pn-1>Dmax]

then[Kbn]：=TURE，and[kbn-1]：=TURE

式中：[pn-Pn-1]为相邻点[pn]和[pn-1]之间的欧几里得距离，[Dmax]为距离阈值，这在RBNN算法中是一个常数，但很难满足点云密度随距离变化的特点。所以，笔者采用自适应阈值检测方法，如图5所示，[pn-2]、[pn-1]和[pn]为相邻点，以点[pn-1]定义一条虚线，该虚线相对于扫描方向[τn-1]产生的夹角[η]，可以推断最差可接受范围点[Pn]。在此约束条件下，设定第[n]个点的距离[rhn]与[rn-1]有关，用公式表示：

[rhnrn-1=sinηsinn-Δτ]

[Phn-Pn-1=rn-1·sinΔτsinn-Δτ]

式中：[Phn-Pn-1]为断点检测阈值，[Phn]为第n个假设断点，并增加[3×σ]的冗余范围，以处理检测过程中可能出现的噪声情况。因此，最终的自适应阈值表示为：

[Dmax=Phn-Pn-1+3σ]

最终的自适应断点检测器表示一个以点[Pn-1]为中心，半径为[Dmax]的阈值圆，如果下一个[Pn]在阈值圆内，则将[Pn]点添加到[Pn-1]集群中，得到最终的精细化结果。

3 实验结果与分析

为了验证本文提出的算法实际效果，在Linux平台Ubuntu18.04上基于PCL1.9.1实现。实验所使用的数据来源是公开的KITTI数据集[15]，其数据采集是搭载一个Velodyne HDL-64E激光扫描仪，它以每秒10帧的速度旋转，每个周期捕获大约100k个点。

如图6（a） 所示为原始点云鸟瞰图，点云庞杂且混乱，因激光扫描目标过多或激光雷达抖动造成的无效目标点云。经过本文采用的点云预处理方法，在没有改变原始点云特性的基础上，滤除了远处大量的离群点噪音点，且去除了不必要的地面点云，如图6（b） 所示，只针对目标点云进行聚类算法的研究。

图7为分别采用传统的聚类分割算法和本文提出的聚类方法的结果，其对目标点云的分割效果明显不同。其中：（a） 为区域生长分割。（b） 为欧式聚类分割。（c） 为DBSCAN聚类分割。（d） 为本文方法的分割。其中区域生长分割和DBSCAN聚类分割存在分割不足的情况，而欧式聚类分割则存在过度分割的问题，本文提出的从粗到细的聚类方法分割效果更好，一定程度上解决了传统聚类方法造成的分割不足或过度的问题。同时，对于点云目标分割的准确率和每种算法所消耗的时间如表1所示，本文提出的方法不仅分割准确率更高，且耗时较短。

4 结束语

本文提出了一种基于改进聚类算法的目标点云分割方法。该方法针对非地面点云进行处理，在距离图像上利用快速邻域搜索的特点，可以达到较高的粗聚类效率。自适应断点检测可以解决粗糙聚类中聚类过度和聚类不足的问题。将本文所提方法与几种常用的点云聚类分割方法进行了比较，结果表明，所提方法聚类效果更好，耗时较短。

参考文献：

[1] 王涔宇，张平.汽车自动驾驶关键技术分析[J].汽车实用技术，2021，46（23）：20-22，29.

[2] WANG W Q，YOU X，YANG J，et al.LiDAR-based real-time panoptic segmentation via spatiotemporal sequential data fusion[J].Remote Sensing，2022，14（8）：1775.

[3] 伍锡如，薛其威.基于激光雷达的无人驾驶系统三维车辆检测[J].光学 精密工程，2022，30（4）：489-497.

[4] 顾立鹏，孙韶媛，刘训华，等.基于激光点云坐标系的3D多目标跟踪算法研究[J].激光与红外，2021，51（10）：1307-1313.

[5] WU B C，WAN A，YUE X Y，et al.SqueezeSeg：convolutional neural nets with recurrent CRF for real-time road-object segmentation from 3D LiDAR point cloud[C]//2018 IEEE International Conference on Robotics and Automation （ICRA）.ACM，2018：1887-1893.

[6] HU Q Y，YANG B，XIE L H，et al.RandLA-net：efficient semantic segmentation of large-scale point clouds[C]//2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition （CVPR）.June 13-19，2020.Seattle，WA，USA.IEEE，2020：11108-11117.

[7] PAIGWAR A，ERKENT ?，SIERRA-GONZALEZ D，et al.GndNet：fast ground plane estimation and point cloud segmentation for autonomous vehicles[C]//2020 IEEE/RSJ International Conference on Intelligent Robots and Systems （IROS）.ACM，2020：2150-2156.

[8] CHEN H，LIANG M，LIU W Q，et al.An approach to boundary detection for 3D point clouds based on DBSCAN clustering[J].Pattern Recognition，2022，124：108431.

[9] 趙涵，刘永生，赵德鹏，等.基于混合滤波的点云去噪算法研究[J].应用激光，2023，43（9）：147-155.

[10] 肖正涛，高健，吴东庆，等.一种基于体素网格的三维点云均匀降采样方法[J].机械设计与制造，2023（8）：180-184.

[11] 丁鸽，燕立爽，彭健，等.基于RANSAC算法的隧道点云横断面提取[J].测绘通报，2021（9）：120-123.

[12] BOGOSLAVSKYI I，STACHNISS C.Fast range image-based segmentation of sparse 3D laser scans for online operation[C]//2016 IEEE/RSJ International Conference on Intelligent Robots and Systems （IROS）.IEEE，2016：163-169.

[13] 杨晓文，王爱兵，韩燮，等.基于KNN-PointNet的点云语义分割[J].激光与光电子学进展，2021，58（24）：272-279.

[14] KLASING K，WOLLHERR D，BUSS M.A clustering method for efficient segmentation of 3D laser data[C]//2008 IEEE International Conference on Robotics and Automation.May 19-23，2008.Pasadena，CA，USA.IEEE，2008：4043-4048.

[15] CORDTS M， OMRAN M， RAMOS S， et al. The cityscapes dataset[C]//CVPR Workshop on the Future of Datasets in Vision. sn， 2015， 2.

【通联编辑：唐一东】