Fast Segmentation of 3D Point Clouds: A Paradigm on LiDAR Data for Autonomous Vehicle Applications

72 阅读 0 评论 48 点赞

我是靠谱客的博主贪玩大侠，最近开发中收集的这篇文章主要介绍Fast Segmentation of 3D Point Clouds: A Paradigm on LiDAR Data for Autonomous Vehicle Applications，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

原文下载链接：https://www.researchgate.net/publication/318325507_Fast_Segmentation_of_3D_Point_Clouds_A_Paradigm_on_LiDAR_Data_for_Autonomous_Vehicle_Applications

摘要

最近在无人驾驶汽车导航领域的活动引发了一系列的反应，这些反应刺激了汽车工业，推动了这项技术的快速商业化，直到最近，这项技术似乎还是未来的。激光雷达传感器能够提供对车辆周围环境的详细了解，使其在大量的自动驾驶场景中非常有用。对现代激光雷达传感器提供的三维点云进行分割，是实现以乘客安全为目标的态势评估管道的重要一步。这一步需要对地面和车辆路径中的障碍物进行精确的分割，并实时处理每一个点云。该管道的目的是解决激光雷达接收数据的三维点云分割问题，以一种快速、低复杂度的方式，针对现实世界的应用。两步算法首先利用确定性分配的种子点迭代提取地面，然后利用激光雷达点云的结构对剩余的非地面点进行聚类。我们提出的算法在运行时间上优于类似的方法，同时产生相似的结果，并支持该管道作为现实世界应用的分割工具的有效性。

1 介绍

最近在无人驾驶汽车导航领域的活动引发了一系列的反应，这些反应刺激了汽车工业，推动了这项技术的快速商业化，直到最近，这项技术似乎还是未来的。尽管一般观众都很兴奋，但工程界有必要认识到将这种产品推向大规模生产水平的责任。这一实现推动了多传感器融合，以提高自动驾驶车辆的感知能力。

其中一个传感器就是激光雷达，它利用多个激光束来定位周围的障碍物，并以其在密集的三维(3D)点云中描述这些信息的能力而闻名。激光雷达以其长距离和令人满意的精度在学术研究团队中广受欢迎，而最近的硬件进步，承诺更好、更低的成本和更小的规模传感器，似乎吸引了业界的兴趣。

安装在一个无人驾驶车辆传感器本身提供的手段获得的3 d表示周围环境,挑战在于如何分析和提取有意义的信息,如数量的障碍,他们的位置和速度的车辆,和他们班一辆车,一个行人,钢管等。

与图像处理类似，这种分析的第一个重要步骤是将输入数据细分为有意义的簇。本文的工作是针对这个精确的问题，并提出了一种侧重于计算速度和复杂性的方法。快速和低复杂性的分割过程允许将宝贵的硬件资源重定向到自主驱动管道中计算要求更高的过程。

在激光雷达传感器能够捕捉360度信息的情况下，数据被表示为一组三维点，称为点云，它是分层组织的。每一层的点也以椭圆的方式组织，所有椭圆层的起点被认为具有相同的方向。所提出的方法依赖于点云中的这类组织，并利用智能索引来执行有效的分割。

与前面在同一领域的工作类似，我们的方法提出了分两步完成的分割过程;(i)提取属于地面的点，并(ii)将其余点聚类成有意义的集合。这两个步骤都提供了解决问题的原始方法，这些方法主要针对真实世界的应用程序，并在公开可用的KITTI dataset[1]上进行了广泛的测试。

相关文献综述见下文第二节。方法在第三节中有明确的描述，结果可以在第四节中找到，最后一节是第五节，总结了这项工作的结果。

2 文献综述

在这项工作中，我们关注的是三维数据点的分割方法，并强调与自动驾驶相关的应用。对于这个特殊的应用程序，通常的做法是将分割过程分为两个步骤;首先提取地面点，然后将剩余的点聚集到汽车需要感知的对象中。

第一步，Thrun等人提出了一种基于网格的方法。[2]根据网格内点高度的最大绝对差将网格单元划分为地面单元和非地面单元。另一方面，Himmelsbach等人[3]在柱坐标下处理点云，利用点的分布来拟合线段到点云。根据边坡的某一阈值，考虑分段来捕捉地表。为了识别地面，Moosmann等人的[4]正在创建一个无向图，并比较平面法线的局部变化，以表征坡度的变化。Douillard等人[5]引入了GP-INSAC，这是一种基于高斯过程的迭代方案，它根据地面和非地面上的点的高度与高斯分布均值的方差对其进行分类。类似地，Chen等人后来使用高斯过程提取地面，而Tse等人的[7]和Byun等人的[8]工作中可以看到利用马尔可夫随机场的概率方法。

连续地，当使用合适的已知聚类算法时，通常将剩余井距非地面点的聚类处理为一个聚类问题。这就是由于集群算法的简单性、易于部署和高执行速度而流行的集群算法。示例包括欧式集群提取[9]，其实现可以在点云库(PCL)[10]、DBSCAN[11]和Mean-Shift[12]中找到。使用体素化技术压缩并聚集剩余的非地面点也被认为是流行的([3]、[5])。这些算法以不规则的方式遍历点云，在找到一个未标记的点后，它们分配一个新的标签，然后根据一些规则将其传播到邻近的未标记点。在三维空间中，点的不规则访问会导致对邻居的彻底搜索，从而减慢整个过程。虽然这对于无组织的点云是必要的，但是在目标应用程序中，没有利用基于层的点云组织。

3.研究方法

以下各段详细描述了由360度覆盖激光雷达传感器接收的点云分割的完整方法。首先，我们提出了一种确定性迭代多平面拟合技术，我们称之为地面拟合(GPF)，用于快速提取地面点，其次是一种点云聚类方法，称为扫描线运行(SLR)，该方法的灵感来自于二值图像中连接组件标记的算法。

每一段从概念上分为三个部分，包括算法选择背后的简单推理以及新术语的定义、根据伪代码图概述算法以及算法实现细节的讨论。

Ground Plane Fitting

属于地面的云点构成了云点的绝大部分，对地面云点的去除大大减少了计算中涉及的点的数量。地面点的识别和提取非常适合这种应用，主要有两个原因;(i)它们很容易识别，因为它们属于平面，平面是具有简单数学模型的原始几何对象;(ii)可以假定高度值最低的点云的点最可能属于地面。该先验知识用于指定算法初始化的一组点，并消除了随机样本一致性(RANSAC)等典型平面拟合技术中出现的随机选择，从而加快了算法的收敛速度。

一般情况下，单平面模型不足以表示真实地面，因为地面点不能形成一个完美的平面，激光雷达测量在长距离测量中会产生较大的噪声。我们已经观察到，在大多数情况下，地表的坡度变化是需要探测的。拟议的地平面拟合技术扩展了其适用性,这种情况下地表除以均匀的点云分成许多段N之后,沿着x轴(车辆前进的方向),并应用的地平面拟合的算法在每一个部分。

如Alg. 1主回路所示，对于每一个点云段，地面拟合从确定性提取一组低高度的种子点开始，然后用这些种子点估计地面的初始平面模型。对点云段P中的每个点根据估计的平面模型求值，得到点到候选平面上的正交投影的距离。此距离与用户定义的阈值Th区进行比较，后者决定该点是否属于地面。将地面上的点作为种子，对一个新的平面模型进行精细估计，这个过程重复N iter次。最后，将该算法得到的每个点云段的地面点进行拼接，得到整个地平面。

我们选择初始种子点的方法引入了最低点代表(LPR)，该点定义为点云中N个LPR最低点高度值点的平均值。LPR保证了噪声测量不会影响平面估计步长。计算出LPR后，将其作为点云P的最低值点，以高度阈值Th种子内的点作为初始种子进行平面模型估计。

对于平面的估计，我们使用简单的线性模型:

ax + by + cz + d = 0

nTx=-d (1)

令n = [a b c] T, x = [x y z] T，通过协方差矩阵c∈，由种子点集S∈计算得到法向量n :

(2)

其中是集合S中的平均值。

通过奇异值分解(SVD)计算得到协方差矩阵C捕捉种子点的离散程度及其三个奇异向量，描述了该色散的三个主要方向。由于地面是平面，垂直于平面的法向n表示方差最小的方向，由与最小奇异值对应的奇异向量表示。

计算得到n后，由公式1代入x和的值求得d，所拟和的平面是地面点所属平面最好的代表。

图1 这四个阶段说明了SLR聚类算法的过程。圆圈表示点，三角形代表类别标签。

B：扫描线算法

其余不属于地面的点Png需要形成集群，以便在更高级别的后处理方案中使用。我们的目标是对于每个点Pk∈Png获取一个表示其集群标识的标签l，同时使用简单的机制来确保处理过程具有快速运行时间和低复杂性。

在360 度激光雷达传感器数据的情况下，三维点云的多层结构与二维图像的行状结构非常相似，主要区别在于各层元素个数的不均匀性及其圆形形式。该方法将三维点作为图像的像素点，采用二进制图像[13]中的二进连通分量标注技术，生成实时三维聚类算法。

我们把由同一激光雷达环产生的一层点称为扫描线。在每个扫描线中，它的元素被组织在称为运行的连续点的向量中。运行中的元素共享相同的标签，并且是集群的主要构建块。

根据Alg. 2，在不失一般性的前提下，我们假设点云Png从顶部扫描线开始，以栅格逆时针方向穿过。第一个扫描线的运行形成，每个扫描线都接收到它自己的newLabel，这个newLabel由它的所有点元素继承。第一个扫描线的运行将成为上面的运行，并用于将它们的标签传播到后续扫描线中的运行。当新运行的点与其在上述扫描线中的最近邻居之间的距离小于合并时，标签将传播到新运行。当同一运行中的许多点具有具有不同可继承标签的最近邻居时，获胜的标签是最小的。另一方面，当无法为运行中的任何点找到合适的最近邻居时，它将接收一个新标签。上述操作在通过点云的单次传递中执行，完成此操作后，将执行第二次传递，以最终更新点的标签并提取集群。

下图1所示的例子涵盖了该算法的主要实例，分别用白色和彩色圆圈表示地面和非地面点。蓝色圆圈是非地面点，尚未访问。在步骤a中，第一个扫描行初始化为两次运行(橙色和绿色)，每次运行都接收一个新标签(三角形中的1和2)。步骤b)演示新标签的分配和两个标签的传播。特别是8的最近的非地面邻居是2，它们之间的距离大于归并。在本例中，labelsToMerge为空，点8表示一个新的集群。另一方面，10的最近的非地面邻居是3，它们之间的距离小于Th merge，这使得label 1传播到point 10。类似地，点12和点13都靠近它们各自的邻居5和6，并且基于非空的labelsToMerge，标签2分配给它们。接下来，在步骤c)中考虑最后的扫描行，其中有一个运行。点17和点19有相邻的10和12，它们属于不同的集群，都适合传播它们的标签。根据我们的算法逻辑，这两个标签(即标签1)中最小的一个被继承。在步骤d)中，注意到两个标签1和2的合并，并相应地使用下面讨论的标签等价分解技术进行处理。

实现细节:算法的大纲很简单，但是为了实现高效，我们提出了以下解决方案:(i)如何创建运行，(ii)如何查找最近的邻居，(iii)如何在合并两个或多个连接组件时解决标签冲突。

1)扫描线第一次访问时创建一个运行作为一个indeces向量，并保存关于哪些连续点足够接近到扫描线中的单个块的信息。考虑到扫描线的圆形形式，一次运行可以跨越第一个和最后一个indeces。当检测到这种情况时，可以通过将扫描线末尾的indeces附加到第一次运行的indeces的开头来解决，如图3所示。

2)当输入点云表示在圆柱坐标点x = [rθz],然后索引的最近邻扫描线上可以看作是简单地比较θ值。然而，在自动驾驶汽车的应用中，集群是一个更大的传感器和算法系统的一个小组件，出于兼容性的原因，首选笛卡尔坐标系。在实现方面，最简单的解决方案是构建一个kdtree结构，其中包含上面扫描线中的所有非地面点，并使用它找到每个最近的邻居，从而得到一个次优但可行的解决方案，该解决方案可以进一步细化。

在扫描线上的点沿整条扫描线均匀分布的假设下，我们使用了一种智能索引方法来克服这个问题元素个数的不均匀性在不同的扫描线上，大大减少了查询最近邻的次数。假设每个扫描线都有N个i号每个点都有两个indeces;一个全局ind g表示它在整个点云中的位置，一个局部ind l表示扫描-中的点线。你可以很容易地在扫描线K的indeces之间切换:

图 4智能索引的例子;(a)当两条扫描线上的点有显著差异时(N外几乎是N内的两倍)，(b)由于传感器的噪声和物理限制，两条扫描线上的点都缺失时。

给定扫描线i中的一个带有局部索引indli的点索引，可以通过下式直接找到相邻的indlj在上述扫描线j中实际最近邻的近处的局部索引:

可从式3计算其全局索引。

根据扫描线内点的分布，索引可能并不表示最近的邻居，而是表示足够接近的点。在这种情况下，可能需要搜索通过它周围的一些点为最近邻，但这个数字远远小于考虑整个扫描线。

在运行过程中，识别潜在的邻居，并在其周围搜索最佳匹配结果，这会带来很大的开销，从而破坏算法的性能。考虑到这一点，建议的解决方案是通过智能索引找到运行的第一个点和最后一个点的最近邻居，用该范围内的所有非地面点形成一个kdtree结构，并用它搜索最近的邻居。

智能索引的两个可视化示例如图4所示。),虽然分在两个扫描线的数量是相当不同的,随机选择的点与局部indec 8, 16,26和32个外扫描线的最近的邻居表示点与局部indec 5、9、15和18分别在内心的扫描线。此外，在b)中，点的分布极不均匀，但智能索引仍然成功地指出了合适的邻居。这些情况是常见的前几个扫描线时，他们的一些激光束永远不会回来，因为吸收或非常高的距离。在很少的情况下，连续扫描线之间的点数有很大的不同，或者扫描线的很大一部分丢失了，智能索引很可能会失败。在这些情况下，将整个扫描线视为潜在的最近邻的朴素解仍然可以得到很好的结果。

在[13]中引入了解决标签合并冲突的方法，其中提供了实现和深入理解的所有细节。下面，给出了一个简单的例子，并简要介绍了其中的要点。

当需要合并两个或多个不同的已标记组件时，会出现标签合并冲突。根据He等人的[13]，解决方案是通过在相同的集合S中积累它们的标签l，并使用复杂的方法用三维一维数组捕获它们的层次结构和连接。这三个向量的大小都与第一次通过点云时创建的标签总数相同。第一个向量“next”的每一项都在它的S中存储下一个l，而S中最后一个l的项是-1。接下来，向量“tail”存储s的最后一个l的索引。最后一个向量“rtable”的辅助作用是报告任意给定时刻每个l的最终标签是什么。在第一次遍历结束时，rtable用作最终标记的查找表。

让我们从这三个向量的角度来看图2的例子。在第一步a)中，创建了两个标签(1和2)，并填充了l2项。这两个集合中的每一个都只有一个元素，因此下一个条目都是-1，尾条目显示了S中的最后一个元素的索引，这两个集合S的索引分别是1和2,rtable显示了最终的代表标签。接下来，在b)中，l3被创建，向量被填满，和之前一样。最后,S 1和2合并这意味着第一项下将指向下一个元素的索引1,尾巴年代1中元素是相同的和点集的最后一个元素的索引,并更新rtable正确描述最终的标签。

4.实验结论

为了测试所提出的管道，我们在KITTI数据集上进行了地面点提取和聚类的实验。我们提供了与在类似场景中使用的指示性算法的性能比较，显示了最终结果，并强调了我们提出的解决方案中的速度差异。该应用的参数校准非常直观，因为它主要反映了3D点之间的距离。在我们的实验中，GPF的参数设定为N segs = 3，N iter = 3，N LPR = 20，Th种子= 0.4m，Th dist = 0.2m。对于SLR，参数是Th run = 0.5m并且Th merge = 1m，而用于比较的欧几里德簇提取的半径设置为0.5m。

Ground Plane Fitting

将GPF与在类似场景中使用的RANSAC平面拟合实现进行了比较。三维点标记结果相似，我们的方法执行更快(图5a)。

图6为单平面拟合与多平面拟合结果的对比图。通过将初始点云分割成多个段，对每一段配以一个平面，就有可能纠正对地面点的错误标注。

Scan-Line Run

得到的集群可以在图7中黄色边框内看到。SLR算法充分利用了点云的结构，比传统的点云算法执行速度快得多以不规则的方式穿过点云的算法。如图5b所示，随着点数的增加，时间呈线性增长。相比之下,欧氏聚类提取(ECE)算法随着点数的增加呈指数级增长。需要搜索内部邻居的聚类算法整个数据集，其性能基于云的总点数。另一方面，对单反的搜索受到其运行大小的限制，并考虑到邻居只有在一个扫描线实现更好的性能。