SURF算法分析課件

用stitching算法進行圖像拼接

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

積分圖像SURF算法分析1.2Hessian矩陣快速Hessian在SURF中，采用近似的Hessian矩陣的行列式的局部最大值來定位感興趣點的位置。當Hessian行列式的局部值最大的時候，所檢測出來的就是感興趣點。感興趣點的特征為比周圍鄰域更亮或者更暗一些。 給定圖像f(x,y)中一個點(x,y)，其Hessian矩陣H(x,o)定義如下：

位置尺度SURF算法分析Lxx(x,?)是高斯二階微分在點X=(x,y)處與圖像I的卷積。Bay指出，高斯函數(shù)雖然是最佳的尺度空間分析工具，但由于在實際應用中總要對高斯函數(shù)進行離散化和剪切處理，從而損失了一些特性（如重復性）。這一因素為我們用其他工具代替高斯函數(shù)對尺度空間的分析提供了可能，只要誤差不大就可以。所以就引入了盒裝濾波器。SURF算法分析如下圖所示第一行圖像就是經(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提取特征點

SURF算法分析1.3盒子濾波器下面介紹利用積分圖像求Dxx、Dyy、Dxy的方法首先用前面的積分公式把輸入圖像轉(zhuǎn)化為積分圖像，然后應用和狀濾波器逐一對積分圖像進行處理，盒裝濾波器灰色部分權值為0，不參與計算，Dxx模板和Dyy模板各有兩個白色部分和一個黑色部分，因此他們的盒裝濾波器共有三個突起部分，而Dxy模板有兩個白色部分和兩個黑色部分，因此它的盒裝濾波器共有四個突起部分，利用盒裝濾波器對圖像進行濾波處理得到響應值得一般公式為：N表示突起部分總和，對于Dxx模板和Dyy模板來說，N=3，對于Dxy模板來說，N=4;Sn表示突起部分的面積，如對于9x9的Dxx模板和Dyy模板來說，突起部分的面積都是是15（即像素數(shù)量），而對于9x9的Dxy模板來說，突起部分面積都是9，除以Sn的作用是對模板進行歸一化處理；Wn表示第n個突起部分的權值；而后面的括號部分就是前面的公式，求模板的每個突起部分對應于圖像四個點A、B、C、D所組成的矩陣區(qū)域的灰度之和。SURF算法分析SURF提取特征點快速Hessian加權系數(shù)Lxx是高斯模板與圖像卷積Dxx是盒子模板與圖像卷積用Dxx近似代替Lxx

如果行列式的結(jié)果符號為負，則特征值有不同的符號，則不是局部極值點。如果行列式的符號為正，則該行列式的兩個特征值同為正或負，所以該點可以歸類為極值點。Hessian矩陣的行列式的極值處即為特征點而盒裝濾波器代替高斯二階微分算子要加一定的權值w，作用是平衡因近似所帶來的誤差,w約為0.9SURF算法分析1.4構(gòu)建金字塔構(gòu)建尺度空間

由于采用的盒子濾波和積分圖像，不需要像SIFT算法那樣去直接建立金字塔圖像，而是采用不斷增大的盒子濾波模板的尺寸的間接方法。通過不同尺寸盒子濾波模板和積分圖像求取Hessian矩陣行列式的響應圖像，然后，在響應圖像上采用3D非最大值抑制，求取各種不同尺度的斑點。SIFT構(gòu)建尺度空間SURF構(gòu)建尺度空間模板圖片SURF算法分析1.5構(gòu)建尺度空間構(gòu)建尺度空間與SIFT相類似，SURF也將尺度空間劃分成若干組(Octaves)。一個組代表了逐步放大的濾波模板對同一個輸入圖像進行濾波的一系列響應圖像。每一組又有若干固定的層組成。915212715273951275175995199147195變化量n*6變化量6*nScaleOctavesSURF算法分析1.6極值點抑制極值點抑制為了在目標影像上確定SURF特征點，我們使用了3*3*3的模板在3維尺度空間進行非最大化抑制，根據(jù)預設的Hessian閾值H，當h大于H，而且比臨近的26個點的響應值都大的點才被選為興趣點。最后進行插值精確。SURF算法分析特征點方向分配為了保證旋轉(zhuǎn)不變性，需要對每一個特征點分配一個主要方向。需要以特征點為中心，以6s（s為特征點的尺度）為半徑的圓形區(qū)域內(nèi)，對圖像進行Haar小波響應運算。這樣做實際就是對圖像進行了梯度運算，但是利用積分圖像，可以提高計算圖像梯度的效率。為了求取主方向值，需要設計一個以方向為中心，張角為PI/3的扇形滑動窗口，以步長為0.2弧度左右，旋轉(zhuǎn)這個滑動窗口，并對窗口內(nèi)的圖像Haar小波的響應值進行累加。主方向為最大的Haar響應累加值對應的方向。

旋轉(zhuǎn)窗口1.7.特征點方向分配SURF算法分析1.8生成特征描述符生成特征描述符生成特征點的特征描述符需要計算圖像的Haar小波響應。在一個矩形的區(qū)域內(nèi)，以特征點為中心，沿主方向?qū)?0s*20s的圖像劃分成4*4個子塊，每個子塊利用尺寸2s的Haar小波模板進行響應計算，然后對響應值進行統(tǒng)計，，，形成的特征矢量。

主方向5s*5s旋轉(zhuǎn)到主方向Hear小波模板SURF算法分析每個子塊中又有25個采樣像素，對于每個區(qū)域內(nèi)，我們需要累加所有25個采樣像素的dx和dy，這樣形成描述符的一部分，而為了把強度變化的極性信息也包括今描述符中，我們還需要對dx和dy的絕對值進行累加。這樣每個區(qū)域就可以用一個4維特征矢量表示，把所有4x4子區(qū)域組合起來，就形成了一個64維特征矢量，即surf描述符。SURF算法分析標出特征點的圖像SURF算法分析二.特征點匹配SURF算法分析特征點匹配特征點匹配步驟1.在檢測特征點的過程中，計算了Hessian矩陣的行列式，與此同時，計算得到了Hessian矩陣的跡，矩陣的跡為對角元素之和。按照亮度的不同，可以將特征點分為兩種，第一種為特征點及其周圍小鄰域的亮度比背景區(qū)域要亮，Hessian矩陣的跡為正；另外一種為特征點及其周圍小鄰域的亮度比背景區(qū)域要暗，Hessian矩陣為負值。根據(jù)這個特性，首先對兩個特征點的Hessian的跡進行比較。如果同號，說明兩個特征點具有相同的對比度；如果是異號的話，說明兩個特征點的對比度不同，放棄特征點之間后續(xù)的相似性度量。SURF算法分析特征點匹配特征點匹配步驟2.對于兩個特征點描述符的相似性度量，我們采用歐式距離進行計算：

式中，Xik表示待配準圖中第i個特征描述符的第k個元素，Xjk是參考圖中第j個特征描述子的第k個元素，n表示特征向量的維數(shù)。。SURF算法分析

對于待配準圖上的特征點，計算它到參考圖像上所有特征點的歐氏距離，得到一個距離集合。通過對距離集合進行比較運算得到小歐氏距離和次最小歐式距離。設定一個閾值，一般為0.8，當最小歐氏距離和次最小歐式距離的比值小于該閾值時，認為特征點與對應最小歐氏距離的特征點是匹配的，否則沒有點與該特征點相匹配。閾值越小，匹配越穩(wěn)定，但極值點越少。特征點匹配特征點匹配SURF算法分析特征點匹配后圖像SURF算法分析三.構(gòu)建透視矩陣完成拼接SURF算法分析三.構(gòu)建透視矩陣完成拼接在參考圖像和待拼接圖像的重疊區(qū)域中提取到相應的特征點集后，就需要構(gòu)造變換透視矩陣，通過特征點集不斷進行迭代對透視矩陣求精，然后根據(jù)求得的透視變換矩陣將待拼接圖像變換到了參考圖像的坐標。但是從透視變換矩陣求得的變換坐標并不是整數(shù)，所以還需要對求得的坐標進行灰度插值計算，以使圖像變換到正確的坐標系中。透視變換矩陣是由Szeliski提出的圖像變換法，首先通過建立圖像序列之間的變換模型，然后通過迭代算法求出模型的變換參數(shù)，實現(xiàn)對圖像序列的拼接，這就是著名的8參數(shù)透視變換模型。對于相鄰兩幅圖像之間的變換關系，可以用一個具有8個參數(shù)的變換模型來描述：SURF算法分析

（3.1）

（3.2）其中，I(x,y)和I?(x?,y?)分別為兩幅圖像的對應點坐標，可以看出，計算透視變換矩陣H，實質(zhì)上就是計算矩陣中的8個參數(shù)。將(3.1)模型的矩陣形式進行改寫，得到

（3.3）SURF算法分析

（3.4）

對于所有的對應點對，如果要確定8個未知參數(shù)，需要使下式的值達到最小：

（3.5）通過(3.3)式和(3.4)式可以知道，選取4組對應點，就能夠計算出透視變換模型的8個參數(shù)，但是隨機選取的對應點不一定就能夠得到模型的準確參數(shù)，所以在求其最小值的過程中采用Levenberg—Marguqrdt迭代非線性最小化方法對透視變換矩陣進行求精。SURF算法分析

首先對于8個未知參數(shù)m，求偏導數(shù)，即：

（3.6）式中的Di是(3.3）和(3.4)式的分母，然后計算兩個矩陣A和b，其中A中的元素為：

（3.7）SURF算法分析

△

△

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

加權平均法對于重疊部分的像素值不是簡單的疊加求平均值，而是先進行加權后，再進行疊加平均。假設現(xiàn)在有兩幅圖像中的重疊部分分別定義一個權值，取為d1和d2,并且d1和d2都滿足條件屬于（0，1），且d1+d2=1。那么選擇合適的權值，就能夠使得重疊區(qū)域?qū)崿F(xiàn)平滑的過度。在重疊部分中，d1由1漸漸過渡到0，到由0漸漸過渡到