描述

这个韩国团队真的挺厉害的，在2017年别人提出的GPF算法（已分析）基础上，持续输出。2021年在RAL发表了两篇文章：一篇R-GPF算法（我还没分析），另外一篇是Patchwork（已分析）。今年刚刚刚，也就是2022年7月份又中了一篇IROS，也就是这篇文章：Patchwork++，主要改进了之前提出的Patchwork。

论文思想挺不错的，我来解析一下（同时，定个小目标，年底争取超越他哈哈，希望能实现）

论文：Patchwork++: Fast and Robust Ground Segmentation Solving Partial Under-Segmentation Using 3D Point Cloud
源码链接：https://github.com/url-kaist/patchwork-plusplus

对这种敢开源的，真的是点赞。

Abstract

在使用3D激光雷达的3D感知领域，对于可行驶区域检测及物体识别等各种操作，地面分割都是一项基本任务。地面分割方法有很多，然后都有一些局限性。首先，一些方法需要调参，费时费力。其次，即使参数调整好后，在一些区域出现欠分割，意味着分割失败。最后，当地面在另外一个结构上方时（例如路沿），无法分割出合适的地面。为了解决这些问题，我们提出了一种鲁棒的地面分割算法，叫做Patchwork++，它是Patchwork的升级。Patchwork++基于之前的地面分割结果，利用了自适应地面似然估计（A-GLE）计算合适的参数。此外，临时地面恢复（TGR）利用临时路面属性，可以解决部分的欠分割问题。同时，引入了区域性的垂直平面拟合（R-VPF）来正确分割即使处在不同高度的地面。最后我们提出了基于3D激光雷达反射模型的反射噪声去除（RNR）方法，可以有效的消除虚拟的噪声点。我们使用了SemanticKITTI数据集来做定性和定量的评估。

相对于Patchwork提出了4个新概念：A-GLE、TGR、R-VPF、RNR，理解它们是这篇论文的关键

I. INTRODUCTION

这节简单过一下，主要是讲清楚一些问题

  • 地面分割是一种基本任务。

  • 基于学习的3D感知存在两个弊端：需要人工标注、训练集和传感器不同时性能有变化。我们专注于非学习的地面分割。

  • 通常来说，地面分割只是第一阶段的任务，而分割后的非地面点可以划分为动态点和静态点。地面点则都是静态点。

  • 地面分割算法需要满足三个特性：1. 速度快，2. 保证精度和召回率，3. 能够应对不平坦地面

  • 一些提出的方法无法满足这些要求，如图所示。我们之前的工作Patchwork能满足这些要求，但偶尔会出现图1(c)中显示的欠分割问题。欠分割问题的原因有两个：一是有些地面分割方法是确定性的；二是最低z值的点被认为是地面，这个假设可能不对。

图1显示了RANSAC和Patchwork的问题。（a）图显示了点云数据存在高度变化。RANSAC利用单一平面分割会错误，而Patchwork由于参数是固定的，也存在一些数据点没有被分割成地面。相比之下新的Patchwork++成功分割了

  • 因此我们提出了Patchwork来解决这些问题，贡献有三个：

  1. A-GLE和TGR减少了FN

  2. R-VPF和RNR剔除了噪声点，以防假设不成立

  3. SemanticKITTI数据集上的实验结果很好

II. RELATED WORKS

不介绍了

III. PATCHWORK ++: FAST , ROBUST , AND ADAPTIVE GROUND SEGMENTATION（Patchwork++：快速鲁棒自适应的分割）

相较于Patchwork，Patchwork++主要是4个部分：A-GLE、TGR、R-VPF、RNR

关于变化作者给了一个图，很清晰

A. Problem Definition

和Patchwork一样；对地面分割做出数学定义

所有点被分割为了地面点和非地面点，这篇文章还增加了真值的概念。四个元素分别进行交集，就是TP、FP、FN和TN。研究的目标就是，最大化TP，最小化FN和FP。

G是真值地面，N是真值非地面，Ĝ是估计的地面，N̂是估计的非地面，P是全部的数据点。

B. RNR: Reflected Noise Removal（反射噪声去除）

去除反射噪声：去除了距离传感器较近距离的、高度小于某个阈值、强度小于某个阈值的数据点，这些数据点被认为是噪声点

新增参数： 高度阈值h_{noise}（A-GLE中自动更新）、强度阈值I_{noise}（人为设定）

原始点云中，实际地面之下偶尔会有噪声点，下图是噪声点产生的原因。R-GPF算法会选取最低点作为初始点，选到这些噪声点时就会出现欠分割了(真实地面没找到，也就是FN错误拒绝)。

为了解决这个问题，一般是采用拒绝选到z值小于某个阈值的方式。但这种方式是假设地面是平的。当地面是向下的陡坡时，如下图，这种去噪方式就会去除真实地面点。

图（a）中红色的点代表z值比较低。图（b）基于高度去掉了这些点，导致了Patchwork产生了欠分割，如图（c）所示。图（d）是Patchwork++ 的效果，解决了这个问题

因此我们要区分真实地面点和噪声点，只用z值是不行的。文献[25]提出了RNR：

1.虚拟的噪声点，是由于发射得到的，例如汽车发动机罩或者玻璃，如图3所示。入射角越小，得到的噪声越低。因此我们假设，噪声点来源于激光雷达靠下线束的光（入射角更小）。

2.噪声点强度值小。额外的反射会使得虚拟点的强度更小。

因此RNR的做法就是：检查雷达数据的一些底环（线束靠下的，例如128线最下面的10线），去除之中高度小于阈值h_{noise} ,强度小于I_{noise} 的数据点，这些点被认为是强度很大高度又很低的噪声点。高度阈值这个参数，在A-GLE会自动更新。

C. R-VPF: Region-wise Vertical Plane Fitting（区域垂直平面的拟合）

R-GPF平面拟合前，找到每个bin中的垂直点集，使得地面估计会更准确

在地面高于一些垂直结构时，R-GPF因为选择了垂直结构中的点作为初始点（因为他们的z值比实际地面点更小），地面估计还是会错误。如图5所示，在当前bin中路沿低于地面，并更靠近传感器。R-GPF选择了墙中的点作为初始点，由于PCA对异常点敏感，所以平面估计错了。

有些人会说，这个高的地面由于可以和另一个地面区分开，而且该地面比正常地面z值大，所以应该不属于地面。但是一些动态的物体，如人类，是可以站在那个地面上的。因此本论文会将这些点，认做地面点。作者说对了，确实会有人反对，我就是反对的这些人之一，以后有机会的话会结合我的理解，给出我的观点。

我们对bin中的点进行预处理，让R-GPF算法拒绝这些垂直的点，以拟合出更准确的平面，我们把这种方法叫做R-VPF。具体的步骤如下：

利用Patchwork中的基于同心区域模型CZM，将点云分为n个bin，第n个bin设为P_n。第n个bin估计出的垂直点V̂_n是经过以下4个步骤得到的：

第1步：首先R-VPF需要经过k次迭代，每次迭代都选择一些z值最低的点，作为种子点。接下来求这些种子点的平均值m^k_n ∈ R^3和单位法向量 v^k_{3,n} ，单位法向量代表这些种子点执行PCA后最小特征值对应的归一化后的单位特征向量。
第2步：第 k 次迭代潜在的垂直平面的点集 Ŵ_{n,k}，是在候选点集 P̂^k_n 中采样得到的，公式如下：

式子中在 k=1时（也就是第一次迭代时），P̂_n^k ← P_n（候选点集是第n个bin的全部点）。候选点集是这样确定的：P̂_n^k ← P_n − U_{i=1}^{k-1}V̂_n^i（每次迭代的候选点集，就是用全部点减去，之前迭代出的全部垂直点）。d_v 表示估计的垂直平面的距离margin。

第3步：V̂_n^k代表第k次迭代认为的垂直点集，它的计算公式如下：

式子中u_z 表示z轴方向的单位法向量，也就是[0, 0, 1]^T，θ_v 是估计平面的单位法向量的margin。(种子点的法向量和z轴法向量做点乘，两个单位向量的点乘结果就是夹角的cos值，判断该值与90度的相近程度。在范围内，由这次迭代的种子点找到的垂直点集，可以被认为是垂直点集；否则，这次的垂直点集，不能认为是垂直的)

第4步：最后，累计所有垂直点得到总的垂直点集V̂_n，K_v代表R-GPF的迭代次数

把公式的含义，以举例子的方式说明会简单很多：

假设有100（随机选个数）个bin，每个bin都需要独立估计垂直点。假设我们估计第7（随机选个数）个bin哈，我们先选这个bin里最低的几个点。假设这个bin里有500个点哈，我们选了20个当种子点，算出了这20个点的平均值和单位最小特征向量。第1次迭代，全部的500个点分别去减平均值，通过公式2来计算判断，会得到一些潜在的（不一定是真的）垂直点，假设有70个吧。再将种子点的最小特征向量，与z轴单位向量去做叉乘，由公式3计算判断得到一个结论：20个种子点我到底选对没有？如果选对了，70个点成为了第1次迭代估计出的垂直点，第2次迭代你就得从剩下的500-70=430个点中再选种子点了；如果没选对，这次算没有估计出垂直点，第2次迭代还是从500个点选种子点。

D. A-GLE: Adaptive Ground Likelihood Estimation（自适应地面似然估计）

Patchwork中提出了GLE的方法，利用f (X_n |θ_n )来确定一个区域是地面还是非地面。以下是Patchwork中的公式定义

GLE的概率由三个概率函数相乘组成：以 v_{3,n}为变量的垂直度 ，以z̄ _n 为变量的高度，以 σ_n 为变量的平坦度。具体来说，v_{3,n}是种子点 PCA 中特征值最小的特征向量，z̄ _n 是种子点的均值，σ_n是局部表面变化，它的值σ_n = \frac{λ_{3,n}}{ λ_{1,n}+ λ_{2,n}+ λ_{3,n}} 其中 λ_{1,n} ，λ_{2,n} 和λ_{3,n} 是给定点的 PCA 的特征值，按降序排列。

需要为这个三个函数设置对应的参数，也就是(θ_τ , κ(r_n ), σ_{τ,m} )，来作为垂直度、高度和平坦度的阈值。在Patchwork++中为简单起见，z̄ _n 、σ_n 、κ(r_n ) 和 σ_{τ,m} 表示为 e_n 、f_n 、e_{τ,m} 和f_{τ,m}。

然而，在Patchwork中，根据环境选择最优的参数，尤其是 e_{τ,m} 和 f_{τ,m}非常耗时。在图 6 中，真实地平面的高度和平坦度值的分布似乎因周围环境而异。因此不同的环境，参数需要进行调整。

序列00、01、04、08的CZM第一环真实地面点的平均高度e_n和平坦度f_n的概率分布。序列 00 和 08 有着相似的分布，相反，序列 01 和 04 是完全不同的分布。 U、H 和 C 分别表示城市、高速公路和乡村场景。

横坐标为真实地面点平均高度和平坦度的值，纵坐标为对应值的数据帧占全部数据帧数的百分比

为了解决这个问题，A-GLE的思想就是自适应的调整参数e_{τ,m}和f_{τ,m}。除非初始值设置的太过异常，A-GLE都能正确的更新参数。除此之外，之前提到的RNR（噪声去除）的高度阈值h_{noise}也是由A-GLE更新的。

Elevation（高度）

高度的参数自动更新，我们提出一个新颖的概念：明显地面（definite ground）D_m。它代表CZM模型第m个环满足垂直度和高度条件的平面（已经满足了Patchwork的垂直度和高度，但还没有考虑平坦度）。A-GLE要采用明显地面的特性，来更新高度参数，以进行下一次估计

令E_m是明显地面D_m中e_n的集合（也就是平均高度值的集合），基于E_m，e_{τ,m}的更新公式如下：

式子中mean(.)代表集合的平均值，stdev(.)代表集合的标准差。a_m>0代表为CZM模型第m环中标准差，给的一个固定增益（固定乘这个值）。

A-GLE的高度自适应更新：对于高度阈值参数，相对于Patchwork的固定值，Patchwork++是在不断更新的

Flatness（平坦度）

在更新平坦度参数f_{τ,m}之前，我们发现Patchwork的计算有潜在问题。上面说到，平坦度是f_n= \frac{λ_{3,n}}{ λ_{1,n}+ λ_{2,n}+ λ_{3,n}} 这样计算的。那么为了使这个平坦值有意义，无论地面与雷达的相对位置如何，对于同一地面该值必须是恒定的。

挺好理解的，Patchwork的问题就是：平坦度计算出的是当前bin的数据经过PCA后的三个特征值，特征值也好或者特征向量也好，我们希望它们是反映世界坐标系下的三维特征的，而Patchwork计算出的特征是在雷达坐标系下的。雷达xy平面如果没有与地面平行呢？又或是运行中雷达意外歪了呢？

但不幸的是，由于Patchwork利用了CZM模型，地面被分为了若干bin。地面被划分成了不同的形状和大小。那么，即使整体的地面没有改变，特征值 λ_{1,n}和 λ_{2,n}也可能发生了变化。因此有人会说，由于潜在的不一致性，这样计算的平坦度f_n是不合逻辑的。为了解决这个问题，Patchwork++设置平坦度为f_n = λ_{3,n}，也就是表面的法向量。

看Patchwork论文时关于平坦度的计算我没有深究，Patchwork++这会儿提到我才关注。设置平坦度为最小特征值，这简直是显而易见的啊，我在点云识别物体的很多代码中，也只是使用了最小特征值，而不是全部特征值组合的关系。从这点来看，Patchwork用错了，而Patchwork++仅仅是纠正了这一错误，这一点算不得改进。

与 e_{τ,m} 类似，f_{τ,m} 也是根据 A-GLE 的 D_m 分布进行了更新。令 F_m 为 明显地面D_m 中所有 f_n 的集合。然后，f_{τ,m} 可以更新如下：

式子中b_m>0代表为CZM模型第m环中标准差，给的一个固定增益（固定乘这个值）。

Noise Removal Height（噪声去除高度）

A-GLE还要更新一下噪声高度阈值h_{noise}，用于去除较近环中出现的噪声点。

其中δ < 0代表噪声去除的一个范围边界值。E_1之前说过了，代表最近环中数据点z值的集合。

相当于，统计了最近环数据点的z值，求了一个平均值，再减去一个固定小值）

E. TGR: Temporal Ground Revert（暂时的地面还原）

通过参数可以自适应更新的A-GLE后，我们成功估计出了地面。然而，一个 bin 内的一些不寻常的地面点，不满足参数的条件。例如，有草的崎岖地形，可能相比自动更新的参数（平均高度e_n 和 平坦值f_n），值更大。这是因为 A-GLE会随着时间的推移根据所有的值，来更新参数。A-GLE可能会起到一个低通滤波的作用，如果一个bin的平坦度暂时比较大，那这个bin这次可能很难被估计为地面了。 A-GLE中的参数自更新，你会发现高度和平坦度都使用了平均值作为基础，那么显然可能会漏检一些值偏大的bin

为了解决这个问题， 我们提出了TGR，利用这个bin仅在时间t时是明显路面D_m^t，将欠分割的路面恢复成路面。换句话说，TGR会将每个欠分割的bin的平坦度f_n，与t时刻的平坦度阈值f^t_{τ,m}进行比较，计算公式如下：

c_m代表CZM第m个环的标准差的常数增益，F_m^t是D_m^t中平坦度f_n的集合。因此，在被拒绝的地面点（其平坦度f_n大于平坦度阈值f_{τ,m}的）中，如果平坦度满足f_n<f_{τ,m}^t，这些被拒绝的地面可以恢复成地面。

理解公式6与公式8的区别是核心关键。假设我们在第99帧去完成A-GLE的计算，那么公式6计算出来的平坦度阈值，是要用在第100帧的计算的，而公式8的意思（也就是TGR的核心）就是，当前第99帧计算第2个平坦度阈值，用这个新阈值，可以将被第99帧第1个阈值拒绝掉的一些bin重新恢复为地面

Patchwork++总的流程图

前面把整个Patchwork++讲的挺清楚了，这里再结合总的流程图快速梳理一下：

给定了数据

  1. 先利用噪声阈值，去除噪声（RNR）
  2. 再对全部数据进行CZM分区
  3. 对每个分区，利用R-VPF去除可能对拟合平面产生干扰的垂直点
  4. 接下来对每个分区进行R-GPF地面拟合
  5. 综合考虑垂直度、高度、平坦度，得到一个总概率进行bin级的地面分割
  6. 利用TGR恢复一些被平坦度阈值拒绝的bin
  7. 得到最终结果
  8. 最终结果结合提出的A-GLE，更新一下算法中使用的阈值，进行新一次的地面估计

总结

这篇文章很好的讲解了Patchwork++，从论文内容上我认为我已经100%理解了作者的意图，当然了他的代码已经在我手里了，接下来会看他的源码。Patchwork++的实验效果，我再考虑是否有时间进行分析把。

总的来说，作者利用了LineFit和GPF的思想，发表了R-GPF、Patchwork的方法，这次又对自己的工作进行了有效的改进，值得肯定。

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