Sift演算法簡介
我們是怎麼識別圖像上面的內容的？
兩個點一樣嗎？
當把兩個點放在一個圖像上是否還是一樣
SIFT
SIFT演算法是由David Lowe在1999年研究出來，
並在2004年完善的一個用於描述和偵測圖像的演算法
Lowe將演算法分為了四個分解步驟：
1. 尺度空間極值檢測： 這一步我們將對圖像進行一些特定的處理，
處理之後，通過微分函數識別不會因為光照、尺度變化不變的興趣點
2. 關鍵點定位： 在第一步的基礎上，我們需要通過擬合判別，來丟掉
一些我們不穩定的興趣點
3. 方向確定： 在第二步的基礎上，我們為每一個點分配一個或者多個
方向
4. 描述子： 在每一個關鍵點的鄰域內，在選定的尺度上測量圖像梯度
這些梯度經過處理之後形成描述子
1. 高斯模糊
這是高斯分布的三維圖
理論上說，進行高斯濾波的時候，每個像素的計算都應該受到
同圖像下所有的像素的影響，但是實際上我們只計算
的鄰域
sigma = 0.6時的高斯模糊模板
矩陣卷積時，先將高斯模板的中心點與當前位置對應，將對應位置進行相乘後加入到當前位置
使用高斯模糊的可分離性可以簡化計算
2. 尺度空間
尺度空間(scale space)思想最早是由Iijima於1962年提出的，
後經witkin和Koenderink等人的推廣
尺度空間理論的基本思想是：在圖像信息處理模型中引入一個被視為尺度
的參數，通過連續變化尺度參數獲得多尺度下的尺度空間表示序列，
對這些序列進行尺度空間主輪廓的提取
尺度空間中各尺度圖像的模糊程度逐漸變大，能夠模擬人在
距離目標由近到遠時目標在視網膜上的形成過程。
尺度空間函數
其中
Sift通過尺度空間來構造Gauss金字塔，具體做法：
a) 設定初始參數 sigma(平滑參數), 初始參數S(該參數決定了金字塔每一層
的張數),初始參數k(躍進參數)，Sift中的參考值為sigma= 1.6、S = [6,8]、
K = 2^(1/(S-3))，並將此時的金字塔層設為初始態，最底層
b) 將原圖像設定位金字塔當前層第一張圖像（不是最底層，在Gauss金字
塔中，層的概念不一樣）
c) 使用高斯函數與原圖像進行卷積，sigma參數以k
進行指數遞增，得到當前層的第二張圖像
d) 循環c)，直到當前層有S張圖像
e) 向上一層，以下一層的倒數第三張圖像進行降採樣，得到當前層的基礎
圖像，重複a) - e),直到到達金字塔頂端（圖像像素為1*1）
尺度空間的圖
自上到下的sigma值
k^3σ
k^2σ
kσ
σ
0
k^3σ
k^2σ
kσ
σ
0
DOG函數
在這之前先看一下Laplace函數
Laplace函數:
2002年Mikolajczyk在詳細的實驗比較中發現尺度歸一化的高斯拉普拉斯
函數的極大值和極小值及其穩定
Laplace前先說明一下有限差分求導
有限差分求導
1. 用差分代替微分方程中的微分，將連續變化的變數離散化，從而
得到差分方程組的數學形式；
2. 求解差分方程組。
有限差分求導的結論
下面看一下推導，泰勒級數展開如下
取x = xi - h
兩式相減可以得到一階倒數，同理可以得到二階導數
通過有限差分求導
DOG函數和LOG函數在xoz或者yoz上的投影圖像
DOG空間
DOG函數
DOG空間上，遍歷空間內的每一個點，將這個點與它所有的相鄰點比較
看是否再其鄰域內共26個點中的最大或者最小，
如果是，則記錄這個點的O，I，X，Y
找到這些點，我們稱為興趣點，它們是連續空間上的極值點，也可能是
在連續空間的極值點附近，也可能與連續空間的極值點偏離較遠
關鍵點定位
我們在離散空間上探測到的興趣點可能不是真正的極值點，可以通過已知的
離散空間點進行子像素差值得到連續空間極值點
二元函數0點泰勒展開如下
矩陣形式
標量形式
通過下面的式子及讓導函數為0
可以求到極值點偏移量
x(x,y,σ) 為三維矢量,
是相對於插值中心點的偏移量
求取三階逆的時候使用如下算式
再加上有限差分求導可以求到
的最終結果
Sift演算法規定，當x，y，σ上任何一個方向上的偏移量大於0.5的時候
意味著該中心點已經發生了偏移，這樣的點不作為關鍵點
分配尺度坐標
尺度坐標定義為:
其中S定義為DOG同一層內，總共多少張圖像，s為當前圖像的位置
3. 關鍵點分配方向
對圖像上的每一個關鍵點求取其3*1.5σ_oct鄰域窗口內像素的梯度和分布特徵
，每一個點的梯度的模值和方向用下面的式子定義
將方向360°分成為8個柱，統計以上得到的那些方向落入某個柱內的總梯度模值(每一個模值按照1.5σ_oct大小的高斯分布加成)，得到的統計直方圖中，
峰值方向代表了關鍵點的主方向。
為了增強匹配的魯棒性，只保留峰值大於主方向峰值80％的方向作為
該關鍵點的輔方向
4. 描述向量
這個描述子不但包括關鍵點，也包含關鍵點周圍對其有貢獻的像素點，
並且描述符應該有較高的獨特性，以便於提高特徵點正確匹配的概率。
Lowe建議描述子使用在關鍵點尺度空間內4*4的窗口中計算的8個
方向的梯度信息，共4*4*8=128維向量表徵。表示步驟如下：
1. 以關鍵點為中心，3σ_oct * (d )為邊長形成一個矩形，將矩形分為
4*4個小的矩形
2. 在每一個矩形內，求取該矩形的方向直方圖。
3. 將求取到16 * 8個方向的數值組成128維向量
SIFT改進
1. 尺度空間構建中，為了保留更多的原始數據，形成更多的特徵，一般處理的時候，將原圖像進行線性插值後的圖像作為基礎圖像
2. 在興趣點選取關鍵點時，還需要剔除對比度較低和不穩定的點
3. 為了形成的描述子有更好的旋轉不變形，在生成描述子的過程中，我們可以對坐標軸旋轉為關鍵點的方向，在進行描述子的生成
4. 基於Sift的改進演算法有SURF和CSIFT
SIFT優點
1. 對於不同的圖像，有很強的穩定性
2. 獨特性好，信息量豐富
3. 擴展能力強，可以方便的將更強能力的某一單一處理演算法引入
SIFT缺點
1. 原始圖像較小的情況下，特徵點下降嚴重
2. 對邊緣光滑的目標無法準確提取特徵點，尤其是
圓，完全無能為力
推薦閱讀：