1）摘要

        3D 点云中的实时平面提取对于许多机器人应用至关重要。作者提出了一种新颖的算法，用于在从 Kinect 传感器等设备获得的有组织的点云中实时可靠地检测多个平面。通过在图像空间中将这样的点云均匀地划分为不重叠的点组，我们首先构建了一个图，其节点和边分别代表一组点及其邻域。然后，在此图上执行凝聚分层聚类，以系统地合并属于同一平面的节点，直到平面拟合均方误差超过阈值。最后，使用像素级区域增长来优化提取的平面。实验表明，所提出的算法可以可靠地以超过 35Hz 的帧速检测场景中的所有主要平面，对于 640×480 个点云，比最先进的算法要快得多。

2）创新点

①提出了一种基于组织点云的凝聚聚类的高效平面提取算法。

②分析了聚类算法的复杂性，并表明它在初始节点的数量上是对数线性的。

③展示了实时性能，其准确性可与最先进的算法相媲美。

3）算法结构

3.1）快速平面粗提取

        快速平面提取算法包括三个主要步骤，如上图所示：该算法首先初始化一个图形，然后执行 AHC 以提取粗平面，最后进行细化。如果应用程序只需要对平面区域进行粗略分割，例如，检测点云中的对象，则可以跳过最后的优化步骤，这可能会将 640 × 480 个点的帧速率增加到 50Hz 以上。

        首先，我们澄清我们的符号。F 表示由 M 行和 N 列组成的有序点云的完整帧。B、C 分别表示粗细分割，即 B/C 的每个元素 Bk/Cl 都是一个段——一组 3D 点 pi，j 。同时 Π、Π0 分别是对应于 B、C 的平面方程组。另请注意，图 G 的每个节点 v 都是一组 3D 点，每个无向边 uv 表示图像空间中线段 u、v 的邻域。

A 图初始化

        我们的算法需要非重叠节点初始化，如算法 2 的第 3 行到第 5 行所示。此步骤在图像空间中将点云均匀划分为一组大小为 H × W 的初始节点。这个要求导致我们的算法失去了自动检测平面边界的优势。为了在此限制下使用 AHC 正确分割平面，我们从图中删除以下类型的节点和相应的边缘，如下图中的示例所示：

        1）具有高 MSE 的节点：非平面区域会导致高平面拟合 MSE，我们只需将其删除即可。

        2）包含缺失数据的节点：由于传感器的限制，可能无法正确感知场景的某些区域，从而导致数据丢失（例如，百叶窗后面的玻璃窗）。

        3）包含深度不连续性的节点：这些节点包含两组点，它们位于两个表面上，这两个表面在 3D 中并不接近，但在图像空间中很接近（通常一个表面部分遮挡了另一个表面，例如，显示器遮挡了后面的墙壁）。如果在属于该节点的点上执行主成分分析 （PCA） 以进行平面拟合，则拟合平面将几乎平行于视线方向，因此仍然具有较小的 MSE。将此“异常值”节点与其相邻节点合并将对平面拟合结果产生不良影响，因为在最小二乘法中存在众所周知的过度加权异常值的问题。

        4）两个平面之间边界处的节点：这些节点包含两组在 3D 中彼此靠近但位于两个不同平面上的点（例如，房间的角落），如果它们合并到其中一个平面，将降低平面拟合精度。

算法 2 中的函数 REJECTNODE 和 REJECTEDGE 旨在减少这四种不良初始节点的影响。REJECTNODE 函数从图形中删除前三种类型的坏节点（以及其中的点），而 REJECTEDGE 函数用于减轻第四种坏节点的影响。有趣的是，这种不重叠的 “劣势 ”的好处是避免了每点的正常估计。我们的初始化步骤可以看作是将节点内的所有点视为具有公共平面法线。与其他最先进的方法相比，这是我们速度提高的一个重要原因，这些方法通常花费大量时间对每个点进行正常估计。

B Agglomerative Hierarchical Clustering

        如算法 3 所示，我们算法中的 AHC 与线回归中的 AHC 几乎相同，只是它是在图而不是双链表上做的。我们首先构建一个最小堆数据结构，以有效地找到具有最小平面拟合 MSE 的节点。然后，我们重复查找一个节点 v，该节点当前在图中的所有节点中具有最小平面拟合 MSE，并将其与它的一个相邻节点 u_best 合并，从而产生最小合并 MSE（回想一下，图中的每个节点都是一组点;因此合并的 MSE 是两组 umerge 的并集的平面拟合 MSE）。如果此最小合并 MSE 超过某个预定义的阈值 TMSE（不一定是固定参数），则找到一个平面段 v 并从图中提取;否则，合并后的节点 umerge 将通过 v 和 ubest 之间的边收缩添加回图中。

3.2）平面分割结果细化

        对于许多应用程序，在上一节中获得的粗平面分割可能还不够，特别是如果应用程序使用平面的边界或需要更高精度的估计平面方程。因此，我们对粗略分割 B 执行细化。

        粗略分割中预计会出现三种类型的伪影，如上图所示：

        • 锯齿波：通常位于两个连接平面之间的边界处。

        • 未使用的数据点：通常位于遮挡或缺失数据节点的边界处。

        • Over-Segmentation：通常在两个对象的遮挡边界之间

        锯齿伪影会导致估计中包含少量异常值，而未使用的数据点和过度分段会导致使用的异常值较少。所有伪影都会产生不准确的平面边界，并略微降低估计平面方程的精度。

        我们对它们的解决方案在算法 4 中进行了描述。由于锯齿伪影几乎总是在 B 的边界区域观察到，因此每个段边界区域的侵蚀可以有效地消除它们（第 5 行至第 13 行）。然后，从所有新的边界点开始像素级区域增长，将所有未使用的数据点分配给之前提取的最近平面（第 14 行到第 27 行）。在区域增长期间，将为每个段 Bk 发现 4 个连接的邻域，从而形成一个新的图形 G0 。最后，在这个非常小的图形（通常少于 30 个节点）上再次应用 AHC 可以修复过度分割伪影（第 28 行）。

4）实验

A 仿真数据

        在模拟深度图上测试了算法的鲁棒性，该深度图具有 20 个不同级别的均匀分布噪声，幅度为 E = 10l、l = 0、. . . 、20（噪声单位：mm;真实深度范围为 1396mm 至 3704mm）。将噪声添加到深度图后，我们将其转换为有组织的点云并输入到我们的算法中 （W = H = 20，TMSE = 502 ）。如下图所示，我们的算法可以可靠地检测 l = 0， . . . ， 14 的所有 4 个平面，并在此之后开始过度分割。然而，即使 E = 200 毫米，我们的算法也能够检测到场景中的主要平面。

B Kinect采集的实际数据

        为了测量算法的处理速度，在室内场景中收集了 2102 帧 640 × 480 像素的真实 Kinect 数据，部分如上图所示。然后使用 12 种不同的初始节点大小（TNUM = 800，α = 0.02，e= 8mm，TANG 从 z = 500mm 的 15◦ 线性增加到 z = 4000mm 的 90◦）。如下图所示，初始节点大小为 10 × 10，即使经过细化，我们的算法平均只需 27.3 ± 6.9 毫秒即可处理一帧 640×480 像素的 Kinect 数据，实现了超过 35Hz 的帧速率。据我们所知，这比其他最先进的算法要快得多。

C 分割数据集

        使用 SegComp 数据集评估了算法的准确性。对平面场景的 ABW （W = H = 4，TMSE = 1，TANG = 60◦ ，TNUM = 160， α = 0.1） 和感知器 （W = H = 8，TMSE = 2.1，TANG = 45◦ ，TNUM = 240， α = 0.03） 数据集进行了实验。ABW 和 PERCEPTRON 测试数据集的典型分割结果如上图所示。使用 SegComp 提供的评估工具的详细基准测试结果如下表所示。可以看出，该算法在分割精度和平面方向估计方面的性能与最先进的算法相当，特别是考虑到帧速率要高得多。

5）结论

        作者提出了一种新颖的有序点云快速平面提取算法，在 640 × 480 个点云上实现了超过 35Hz 的帧速率，同时提供了准确的分割。将来，希望将该算法扩展到无组织的点云以及球体和圆柱体等其他基元的快速提取。