SURF算法分析課件

用stitching算法進(jìn)行圖像拼接

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

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

位置尺度SURF算法分析Lxx(x,?)是高斯二階微分在點(diǎn)X=(x,y)處與圖像I的卷積。Bay指出，高斯函數(shù)雖然是最佳的尺度空間分析工具，但由于在實際應(yīng)用中總要對高斯函數(shù)進(jìn)行離散化和剪切處理，從而損失了一些特性（如重復(fù)性）。這一因素為我們用其他工具代替高斯函數(shù)對尺度空間的分析提供了可能，只要誤差不大就可以。所以就引入了盒裝濾波器。SURF算法分析如下圖所示第一行圖像就是經(jīng)過離散化，被剪切成9X9方格，=1.2的沿x方向、y方向和xy方向的高斯二階微分算子，即Lxx,Lxy,Lyy模板，這些微分算子可以用9x9的盒裝濾波器—Dxx模板、Dxy模板、Dyy模板替代，即圖中第二行圖像。盒裝濾波器中白色部分權(quán)值為1，灰色部分權(quán)值為0，Dxx和Dyy模板黑色部分的權(quán)值為-2，Dxy模板黑色部分權(quán)值為-1，白色部分和黑色部分統(tǒng)稱突起。SURF提取特征點(diǎn)

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

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

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

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

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

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

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

（3.1）

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

（3.3）SURF算法分析

（3.4）

對于所有的對應(yīng)點(diǎn)對，如果要確定8個未知參數(shù)，需要使下式的值達(dá)到最?。?/p>

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

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

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

（3.7）SURF算法分析

△

△

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

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