陳偉杰，孫作雷

(上海海事大學(xué) 機(jī)器辨識與交互研究組，上海 201306)

基于LK光流法的單目視覺里程計

陳偉杰，孫作雷

(上海海事大學(xué) 機(jī)器辨識與交互研究組，上海201306)

在移動機(jī)器人快速發(fā)展的今天，視覺里程計是通過視覺傳感器進(jìn)行導(dǎo)航定位的主要方式之一。文章介紹了基于單個攝像頭的單目視覺里程計的一種實現(xiàn)方法，使用SURF算法提取特征點，用LK光流法進(jìn)行特征追蹤，相比于傳統(tǒng)特征匹配在運算效率上有極大的提高，再對特征點計算位移與旋轉(zhuǎn)量，以里程計的方式達(dá)到定位目的。詳細(xì)介紹了視覺里程計的數(shù)學(xué)原理以及SURF算法和LK算法的原理及其數(shù)學(xué)推導(dǎo)、單目視覺里程計的尺度不確定原理。最后通過對比確定LK算法的優(yōu)勢以及最優(yōu)參數(shù)的選擇。

視覺里程計；LK光流法；圖像處理；特征跟蹤；多視圖幾何

0 引言

智能機(jī)器人在近年來越來越多地進(jìn)入公眾視野。要想讓機(jī)器人實現(xiàn)全自主的移動，其關(guān)鍵技術(shù)是即時定位與地圖構(gòu)建(Simultaneous Localization and Mapping，SLAM)，使機(jī)器人通過傳感器感知周邊環(huán)境，通過傳感器反饋信息構(gòu)建出一幅“地圖”，從而達(dá)到自主定位和導(dǎo)航的功能。

根據(jù)傳感器的種類不同，SLAM技術(shù)可以進(jìn)行分類，如激光SLAM[1]、視覺SLAM。其中視覺傳感器可以獲取到的影像數(shù)據(jù)包含著豐富的信息。視覺里程計(Visual Odometry，VO)就是一種基于視覺傳感器的機(jī)器人定位方法，無需場景和運動的先驗信息，可以不受移動部件的打滑、磨損、漂移等因素的誤差影響，而且只要有光線的地方利用相機(jī)就可以使用，因而被廣泛應(yīng)用到各種移動機(jī)器人中，如火星探測器“勇氣號”和“機(jī)遇號”[2]、無人飛行器[3]以及陸地機(jī)器人[4]等。

視覺里程計的概念最早在1980年提出[5]，其大致理論框架為：特征提取、特征匹配或追蹤以及運動估計，主要理論依據(jù)是機(jī)器視覺中的多視圖幾何[6]，即通過前后幀圖像的匹配特征點對集合計算出相機(jī)在獲取兩幀圖像時的位姿變化。單目視覺僅由一個相機(jī)實現(xiàn)，雖然有尺度不確定性的缺陷但是方便實用、成本低。本文闡述一種基于LK光流法進(jìn)行特征追蹤的單目視覺里程計的方法原理。

1 特征提取

對于輸入的圖像序列，全局運算過于繁瑣，因此需要提取一些特征點?？焖亵敯籼卣?Speed Up Robust Feature，SURF)[7]是目前十分流行的算法，繼承了較成熟的SIFT[8]算法的優(yōu)點的同時提高了運算效率。

(1)

取近似值將濾波模型“量化”，簡化后的濾波模型D≈L，得到簡化后的海森矩陣為：

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

(2)

式中0.9是經(jīng)驗值，是一個常數(shù)，補償簡化后的誤差。當(dāng)Happrox>1時將該點作為特征候選點。

不同于SIFT算法中的圖像金字塔尺度空間，SURF建立尺度空間利用縮放濾波器大小實現(xiàn)，有效降低運算量。取得尺度空間后，對每個特征候選點，取其上下兩層尺度的26個鄰域點進(jìn)行比較，如圖1所示，當(dāng)它的灰度值是26個點中的最大值時，則判定為特征點。

圖1 特征點判定示意圖

2 特征追蹤

確定特征點后需要將前后幀的圖像特征點配對才可以進(jìn)行解算，而對特征直接進(jìn)行配對需要較大的運算量，此時可以用LK光流法[9]追蹤特征點達(dá)到尋找匹配點的目的。

光流法在近些年十分熱門，在計算機(jī)視覺方面應(yīng)用廣泛，特別是目標(biāo)追蹤方面卓有成效。光流是指三維物體的運動在二維平面上的投影。LK算法是稀疏光流法的代表，取局部區(qū)域?qū)ζ涔饬鬟M(jìn)行追蹤，效率高。

LK算法基于三個前提假設(shè)：亮度恒定、運動幅度小、局部一致性。LK算法的目的是對某一幀中的特征點，確定下一幀圖像中該點所在的位置。首先取特征點周圍的一個窗w，根據(jù)局部一致性假設(shè)窗w內(nèi)的點有相同光流，且假設(shè)亮度恒定，前后幀圖像表示同一點的灰度值相等，而在運動幅度不大的情況下，只需要在一個小范圍內(nèi)搜索灰度值最相近的窗即可。因此LK算法所求特征點u的光流d可以總結(jié)為求誤差函數(shù)ε(d)的最小值：

(3)

由于完全相同的匹配點只可能有一個，所以最小值也是極小值，也就是偏導(dǎo)為0。

(4)

對ε(d)求偏導(dǎo)之后，再對J(x+dx,y+dy)取其一階泰勒展開式可以得到：

(5)

為簡化上式，定義等式:

(6)

(7)

因此式子可以簡化為:

(8)

(9)

定義

(10)

(11)

則光流d的極值可以表示為:

dopt=G-1b

(12)

根據(jù)光流d，也就是運動量，特征點u就可以確定在下一幀圖像所在的位置，那個點就是匹配點。

3 運動估計

根據(jù)兩幀圖像匹配點求解運動關(guān)系理論依據(jù)稱為對極幾何。現(xiàn)有兩幅不同位置拍攝同一物體X的圖像模型如圖2所示。C、C′表示相機(jī)位置，兩者之間的連線稱為基線b，與圖像平面的交點e、e′為對極點，b與X所確定的平面稱為對極平面，對極平面與圖像平面的交線l、l′為對極線，其中b與e由左右圖像唯一確定，對極平面與對極線有無限個。

圖2 對極幾何模型

顯然，當(dāng)已知圖像左側(cè)上的點x，根據(jù)相機(jī)拍照的原理與對極幾何，x在圖右側(cè)上的匹配點x′必然在對極線l′上。這種映射關(guān)系用數(shù)學(xué)表示為3×3大小的本質(zhì)矩陣E或基本矩陣F，分別對應(yīng)經(jīng)過標(biāo)定去畸變的圖像與原圖像。

Ex=l′或Fx=l′

(13)

E=K′TFK

(14)

由點在直線上表示為xTl=0，可以得到Longuet-Higgins公式：

x′TEx=0

(15)

設(shè)C到C′的位移和旋轉(zhuǎn)量分別為t和R，稱為相機(jī)外參，包含于表示兩幀圖像映射關(guān)系的E和F的參數(shù)中。因此求解本質(zhì)矩陣E或者基本矩陣F，即可得知兩幀圖像之間的位姿變化量，完成相機(jī)的運動估計。

在實際應(yīng)用過程中，直接對圖像去畸變再進(jìn)行處理過于繁瑣，因此通常直接使用原圖像的匹配點代入公式(15)，先計算出本質(zhì)矩陣F，使用RANSAC[10]算法對其進(jìn)行優(yōu)化，剔除誤差；然后根據(jù)標(biāo)定矩陣得到本質(zhì)矩陣E；最后對E進(jìn)行奇異值分解得到相機(jī)外參R和t。

4 實驗結(jié)果

此次實驗基于VS2012，openCV2.4.9進(jìn)行，實驗數(shù)據(jù)主要來源于kitti中的第00組測試圖像中的前1 000幀圖像，圖像大小為1 241×376，第一幀圖像序號為000000，如圖3所示。

圖3 實驗原圖像000000

LK光流法極大地提高了尋找匹配點的速度，減少了運算時間。除了運算速度快，LK算法還可以追蹤特征點，不必對每幅圖像進(jìn)行特征提取操作，直到特征點數(shù)量小于閾值T時才進(jìn)行一次特征提取，進(jìn)一步減少了程序運行的時間。將LK算法與傳統(tǒng)匹配算法最近鄰搜索算法(FLANN)[11]進(jìn)行比較。另取一組大小為512×272的圖像，圖像如圖4所示。實驗中SURF算法的海森矩陣參數(shù)設(shè)置為400，該值越小，特征點越多。

圖4 實驗原圖像“房子”

實驗結(jié)果如表1所示。

表1 不同圖像、算法比較

結(jié)果中平均時間由運行三次求算術(shù)平均得到，可以看出LK光流法的運行時間遠(yuǎn)小于FLANN匹配算法。在圖像特征點數(shù)增加5倍左右的情況下，F(xiàn)LANN匹配所需花費的時間也需要增加為原來的5倍多，而LK光流追蹤卻只增加2.5倍左右的花費時間，也就是說特征點數(shù)量越大，LK算法的優(yōu)勢越加明顯。

為得到較優(yōu)的參數(shù)，取測試圖像序列前1 000幀圖像進(jìn)行比較。其中SURF的海森矩陣參數(shù)取200。將閾值T分別設(shè)置為1 000、1 500、2 000，當(dāng)特征點數(shù)小于該參數(shù)時重新進(jìn)行一次特征提取。實驗結(jié)果示例如圖5所示。

圖5 海森矩陣參數(shù)為200時不同閾值參數(shù)實驗結(jié)果

從圖5中可以較為直觀地看出閾值T為1 000時的誤差明顯大于另外兩者，相同海森矩陣參數(shù)下閾值設(shè)為1 500和2 000較為接近。可以得到初步結(jié)論，平均特征點數(shù)目越多，實驗結(jié)果越好，而且可能存在臨界值。

為進(jìn)一步分析，本文使用kitti提供的誤差評估程序?qū)φ`差進(jìn)行評估，取不同的海森矩陣參數(shù)和閾值進(jìn)行比較，得到平均誤差如表2所示，主要考慮平均位移誤差。同時比較不同參數(shù)所需的運行時間，三次運行取平均值，結(jié)果如表3所示。

表2 不同參數(shù)的位移誤差 (%)

表3 不同參數(shù)運行時間 (s/百幀)

從表2、表3中可以看出，海森矩陣參數(shù)值越大，所需時間降低，位移誤差增加；閾值參數(shù)越大，所需時間增加，位移誤差減小。

縱向比較，海森矩陣參數(shù)變化時，時間變化量約為5～10 s/百幀，而位移誤差在50和100時變化不大，值為200時卻成倍增長。橫向比較，閾值T變化時，時間變化量較大，約有20～25 s/百幀，而位移誤差在1 500與2 000時變化量較小，1 000時誤差較大。綜合比較，在50、100和1 500、2 000幾個數(shù)據(jù)中，位移誤差相差1%左右的情況下，選擇較小的海森矩陣參數(shù)比較小的T值多花費15～20 s/百幀的時間，50/1 500的參數(shù)與100/2 000的參數(shù)誤差僅相差0.2%，時間少了16 s/百幀。

因此更改閾值T更有效于速度調(diào)節(jié)，但不宜過低；更改海森矩陣參數(shù)更有效于精度調(diào)節(jié)，但不宜過高。若只追求精確度，選擇小的海森矩陣參數(shù)和大的閾值T。

5 結(jié)論

本文詳細(xì)介紹了基于SURF算法進(jìn)行特征提取，基于LK光流法進(jìn)行特征追蹤的單目視覺里程計。對比分析了LK光流法的優(yōu)勢，實驗證明LK算法可以極大地提高程序運算效率，減少運行時間。通過對比不同參數(shù)的結(jié)果選擇較優(yōu)的參數(shù)使得算法有較快的運行速度也有較低的位移誤差。單目視覺有良好的前景，有待進(jìn)一步發(fā)展，相信不久的將來就可以進(jìn)入每個人的生活之中。

[1] 李延炬，肖宇峰，古松,等.基于激光傳感器的SLAM數(shù)據(jù)關(guān)聯(lián)算法的研究[J].微型機(jī)與應(yīng)用，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，F(xiàn)RAUNDORFER 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.微型機(jī)與應(yīng)用，2017,36(21)：45-47,50.

2017-05-02)

陳偉杰(1993-)，男，碩士研究生，主要研究方向：計算機(jī)視覺。

孫作雷(1982-)，男，博士，副教授，主要研究方向：機(jī)器人定位與地圖構(gòu)建(SLAM)、機(jī)器學(xué)習(xí)。