一起自学SLAM算法：3.4 图像特征点提取
??連載文章，長期更新，歡迎關注：
寫在前面
第1章-ROS入門必備知識
第2章-C++編程范式
第3章-OpenCV圖像處理
? ? ? ??3.1 認識圖像數據
????????3.2 圖像濾波
????????3.3 圖像變換
????????3.4 圖像特征點提取
第4章-機器人傳感器
第5章-機器人主機
第6章-機器人底盤
第7章-SLAM中的數學基礎
第8章-激光SLAM系統
第9章-視覺SLAM系統
第10章-其他SLAM系統
第11章-自主導航中的數學基礎
第12章-典型自主導航系統
第13章-機器人SLAM導航綜合實戰
特征點提取算法能幫助計算機獲取圖像的區域特征信息，并應用于圖像識別、圖像匹配、三維重建、物體跟蹤等領域。在實際工程中，具有很高的應用價值。在圖像領域，特征點（feature points）也常常被稱為關鍵點（key points）或興趣點（interest points）。特征點的提取有多種算法，可以從圖像紋理信息來提取，也可以通過圖像區域灰度統計信息來，或者通過頻譜變化、小波變換等變換后在變換空間進行提取。本節將對最常用的SIFT（scale invariant?feature?transform，尺度不變特征變換）特征點、SURF（Speeded Up Robust Features，加速穩健特征）特征點和ORB（Oriented FAST and Rotated BRIEF，快速特征點提取和描述）特征點進行分析和講解，并對比其性能表現。
SIFT在性能方面非常突出，在業界有很高的名氣；SURF是對SIFT的改進，在提取速度方面做了優化；ORB是用于取代SIFT和SURF的簡潔提取算法，提取速度比SIFT和SURF快很多。后續視覺SLAM中的ORB_SLAM框架就是基于ORB特征點的，在實時性方面表現非常出色。因此學好本節的內容，將極大降低后續視覺SLAM章節的學習難度。
本節的重點放在SIFT、SURF和ORB三種特征點提取的原理講解中，如果對OpenCV中具體實現程序感興趣，可以閱讀OpenCV3中相應的源代碼，源代碼的路徑如下。
- SIFT源碼路徑：opencv_contrib/modules/xfeatures2d/src/sift.cpp。
- SURF源碼路徑：opencv_contrib/modules/xfeatures2d/src/surf.cpp。
- ORB源碼路徑：opencv/modules/features2d/src/orb.cpp。
3.4.1 SIFT特征點
SIFT是對旋轉、尺度和亮度保持不變，對仿射變換、噪聲等也有比較好的穩定性的圖像局部特征。那什么是旋轉尺度不變性呢？簡單點說就是同一個物體，用相機在不同的角度和距離拍出來的圖片，圖片中物體的特征應該是一樣的，不因圖片的大小和旋轉而改變。
SIFT特征提取過程，如圖3-7所示。由于所有操作都在灰度圖上進行，因此輸入原始圖需要先經過灰度轉換。然后構建高斯金字塔（Gaussian Pyramids），用于表示圖像的尺度空間。將高斯金字塔每組（Octave）中相鄰兩圖層（Layer）求差值得到高斯差分金字塔（Difference of Gaussian Pyramids，DoG金字塔），用于尺度空間的極值點檢測。接著通過極值點檢測、特征點定位和特征點篩選操作，提取出特征點在尺度空間的位置。之后回到高斯金字塔，求取該尺度空間位置上的特征點主方向以及鄰域方向。最后利用特征點的方向信息可以生產特征的描述向量，整個提取過程最后輸出所有特征點的描述向量。特征點包含尺度、位置和特征描述信息，利用這些信息就可以做圖像識別、圖像匹配等應用了。
?圖3-7 ?SIFT特征提取過程
1.尺度空間
將單張圖像利用尺度參數進行處理，得到多尺度空間的圖像序列。尺度空間中的圖像模糊度逐漸變大，這樣能夠模擬人眼由近及遠觀察目標時在視網膜上成像的過程。從多尺度空間的圖像序列提取特征，能得到具有尺度不變性的特征。下面依次對圖像金字塔、高斯金字塔和高斯差分金字塔的構建過程進行解析。
（1）圖像金字塔
正如其名，圖像金字塔由一張一張逐漸縮小的圖片組合而成，形狀就像一個金字塔。金字塔最底層放置的是原始圖像，然后上一層圖像由下一層圖像經過1/2倍降采樣得到，其實就是隔點采樣，這樣圖像尺寸會逐漸縮小，如圖3-8所示。
圖3-8 ?圖像金字塔
?金字塔中含有圖像的數量n可用下面的式（3-20）計算。其中rows和cols分別為原始圖像的行和列數，t為金字塔頂層圖像期望尺寸的對數值。也就是說已知塔頂圖像的尺寸，就可以求得塔包含圖像的數量。
（2）高斯金字塔
將尺度連續性考慮進來的話，還需要在圖像金字塔的基礎上引入高斯濾波，這就是高斯金字塔。在SIFT特征提取過程中，高斯金字塔的構建過程如圖3-9所示。
?圖3-9 ?高斯金字塔
高斯金字塔中的圖像有組（Octave）和層（Layer）的概念，通過組索引o和層索引s可以對塔中的每個圖像建立索引。SIFT算法的提出者Lowe建議將原始灰度圖擴大到2倍大小，即通過2倍升采樣和高斯濾波，將擴大后的圖作為塔最底層的圖開始構建，這樣做可以保留原圖信息，增加特征點數量。同一組內的圖層具有相同的大小，后一個圖層由前一個圖層經過尺度因子為的高斯濾波得到，也就是說同一組內遞增的圖層將越來越模糊。尺度因子的計算如式3-21所示，o和s分別為組索引和層索引，為初始尺度因子，在程序中為一個常數值，S是組中圖層的總數量。
?
在不同組中，后一組的第1個圖層由前一組的倒數第3個圖層直接經過1/2倍降采樣得到，取倒數第3個圖層是為了保持下一步高斯差分金字塔的尺度空間連續性。按照這個步驟，不斷構建出新的組，最終就能得到一個完整的高斯金字塔。關于金字塔的組數O、層數S等參數，請參考具體程序，這里的講解只是舉例說明。
（3）高斯差分金字塔
構建高斯差分金字塔，通過檢測高斯差分金字塔的極值點，能夠提取原圖像中的角點特征。要講解清楚其中的原理，需要先從拉普拉斯算子開始說起。拉普拉斯算子是n維歐式空間的一個二階微分算子，定義為求梯度的散度，定義如式（3-22）所示。
利用拉普拉斯算子對函數求二階導，能求出函數一階導的極值點，也就是最大梯度點。這里先以最簡單的1維空間為例，展示利用二階導求出函數局部最大梯度點的過程，如圖3-10所示。
?圖3-10 ?二階導求最大梯度點
?再來討論2維空間的情況，也就是圖像中，局部像素大梯度點是變化最明顯的點，這樣的點可以作為特征點。但是直接的拉普拉斯操作，非常容易受圖像噪聲點的干擾，于是就引入了抗干擾的高斯濾波，先進行高斯濾波，再進行拉普拉斯操作，這就是高斯拉普拉斯運算（Laplace of Gaussian,LoG）。雖然對圖像做高斯拉普拉斯運算，能實現角點檢測，但是運算復雜。理論證明，高斯差分函數與尺度歸一化高斯拉普拉斯函數非常近似，因此可以用高斯差分運算替代高斯拉普拉斯運算來做圖像角點的檢測。關于近似的理論推導，如式3-23、式3-24和式3-25所示。
?弄明白了高斯差分運算求圖像角點，也就是局部最大梯度點。接下來就講一下如何構建高斯差分金字塔，其實就是將高斯金字塔同組內的相鄰圖層做差就行了，如圖3-11所示。
?圖3-11 ?高斯差分金字塔
2.特征點位置提取
特征點位置提取在高斯差分金字塔中完成，分為極值點檢測、特征點定位和特征點篩選這些步驟。
（1）極值點檢測
在高斯差分金字塔的同一組內，圖層上的極點由該圖層像素的8個領域點與上下相鄰圖層的9×2個領域點比較大小得到。也就是說要判斷一個點是否為極值點，需要將其與周圍的26個點比較大小，如圖3-12所示。通過這里可以看到，要檢測全尺度下的極值點，高斯差分金字塔的每個組內要多出2個圖層，而高斯差分金字塔是由高斯金字塔做差得到的，那么高斯金字塔的每個組內要多出3個圖層，這就是前面講到的為什么要從倒數第3個圖層來生成下一個組的原因，即為了保持高斯差分金字塔中尺度的連續性。
?圖3-12 ?極值點檢測
（2）特征點定位
通過上面方法得到的是離散空間的極值點，但是離散空間的極值點并不是真正的極值點。如圖3-13所示，曲線的離散采樣點A、B、C、D……中，A和B分別是極大值和極小值點，但并不是曲線上真正的極值點。因此，需要利用曲線擬合的方法得到連續空間的曲線，并得到真正的極值點。這個操作在圖像中是一個亞像素定位的過程，擬合過程為在極值點附近做泰勒級數展開，找出特征點更精確的位置。
?圖3-13 ?離散空間極值點
（3）特征點篩選
高斯差分算子容易產生較強的邊緣響應，因此特征點還需要經過篩選，去除掉邊緣點的影響。首先獲取特征點位置處的Hessian矩陣H，計算如式（3-26）所示。
?矩陣H的特征值a和b表示x和y方向的梯度。邊緣點的梯度肯定是一個方向大一個方向小。因此可以設置一個閾值T，用于剔除邊緣點，假設a>b，則滿足a/b?> T的點將被判斷為邊緣點而被剔除。
3.特征點方向提取
特征點方向提取在高斯金字塔中完成，分為特征點主方向、特征點鄰域方向和特征描述子這些步驟。
（1）特征點主方向
經過在高斯差分金字塔中的一系列操作，提取出了特征點在尺度空間的位置信息。接下來就可以去高斯金字塔中提取該尺度空間位置處點的方向信息。首先需要提取特征點的主方向，提取過程如圖3-14所示。
?圖3-14 ?特征點主方向
找到高斯金字塔中相應尺度空間的圖層，在特征點位置的鄰域窗口計算像素的梯度，梯度的幅值m和方向θ通過下面的式（3-27）和式（3-28）求得，其中f(x,y)為鄰域窗口的像素值。
計算好梯度的幅值和方向后，將方向每10度劃分一個范圍，對方向進行統計，方向對應的幅度需要經過高斯系數加權后進行累計，也就是說離特征點中心越遠的梯度點其幅值累計時需被乘以一個越小的加權系數。對所有方向統計完成后，就得到方向的統計直方圖，直方圖的橫軸是方向角度，一共有36個刻度（10度，20度，...，360度），直方圖的縱軸是對應方向幅值加權累計的結果。以直方圖峰值的方向作為主方向，并保留大于80%峰值的方向作為輔方向，以增強魯棒性。
（2）特征點鄰域方向
要對特征點做一個好的表示，還需要用到特征點鄰域上的方向。在計算鄰域上的方向分布前，需要先將鄰域圖像按主方向進行旋轉，這樣鄰域方向就是統一以主方向為基準來表示，以實現特征的旋轉不變性，如圖3-15所示。
?圖3-15 ?按主方向旋轉圖像
在得到的旋轉不變性鄰域上，進行4×4的區域劃分，得到16個區域。對每個區域求方向的統計直方圖，這里的直方圖將方向每45度劃分一個范圍，也就是8個方向。方向對應的幅度同樣需要經過高斯系數加權后進行累計，這里的高斯系數是以各自區域中心來計算的。
?圖3-16 ?特征點鄰域方向
（3）特征描述子
從上面特征點鄰域方向一共有得到了4×4×8=128個量，也就是說一個特征點可以用這個樣的128維向量來描述，即描述向量。為了去除光照變化的影響，需要對描述向量做歸一化。同時為了消除成像時飽和度變化的影響，需要對歸一化后的描述向量做閾值化，設置一個閾值，將大于閾值的具有較大幅值的方向去除，然后再做一次歸一化。最后按照特征點的尺度對描述向量進行排序。SIFT特征提取完成后，能得到一系列特征點。每個特征點包含尺度、位置和描述信息，有了這些信息就可以做圖像識別、匹配之類的應用了。如圖3-17所示，是從圖片中提取SIFT特征的效果。
?圖3-17 ?提取SIFT特征示例
3.4.2 SURF特征點
SIFT算法最大的缺點是在一般設備上達不到實時性的要求，SURF是對SIFT的改進，在提取速度方面做了優化。SURF特征提取過程跟SIFT特征提取過程基本一樣，只是在一些步驟上做了改進，以提高運行實時性。下面針對改進的地方，展開講解。
1.尺度空間
基于高斯拉普拉斯算子檢測圖像角點的良好特性，在SIFT特征提取中，先創建高斯金字塔，然后再利用高斯差分運算DoG能近似高斯拉普拉斯運算LoG的性質，對高斯金字塔中的組內圖層做差得到高斯斯差金字塔。也就是說SIFT中建立尺度空間的步驟包括創建高斯金字塔和創建高斯差分金字塔兩步，而在創建高斯金字塔過程中，要利用不同尺度因子的高斯濾波器對圖像進行濾波來得到多尺度空間。高斯濾波運算是很耗時的，所以這一步需要進行優化。
基于高斯拉普拉斯算子檢測圖像角點的良好特性，在SURF特征提取過程中，使用了另一種近似高斯拉普拉斯運算的方式，即基于Hessian矩陣的盒式濾波運算，能大幅降低運算耗時。下面就解析一下整個過程，高斯拉普拉斯運算的第一步是對圖像I(x,y)進行高斯濾波，如式（3-29）所示。
然后對高斯濾波后的圖像中的每個像素進行拉普拉斯運算，拉普拉斯運算結果用Hessian矩陣表示，如式（3-30）所示。矩陣中的元素分別是對x方向求二階導、對x和y方向依次求偏導、對x和y方向依次求偏導和對y方向求二階導這4個操作。
不難發現上面Hessian矩陣中4個元素的操作是關鍵，這4個操作分別對應在x方向求二階導、在x和y方向依次求偏導、在x和y方向依次求偏導和在y方向求二階導高斯濾波窗。這種濾波窗有3種形狀，分別是x方向二階導形、y方向二階導形和x、y混合導形，如圖3-18的左半部分所示。窗口中的不同亮度表不同的加權系數，可以看到這些窗口中的系數還是非常多，計算起來很耗時。解決辦法是利用盒式濾波來近似這些窗，其實就是將一定區域的不同加權系數統一用某個固定值表示，如圖3-18的右半部分所示，積分圖像具有的性質是這樣近似的理論依據。
?圖3-18 ?盒式濾波器
在利用上面盒式濾波器求出圖像中每個像素的Hessian矩陣后，接著求Hessian矩陣的決定值，如公式3-31所示。
?考慮到利用盒式濾波近似，可能帶來的誤差，這里加一個0.9的補償系數，如公式3-32所示。
這樣圖像中每個Hessian矩陣的決定值就可以用于后續的極值點檢測了。
與SIFT尺度空間不同的是，在SURF中金字塔的不同組的圖層大小是一樣的。通過在不同組上使用盒式濾波器窗口尺寸逐漸增大，同一組內的不同圖層上使用相同窗口尺寸盒濾波器，但是窗口中的尺度因子取值逐漸增大，這樣的方式來實現多尺度空間。
2.特征點位置提取
SIFT特征點位置是在DoG空間進行的，而SURF特征點位置是在Hessian矩陣的決定值中進行的。除了這一點區別外，極值點檢測、特征點定位和特征點篩選的方式是一樣的，因此就不贅述了。
3.特征點方向提取
在SIFT中，特征點主方向是通過求特征點鄰域上梯度的方向統計直方圖，取直方圖峰值的方向。在SURF中，不求特征點鄰域上梯度的方向統計直方圖，而是統計特征點鄰域上的Haar小波特征。統計60度扇形區域內所有x和y方向小波特征，這些特征通過高斯加權系數進行累計，即遠離中心的小波特征乘上的加權系數小。然后以15度間隔旋轉這個60度扇形區域，將整個圓遍歷，統計最大值的那個扇形方向就是特征點主方向，如圖3-19所示。
?圖3-19 ?特征點主方向
?在SIFT中，先將特征點鄰域按主方向旋轉后，計算該鄰域各個區塊的梯度方向直方圖，來描述特征點，描述向量是4×4×8=128維。在SURF中，不旋轉領域圖像，而是按主方向旋轉鄰域窗。以旋轉之后窗的x和y方向作為Haar小波特征計算的方向，窗同樣被劃分成4×4的區塊，每個區塊含有5×5個像素，統計每個區塊中5×5個像素的x方向小波特征之和、x方向小波特征絕對值之和、y方向小波特征之和、y方向小波特征絕對值之和，如圖3-20所示。
?圖3-20 特征點鄰域方向
把這4個統計值作為該區塊的描述，那么描述向量是4×4×4=64維。也就是說SURF特征描述向量維度只有SIFT特征描述向量維度的一半。如圖3-21所示，是從圖片中提取SURF特征的效果。
?圖3-21 ?提取SURF特征示例
3.4.3 ORB特征點
學習完SIFT和SURF特征后，最后來學習ORB特征。ORB特征的最大優點是提取具有很好的實時性，按業界的說法，ORB提取速度比SURF快10倍，比SIFT快100倍。ORB提取速度能這么快，得益于其基于的FAST（Features from Accelerated Segments Test）特征和BRIEF（Binary Robust Independent Elementary Features）描述。
ORB特征提取過程，如圖3-22所示。由于所有操作都在灰度圖上進行，因此輸入原始圖需要先經過灰度轉換。然后構建圖像金字塔，用于表示圖像的尺度空間。從這里可以看到ORB的尺度空間構建方法比SIFT和SURF簡單多了，因為圖像僅僅進行逐個的降采樣就行了。并且構建出來的圖像金字塔中各張圖直接拼接成一張大圖，用這張大圖就能直接表示尺度空間，這樣做也能大大加快速度，后面特征提取與描述都直接在這張大圖上進行，以使特征具有尺度不變性。這里提取的是FAST特征，并且對FAST特征做了改進，增加了FAST特征點的旋轉方向信息提取，改進后稱oFAST。最后在特征點鄰域內，計算BRIEF描述，并且對BRIEF描述也做了改進，借助特征點的旋轉方向信息來計算BRIEF描述，改進后稱rBRIEF。這里對FAST特征和BRIEF描述做出的改進，都是為了使特征點具有旋轉不變性。計算完所有的oFAST和rBRIEF，就能得到所有特征點的描述向量，提取過程完成。
?圖3-22 ?ORB特征提取過程
1.尺度空間
相比于SIFT中要構建高斯金字塔和高斯差分金字塔來表示尺度空間，ORB中僅僅對圖像進行逐個的降采樣就行了，將構建出的圖像金字塔中的各種圖片拼接在一起成為一張大圖，并記錄好大圖中每個尺度的起始和結束位置，用這張大圖就能直接表示尺度空間，如圖3-23所示，這樣做能大大加快速度，后面特征提取與描述都直接在這張大圖上進行，以使特征具有尺度不變性。
?圖3-23 ?圖像金字塔的拼接表示
2.特征點提取
這里提取的是FAST特征，并且對FAST特征做了改進，增加了FAST特征點的旋轉方向信息提取，改進后稱oFAST。先說FAST特征的提取過程，對給定的像素點p，判斷p點鄰域圓周上的16個像素點中是否有連續N個點的灰度值與p點灰度值之差超過某一閾值，這個閾值一般設為p點灰度值的20%，滿足這個判斷的點就是FAST特征點。根據N的具體取值，FAST有幾種不同的形態，常用的有FAST-12、FAST-11和FAST-9。由于這樣提取的過程并沒有包含特征點的旋轉方向信息，為了使特征點具有旋轉不變性，還要計算特征點的方向。只需要計算出鄰域的灰度質心m，鄰域中心p到灰度質心m的方向，就是特征點的方向，這樣就得到了oFAST特征。oFAST特征提取過程，如圖3-24所示。
?圖3-24 ?oFAST特征提取過程
3.特征點描述
通過上面的方法確定出oFAST特征點后，就可以在特征點鄰域內，計算BRIEF描述，并且對BRIEF描述也做了改進，借助特征點的旋轉方向信息來計算BRIEF描述，改進后稱rBRIEF。BRIEF描述計算過程，首先對圖像金字塔拼接的大圖做高斯濾波，以去除掉一些高頻噪聲點的干擾；然后在特征點的鄰域內，隨機挑選兩個點作為一個點對，如果點對中的第1個點亮度大于第2個點，則為這個點對分配特征值1，反之分配特征值0；按照高斯分布依次挑選256個這樣的點對，最終可以得到一個256維的向量，并且向量中的每個元素只能取0或1兩個值，比如V=[101001110101010111010...]這樣的形式。為了使特征點描述具有旋轉不變性，還要將特征點的方向考慮進來。其實很簡單，只需要將BRIEF中按照高斯分布依次挑選的256個點對按特征點方向旋轉，得到新的256個點對，對新的點對計算分配特征值就行了，這樣就得到了rBRIEF描述。到這里，ORB特征就提取出來了。如圖3-25所示，是從圖片中提取ORB特征的效果。
?圖3-25 ?提取ORB特征示例
源碼倉庫
-
Github下載：github.com/xiihoo/Books_Robot_SLAM_Navigation
-
Gitee下載（國內訪問速度快）：gitee.com/xiihoo-robot/Books_Robot_SLAM_Navigation
參考文獻
【1】 張虎，機器人SLAM導航核心技術與實戰[M]. 機械工業出版社，2022.
總結
以上是生活随笔為你收集整理的一起自学SLAM算法：3.4 图像特征点提取的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： python canny 保留指定区域的
- 下一篇： [USACO 2012 January