基于光流法算法的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

(編輯苗秀芝)