大綱

• 引言
• 一、高斯金字塔
• 二、高斯差分金字塔
• 三、特征點處理
• • 1.閾值化
  • 2.非極大值抑制
  • 3. 二階泰勒修正
  • 4.低對比度去除
  • 5.邊緣效應去除
• 四、特征點描述子
• • 1. 確定特征點區域方向
  • 2. 特征點區域描述子
• 總結
• 參考：

引言

?SIFT算法是為了解決圖片的匹配問題，想要從圖像中提取一種對圖像的大小和旋轉變化保持魯棒的特征，從而實現匹配。這一算法的靈感也十分的直觀：人眼觀測兩張圖片是否匹配時會注意到其中的典型區域（特征點部分），如果我們能夠實現這一特征點區域提取過程，再對所提取到的區域進行描述就可以實現特征匹配了。于是問題就演變成了以下幾個子問題：

應該選取什么樣的點作為特征點呢？：人眼對圖像中的高頻區域更加的敏感，由此我們應該選擇變化劇烈的邊緣或者角點進行檢測，這里我們選擇檢測角點。（這里的intuition不是很明白，但感覺來說可能是我們提取的是特征點進行匹配，而邊緣往往是由多個點組成。）

怎樣使得選取的特征點有尺度不變性呢？：使用高斯金字塔獲取不同尺寸下的圖像變體，由這些變體獲得尺度不變特征。

怎樣使得選取的特征點有縮放不變性呢？：使用高斯金字塔獲取不同尺寸下的圖像變體，每個變體里都提取特征點再縮放回原大小以獲得圖像不同尺寸下的特征點。

怎樣使得選取的特征點有旋轉不變性呢？：后續采取將特征點區域旋轉到主方向的設定以獲得旋轉不變性。

如何描述特征點區域呢？： 使用特征點區域內每個方向的梯度賦值，類似HOG算子。

以上幾個問題在SIFT算法里都用了很有意思的trick，后續會一一介紹。

一、高斯金字塔

?引入高斯金字塔的目的在引言中已經介紹過了–解決圖片縮放及尺度變化下特征提取的問題，高斯金字塔的Intuition有兩個：1. 人看物體時近大遠小，可以對圖片下采樣實現（金字塔->組）；2. 人看物體時近處清晰，遠處模糊，可以對圖像高斯平滑實現（高斯->層）；具體的推導可以參見我的另一篇博客：
Opencv學習筆記（六）圖像金字塔
在SIFT里，高斯金字塔的層數和組數有著如下設定：

組數：$O=[lo{g}_{2}min(M,N)]?3$

層數：$S=n+3$

?組數的設定是來自于提出SIFT算法的原始論文給出的經驗值，理論上來說知要$O\le [lo{g}_{2}min(M,N)]$即可，層數的設定則是有著理論依據的，這里的$n$是我們想要提取特征點的圖片層數，由于提取出高斯金字塔后需要計算層間差分以獲得高斯差分金字塔(DOG, Difference of Gausssian)，高斯金字塔層數需要比DOG層數多1，而計算特征值時要求在尺度層面，即上下相鄰層間計算，則DOG層數要比特征層數多2，則要求$S=n+3$。

附：在SIFT中對于高斯金字塔有幾個需要補充的知識點。

SIFT算法中的S指的是"scale"即尺度的概念，這一概念有別于傳統的圖像尺寸，而是一種連續變化的參數，在高斯金字塔里的$\sigma$就是這樣一個尺度空間的參數，更特殊的，高斯核是唯一可以產生連續多尺度變化的線性核，這就是為什么我們用高斯金字塔，這一部分內容涉及到尺度空間的概念，可以自行了解。

圖像金子塔一文中提到了兩個基礎參數，層間尺度變化系數$k$和初始尺度${\sigma }_0$，在原始算法中規定$k=2^{o+\frac{r}{n}}，r=0,1...,n+2$，由于每組的起始層是由前一組倒數第三層降采樣得到，實際上保證了每組開始的尺度為${\sigma }_0,2{\sigma }_0,3{\sigma }_0...$。此外我們提到${\sigma }_0=1.6$，而實際拍攝圖片時相機已經原始景物進行了一次尺度變換，此變換的系數原文設定經驗值為${\sigma }^{\prime }=0.5$，由此我們得到${\sigma }_0=\sqrt{1.6^2?{\sigma }^{\prime 2}}=1.52$。這一式子的來歷為：高斯濾波體現為高斯核與原圖進行卷積$f(x)?G^{\prime }(x)$，兩次高斯濾波的級聯相當于$f(x)?(G^{\prime }(x)?G(x))$，而兩個高斯卷積的結果仍為高斯卷積，且方差滿足平方和關系，可用時域卷積或者傅里葉變換證明，詳見參考文獻。

二、高斯差分金字塔

?通過高斯金字塔，我們獲取了不同尺度的圖片，接下來的問題是如何獲取高頻區域呢，一個很簡單的思路就是按照邊緣檢測的算法使用差分濾波器如拉普拉斯濾波器、sobel濾波器在圖片上滑動找到灰度值變化劇烈的區域。而經前人研究，歸一化的高斯拉普拉斯算子的極大值極小值相較于其他特征提取函數可以獲得最穩定的圖像特征，因此我們打算使用歸一化的高斯拉普拉斯算子在多尺度圖片上提取特征，但是使用這種方式提取復雜度會很高，又尺度歸一化高斯拉普拉斯算子和DOG函數有著如下關系:
$G(x,y,k\sigma )?G(x,y,\sigma )\approx (k?1){\sigma }^2{?}^{2}G$
證明如下：
忽略高斯函數系數:
$$\begin{array}{rl}& G(x,y,\sigma )=\frac{1}{{\sigma }^2}exp(?\frac{x^2+y^2}{2{\sigma }^2})\\ & \frac{?G}{?x}=?\frac{x}{{\sigma }^4}exp(?\frac{x^2+y^2}{2{\sigma }^2})\\ & \frac{{?}^{2}G}{?x^2}=\frac{?{\sigma }^2+x^2}{{\sigma }^6}exp(?\frac{x^2+y^2}{2{\sigma }^2})\\ & {?}^{2}G(x,y)=\frac{{?}^{2}G}{?x^2}+\frac{{?}^{2}G}{?y^2}\\ & =\frac{?2{\sigma }^2+x^2+y^2}{{\sigma }^6}exp(?\frac{x^2+y^2}{2{\sigma }^2})\\ & \frac{?G}{?\sigma }=\frac{?2{\sigma }^2+x^2+y^2}{{\sigma }^5}exp(?\frac{x^2+y^2}{2{\sigma }^2})\\ & ?\\ & \sigma {?}^{2}G=\frac{?G}{?\sigma }\end{array}$$
又對于差分高斯金字塔有：
$$\begin{array}{rl}& DOG=\frac{G(x,y,k\sigma )?G(x,y,\sigma )}{(k?1)\sigma }\approx \frac{?G}{?\sigma }\\ & DOG\approx (k?1){\sigma }^2{?}^{2}G\end{array}$$
由此我們不再需要在高斯金子塔上進行卷積操作，只需要計算在尺度層面$\sigma$進行層間差分得到高斯差分金字塔(DOG)，即完成了特征提取的操作。

三、特征點處理

?得到DOG后，我們理論上來說就已經獲得了特征值，但我們需要對特征值進行一些處理，就像我們在cannny邊緣檢測中使用的非極大值抑制等思路，去掉沒那么特征的特征值。

1.閾值化

?簡單的閾值化去除掉變換沒有那么劇烈的點，這些點就有可能是噪聲引起的，算是在高斯拉普拉斯之外又加了一層去噪措施。
$val=\{\begin{array}{ll}val& abs(val)>0.5\frac{T}{n}\\ 0& otherwise\end{array}$
這里的$T$為經驗值0.04，$n$為之前提過的提取特征點數目。

2.非極大值抑制

?非極大值一致的思路就和在其他算法中的一樣，我們要求選取出的特征值應該是其領域范圍內的極值，不同之處在于其他算法要求的只是圖像這一二維平面內的極值，而這里要求還要在尺度$\sigma$這一層面上也是極值，這也承接了前文DOG層數要比提取特征所用層數多2的設定。

3. 二階泰勒修正

?由于我們的圖片在$x,y,\sigma$方向上都只能取到離散值，即使通過前兩個步驟取到了一些特征點，但這些特征點都不夠精確，我們需要引入二階泰勒函數對齊進行修正，使得特征點可以出現在亞像素（亞尺度）位置。

$f(X)=f(X_0)+\frac{?f^T}{?X}\hat{X}+\frac{1}{2}\widehat{X^T}\frac{{?}^{2}f}{?X^2}\hat{X}$
上式給出了特征點$X_0$附近函數的近似值$f(x)$，其中$\hat{X}=X?X_0$，對該式求取一階導數零點，即可得函數實際極值點位置與$X_0$的距離，從而對離散特征點修正到亞尺度處。
$f^{\prime }(X)=\frac{?f^T}{?X}+\frac{?f^2}{?X^2}\hat{X}$

${\hat{X}}_{ex}=?\frac{{?}^2{f}^{?1}}{?X^2}\frac{?f}{?X}$
帶入前式可求取新的特征點的灰度值：
$f(X^{\prime })=f(X_0)+\frac{1}{2}\frac{?f^T}{?X^{\prime }}{\hat{X}}_{ex}$
需要注意的是，上式是一個不斷迭代的過程，也即根據當前特征點二階泰勒求取新的特征點這一過程會不斷重復直到滿足終止條件，如$\hat{X}$過小。另需注意當所得解超出離散極值點一定范圍時需要舍去，因為二階泰勒擬合只在其附近有效。

附：一個挺有意思的點在于這里的迭代目的和梯度下降法里的迭代并不是同一個目的，梯度下降里我們求取的是函數在某點的梯度，因為我們很難對復雜非線性的神經網絡求除其一階導數零點，即使求取到了也可能落入局部極值；而這里我們是直接求到了函數的一階零點，迭代的目的是因為函數本身是一種近似，泰勒展開只取到了第二項，需要不斷對原函數進行近似。這兩種迭代的目的并不相同。

4.低對比度去除

?目的和之間的閾值化類似，同樣是去除掉沒那么劇烈變化的特征點。要求：
$|f(x)|\ge \frac{T}{n}$

5.邊緣效應去除

?引言中提過我們想要提取的特征點為角點而非邊緣，而前述一系列措施只能保證取到灰度值變換劇烈的點，而邊緣點同樣符合這一特征，因此我們將通過以下方式去除邊緣點。

• 計算黑森矩陣$$H(x,y)=\left[\begin{array}{cc}{D}_{xx}(x,y)& D_{xy}(x,y)\\ D_{yx}(x,y)& D_{yy}(x,y)\end{array}\right]$$
• 若矩陣行列式$Det(H)<0$，舍去該特征點
• 若矩陣行列式和跡不滿足：$\frac{Tr(H)}{Det(H)}<\frac{({\gamma }_0+1{)}^2}{{\gamma }_0}$，舍去該特征點，${\gamma }_0$為有實際意義的經驗值，通常設定為10。

接下來解釋以下這幾個步驟的意義，角點和邊緣點的區別在于邊緣在圖像中表現為一條線，垂直于線的方向頻率高，沿著線的方向頻率比較低；而角點則在多（大于2）個方向方向出現強高頻分量。黑森矩陣實際上是函數的二階偏導構成的矩陣，可以反應函數的曲率變化狀況。又對于二次型矩陣有如下性質：

假定二次型矩陣$H$兩個特征值為$\alpha ,\beta$，則$Det(H)=\alpha \beta$，$Tr(H)=\alpha +\beta$;

實二次型矩陣的特征值異號時，該矩陣為不定矩陣，黑森矩陣為不定矩陣時，該臨界點為非極值點；

黑森矩陣的特征值標定了函數在相應特征向量方向上變化的快慢。

由性質1，2我們可以推導處當$Det(H)<0$時，特征點為非極值點，舍去；
由性質1，3我們可以推導出當$\frac{Tr(H)}{Det(H)}=\frac{(\alpha +\beta {)}^2}{{\alpha }^2{\beta }^2}$過小時，由兩特征特征向量的比值$\gamma$構成的式子$\frac{(\gamma +1{)}^2}{\gamma }$同樣較小，且對勾函數在$\gamma >1$時單增，我們可以根據$\frac{Tr(H)}{Det(H)}$大小判斷特征向量的相對大小，該值過小，說明函數在該點不同方向上的變化非常不均勻，類似于邊緣，舍去。

四、特征點描述子

?通過前述步驟，我們已經獲得了不同尺寸層面上的穩定特征點，接下來需要對其進行描述。

1. 確定特征點區域方向

?引言中提到為了使特征點擁有旋轉不變性，我們會將特征點區域統一旋轉到特定方向，這一方向即為特征點區域的主方向，因此我們需要先確定主方向。
計算方式為：統計在離該特征點尺度${\sigma }^{?}$最近的尺度層${\sigma }_{oct}上，$以特征點為中心$3{\sigma }^{\prime }=3?1.5{\sigma }_{oct}$范圍內的像素的梯度幅值及方向，對于范圍內的梯度幅值用$1.5{\sigma }^{?}$高斯核濾波以實現距離加權。得到一系列梯度幅值和方向對$pairs=\{amp,ang\}$后，將$360°$方向劃分為多個bins，將包含相應$ang$的$pairs$中的$amp$值累加到對應的bins上，如果$ang$在兩個bins劃分間則根據距離分配$amp$。（此處和HOG算法類似，可自行查閱）。最終可以獲得特征點區域內幅值-方向直方圖，選取其中幅值最大的方向作為主方向。

附：這里的幾個參數像是統計區域的半徑，高斯加權的方差，有著不同的設置方式，但內在思路是一致的。此外如果在主方向之外出現了幅值達到了主方向幅值80%的其他方向，我們會將其作為輔方向，后續匹配時會出現兩個位置、尺度相同但方向不同的兩個特征點區域。

2. 特征點區域描述子

?獲得了特征點區域的主方向之后，我們就可以利用該值計算出有旋轉不變性的描述子了。首先還是和前一步類似，統計該特征點所在尺度層面一定區域內的梯度幅值和方向，實施起來略有不同。

首先在特征點所處尺度層面內劃定特征區域，半徑為：
$r=\frac{3\sqrt{2}{\sigma }_{oct}(d+1)}{2}$，其中$d$為我們在一個維度上劃分的子塊數目，通常為4；

將該區域劃分為共$d?d$個子塊，每個子塊內包含多個像素點 ；

將劃定出來的區域旋轉到該區域的主方向（前一步已求出）；

在每個子塊內構筑幅值-方向直方圖，統計8個方向的梯度幅值。由此該區域可用$8?d?d$維向量表示，由此完成了特征點區域描述子的構建；
附：需要注意的是以上的計算都是發生在相應的高斯金字塔尺度層面上，而非原圖或者DOG上，此外由于旋轉產生的像素值丟失通過插值算法解決，可以自行了解。如果想在原圖上可視化SIFT特征，需要將我們獲得的穩定特征點坐標變換回原始的圖像尺寸上，簡單的乘以原下采樣倍數即可。

總結

?至此SIFT算法就講解完畢了，匹配的部分根據提的特征采用其他的聚類算法即可，總的來說這個算法還是有一定難度，本文也只是針對其他博客沒有提到的細節引入了數學推導，使得整個思考過程更加連貫，更加詳細的數學證明如有限差分法還請移步參考。

參考：

SIFT原理部分：
SIFT算法詳解
SIFT算法原理詳解
SIFT算法
SIFT(尺度不變特征變換)
LOG和DOG關系部分：
LOG算子
黑森矩陣意義部分：
Hessian矩陣以及在圖像中的應用
Hessian 矩陣的特征值有什么含義？
Hessian矩陣與多元函數極值
Hessian矩陣（黑塞矩陣）
為何矩陣特征值乘積等于矩陣行列式值？
高斯相乘部分：
兩個高斯函數的卷積仍為一高斯函數

總結

以上是生活随笔為你收集整理的SIFT算法详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。