基于改进欧式聚类的三维激光雷达点云目标分割方法

姚绍华， 贺 松， 涂园园

（贵州大学 大数据与信息工程学院， 贵阳 550025）

0 引 言

三维激光雷达有着较高的测量准确性、较大的探测范围以及不受光照条件影响的抗干扰能力，这些优势使其成为了环境主动感知领域的一项关键技术，在智能驾驶、移动机器人等领域得到广泛的应用［1］。 三维激光雷达扫描产生的点云是一系列无序的点，点与点之间无拓扑关系，要实现对环境周围目标的识别，首先，关键内容就是要对点云进行聚类分割，使其成为一个个独立的子集，每个子集都有相对照的物理目标，这为后续的目标分类或识别提供了重要基础。 进一步也表明分割的准确程度将直接影响后续的处理效果。 因此研究一种能提高分割准确率的分割方法是非常有必要的。

目前，点云分割算法主要基于从几何约束和统计规则出发制定的严格的人工设计的特征。 分割的主要过程是将原始3D 点分组为非重叠区域。 这些区域对应于一个场景中的特定结构或对象。 由于这种分割过程不需要有监督的先验知识，因此所得到的结果没有很强的语义信息。 这些方法可以分为基于边缘的、基于区域增长的、基于模型拟合的和基于聚类的4 种方法［2］。 其中，基于边缘的分割方法是通过定位亮度快速变化的点，这类似于一些二维图像分割方法。 此方法虽然可以简单快速运行，但只适用于简单场景，对于密集和大面积的点云数据集处理效果不佳。 基于区域增长的分割方法是一种经典的分割方法，通过将2 个点或2 个区域单元之间的特征相结合，以测量像素（2D）、点（3D）或体素（3D）之间的相似性，并将其合并在一起。 此算法的精度依赖于种子的生长准则和位置，且计算量大，不利于智能驾驶系统的实时性。 模型拟合的核心思想是将点云与不同的原始几何图形进行匹配，通常被认为是一种形状检测或提取方法。 RANSAC 技术就是一种流行的模型拟合方法，但该算法必须手动定义或选择模型，通常是平面、球体或其他可以用代数公式表示的几何图元，不适用于交通道路上的障碍物分割［3］。 基于聚类的方法广泛应用于无监督分割任务［4］，该算法是具有相同目标的不同方法的混合，即将具有相似几何谱特征或空间分布的点组合成相同的均匀模式。 与区域生长和模型拟合不同，这些模式通常没有预先定义，因此基于聚类的算法可用于不规则对象分割。 对于每种聚类方法，可以选择具有不同特征的几个相似性度量，包括欧几里德距离、密度和法向量。

为了满足目标点云分割算法的准确性要求，本文基于传统欧几里得聚类算法，提出了一种优化算法来分割目标。 由于点云数据具有近密远疏的特点，将距离阈值变为根据距离改变的可变阈值，并同时考虑距离阈值与角度阈值，增加分割的可靠性。

1 基本工作

1.1 数据预处理

1.1.1 下采样

通过车载激光扫描系统获取的车载LiDAR 点云数据是海量的，且存在数据冗余，为了便于后续处理，需对点云数据进行下采样，减少点云数量，以减少后续处理时间。

1.1.2 地面去除

本文认为需要检测的目标均在地面之上，目标点云与地面点云相连接，若直接进行分割操作，可能造成分割结果不理想。 因此将地面移除后，目标点云会相互分离，再利用聚类算法对目标点云进行聚类分割。 传统的地面点云去除算法是将地面建模为一个固定平面或者二次曲面，但大都依赖于固定阈值［5］，而且现实情况下的路面点云并不是一个标准的曲面模型。 本文采用多尺度网格的点云滤波算法，通过找到地面种子点并将其他点的高度与其比较，判断网格中的点是否为地面点，从而分离点云数据中的地面点和非地面点。 对此拟做探讨阐释如下。

（1）多尺度网格构建。 激光雷达扫描得到的点云数据是一系列无序的点，但每个点都包含了相应的空间坐标信息，由此可以引入虚拟网格概念。 多尺度网格的示意图如图1 所示。

图1 多尺度网格示意图Fig.1 Multi-scale grid diagram

图1（a）中，黑点表示点云数据，长方体表示相应尺度的网格；图1（b）中，即为在虚拟网格内将三维坐标点投影到X - Y平面，方格的颜色深浅表示虚拟网格尺度的大小。 由此可知，将点云数据按照其X-Y坐标建立网格索引，这样每个点均可通过索引快速查询。

点云网格间的索引关系计算公式为：

其中，X，Y为网格号；x，y为点云的平面坐标；xmin，ymin为整个数据集的最小平面坐标；m为网格单元的尺度；INT 表示对计算结果向下取整。

（2）地面去除。 点云网格化处理后，在每个网格内搜寻最低点作为种子点，并通过将网格中的其他点与种子点比较判断该点是否为地面点。 为了防止最低点在地面以下，即非地面点，本文将最低点加上0.13 作为种子点的高度，再进行比较。 然后保留非地面点，最终实现对地面点云的去除。

1.2 聚类

聚类算法是一种无监督算法，由于不需要训练集，而且算法简单快速，已经广泛应用于图像处理、数据挖掘以及模式识别等领域。 欧式聚类是一种基于欧式距离度量的聚类算法［6］，基于KD-Tree 的近邻查询算法，计算邻域点到该点的欧氏距离，将在阈值范围内的点聚为一类，通过反复迭代，直到没有新点加入为止［7］。 具体数学公式可写为：

其中，qi，pi∈Q，Q是一个点云集。 欧式聚类流程步骤如图2 所示。

图2 欧式聚类流程图Fig.2 Euclidean clustering flowchart

通过欧氏聚类进行分割的效果主要由设置的距离阈值决定，当设置的阈值过大时，会出现过分割现象，反之，则出现欠分割情形［8］。 同时点云数据具有近密远疏的特点，如何设置合适的阈值成为一个关键问题。 本文根据目标到激光雷达的距离动态的选择阈值，来避免使用同一阈值产生的过分割或欠分割问题。 动态阈值可根据式（3）来设置：

其中，Xi和Yi是待搜索的点或待搜索的聚类中心点的坐标；α和β是用来调整d的参数，与激光雷达的角分辨率和角度精度有关，角分辨率越小，角度精度越高，α和β的值越小，具体数值需通过多次实验确定。

然而仅通过距离阈值判断，在相邻的行人目标上还是容易出现欠分割问题，如图3 所示。 由于激光雷达中的多个激光器水平扫描周围环境中的物体［9］，相邻2 个行人腿部之间形成的夹角相较于属于同一物体内点与点之间形成的夹角要大一些，如图4 所示。 研究中可以充分利用这一特点，在高度小于行人腿部的种子点进行聚类时设置一角度阈值，将小于角度阈值的点归于同一物体，这样同时利用动态距离阈值和角度阈值可较好地处理相邻行人目标的欠分割问题。

图3 相邻目标欠分割问题Fig.3 Adjacent target under-segmentation problem

图4 行人点云Fig.4 Pedestrian point cloud

2 实验结果与分析

为验证本文方法的有效性，利用自动驾驶领域内比较知名的KITTI 数据集。 数据集由1 台车载Velodyne HDL-64E 激光所采集，扫描频率10 Hz，64线，角度分辨率0.09°探测精度2 cm，每秒130 万点数，探测距离120 m。 计算所使用的电脑配置为：Intel 4.1 GHz i5-10600 CPU，16 GB 内存。 编程环境为C++。

在数据集中随机抽取20 张激光雷达数据进行试验，在对数据进行聚类之前，先进行预处理，原始点云图如图5 所示，预处理后的点云图如图6 所示。

图5 原始点云图Fig.5 Original point cloud

图6 预处理后的点云图Fig.6 Point cloud after pretreatment

通过多次实验将点云图中离原点5 m 以内的障碍物能得到较好聚类结果的阈值0.1 设为d1， 再将使距原点10 m 到20 m 内的障碍物能得到较好聚类结果的阈值0.25 设为d2。 将d1、d2以及对应范围到原点的距离代入式（3）中， 经过调整得到相应的α和β的值。 即：

接着进行欧式聚类，当聚类的中心点的高度小于0.3 m 时加入角度阈值，使角度小于0.4°且满足对应欧式距离阈值的点聚类为一类。 传统欧氏聚类结果和改进的欧氏聚类结果如图7 所示，不同的目标用不同的颜色显示。 传统欧式聚类算法依赖固定阈值，一些相邻目标并没有被分割开，出现了欠分割问题。 而由图7（b）可以看出，本文提出的算法可将相邻行人较好地分割开来。 为了使结果更可靠，通过对点云数据选取200 个目标进行人工标记，以此作为准确率Acc计算的参考。 准确率的计算如下：

图7 点云目标分割结果Fig.7 Point cloud target segmentation results

其中，S1是准确分割的数量，S是总目标数量。

分别通过传统欧式聚类算法和本文提出算法进行处理，计算2 种算法的准确率。 2 种算法的结果见表1。 由表1 结果可知，本文提出的算法准确率达到了86%，而传统欧式聚类算法的准确率只有83.5%，本文提出算法的准确率提高了约2.5%。 但对于行人目标来说，本文提出的算法准确率达到了88.02%，相传较于传统欧式聚类算法82.6%的准确率，提升了约5.4%。 说明本文提出算法能够有效地提高点云目标分割的准确度，并且与分割汽车目标相比对行人目标的分割具有更好的分割效果。

表1 传统算法与本文算法结果比较Tab.1 Comparison of results between traditional algorithm and this algorithm

3 结束语

提出了一种基于欧几里得聚类的改进算法，将原始点云图下采样后经过多尺度网格去除地面点云，然后根据预处理后的点云图中目标到原点的距离动态地选择距离阈值，同时加入角度阈值一同判断，较好地克服了相邻行人目标的欠分割问题。 通过实验进行验证，结果表明本文提出方法在分割目标上准确度提高约2.5%，而在对行人目标的分割上提升了约5.4%，为点云目标的分割提供了一种新思路，是一种较为有效的方法。 但在处理时间上并未取得较好效果，实时性不足，如何改进算法减少分割时间将是下阶段研究的重点。