基于三角剖分的視覺里程計特征點匹配算法*

陳一偉， 張會清， 蘇園竟

(北京工業大學 信息學部，北京 100124)

0 引 言

目前，單目視覺里程計(monocular visual odometry)[1]根據是否需要提取特征，主要分為特征點法與直接法，基于特征點法的單目視覺里程計的方案較為成熟，精度普遍高于直接法。因此，本文基于特征點法的框架進行研究，其研究的熱點問題是如何得到精確的匹配的特征點對。根據相鄰兩幀圖像計算匹配對，求解載體位姿變化的這種增量式求解方法，對匹配點對的正確性尤為敏感。為此研究者們在長期的探索中，研究出了許多十分穩健的圖像局部特征描述方法，以尺度不變特征變換(scale invariant feature transform,SIFT)[2]算法為代表。盡管這類方法表現好，但實時性較差。因此，有研究者利用稀疏光流法直接跟蹤特征點，避免進行耗時的描述子計算，以著名的LK(Lucas-Kanade)光流[3]算法為代表。現有的特征點匹配只考慮了特征點的局部關系，然而由于實際場景中不可避免存在重復的紋理，使得不同特征點的描述子可能相似，因此僅僅依靠特征點的局部特性解決誤匹配是很困難的。

本文提出一種應用于單目視覺里程計的特征點匹配方法，不同于其他匹配方法，本文利用三角剖分去表示特征點之間的相對關系，引入了圖像的全局性。

1 基于特征的單目視覺里程計算法

本文采用基于特征的單目視覺定位方法。首先，單目相機獲取的序列圖像，對序列圖像進行畸變矯正、灰度化與高斯濾波；然后，在預處理后的圖像上進行特征點提取與匹配；并獲取相鄰圖像幀的匹配點，對錯誤匹配進行剔除；最后利用對級約束進行運動估計，求解當前幀的位姿。

1.1 特征點的提取

采用FAST(feature from accelerated segment test)[4]算法提取特征點，該算法相較SIFT、加速穩健特征(speeded up robust features,SURF)[5]和HARRIS[4]等特征點檢測算法，有更高的實時性，因此采用Fast作為特征點檢測算法。在特征點提取過程中檢測每個像素點與周圍點的差值，根據給定的閾值，判定該點是否為特征點。同時，為了防止特征點分布過于密集，采用非極大值抑制(non-maximal suppression，NMS)[6]的方法去除與周圍像素差值小的點。

1.2 特征點的匹配

在特征點提取過程中，使用LK光流法跟蹤代替匹配算法，確定特征點匹配對。這種算法假設像素點周圍領域內的圖像灰度是不變的，通過最小二乘法求解像素點在周圍領域內的光流方程。通過結合像素點周圍的局部信息，所以對噪聲不敏感。為了有效處理大像素移動，構建圖像金字塔。在頂層計算光流，并初始化一個猜測并傳遞到下一層，依次傳遞到底層。通過迭代的光流計算，找到匹配點。

1.3 位姿估計

如圖1所示，需要求解Ck-1到Ck的狀態：使用旋轉矩陣R(r11,r12,r13,r21,r22,r23,r31,r32,r33)來描述相機旋轉，使用平移向量t來描述相機的平移。

圖1 位姿模型

xbi=Rxai+t

(1)

式中xai,xbi為兩個像素點歸一化平面上的坐標

pi=Kxi

(2)

式中pai,pbi為兩個像素點的坐標。這里的K為相機的內參矩陣，通過標定可以得到。根據對極幾何(epipolar geometry)[7]關系可以把求解位姿轉換為求解一個3×3的基礎矩陣F

(3)

現有的基礎矩陣估計方法[8]包括線性算法、非線性算法和魯棒估計算法。本文采用張正友提出的最小平方中值(least median of squares,LMedS)[9]算法等，此種方法屬于魯棒估計算法，能夠較好應對噪聲和誤匹配，估計精度較高。通過最小化重投影誤差(reprojection error)獲得最優解。

步驟如下：

1)從匹配點對序列中抽取m組樣本點，每組樣本由q個點組成。

2)采用8點法[11]計算其中一個樣本Xi的基礎矩陣Fi。

3)對于Fi，計算每個匹配點集的重投影誤差erri，并記錄誤差中值Mj。

(4)

(5)

式(4),式(5)中的符號“^”代表的是該點的投影估計點

(6)

4)重復步驟(2)、步驟(3)，在m組樣本中尋找最小的中值Mmin和其對應的Fmin。

采用LMedS法獲得本質矩陣后，使用支持向量機(support vector machine,SVD)[11]分解得到平移矩陣T和旋轉矩陣R，結合尺度信息獲得位姿變化。

2 結合特征點三角剖分的誤匹配剔除

結合特征點三角剖分的誤匹配剔除步驟：對參考幀特征點進行空間關系的初始化，獲得空間位置的相對關系；將這個關系轉移到當前幀，通過檢測重疊區域而獲得誤匹配的候選點；評估誤匹配候選點，獲得誤匹配點。

假設環境無遮擋(即環境中不存在前后景關系時)。在這種假設下，三維空間映射到二維圖像上時，它們之間的相對位置保持不變。利用這種空間上的點與點之間的約束，可以剔除大量匹配錯誤的特征點，增強匹配算法的魯棒性。

2.1 空間關系初始化

空間關系采用特征點間連線形成的三角形來描述。其初始化的過程，為對參考幀特征點進行Delaunay三角剖分。由于三角網的時間效率較低，而分治算法的空間效率較低，因而選擇逐點插入法中的Bowyer-Watson[12]作為Delaunay三角剖分的實現方式。

三角剖分算法始于一個外部的虛擬三角形，所有的外部點都連接著兩個虛擬三角的頂點，通過檢查可以確定由點集構成的外部輪廓。再逐個加入內部點，并在三角形的外接圓內搜索該點，去掉包含該點的三角剖分。利用Voronoi劃分確定在何處插入Delaunay線，重新構造三角形。

2.2 獲取重疊區域

使用參考幀特征點的連接關系，連接對應的匹配點，形成新的三角形。掃描新產生的三角連接圖，記錄重疊區域的三角形。步驟如下：

1)將參考幀的三角關系轉換為當前幀的三角關系；

2)使用等比縮小的灰度圖像來記錄所生成的三角形；

3)使用第(2)步的歷史信息，來判斷重疊區域的位置，并記錄存在重疊的三角形。

2.3 誤匹配候選點選取

無遮擋的假設下，圖像中像素的位置關系保持不變。即不管如何移動，其特征點三角剖分形成的新三角形在傳遞過程中始終不存在重疊區域。若三角形存在重疊區域，則評估該三角形的三個頂點，得到可能誤匹配的點。

誤匹配候選點選取過程中，根據重疊面積由大到小依次剔除重疊的三角形，直到無重疊區域。

重疊區域大致可以分為以下三種情況：

1)△ABC與△BCD形成的三角形重疊面積相等，如圖2(a)。這種情況下，為了剔除盡量少的誤匹配點，依次選擇剔除重疊面積最大的三角形，然而存在重疊面積相同的△ABC或△BCD，雖然消除其中一個三角形即可消除重疊區域，為了得到更好的匹配點正確率，這里將重疊面積相同的三角形也一并剔除。即剔除了△ABC和△BCD，記錄A，B，C，D4個頂點的誤匹配均有可能造成重疊。

2)△ABC存在于△BCD的內部，如圖2(b)。這種情況下，只需去除△ABD或△BDF均可消除重疊區域。又因為△ABD與△BDF重疊面積相同，因此，記錄A，B，D，F4個頂點的為可能的誤匹配點。

3)如圖2(c)，這種情況下，去除△ACE或△CEF均可消除重疊區域。記錄A，C，E，F4個頂點為可能的誤匹配點。

圖2 重疊情況

對上述記錄的每個誤匹配候選點計算可信度C

(7)

式中numj為該匹配點所連接形成的三角形數量，Pi為其中無重疊的三角形數量，Ni為重疊的三角形數量。對可信度Cj進行排序，去掉可信度不大于中位數的特征點，例如圖2(a)，誤匹配點的可信度為CA=0，CB=0，Cc=0，CD=0，中位數值為0，所以剔除點A，B，C，D。圖2(b)，誤匹配點可信度為CA=-4，CB=0，CD=-5，CF=-3，中位數值為-4，所以剔除點A，B，D。圖2(c)，CA=-1，CC=-5，CE=-6，CF=-6，中位數值為-5.5，剔除點E，F。

2.4 獲得誤匹配點

考慮到實際場景中有可能存在的遮擋，會出現前后景，造成局部的圖像塊的相對位置不能保持不變，因而會違背本文算法前提條件，即特征點的相對位置保持不變，使得算法失效。如圖3所示。

圖3 環境存在遮擋的情況

本文在相鄰幀之間的進行特征點提取與匹配，在遮擋物在圖像上較小或較細時會影響判斷。為了解決這個問題，本文引入SIFT算法計算上述需剔除的匹配點對的描述向量。

(8)

使用歐式距離表示向量的匹配程度。距離越小匹配程度越高，匹配程度高的點保留。

3 實驗與分析

本文實驗用電腦配置為:CPU酷睿i7—6500U 2.4 GHz，8 G內存，Windows 8操作系統，開發環境為VS2013,OpenCV2.4.13。

實驗分為3組，每組除了特征點匹配過程不同，其余配置與程序均為相同。第一組匹配采用LK算法，記為傳統算法1；第二組匹配采用SIFT算法，記為傳統算法2；第三組匹配采用本文算法，使用Delaunay算法引入特征點的全局性，并結合LK算法與SIFT算法的優勢，快速準確匹配特征點。

采用數據集KITTI[13]對本文算法進行檢驗。圖4為實驗的設置框圖。

圖4 實驗設置框圖

圖5為對特征點Delaunay三角剖分的結果。圖6中橙色部分為誤匹配區域。其中形成重疊區域的三角形的頂點作為誤匹配候選點，經由上述算法獲得最終的匹配點。圖7為匹配點的正確率。

圖5 三角剖分

圖6 誤匹配區域

圖7 匹配正確率

本文算法基于LK算法，在實驗過程中，匹配精度幾乎是沿著LK算法的邊沿提升的，可以容易看出本文算法增強了匹配的魯棒性，減少了(如1400，1900幀)匹配精度的突然下降；而與SIFT又有相近的匹配率表現。

由圖8中的時間消耗對比可以發現，SIFT特征點匹配法為代表的傳統算法圖像幀的處理時間最久，以LK特征點跟蹤法為代表的傳統算法的每幀圖像處理時間較快。

圖8 時間消耗

由圖9中的實驗軌跡對比可以發現，以SIFT特征點匹配法為代表的傳統算法2的精度略高于以LK特征點跟蹤法為代表的傳統算法1。

圖9 軌跡

本文提出的結合三角剖分的方法，在特征點匹配階段使用了特征點之間的相互關系，可以發現與只考慮的特征點局部性的兩個傳統方法相比較，可以有效提高定位精度。在對匹配點的正確率采用模型的內點比來描述

(9)

經不同匹配方法對比，本文算法、SIFT、LK 、SURF、ORB的平均每幀圖像的處理時間分別為186.25，895.69，140.91，143.33，114.91 ms；正確匹配率分別為85.87 %，85.09 %，82.36 %，79.40 %，67.47 %。本文算法結合三角剖分的全局約束，在LK算法基礎上處理時間增加32.17 %，匹配率提升了3.51 %。匹配正確率與現有算法相比有很大優勢。

4 結 論

實驗證明：能夠以較小的代價，提高視覺里程計的精度。本文采用的是單目相機沒有深度信息，因此，在有前后景的場景里引用了SIFT算法減少錯誤判定。然而，在以Kinect為代表的深度相機中，可以直接獲得深度信息，判斷前后景關系。這種情況下，可以在進行三角剖分的同時引入深度信息的約束，結合深度信息對三角形重合的匹配點誤匹配判定，不再需要再計算SIFT描述子，可以更好滿足實時要求。因此，在采用單目、雙目或者深度相機的視覺里程計中，都具有較高的實用價值。