泡泡点云时空，带你精读点云领域顶级会议文章

标题： Scan Registration for Autonomous Mining Vehicles Using 3D-NDT

作者： Martin Magnusson and Achim Lilienthal，Tom Duckett

来源：JFR 2007

编译：阮建源

审核：Lionheart

欢迎个人转发朋友圈；其他机构或自媒体如需转载，后台留言申请授权

扫描配准是基于测距仪数据从移动机器人构建地图的一项重要工作。该问题是根据扫描帧重叠部分的形状，推断出机器人是如何在连续扫描帧之间移动的。本文提出了一种新的三维数据 配准 算法。该算法是Biber和Strasser所开发的 2D NDT算法的泛化和改进 ，其可以使用一种节省内存的扫描表面表示方法进行精确的配准。还将此新算法与3D ICP算法进行了一个详细的定量和定性的比较。使用实际矿山数据，其中一些是利用新型3D扫描仪采集的，实验结果表明，比和标准的ICP算法相比，可靠的三维配准，本文提出的算法 速度较快，且可靠性稍高 ，同时，这一表面表征方法 存储效率更好 。

图1，阿特拉斯·科普柯在自然环境中的钻机。该车配备了安装在伸缩臂上的凿岩机，用于爆破前在岩面钻孔。

一，2D NDT

正态分布变换（normal distributions transform ，NDT）是一种点云配准方法。本基于Biber & Strasser的工作，他们的2D NDT 着眼于表面的概率分布，而不是独立的点。这样的表示具有 连续的一阶和二阶可导性质 ，因此可以使用牛顿法来求解，同时避免了ICP的最近点查找，具备较好的存储优势。

图2，一帧部分房间的二维激关雷达扫描结果以及NDT描述。原始点用小正方形表示，而圆角形状则显示所占网格单元格的正态分布。每个单元是边长1米的正方形。较亮的区域代表较高的可能性。

2D NDT的流程如下：

具体来看，参考帧为model，被配准到其上的帧为data，对于model帧中点云，进行网格的划分，将点存储在网格中，而后计算每个网格的重心和协方差：

概率密度函数（PDF）为：

待优化的参数为位姿，二维场景下表示为：

该位姿作用于data帧，给定一个位姿，可以利用一个得分表示两帧数据被配准的优劣，即PDF的和：

用x’表示变换之后的点：

这一得分的一阶偏导数和二阶偏导数为：

其中，对于变换的偏导具体为：

二，3D NDT

图3，一个隧道切片的三维NDT概率函数。更亮的区域代表更高的概率，格子的边长为1m。

3维场景的区别在于，三维的变换以及对其的一阶二阶偏导数。使用轴角+位置的方式表达3维位姿，参数为：

则一阶偏导和二阶偏导分别为：

三，实施细节

有几个细节需要考虑，包括 降采样 的方法， 网格的大小 ，和 离散化 的细节。

对于NDT而言，比网格更小的特征在PDF的表示下是模糊的，因此需要进一步细化网格。但是过小的网格又会导致在关联中只能和很小区域内的点形成关系。本文采用的首先是存储一系列均匀大小的网格，这样可以避免过多的闲置叶子节点，同时具备线性的查找时间。在这些网格之中，采用八叉树的结构，同时采用的是一种加法细分的方法，也就是说，在细分之后，对于一个点，每个叶节点PDF的和起作用，而不是只剩某个叶节点中的PDF。

图4，八叉树和加法细分的比较。左图显示了一个格子的划分情况，右侧则是树的结构。八叉树的划分在格子g内的得分仅仅由该格子内的PDF提供，采用加法细分则g的得分为其余子网格PDF影响之和。

按照此前的离散化方法，落在未占据网格中的data帧数据在配准中将被忽略，为了缓解这一现象，我们将距离最近的网格关联在一起。尽管在未占据网格中，其他网格的PDF影响较小。

图5，配准两个隧道分段的2维扫描。虚线表示的点云被配准到实线表示的点云上。如果关联网格方法没有使用的话，阴影网格外的扫描就被忽略，关联网格的关系使用箭头表示。

作者采用了三个地下矿井采集的数据集，相对于ICP进行了全方面的评价。这样的矿井环境的特点是，平面特征较少，表面比较破碎。

一，数据集

图6，实验的一个隧道。

图7，JUNCTION数据集的一帧扫描数据。

图8，TUNNEL数据集的两帧扫描。

图9，扫描仪原型机。

图10，使用的扫描机器人。

图11，KVARNTORP-LOOP数据集的前65帧扫描。

采样率的影响：

使用空间分布的降采样，采样率的影响：

均匀降采样时，采样率的影响：

不同格子大小的影响：

ICP和NDT对初始位移变换敏感性的对比：

ICP和NDT对初始旋转变换敏感性的对比：

不同离散化方法的影响：

图19，两帧数据配准之前。

不同离散化方法的影响：

是否采用外部边界的影响：

ICP的结果作为对照：

Abstract

Scan registration is an essential subtask when building maps based on range finder data from mobile robots. The problem is to deduce how the robot has moved between consecutive scans, based on the shape of overlapping portions of the scans. This paper presents a new algorithm for registration of 3D data. The algorithm is a generalization and improvement of the normal distributions transform NDT for 2D data developed by Biber and Strasser, which allows for accurate registration using a memory-efficient representation of the scan surface. A detailed quantitative and qualitative comparison of the new algorithm with the 3D version of the popular ICP iterative closest point algorithm is presented. Results with actual mine data, some of which were collected with a new prototype 3D laser scanner, show that the presented algorithm is faster and slightly more reliable than the standard ICP algorithm for 3D registration, while using a more memory efficient scan surface representation.

泡泡机器人SLAM的原创内容均由泡泡机器人的成员花费大量心血制作而成，希望大家珍惜我们的劳动成果，转载请务必注明出自【泡泡机器人SLAM】微信公众号，否则侵权必究！同时，我们也欢迎各位转载到自己的朋友圈，让更多的人能进入到SLAM这个领域中，让我们共同为推进中国的SLAM事业而努力！

泡泡机器人SLAM的原创内容均由泡泡机器人的成员花费大量心血制作而成，希望大家珍惜我们的劳动成果，转载请务必注明出自【泡泡机器人SLAM】微信公众号，否则侵权必究！同时，我们也欢迎各位转载到自己的朋友圈，让更多的人能进入到SLAM这个领域中，让我们共同为推进中国的SLAM事业而努力！

商业合作及转载请联系liufuqiang_robot@hotmail.com 返回搜狐，查看更多