基于LK光流法的单目视觉里程计

陈伟杰，孙作雷

(上海海事大学 机器辨识与交互研究组，上海 201306)

基于LK光流法的单目视觉里程计

陈伟杰，孙作雷

(上海海事大学 机器辨识与交互研究组，上海201306)

在移动机器人快速发展的今天，视觉里程计是通过视觉传感器进行导航定位的主要方式之一。文章介绍了基于单个摄像头的单目视觉里程计的一种实现方法，使用SURF算法提取特征点，用LK光流法进行特征追踪，相比于传统特征匹配在运算效率上有极大的提高，再对特征点计算位移与旋转量，以里程计的方式达到定位目的。详细介绍了视觉里程计的数学原理以及SURF算法和LK算法的原理及其数学推导、单目视觉里程计的尺度不确定原理。最后通过对比确定LK算法的优势以及最优参数的选择。

视觉里程计；LK光流法；图像处理；特征跟踪；多视图几何

0 引言

智能机器人在近年来越来越多地进入公众视野。要想让机器人实现全自主的移动，其关键技术是即时定位与地图构建(Simultaneous Localization and Mapping，SLAM)，使机器人通过传感器感知周边环境，通过传感器反馈信息构建出一幅“地图”，从而达到自主定位和导航的功能。

根据传感器的种类不同，SLAM技术可以进行分类，如激光SLAM[1]、视觉SLAM。其中视觉传感器可以获取到的影像数据包含着丰富的信息。视觉里程计(Visual Odometry，VO)就是一种基于视觉传感器的机器人定位方法，无需场景和运动的先验信息，可以不受移动部件的打滑、磨损、漂移等因素的误差影响，而且只要有光线的地方利用相机就可以使用，因而被广泛应用到各种移动机器人中，如火星探测器“勇气号”和“机遇号”[2]、无人飞行器[3]以及陆地机器人[4]等。

视觉里程计的概念最早在1980年提出[5]，其大致理论框架为：特征提取、特征匹配或追踪以及运动估计，主要理论依据是机器视觉中的多视图几何[6]，即通过前后帧图像的匹配特征点对集合计算出相机在获取两帧图像时的位姿变化。单目视觉仅由一个相机实现，虽然有尺度不确定性的缺陷但是方便实用、成本低。本文阐述一种基于LK光流法进行特征追踪的单目视觉里程计的方法原理。

1 特征提取

对于输入的图像序列，全局运算过于繁琐，因此需要提取一些特征点。快速鲁棒特征(Speed Up Robust Feature，SURF)[7]是目前十分流行的算法，继承了较成熟的SIFT[8]算法的优点的同时提高了运算效率。

(1)

取近似值将滤波模型“量化”，简化后的滤波模型D≈L，得到简化后的海森矩阵为：

Det(Happrox)=DxxDyy-(0.9Dxy)2

(2)

式中0.9是经验值，是一个常数，补偿简化后的误差。当Happrox>1时将该点作为特征候选点。

不同于SIFT算法中的图像金字塔尺度空间，SURF建立尺度空间利用缩放滤波器大小实现，有效降低运算量。取得尺度空间后，对每个特征候选点，取其上下两层尺度的26个邻域点进行比较，如图1所示，当它的灰度值是26个点中的最大值时，则判定为特征点。

图1 特征点判定示意图

2 特征追踪

确定特征点后需要将前后帧的图像特征点配对才可以进行解算，而对特征直接进行配对需要较大的运算量，此时可以用LK光流法[9]追踪特征点达到寻找匹配点的目的。

光流法在近些年十分热门，在计算机视觉方面应用广泛，特别是目标追踪方面卓有成效。光流是指三维物体的运动在二维平面上的投影。LK算法是稀疏光流法的代表，取局部区域对其光流进行追踪，效率高。

LK算法基于三个前提假设：亮度恒定、运动幅度小、局部一致性。LK算法的目的是对某一帧中的特征点，确定下一帧图像中该点所在的位置。首先取特征点周围的一个窗w，根据局部一致性假设窗w内的点有相同光流，且假设亮度恒定，前后帧图像表示同一点的灰度值相等，而在运动幅度不大的情况下，只需要在一个小范围内搜索灰度值最相近的窗即可。因此LK算法所求特征点u的光流d可以总结为求误差函数ε(d)的最小值：

(3)

由于完全相同的匹配点只可能有一个，所以最小值也是极小值，也就是偏导为0。

(4)

对ε(d)求偏导之后，再对J(x+dx,y+dy)取其一阶泰勒展开式可以得到：

(5)

为简化上式，定义等式:

(6)

(7)

因此式子可以简化为:

(8)

(9)

定义

(10)

(11)

则光流d的极值可以表示为:

dopt=G-1b

(12)

根据光流d，也就是运动量，特征点u就可以确定在下一帧图像所在的位置，那个点就是匹配点。

3 运动估计

根据两帧图像匹配点求解运动关系理论依据称为对极几何。现有两幅不同位置拍摄同一物体X的图像模型如图2所示。C、C′表示相机位置，两者之间的连线称为基线b，与图像平面的交点e、e′为对极点，b与X所确定的平面称为对极平面，对极平面与图像平面的交线l、l′为对极线，其中b与e由左右图像唯一确定，对极平面与对极线有无限个。

图2 对极几何模型

显然，当已知图像左侧上的点x，根据相机拍照的原理与对极几何，x在图右侧上的匹配点x′必然在对极线l′上。这种映射关系用数学表示为3×3大小的本质矩阵E或基本矩阵F，分别对应经过标定去畸变的图像与原图像。

Ex=l′或Fx=l′

(13)

E=K′TFK

(14)

由点在直线上表示为xTl=0，可以得到Longuet-Higgins公式：

x′TEx=0

(15)

设C到C′的位移和旋转量分别为t和R，称为相机外参，包含于表示两帧图像映射关系的E和F的参数中。因此求解本质矩阵E或者基本矩阵F，即可得知两帧图像之间的位姿变化量，完成相机的运动估计。

在实际应用过程中，直接对图像去畸变再进行处理过于繁琐，因此通常直接使用原图像的匹配点代入公式(15)，先计算出本质矩阵F，使用RANSAC[10]算法对其进行优化，剔除误差；然后根据标定矩阵得到本质矩阵E；最后对E进行奇异值分解得到相机外参R和t。

4 实验结果

此次实验基于VS2012，openCV2.4.9进行，实验数据主要来源于kitti中的第00组测试图像中的前1 000帧图像，图像大小为1 241×376，第一帧图像序号为000000，如图3所示。

图3 实验原图像000000

LK光流法极大地提高了寻找匹配点的速度，减少了运算时间。除了运算速度快，LK算法还可以追踪特征点，不必对每幅图像进行特征提取操作，直到特征点数量小于阈值T时才进行一次特征提取，进一步减少了程序运行的时间。将LK算法与传统匹配算法最近邻搜索算法(FLANN)[11]进行比较。另取一组大小为512×272的图像，图像如图4所示。实验中SURF算法的海森矩阵参数设置为400，该值越小，特征点越多。

图4 实验原图像“房子”

实验结果如表1所示。

表1 不同图像、算法比较

结果中平均时间由运行三次求算术平均得到，可以看出LK光流法的运行时间远小于FLANN匹配算法。在图像特征点数增加5倍左右的情况下，FLANN匹配所需花费的时间也需要增加为原来的5倍多，而LK光流追踪却只增加2.5倍左右的花费时间，也就是说特征点数量越大，LK算法的优势越加明显。

为得到较优的参数，取测试图像序列前1 000帧图像进行比较。其中SURF的海森矩阵参数取200。将阈值T分别设置为1 000、1 500、2 000，当特征点数小于该参数时重新进行一次特征提取。实验结果示例如图5所示。

图5 海森矩阵参数为200时不同阈值参数实验结果

从图5中可以较为直观地看出阈值T为1 000时的误差明显大于另外两者，相同海森矩阵参数下阈值设为1 500和2 000较为接近。可以得到初步结论，平均特征点数目越多，实验结果越好，而且可能存在临界值。

为进一步分析，本文使用kitti提供的误差评估程序对误差进行评估，取不同的海森矩阵参数和阈值进行比较，得到平均误差如表2所示，主要考虑平均位移误差。同时比较不同参数所需的运行时间，三次运行取平均值，结果如表3所示。

表2 不同参数的位移误差 (%)

表3 不同参数运行时间 (s/百帧)

从表2、表3中可以看出，海森矩阵参数值越大，所需时间降低，位移误差增加；阈值参数越大，所需时间增加，位移误差减小。

纵向比较，海森矩阵参数变化时，时间变化量约为5～10 s/百帧，而位移误差在50和100时变化不大，值为200时却成倍增长。横向比较，阈值T变化时，时间变化量较大，约有20～25 s/百帧，而位移误差在1 500与2 000时变化量较小，1 000时误差较大。综合比较，在50、100和1 500、2 000几个数据中，位移误差相差1%左右的情况下，选择较小的海森矩阵参数比较小的T值多花费15～20 s/百帧的时间，50/1 500的参数与100/2 000的参数误差仅相差0.2%，时间少了16 s/百帧。

因此更改阈值T更有效于速度调节，但不宜过低；更改海森矩阵参数更有效于精度调节，但不宜过高。若只追求精确度，选择小的海森矩阵参数和大的阈值T。

5 结论

本文详细介绍了基于SURF算法进行特征提取，基于LK光流法进行特征追踪的单目视觉里程计。对比分析了LK光流法的优势，实验证明LK算法可以极大地提高程序运算效率，减少运行时间。通过对比不同参数的结果选择较优的参数使得算法有较快的运行速度也有较低的位移误差。单目视觉有良好的前景，有待进一步发展，相信不久的将来就可以进入每个人的生活之中。

[1] 李延炬，肖宇峰，古松,等.基于激光传感器的SLAM数据关联算法的研究[J].微型机与应用，2017，36(2):78-82.

[2] MAIMONE M，CHENG Y，MATTHIES L.Two years of visual odometry on the mars exploration rovers[J].Journal of Field Robotics，2007，24(3):169-186.

[3] KELLY J，SUKHATME G S.An experimental study of aerial stereo visual odometry[J].IFAC Proceedings Volumes，2007，40(15):197-202.

[4] DORNHEGE C，KLEINER A.Visual odometry for tracked vehicles[C].Proc.of the IEEE Int.Workshop on Safety，Security and Rescue Robotics.IEEE，2006:351-356.

[5] MATTHIES L，SHAFER S A.Error modeling in stereo navigation[J].IEEE Journal of Robotics and Automation，1987，3(3): 239-248.

[6] HARTLEY R，ZISSERMAN A.Multiple view geometry in computer vision[M].Cambridge University Press，2003.

[7] BAY H，TUYTELAARS T，GOOL L V.SURF: Speeded up robust features[J].Computer Vision & Image Understanding，2006，110(3):404-417.

[8] NG P C，HENIKOFF S.SIFT: predicting amino acid changes that affect protein function[J].Nucleic Acids Research，2003，31(13):3812-3814.

[9] LUCAS B D，KANADE T.An iterative image registration technique with an application to stereo vision[C].International Joint Conference on Artificial Intelligence.Morgan Kaufmann Publishers Inc，1981:674-679.

[10] SCARAMUZZA D，FRAUNDORFER F，SIEGWART R.Real-time monocular visual odometry for on-road vehicles with 1-point RANSAC[C].IEEE International Conference on Robotics and Automation.IEEE，2009:488-494.

[11] MUJA M.Fast approximate nearest neighbors with automatic algorithm configuration[C].International Conference on Computer Vision Theory and Application Vissapp, 2009:331-340.

Monocular visual odometry based on LK optical flow

Chen Weijie，Sun Zuolei

(Machine Perception and Interaction Group (MPIG)，Shanghai Maritime University，Shanghai 201306，China)

Nowadays, with the rapid development of mobile robots，visual odometer is one of the main ways of navigating through visual sensors.In this paper，we introduce a method of monocular visual odometer based on single camera.We use SURF to extract feature points and then use LK optical flow to track features.The operational efficiency of LK is higher than usual matching.Finally，we use matching points to get translation and rotation to achieve the purpose of positioning.We introduce how SURF and LK work and what’s projective ambiguity.At last，we show the result that LK is really faster than usual matching, and the optimal parameters are determined by comparing the selection.

visual odometry; LK optical flow; image processing; feature tracking; multi-view geometry

TP242.6+2

A

10.19358/j.issn.1674-7720.2017.21.014

陈伟杰，孙作雷.基于LK光流法的单目视觉里程计J.微型机与应用，2017,36(21)：45-47,50.

2017-05-02)

陈伟杰(1993-)，男，硕士研究生，主要研究方向：计算机视觉。

孙作雷(1982-)，男，博士，副教授，主要研究方向：机器人定位与地图构建(SLAM)、机器学习。