M. Himmelsbach, A. M¨uller, T. L¨uttel and H.-J. W¨unsche. 2008

摘要

本文描述了基于激光雷达的感知地面机器人移动系统，包含了3D物体检测，分类和跟踪。 该系统被应用于我们的自动地面车辆MuCAR-3，使其能够安全地在城市交通以及野外场景种航行。 我们的方法的效率源于2D和3D数据处理技术的独特组合。 其中点云快速分割在2.5D网格中进行，物体聚类在原始3D点云中完成。为了快速切换域，增强了占用网格使其具有哈希表的性质，以快速获取3维点云。 现在大多数3D点云分类工作都不能做到实时操作，但我们的系统可以0.1s帧速率实时执行。

I. 引言

本文解决了将3D扫描数据分割为已知对象的问题。给定3D点的集合，分割的目标是将点归到一组候选对象类别。在地面自动机器人领域，分割能力不仅对高级别任务（如场景理解和规划）而言至关重要，也可以用于扫描配准和机器人定位（如SLAM框架[1]）。另外，了解对象的类别在动态环境中特别有用，它有助于规划和估计：使用合适的动力学模型可以改善估计，规划可以纳入关于特定对象类的典型行为或意图的知识。

我们的感知方法可以分解为3步：分割、分类和追踪。分割在占用网格中进行，产生不属于地面的连通网格，然后通过一个高效的方法确定所有与分割物体对应的3D测量点。在分类步骤中，我们通过对象点云提取特征，在每个点周围固定支持体积内捕获局部空间分布并提取相对属性，然后给出手工标记的点云案例，利用支持向量机（SVM）来分类点云，例如其他交通参与者。

A. 相关工作

随着距离扫描设备成为移动机器人的标准设备，3D扫描分割和分类的任务是增加实际相关性的任务之一。有趣的是，尽管距离扫描仪是DARPA城市挑战赛2007的主要传感器，但主要是在2.5-D占用网格上进行分割。 如果有的话，分割对象的分类是在2D域中完成的，通过拟合L形或边界框并根据简单规则验证它们[2][3]。 由于严格的竞赛规则，分类可以被省略，因为在道路边界内检测到的每个物体只能对应另一辆车。

相比之下，Anguelov[4]和Lalonde[5]描述了为每个扫描点分配类标签的方法。给出标记的点云，然后分割扫描是十分直接的。虽然为每个点提取的特征没有显着差异——两种方法都使用局部点云统计进行特征提取，稍后将详细说明——但遵循不同的分类范例。 Anguelov等人[4]通过概率分布对点的类标签进行建模，该概率分布以局部特征和点邻域中的标签为条件。 因此，它们利用扫描中的相邻点应具有相似标签的事实来强制空间连续性。该分布由马尔可夫随机场（MRF）建模，其参数在监督学习阶段中确定，使得得到的分类器最大化所学习的类之间的余量，如SVM那样。 虽然[4]中没有给出运行时间，但从[6]可以得出结论，该方法不允许实时使用。

Lalonde等[5]通过在手标记的训练数据集上使用期望最大化（EM）算法拟合高斯混合模型（GMM）来学习每个类的特征分布的参数模型。通过在分类之后运行简单的基于规则的过滤器来保证空间连续性，例如，通过将点的标签更改为其邻域中频率最高的类。但是，为了使它们的方法能实时执行，尚需进行一些修改。特别是不再对单个点进行分类，而是对3D体素网格单元中的原型点进行分类，分类速度可以达到7000个体素/秒。

我们采用了一种截然不同的独特方法，即基于2.5D占用网格压缩数据进行分割。然后，我们再次使用Velodyne的3D点云中包含的丰富信息，再次将域切换为3D，现在仅对所有点云的子集进行分类，因为每个子集代表一个单独的对象。 由于2D和3D数据处理技术的有效组合，可以在自动车辆上实时地对由其3D点云表示的对象进行分类。

II. 物体检测

A. 占用网格

我们使用一个2.5维的以自车为中心的维度占用网格100m x 100m，每个单元覆盖0.15m x 0.15m的小地面块。每个单元存储单个值，表示该单元被障碍物占用的程度。在我们的实现中，该值具有物理单位[m]的度量长度。在我们详细说明其含义和计算之前，请注意在我们的方法中，我们在每次新的LIDAR数据帧中创建一个新的占用网格，比如每0.1s。因此，我们不会累积更长时间的数据。这个决定的原因是双重的。首先，Velodyne一帧提供了大约100000个3D点，这证明是足够的。其次，如果不以非常高的精度估计传感器的物理运动，则累积占用网格的质量可能容易恶化。传感器估计的小角度偏差可能导致大的误差。相互定位扫描，例如使用ICP算法[7]或它的一些衍生物，可以解决这个问题，但需要大量额外的计算负荷。

为了计算占用率值，我们首先对LIDAR扫描进行惯性校正，考虑车辆的运动（利用IMU和测距信息）。这是通过将当地点云测量转换到全局3D空间的同时移动局部坐标系来完成的。 在一帧完成之后，所有点都被转换回车辆的最后一个局部坐标系，模拟扫描，好像所有测量都是在单个时间点而不是一个LIDAR旋转的0.1s时间段进行的。然后，与Thrun等类似[8]，每个单元的值计算为落入相应网格单元的所有点的z坐标的最大绝对差。当激光束击中网格单元并更新其占用值时，我们将激光点存储在单元中，以便后续可以查询，详见第III节。图2显示了具有叠加点云的占用网格。

图2. 占用网格

B. 分割对象

为了获得初始对象假设，我们接下来查找网格单元的连通子图来执行对占用的网格单元的分割。为了应用连通子图算法，首先需要对网格进行二值化。可以简单地将所有单元的占用值与适当的值（对于MuCAR-3为0.15m，从其轮胎的直径得到）进行阈值处理，将所有占用值低于1的单元设置为0，其他的设置为1。然后，可以应用从机器视觉[9]中的标准连通子图算法，其为每个网格单元 分配它所属的连通子图的标签 。

对于每个连通子图，我们给出未知类的对象3D边界框。可以根据属于相应连通子图的所有单元的离散网格坐标 来计算对象边界框的x轴和y轴， 。 这里，“ego”上标用于表示现在所有网格坐标都在自车坐标系中表示，通过自车和网格单元之间的静态几何关系极大地简化了转换。边界框的轴对应于坐标协方差矩阵 的正交特征向量，通过降序保存，即对应特征值 。

将所有 线性变换到特征向量定义的坐标系中（所谓特征空间）， 然后在结果坐标中取最大最小值，就得到包络盒的平面尺寸。对象的位置 简单地定义为连接子图的重心。这个2D包络盒的可以保证覆盖连接子图的所有单元，但是丧失了一些期望的性质，例如具有最小包络面积。虽然目前运作良好，但是未来可能会进一步改进。

假设对象的z轴垂直xy平面，可将z的值设为所有单元中的最大值。至此，获得了最终的3D边界框。

                                  图3. 占用网格的3D包络盒

III. 分类

如前所述，我们希望根据3D点测量值对检测到的对象进行分类。但是，对象检测只为我们提供了对象的边界框表示。在本节中，我们将展示如何通过占用网格查询给定对象的3D点，以及从点云中提取何种特征。 最后，我们描述了如何训练我们的对象分类器并简要展示一些分类结果。

A. 对象点云

回忆到在使用激光点云更新网格单元时，我们将激光数据存储在单元中。因此，获得对应于对象的点云的简单方法是简单地收集存储在相应连通子图内的所有激光数据。然而，这在我们的案例中是不合适的。原因在于，连通子图仅由z坐标差异大的单元构成，并且不能理所当然地认为对象的所有测量都落入这样的单元中。因此，仅从连接子图单元中取出点可能会错过大量的对象测量并且使得后续分类步骤变得困难。

相反，我们提取对象3D边界框中包含的所有激光读数。为此，我们扩充网格的功能，以响应对任意（凸面和非凸面）多边形的数据的查询，其中顶点在局部坐标系中定义。 给定这样的查询，我们首先将顶点坐标从局部坐标变换为网格坐标，并将得到的多边形分割成三角形。接下来，我们在每个结果三角形上应用三角形扫描线算法，以得到原始多边形中包含的每个网格单元。然后，回答查询就简化为收集存储在被访问单元中的所有激光数据的问题。

                                          图4. 查询包络盒内所有点云

B. 点云特征提取

下一步是从点云中提取有意义的特征。主要困难是找到点云的紧凑表示，从而与原始点云相比显着降低维度。否则，生成的分类器将不能实时执行。同时，丢弃过多的原始数据可能导致分类器做出太多错误的决定而根本没用。

Anguelov等人使用的特征[4]和Lalonde等[5]为我们提供了这一步骤的基础。然而，它们不能直接应用，因为在我们的例子中，提取的特征必须提供可能包含大量点的点云数据紧凑描述，而Anguelov和Lalonde的工作中使用的特征仅需要描述单个点的突出属性。另一方面，可以从点云计算的特征不限于本地点属性。相反，某些特征还应该捕获全局对象属性，例如对象的尺寸或体积等。因此，我们将同时使用局部和全局特征来描述点云。

形式上，点云P可写为 ，其中 表示单个激光读数，由坐标和强度  组成。 对于实际数据，对象点云的大小通常在M = 100 ~1000的范围内。 然而，对于更接近传感器的物体，M = 10000点的点云在极端情况下是可能的。在实时操作时，针对如此大量的点计算每个激光读取的本地统计数据是难以处理的。因此，我们对每个点云进行均匀的降采样，以在特征提取之前将点数减少到常数M = 200。

我们现在描述从降采样后的点云中提取的特征。

1）对象级特征：我们不涉及任何局部计算特征为“对象级特征”。 在我们最终的特征向量中包括了4个这种特征，它们都是标量值。

1. 最大对象强度  
2. 平均对象强度
3. 对象强度方差
4. 对象体积，由3D包络盒计算得到

显然，上述计算中 。

       2) 点级特征：对象级特征不涉及局部点属性，我们现在转向捕获局部点云统计类型的特征。为了将特征从点级别转移到对象级别，我们为每个点要素引入直方图，并通过对每个点的特征评估更新直方图。在为计算了所有点的特征之后，我们通过将每个bin值除以M来标准化相应的直方图。然后，将得到的直方图输入到我们的最终特征向量中。为了能够在固定的有限范围内定义直方图区间，我们将所有点特征标准化为0~1范围内的值。

• Lalonde特征 。

Ladone等人[5]通过检查相邻点的分布计算了表示点散射度  、线形度  和表面度  的特征。为了计算特征，他们对相邻点的3D坐标的协方差矩阵进行特征值分析，得到特征向量 ，相应特征值  。然后令 ， ， 。由于这些特征没有任何实际的上限，我们可以做个替换   使得 。 为了将这些点级特征转换为对象级，我们将3个直方图添加到最终特征向量中，每个直方图由4个0~1之间的等间隔bins组成。

Anguelov特征  。

Anguelov等人[4]描述了两个特征，但我们只使用了其中一个特征，因为另一个特征Lalonde特征没有显着差异。我们采用的特征定义了一个高度为2m且半径为0.1m的垂直圆柱体，该圆柱体围绕计算该特征的点。然后将该圆柱体垂直等分成3个部分 ，并统计每个部分包含点的数量占整个圆柱内所有点数的比。这将另外三个4槽直方图添加到最终特征向量，描述给定点云中 的分布。

       我们还没有准确定义“相邻点”这个词。在这里它指的是该点0.5m范围内最近邻的20个点。最近邻点可以通过构造一个kd树来找到。

       最终的特征向量包含了4个标量，6个直方统计特征，每个直方统计特征包含4个直方条，总共28个特征。

                                                  

其中   表示直方图上的标量值变量v有b个bin值。

C. 训练SVM分类器

SVM分类器在手工标记的训练数据集上训练。与Anguelov等人使用的最大间隔MRF（M3）一样，SVM最大化了它所训练的不同类之间的间距，但缺乏空间连续性的概念。不过我们在分类之前已做了分割，空间连续性就不太重要了。我们使用通用的 变体，它允许一些标记被判定为错误标识，以防止类别在特征空间中不能完全分离[10]。多分类的方法是一对所有（one-against-all）分类，针对每个类训练一个二分类器，将其与所有其他类分开。

关于车的二分类效果如下图所示，其中上面四行是正例，下面四行是反例。