描述

点云地面分割算法——Patchwork的论文分析
该论文是ICRA2021年的一篇文章，比较新，效果不错，在这里进行介绍
论文全称：Patchwork: Concentric Zone-based Region-wise Ground Segmentation with Ground Likelihood Estimation Using a 3D LiDAR Sensor

简述

Patchwork 主要由三部分组成：基于同心带模型（CZM）的极坐标网格表示、区域地平面拟合（R-GPF）和地面似然估计（GLE）。

• A: 所有点，需要被划分成了 地面点 和 非地面点

• B：极坐标对点云进行分区，类似于gridmap，但是距离原点越近区域面积越小，文章也给出了分区的公式，利用min和max值

• C: 每个区域找地面，然后地面再拼接在一起，用到了PCA

  Nz就是1-4，整个数据分成了4个区域Z1-Z4，每个bin叫做 Sn

  m代表区域id，每个点就是pk。

  每个区域利用z值进行“生长”，然后得到地面点集

  在最靠近车的Z1，利用传感器高度来决定初始点，越离车远，传感器高度值要乘以一个系数，保证考虑到下坡的情况

• D: 通过垂直度、高度、平整度三个特征，来进行二分类，使得所有的bin集合成整个路面

以上就是我的简单说明，具体的我们来往下看

Abstract

地面分割是地面移动平台进行导航或相邻物体识别的关键。不幸的是，地面并不平坦，因为它具有陡峭的斜坡；崎岖不平的道路；或物体，如路缘石、花坛等。为了解决这个问题，本文提出了一种新的地面分割方法，称为Patchwork，该方法对解决欠分割问题具有鲁棒性，并且工作频率超过40Hz。在本文中，将点云编码到基于同心区域模型的表示中，以一种计算简单的方式为bin分配合适的点云密度。然后在区域内进行平面拟合，来估计每个bin的地面。最后，引入地面似然估计以显著减少误报。实现结果在SemanticKITTI和粗糙地形数据集上进行了验证，与最先进的方法相比，我们提出的方法具有良好的性能，与现有的基于平面拟合的方法相比，速度更快。

METHODOLOGY OF PATCHWORK

A. Problem Definition

对估计地面这一问题,做出了数学定义,

全部的点云表示为P，P的表示如下

N代表点云总的数据量，第k个点表示为 p_k = (x_k, y_k,z_k )

在这篇文章中，P被分为了两类，地面点集和非地面点集。其中非地面点集包括车辆、墙壁、街道树 、行人等。它们用如下公式表示：

4个大写字母定义都是很常见的：TP正确接受，FP错误接受，FN错误拒绝，TN正确拒绝。我们估计出的地面点集合是Ĝ，是真实地面，和错误认为是地面点的集合；估计出的非地面点集合是Ĝ^c，是真实非地面点，和错误认为是非地面点的集合。

B. Concentric Zone Model

对之前的同心区划分方式（LineFit算法、R-GPF算法采用的方式），进行了非常合理的改进：靠里的环面积小，靠外的环面积大

大多数基于多平面的方法都基于假设：可观测世界可能不是平坦的。因此，不应该直接估计地面，而是通过假设非平坦世界有小块或bins，并且地面在该区域内确实可以是平坦的。以前的一些方法利用统一的极坐标网格表示扇区，再将扇区S划分为具有规则间隔的径向和方位角方向的多个bin，即环和扇区 。更具体地说，让 N_r 和 N_θ 分别是环和扇区的数量。然后，每个扇区 S 被划分为相同大小的扇环bin。其径向大小为 L_{MAX} / N_r，其中L_{MAX} 表示最大边界长，扇区方位角大小为 2 \pi/ N_θ。下图是传统划分方法与我们提出方法的区别。

如图所示，为了考虑泛化，在 SemanticKITTI 数据集上的整个序列上测量的实验证据表明，大多数地面点都位于靠近传感器的位置，即90%以上属于地面的点位于20m以内。

因此之间的划分方式有两个不足。首先，随着距离越来越远，点云变得太稀疏而无法找到正确的地平面，我们称之为稀疏问题。有一些方法自适应地调整 bin 的大小以应对数据点呈对数分布的情况（分析：对数分布代表数据越远越稀）。但是，bin 的个数会以线性或二次方式增加，因此稀疏问题并未完全解决（分析：说的有点牵强）。另一方面，当靠近原点的 bin 的太小而无法表示扇区中的单位空间时，有时会导致地平面的法向量估计失败，我们称之为代表性问题。

为了解决这些问题，本文提出了基于 CZM 的极坐标网格表示，以一种不增加计算复杂度的方式在 bin 之间分配适当的密度。因此，全部点集P被分成多个区域，每个区域由不同面积大小的bin组成，如图所示。文章提出的模型定义如下：

Z_m代表第m个区域，N_z代表区域的个数（分析：区域就是之前说的面积不同的区域，图中用四种颜色标识了）。根据经验，N_z被设置为了4（如图所示，4个颜色代表4种区域）。Z_m的表示如下：

（分析：下面就是每个区域的计算过程了，感兴趣的可以继续阅读，我这里用一句话来解释下面的那些公式。文章的参数设置，就是将全部的区域做了4次二分法，如下图）

其中 L_{min,m}和L_{max,m}分别表示 Z_m 的最小和最大径向边界； 然后， Z_m 也被划分为 N_{r,m} × N_{θ,m} 个 bin，其中每个区域具有不同的 bin 大小。 因此，代表每个 bin的变量S_{i,j,m} 定义如下

Z_1、Z_2、Z_3和 Z_4分别称为中心区、四分之一区、半区和外区。

请注意，Z1 和 Z4 中的 bin 大小设置得更大，以解决稀疏性问题和可表示性问题。 因此，与现有的分区方法相比，本方法提高了可表达性，从而允许对法线向量进行稳健估计，从而防止分割不足。 此外，它还减少了实际的 bin 数量，例如，从之前分割的 3240 个（LineFit和R-GPF）到现在的 504 个，从而能够以超过 40 Hz 的频率运行

C. Region-wise Ground Plane Fitting

每个 bin 通过提出的 R-GPF 来估计局部地面， 随后将这些局部地面点合并

每个区域的点进行PCA分析，取出第三个特征代表高度方向的特征（显而易见前两个是 x 和 y ）。

在本文中，使用主成分分析 (PCA) 而不是使用 RANSAC。 当然，与 PCA 相比，RANSAC 对异常值的敏感性往往较低。 然而，使用 PCA 的速度比使用 RANSAC 快得多，并且表现出可接受的性能； 因此，基于 PCA 的估计更适合作为预处理过程。 此外，实验表明基于 PCA 的方法至少比基于 RANSAC 的方法快两倍。

每个bin中的数据点集合都被命名为S_n ，bin的总个数是 N_c

其实就是总个数 = 对区域求和（每一个区域有多少个bin * 有多少个角度分区）。如果bin的个数很多（分析：意味着整个点云已经在xy平面分的已经很细了），最低高度的点会被选作种子点。事实上是因为，每个bin中高度最低的点是最有可能属于地面的。令 z_{init} 为 选择的总数为 N_{seed}的种子点的平均值。那么初始的地面估计如下所示：

z(.)返回的是点的高度值，z_{seed} 代表的是高度阈值。第一次估计的地面点，是z高度不大于 平均值z_{init}+阈值z_{seed}的点集

我们的方法是需要迭代的，因此我们令第 l 次迭代出的地面点是 G_n^l，第l 次迭代地面点的法向量是 n_n^l。下一步就是，地面系数表示是d_n^l ，它是由如下公式计算的。

p_n^l是第l次迭代时，所有被分类为地面的点的平均值。

使该次地面估计的平均点与法向量进行点乘，能够反映两向量之间的投影值

第l+1次地面点估计的迭代公式如下

之中 第k个数据点的参数 d_k 表示为：

M_d 是点到地面设置的距离阈值（实际上就是设置了一个阈值来决定： 一个点是否会在这次迭代过程中被分为地面点）。文章中说，迭代3次是一个比较好的结果。

我们的方法与之前的R-GPF（作者之前的文章）有了改进。由于多路径及雷达信号反射的问题（激光在经过例如车顶的地方发生反射，该束光线方向不变，值变大了），会出现数据点在实际地面的下方。这种情况更多发生在距离最近的区域Z1中，因为反射更多发生在信号较强的区域。我们如果将这些点作为初始点，地面估计会错误。如图是在KITTI数据集上的测试结果。

绿色代表TP、蓝色代表FN，红色代表FP。显然蓝色FN错误拒绝的点，越少越好。

文章的解决思路是：利用区域Z1中的地面点主要分布在 -h_s 附近这一事实，h_s代表雷达高度。如果点比M_h*h_s低时，不认为这些点是地面点，参数 M_h 是一个系数。参数 M_h 是随着距离增大而减小（可以理解为放宽高度差的限制），这样一些下坡点就不会被错误过滤了。

D. Ground Likelihood Estimation地面似然估计

综合考虑三个方向的概率，求一个概率之积得到每个bin是否为地面点的总概率

为了更鲁棒的判断G_n是否属于实际地面，提出了 GLE，这是一种用于二分类的区域概率测试。Patchwork 利用 GLE 来提高整体精度，不包括由非地面点组成的初始非预期平面。
地面点估计 L(\theta|X) 是从 垂直度、高度、平整度这3个角度去定义的，分别是 \phi(.),\psi(.),\varphi(.)，如下图

三者的乘积将决定，这个bin是否为地面。

垂直度

利用每个平面提取出的PCA中的第三维特征向量v3，进行判断，为了得到平的地面

公式

公式解释
z代表[0,0,1] ，\theta_{\tau}代表垂直度阈值。公式中if计算的值实际上计算的就是法向量与90度的角度差。\theta_{\tau}设置的越接近90度，意味着(\pi/2 - \theta_{\tau})越接近于0，条件越严格，意味着平面法向量的角度需要严格垂直向上。实验中，这个值被设置为了45度

高度

利用每个平面的平均高度值，进行判断，为了滤除近处的非地面情况

如果大型车辆靠近传感器时，会发生遮挡，产生局部观察的情况。这时被遮挡空间上方的数据点被认为是地面，但事实上这些点并不是最低的部分。为了解决这个问题，提出了如下公式。核心思路就是：一旦传感器框架附近的z_n 与 -h_s 之比很高，G_n 可能不是地面。

公式

公式解释

κ(⋅) 表示根据 r_n 呈指数增长的自适应中点函数（上一节提到的M_h，但具体计算我没理解）

r_n 距离超过固定阈值参数L_{\tau} （距离传感器很远了），这个公式的计算值为1（这个公式算是没有输出结果，可以理解该公式对结果不予置评，由垂直度和平整度来决定判别结果），因为我们也不知道这个bin是地非地面啊还是一个上坡。

另一种情况是如果距离在L_{\tau} 范围内，意味着现在距离传感器很近了。如果这个bin的平均z值z_n ，大于κ(r_n)，那么计算出来的值就会小于0.5，这个差值越大，计算出来的值就会越倾向于0，意味着这个bin越不可能是地面。相反，如果小于κ(r_n)，计算出来的值就会是大于0.5的，意味着它可能是地面点的概率更高。（不要去和上一种情况的1去比较，因为1意味着根本没起作用，只有这个公式的结果输出如0.4或0.6，才是对判断地面起到了作用）

平整度

利用之前的高度判断结果，进行判断，为了增加上坡地面

如果是一个陡峭的上坡，平均z值如果大于κ(r_n)，有可能这个bin就会被高度公式过滤掉，认为是非地面（可以想象一下你要开出地下车库上坡时）。但这是错误的。

公式

公式理解

如果高度公式认为它是大于0.5的，这个公式的值为1，不起作用。如果高度公式结果是小于0.5的（如果这时是上坡，我们需要一个值来扭转高度公式的结果），我们来计算平整度与阈值的关系。\sigma_{n}代表当前bin的平整度，\sigma_{\tau}代表我们设置的阈值。如公式所示，平整度小于阈值时，公式结果肯定会大于1，来降低高度公式的影响。如果平整度大于阈值，加上一个大于1 的系数 \zeta，会得到一个结果（这个结果会受参数\zeta影响，但我理解参数\zeta的选择，是绝对不可以抵消高度公式小于0.5的那个值的，否则高度公式和平整度公式共同存在的意义就不大了）。

综上三个公式的结果，乘积大于0.5的bin，被认为是地面。这些bin的集合就是最后的地面。其中 [·] 表示 Iverson 括号，如果条件满足则返回 true，否则返回 false。

IV. EXPERIMENTS

A Dataset

使用了两个数据集，一个是KITTI，一个是自采数据集

B. Error Metrics

评价公式很常见

C. Parameters of Patchwork

参数使用

V. RESULTS AND D ISCUSSION

A. Performance Analysis with Different Bin Sizes

bin的划分对结果的影响

B. Impact of Uprightness

垂直度公式的结果就很好了，阈值\theta_{\tau}根据实验结果选择了45度。（很无语，其他两个公式写了这么多然后说没啥用。当然了，事实上还是有用的，因为数据集并不能表示所有的情况，高度和平整度的考虑有助于提升路面检测鲁棒性。也许我们可以通过一些数据来验证）

C. Effectiveness of Ground Likelihood Estimation

我们的 GLE 成功过滤掉了错误估计的部分地面，从而显着减少了 FN。特别是，许多墙壁和停放的汽车分别被垂直度和高度过滤器拒绝了。

D. Comparison with State-of-the-Art Methods

与其他方法的比较，挺重要的

Patchwork 与最先进的方法进行了定量比较，即 RANSAC、LineFit、GPF和 CascadedSeg。我们利用开源实现进行实验。

下图是所有方法的地面估计。

其他方法在非平面区域遇到困难，包括陡坡、复杂的交叉路口以及存在许多路缘石的区域。LineFit 在遇到起伏地形或灌木丛区域时可能很敏感，有许多FN。GPF 和 CascadeSeg 中的一些 bin 有时会趋向于收敛到局部最小值，因为 bin 设置的面积比较大，因此假设 bin 内的地面是平面并不安全，尤其是在崎岖不平的地形上。同时，从图中看出，Patchwork 的 FN 数量比 LinFit、GPF 和 CascadedSeg 的数量要多，但实际上这些是某些对象的最低部分。这意味着，我们的FN值虽然降低了定量指标的性能，但实际上更有助于解决细分不足。（意思就是说，我FN虽然多，但我结果就是好）

U、E 和 F 分别表示垂直度、高度和平面度

其他方法在 SemanticKITTI 数据集上显示出很大的召回方差。Patchwork召回率比较低，证明了我们的方法克服了分割不足的问题，因此对城市环境中的这些极端情况具有鲁棒性。

E. Algorithm speed

算法这一点我比较关注，多介绍一点

实验配置: Intel® Core™ i7-7700K CPU。

显示了各种基于多平面拟合的方法中最快的速度，如下表所示。Patchwork 比 R-GPF 更快。这是因为Patchwork的CZM减少了bin的数量，所以平面拟合的量也减少了；例如，Patchwork 使用 504 个 bin，而 R-GPF 使用 3,240 个 bin。此外，Patchwork基于 PCA，因此它也比 CascadedSeg 更快，CascadedSeg 是一种基于 RANSAC 的方法。因此，该结果表明Patchwork方法不仅鲁棒，而且速度足够快，可用于预处理。

VI. CONCLUSION

提出了Patchwork，效果不错。

总结

Patchwork的实验真的做的不错，挺全的。数据集不仅包含了KITTI，还有自采数据；不仅比较了分割结果，还定量的给出了结果；比较难得的是它还对比了不同算法的速度。
这个方法提出的也比较新，虽然速度比我之前分析的LineFit算法要慢一些，但地面判别结果要更优，我要考虑一下了。

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