视觉SLAM特征与提取算法综述

郑泰皓 方子彬

摘要：为了使机器人在陌生环境中能够通过传感器对环境进行探测，并在对自身定位的同时得到周围环境的三维重建地图，视觉SLAM（Simultaneous Localization and Mapping），即时定位与地图构建应运而生。文章对视觉SLAM方法与特征匹配SIFT算法进行了论述与提取效率分析。SIFT算法包含大量单指令多数据流模式的密集型计算，使用CPU+GPU混合异构加速平台在理论上能有效提高其执行性能。通过对国内外学者在GPU并行加速领域研究成果的分析，针

GPU加速SIFT算法展开了分析与展望。

关键词：视觉SLAM;自身定位;特征匹配;SIFT算法;GPU加速

中图分类号：TP391 文献标识码：A 文章编号：1006-8228（2020）07-16-06

0引言

SLAM（Simultaneous Localization and Mapping）系统指的是在给定的环境中利用传感器进行探测，基本任务是确定自身的位置同时绘制环境地图，也叫做“同时定位与地图创建”系统。SLAM技术通常是指将携带相机传感器的移动机器人放置在一个未曾探索过的给定的一个环境中，利用其传感器的特性，捕获周围环境图像信息，从而对周围环境进行观测感知，目的是为了确定当前系统的位姿和运动过程产生的轨迹，來进行自身的定位导航，并同时构建出增量式地图的一种技术，最常用在移动机器人领域。

相机传感器有着小巧的体积、低廉的成本和大幅缩小的重量，存储的图像信息同时也更为丰富，所以以相机作为外部传感器的SLAM得到了快速的发展，这样的SLAM被称为视觉SLAM。而SIFT（scaleInvariant Feature Transform）算法也称作尺度不变特征变换算法，是视觉SLAM中最基础最经典也是最重要的算法。

通过对SIFT算法进行优化，可以进一步对视觉SLAM算法进行加速。

1相关研究

1.1SLAM系统介绍

SLAM技术的关键问题是要通过传感器对环境进行感知预测，了解到机器人准确的位置和运动轨迹，从而才能构建出准确的环境地图，而这些问题的前提是要知道其所处位置的准确地图环境。

在机器人定位导航的过程中，最关键的三个方面分别是定位，建图和路径规划，其中定位与建图相互关联与依赖。Durrant-Whyte和Baileyt全面回顾了SLAM技术的在1986年到2004年“经典时期”的发展历史，见证了该技术朝工业方向的转变。

1.2 SLAM系统流程

到目前为止，有大量的国内外研究学者对于开源SLAM算法进行了深入的研究，内容包括但不限于特征检测与特征匹配、闭环检测、边缘检测与优化、大规模环境场景等等关键技术。

实际上，整个视觉SLAM流程包括以下步骤。

（1）读取传感器图像信息：机器人主要以相机作为外部传感器，采集到的信息内容主要是图像，对这些信息进行读取同时做预处理操作。

（2）视觉里程计（VisualOdometry）：仅通过视觉输入引起的图像变化来估计相机运动，从而确定机器人的位置和姿态，是SLAM系统的构建模块。方法通常是利用ORB（Oriented FAST and Rotated BRIEF）算法来检测与匹配特征。

（3）后端优化（Optimization）：后端考虑不同时刻的轨迹与地图准确率问题，会接收并使用一段时间内的视觉里程计来更新相机位置与姿态以及避免回环检测的问题，从而进行优化，得到更加准确的移动路径与地图。

（4）回环检测（LoopClosing）：在机器人进行定位与绘图的过程中，相机传感器根据机器人的运动轨迹记录下图像信息。对这些轨迹图像进行计算比较，若相似度超过某一阈值，则认为出现回环。即检测机器人是否进入同一地点。

（5）建图（Mapping）：建立地图。机器人感知信息规划路线，通过预估的轨迹，构建对应任务的地图。

整个过程如图1所示。

1.3 SLAM系统的应用

近二十年来SLAM方法在智能机器人领域无论是从基础理论上，还是在应用实例上，都已经取得了极大的成功和突破，建立了一些稳定实用的SLAM方法，并能很好地适用于各种不同的环境。例如，室内环境（groundindoor）、室外（groundoutdoor）、空间（air-borne）和水下（underwater）等。

传统的单目视觉SLAM则是借助于扩展卡尔曼滤波器来实现轨迹规划与定位绘图的。在移动机器人领域中，SLAM方法应用越来越广泛，算法越来越强大，其中便有经典的期望最大化（ExpectationMaximi-zation，EM）算法。

传统的算法计算量大，复杂度高，一直到2000年，对SLAM方法的研究重点逐渐从传统的声呐、激光等测距传感器发展到视觉传感器。视觉传感器也逐渐有了专有名词——VisualSLAM。视觉传感器有着测距传感器不可比拟的优点，最大的特点即是低成本高作用，不仅提高了探测范围，还拥有更好的环境适应能力。

微软研发出Kinect相机的原理是提取彩色图像中具有深度信息的SIFT特征，用特定的方法计算出3D特征点的匹配信息，并结合ICP（Iterative ClosestPoint）算法进行位姿的估计与优化。

ICP算法基本流程如图2所示。

相比于其他传统的特征提取算法，SIFT算法的精确度高，对于噪声或者其他不利因素的鲁棒性也比较强。因此，通常会用SIFT算法作为视觉SLAM系统中的特征提取算法。

2SlFT算法原理

由于SIFT算法能够提取局部特征，所以它的实质便是在不同的尺度空间检测这些局部特征点作为关键点，并且这些关键点为不会因光照、噪声、杂物、旋转等外界因素而受到影响的点，然后计算出这些关键点的特征方向和特征向量，从而建立图像中点的对应关系。

下面对SIFT算法具体步骤及其原理进行简单的介绍。

2.1构造DOG金字塔

首先需要构造DOG（Difference of Gaussian）金字塔，中文全称为高斯差分金字塔。要构造DOG金字塔，需要以下几步：

（1）构造高斯金字塔

二维空间高斯函数为：

可以看出G（x，y，σ）是正态分布，将式（1）进行化简计算，得到它的均值和方差分别为0和σ。对于二维图像I（x，y），如公式（2）所示，利用高斯函数与图像进行卷积，得到其在不同尺度下的尺度空间表示。其中，L与σ与图像平滑程度正相关，它们分别表示尺度空间与尺度因子。利用式（1）、式（2），建立高斯金字塔，得到高斯金字塔示意图，如图3所示。

其中，k为固定系数。由式（3）可知，计算要得到的函数差，便要对相邻两组尺度空间分别进行高斯卷积，然后将得到的结果做减法运算。

2.2DOG极值点检测及筛选

在高斯金字塔中一共生成若干组和若干层不同尺度的图像，这些不同的层和组就构成了高斯金字塔的尺度空间。在该尺度空间中间层的基础上除去上下两层而只取中间层，在中间层选取某一点作为待检测点，分别与上下层像素点与该点周围的8个像素点进行一一计算比较，记录下该局部极值点的位置及其对应尺度。然后通过SIFT算法泰勒展开DOG函数，便可得到极值点的位置和维数。

将空间函数D（x，y，σ）在局部极值点（xo，yo，σ）处进行泰勒展开，得到泰勒展开式，如公式（4）。

由此可得此展开式的导数，并令其為0，得到精确的极值点位置Xmax。将Xmax带入公式（4），只取前两项，可得到公式（5）。

2.3生成SIFT特征向量

生成SIFT特征向量的第—步是确定特征点主方向，根据公式（6）可分别得到特征点的梯度值与梯度方向。

在得到特征点的梯度值与主方向后，以特征点为中心去除掉其所在的行与列，并选取一个8×8大窗口。将这个大窗口划分为4个规模为4×4的小窗口，为每个小窗口计算8个方向的梯度方向直方图，对得到的直方图进行分析，并将每个方向相对应的幅值加起来以形成关键点。分配给关键点的方向并不直接是关键点的梯度方向，而是按照一种梯度方向直方图的方式给出的。将这些样本累积在方向直方图中，每个箭头对应了每个方向，同时它在直方图中的长度对应于小窗口内该方向附近的梯度幅度之和。

由上述可知，每个小窗口对应一个关键点，每个关键点具有8个方向矢量信息，这些信息可以生成4×4×8=128个元素的SIFT特征矢量。由于SIFT本身的特性，并且在选取特征点时特意选择了受光照、缩放、噪声影响较小的点作为关键点，因此此时的SIFT特征向量受外界几何因素干扰较小，可以很好地描述图像的特征。

3SIFT算法的GPU加速研究

SIFT算法功能强大，同时也伴有较高的算法复杂度和计算时间，无法满足于一些实时需求，这使得加速图像处理的过程成为学者们研究探讨的热点。而随着技术的不断突破，图像处理领域强大的图形处理器GPU（Graphics Processing Unit）技术的成熟，这一切都将成为可能。GPU的主要是对图像信息进行构建和渲染，在浮点运算与并行运算方面，它的速度远远超过CPU。由于其高速运算能力与强大并行计算能力，而受到了图像处理领域的青睐。

针对SIFT特征提取的计算效率，国内外许多学者进行了大量研究。将GPU技术与多核CPU应用于SIFT算法在近几年来的热度逐渐提升。Sinha等人在基于OpenGL和cg语言的NVIDIA 7900GTX显卡上通过GPU并行操作实现了SIFT功能，但是由于当时的硬件和软件条件，一些步骤在GPU上并未执行，从而导致大量数据传输在GPU和CPU之间转换，花费了大量时间。

SIFT算法包含了大量的单指令多数据流SIMD（Single Instruction Multiple Data）模式的计算，使用CPU+GPU混合架构在理论上能减少重复运算的运行时间。下面通过引用的一些实验数据对SIFT算法的GPU加速进行讨论。

Zhang等在Intel 8核CPU上实现了SIFT算法，达到了6.4倍的性能加速效果，并对算法的可扩展性进行了详细的分析和实验。

Feng等人在16核CPU和64核模拟器上实现了11倍的加速。事实上除了并行优化外，其中还还包括达到2倍速度提升的局部串行优化。

Warn等人在混合机群上，运用多核CPU与GPU进行了实验。结果表明，在8核处理器上只达到了2倍的加速，而GPU版本却加速了13倍。

王蓓蕾等人基于CUDA编程模型实现了SIFT算法的GPU加速。并通过合理计算，利用CPU+GPU混合异构来优化算法。实验结果如表1所示（ms表示单位为毫秒）。

王化喆等人通过CPU+GPU混合异构模式，对遥感图像配准的SIFT算法进行了优化。通过负载均衡计算，把大量的重复性计算放到GPU上进行运算，CPU上进行逻辑判断等运算。实验采用了一幅6000×6000的遥感图像，对SIFT算法的各个步骤分别进行CPU以及CPU+GPU的运行时间对比，实验结果如表2所示（ms表示单位为毫秒）。

实验结果表明，主方向模值梯度计算的加速比达到了10，远超过其他实验项目，所以它的并行效果最好。

付波等在GPU为NVIDIAGeForceGTX550Ti，显存为1GB的环境下，得到了如表3的实验结果（ms表示单位为毫秒）。

可以看出，SIFT算法对于有不同分辨率的图像处理速度也不同，而GPU优化之后的SIFT算法效率明显高于串行SIFT算法。不仅如此，在特征描述子的性能计算上，也得出了相应的结果，实验结果如表4（ms表示单位为毫秒）。

分析可知，对于SIFT算法无论是在特征点计算性能、极值点检测、主方向模值梯度计算，还是在尺度空间和差分尺度空间计算性能、特征描述子计算性能上，GPU加速都达到了很好的加速效果。采用GPU加速适合并行的部分，会对算法整体产生优化效果。

这也证明了GPU加速SIFT算法是可行和有效的。未来，GPU优化加速可以应用到更多的算法以及应用领域中。

4结束语

通过以上对基于特征的视觉SLAM方法及其一种特征提取算法SIFT的介绍，以及引用的论文中对SWT算法的GPU并行优化实验结果分析，可以得出如下结论：

（1）视觉SLAM算法可以通过引.）kGPU来进行并行优化;

（2）合理考虑负载均衡问题，采用CPU+GPU混合异构系统能够在一定程度上提高视觉SLAM算法的实时性;

（3）视觉SLAM算法关键帧的合理选取，特征检测及匹配算法的选取，以及算法并行与串行部分所占的比重都会影响到整体的优化效果。

综上所述，对视觉SLAM算法进行优化时需考虑多方面的因素，特别是当GPU存储及计算资源不足时的负载均衡问题，以及程序的并行粒度计算，都是值得研究的问题。