尺度不變特徵轉換(SIFT, Scale Invariant Feature Transform)是在2004年由David G. Lowe所提出，主要是用在影像特徵點萃取．其優點是所萃取 的特徵不易受到影像旋轉、縮放和灰度值差異而有所變化、具有良好特徵點選取與匹配，其匹配結果正確率較高並可消除影像處理中不確定性．目前常見的應用為全景圖的拼接：將圖片中相似特徵點的位置找出，並進行拼接，本篇文章將解釋SIFT的數學原理，並在最後我們會python將它實現在全景圖的拼接上．
SIFT演算法分成四個步驟：
- 特徵值位置偵測(使用DoF)
- 特徵點校正
- 方向指定
- 特徵描述
SIFT特徵萃取因為是尺度不變(Scale Invariance)，所以在做特徵萃取時效果比Harris好，Harris演算法常常在圖片放大時把corner特徵辨識為edge特徵，如下圖所示：
特徵值位置偵測(使用DoF)
SIFT如何達到尺度不變？？ 可以使用Laplacian of Gaussian(LoG)．
Laplacian of Gaussian(LoG)的操作方法如下：
- 取一張圖，並用高斯濾鏡將它變模糊
- 計算二次微分的總和(Laplacian)
得到特徵點(corner和edge)的位置．
從上面兩張圖可以得知，Edge的找法有兩種：
- 高斯函數一次微分對圖片做convelution的最大值
- 高斯函數二次微分對圖片做convelution的crossing 0點
找corner的方法如上：高斯內核(Gausian kernal)二次微分對圖片做convelution的極值(最大值或最小值)為corner的位置，偵測到的corner大小與高斯內核的大小相似．因此這個方法並非“尺度不變”．
若圖片中有一個半徑為8的corner，我們用σ=1,2,4,8,16的高斯內核二次微分分別對圖片做convelution．只有σ=8的高斯內核二次微分對圖片做convelution的極值才是corner的位置．且convolution值的大小會隨著σ的增加而變小，原因如下：σ越大下圖的紅色面積越小，所以convolution的值也就會越小．為了達到“尺度不變”，我們必須對comvolution的值乘上σ平方．數學證明參考以下連結．
經過σ平方的normalization後可以找到σ=8時會有極值，而這個物質就是corner的位置．
從上圖得知，實際上difference of Gausian (DoG)與Laplacian of Gausian (LoG)相似，實際上我們看可以用熱傳的方程式來證明DoF近似LoF：
左邊就是DoF；右邊就是LoF乘上σ平方．因此LoF可以用DoF取代，其運算流程如下圖所示．
特徵點校正
參考文章：N Campbell’s article
因為第一步驟的特徵點位置精確度與內核的選取數量(σ的數量)有關，因此我們要重新校正第一步驟搜尋到的特徵點位置．步驟如下：利用Taylor expansion fitting 3D quadratic surface (in x,y, and σ)找尋內差的最大或最小值．
z0是由[X,Y,σ]所組成的平面，z=[δx,δy,δσ]
把上面的式子對z做微分取零得到極值．
設定threshold，過濾掉threshold以下的特徵點位置．
方向指定
使用Histogram of Oriented Gradient (HOG)來定位．
特徵描述
