基于光流法算法的Visual Map快速建立方法

马 琳， 赵 航， 谭学治

(哈尔滨工业大学 通信技术研究所， 哈尔滨 150001)

基于光流法算法的Visual Map快速建立方法

马 琳， 赵 航， 谭学治

(哈尔滨工业大学 通信技术研究所， 哈尔滨 150001)

Visual Map是一个含有丰富位置信息的图像数据库，数据库中每一幅图片或图片的特征在存储时会加入相应的位置信息. 室内定位的性能与Visual Map 图片的数量有关. 建立庞大的图片数据库能够使得定位结果更加准确，但是花费时间成本会更大. 针对这个问题，本文提出了使用光流法算法来建立图片数据库Visual Map. 针对光流法用于室内图像的计算会受到光线明暗不同的影响以及相机转向会产生横向偏移的问题，本文对光流法进行了改进，并使用改进后的光流法算法对摄像机采集的图像序列进行计算，得到摄像机的自身位移，从而得到每一幅图片的对应的地理位置信息. 实验结果表明，利用使用光流法快速建立的Visual Map进行室内定位，误差小于1米的概率是26%，误差小于2米的概率是70%. 与传统的视觉室内定位法相比，定位精度虽然略有降低，但建立图像数据库所需时间消耗大大减少. 相比于视频流快速建立Visual Map方法，定位效果相当，建立Visual Map所需的设备更少，要求更加宽松. 利用光流法算法快速建立Visual Map能够很好的应用于室内视觉定位系统，特别是应用于大型场所以及室内场景多变化的场所.

计算机应用；Visual Map；光流法；室内定位系统；图像数据库

室内定位以其低成本、方便操作、易覆盖等优势，成为主流定位技术之一，并被广泛究. 文献[1]利用对极几何理论对数据库中的图片与用户输入的图片进行匹配计算，从而得到用户位置，该定位方法达到了米级甚至亚米级的定位精度. 文献[2]提出利用纠正线与单应矩阵的方法进行室内定位，在保证定位精度的同时，提高了定位速度. 文献[3]利用智能手机中摄像头进行定位与运动轨迹的估计，并与手机中的惯导设备的定位结果进行对比. 通过实验，该文献指出，视觉方法进行定位与导航的精度要高于惯导设备，而且避免了惯导设备的累计误差问题. 文献[4]提出利用价格昂贵的RGB-D摄像机进行轨迹的估计与计算，该算法利用视觉信息弥补景深信息距离短的不足，而景深信息可以帮助提高视觉定位的精度. 文献[5]利用深度相机进行室内定位，并粗略的给出了运动轨迹. 文献[6]充分利用相机的视觉信息、激光雷达的距离信息以及几何传感器等给出了运动轨迹的估计，并对室内环境进行了重建. 文献[7]利用智能眼镜中的相机实现视觉定位对智能眼镜中的步行者航位推算仪PDR所计算出的位置进行修正，从而得到更加准确的运动轨迹，将平均误差降低一半以上.

然而，以上方法虽然提高了视觉定位精度提高，但是室内视觉定位系统的使用需要建立一个包含大量图片以及每张图片对应的位置信息的图片数据库，而在一个大范围场景建立这些数据库是非常消耗时间和人力的. 为了解决这个问题，文献[8]提出了一种基于视频流的快速建立Visual Map算法. 然而利用此算法进行地理位置的计算时，需要知道每一时刻的运动方向与坐标轴的夹角，在提取帧频率过高和角度变化过快的情况下，角度信息和图片采集很可能无法正确对应. 而且此算法的计算是假定相机是匀速运动的，这是现实使用过程中是很难做到的.

为减少对传感器需求以及解决上述算法实用性差的问题，本文提出利用光流法进行相机位移的计算从而得到每一帧图像地理位置. 光流法经常被用于运动检测、里程计算，自运动检测等[9-10]. 文献[11]详细介绍了利用光流法进行物体检测的基本原理，并进行了验证. 文献[12]将要检测的目标从背景中隔离出来，从而实现运动目标的检测与追踪. 文献[13]利用光流法和几何流结合的方式对运动的人物进行检测体现了光流法的准确性、低复杂度的优点. 文献[14]中，一种基于单目相机的定位导航算法被提了出来，该算法利用八点法和RANSAC算法提升了光流法的计算准确度，显著地降低了定位误差. 由于运动是相对的，因此可以通过图片序列中物体的光流，反过来对相机的运动进行估计. 本文利用改进后的光流法，在已知起点的前提下，计算图片序列中每一幅图片的地理位置.

1 室内视觉定位系统

1.1系统框架

本文提出的视觉定位系统分为两个阶段，分别是离线和在线两个阶段，系统框图见图1. 本文所提出的建立图像数据库的方法只需要利用一个摄像头在行进过程中进行视频的采集，利用这个视频便可以计算得到所需要的图片对应的位置. 这种建立Visual Map的方法相比于已有方法是十分方便的. 系统中，在线定位过程分为两个部分，分别是根据用户所提供的图片与数据库进行匹配和利用对极几何算法进行用户位置估计. 先将用户的图像与数据库中的图像进行匹配，找到最接近的四幅图像；然后利用SURF算法挑选出最接近的一幅图像，最后利用对极几何算法对用户进行精确定位[15].

图1 室内视觉定位系统框图

1.2离线阶段

为提高建立图像数据库速度，本文的方法是利用改进后的光流法对每一幅图片进行地理位置的计算，这样既提高了数据采集的速度又减小了使用的传感器的成本. 本文利用一个硬连接的摄像头，在行进的过程中进行视频的录制. 根据需要，视频会被每隔一段时间截取一幅图像，这些截取的图像可以用来进行地理位置的计算，然后对这些图片进行特征点的提取之后作为Visual Map中的视觉信息.

针对光流法计算结果受光线明暗变化影响而导致计算结果不准确的问题，本文根据图像灰度特征根据场景光线条件选取高灰度值的光流点进行光流的计算. 由于相机在转向过程中会产生光流偏移，本文提出了相机转向模型，将光流的偏移转换成行进的线速度，从而实现光流偏移的修正. 经过两次修正后的光流的计算结果，能够保证更准确的建立图像数据库，这对在线阶段定位是十分重要的. 从视频流中截取的每一幅图片都会进行特征提取. 本文提取Gist描述子和SURF特征作为图像特征.

1.3在线阶段

在线阶段，定位系统根据用户提供的图像进行检索与计算，得到并提供给用户精确明确的地理位置信息. 用户只需要输入一幅在所在位置拍摄的图片，系统便可以对用户进行定位并将定位结果反馈给用户. 系统在接收到用户提交的图片后，会将用户图片的Gist描述子与数据库中的描述子进行粗匹配. 根据Gist描述子的相似度选出四帧数据库中的图片. 然后对这四幅图片和用户提交的图片进行精匹配. 由于粗匹配时候选取出来4幅图片，因此利用SURF算法进行精匹配的过程需要进行4次. 在每次SURF匹配过程中，利用RANSAC算法在两幅图片中选取8对匹配点. 因此，一共选出了32对匹配点，这些匹配点根据4幅图片共分成4组. 由于数据库中每一幅图片都代表不同的地理位置，因此可以理解为，每一个地理位置都对应于8对匹配点. 由这4个位置的图片与用户图片计算得到的共32对匹配点可以作为对极几何定位算法的输入. 利用对极几何定位算法，可以很快地得到用户的位置信息，并将信息提供给用户.

2 光流法算法建立Visual Map

2.1传统光流法

利用光流法可以从相邻图像序列中的光流运动分析出物体在真实三维世界的运动情况. 光流是指在相邻的图片系列中每一个像素点所呈现的物体的运动. 光流法算法的核心思想是一个物体在相邻两幅图像中灰度值是不变的，由此根据运动场和光流场可得到光流法的核心方程为

Exu+Eyv+Et=0

式中Ex、Ey、Et表示图像中像素点灰度沿x、y、t方向的梯度. 根据Horn-Schunck算法，经过迭代计算可得到物体的水平速度和垂直速度. 迭代公式为

式中：fx为图像沿x方向梯度，fy为图像沿y方向的梯度，ft为图像沿时间方向梯度，n是迭代的次数，un+1和vn+1分别是迭代n+1次后的水平速度和垂直速度，a是平滑因子. 本文提出的改进后的光流法的系统框图见图2.

图2 光流法计算的系统框图

光流法虽然可以用于对三维运动的检测，但是光流法的计算过程很大程度上会受到室内环境的影响. 室内光线明暗变化会造成相邻图像的相同物体的灰度值不同；在室内转弯处，相机的转向会带来光流法的横向偏移. 这两个问题将会极大的影响利用光流法进行位移的计算和轨迹的估计. 因此本文提出了一种结合图像灰度特征的光流法改进方法，并提出照相机的转向模型将光流横向偏移转化为线速度，从而降低了误差，提高了光流法计算精度.

2.2结合灰度特征处理的光流法改进

本节对传统光流法进行了改进. 光流是指这些图像上像素点亮度模式运动的速度或者说是物体所带的发光部位的移动投影到图像平面所引起的像素点亮度变化. 光流表示了图像上像素亮度模式的变化，包含了真实场景中物体运动的丰富信息. 然而，由于室内环境的光线明暗变化，以及室内转角过多的影响，传统光流法在室内的使用会有很大的误差. 为了解决光线的明暗变化的影响，提出了结合灰度特征的光流法算法，选取受光线影响较小的区域进行位移的计算，从而减小误差. 选取灰度值较大像素点的原因是，在产生相同的灰度值变化的过程中，灰度值越大的点，相对灰度变化越小. 灰度变化率计算公式为

式中：γ为像素点灰度值的变化比率，Δg为相邻两幅图片同一物体灰度的变化值，g为图像点变化前的灰度值.

在相同的灰度值变化的情况下，灰度值越大的点，变化比率越小，代表灰度的变化对其影响越小. 选取灰度大于平均灰度的像素记录下每个选取出来的像素的位置用(lh(m),lv(m))表示. 选取过程为

式中：m表示像素，lh和lv是一维向量，这两个向量中的每一个元素都是一个像素点的横坐标或者纵坐标，G为阈值.

式中k为一维向量中元素的个数.

2.3光流的横向偏移修正

在进行运动轨迹估计时，研究人员或者小车的自运动中存在转弯是不可避免的. 室内场景往往在很短的时间内就进行了很大角度的转弯. 由于摄像机的转弯会在光流法中带来光流横向偏移，因此计算出来的速度结果将会有很大的误差. 在室内进行光流法的计算时，必须要将光流的水平偏移误差部分扣除出去，这样才能够得到更精确的结果. 本节提出修正光流横向偏移的光流法改进算法，旨在解决由于相机转向运动而导致的光流横向偏移问题.

图3 摄像机转向模型

图4 光流横向偏移计算

在图4中，S点为第一幅图片位置，相机方向是正前方，也即是走廊的垂直方向.T点为最终转向结束后位置，相机方向与转弯前方向垂直.M点为转弯过程中的任一点. 图中α为相机在运动过程中的转向角，|OM|为相机相对与转向中心的转向半径，也即是圆O的半径. 在图4中，该转向所引入的光流误差体现在运动中应为相机运动的线速度. 因此只需要计算出线速度，并且在光流法计算的结果中将线速度减掉即可. 计算公式为：

vli=ω·|OM|.

式中：α是旋转角度(按照规划路线行走时为已知的先验条件)，Tseq是相邻两幅图片的时间间隔，ω是转向的角速度.

3 实验仿真

3.1实验环境

为了验证所提算法的可靠性，将本算法用在走廊实验环境中，实验地点是哈尔滨工业大学通信技术研究所12楼. 实验场所的平面见图5.

图5 实验场所的平面

为避免手持设备因手的抖动等问题引入计算误差，建立了一个采集平台进行视频获取. 本文中的实验主要利用该平台进行视频的获取，并进行Visual Map的建立，平台图片见图6. 平台上所有的设备均是硬连接，这样是防止设备的晃动会引起误差. 利用这套设备，只需要在打开摄像头，边移动边采集视频即可. 本文中摄像头所采集的视频是MP4格式的，所截取图片是jpg格式.

图6 数据采集平台

3.2仿真结果

光流法的计算是计算截取视频得到的图片序列中每个像素的运动速度和位移. 利用光流法对相邻两幅图像的计算结果见图7. 图7(a)为图片序列的相邻两幅图片，将这两幅图片作为光流法的输入，即可得到图7(b)的计算结果. 图7(b)中的每一个蓝色点放大后均为带方向有大小的箭头，代表图片中每个像素的运动速度大小和方向. 由于图像序列是根据所录视频，按照人为设定的视觉截取得到，因此根据截取图片的时间与每两幅相邻图片计算得到的速度，便可以计算得到相对应的位移. 图片采样速率根据实际情况而定，本文采样速率为0.5 s截取一帧图片. 实际操作过程中如果速度过快则采样速率要更快，运动速度慢则可以降低采样速率.

图8为光流法计算相邻两幅图片的累计误差概率曲线，实验采样图片共930张图片，每31张一组，每组图片共可以计算30个位移，对这900个位移进行误差统计画出CDF曲线. 两条曲线是分别利用改进后的光流法算法与传统的光流法的算法对相同的图片序列进行计算统计得到. 图片序列是，严格每隔80 cm进行一次照片的拍摄，共连续拍摄100组照片. 由图8可看出，改进后算法的计算准确度要明显好于传统光流法的计算结果. 经过改进的光流法，即本文提出的算法，计算结果70%的概率误差小于1.2 cm，而传统光流法的计算的误差小于2 cm的概率是70%. 本文的算法计算结果最大误差只有2.4 cm，小于传统光流法的2.7 cm.

(a)相邻两幅图片

(b)光流法计算结果

利用本文所提出的Visual Map方法对用户进行定位，在Visual Map建立的环境内随机采集图片进行输入共进行150次定位，得到的定位结果与传统视觉室内定位方法得到的定位结果以及文献[8]中提出快速建立Visual Map的算法的定位精度进行比较并绘制CDF曲线见图9. 三种方法在线定位算法均为对极几何算法，只有离线建库算法不同.

图8 传统光流法与改进的光流法计算误差

Fig.8 Calculation error of traditional optical flow algorithm and improved algorithm

图9 定位误差的CDF

本文提出算法建立的Visual Map进行室内定位得到的结果的误差小于1 m的概率是26%，小于2 m的概率是70%. 本文的定位误差在2.5 m以内的时候略好于视频流建库的定位方法，在2.5 m以上的时候略差与该方法. 虽然本文提出的方法比传统定位方法误差略大，但是以较小的误差增大换取建库时间的大幅度减小是值得的. 经过分析，定位误差在2.5 m以上时的定位效果与视频流方法稍有不如，原因是，由于光流法对弯道环境的计算仍然存在少量误差，这些误差是由于本文平台只使用了单一摄像头，相比视频流方法使用了较少的传感器. 虽然本文的算法定位误差在2.5 m以上时增加了一点，但是相比于视频流方法操作更加简单，要求也更加宽松，比如：不再需要匀速运动与角度转变信息的实时记录等. 定位误差最大可达到5 m以上，这在室内定位时不可接受的.

由于传统的视觉室内定位系统是逐点采集数据，因此建立的数据库中图片所对应的地理位置几乎是完全准确的，不存在误差，因此定位结果的误差主要来源于在线定位算法. 本文采用的光流法在经过提升后虽然误差大幅度降低，但是仍然存在很小的误差，因此在定位结果的误差除了存在于在线定位算法的误差，也来自于离线数据库的误差，因此定位误差会有所上升. 本文提出的算法目的在以少量的精度降低换取离线采集数据的时间人力成本.

本实验室使用的传统室内定位方法在采集数据时使用激光雷达采集距离信息，使用摄像头采集图片. 由于需要逐点采集，根据实验场景情况在实验过程中，每隔50 cm便停下进行数据的采集，不考虑运动过程的时间，每次采集数据需要大概5 s共采集224幅图片，花费18.7 min. 利用本文的方法，利用摄像头对同样的场景进行视频的录制，采集数据过程共花费了2 min左右，共截取图片238张. 由此可以看出，本文提出的算法虽然使得定位精度略有下降，但是采集数据花费的时间大大降低，因此本算法非常适合在大面积多楼层建筑内使用.

4 结 论

本文提出了一种基于光流法的Visual Map快速建立算法. 本文对光流法进行了改进，提高了光流法的计算准确度，使得该算法能够更好地用于视觉定位系统中，因为能够建立一个更准确的Visual Map有助于提高在线阶段时候的定位精度. 相比于传统的视觉定位系统和已存在的视频流快速建立Visual Map算法，本文的方法充分利用了图像中的信息，比传统视觉定位系统建立数据库要更方便，比已有的视频流算法所用的设备更简便、要求更宽松，达到了快速建库的目的. 经过实验，本文提出的方法可以很好的用于复杂的室内环境中，降低了建立Visual Map的复杂度.

[1] SADEGHI H, VALAEE S, SHIRANI S. A weighted KNN epipolar geometry-based approach for vision-based indoor localization using smartphone cameras[C]// IEEE 8th Sensor Array and Multichannel Signal Processing Workshop. Coruna: IEEE Computer Society, 2014: 37-40. DOI: 10.1109/SAM.2 014.6882332.

[2] GUAN Kai, MA Lin, TAN Xuezhi, et al. Vision-based indoor localization approach based on SURF and landmark [C] //2016 International Wireless Communications and Mobile Computing Conference, 2016 IWCMC. Paphos: Institute of Electrical and Electronics Engineers Inc., 2016: 655-659. DOI: 10.1109/IWCMC. 2016.7577134.

[3] ELLOUMI W, LATOUI A, CANALS R, et al. Indoor pedestrian localization with a smartphone: a comparison of inertial and vision-based methods [J]. IEEE Sensors Journal, 2016, 16(13): 5376-5388. DOI: 10.1109/JSEN.2016.2565899.

[4] ALADREN A, LOPEZ G, PUIG L, et al. Navigation assistance for the visually impaired using RGB-D sensor with range expansion [J]. IEEE Systems Journal, 2016, 10(3): 922-932. DOI: 10.1109/JSYST.2014.2320639.

[5] MENG Lili, SILVA C, ZHANG Jie. 3D visual SLAM for an assistive robot in indoor environments using RGB-D cameras[C]// 9th International Conference on Computer Science & Education, ICCSE 2014. Vancouver: Institute of Electrical and Electronics Engineers Inc, 2014: 32-37. DOI: 10.1109/ICCSE.2014.6926426.

[6] TURNER E, CHENG P, ZAKHOR A. Fast, automated, scalable generation of textured 3D models of indoor environments [J]. IEEE Journal of Selected Topics in Signal Processing, 2017, 9(3): 409-421. DOI: 10.1109/JSTSP. 2014.2381153.

[7] ZHANG Y, HU W, XU W, et al. NaviGlass: Indoor localisation using smart glasses [C] //International Conference on Embedded Wireless Systems and Networks, EWSN2016. Graz: Junction Publishing, 2016:205-216.

[8] XUE Hao, MA Lin, TAN Xuezhi. A fast visual map building method using video stream for visual-based indoorlocalization [C] //2016 International Wireless Communications and Mobile Computing Conference, 2016 IWCMC. Paphos: Institute of Electrical and Electronics Engineers Inc., 2016: 650-654. DOI:10.1109/IWCMC .2016.7577133.

[9] RAO A S, GUBBI J, MARUSIC S, et al. Crowd event detection on optical flow manifolds [J]. IEEE Transactions on Cybernetics, 2016, 46(7): 1524. DOI: 10.1109/TCYB.2015. 2451136.

[10]DENMAN S, FOOKES C, SRIDHARAN S. Improved simultaneous computation of motion detection and optical flow for object tracking [C]// 2009 Digital Image Computing: Techniques and Applications, 2009 DICTA. Melbourne: IEEE Computer Society, 2009: 175-182. DOI: 10.1109/DICTA.2009. 35.

[11]AGARWAL A, GUPTA S, SINGH D. Review of optical flow technique for moving object detection[C] //2016 2nd International Conference on Contemporary Computing and Informatics(IC3I). Noida: Institute of Electrical and Electronics Engineers Inc., 2016:409-413. DOI: 10.1109/IC3I.2016.7917999.

[12]KALE K, PAWAR S, DHULEKAR P. Moving object tracking using optical flow and motion vector estimation [C]// 2015 4th International Conference on Reliability, Infocom Technologies and Optimization, 2015 ICRITO. New York: Institute of Electrical and Electronics Engineers Inc., 2015:1-6. DOI: 10.1109/ICRITO.2015.7359323.

[13]HAN Hong, TONG Minglei. Human detection based on optical flow and spare geometric flow [C] // 2013 Seventh International Conference on Image and Graphics, 2013 ICIG. Hong Kong: IEEE Computer Society, 2013: 459-464. DOI: 10.1109/ICIG.2013.96.

[14]WANG Yandong, DONG Qihao. Using optical flow with principal direction screen strategy for road navigation [C]. // 2016 9th International Symposium on Computational Intelligence and Design, 2016 ISCID. Hang Zhou: Institute of Electrical and Electronics Engineers Inc., 2016:52-55. DOI: 10.1109/ISCID.2016.2021.

[15]BAY H, ESS A, TUYLARRS T, et al. Speeded-up robust features(SURF) [J]. Computer Vision and Image Understanding, 2008, 110(3): 404-417. DOI: 10.1016/j.cviu.2007.09.014.

EstablishingVisualMaprapidlyusingopticalflowtechnique

MA Lin, ZHAO Hang, TAN Xuezhi

(Communication Research Center, Harbin Institute of Technology, Harbin 150001, China)

A Visual Map can be seen as an image database with rich location information. All images or image features stored in this database have their corresponding location information. An accurate localization needs a large image database, but building a large database must be laborious and time-consuming. In order to solve this problem, a method based on Optical Flow Technique is proposed to establish a Visual Map. The accuracy of Optical Flow algorithms is always influenced by the difference of indoor illumination and lateral deviation of optical flow caused by turning of the cameras. A method to improve optical flow algorithm is proposed and the new algorithm is used to calculate the displacement of image sequences to acquire location information of the camera and each picture. The experimental results show that the probability of localization error less than 1 meter and 2 meters is 26% and 70%, respectively. Compared with traditional visual indoor localization system, using optical flow algorithm to build a visual map is much more convenient and time-saving, although the positioning accuracy of the proposed method is slightly worse than the traditional method. Although the performance of the proposed method is similar to the video stream method, it needs fewer sensors to build image database and can be used in more complicated environment. Overall, the proposed method will perform well in indoor visual localization systems especially in large buildings and changeable places.

computer application; Visual Map; optical flow; indoor localization system; image database

10.11918/j.issn.0367-6234.201706026

tp399

A

0367-6234(2017)11-0024-06

2017-06-05

国家自然科学基金(61571162); 黑龙江省自然科学基金(F2016019)

马 琳(1980—)，男，副教授，博士生导师;谭学治(1957—)，男，教授，博士生导师

马 琳，malin@hit.edu.cn

(编辑苗秀芝)