cartographer论文翻译
初衷
因为自己看了两天论文毫无头绪，就想着那就先把这篇论文翻译一下，然后加上自己的一些理解。看看能不能得出点啥来。
摘要
便携式激光测距仪(也就是LIDAR)以及实时定位和绘图（slam）都是比较有效的一种建立平面图的方法。实时生成和绘制平面图能很好的评估捕获的数据的质量。因此建立一个在有限的资源下可接入的平台是非常有必要的。这篇论文提供了一种在mapping 平台后台使用的方法来实现5cm分辨率的实时绘图和闭环检验。为了达到实时闭环检测，我们使用了分支上界法来计算scan-to-map的匹配作为约束。
一、介绍
建立平面图对于各种应用都是非常有用的。吧啦巴拉巴拉….(以上是一些简单的关于这些技术的重要性的介绍。这部分不做翻译，相信大家的水平也是可以理解的，因为我都理解了。嗯，就是这样的)。但是需要说明的一点是：SLAM并不是这篇论文所主要的研究，这篇论文的contribution在于减少了计算量，提高了计算效率，对于大平面图更加适用。
二、相关工作
这里涉及到几种的匹配算法：
- scan-to-scan matching：会累计误差，最终误差会很大
- scan-to-map matching：减少了误差的累计（本篇论文使用方法）
- pixel-accurate scan matching：最后有说这个算法在后台用于将scan点集和最近的submap进行匹配，生成loop closing的约束条件。
解决局部误差的累计有两种方法：一种是粒子滤波法，一个基于图的SLAM方法（graph-based）。这篇文章使用的是后者。讲一下关于graph-based的吧。
graph-based是一种工作于基于位姿和特征的集合的方法。图中的边表示从观察结果中生成的约束，节点表示的是位姿和特征。对于优化由约束引进的误差有很多方法，比如文中的参考文献11，12。对于室外绘图的系统使用详情见参考论文13。
对于第二部分也就不多解释了，接下来重点来了！第三，四，五部分是这篇论文的核心，基本的理论知识阐述！非常重要，重要到我都没看明白就只能先翻译一下了。
三、系统概述
google的cartographer提供了一种室内实时绘图的解决方法，这种方法是基于激光雷达的。绘制的是2D图像，分辨率是5cm。激光数据scans会以最佳的位置插入到submap中，这个最佳的位置假设在一段时间内是很准确的。scan matching必须是和它相对应的submap进行匹配,所以它只和最近的scan点集有关。（？？这部分有些疑问，是这么理解吗？还是说scan matching必须在submap之前进行匹配？）对于位姿的估计误差会在全局的帧当中积累起来。
综合硬件等条件，这篇论文使用的是pose optimization来处理误差累计（如何使用pose optimization实现累计误差的优化?????接下来讲的是关于位姿优化算法？？）当一个子图构建完成之后，不在有其它的scan插入这个子图当中，这个已有的子图会用来作为loop closing的scan matching。所有子图和scan点集都会被用来进行loop closure。如果他们（ 他们指的是submap和scan，还是scan和scan，还是submap和submap？？？）离的足够近的话，那么就会尝试在子图中找到相应的scan。
当一个新的laser scan加入到地图中时，如果该laser scan的估计位姿与地图中某个submap的某个laser scan的位姿比较接近的话，那么通过某种 scan match策略就会找到该闭环
以上是对泡泡机器人公众号的文章引用的一段话。泡泡机器人文章
如果在当前估计位置的窗口范围内找到一个足够好的匹配结果，那么这个匹配结果就会被用来作为优化问题的闭环检测约束条件。（匹配的结果？指的是什么？也就是需要存储什么？）每隔几秒就进行闭环检测，按照经验来说，就是一个位置点被重复访问之后就算达到闭环了（这个重复访问是如何判断的，两个位姿的距离足够小？？）这样的判断要求闭环检测必须在新的点被加入到submap中之前完成。如果不是，可能会导致失败.为了达到这样的目的（之前提高的必选检测在前的目的？？）,通过使用分支上界法以及对于每个完成的submap有对应的几个预处理的网格（several precomputed grids per finished submap）.
四、局部二维的实时定位和绘图
这个系统实现2DSLAM结合了局部的和全局的方法，局部和全局的方法都对LIDAR观测到的位置进行了优化。位置的表示
这个位置表示包括(x,y)坐标的转化，以及角度的旋转，实际上就是对scan点集的优化。平台采用的是IMU测量方向，然后将其映射到2D平面上。
在这篇论文的局部方法中，每个连续的点集被拿来和整个地图的一部分进行匹配，就是和submap进行匹配。使用一种非线性的优化方法将submap和scan点集联系起来，这也是scan matching的过程。局部方法积累的误差在之后的第五部分的全局方法去掉。
1、scans
submap的构建是不断的校准点集和submap的坐标。文中将点集表示成H=
，这个scan点集的在submap点集的位置被表示成
，这个位置转为submap的位置方法如下： 
2、submaps
一个submap是由连续的几个scans建立的，这些submap采用的是概率网格M :
这个代表着离散网格点中概率值（这个部分真没懂是怎么样的映射关系）。这个值可以作为表示这个网格是否为障碍物的概率。对于每个网格点，论文中都定义了一个相应的像素，这个像素包含了所有靠近这个网格点的scan points。
无论什么时候一个scan点集被插入到这个概率网格中，一个包含网格点的hits集合以及一个miss集合都会被重新计算。对于每一次的hit，我们将这个最近的网格点加入hit集合，对于每一次的miss，我们将每个像素关联的网格插入这个miss集合，对于已经在hit集合中的网格点不需要插入。
对于每一个之前没有观察到的网格点都会根据他们所在集合是hit还是miss赋予一个概率值
如果一个网格点已经被观察到了，我们将会更新这个概率值。通过以下的方式（hit的修改）： 
对于miss的网格点的修改也是同样的。贴出论文中的图： 
灰色的网格代表的是一次scan点集的范围，黑色的点表示hit（是障碍物的）的网格。
3、Ceres scan matching
在将一个scan点集插入submap中之前，这个scan点集的位置必须使用Ceres-based的scan matcher的方法进行优化（这个优化是相对于submap的位置）。这个scan matcher目的是为了找到一个点集位置，这个点集的位置在submap中的概率最大，将其作为一个非线性最小二乘问题。如下： 
公式中的各个符号解释自己看啦！对于M这个函数，这篇论文中使用的是双三次插值法（bicubic interpolation）。这个函数的数学优化往往比网格分辨率优化有更高的准确性。因为这是一个局部的优化，所以一个好的初值很重要。IMU被用来测量scan match中的角度旋转参数theta。一个高概率的scan matcher 或者一个高的pixel-accurate scan matching方法会被用来弥补IMU不能使用的情况，尽管复杂度很高。
五、闭环的实现
因为一个submap是有少数的几个连续scan点集生成的，所以误差很小。这篇论文中优化所有点集和submap位置的方法使用的是Sparse Pose Adjustment（参见原论文的[2]）。一个scan点集呗插入submap中的这个相对位置会被存储下来，用于之后的闭环优化。除了这些位置信息，还有的包含scan点集和submap，而且这个submap不再变化的时候，都会被用来作为闭环检测。一个scan matcher一直会在后台不断的运行，当一个好的scan match被找到之后，这个相应的位置也会被加入到优化问题中。
1、优化问题
闭环的优化，就像scan matching 一样，也被表示成非线性最小二乘问题。每隔几秒，就会使用Ceres计算一个解决方法。计算方式如下： 
同样，符号的表示我也不一一阐述了。自己看吧~
其实这个就是一个损失函数，比如Huber loss等等。使用损失函数的目的是减少加入到优化问题中的离群点对于系统的影响。
2、Branch-and-bound scan matching
对于优化的，pixel-accurate match还是非常感兴趣的。这个匹配算法公式如下：找到最佳的位置点 
，其中的W表示的是一个窗口大小，M是之前M函数一个延伸。这里的含义以及包括接下来的算法1的含义，在我理解看来就是在一个新的scan点集的周围画一个圆（窗口），然后不断的修改x，y，以及角度来找一个最佳的位置。这个位置的修改不能超过一定的范围。这个范围是点集的最大范围。同时角度变化step也设置如下： 
以上的这些参数都是算法中涉及的。
其实呢，个人觉得这个算法的思想就是不断的在窗口内找到这个最佳位置。
但是这篇论文呢，并没有采用这种方法（真的要注意啦！只是介绍了这种方法，但是并木有采用）采用的是分支上界法来计算这个最佳位置。这个算法就是算法2了。分支上界法就是每个分支代表一种可能。使用DFS找到最佳的那个位置即可。他和算法1一样都是解决的相同的问题。只不过这个节点的score是可能的最大值而已。为了达到一个实际的算法，需要分为以下几步：节点选择，分支，计算上限。对于这三步，论文中有具体讲解。节点选择采用的是DFS，对于分支算法，采用的是算法2。算法3是将节点选择和分支结合到一起之后的算法。
对于计算上限的地方，采用的是提前处理的网格：
，预处理的每个网格有一个初始假设高度，能够让我们计算这个scan的score。至于接下来的计算过程。我就自动忽略了，因为实在是没get到！泪崩~
实验结果部分自动忽略了翻译。嗯，可以自己去看。
总结
这篇论文阐述了一个2D的SLAM的系统，这个系统采用了闭环检测的scan-to-submap matching，同时还有图优化（graph optimization）。一个submap的创建是使用的是局部的，基于网格的（grid-based）SLAM方法。在后台，所有的点集与相近的submap的匹配使用的是pixel-accurate scan matching的方法，然后建立闭环检测的约束。这个约束图（基于submap和scan pose的）都会周期性的在后台被更改。这个操作是采用GPU加速将已完成的submap和当前的submap进行结合。
以上，就是这篇文章的大概了。整个系统图可以盗用一下作者jsgaobiao的博客里面的图： 
上图中对于scan与scan集合成submap采用的是grid-based 的SLAM方法。生成约束关系的scan和submap的匹配算法采用的是pixel-accurate scan matching的方法。目前还没看代码，不是很清楚这部分。
以上就是我读完整篇论文的结果了，果然做科研是需要智商的，我的智商还待修炼~