Efficient Online Segmentation for Sparse 3D Laser Scans

描述

本文来分析另外一篇点云分割的算法
原文：Efficient Online Segmentation for Sparse 3D Laser Scans

算法中分为两步，第一步是点云地面分割，第二步是对除去地面后的点进行分割。和之前一样，我们还是先只介绍地面分割的部分，之后有时间再来填坑。

算法

构建一个范围图像（range image），图像的行数是激光雷达的线数（例如Velodyne的16、32、64线），列数是360°范围内旋转的激光点数。这样一个虚拟图像，每个像素点存储的是传感器到物体的距离值。

如果使用其他的激光传感器，提供的是3D的点云而不是原始测量数据（数据格式是xyz，而不是距离值和方向），可以将点云投影在圆柱图像上，计算每个像素的欧式距离，就可以继续使用我们的方法了。这样的计算会增加2倍，但是仍然满足快速分割的时间要求。

为了确定地平面，文中做了三个假设：

1.假设传感器相对于移动底盘或者机器人，是水平安装的。

2.假设地面曲率很低。

3.假设机器人至少在图像最下面一行的一些像素（即， 激光扫描到靠近机器人最近的地面），观察到了地平面。

基于以上的假设，我们把range图像的每列的像素值，变成一个堆栈。堆栈中的每个数都代表连接A和B两点的直线的倾斜角。这个倾斜角如图所示。

倾斜角的计算公式如下：

分析：经过以上操作，range图像实际上转化为了一个大小为激光一圈扫描个数的堆栈，每个堆栈的大小是线束个数-1。

range图像进一步计算得到的这个倾斜角的堆栈，写成一个矩阵形式

不幸的是，像Velody HDL-64这种激光传感器，存在一定的异常值，这些异常值需要被剔除。文中提到了参考文献WEINMANN&JUTZI等人利用像素的局部邻域特征来做滤波，作者认为这种办法虽然会过滤掉噪点，但也会过滤掉对分割很关键的一些边缘信息。作者采用的是Savitsky-Golay滤波器，该滤波器在滤波窗口内，利用最小二乘法的原理，对数据做多项式拟合。

分析：如上图所示。左上第一张图就是得到的range图像，第二张图片就是我们计算出的代表倾斜角的图像，第三张就是做了滤波后的图像。

对矩阵M_{\alpha}做完滤波后，从预期属于地面的点开始，做广度优先搜索（BFS）。广度优先搜索是一种流行的图搜索和遍历算法，从图的一个节点开始，首先搜索同层相邻节点，再搜索下一层节点。作者的方法是，矩阵中每个点代表的角度值\alpha，在它的4-邻域内的角度差大小，来决定是否分为一类。作者选择了一个0.5°的阈值\triangle{\alpha}

如果矩阵最低行的角度值小于设定阈值（作者实验中采用的是45°），则这些点会被标记为了地面点。这样，几乎垂直的结构如墙等，是不会被认为是地面的。最低一行中被标记为地面的，其列下标的集合被设为G，

每个点\alpha_{0,c}^1，都在矩阵上去进行BFS（广度优先搜索），当我们处理完集合G中的全部点c\in{G}后，图像中所有的像素点就都被标记完了。算法框图如下：

下图是一个点云示例，标记出的地面用浅蓝色表示。

总结

显然，这种方法与之前的点云分区思路不同。相较而言，这种算法将点云映射到了二维图像上，这在物理上一定意义上代表着激光传感器的FOV。事实上，如果了解过激光与视觉融合的算法可以知道，有一些研究也是将激光投射到了图像上，如我之前介绍过的算法PLARD。

但是显而易见的，我觉得这种方法牺牲掉了很多点云原有信息。同时，对于非文章提到的Velodyne传感器，在点云数据几十万大小的情况下，投射到图像上再去计算并不划算。文中也说了该方法无法处理有坡度的地面，因此该方法实用性就受到了很大的限制。

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