## SIFT步驟### 找尺度空間極值    可以用DoG找    需要講理論依據和DoG結合進行推導    s值和$\sigma$值的選取問題### 關鍵點定位    和泰勒展開相關### 方向賦值### 局部圖像描述符## SIFT用于目標識別的步驟    目標圖像提取SIFT特征；搭建SIFT特征數據庫    用快速kNN將目標特征在數據庫中查找    用霍夫變換尋找屬于同一單目標的簇(cluster)    用least-square(最小二乘法)驗證## SIFT算法步驟    多尺度極值檢測(用DoG找)    關鍵點定位    方向賦值    關鍵點描述符## 尺度空間極值檢測尺度空間定義：$L(x,y,\sigma)=G(x,y,\sigma)*I(x,y)$相關論文已證明，真正具有尺度無關性的算子只有一種：歸一化的LoG函數：$\sigma^2\nabla^2G$考慮高斯查分函數DoG:$G(x,y,k\sigma)-G(x,y,\sigma)$對應的尺度空間表達式有：$D(x,y,\sigma)=L(x,y,k\sigma)-L(x,y,\sigma) \\=(G(x,y,k\sigma)-G(x,y,\sigma))*I(x,y)$考慮熱放射等式，有：$\frac{\partial G}{\partial \sigma}=\sigma\nabla^2G$其證明過程：$G(x,y)=\frac{1}{2\pi \sigma^2}e^{\frac{x^2+y^2}{2\sigma^2}} \\\frac{\partial G}{\partial x}=-\frac{x}{2\pi\sigma^4}e^{-\frac{x^2+y^2}{2\sigma^2}}  \\\frac{\partial^2G}{\partial^2x}=-\frac{\sigma^2-x^2}{2\pi\sigma^6}e^{-\frac{x^2+y^2}{2\sigma^2}} \\\nabla^2G=\frac{\partial^2G}{\partial^2x}+\frac{\partial^2G}{\partial^2y} = \frac{x^2+y^2-2\sigma^2}{2\pi\sigma^6}e^{-\frac{x^2+y^2}{2\sigma^2}} \\\frac{\partial G}{\partial \sigma}=\frac{x^2+y^2-2\sigma^2}{2\pi\sigma^5}e^{-\frac{x^2+y^2}{2\sigma^2}}  \\\therefore \frac{\partial G}{\partial x}=\sigma \nabla^2 G$$G(x,y)=\frac{1}{2\pi \sigma^2}e^{\frac{x^2+y^2}{2\sigma^2}} \\\frac{\partial G}{\partial x}=-\frac{x}{2\pi\sigma^4}e^{-\frac{x^2+y^2}{2\sigma^2}}  \\\frac{\partial^2G}{\partial^2x}=-\frac{\sigma^2-x^2}{2\pi\sigma^6}e^{-\frac{x^2+y^2}{2\sigma^2}} \\\nabla^2G=\frac{\partial^2G}{\partial^2x}+\frac{\partial^2G}{\partial^2y} = \frac{x^2+y^2-2\sigma^2}{2\pi\sigma^6}e^{-\frac{x^2+y^2}{2\sigma^2}} \\\frac{\partial G}{\partial \sigma}=\frac{x^2+y^2-2\sigma^2}{2\pi\sigma^5}e^{-\frac{x^2+y^2}{2\sigma^2}}  \\\therefore \frac{\partial G}{\partial x}=\sigma \nabla^2 G$而考慮$\frac{\partial G}{\partial \sigma}$的近似替代公式：$\sigma\nabla^2G=\frac{\partial G}{\partial \sigma} \approx \frac{G(x,y,k\sigma)-G(x,y,\sigma)}{k\sigma-\sigma}$因此有：$G(x,y,k\sigma)-G(x,y,\sigma) \approx (k-1)\sigma^2\nabla^2G$即：用DoG來近似替代LoG算子，得到近似不變的尺度無關特性。相差的倍數是常量沒有影響。當k->1，誤差幾乎為0.### 高斯金字塔的建立**octave**：采樣率相同、尺寸相同，模糊度逐漸增強的一組相鄰圖像**level**：octave中的每張圖像，叫做一個level每個octae內是持續高斯模糊得到；每個octave的第一個levle通過降采樣得到。每個octave內有s次模糊。$\sigma$的選取和$s$選取，不能太小，否則不準確；太大又會消耗太多計算資源，得不到實時效果。Lowe的論文實驗表明，選取$\sigma=1.6$，$s=3$是合適的。不過為了充分利用輸入的圖像，可以考慮在生成octave前做一次升采樣：認為照相機采集的圖像本身就是模糊的，其$\sigma=0.5$，利用線性插值得到$\sigma=1.0$的圖像，然后用于生成octave**疑問**l升采樣后的圖像，有沒有再次做模糊操作得到octave的第一張？還是說直接作為octave的第一個level？### DoG金字塔每兩個高斯金字塔level之間做差值就得到DoG的一個level。為了得到所有極值，因為高斯金字塔的首尾兩層不會被帶入計算，因此在首尾各添加一層，最上面再加一層**這段還是不夠清晰，需要修改**### 局部極值檢測在DoG金字塔中，檢測空間中每個像素點周邊的26個點。如果是極值，那么繼續往金字塔高層進行檢測。極值檢測需要考慮檢測的策略：檢測到的極值點數量會影響到后續的特征檢測數量，特征越少則匹配的結果越少，但是往往是正確率較高的匹配；特征越多則匹配的結果越多，但是正確率往往不高。前者更多地考慮了效率，后者更多地考慮了完整性，需要在效率和完整性之間權衡。因而，要選取合適數量的特征數量，在這之前需要選取合適數量的極值點，這就需要考慮采樣頻率的問題。（實際上，集中在一起的極值點對于小的擾動非常不穩定）。采樣頻率的問題，包括尺度上的采樣頻率、空間域上的采樣頻率兩個方面。Lowe通過實驗得到一些測量結果，從結果的圖表中得到$s$值和$\sigma$值的經驗值。Lowe的實驗圖像“有32張，包括室外場景、人臉、航拍圖片、工業圖像（這些圖像的來源領域對結果幾乎沒有影響）”。但是本人認為，僅僅從32張圖像就得到相關的經驗參數，并不很具有說服力，如果有時間，不妨使用更多的圖片進行相關測定。尺度上的采樣頻率問題，就是考慮圖像金字塔中每個octave內的尺度空間數量s。實驗中尺度圖像由隨機的旋轉和0.2~0.9之間的隨機尺度變換得到，同時也添加了1%的噪聲（使用平均分布為每個像素點增加一個隨機數）。實驗結果為：隨著尺度數量s的增加，同一位置的重復匹配率“先增加后減小”，同一極值點對應的特征描述符在數據庫中被**正確**搜索到的比率，也是“先增加后減小”。折可以被解釋為：隨著尺度數量s的增加，盡管極值點數量增加，但是過了一定限度后增加的極值點都是低于平均穩定程度的，因而反倒降低了匹配的重復率和正確率。對應于Lowe的實驗結果，選取$s=3$時，正確匹配率最高。而隨著尺度數量s的增加，極值點數量也增加，并且正確匹配的極值點的總數也是增加的；而通常目標識別通常更依賴于正確匹配的極值點數量而不是正確匹配率，因此看起來使用更大的尺度空間數s會得到更好的效果。但是，這會增加計算消耗。因而，Lowe的論文中權衡了正確率和計算消耗，選取$s=3$作為每個octave內的尺度數量。也就是說，僅僅檢測那些穩定的極值點，同時又能夠避免大量的計算消耗，還能夠得到很好的正確率。空間域上的采樣頻率問題，就是高斯模糊的參數$\sigma$，即平滑尺度。考慮到極值可能隨機地出現在一起，也需要類似前面一種情況考慮采樣頻率和檢率的問題。實驗數據表明，隨著$\sigma$的增加，同一特征點在變換后的圖像中被重復檢測到的百分比、極值點對應的特征描述符在數據庫中被查找到的正確率，都呈現增加趨勢。但是$\sigma$增加后計算量也增加，權衡考慮算法效率和正確率，使用$\sigma=1.6$。（同樣地，這顯然也是Lowe的32張圖像的測試結果帶來的經驗數據，個人認為這個數據要根據不同的情況可以適當修改）。同時也可以考慮圖像預先平滑操作，這樣能**有效地忽略最高空域頻率**（這句其實并不理解），其做法是：認為相機拍攝得到的原始圖像的模糊度為$\sigma=0.5$，通過雙線性差值得到$\sigma=1.0$模糊尺度的圖像。這就意味著，在創建尺度空間的第一個octave之前，需要做一次平滑操作（也就是：原圖升采樣得到$\sigma=1.0$-->做第一次預先處理的平滑得到$\sigma=1.6$的尺度圖像作為第一個octave的第一個level）。**這里發現對于“采樣”并不很理解，需要找書仔細看下**## 確定關鍵點的精確位置前面得到的極值，只是離散的圖像金字塔中不同尺度下的極值點。真正的尺度空間應當是連續的，而不是離散的，圖像金字塔中的極值只是真正極值的近似，還需要進一步的精確檢測，得到真正的極值點和極值。使用泰勒公式對DoG函數進行展開，并求導，解出導數為0的點，得到的解就是“前面極值檢測中檢測到的極值采樣點，與真正的尺度空間中的極值點的偏差（這個偏差是向量(x,y,$\sigma$)）”。即：$定義向量\vec{x} = (x, y, \sigma)對D函數，泰勒展開有：D(\vec {x})=D+\frac{\partial D^T}{\partial \vec {x}}\vec {x} + \frac{1}{2}\vec {x}^T\frac{\partial^2 D}{\partial \vec{x}^2}\vec {x}求解得到：\vec {x_0} = - \frac{\partial^2 D^{-1}}{\partial \vec {x}^2}\frac{\partial D}{\partial \vec {x}} $$其中使用到對于向量求導的計算，包括：  \\\frac{\partial \vec {x}}{\partial \vec {x}}=單位矩陣E    \\\frac{\partial \vec{x}^T \vec{x}}{\vec{x}} = 2 \vec{x}$將$\vec{x_0}$帶入$D(\vec{x})$的表達式，得到對應的極值：$D(\vec{x}) = D + \frac{1}{2}\frac{\partial D^T}{\partial \vec{x}}\vec{x}$實驗中忽略$D \lt 0.03$的極值點。這樣，得到的$\vec{x}$表示采樣點的偏離量。此時，keypoint的表示中包括了：位置(x,y),尺度$\sigma$。后面還會包括方向。### 消除邊界響應還需要去除邊界上的干擾，需要考慮**主曲率**。 通過計算**黑塞矩陣**能得到特征值之間的關系，而主曲率和特征值之間是成倍的關系，因此只需要考慮特征值之間的關系。假設黑塞矩陣算出的特征值中，大的為$\alpha$，小的為$\beta$，而：$ H=\begin{matrix}     D_{xx} & D_{xy} \\     D_{xy} & D_{yy}\end{matrix}$$Tr(H)=D_{xx}+D_{yy} = \alpha + \beta  \\Det(H)=D_{xx}D_{yy}-(D_{xy})^2 = \alpha \beta$顯然，$\frac{Tr(H)}{Det(H)}$是增函數，因此只需要保證：$\frac{Tr(H)^2}{Det(H)}