陳偉杰，孫作雷

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

基于LK光流法的單目視覺里程計(jì)

陳偉杰，孫作雷

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

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

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

0 引言

智能機(jī)器人在近年來越來越多地進(jìn)入公眾視野。要想讓機(jī)器人實(shí)現(xiàn)全自主的移動(dòng)，其關(guān)鍵技術(shù)是即時(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ù)包含著豐富的信息。視覺里程計(jì)(Visual Odometry，VO)就是一種基于視覺傳感器的機(jī)器人定位方法，無需場(chǎng)景和運(yùn)動(dòng)的先驗(yàn)信息，可以不受移動(dòng)部件的打滑、磨損、漂移等因素的誤差影響，而且只要有光線的地方利用相機(jī)就可以使用，因而被廣泛應(yīng)用到各種移動(dòng)機(jī)器人中，如火星探測(cè)器“勇氣號(hào)”和“機(jī)遇號(hào)”[2]、無人飛行器[3]以及陸地機(jī)器人[4]等。

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

1 特征提取

對(duì)于輸入的圖像序列，全局運(yùn)算過于繁瑣，因此需要提取一些特征點(diǎn)。快速魯棒特征(Speed Up Robust Feature，SURF)[7]是目前十分流行的算法，繼承了較成熟的SIFT[8]算法的優(yōu)點(diǎn)的同時(shí)提高了運(yùn)算效率。

(1)

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

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

(2)

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

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

圖1 特征點(diǎn)判定示意圖

2 特征追蹤

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

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

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

(3)

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

(4)

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

(5)

為簡(jiǎn)化上式，定義等式:

(6)

(7)

因此式子可以簡(jiǎn)化為:

(8)

(9)

定義

(10)

(11)

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

dopt=G-1b

(12)

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

3 運(yùn)動(dòng)估計(jì)

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

圖2 對(duì)極幾何模型

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

Ex=l′或Fx=l′

(13)

E=K′TFK

(14)

由點(diǎn)在直線上表示為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ùn)動(dòng)估計(jì)。

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

4 實(shí)驗(yàn)結(jié)果

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

圖3 實(shí)驗(yàn)原圖像000000

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

圖4 實(shí)驗(yàn)原圖像“房子”

實(shí)驗(yàn)結(jié)果如表1所示。

表1 不同圖像、算法比較

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

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

[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.微型機(jī)與應(yīng)用，2017,36(21)：45-47,50.

2017-05-02)

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

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