了解SIFT理解SIFT

了解SIFT

## 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)}