基于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)、機器學習。