王忠立，赵 杰，蔡鹤皋

(1.北京交通大学电子信息工程学院，100044北京;2.机器人技术与系统国家重点实验室(哈尔滨工业大学)，150080哈尔滨)

近年来，同步定位和地图构建(SLAM)逐渐成为机器人领域研究的热点问题，被认为是实现移动机器人自主化的核心技术［1］.对SLAM问题的研究，最早可以追溯到上世纪80年代.Standford大学的Smith等［2］发表了关于SLAM问题的开创性论文，论文以空间不确定性描述及变换的表示方法为研究内容，并提出了随机地图的概念.到1991年，Leonard等［3］正式提出SLAM概念.SLAM方法的理论意义和应用价值逐渐引起了众多学者的关注.在1999年的ISRR国际会议上，第一次有SLAM专题研讨会［4］.近些年来，每年的机器人国际会议(ICRA、IROS、Robio等)都有SLAM专题讨论，同时机器人领域的一些国际期刊，也不定期推出SLAM专辑.由此可见国内外学者对移动机器人SLAM问题的关注程度.Durrant等［1］对该问题的早期研究方法进行了总结，并对SLAM问题的结构、收敛性等开放性问题进行了讨论.图1是到目前为止，根据所用的传感器种类、地图类型、主要算法以及应用环境类型对SLAM的研究方法进行整理分类的结果.

图1 SLAM的主要研究方法

SLAM本质上是一个系统状态(包括机器人当前位姿以及所有地图特征位置等)估计问题.从这一角度，其求解方法可大致分为基于Kalman滤波器的方法、基于粒子滤波器的方法、基于图优化的方法3类.

基于Kalman滤波(KF)和粒子滤波(PF)的方法主要依据递归贝叶斯状态估计理论.从初始时刻起到当前时刻t的观测信息以及控制信息均已知的条件下，对系统状态的后验概率进行估计(由于PF方法是一种非参数化滤波器，这里将其单独作为一类).根据后验概率表示方式的不同，提出了多种基于KF的方法，如EKF-SLAM方法［5］、UKF-SLAM方法［6］、扩展信息滤波(EIF)方法、稀疏扩展信息滤波(SEIF)方法［7］.基于KF的方法，在满足高斯分布假设，系统的非线性较小时，能获得较为满意的效果.基于PF的SLAM方法中，有代表性的算法包括Doucet等［8］提出的基于Rao-Blackwellized粒子滤波器(RBPF)方法.该方法假定地图特征点之间彼此是独立无关的，仅通过机器人的轨迹关联，将SLAM问题分解成机器人路径估计后验概率和地图部分的后验概率两个后验概率的乘积形式.通过分解使基于PF的SLAM方法的计算效率大大提高.基于RBPF，Montemerlo等［9］提出了FastSLAM方法，并通过进一步优化提出了FastSLAM2.0［10］.FastSLAM是基于PF的SLAM方法的代表，国内外不少学者在此基础上，对该方法进行了局部改进和完善，使该方法在室外小规模环境下也能得到比较满意的效果.和基于KF的方法相比，FastSLAM方法能用于非线性系统.基于递归Bayes状态估计理论的方法具有相似的计算框架，即根据机器人系统的运动模型和传感器的观测模型，在HMM的假设下，实现系统状态的预测更新和观测更新.可以实现地图的在线更新，具有较好的实时性.但这类滤波方法多采用增量式的地图创建过程，由于系统参数和传感器观测等存在的不确定性，会造成误差的逐渐累积，最终可能导致地图的不一致性.在大规模环境中应用时，基于递归Bayes状态估计方法很难保证地图的一致性和精度.

随着SLAM问题研究的深入，其应用逐步从小规模环境向大规模环境发展.基于图优化的SLAM方法，由于采用了全局优化处理方法，能获得更好的建图效果，是大规模环境下SLAM问题的主要研究方法，也是目前国内外学者研究的热点方法.

国外学者对该类方法的研究已经非常活跃，但国内学者对该类方法的研究相对较少.针对这一现状，本文对该类方法的建模原理、基本实现框架等进行介绍.基于图优化的SLAM方法涉及到的内容较多，国外一些学者通常将这类方法划分为前端和后端两大部分.前端主要解决图的构建问题，而后端则主要是基于图的优化估计.这一划分有助于理解基于图优化SLAM方法的基本框架，因此本文也遵循这一划分方法.值得一提的是，在现有的图优化方法概述文献中，绝大多数集中在后端的优化方法上，假设前端的图构建过程已经完成.但笔者认为，作为一个完整的SLAM系统，前、后端是密不可分的.另外，前端所涉及到的问题很多是SLAM的经典问题，如数据关联等，尽管已经有多年的历史，但还远未得到很好地解决.因此本文先将重点放在前端相关研究方法的总结上.

本文主要对基于图优化SLAM方法的建模基础(3种图描述方法)、帧间数据关联和环形闭合检测方法等进行总结.后者是前端部分研究的核心.由于数据关联和环形闭合检测与系统所使用的传感器有关，本文仅侧重于视觉的方法.除了对上层的方法进行分类介绍之外，也对特征提取、特征匹配、运动估计、环形闭合检测等内容的具体方法进行总结，在对相关方法的介绍中加入了最新的研究成果.目的在于让读者对该类方法有一个全面而具体的了解.

1 基于图优化的SLAM方法框架

1.1 SLAM问题的最小二乘描述

基于概率的SLAM方法，其核心是根据里程计等提供的运动模型和观测器的输入对机器人位姿及路标点位置的最大后验概率估计问题(MAP)，即

式中:U包括运动控制输入(ui)、环形闭合检测(uij)，X为待估计的机器人位姿及路标点位置．为求解式(1)右边的联合概率分布，可将其分解为

式中，后验概率的计算分解为里程计提供的运动模型约束和环形闭合检测提供的环形闭合约束.在高斯分布的假设下，对式(2)两边取对数，得

从式(3)可看出，基于图优化的方法将SLAM问题视为最小二乘优化求解问题.

1.2 基于图优化的基本架构

基于图优化的SLAM方法，利用图模型对SLAM问题进行建模.模型中的节点对应于机器人及环境组成的系统在不同时刻的状态，边则描述了系统状态(节点)之间的约束关系［11］.这类方法将SLAM问题划分为前端(front-end)和后端(back-end)两个部分，如图2所示.前端完成图的构建，即根据观测和系统约束构建图的节点和边;后端主要完成图的优化.基于图优化的方法利用所有的观测信息来优化估计机器人完整的运动轨迹，并在此基础上，进一步得到环境地图，也称为全SLAM方法(full SLAM).

图2 基于图优化的SLAM框架

在前端部分，顺序数据关联是指相邻观测数据帧间的匹配及相对姿态估计问题，而环形闭合检测则根据观测数据判断机器人是否处在之前已访问过的环境中.这两部分都与观测数据密切相关，从数据处理的观点来看，二者的核心是要解决数据关联问题，前者考虑局部数据关联，而后者则涉及全局数据关联.从基于图的表示上看，顺序数据关联与环形闭合检测都是根据观测信息建立图节点间的约束，即完成图的构建，是基于图优化方法前端两个核心部分.

由于观测噪声以及数据关联误差的存在，前端得到的图往往存在不一致性.若用Ti来表示数据帧间的相对变换矩阵，而且若T0，T1，…，Tn构成一个闭环，在理想情况下，应当满足

式中Ⅰ为单位矩阵．但通过观测信息关联得到的相对变换矩阵通常不满足该约束．在基于图的形式化表示中，机器人的位姿是待估计的随机变量，位姿间的约束则是与随机变量相关的观测，那么图优化结果则对应于位姿的最大似然估计．与顺序数据关联及环形闭合检测不同，图优化部分一般不直接处理观测数据，而是在前端构造图的基础上进行优化．

1.3 图建模方法

SLAM问题可以很方便地用不同类型的图来建模.目前主要有3种类型的图结构:1)基于动态贝叶斯网络的图建模方法;2)基于因子图的建模方法;3)基于Markov随机场的建模方法.

1.3.1 DBN建模方法

自1988年Dean和Kanazawa提出动态贝叶斯网络(DBN)的概念直到现在，DBN方法已经在计算机视觉、模式识别和信号处理等领域得到广泛的研究和应用，其相关的理论仍在不断发展中.DBN是一种有向非循环图，可以很方便地表示随时间变化的随机变量及其相互之间的条件依赖关系.基于DBN描述的图中通常有两类节点:可观测变量对应的显式状态节点和不可观测变量对应的隐式状态节点.图3就是基于DBN描述的SLAM图结构.在图中，灰色节点代表可观测变量，如机器人的控制输入ut(t=1，…，i)，路标mt的观测输出zt(t=1，…，i+1);白色节点代表DBN中的隐式变量，如机器人的位姿xt(t=1，…，i+1)，路标的位置mt(t=1，…，i+1)，这些变量是不可观测的．图中的边表示两个节点之间的条件依赖关系．

图3 静态环境下基于DBN的SLAM描述

Russell等［12］对DBN的推理方法进行了介绍.Thrun在他的经典专著《概率机器人学》［13］中，对DBN在SLAM和状态估计中的应用做了较系统的阐述.

1.3.2 基于因子图的建模方法

因子图是一种二部无向图，由Kschischang等［14］在2001年提出.在利用因子图对SLAM进行建模时，可以将SLAM的联合概率分布估计分解为多个因子的概率分布的乘积.根据其图中是否包括路标位置节点可分为两类:有路标因子的因子图和无路标因子的位姿图.后者即为位姿图(PoseGraph)，是目前基于图优化方法中研究的最为广泛的一类表示方法.

式中:p(xi|ui，xi-1)为机器人位姿的概率分布，lk为构成地图的各个路标的位置，p(lk|xi，zj)为路标节点的概率分布．

在因子图中，有两类节点:第1类为表示变量的节点，如图4(a)中机器人的位姿xt(t=1，…，i+1)和路标的位置mt(t=1，…，i+1)，以及表示变量之间的概率关系的因子节点(空心小圆点)．图4(a)是和图3对应的有路标节点的因子图表示方法，在该图中，里程计因子用实心小圆点表示，而路标观测因子用空心小圆点表示．图4(b)是没有路标因子节点的因子图表示方法，在该图中，用一个因子(空心节点)来表示非连续机器人状态之间的环形闭合因子．

图4 基于因子图的SLAM描述

1.3.3 基于MRF的建模方法

MRF建模与因子图类似，都是无向图.在因子图中，变量节点之间有因子节点，但在MRF图建模中，只有变量节点.因此，在MRF图中，只有变量节点之间的边，没有变量节点和因子节点之间的边.两个节点之间如果有边连接，表明两个随机变量之间有依赖关系，如果两个节点没有边连接，则说明它们之间是彼此无关的.图5是和图3对应的MRF图结构.在该图中，有两类变量节点，即机器人的位姿xt(t=1，…，i+1)和路标的位置mt(t=1，…，i+1)，节点之间的边是无向的，表示节点之间的依赖关系．

图5 基于MRF的SLAM描述

在因子图中，可以用先验因子的方式表示一些先验知识对变量节点的约束，但MRF不能描述这种先验约束，否则这些因子图中的“先验因子”在MRF中会形成单边(open edge).在MRF图结构中，采用邻接矩阵来求解最小二乘问题，邻接矩阵和优化问题中的Hessian矩阵是等价的.

上述3种图模型的描述方法中，因子图中的PoseGraph是应用较多的一种图模型.但笔者认为，在描述一些复杂环境下的SLAM问题，如动态环境SLAM问题中，基于DBN的模型具有更大的优势.但对有关问题的研究，正在逐步展开.

2 顺序数据关联

顺序数据关联是要建立前后两个连续帧间特征点的对应关系并求解帧间的相对运动(变换)，从而可以将不同位置下的观测结果转换到一个全局坐标系中，以实现机器人自身位姿和环境中的路标(或特征点)在全局坐标系下的表示.

根据所使用的传感器不同，相邻两帧之间、环形闭合检测的数据关联方法也不同.在SLAM的研究中，采用激光扫描/雷达、Kinect、RGBD、立体视觉等这类传感器可以获得3D观测结果，其数据关联方法主要采用迭代最近点(ICP).单目摄像机是一种Bearing-only传感器，需要机器人在两个或以上的位置获取的信息才能确定空间点的坐标.基于单目视觉的3D重建及运动估计是计算机视觉领域中经典的从运动恢复结构(structure from motion，SFM)问题.也正是从这个意义上，很多学者将SFM和SLAM问题视为等价问题.也可以将多种传感器结合起来，基于多传感器的信息融合实现数据关联.

2.1 基于3D的数据关联方法

假设前后两帧得到的数据集分别为pi(i=1，…，N)和pj(j=1，…，M)，数据关联的主要任务是:1)两帧中数据点对应关系的确定;2)根据对应关系，求解两帧之间的齐次变换关系(运动估计).

对应关系的确定一般通过最近邻(nearest neighbor，NN)方法.求解最近邻的一般方法是逐个比较，由于需要确定N个数据的对应点，其时间复杂度为O(MN)．K-D树通过树型结构来描述空间点的分布，可用来加速最近邻点的查找［15］.

因此，可以通过定义一个误差最小化函数进行优化求解:

式中:Ti为要求解的变换矩阵．这一步实际上是要解决已知对应关系情况下相对变换的求解问题，其中较为常用的是基于SVD分解的求解方法［16］.Eggert等［17］对这一问题的4种解析求解方法进行了比较.

式(4)采用了变换后的点到实际点之间的距离误差作为优化目标函数.从优化求解的角度，还可以定义其他形式的误差函数，如Yang等［18］采用点到面的距离减少迭代的次数，加快收敛速度;Segal等［19］提出面到面的距离来定义目标函数，提高了配准的精度及鲁棒性.

ICP方法采用迭代的形式，对建立的对应关系和相对变换矩阵进行逐步修正.在迭代过程中，对应关系和相对变换都会被不断地更新，二者相互影响，一般经过若干次迭代后会收敛到最优解.该方法需要一个初始值来启动迭代过程，如果前后两帧运动较小时，可以用单位矩阵作为初值(T0=Ⅰ)．但如果初始值和最优解之间的距离较远，初始值选取不适当时，优化过程往往陷入局部最小值中，导致错误的收敛结果.

在ICP方法的基础上，一些学者从可靠性、计算量等方面提出了改进的方法.如Turk等［20］通过均匀采样进行控制点选取以减少计算量，Zhang等［21］采用了设定阈值的方法对错误匹配进行剔除，Godin等［22］根据点间距离给每对对应点赋予不同的权值以减小误差较大值的影响，Fitzgibbon等［23］直接采用非线性优化方法对问题进行求解，并通过实验验证其结果与基于解析求解的方法具有更好的效果.文献［24-25］对ICP进行了全面的综述.

2.2 基于2D的图像关联方法

基于2D的图像关联方法是指对图像序列中前后两帧图像进行处理，得到机器人运动估计及环境的结构信息.从图像序列估计运动有多种方法，如基于光流的运动估计方法以及基于特征点匹配的方法等.基于光流的方法由于计算量大及其他问题，在SLAM中极少采用.在单目视觉SLAM中，绝大多数采用基于特征的地图表示，因此这里主要对基于特征的运动估计方法进行分析.对该问题的研究，是计算机视觉领域中经典的从运动恢复结构(SFM)问题［26］，也有学者将其等同于视觉里程计［27-28］的研究.但笔者认为，后者侧重于机器人定位估计，忽略了对环境特征点位置的优化估计，因此更倾向于前者的说法.基于2D图像特征的运动估计一般包括特征检测、特征匹配，以及运动估计3个步骤.

2.2.1 特征检测

在基于特征的视觉SLAM中，特征检测是至关重要的环节.对图像进行特征提取，需要考虑特征的准确性、显著性、鲁棒性以及高效性等.一般而言，这些特性的性能越高，对特征的匹配就越有利.在计算机视觉的开源代码OpenCV中，实现了多种特征的提取方法，如Harris角点［29］、Shi-Tomasi角点［30］、SURF角点［31］、STAR关键点［32］(即CenSurE)、FAST关键点［33］等.SIFT检测［34］、MSER区域检测［35］.

Khairulmuzzammil等［36］以及Khvedchenia等［37］考虑了特征提取的速度、质量、光照和尺度不变性等因素，对常见的几类特征(主要是FAST，Shi-Tomasi(GFTT)、MSER、STAR、SIFT、SURF)进行综合比较.不同特征提取算法对Barbara、Lena、Peppers、Mandril这4幅测试图像进行对比实验.图6分别给出了各种算法在以下几方面的比较:1)检测得到的特征点数;2)算法复杂度;3)将提取特征用于LKT跟踪时的平均跟踪误差;4)用于LKT跟踪时跟踪成功的特征数;5)对光照变化的稳定性.从这些对比来看，特征提取在准确性、显著性、鲁棒性、高效性等方面存在一定程度的冲突.例如，如果要求特征的显著性好，其鲁棒性可能就稍差，反之亦然.

图6 不同特征提取算法的比较［37］

在上述几种特征中，SIFT具有较好的重现性、准确性及鲁棒性，已成功应用于物体识别、目标跟踪、场景分类以及视觉里程计等问题中，具有较好的实验效果.但SIFT特征提取的方法计算复杂度很高，SURF在SIFT基础上进行了简化，采用格子滤波来近似高斯滤波，大大提高了计算效率，但在鲁棒性上比SIFT稍差.

BRIEF特征描述子［38］和SIFT一样，考虑了对光照变化、模糊、畸变等，但对旋转变化比较敏感［36］.基于BRIEF描述子的这一不足，Rosten等［39］提出了改进的FAST方法.Rublee等［40］提出的ORB方法则综合Fast和BRIEF两种方法的优势.

室外大规模环境下特征的提取受光照、环境的动态变化等多种因素的影响，是一个非常复杂的任务.已有的方法都有一定的局限性.

2.2.2 特征匹配

特征匹配的可靠性和稳定性对SLAM的结果有决定性影响.在SLAM的方法中，为了实现前后两帧之间的特征匹配，有两种不同的思路:1)只对前一帧图像进行特征提取，并依靠Bayes推理方法预测这些特征点在下一帧图像中的对应点位置.因此只需要在预测位置附近进行局部的搜索，如主动匹配(Active Matching)方法［41］.由于只需要进行局部搜索，具有速度快、稳定性好等优点(较少出现匹配不一致的情况).不足之处是只能用于两帧图像变化较小的情况.2)分别对两帧图像进行特征提取，然后依据特征的相似性建立起对应关系.对每个特征作全局的查找，对帧间变化较大时也具有较好的适应性.但如果特征提取方法的计算复杂度较高，对整幅图像进行处理时效率低，而且根据相似性准则进行对应点的关联时，也会出现匹配不一致的情况.可以通过随机采样一致性［42］或者利用几何约束关系剔除错误的匹配.

2.2.3 运动估计

建立了特征点的对应关系，在已知摄像机的成像模型的基础上，可以实现传感器运动的估计.在SLAM问题中，运动估计实际包括摄像机的运动估计、特征点的位置估计两个任务.这两个任务是紧密联系、相互依赖的.对于空间3D特征点和6DOF的运动估计，利用两帧图像建立的对应关系估计运动时，在摄像机内参数已知的情况下，可以通过两幅图像之间的本质矩阵E的分解计算得到摄像机的运动.这类方法在计算视觉领域中得到深入研究［43-44］.其中，因子分解法是研究得较为广泛的一种方法，自1992年Tomasi等［45］提出该方法之后，一些学者对其进行了扩展，提出了如平行透视成像模型［46］、透视成像模型［47］等条件下的因子分解问题，以及序列图像的因子分解方法［48］，Irani等［49-50］则对因子分解中的不确定性问题进行研究.

E矩阵是一个与比例因子有关的3×3矩阵，从矩阵计算的角度，需要8个点就可以计算E矩阵，基于这一思想，Hartley等［51］提出了8点法计算E矩阵，为了减小数据噪声对解精度的影响，一般采用SVD进一步得到运动(R，T)．根据两个视点下的对应关系求解运动参数时，只能得到单位平移矢量，因此，运动参数实际只有5个独立变量，基于此，Nister［52］提出了5点法.如果考虑到移动机器人一般在平面上运动，这时运动可以用3个独立参数描述，通过施加这一约束，基于主动匹配的方法，Civera等［53］提出了单点RANSAC的SLAM方法.前述这些方法主要是基于2帧间的约束求解运动.考虑到多帧(大于2帧)时，能提供更多的约束条件，对运动求解更为有利，一些学者对多视几何下的SFM问题进行了研究［54-56］.

在基于两帧或多帧的运动估计时，通常可以得到较多的匹配点，可以采用优化估计方法来提高结果的精度，如光速法平差(BA).假定特征点{ui}的3D空间点为{pi}，T为前后两帧间的运动变换，则优化目标函数可以采用最小化重投影误差的方法:

式中f(·)为投影变换函数．由于匹配过程中可能会出现错误的匹配点，可通过M-估计子、RANSAC等提高输出结果的鲁棒性.

2.3 基于多传感器融合的数据关联方法

复杂环境下SLAM应用时，针对单一传感器在数据关联等问题上的不足，不少学者对基于多传感器融合的SLAM方法进行了研究.其实在早期的基于激光扫描传感器的SLAM研究中，采用里程计的运动估计作为机器人的运动模型，激光扫描传感器作为观测输入，就已经隐含地利用多传感器融合了.Vasconcelos等［57］提出了摄像机与激光测距传感器的融合方法，并对两个传感器之间的参数标定方法进行了研究.Kunz等［58］提出了利用声纳测距和视觉传感器相结合实现水下环境的地图构建.

目前研究较多的融合方法是将惯性测量单元(IMU)与摄像机相结合.根据融合的信息级别来看，这种融合主要有松散耦合和紧耦合两种模式.松散耦合是在较高信息层次上进行融合的方法，如先利用摄像机相邻两幅图像估计得到相对运动，然后和IMU的运动信息进行融合［59］，或先由IMU输出估计得到旋转运动分量，然后和基于图像特征的运动估计进行融合［60］.松散耦合的优点是计算量相对较小，但这是以损失信息为代价的，在微型飞行器(MAV)这类资源受限的情况下应用较多.紧耦合模式是在两种传感器的特征级别进行融合，如基于融合的EKF-SLAM方法［61］.这类方法能更充分地应用传感器信息，获得更高的精度.在紧耦合模式中，根据融合输出结果可分为视觉-IMU里程计(VIO)和EKF-SLAM两类，前者在状态矢量中只包括了传感器的位姿，后者则将环境特征点的位置(地图)也作为状态矢量参数.

基于多传感器融合的数据关联方法，能够获得更为可靠、精度更高的结果，因此这类方法无论是从理论研究，还是实际应用，均受到越来越多的关注.

3 环形闭合检测

环形闭合检测(简称环闭检测)是图优化方法中非常关键的一部分，也是SLAM问题的一个难点.正确的环闭检测可以修正传感器的累计误差，从而得到一致性地图;错误的环闭检测结果则会对后续图优化造成干扰，甚至可能毁坏已有的地图创建结果，导致地图创建的失败.

环形闭合检测的困难来自于:1)感知的歧义.如场景中存在大量相似的事物，如室内的桌子、椅子，室外的树木、建筑等，增加了判断的难度.2)传感器只能获得环境的部分信息，观测数据的可区分性受限.3)数据规模很大.在进行环闭检测时，需要将当前的观测数据与之前已有的观测数据作比较，计算它们之间的相似性或对它们出自同一地点的概率进行估计.要处理的数据随运行时间或访问过的地点的增加而不断增大，要求能处理的数据规模非常大.

在已提出的环形闭合检测技术中，基于视觉信息的环形闭合检测最为成功.在基于特征的闭环检测方法中，Newman等［62］先通过信息熵检测图像中的显著区域并提取位于区域内的稳定特征，然后利用提取的特征来构建场景数据库.Liu等［63］采用图像的Gabor-Gist描述子，并通过PCA(主元分析)降维，在保留特征的可区分性的同时，提高了计算效率并且节省了存储空间.Zhang［64］利用不同尺度下特征匹配重现性的差异对特征进行选择，用得到尺度不变性视觉特征来检测闭环.Cadena等［65］提出利用条件随机场匹配(CRF-matching)对特征的外观、分布等作一致性检验，并通过实验验证了方法的有效性.

Campos等［66］则提出通过各自的图像聚类方法得到最具代表性的关键帧图像，用以描述地图中的显著地点，以减少存储地图所需的存储空间，并减少匹配定位计算量.Dong等［67］提出了将离线的关键帧选择和在线匹配(实时获得的图像与离线得到的关键帧)采用两个并行处理流程来实现相机实时跟踪的方法，该方法也可以用在环闭检测中.

基于词袋(BOW)法的环闭检测方法，主要思想是将从图像中提取的局部特征进行聚类(如通过K均值聚类方法等)，将连续变化的特征转变为离散化的“词”，然后采用词的统计直方图对场景进行描述.在计算机视觉领域又常被称为视觉词袋(bag of visual word)方法，也称为基于外观(appearance-based)的场景识别方法.Nister等［68］在词袋思想基础上提出基于树型结构的存储和管理方式，从而大大地提升了检索效率.Schindler等［69］分析了词典构造中特征的选取问题，并利用信息增益对特征进行评估，只挑选区分性好的特征进行词典构造，从而使方法的性能和扩展性得到显著提高.Cummins等［70-71］考虑了词与词之间的相互关系，用Chow-Liu树来近似描述它们间的相关性，通过利用上下文信息来减少感知歧义，提出了FAB-MAP方法，被看作是该类方法的代表.Angeli等［72］探讨了增量式词典构造的相关问题.Sunderhauf等［73］基于BRIEF描述子的BRIEFGist方法，该方法比FAB-MAP方法简单，对于大尺度SLAM的前端是一个很有潜力的方法.Zhang［64］通过实验证实，离散化会降低特征的可分辨性，从而可能引起感知歧义.Will等［74］将基于外观的场景识别和局部度量位姿滤波器结合起来，提出了CAT-SLAM方法.与FAB-MAP方法进行对比，CAT-SLAM的闭环识别效果要优于FABMAP方法.Glover等［75］给出了开源的FAB-MAP开发包.Milford等［76］基于SeqSLAM框架，对不同图像分辨率、像素深度、运动模糊，图像序列的长度等条件下的场景识别进行了分析，并指出，单帧或很短时间内的序列图像，在识别时效果很差，随着图像序列长度的增加，识别效果会得到改善.Labbe等［77］提出了一种大规模环境下实时的环闭检测方法——RTAB-Map，通过对已访问过的场景的数据管理，将环闭检测时的数据规模限制在能实时处理的上限之内.CMU机器人研究所的Tully等［78］提出一种混合式地图表示方法，采用贝叶斯方法来估计环闭检测的概率.

4 总结

在对SLAM的研究方法进行全面概括的基础上，对当前大规模环境下SLAM的热点研究方法——基于图优化的方法进行了介绍.本文侧重于总结图优化方法前端部分的相关研究现状.首先对3种图建模的方法进行介绍，然后对基于视觉的前端图构建中的核心问题——顺序数据关联和环形闭合检测进行了全面的总结.在顺序数据关联中，对基于3D的、2D的以及基于多传感器融合的数据关联方法分别进行了介绍，让读者对前端方法有一个全面而具体的了解.

现有的基于图优化SLAM的文献中，主要介绍后端的优化方法，而对前端的总结相对较少，本文的工作是一种有益的补充.

［1］DURRANT W H，BAILEY T.Simultaneous localization and mapping:Part I［J］.Robotics and Automation Magazine，2006，13(2):99-110.

［2］SMITH R，CHEESMAN P.On the representation of spatial uncertainty［J］.International Journal of Robot Research，1987，5(4):56-68.

［3］LEONARD J J，DURRANT-WHYTE H F.Simultaneous map building and localization for an autonomous mobile robot.Intelligent Robots and Systems［R］.Washington:NASA，1990:1442-1447.

［4］LEONARD J J，FEDER H J S.A computationally efficient method for large-scale concurrent mapping and localization［C］//9th International Symposium of Robotics Research.London:Springer-Verlag，2000:169-176.

［5］SMITH R，SELF M，CHEESERMAN P.Estimating uncertain spatial relationships in robotics［C］//Proceedings of the Second Annual Conference on Uncertainty in Artificial Intelligence.philadelphia:Elsevier，1986:435-461.

［6］HOLMES S A，KLEIN G，MURRAY D W.An O(N2)square root unscented Kalman filter for visual simultaneous localization and mapping［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2009，31(7):1251-1263.

［7］THRUN S，LIU Y F，KOLLER D，et al.Simultaneous localization and mapping with sparse extended information filters［J］.International Journal of Robotics Research，2004，23(7/8):693-716.

［8］DOUCET A，FREITAS N，MURPHY K，et al.Raoblackwellised particle filtering for dynamic bayesian networks［C］//Proceeding of the 16th Annual Conference on Uncertainty in Artificial Intelligence.Stanford:Morgan Kaufmann Publishers，2000:176-183.

［9］MONTEMERLO M，THRUN S，KOLLER D，et al.Fast SLAM:A factored solution to the simultaneous localization and mapping problem［C］//Proceedings of the AAAI National Conference on Artificial Intelligence.Alberta:AAAI Press，2002:593-598.

［10］MONTEMERLO M，THRUN S，KOLLER D，et al.Fast-SLAM2.0:An improved particle filtering algorithm for simultaneous localization and mapping that provably converges［C］//Proceeding of the International Joint Conference on Artificial Intelligence.Mexico:IJCAI，2003:1151-1156.

［11］GRISETTI G，KUMMERLE R，STACHNISS C，et al.A Tutorial on Graph-Based SLAM［J］.IEEE Transaction on Intelligent Transportation Systems Magazine，2010，2(4):31-43.

［12］RUSSELL S J，NORVIG P.Artificial intelligence-A modern approach［M］.3rdEdition.Upper Saddle River:Prentice Hall，2003.

［13］THRUN S，BURGARD W，FOX D.Probabilistic robotics［M］.Cambridge:The MIT Press，2005.

［14］KSCHISCHANG F，FREY B，LOELIGER H A.Factor graphs and the sum-productalgorithm［J］.IEEE Transactions on Information Theory，2001，47(2):498-519.

［15］ZHANG Z Y.Iterative point matching for registration of free-form curves and surfaces［J］.International Journal of Computer Vision，1994，13(2):119-152.

［16］ARUN K S，HUANG T S，BLOSTEIN S D.Leastsquares fittingoftwo 3-D pointsets［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1987，9(5):698-700.

［17］EGGERT D W，LORUSSO A，FISCHER R B.Estimating 3-D rigid body transformations:a comparison of four major algorithms［J］.Machine Vision and Applications，1997，9(5/6):272-290.

［18］YANG C，MEDIONI G.Object modeling by registration of multiple range images［J］.Image and Vision Computing，1992，10(3):145-155.

［19］SEGAL A，HAEHNEL D，THRUN S.Generalized-ICP［C］//Robotics:Science and Systems V.Cambridge:MIT Press，2009.

［20］TURK G，LEVOY M.Zippered polygon meshes from range images［C］//21st Annual Conference on Computer Graphics and Interactive Techniques.New York:ACM，1994:311-318.

［21］ZHANG Z Y.Iterative point matching for registration of free-form curves and surfaces［J］.International Journal of Computer Vision，1994，13(2):119-152.

［22］GODIN G，RIOUX M，BARIBEAU R.Three-dimensional registration using range and intensity information［C］//Proceedings of the SPIE.Bellingham:SPIE，1994:279-290.

［23］FITZGIBBON A W.Robust registration of 2D and 3D point sets［J］.Image and Vision Computing，2003，21(13/14):1145-1153.

［24］SALVI J，MATABOSCH C，FOFI D，et al.A review of recent range image registration methods with accuracy evaluation［J］.Image and Vision Computing，2007，25(5):578-596.

［25］RUSINKIEWICZ S，LEVOY M.Efficient variants of the ICP algorithm［C］//Third International Conference on 3-D Digital Imaging and Modeling.Los Alamitos:IEEE Computer Society，2001:145-152.

［26］FAUGERAS O，LUONG Q T，.PAPADOPOULO T.The geometry of multiple images［M］.Cambridge:MIT Press，2001.

［27］NISTER D，NARODITSKY O，BERGEN J.Visual odometry for ground vehicle applications［J］.Journal of Field Robotics，2006，23(1):3-20.

［28］NISTER D，NARODITSKY O，BERGEN J.Visual odometry［C］//IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Los Alamitos:IEEE Computer Society，2004:652-659.

［29］HARRIS C，STEPHENS M.A combined corner and edge detector［C］//Proceeding of 4th Alvey vision conference(AVC88).Sheffield:the University of Sheffield Printing Unit，1988:147-151.

［30］SHI J，TOMASI C.Good features to track［C］//Int Conference on Computer Vision and Pattern Recognition.Piscataway:IEEE，1994:593-600.

［31］BAY H，ESS A，TUYTELAARS T，et al.SURF:Speeded up robust features［J］.Computer Vision and Image Understanding，2008，110(3):346-359.

［32］AGRAWAL M，KONOLIGE K，BLAS M R.CenSurE:center surround extremas for realtime feature detection and matching［J］.10th European Conference on Computer Vision.Marseille:Springer Verlag，2008:102-115.

［33］ROSTEN E，DRUMMOND T.Machine，learning for high-speed corner detection［C］//9th European Conference on Computer Vision，Lecture Notesin Computer Science.Graz:Springer-Verlag，2006:430-443.

［34］MIKOLAJCZYK K，SCHMIDSCALE C.Affine invariant interest point detectors［J］.International Journal of Computer Vision，2004，60(1):63-86.

［35］DONOSER M，BISCHOF H.Efficient maximally stable extremal egion(MSER)tracking［C］//2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.New York:IEEE，2006:553-560.

［36］KHAIRULMUZZAMMIL S，NURUL A，AMMAR A，et al.Comparison of feature extractors for real-time object detection on android smartphone［J］.Journal of Theoretical and Applied Information Technology，2013，47(1):135-142.

［37］KHVEDCHENIA I.Comparison of the opencv feature detection-algorithms［EB/OL］.2011［2014-03-20］.http://computer-vision-talks com/articles/2011-01-04-comparison-of-the-opencv-feature-detection-algorithms.

［38］CALONDER M，LEPETIT V，STRECHA C，et al.BRIEF:binary robust independent elementary features［C］//The 11th European Conference on Computer Vision.Heraklion:Springer，2012:778-792.

［39］ROSTEN E，PORTER R，DRUMMOND T.Faster and better:a machine learning approach to corner detection［J］.IEEE Transactionson Pattern Analysisand Machine Intelligence，2010，32(1):105-119.

［40］RUBLEE E，RABAUD V，KONOLIGE K，et al.ORB:an efficient alternative to SIFT or SURF［C］//IEEE International Conference on Computer Vision.Barcelona:IEEE，2011:2567-2571.

［41］CHLI M，DAVISON A J.Active matching［C］//10th European Conference on Computer Vision.Marseille:Springer，2008:72-85.

［42］NISTÉR D.Preemptive RANSAC for live structure and motion estimation［J］. Machine Vision and Applications，2005，16(5):321-329.

［43］KANADE T，MORRIS D D.Factorization methods for structure from motion［J］.Philosophical Transactions of the Royal Society B Biological Sciences，1998，356(1740):1153-1173.

［44］WENG J，HUANG T S，AHUJA N.Motion and structure from two perspective views:algorithms，error analysis，and error estimation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1989，11(5):451-476.

［45］TOMASI C，KANADE T.Shape and motion from image streams:a factorization method［J］.International Journal of Computer Vision，1992，9(2):137-154.

［46］POELMAN C J，KANADE T.A paraperspective factorization method for shape and motion recovery［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1997，19(3):206-218.

［47］STURM P，TRIGGS B.A factorization based algorithm for multi-image projective structure and motion［C］//4th European Conference on Computer Vision.Cambridge:Springer-Verlag，1996:709-720.

［48］MORITA T，KANADE T.A sequential factorization method for recovering shape and motion from image streams［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1997，19(8):858-867.

［49］IRANI M，ANANDAN P.Factorization with uncertainty［C］//European Conference on Computer Vision.Ireland:Springer，2000:539-553.

［50］ANANDAN P，IRANI M.Factorization with uncertainty［J］.International Journal of Computer Vision，2002，49(2/3):101-116.

［51］HARTLEY R.In Defense of the eight-point algorithm［J］.IEEE Transaction on Pattern Recognition and Machine Intelligence，1997，19(6):580-593.

［52］NISTER D.An efficient solution to the five-point relative pose problem［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26(6):756-770.

［53］CIVERA J，GRASA O G，DAVISON A J，et al.1-Point RANSAC for EKF filtering:Application to real-time structure from motion and visual odometry［J］.Journal of Field Robotics，2010，27(5):609-631.

［54］HARTLEY R，ZISSERMAN A.Multiple view geometry in computer vision［M］.London:Cambridge University，2003.

［55］FAUGERAS O，LUONG Q T，PAPADOPOULO T.The geometry of multiple images［M］.Cambridge:MIT Press，2001.

［56］MA Y，SASTRY S S，KOSECKA J，et al.An invitation to 3-D vision:from images to geometric models.Interdisciplinary Applied Mathematics Series，Book.26［M］.New York:Springer-Verlag，2005.

［57］VASCONCELOS F，BARRETO J，NUNES U.A minimal solution for the extrinsic calibration of a camera and a laserrange finder［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34(11):2097-2107.

［58］KUNZ C，SINGH H.Map building fusing acoustic and visual information using autonomous underwater vehicles［J］.Journal of field robotics，2013，30(5):763-783.

［59］MA J，SUSCA S，BAJRACHARYA M，et al.Robust multi-sensor，day/night 6-DOF pose estimation for a dynamic legged vehicle in GPS-denied environments［C］//Proceedings of the IEEE International Conference on Robotics and Automation.Minnesota:IEEE，2012:619-626.

［60］BROCKERS R，SUSCA S，ZHU D，et al.Fully selfcontained vision-aided navigation and landing of a micro air vehicle independent from external sensor inputs［C］//Proc SPIE，Unmanned Systems Technology.Baltimore:SPIE，2012:25-34.

［61］KELLY J，SUKHATME G S.Visual-inertial sensor fusion:localization，mapping and sensor-to-sensor self calibration［J］.International Journal of Robotics Research，2011，30(1):56-79.

［62］NEWMAN P，HO K.SLAM-Loop closing with visually salient features［C］//IEEE International Conference on Robotics and Automation.Piscataway:IEEE，2005:635-642.

［63］LIU Y，ZHANG H.Visual loop closure detection with a compact image descriptor［C］//IEEE/RSJ International Conference on Intelligent Robots and Systems.Piscataway:IEEE，2012:1051-1056.

［65］CADENA C，GALVEZ-LOPEZ D，RAMOS F，et al.Robust place recognition with stereo cameras［C］//IEEE/RSJ International Conference on Intelligent Robots and Systems.Piscataway:IEEE，2010:5182-5189.

［66］CAMPOS F M，CORREIA L，CALADO J.Mobile robot global localization with non-quantized SIFT features［C］//Proc of the 15th International Conference on Advanced Robotics.Tallinn:IEEE，2011:582-587.

［67］DONG Z，ZHANG G，JIA J.Efficient keyframe-based real-time camera tracking［J］.Computer Vision and Image Understanding，2014，118(1):97-110.

［68］NISTER D，STEWENIUS H.Scalable recognition with a vocabulary tree［C］//IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Los Alamitos:IEEE Computer Society，2006:2161-2168.

［69］SCHINDLER G，BROWN M，SZELISKI R.City-scale location recognition［C］//IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Los Alamitos:IEEE Computer Society，2007:1-7.

［70］CUMMINS M，NEWMAN P.Probabilistic appearance based navigation and loop closing［C］//IEEE International Conference on Robotics and Automation.Piscataway:IEEE，2007:2042-2048.

［71］CUMMINS M，NEWMAN P.Appearance-only SLAM at large scale with FAB-MAP 2.0［J］.International Journal of Robotics Research，2011，30(9):1100-1123.

［72］ANGELI A，FILLIAT D，DONCIEUX S，et al.Fast and incremental method for loop-closure detection using bags of visual words［J］.IEEE Transactionson Robotics，2008，24(5):1027-1037.

［73］SUNDERHAUF N，PROTZEL P.Brief-gist-closing the loop by simple means［C］//IEEE/RSJ International Conference on Intelligent Robots and Systems.Piscataway:IEEE，2011:1234-1241.

［74］WILL M，MICHAEL M，GORDON W.CAT-SLAM:probabilistic localization and mapping using a continuous appearance-based trajectory［J］.The International Journal of Robotics Research，2012，31(4):429-451.

［75］GLOVER A，MADDERN W，WARREN M，et al.Open-FABMAP:An open source toolbox for appearance based loop closure detection［C］//IEEE International Conference on Robotics and Automation.Minnesota:IEEE，2012:4730-4735.

［76］MILFORD M.Vision-based place recognition:how low can you go?［J］.The International Journal of Robotics Research，2013，32(7):766-789.

［77］LABBE M，MICHAUD F.Appearance-based loop closure detection for online large-scale and long-term operation［J］.IEEE Transactions On Robotics，2013，29(3):734-745.

［78］TULLY S，KANTOR G，CHOSET H.A unified bayesian framework for global localization and SLAM in hybrid metric/topological maps［J］.International Journal of Robotics Research，2012，31(3):271-288.