SIFT（Scale-invariant feature transform）尺度不變特徵變換。這是一種傳統的圖像特徵提取算法，由David G. Lowe於1999年發表，在修改完善後，於2004年發表於IJCV。

論文名稱：Distinctive Image Features from Scale-Invariant Keypoints。

SIFT算法是一種基於局部興趣點的算法，正如其名稱那樣，SIFT對於「圖像的尺度與圖像的旋轉不敏感」，而且算法對於光照、噪聲等影響也具有較好的魯棒性。

SIFT算法專利於2000年申請，經過20年，已於2020年3月到期。opencv中已經重新集成了這種算法。

最近兩年一直在搞深度學習，對於本科時候看的SIFT算法已經忘得差不多了，最近重新學習梳理一下這個經典的圖像特徵提取算法。

SIFT算法主要分為四個步驟：

「尺度空間極值檢測（Scale-space extrema detection）」：通過使用「高斯差分函數」來搜索所有尺度上的圖像位置，識別出其中對於尺度和方向不變的潛在興趣點。
「關鍵點定位（Keypoint localizatio）」：在每個候選位置上，利用一個擬合精細的模型確定位置和尺度，關鍵點的選擇依賴於它們的穩定程度。
「方向匹配（Orientation assignment，為每個關鍵點賦予方向）」：基於局部圖像的梯度方向，為每個關鍵點位置分配一個或多個方向，後續所有對圖像數據的操作都是基於相對關鍵點的方向、尺度和位置進行變換，從而獲得了方向於尺度的不變性。
「關鍵點描述符（Keypoint descriptor）」：在每個關鍵點領域內，以選定的尺度計算局部圖像梯度，這些梯度被變換成一種表示，這種表示允許比較大的局部形狀的變形和光照變化。

接下來分別介紹這四個步驟。

1. 尺度空間極值檢測（Scale-space extrema detection）

利用高斯核構建高斯金字塔，每個尺度層包含一組尺度的圖像。這裡不同組的特徵金字塔的獲取採用隔點取樣獲得。

在每個組內（octave）兩兩做差，構建高斯差分金字塔。

在高斯差分金字塔中，每個3x3x3的立方體，比較中心點與其他的26個點的大小，如果中心點最大或者最小，那麼這個中心點就是極值點。

s表示我們要在高斯差分金字塔中求得的特徵層的數目，那麼需要s+2層的高斯差分金字塔，需要s+3層的高斯金字塔。因此每組的octave中需要s+3層圖像。

2. 關鍵點定位（Keypoint localizatio）

上邊的步驟所檢測到極值點是「離散空間的極值點」，這些極值點並不是十分準確，我們需要來精確確定關鍵點的位置和尺度，同時去除低對比度的關鍵點和不穩定的邊緣點(因為DoG算子會產生較強的邊緣響應)，從而增強穩定性。

離散空間的極值點並不是真正的極值點，正如下圖所示，利用離散空間的極值點的插值可以得到「連續空間的極值點」。

因此，這裡對於圖像極值點進行二階泰勒展開近似：

求導，讓其為0，求得連續空間的極值點：

將極值點代入上述泰勒近似公式，得到在極值點位置的值：

由此，即可得到真正的連續空間的極值點。

然後去除低對比度以及邊緣效應的極值點（這部分的細節可以看原始論文），就得到最終需要保留的所有極值點。

邊緣效應的去除，採用hassian陣的特徵值，hassian陣實際為二階偏導數。在高斯差分圖像中，如果其邊緣特徵點，那麼其垂直於邊緣的方向，值變化較大（對應於hassian陣中較大的特徵值），沿邊緣方向，值變化較小（對應於hassian陣中較小的特徵值）。因此採用hassian陣中的較大特徵值與較小特徵值的比例超過閾值的特徵點去除，就去除了邊緣效應。（文章中採用矩陣的跡與行列式近似計算）

文中取r=10.

a圖是原圖像，b圖是直接進行關鍵點檢測得到的效果圖，c圖是捨棄對比度較小的極值點得到的效果圖。d圖是去除邊緣效應極值點後得到的效果圖。

3. 方向匹配（Orientation assignment，為每個關鍵點賦予方向）

對於每個極值點，統計以該特徵點所在的⾼斯圖像的尺度的1.5倍為半徑的圓內的所有的像素的梯度方向及其梯度幅值。得到下圖所示的直方圖（論文中以每10度為一個範圍，也就是有36個方向）。直方圖峰值所對應的方向為主方向，任何大於峰值80%的方向為特徵點的輔方向。

4. 關鍵點描述符（Keypoint descriptor）

前邊三個步驟，我們找到了所有的特徵點的位置，並且每個特徵點都有方向，尺度信息。接下來就是計算在局部區域內這些特徵點的描述符。

如下圖，左邊是圖像梯度圖像，右邊是關鍵點描述符。描述符與特徵點所在的尺度圖像有關，因此在某個高斯尺度圖像上，以特徵點為圓心，將其附近鄰域劃分為4x4個子區域，每個區域統計特徵點的方向以及尺度，每個子區域獲得8個方向的梯度信息，因此每個特徵點共有4x4x8=128維的特徵。

❝

原文首發於「小哲AI」公眾號，公眾號主要分享人工智慧前沿算法解讀，AI項目代碼解析，以及編程、網際網路求職等技術資料文章，偶爾也會分享個人讀書筆記、工作學習心得，歡迎關注，一起學習。

❞