SURF算法分析

1、用用stitching算法算法進行圖像拼接進行圖像拼接 第一部分：用surf算法提取特征點 第二部分：特征點匹配 第三部分：構建透視矩陣完成拼接 第四部分 : 圖像融合1.SURF 介紹介紹 SURF (Speeded Up Robust Feature)是一種高魯棒性的局部特征點檢測器。由Herbert Bay 等人在2006年提出。該算法可以用于計算機視覺領域例如物體識別或者三維重建。根據(jù)作者描述該算法比SIFT更快更加具有魯棒性。該算法中采用積分圖像、Haar小波變換和近似的Hessian矩陣運算來提高時間效率,采用Haar小波變換增加魯棒性。一.用SURF算法提取特征點1.1積分圖像積

2、分圖像BC積分圖像積分圖像AD1.2Hessian矩陣矩陣快速快速Hessian 在SURF中，采用近似的Hessian矩陣的行列式的局部最大值來定位感興趣點的位置。當Hessian行列式的局部值最大的時候，所檢測出來的就是感興趣點。感興趣點的特征為比周圍鄰域更亮或者更暗一些。給定圖像f(x,y)中一個點 (x,y)，其Hessian矩陣H(x,o)定義如下： 位置尺度 Lxx(x, ? )是高斯二階微分在點X=(x,y)處與圖像I的卷積。 Bay指出，高斯函數(shù)雖然是最佳的尺度空間分析工具，但由于在實際應用中總要對高斯函數(shù)進行離散化和剪切處理，從而損失了一些特性（如重復性）。這一因素為我們用其

3、他工具代替高斯函數(shù)對尺度空間的分析提供了可能，只要誤差不大就可以。所以就引入了盒裝濾波器。如下圖所示第一行圖像就是經(jīng)過離散化，被剪切成9X9方格，=1.2的沿x方向、y方向和xy方向的高斯二階微分算子，即Lxx,Lxy,Lyy模板，這些微分算子可以用9x9的盒裝濾波器Dxx模板、Dxy模板、Dyy模板替代，即圖中第二行圖像。盒裝濾波器中白色部分權值為1，灰色部分權值為0，Dxx和Dyy模板黑色部分的權值為-2，Dxy模板黑色部分權值為-1，白色部分和黑色部分統(tǒng)稱突起。SURF 提取特征點提取特征點1.3盒子濾波器盒子濾波器下面介紹利用積分圖像求Dxx、Dyy、Dxy的方法首先用前面的積分公式把

4、輸入圖像轉化為積分圖像，然后應用和狀濾波器逐一對積分圖像進行處理，盒裝濾波器灰色部分權值為0，不參與計算，Dxx模板和Dyy模板各有兩個白色部分和一個黑色部分，因此他們的盒裝濾波器共有三個突起部分，而Dxy模板有兩個白色部分和兩個黑色部分，因此它的盒裝濾波器共有四個突起部分，利用盒裝濾波器對圖像進行濾波處理得到響應值得一般公式為：N表示突起部分總和，對于Dxx模板和Dyy模板來說，N=3，對于Dxy模板來說，N=4;Sn表示突起部分的面積，如對于9x9的Dxx模板和Dyy模板來說，突起部分的面積都是是15（即像素數(shù)量），而對于9x9的Dxy模板來說，突起部分面積都是9，除以Sn的作用是對模板進

5、行歸一化處理；Wn表示第n個突起部分的權值；而后面的括號部分就是前面的公式，求模板的每個突起部分對應于圖像四個點A、B、C、D所組成的矩陣區(qū)域的灰度之和。SURF 提取特征點提取特征點快速快速Hessian加權系數(shù)Lxx是高斯模板與圖像卷積Dxx是盒子模板與圖像卷積用Dxx近似代替Lxx 如果行列式的結果符號為負，則特征值有不同的符號，則不是局部極值點。 如果行列式的符號為正，則該行列式的兩個特征值同為正或負，所以該點可以歸類為極值點。Hessian矩陣的行列式的極值處即為特征點而盒裝濾波器代替高斯二階微分算子要加一定的權值w，作用是平衡因近似所帶來的誤差,w約為0.91.4構建金字塔構建金字

6、塔構建尺構建尺度空間度空間 由于采用的盒子濾波和積分圖像，不需要像SIFT算法那樣去直接建立金字塔圖像，而是采用不斷增大的盒子濾波模板的尺寸的間接方法。通過不同尺寸盒子濾波模板和積分圖像求取Hessian矩陣行列式的響應圖像，然后，在響應圖像上采用3D非最大值抑制，求取各種不同尺度的斑點。SIFT構建尺度空間構建尺度空間SURF構建尺度空間構建尺度空間模板模板圖片圖片1.5構建尺度空間構建尺度空間構建尺構建尺度空間度空間 與SIFT相類似，SURF也將尺度空間劃分成若干組(Octaves)。一個組代表了逐步放大的濾波模板對同一個輸入圖像進行濾波的一系列響應圖像。每一組又有若干固定的層組成。 9

7、 15 21 27 15 27 39 51 27 51 75 99 51 99 147 195 變化量 n*6變化量6*nScaleOctaves1.6極值點抑制極值點抑制極值點極值點抑制抑制 為了在目標影像上確定SURF特征點，我們使用了3*3*3的模板在3維尺度空間進行非最大化抑制，根據(jù)預設的Hessian閾值H，當h大于H，而且比臨近的26個點的響應值都大的點才被選為興趣點。最后進行插值最后進行插值精確。精確。特征點特征點方向分配方向分配 為了保證旋轉不變性，需要對每一個特征點分配一個主要方向。需要以特征點為中心，以6s（s為特征點的尺度）為半徑的圓形區(qū)域內，對圖像進行Haar小波響應運

8、算。這樣做實際就是對圖像進行了梯度運算，但是利用積分圖像，可以提高計算圖像梯度的效率。為了求取主方向值，需要設計一個以方向為中心，張角為PI/3的扇形滑動窗口，以步長為0.2弧度左右，旋轉這個滑動窗口，并對窗口內的圖像Haar小波的響應值進行累加。 主方向為最大的Haar響應累加值對應的方向 。 旋轉窗口旋轉窗口1.7.特征點方向分配1.8生成特征描述符生成特征描述符生成特生成特征描述符征描述符 生成特征點的特征描述符需要計算圖像的Haar小波響應。在一個矩形的區(qū)域內，以特征點為中心，沿主方向將20s*20s的圖像劃分成4*4個子塊，每個子塊利用尺寸2s的Haar小波模板進行響應計算，然后對響

9、應值進行統(tǒng)計 ， ， ， 形成的特征矢量 。dxdxdydy 主方向主方向5s*5s旋轉到主方向旋轉到主方向Hear小波模板 每個子塊中又有25個采樣像素，對于每個區(qū)域內，我們需要累加所有25個采樣像素的dx和dy，這樣形成描述符的一部分，而為了把強度變化的極性信息也包括今描述符中，我們還需要對dx和dy的絕對值進行累加。這樣每個區(qū)域就可以用一個4維特征矢量表示，把所有4x4子區(qū)域組合起來，就形成了一個64維特征矢量，即surf描述符。標出特征點的圖像標出特征點的圖像二.特征點匹配特征點匹配特征點匹配特征點特征點匹配匹配 步驟1. 在檢測特征點的過程中，計算了 Hessian 矩陣的行列式，與

10、此同時，計算得到了 Hessian 矩陣的跡，矩陣的跡為對角元素之和。 按照亮度的不同，可以將特征點分為兩種，第一種為特征點及其周圍小鄰域的亮度比背景區(qū)域要亮，Hessian 矩陣的跡為正；另外一種為特征點及其周圍小鄰域的亮度比背景區(qū)域要暗，Hessian 矩陣為負值。根據(jù)這個特性，首先對兩個特征點的 Hessian 的跡進行比較。如果同號，說明兩個特征點具有相同的對比度；如果是異號的話，說明兩個特征點的對比度不同，放棄特征點之間后續(xù)的相似性度量。特征點匹配特征點匹配特征點特征點匹配匹配步驟2.對于兩個特征點描述符的相似性度量，我們采用歐式距離進行計算： 式中，Xik表示待配準圖中第 i 個特

11、征描述符的第 k 個元素， Xjk是參考圖中第 j個特征描述子的第k 個元素，n表示特征向量的維數(shù)。 對于待配準圖上的特征點，計算它到參考圖像上所有特征點的歐氏距離，得到一個距離集合。通過對距離集合進行比較運算得到小歐氏距離和次最小歐式距離。設定一個閾值，一般為 0.8，當最小歐氏距離和次最小歐式距離的比值小于該閾值時，認為特征點與對應最小歐氏距離的特征點是匹配的，否則沒有點與該特征點相匹配。閾值越小，匹配越穩(wěn)定，但極值點越少。特征點匹配特征點匹配特征點特征點匹配匹配特征點匹配后圖像特征點匹配后圖像三.構建透視矩陣完成拼接三三.構建透視矩陣完成拼接構建透視矩陣完成拼接 在參考圖像和待拼接圖像的

12、重疊區(qū)域中提取到相應的特征點集后，就需要構造變換透視矩陣，通過特征點集不斷進行迭代對透視矩陣求精，然后根據(jù)求得的透視變換矩陣將待拼接圖像變換到了參考圖像的坐標。但是從透視變換矩陣求得的變換坐標并不是整數(shù)，所以還需要對求得的坐標進行灰度插值計算，以使圖像變換到正確的坐標系中。 透視變換矩陣是由Szeliski提出的圖像變換法，首先通過建立圖像序列之間的變換模型，然后通過迭代算法求出模型的變換參數(shù)，實現(xiàn)對圖像序列的拼接，這就是著名的8參數(shù)透視變換模型。對于相鄰兩幅圖像之間的變換關系，可以用一個具有8個參數(shù)的變換模型來描述： （3.1） （3.2） 其中，I(x,y)和I(x,y)分別為兩幅圖像的對

13、應點坐標，可以看出，計算透視變換矩陣H，實質上就是計算矩陣中的8個參數(shù)。將(3.1)模型的矩陣形式進行改寫，得到 （3.3） （3.4） 對于所有的對應點對，如果要確定8個未知參數(shù)，需要使下式的值達到最?。?（3.5）通過(3.3)式和(3.4)式可以知道，選取4組對應點，就能夠計算出透視變換模型的8個參數(shù)，但是隨機選取的對應點不一定就能夠得到模型的準確參數(shù)，所以在求其最小值的過程中采用LevenbergMarguqrdt迭代非線性最小化方法對透視變換矩陣進行求精。 首先對于8個未知參數(shù)m，求偏導數(shù)，即： （3.6） 式中的Di是(3.3）和(3.4)式的分母，然后計算兩個矩陣A和b，其中A中

14、的元素為： （3.7） 總結：采用這種變換矩陣的方法可以處理圖像之間存在平移、旋轉、縮放等變化條件下的拼接。四.圖像融合 四：圖像融合 通過圖像匹配將兩幅圖像變換到了同一坐標系后，得到了兩幅圖像的拼接結果。但是，由于圖像采集所帶來的光照、視野等的差異，拼接好的兩幅圖片在相結合的部分會出現(xiàn)明顯的拼接縫隙，圖像融合技術就是為了去除這種拼接縫隙的有力工具。圖像融合應當滿足幾個方面的要求：首先，為了消除圖像的拼接縫隙，就必須采用一種漸變的方法來將拼接的縫隙部分像素轉變?yōu)閺牡谝桓眻D片漸變?yōu)榈诙鶊D片；其次，圖像的融合應當只針對于拼接的結合部分有效，對于圖像的其他部分不能夠產生影響；最后， 融合算法在算法的復雜度上不能太高，不能影響了圖像拼接的整體速度。 加權平均法對于重疊部分的像素值不是簡單的疊加求平均值，而是先進行加權后，再進行疊加平均。假設現(xiàn)在有兩幅圖像中的重疊部分分別定義一個