如何提取、匹配圖像特征點(diǎn)

視覺(jué) SLAM 主要分為視覺(jué)前端和優(yōu)化后端。

前端也稱為視覺(jué)里程計(jì)（VO）。

VO 的實(shí)現(xiàn)方法，按是否需要提取特征，分為特征點(diǎn)法的前端以及不提特征的直接法前端。

基于特征點(diǎn)法的前端，長(zhǎng)久以來(lái)被認(rèn)為是視覺(jué)里程計(jì)的主流方法。

本文，我們將從特征點(diǎn)法入手，學(xué)習(xí)如何提取、匹配圖像特征點(diǎn)。

01

特征點(diǎn)

VO 的主要問(wèn)題是如何根據(jù)圖像來(lái)估計(jì)相機(jī)運(yùn)動(dòng)。

我們習(xí)慣從圖像中選取比較有代表性的點(diǎn)，然后，在此基礎(chǔ)上，討論相機(jī)位姿估計(jì)問(wèn)題，以及這些點(diǎn)的定位問(wèn)題。

在經(jīng)典 SLAM 模型中，把它們稱為路標(biāo)，而在視覺(jué) SLAM 中，路標(biāo)則是指圖像特征（Features）。

特征是圖像信息的另一種數(shù)字表達(dá)形式。

特征點(diǎn)是圖像里一些特別的地方，我們可以把圖像中的角點(diǎn)、邊緣和區(qū)塊作為圖像特征的部分。

特征點(diǎn)由關(guān)鍵點(diǎn)（Key-point）和描述子（Descriptor）兩部分組成。

當(dāng)我們談?wù)?SIFT 特征時(shí)，是指 “提取 SIFT 關(guān)鍵點(diǎn)，并計(jì)算 SIFT 描述子” 兩件事情。

關(guān)鍵點(diǎn)是指該特征點(diǎn)在圖像里的位置，有些特征點(diǎn)還具有朝向、大小等信息。

描述子通常是一個(gè)向量，按照某種人為設(shè)計(jì)的方式，描述了該關(guān)鍵點(diǎn)周圍像素的信息。

描述子是按照 “外觀相似的特征應(yīng)該有相似的描述子” 的原則設(shè)計(jì)的。

因此，只要兩個(gè)特征點(diǎn)的描述子在向量空間上的距離相近，就可以認(rèn)為它們是同樣的特征點(diǎn)。

在目前的 SLAM 方案中，ORB（Oriented FAST and Rotated BRIEF）特征是非常具有代表性的實(shí)時(shí)圖像特征。

它在保持特征子具有旋轉(zhuǎn)，尺度不變性的同時(shí)，還會(huì)使整個(gè)圖像特征提取的環(huán)節(jié)大大加速，對(duì)于實(shí)時(shí)性要求很高的 SLAM 來(lái)說(shuō)是一個(gè)很好的選擇。

因此，我們以 ORB 特征為代表，介紹提取特征的過(guò)程。

02

ORB 特征

ORB 特征亦由關(guān)鍵點(diǎn)和描述子兩部分組成。

它的關(guān)鍵點(diǎn)稱為 “Oriented FAST”，是一種改進(jìn)的FAST 角點(diǎn)；它的描述子稱為 BRIEF。

因此，提取 ORB 特征分為兩個(gè)步驟：

1. FAST 角點(diǎn)提取：找出圖像中的 “角點(diǎn)”。相較于原版的 FAST，ORB 中計(jì)算了特征點(diǎn)的主方向，為后續(xù)的 BRIEF 描述子增加了旋轉(zhuǎn)不變特性。

2. BRIEF 描述子：對(duì)前一步提取出特征點(diǎn)的周圍圖像區(qū)域進(jìn)行描述。

下面我們分別介紹FAST 和BRIEF。

FAST 關(guān)鍵點(diǎn)

FAST 是一種角點(diǎn)，主要檢測(cè)局部像素灰度變化明顯的地方，以速度快著稱。

它的思想是：如果一個(gè)像素與它鄰域的像素差別較大（過(guò)亮或過(guò)暗），那它更可能是角點(diǎn)。

相比于其他角點(diǎn)檢測(cè)算法，F(xiàn)AST 只需比較像素亮度的大小，十分快捷。

但它也有一些問(wèn)題。

首先，F(xiàn)AST 特征點(diǎn)數(shù)量很大且不確定。

其次，F(xiàn)AST 角點(diǎn)不具有方向信息。

所以，在 ORB 中，我們對(duì)原始的 FAST 算法進(jìn)行了改進(jìn)。

我們指定最終要提取的角點(diǎn)數(shù)量 N，對(duì)原始 FAST 角點(diǎn)分別計(jì)算 Harris 響應(yīng)值，然后選取前 N 個(gè)具有最大響應(yīng)值的角點(diǎn)，作為最終的角點(diǎn)集合。

同時(shí)，針對(duì) FAST 角點(diǎn)不具有方向性和尺度的弱點(diǎn)，ORB 添加了尺度和旋轉(zhuǎn)的描述。

我們把改進(jìn)后的 FAST 稱為 Oriented FAST。

BRIEF 描述子

在提取 Oriented FAST 關(guān)鍵點(diǎn)后，我們對(duì)每個(gè)點(diǎn)計(jì)算其描述子。

ORB 使用的是改進(jìn)的 BRIEF 特征描述。

BRIEF 是一種二進(jìn)制描述子，它的描述向量由許多個(gè) 0 和 1 組成，這里的 0 和 1 編碼了關(guān)鍵點(diǎn)附近兩個(gè)像素（比如說(shuō) p 和 q）的大小關(guān)系：如果 p 比 q 大，則取 1，反之就取 0。

BRIEF 使用了隨機(jī)選點(diǎn)的比較，速度非常快，而且由于使用了二進(jìn)制表達(dá)，存儲(chǔ)起來(lái)也十分方便，適用于實(shí)時(shí)的圖像匹配。

原始的 BRIEF 描述子不具有旋轉(zhuǎn)不變性，因此在圖像發(fā)生旋轉(zhuǎn)時(shí)容易丟失。

而 ORB 在 FAST 特征點(diǎn)提取階段計(jì)算了關(guān)鍵點(diǎn)的方向，所以可以利用方向信息，計(jì)算了旋轉(zhuǎn)之后的 “Steer BRIEF” 特征，使 ORB 的描述子具有較好的旋轉(zhuǎn)不變性。

由于考慮到了旋轉(zhuǎn)和縮放，ORB 在平移、旋轉(zhuǎn)、縮放的變換下仍有良好的表現(xiàn)。

同時(shí)，F(xiàn)AST 和 BRIEF 的組合也非常的高效，使得 ORB 特征在實(shí)時(shí) SLAM 中非常受歡迎。

03

特征匹配

特征匹配是視覺(jué) SLAM 中極為關(guān)鍵的一步，寬泛地說(shuō)，特征匹配解決了 SLAM 中的數(shù)據(jù)關(guān)聯(lián)問(wèn)題（data association），即確定當(dāng)前看到的路標(biāo)與之前看到的路標(biāo)之間的對(duì)應(yīng)關(guān)系。

通過(guò)對(duì)圖像與圖像，或者圖像與地圖之間的描述子進(jìn)行準(zhǔn)確的匹配，可以為后續(xù)的姿態(tài)估計(jì)，優(yōu)化等操作減輕大量負(fù)擔(dān)。

然而，由于圖像特征的局部特性，誤匹配的情況廣泛存在，且長(zhǎng)期以來(lái)沒(méi)有得到有效解決，目前已經(jīng)成為視覺(jué) SLAM 中制約性能提升的一大瓶頸。

部分原因是因?yàn)閳?chǎng)景中經(jīng)常存在大量的重復(fù)紋理，使得特征描述非常相似。

在這種情況下，僅利用局部特征解決誤匹配是非常困難的。

不過(guò)，現(xiàn)在我們先來(lái)看正確匹配的情況。

考慮兩個(gè)時(shí)刻的圖像。如果在圖像 It 中提取到特征點(diǎn) xmt，m = 1，2，……，M，在圖像 It+1 中提取到特征點(diǎn) xnt+1，n = 1，2，……，N，如何尋找這兩個(gè)集合元素的對(duì)應(yīng)關(guān)系呢？

最簡(jiǎn)單的特征匹配方法就是暴力匹配，即對(duì)每一個(gè)特征點(diǎn) xmt，與所有的 xnt+1測(cè)量描述子的距離，然后排序，取最近的一個(gè)作為匹配點(diǎn)。

描述子距離表示了兩個(gè)特征之間的相似程度，不過(guò)在實(shí)際運(yùn)用中還可以取不同的距離度量范數(shù)。

對(duì)于浮點(diǎn)類型的描述子，使用歐氏距離進(jìn)行度量即可。

而對(duì)于二進(jìn)制的描述子（比如 BRIEF 這樣的），我們往往使用漢明距離做為度量——兩個(gè)二進(jìn)制串之間的漢明距離，指的是它們不同位數(shù)的個(gè)數(shù)。

然而，當(dāng)特征點(diǎn)數(shù)量很大時(shí)，暴力匹配法的運(yùn)算量將變得很大，特別是當(dāng)我們想要匹配一個(gè)幀和一張地圖的時(shí)候。

這不符合我們?cè)?SLAM 中的實(shí)時(shí)性需求。

此時(shí)快速近似最近鄰算法更加適合于匹配點(diǎn)數(shù)量極多的情況。

審核編輯：黃飛