点云地面分割算法——Fast Segmentation of 3D Point Clouds for Ground Vehicles文章解析（一）

描述

《Fast Segmentation of 3D Point Clouds for Ground Vehicles》是美国加州大学圣地亚哥分校发表在2010 IEEE Intelligent Vehicles Symposium会议上的一篇文章。

文章提出的方法，可以用于点云中的地面点。本文主要参照原文，对这篇文章进行逐行翻译与分析。我的理解，会通过（分析：）来给出。

源码链接：https://github.com/lorenwel/linefit_ground_segmentation

原文解析

Abstract

本文提出了一种针对大尺寸长距离三维点云的快速分割方法，之后要继续进行对象分类的情况尤其适合该方法。我们的方法目标是实现自主地面机器人的高速移动，因此分割方法的实时性是很关键的。当分割被认为只是更重要的目标分类任务的一个必要的初步步骤，而目标分类本身的计算要求非常高时，这一点尤为正确。我们的方法通过将分割问题分解为两个复杂度较低的简单子问题来实现效率：对2D连通分支快速打标签，完成局部地平面估计。

我们在不同室外场景中采集的真实数据上，评估了该方法的性能，并将结果与现有方法进行了比较。我们表明，我们的方法需要更少的运行时间，同时产生的分割结果更适合于识别对象的后续分类。

分析：简单介绍了一下他们的方法：先将区域打label，再对每个区域进行地面估计。表明他们方法优势是运行时间短

Introduction

跳过。感兴趣自己阅读

跳过。事实上有很多核心的相关工作，我都会单独写文章来分析

Fast 3D Point Cloud Segmentation

分析：在真正详细说明前，我一句话来概况该方法吧
把所有点云按极坐标划分区域，每个区域再根据远近划分小块。每个小块中的雷达点都降维成（距离，高度），再拟合直线

相较于点云分割普遍方法去建立复杂的邻域关系并提取复杂的点云特征，我们使用了一种方法去分割数据并利用简单的直线拟合来估计地面平面。分割数据和直线拟合两步合在一起，实际上可以被认为是一种2D的range数据拓展到3D点云数据的一种线段提取算法。只不过特别的是，拟合出的直线要进一步为地面点识别而服务。已被分类为非地面的点，会被映射到xy平面上的高分辨率的grid中，并在这个grid中进行快速的连通算法。

接下来，我们会从获取数据、对数据进行预处理解释该方法，之后也会说明如何进行地面估计的。我们最终会展示，我们如何将非地面点分割成子集，并为之后的目标分类获取一个适合的分割结果。

A. Data Acquisition And Preprocessing

分析：再正常不过的点云数据定义了

雷达点云数据是384个角度，经由百兆网以2.5KHz来得到的。在所有步骤之前，我们需要对雷达进行内参标定，并进行运动补偿。

雷达在时间t时的数据为 :

每个点的数据为：

他们都是在车体坐标系（以车重心为中心的坐标系）下的

B. Local Ground Plane Estimation

室外场景中的大范围点云数据分割的第一步，就是建立一个针对所有点的二值化标签，区分它们是地面点和非地面点。由于我们的目标是室外场景，因此我们要考虑到不平地面、倾斜地面以及它们之间的过渡部分。为捕获到这些过渡部分，局部地面的预测需要被考虑。这就需要我们把无序的点云有序化。常见的做法有使用特殊的传感器参数或者构建KD-Tree。前者不通用，后者没法实时使用（分析：KD-Tree每帧你都要构建啊）

本文提出了一个xy平面下、半径无限的圆。我们把圆分为M个Segmentation，每个Segmentation的角度差为 {\Delta\alpha}。那么每个点所属的区域id就可以表示成：

{atan2(y, x)}代表数据点到x轴正方向的夹角。点的角度范围为[0, {2\pi})，每个区域中的点的集合{P_s}可以表示为：


这么操作之后点依旧是三维的，我们依旧没法使用快速的2D直线提取。

因此进一步的，将一个区域{P_s}中的点分到若干个bin中。每个segmentation分为B份，每个bin被命名为{b_j^s}。我们需要设置两个数：bin范围的最小距离{r_j^{min}}，和最大距离{r_j^{max}}。当然了，所有的点距离中心的距离，都会在这最小值与最大值中间。因此在 {b_j^s}中的点集被命名为 {P_{b_j^s}}。每个segmentation都使用相同的bin划分，不同的分区中会有bin具有相同的range。

一旦每个点被分到一个区域和一个bin，点需要被降维成2D。降维后的点的表示方式如下：

分析：相当于只保留距离和高度信息，结合论文截图很好理解，结果是每个bin中的点都简化成了一条折线

现在点按照range大小已经是有序的了。显然一个bin可能不止一个点，也有可能没有点。因为我们只计算非空的bin，将之中的点降维得到新的2D点集 {P’_{b_j^s}}。计算每个原型点 {p’_{b_j^s}}的方式有几种，比如点取平均值。我们发现使用最小z值的点会有更好的效果，因为它更有可能在地面上

分析：每个bin的全部点，计算出一个“原型点”，论文中使用的是最小z值点

总而言之，原型点是为了之后的直线拟合，进行的原始3D点云的合理降维。更重要的是，地面平面估计的计算复杂度，将不取决于点云大小，而是取决于角度差{\Delta\alpha}和bin数B了。因此在实时算法中，这种方法具备灵活性（分析：改变参数来改变计算复杂度）

接下来地面拟合就是需要对原型点进行直线提取了。我们可以直接采用“增量算法”，因为它简单且有效。我们只需要拟合出公式{y = mx + b}，就可以表示局部地面了。

  • 直线的斜率m不能超过一个确定的阈值{T_m}，例如地面不可能是垂直的

  • 对于一个小于斜率极小阈值 {T_{m_{small}}}的直线，它的偏移{b}不能超过一个阈值{T_b}，因为这样拟合出的平面就不在地面上了

  • 使用的是均方误差，不能超过阈值{T_{RMSE}}

  • 一条直线的起始点，距离上一条拟合出来的直线的距离，不能超过阈值{T_{d_{prev}}}，确保两条成功直线之间是平滑的过渡

算法1展示了如何提取地面直线X的方法。在第5-9行我们使用了常用的总体方差（TLS）作为拟合损失。

一个分区会被一系列的直线表示后，我们也许可以判断点是否属于地面了。对于每个分区，我们从线段的端点中找到距离每个点最近距离的两个端点。点到直线距离很大时，意味着最近的线段也与这个点距离很远，因此在这个点的下面不能给出一个合理的地面估计。这种情况下，我们会采取保守的态度来标记这个点不是地面点。否则，我们会评价点到线段的距离，如果低于阈值X时，认为这个点不是地面点。

C. Segmentation of Non-Ground Points

当我们在一帧雷达中对点都打完了标签，最后一步就是将靠近在一起，而非地面的点进行分类了。在实验中，可以使用简单的3D信息进行分类。我们因此采用上述提到的grid技术，并利用计算机视觉已知的快速连通域，应用到2D栅格地图结构上。

在参考文献1中的，所有的非地面点被映射到栅格地图上。然后，通过查找存储在已占用网格单元的连通域上的三维点，来找到点云中的单个对象。请注意，尽管这依赖于中间降维，但我们的方法中不存在占用网格常见的欠分割问题。 这是因为在上一步中，非地面点已经与地面点分离，并且只能基于非地面点确定单元占用率。此外，由于单个非地面点已经渲染了已占用的单元，因此可以在更大范围内检测对象。

分析：上一个B步骤已经将地面和非地面点区分开了，这一节说的就是一些参考文献方法，对于非地面点进行的分割操作

D. 3D Voxel Grid Segmentation

尽管如此，如果一个非地面物体被放置在另一个非土地物体的下方，例如一辆汽车在一棵树下，那么到目前为止所描述的方法将导致欠分割，将汽车和树分配到同一聚类。因此，我们需要检测这种罕见的情况，并通过在3D中（例如在体素网格中）执行最终分割来优化分割结果。然而，简单地将最终3D分割应用于所有分割是不合适的，因为这将违反实时性要求。因此，我们需要检测需要哪些voxel需要被特殊3D处理，以避免处理所有的voxel。幸运的是，我们仍然知道线段的哪些点映射到单个网格单元。因此，为了决定哪个分区需要在3D中处理，我们建议检查一个分割对象{O_i}中每个单元格{c \in C_i}中的z值差异。令{P_c^{O_i}}代表对象{O_i}中的非地面点，映射到{c \in C_i}后的点集。我们建议满足如下关系的voxel，需要被进一步分割

意思就是说，如果在分割对象{O_i}的几个cell {c}上，z坐标中的任意两点之间存在较大的间隙，而没有第三个点落入该间隙中，则我们需要对点执行3D分割。3D体素网格分割方法，与上述的2D占用网格分割类似。最终分割结果采用的参数是N_{3D}= 2（竖直方向再分2类）和T_{3D}= 0.4（竖直方向z阈值）情况下，结果如下图所示。

总结

这篇文章对Fast Segmentation of 3D Point Clouds for Ground Vehicles的前半部分主要内容进行了解析。

下一篇将对这篇文章的实验结果进行阐述，同时对直线拟合算法进一步分析。另外会结合源码给出理解。

写的不容易，欢迎各位朋友点赞并加关注，谢谢！