SLAM（Simultaneous localization and mapping）,我们要达到的目的就是估计机器人（传感器-比如相机）的位置轨迹，然后创建地图。locating和map两者互相依赖，密不可分。然而我们已知的信息一个是observation，即传感器收集到的信息（现在研究的多的一般是基于RGB-D相机的，比如微软Kinect，因为不仅能收集到深度和颜色信息，而且比以前laser scanner等轻巧便宜）；还有一个就是我们施加给机器人的control commands.我们要解决的就是通过这两个已知，去估计位置和地图这样一个问题。表达成概率问题如下：



Map形式的有好多种。最传统就是去重建一些landmark,用Extend Kalman滤波器（EKF）去估计landmarks以及机器人的位置，是第一个SLAM的有效的解决方案。其他的map representation比如occupancy grids也比较常见，是把要重建的环境表达成网格的形式，通过比如Bayes滤波器family中的某种可以计算每个小格被占用的概率，来还原地图。在S. Thrun. 的《Robotic mapping: A survey》中有详细的说明，如下表列举了一些主要的算法以及相关特性。这个在2002年就发表了，也算比较老了，但许多描述都是SLAM的重要基础。



SLAM一个重要的首先要解决的问题是registration的问题，我的理解是把不同角度采集到的数据整合（alignment）到一个坐标系中。针对两组数据（比如两幅不同角度采集的画面），可以点对点的进行匹配，寻找他们之间的transformation从而进行数据alignment并进行对sensor的定位，一个重要的算法是ICP（Iterative closest point ）。

（Example: Aligning Two 3D Maps）

从registration的角度，很多研究有把SLAM的问题分成dense和feature-based两种（如下图），前者（右图）多是对密集的点云（point cloud）通过ICP来进行点对点alignment ，这种做法比较准确，把所有的数据都联合起来就可以得到地图与sensor的轨迹。但因为纯是点对点运算，可能会丢失一些画面中属于画面特征的重要信息。所以feature-based也被广为应用，我们提取出SIFT,SURF等图像特征，再对这些特征进行alignment，算法比如RANSAC，可以实现对特征的联合。但针对特征不明显的环境，比如深夜环境，特征的办法就没有dense的办法有效了。两种方法都可以实现对数据的registration，也有一些项目是结合两种方法的。



（来源 http://vision.in.tum.de/research/vslam）

除了registration，SLAM（主要是graph-based SLAM）还有一个重要的待解决问题是Loop Closure Detection（闭环检测？），它是检测新的观察到的环境来确定自己是不是到了一个曾经到过的地点， 以消除localization的不确定性。因为如果一直是通过对不同角度采集到的不同画面（不同帧）一步一步的进行联合来估计sensor的位置的话，这个定位误差会累积，多以loop closure意义重大，这里不展开了。

接下来我们需要对地图的整体构建进行optimization,这是关键一步。我们要解决将特征点re-project回3D空间时的误差最小化问题，这就是bundle adjustment（BA）问题，用到least square等算法，最小化误差。g2o便是一个解决SLAM或者BA中这个误差最小化问题的框架，原话是：an open-source C++ framework for optimizing graph-based nonlinear error functions。另外还有TORO，是通过梯度下降实现graph中constraint带来的误差从而达到优化的有效算法。

最终我们要的3D地图，有颜色，有表面，可能质地也可以展现出来。这是map representation的问题，相关的方法有Surfel，Volumetric Representation(代表KinectFusion)，Mesh，等等...