基于平面拟合的方法-Ground Plane Fitting

算法思想：一种简单的处理方法就是沿着x方向（车头的方向）将空间分割成若干个子平面，然后对每个子平面使用地面平面拟合算法（GPF）从而得到能够处理陡坡的地面分割方法。该方法是在单帧点云中拟合全局平面，在点云数量较多时效果较好，点云稀疏时极易带来漏检和误检，比如16线激光雷达。

算法伪代码：

伪代码

算法流程是对于给定的点云 P ,分割的最终结果为两个点云集合，地面点云 和非地面点云。此算法有四个重要参数，如下：

Niter : 进行奇异值分解(SVD)的次数，也即进行优化拟合的次数

NLPR : 用于选取LPR的最低高度点的数量

Thseed : 用于选取种子点的阈值，当点云内的点的高度小于LPR的高度加上此阈值时，我们将该点加入种子点集

Thdist : 平面距离阈值，我们会计算点云中每一个点到我们拟合的平面的正交投影的距离，而这个平面距离阈值，就是用来判定点是否属于地面

种子点集的选择

我们首先选取一个种子点集(seed point set)，这些种子点来源于点云中高度（即z值）较小的点，种子点集被用于建立描述地面的初始平面模型，那么如何选取这个种子点集呢？我们引入最低点代表（Lowest Point Representative, LPR）的概念。LPR就是NLPR个最低高度点的平均值，LPR保证了平面拟合阶段不受测量噪声的影响。

种子点的选择

输入是一帧点云，这个点云内的点已经沿着z方向（即高度）做了排序，取 num_lpr_ 个最小点，求得高度平均值 lpr_height（即LPR），选取高度小于 lpr_height + th_seeds_的点作为种子点。

具体代码实现如下

平面模型

接下来我们建立一个平面模型，点云中的点到这个平面的正交投影距离小于阈值Thdist，则认为该点属于地面，否则属于非地面。采用一个简单的线性模型用于平面模型估计，如下：

ax+by+cz+d=0

即：

其中

,通过初始点集的协方差矩阵C来求解n，从而确定一个平面，种子点集作为初始点集，其协方差矩阵为

这个协方差矩阵 C 描述了种子点集的散布情况，其三个奇异向量可以通过奇异值分解（SVD）求得，这三个奇异向量描述了点集在三个主要方向的散布情况。由于是平面模型，垂直于平面的法向量 n 表示具有最小方差的方向，可以通过计算具有最小奇异值的奇异向量来求得。

那么在求得了 n 以后， d 可以通过代入种子点集的平均值 ,s(它代表属于地面的点) 直接求得。整个平面模型计算代码如下：

优化平面主循环

得到这个初始的平面模型以后，我们会计算点云中每一个点到该平面的正交投影的距离，即 points * normal_，并且将这个距离与设定的阈值(即th_dist_d_) 比较，当高度差小于此阈值，我们认为该点属于地面，当高度差大于此阈值，则为非地面点。经过分类以后的所有地面点被当作下一次迭代的种子点集，迭代优化。

基于雷达数据本身特点的方法-Ray Ground Filter

代码

https://github.com/suyunzzz/ray_filter_ground

算法思想

Ray Ground Filter算法的核心是以射线（Ray）的形式来组织点云。将点云的 (x, y, z)三维空间降到（x,y）平面来看，计算每一个点到车辆x正方向的平面夹角 θ, 对360度进行微分，分成若干等份，每一份的角度为0.2度。

激光线束等间隔划分示意图（通常以激光雷达角度分辨率划分）

同一角度范围内激光线束在水平面的投影以及在Z轴方向的高度折线示意图

为了方便对同一角度的线束进行处理，要将原来直角坐标系的点云转换成柱坐标描述的点云数据结构。对同一夹角的线束上的点按照半径的大小进行排序，通过前后两点的坡度是否大于我们事先设定的坡度阈值，从而判断点是否为地面点。

线激光线束纵截面与俯视示意图（n=4）

通过如下公式转换成柱坐标的形式：

转换成柱坐标的公式

radius表示点到lidar的水平距离(半径)，theta是点相对于车头正方向(即x方向)的夹角。对点云进行水平角度微分之后，可得到1800条射线，将这些射线中的点按照距离的远近进行排序。通过两个坡度阈值以及当前点的半径求得高度阈值，通过判断当前点的高度（即点的z值）是否在地面加减高度阈值范围内来判断当前点是为地面。

伪代码

伪代码

local_max_slope_ ：设定的同条射线上邻近两点的坡度阈值。

general_max_slope_ ：整个地面的坡度阈值

遍历1800条射线，对于每一条射线进行如下操作：

1.计算当前点和上一个点的水平距离pointdistance

2.根据local_max_slope_和pointdistance计算当前的坡度差阈值height_threshold

3.根据general_max_slope_和当前点的水平距离计算整个地面的高度差阈值general_height_threshold

4.若当前点的z坐标小于前一个点的z坐标加height_threshold并大于前一个点的z坐标减去height_threshold：

5.若当前点z坐标小于雷达安装高度减去general_height_threshold并且大于相加，认为是地面点

6.否则：是非地面点。

7.若pointdistance满足阈值并且前点的z坐标小于雷达安装高度减去height_threshold并大于雷达安装高度加上height_threshold，认为是地面点。

基于雷达数据本身特点的方法-urban road filter

原文

Real-Time LIDAR-based Urban Road and Sidewalk Detection for Autonomous Vehicles

代码

https://github.com/jkk-research/urban_road_filter

z_zero_method

z_zero_method

首先将数据组织成[channels][thetas]

对于每一条线，对角度进行排序

以当前点p为中心，向左选k个点，向右选k个点

分别计算左边及右边k个点与当前点在x和y方向差值的均值

同时计算左边及右边k个点的最大z值max1及max2

根据余弦定理求解余弦角

如果余弦角度满足阈值且max1减去p.z满足阈值或max2减去p.z满足阈值且max2-max1满足阈值，认为此点为障碍物，否则就认为是地面点。

x_zero_method

X-zero和Z-zero方法可以找到避开测量的X和Z分量的人行道，X-zero和Z-zero方法都考虑了体素的通道数，因此激光雷达必须与路面平面不平行，这是上述两种算法以及整个城市道路滤波方法的已知局限性。X-zero方法去除了X方向的值，使用柱坐标代替。

x_zero_method

首先将数据组织成[channels][thetas]

对于每一条线，对角度进行排序

以当前点p为中心，向右选第k/2个点p1和第k个点p2

分别计算p及p1、p1及p2、p及p2间z方向的距离

根据余弦定理求解余弦角

如果余弦角度满足阈值且p1.z-p.z满足阈值或p1.z-p2.z满足阈值且p.z-p2.z满足阈值，认为此点为障碍物

star_search_method

该方法将点云划分为矩形段，这些形状的组合像一颗星；这就是名字的来源，从每个路段提取可能的人行道起点，其中创建的算法对基于Z坐标的高度变化不敏感，这意味着在实践中，即使当激光雷达相对于路面平面倾斜时，该算法也会表现良好，在柱坐标系中处理点云。

具体实现：

star_search_method

参考文献

1.https://blog.csdn.net/AdamShan/article/details/84569000

2.https://zhuanlan.zhihu.com/p/553575548