第1期 周彦，等：视觉同时定位与地图创建综述 ·101· 方法中，只对约束关系进行局部更新，这种局部更 线性优化的方法（现代SLAM系统）可以取得更好 新使得信息矩阵近似于系数矩阵，有效降低 的效果1o SLAM的时间复杂度。 另外，在2011年滤波方面出现了基于RFS Davisonl3s于2007年提出的MonoSLAM,是第 (random finite set)的方法B。RFS是滤波中新兴的 一个基于EKF方法实时的单目VSLAM系统，虽然 潮流B8),RFS是以集合为元素的集合，此集合中的 初步解决了实时的问题，能够在线创建稀疏地图， 元素及元素个数都是随机变量。文献38]对环境地 漂移多少仍然不能确定，目前已经停止对其的开发。 图和传感器观测信息用RFS建模，构造联合目标状 图S是基于EKF的单目VSLAM流程图。 态变量的RFS。依据贝叶斯滤波框架，利用概率假 设密度滤波(probability hypothesis density,.PHD)B9 传感器信息 实现对机器人位姿和环境地图同时估计。该算法避 免了数据关联的问题，相对于EKF和P℉能更有效 地表达SLAM问题。 开始/ 运动模型 EKF 待征 新特 2.2现代SLAM系统：基于非线性优化的方法 EKF预测 更新 转换 征点 现代S1AM系统分为两个部分：前端和后端。 前端提取传感器数据构建模型用于状态估计，后 数据 测量 6维特征 端根据前端提供的数据进行优化。这个架构如图6 关联 模型 到3维特征 所示。 前端 后端 视 特征点 传感器数据 图像 初始化 特征提取 致据关联 优化 图5基于EKF的单目VSLAM流程图 短期（跟踪 Fig.5 Flowchart of EKF-based monocular VSLAM 长期（回环 2.1.2基于粒子滤波器的FastSLAM M.Montemerlo等B6-3提出了1种基于粒子滤 波器(particle filter,PF)的FastSLAM方法。Fast- 图6典型SLAM系统 Fig.6 Typical SLAM system SLAM包含了机器人定位和特征标志位置估计两个 当前SLAM事实标准形成来源于Lu和Milios 过程。粒子滤波器法中机器人可能的运动路径用粒 它是Gutmann和Konoligel研究的后续。典型的 子表示，1个粒子对应着1种可能，每条路径的好坏 SLAM系统如图6所示，前端进行特征提取、数据 由利用观测信息计算得到的粒子权重来评价。对于 关联和初值优化。前端的数据关联模块包括1个短 每个粒子来说机器人的运动路径是确定的，故特征 标志之间相互独立且其观测信息只与机器人的位姿 期（局部）数据关联模块和1个长期（回环）数据关 联模块。通常意义下的数据关联问题在SLAM中 有关。FastSLAM的时间复杂度为O(kn),其中 k为粒子个数0。用树形数据结构优化后的时间复 是指递增定位与建图过程中如何确定当前连续的传 杂度可以达到O(k log n)B0。FastSLAM能够比较 感器观测之间或者当前时刻的观测与最近所创建的 好地表示机器人的非线性、非高斯运动模型。 局部地图中特征间的关联关系，这也称为短期（局 EKF存在非线性误差，且需要存储、维护和更 部)数据关联；回环检测中的数据关联研究机器人 新状态量的均值和方差。如果把路标也加入状态的 沿不同的路径回到某一循环的起点时，如何确定当 话，由于V SLAM中路标数量很大，这个存储量是 前创建的局部地图中的特征与以前所创建的循环起 相当大的，且与状态量呈平方增长（因为要存储协 点处地图中的特征间的关联关系，这称为长期（回 方差矩阵)。因此，EKF普遍被认为不适用于大型 环)数据关联。短期的数据关联模块负责关联传感 场景。P℉采样所需的粒子数量，随维度的增加呈指 器中连续的观测值对应的特征：得到1帧图像数据 数增长，所以仅限于低维的问题，对高维问题不适 后，对其进行预处理，筛选出关键帧，对图像进行特 用。除此之外，滤波器方法在一定程度上假设了马 征提取、匹配以及运动求解并得到局部地图，也就 尔可夫性，如果当前帧与很久之前的帧有关（例如 是视觉里程计(visual odometry,VO);长期的数据 回环)，那么滤波器就会难以处理这种情况。因为 关联负责将新的观测值关联到旧的路标上，也就是 滤波这些明显的缺点，在同等计算量的情况下，非 回环(loop closure),方法中，只对约束关系进行局部更新，这种局部更 新使得信息矩阵近似于系数矩阵，有效降 低 SLAM 的时间复杂度。 Davison[35]于 2007 年提出的 MonoSLAM，是第 一个基于 EKF 方法实时的单目 VSLAM 系统，虽然 初步解决了实时的问题，能够在线创建稀疏地图， 漂移多少仍然不能确定，目前已经停止对其的开发。 图 5 是基于 EKF 的单目 VSLAM 流程图。 2.1.2 基于粒子滤波器的 FastSLAM M. Montemerlo 等 [36-37]提出了 1 种基于粒子滤 波器 (particle filter, PF) 的 FastSLAM 方法。 Fast￾SLAM 包含了机器人定位和特征标志位置估计两个 过程。粒子滤波器法中机器人可能的运动路径用粒 子表示，1 个粒子对应着 1 种可能，每条路径的好坏 由利用观测信息计算得到的粒子权重来评价。对于 每个粒子来说机器人的运动路径是确定的，故特征 标志之间相互独立且其观测信息只与机器人的位姿 有关。FastSLAM 的时间复杂度为 O (kn) ，其中 k 为粒子个数[30]。用树形数据结构优化后的时间复 杂度可以达到 O (k log n) [30]。 FastSLAM 能够比较 好地表示机器人的非线性 、非高斯运动模型。 EKF 存在非线性误差，且需要存储、维护和更 新状态量的均值和方差。如果把路标也加入状态的 话，由于 V SLAM 中路标数量很大，这个存储量是 相当大的，且与状态量呈平方增长（因为要存储协 方差矩阵）。因此，EKF 普遍被认为不适用于大型 场景。PF 采样所需的粒子数量，随维度的增加呈指 数增长，所以仅限于低维的问题，对高维问题不适 用。除此之外，滤波器方法在一定程度上假设了马 尔可夫性，如果当前帧与很久之前的帧有关（例如 回环），那么滤波器就会难以处理这种情况。因为 滤波这些明显的缺点，在同等计算量的情况下，非 线性优化的方法（现代 SLAM 系统）可以取得更好 的效果[10]。 另外，在 2011 年滤波方面出现了基于 RFS (random finite set) 的方法[38]。RFS 是滤波中新兴的 潮流[38] ，RFS 是以集合为元素的集合，此集合中的 元素及元素个数都是随机变量。文献[38]对环境地 图和传感器观测信息用 RFS 建模，构造联合目标状 态变量的 RFS。依据贝叶斯滤波框架，利用概率假 设密度滤波（probability hypothesis density, PHD） [39] 实现对机器人位姿和环境地图同时估计。该算法避 免了数据关联的问题，相对于 EKF 和 PF 能更有效 地表达 SLAM 问题。 2.2 现代 SLAM 系统：基于非线性优化的方法 现代 SlAM 系统分为两个部分：前端和后端[1]。 前端提取传感器数据构建模型用于状态估计，后 端根据前端提供的数据进行优化。这个架构如图 6 所示。 当前 SLAM 事实标准形成来源于 Lu 和 Milios[40] ， 它是 Gutmann 和 Konolige[41]研究的后续。典型的 SLAM 系统如图 6 所示，前端进行特征提取、数据 关联和初值优化。前端的数据关联模块包括 1 个短 期（局部）数据关联模块和 1 个长期 (回环) 数据关 联模块。通常意义下的数据关联问题在 SLAM 中 是指递增定位与建图过程中如何确定当前连续的传 感器观测之间或者当前时刻的观测与最近所创建的 局部地图中特征间的关联关系，这也称为短期（局 部）数据关联；回环检测中的数据关联研究机器人 沿不同的路径回到某一循环的起点时，如何确定当 前创建的局部地图中的特征与以前所创建的循环起 点处地图中的特征间的关联关系，这称为长期（回 环）数据关联。短期的数据关联模块负责关联传感 器中连续的观测值对应的特征：得到 1 帧图像数据 后，对其进行预处理，筛选出关键帧，对图像进行特 征提取、匹配以及运动求解并得到局部地图，也就 是视觉里程计（visual odometry，VO）；长期的数据 关联负责将新的观测值关联到旧的路标上，也就是 回环（loop closure）。 ᐬ໷/ ֈ₎ ьᙋஔԍᖛ 䓼ߔὍಷ EKF 䶰≷ ᪜ᢚ 㖀ڟ EKF ᰠ᫜ ≷䛻 Ὅಷ 6 㐠➥ᒭ ݜ
3 㐠➥ᒭ ➥ᒭ◥ ࡂ໷݉ ➥ᒭ 䒘ᢎ ᫜➥ ᒭ◥ 㻲䶽 ׻ప N N Y Y 图 5 基于 EKF 的单目 VSLAM 流程图 Fig. 5 Flowchart of EKF-based monocular VSLAM ьᙋஔ᪜ᢚ ࡂф 〚ऺ 〚ݹ ➥ᒭ᣼ं ᪜ᢚڟ㖀 ⴙ᱋
(䌋䍖) 䪫᱋
(ఊ⣛) 图 6 典型 SLAM 系统 Fig. 6 Typical SLAM system 第 1 期 周彦，等：视觉同时定位与地图创建综述 ·101·