论文题目：Normal Distributions Transform Occupancy Maps: Application to Large-Scale Online 3D Mapping

这篇论文结合了NDT和占用栅格地图的优点，同时对二者都结合3D激光雷达做了适应性改进，最终实现了既能够增量式更新地图表示，又能够移除动态物体的效果。

本篇论文的作者还有另外几篇论文，其实讲的是同样的东西，只不过把某些细节详细解释了一番，然后加了一些应用案例，如果对本篇论文有什么疑惑，可以参考他们，分别是：

1)3D Normal Distributions Transform Occupancy Maps: An Efficient Representation for Mapping in Dynamic Environments.

2)Fast 3D Mapping in Highly Dynamic Environments using Normal Distributions Transform Occupancy Maps.

3)Normal Distributions Transform Occupancy Map Fusion: Simultaneous

4)Mapping and Tracking in Large Scale Dynamic Environments

5)Normal Distributions Transform Traversability Maps: LIDAR-Only Approach for Traversability Mapping in Outdoor Environments

话说这种做法不算一稿多投吗，还是说这是灌水的常见做法？

一、整体思路

我们知道NDT和占用栅格地图是两种不同类型的点云表示方法，之前很多SLAM系统都是分别基于二者进行构建的。它们各自有各自的优点，NDT对于匹配来讲，精度高而且稳定，在同样分辨率下(同样分辨率是指NDT的grid的边长和栅格地图cell的边长)，效果要好于占用栅格方法。而栅格在更新过程中，又可以根据占用概率，移除动态物体，因为动态物体所经过的栅格占用概率较低。所以作者就结合二者的优点，做了本文中提出的方法。

在结合二者进行设计的同时，需要对两种方法本身各自进行一些优化或适应性改进。

对NDT来讲，由于每次有新的点云到来时都要对每个grid的的表示(包括均值和方差)进行计算，这样给地图更新带来很大的麻烦，不仅运算量大，而且要把点云中所有的点存下来，以备下次更新时使用，而我们真正进行匹配的时候，需要的并不是点，而是均值和方差。如果能够增量式更新，对每个grid，当有新的点云到来的时候，可以在原来均值和方差基础上进行叠加，不就同时解决这两个问题了吗？

对于栅格地图来讲，我们所使用的栅格地图多是二维的。当有雷达的点落在栅格中时，就增加它的占用概率，反之，就减小它的概率，而对于三维来讲，就会带来问题，至于是什么问题，该怎样解决，我们在后面的详细介绍中一一展开。

二、方法实现

我们要实现的就是上面介绍的那两个问题的解决办法，NDT一个，栅格地图一个。

1. NDT增量式更新

目的我们刚才已经说了，就看方法了。

传统NDT每个grid的均值和方差计算公式如下

更新地图时就按照这个公式再重新计算一遍。

而所谓增量式更新，就是如果原来地图已经有了计算好的grid的均值和方差，当新来一帧点云时，先对这一帧进行均值和方差计算，然后直接用二者的计算记过去计算新的地图的均值和方差，公式如下

其中m和n分别是grid中地图和单帧点云的点的数量。

公式的证明过程在论文里，感兴趣的可以自己去看一下。

所以有了上面这两个公式，我们再更新地图时就不需要存储所有的点了，只需要存储每个grid均值、方差和点的数量就可以了。

这样的方法还有另外一个好处，就是我们有时候并不需要这么高分辨率的grid，只需要低分辨率的就可以，在计算低分辨率的时候，就直接使用高分辨率的结果就行，因为多个grid按照上面的公式一叠加不就是一个更大的grid吗

2. 占用栅格地图

我们上面提到在使用3D雷达建立三维栅格地图时会带来问题，我们现在就来具体说说有哪些问题：

1)栅格的miss判断。

对2D栅格地图比较了解的朋友应该知道，栅格是用占用概率表示的，而占用概率是根据每一帧点云在该栅格上有没有点来更新的。当有点落在栅格上时，这个栅格就是被hit，就增加它的概率，这时候在雷达和被hit的中间，沿着激光束的方向，这条线经过的所有栅格里自然就没有物体存在，这些栅格就是被miss，要减小它的占用概率。

对于三维来讲，hit的判断是不变的，而miss的判断如果还用原来的方法就会带来一个问题，如果雷达和hit的点之间的连线只经过了grid的一小部分，比如边缘部分，如果也被当成miss，就有点冤枉，因为有可能这个grid的其他部分是有被占据的。

这时候肯定有人会说，这个问题在2D中同样存在呀。确实是，所以此处对这个问题我是这么理解的，它确实不是3D独有的问题，但可能在三维空间中这种被冤枉的概率更大，影响更严重。另一方面，如果把解决这个问题的方法也应用到2D中也不是不可以，从理论上也能起到一定效果。

不管怎样，我们要解决这个问题，方法很简单，就是一个公式。

在这个式子里，Np是栅格被hit的次数，当被hit时，更新和之前的栅格更新方式是一样的，当Np=0时，也就是在原有的判断方法中被判断为miss时，这地方做了一些改进，加入了Ne这个量，它表示被miss的次数，可以直观理解为，这个grid不仅要被miss，还要被多次miss时，我们才会明显降低它的被占据概率。

到这里，本论文里两个核心点就解释完了。下面我们看看效果。

三、实验效果

作者给出了一张图，是在一个工厂车间建的图，同时给出多种方法的对比

在这张图离，e)就是车间真实环境，a)是作者所提出的方法建的图，c)中白色部分是a)那张图里的空栅格，即被占据概率特别低的栅格，d)是a)的低分辨率显示效果。

我们需要重点分析的是a)和b)的对比，这里b)是只加了改进NDT，而未加栅格判断的方法，我们上面提到，栅格就是为了移除动态物体，所以b)图中多出了红色部分，那些就是动态物体在NDT的grid中留下的身影。