背景引言
計算機視覺中，引入尺度不變的特征，主要的思想是每個檢測到的特征點都伴随着對應的尺寸因子。當我們想比對不同圖像時，經常會遇到圖像尺度不同的問題，不同圖像中特征點的距離變得不同，物體變成不同的尺寸，如果我們通過修正特征點的大小，就會造成強度不比對。為了解決這個問題，提出一個尺度不變的SURF特征檢測，在計算特征點的時候把尺度因素加入之中。SURF與SIFT算法相似，SIFT算法比較穩定，檢測特征點更多，但是複雜度較高，而SURF要運算簡單，效率高，運算時間短一點。相關SIFT算法請詳見博文【圖像分析】尺度不變特征變換(SIFT)特征提取分析。本節介紹SURF算法相關知識。
基本介紹
首先，我們引用[3]中對SURF描述為：“SURF (Speeded Up Robust Features)isa robust local feature detector, first presented by Herbert Bay et al. in 2006, that can be used in computer vision tasks likeobject recognition or 3D reconstruction. It is partly inspired by the SIFT descriptor.The standard version of SURF is several times faster than SIFT and claimed by its authors to be more robust against different image transformations than SIFT. SURF is based on sums of2D Haar wavelet responses and makes an efficient use ofintegral images.It uses an integer approximation to the determinant of Hessian blob detector, which can be computed extremely quickly with an integral image (3 integer operations). For features, it uses the sum of the Haar wavelet response around the point of interest. Again, these can be computed with the aid of the integral image".
從上述對SURF描述，可知：第一、SURF算法是對SIFT算法加強版，同時加速的具有魯棒性的特征。第二、标準的SURF算子比SIFT算子快好幾倍，并且在多幅圖檔下具有更好的魯棒性。SURF最大的特征在于采用了harr特征以及積分圖像integral image的概念，這大大加快了程式的運作時間。
算法描述
為了實作尺度不變性的特征點檢測與比對，SURF算法則先利用Hessian矩陣确定候選點，然後進行非極大抑制，計算複雜度降低多了。整個算法由以下幾個部分組成。
1.Hessian黑森矩陣建構
我們知道：SIFT算法建立一幅圖像的金字塔，在每一層進行高斯濾波并求取圖像差(DOG)進行特征點的提取，而SURF則用的是Hessian Matrix進行特征點的提取，是以黑森矩陣是SURF算法的核心。假設函數f(x,y)，Hessian矩陣H是由函數偏導數組成。首先來看看圖像中某個像素點的Hessian Matrix的定義為：
進而每一個像素點都可以求出一個Hessian Matrix. Hessian矩陣判别式為：
判别式的值是H矩陣的特征值，可以利用判定結果的符号将所有點分類，根據判别式取值正負，從來判别該點是或不是極點的值。在SURF算法中，通常用圖像像素I(x,y)取代函數值f(x,y)。然後選用二階标準高斯函數作為濾波器。通過特定核間的卷積計算二階偏導數，這樣便能計算出H矩陣的三個矩陣元素Lxx, Lxy, Lyy，進而計算出H矩陣公式如下：
但是由于我們的特征點需要尺度無關性，是以在進行Hessian矩陣構造前，需要對其進行高斯濾波。這樣，經過濾波後在進行Hessian的計算，其公式如下：
L(x,t)是一幅圖像在不同解析度下的表示，可以利用高斯核G(t)與圖像函數I(x)在點x的卷積來實作，其中高斯核G(t)為：
其中g(t)為高斯函數，t 為高斯方差。通過這種方法可以為圖像中每個像素計算出其H矩陣的決定值，并用這個值來判别特征點。為此Herbert Bay提出用近似值現代替L(x,t)。為平衡準确值與近似值間的誤差引入權值。權值随尺度變化，則H矩陣判别式可表示為：
其中為何式中0.9呢.請詳見[1]。因求Hessian時要先高斯平滑，然後求其二階導數，這在離散的像素是用模闆卷積形
成的。這比如說y方向上的模闆Fig1(a)和Fig1(c).Fig1(a)即用高斯平滑後在y方向上求二階導數的模闆。為了加快運算用了近似處理，其處理結果如Fig1(b)所 示，這樣就簡化了很多。并且可以采用積分圖來運算，大大的加快了速度。同理，x和y方向的二階混合偏導模闆Fig1(b)與Fig1(d)。
2. 尺度空間生成
圖像的尺度空間是這幅圖像在不同解析度下的表示。上面講的這麼多隻是得到了一張近似Hessian行列式圖，這類似SIFT中的DOG圖，但是在金字塔圖像中分為很多層，每一層叫做一個octave，每一個octave中又有幾張尺度不同的
圖檔。在SIFT算法中，同一個octave層中的圖檔尺寸(即大小)相同，但是尺度(即模糊程度)不同，而不同的octave層中的圖檔尺寸大小也不相同，因為它是由上一層圖檔降采樣得到的。在進行高斯模糊時，SIFT的高斯模闆大小是始終不變的，隻是在不同的octave之間改變圖檔的大小。而在SURF中，圖檔的大小是一直不變的，不同的octave層得到的待檢測圖檔是改變高斯模糊尺寸大小得到的，當然了，同一個octave中個的圖檔用到的高斯模闆尺度也不同。算法允許尺度空間多層圖像同時被處理，不需對圖像進行二次抽樣，進而提高算法性能。上圖左邊是傳統方式建立一個如圖所示的金字塔結構，圖像的寸是變化的，并且運 算會反複使用高斯函數對子層進行平滑處理，上圖右邊說明SURF算法使原始圖像保持不變而隻改變濾波器大小。SURF采用這種方法節省了降采樣過程，其處理速度自然也就提上去了(注：上圖檔來自于網絡)。
3. 利用非極大值抑制初步确定特征點和精确定位特征點
将經過hessian矩陣處理過的每個像素點與其3維領域的26個點進行大小比較，如果它是這26個點中的最大值或者最小值，則保留下來，當做初步的特征點。檢測過程中使用與該尺度層圖像解析度相對應大小的濾波器進行檢測，以3×3的濾波器為例，該尺度層圖像中9個像素點之一.如下圖中檢測特征點與自身尺度層中其餘8個點和在其之上及之下的兩個尺度層9個點進行比較，共26個點，圖中标記‘x’的像素點的特征值若大于周圍像素則可确定該點為該區域的特征點。
然後，采用3維線性插值法得到亞像素級的特征點，同時也去掉那些值小于一定門檻值的點，增加極值使檢測到的特征點數量減少，最終隻有幾個特征最強點會被檢測出來。
4. 選取特征點主方向确定
為了保證旋轉不變性，在SURF中，不統計其梯度直方圖，而是統計特征點領域内的Harr小波特征。即以特征點為中心，計算半徑為6s(S為特征點所在的尺度值)的鄰域内，統計60度扇形内所有點在x(水準)和y(垂直)方向的Haar小波響應總和(Haar小波邊長取4s)，并給這些響應值賦高斯權重系數，使得靠近特征點的響應貢獻大，而遠離特征點的響應貢獻小，然後60度範圍内的響應相加以形成新的矢量，周遊整個圓形區域，選擇最長矢量的方向為該特征點的主方向。這樣，通過特征點逐個進行計算，得到每一個特征點的主方向。該過程的示意圖如下：
5. 構造SURF特征點描述算子
在SURF中，也是在特征點周圍取一個正方形框，框的邊長為20s(s是所檢測到該特征點所在的尺度)。該框帶方向，方向當然就是第4步檢測出來的主方向了。然後把該框分為16個子區域，每個子區域統計25個像素的水準方向和垂直方向的haar小波特征，這裡的x(水準)和y(垂直)方向都是相對主方向而言的。該haar小波特征為x(水準)方向值之和，水準方向絕對值之和，垂直方向之和，垂直方向絕對值之和。該過程的示意圖如下所示：
綜上所述，目前，對SURF算法有了一定了解。是以，可知SURF采用Henssian矩陣擷取圖像局部最值還是十分穩定的，但是在求主方向階段太過于依賴局部區域像素的梯度方向，有可能使得找到的主方向不準确，後面的特征向量提取以及比對都嚴重依賴于主方向，即使不大偏差角度也可以造成後面特征比對的放大誤差，進而比對不成功；另外圖像金字塔的層取得不足夠緊密也會使得尺度有誤差，後面的特征向量提取同樣依賴相應的尺度，在這個問題上我們隻能采用折中解決方法：取适量的層然後進行插值。
實驗結果：
圖像特征提取效果圖如下所示：
圖像比對效果圖所示：
補充思考問題
1. 為什麼選用高斯金字塔來作特征提取？
首先，采用DOG的金字塔原因是：因為它接近LOG，而LOG的極值點提供了最穩定的特征，而且DOG友善計算(隻要做減法).而LOG的極值點提供的特征最穩定。其次，我們從直覺了解：特征明顯的點經過不同尺度的高斯濾波器進行濾波後，差别較大，是以用到的是DOG。但是直覺上怎麼了解呢. 如果相鄰Octave的sigma不是兩倍關系還好了解：如果兩幅圖像隻是縮放的關系，那麼假設第一個Octave找到了小一倍圖像的極值點，那麼大一倍圖像的極值點會在下一個Octave找到相似的。但是現在，如果把大一倍圖像進行一次下采樣(這樣和小的圖像就完全一樣了)，進行Gauss濾波時，兩個圖像濾波系數(sigma)是不一樣的，不就找不到一樣的極值點了麼.
2.Hessian矩陣為什麼能用來篩選極值點？
SIFT先利用非極大抑制，再用到Hessian矩陣進行濾除。SURF先用Hessian矩陣，再進行非極大抑制。SURF的順序可以加快篩選速度麼(Hessian矩陣濾除的點更多?)至于SURF先用Hessian矩陣，再進行非極大抑制的原因，是不管先極大值抑制還是判斷Hessian矩陣的行列式，金字塔上的點的行列式都是要計算出來的。先判斷是否大于0隻要進行1次判斷，而判斷是否是極大值點或者極小值點要與周圍26個點比較，隻比較1次肯定快。而在SIFT中，建構的高斯金字塔隻有一座(不想SURF是有3座)，要進行非極大抑制可以直接用金字塔的結果進行比較。而如果計算Hessian矩陣的行列式，還要再計算Dxx、Dxy、Dyy。是以先進行非極大抑制。這兩個步驟的先後與SIFT/SURF的實際計算情況有關的，都是目前算法下的最佳順序，而不是說哪種先計算一定更好。
3、為什麼采用梯度特征作為局部不變特征？
這與人的視覺神經相關。采用梯度作為描述子的原因是，人的視覺皮層上的神經元對特定方向和空間頻率的梯度相應很敏感，經過SIFT作者的一些實驗驗證，用梯度的方法進行比對效果很好。
4、為什麼可以采用某些特征點的局部不變特征進行整幅圖像的比對？
從直覺的人類視覺印象來看，人類視覺對物體的描述也是局部化的，基于局部不變特征的圖像識别方法十分接近于人類視覺機理，通過局部化的特征組合，形成對目标物體的整體印象，這就為局部不變特征提取方法提供了生物學上的解釋，是以局部不變特征也得到了廣泛應用。圖像中的每個局部區域的重要性和影響範圍并非同等重要，即特征不是同等顯著的，其主要理論來源是Marr的計算機視覺理論和Treisman的特征整合理論，一般也稱為“原子論”。該理論認為視覺的過程開始于對物體的特征性質和簡單組成部分的分析，是從局部性質到大範圍性質。SIFT/SURF都是對特征點的局部區域的描述，這些特征點應該是影響重要的點，對這些點的分析更加重要。是以在局部不變特征的提取和描述時也遵循與人眼視覺注意選擇原理相類似的機制，是以SIFT/SURF用于比對有效果。
5. 為什麼Hessian矩陣可以用來判斷極大值/極小值?
在x0點上，hessian矩陣是正定的，且各分量的一階偏導數為0，則x0為極小值點。在x0點上，hessian矩陣是負定的，且各分量的一階偏導數為0，則x0為極大值點。
對于某個局部區域，若hessian矩陣是半正定的，則這個區域是凸的（反之依然成立）；若負定，則這個區域是凹的(反之依然成立)。而對于正定和負定來說，Hessian矩陣的行列式總是大于等于0的。反過來就是說：某個點若是極大值/極小值，hessian矩陣的行列式必然要大于等于0，而大于等于0如果是滿足的，這個點不一定是極大值/極小值(還要判斷一階導數)。是以後面還要進行極大值抑制.
補充知識
[1] OpenSURF-The Offical Home of the Image Processing Libary. http://www.chrisevansdev.com/computer-vision-opensurf.html.(補充時間：2013年12月5日)
參考資料
[1] Herbert Bay, Andreas Ess, Tinne Tuytelaars, Luc Van Gool, "SURF: Speeded Up Robust Features", Computer Vision and Image Understanding (CVIU), Vol. 110, No. 3, pp. 346--359, 2008.
[2] The Website of SURF: Speeded Up Robust Features.
[3] Speeded Up Robust Features(SURF) ,Wikipedia, the free encyclopedia .
關于Image Engineering & Computer Vision的更多讨論與交流，敬請關注本博和新浪微網誌songzi_tea.