SURF算法分析教學(xué)課件

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

2、共34頁(yè)。1.1積分圖像積分圖像第4頁(yè)，共34頁(yè)。1.2Hessian矩陣快速Hessian 在SURF中，采用近似的Hessian矩陣的行列式的局部最大值來(lái)定位感興趣點(diǎn)的位置。當(dāng)Hessian行列式的局部值最大的時(shí)候，所檢測(cè)出來(lái)的就是感興趣點(diǎn)。感興趣點(diǎn)的特征為比周?chē)徲蚋粱蛘吒狄恍?。給定圖像f(x,y)中一個(gè)點(diǎn) (x,y)，其Hessian矩陣H(x,o)定義如下： 位置尺度第5頁(yè)，共34頁(yè)。Lxx(x, )是高斯二階微分在點(diǎn)X=(x,y)處與圖像I的卷積。Bay指出，高斯函數(shù)雖然是最佳的尺度空間分析工具，但由于在實(shí)際應(yīng)用中總要對(duì)高斯函數(shù)進(jìn)行離散化和剪切處理，從而損失了一些特性（如重復(fù)性

3、）。這一因素為我們用其他工具代替高斯函數(shù)對(duì)尺度空間的分析提供了可能，只要誤差不大就可以。所以就引入了盒裝濾波器。第6頁(yè)，共34頁(yè)。如下圖所示第一行圖像就是經(jīng)過(guò)離散化，被剪切成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)第7頁(yè)，共34頁(yè)。1.3盒子濾波器下面介紹利用積分圖像求Dxx、Dy

4、y、Dxy的方法首先用前面的積分公式把輸入圖像轉(zhuǎn)化為積分圖像，然后應(yīng)用和狀濾波器逐一對(duì)積分圖像進(jìn)行處理，盒裝濾波器灰色部分權(quán)值為0，不參與計(jì)算，Dxx模板和Dyy模板各有兩個(gè)白色部分和一個(gè)黑色部分，因此他們的盒裝濾波器共有三個(gè)突起部分，而Dxy模板有兩個(gè)白色部分和兩個(gè)黑色部分，因此它的盒裝濾波器共有四個(gè)突起部分，利用盒裝濾波器對(duì)圖像進(jìn)行濾波處理得到響應(yīng)值得一般公式為：N表示突起部分總和，對(duì)于Dxx模板和Dyy模板來(lái)說(shuō)，N=3，對(duì)于Dxy模板來(lái)說(shuō)，N=4;Sn表示突起部分的面積，如對(duì)于9x9的Dxx模板和Dyy模板來(lái)說(shuō)，突起部分的面積都是是15（即像素?cái)?shù)量），而對(duì)于9x9的Dxy模板來(lái)說(shuō)，突起部

5、分面積都是9，除以Sn的作用是對(duì)模板進(jìn)行歸一化處理；Wn表示第n個(gè)突起部分的權(quán)值；而后面的括號(hào)部分就是前面的公式，求模板的每個(gè)突起部分對(duì)應(yīng)于圖像四個(gè)點(diǎn)A、B、C、D所組成的矩陣區(qū)域的灰度之和。第8頁(yè)，共34頁(yè)。SURF 提取特征點(diǎn)快速Hessian加權(quán)系數(shù)Lxx是高斯模板與圖像卷積Dxx是盒子模板與圖像卷積用Dxx近似代替Lxx 如果行列式的結(jié)果符號(hào)為負(fù)，則特征值有不同的符號(hào)，則不是局部極值點(diǎn)。 如果行列式的符號(hào)為正，則該行列式的兩個(gè)特征值同為正或負(fù)，所以該點(diǎn)可以歸類為極值點(diǎn)。Hessian矩陣的行列式的極值處即為特征點(diǎn)而盒裝濾波器代替高斯二階微分算子要加一定的權(quán)值w，作用是平衡因近似所帶來(lái)的

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

7、9 15 21 27 15 27 39 51 27 51 75 99 51 99 147 195 變化量 n*6變化量6*nScaleOctaves第11頁(yè)，共34頁(yè)。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個(gè)點(diǎn)的響應(yīng)值都大的點(diǎn)才被選為興趣點(diǎn)。最后進(jìn)行插值精確。第12頁(yè)，共34頁(yè)。特征點(diǎn)方向分配 為了保證旋轉(zhuǎn)不變性，需要對(duì)每一個(gè)特征點(diǎn)分配一個(gè)主要方向。需要以特征點(diǎn)為中心，以6s（s為特征點(diǎn)的尺度）為半徑的圓形區(qū)域內(nèi)，對(duì)圖像進(jìn)行Haar小波響應(yīng)運(yùn)算。這樣做

8、實(shí)際就是對(duì)圖像進(jìn)行了梯度運(yùn)算，但是利用積分圖像，可以提高計(jì)算圖像梯度的效率。為了求取主方向值，需要設(shè)計(jì)一個(gè)以方向?yàn)橹行?，張角為PI/3的扇形滑動(dòng)窗口，以步長(zhǎng)為0.2弧度左右，旋轉(zhuǎn)這個(gè)滑動(dòng)窗口，并對(duì)窗口內(nèi)的圖像Haar小波的響應(yīng)值進(jìn)行累加。 主方向?yàn)樽畲蟮腍aar響應(yīng)累加值對(duì)應(yīng)的方向 。 旋轉(zhuǎn)窗口1.7.特征點(diǎn)方向分配第13頁(yè)，共34頁(yè)。1.8生成特征描述符生成特征描述符 生成特征點(diǎn)的特征描述符需要計(jì)算圖像的Haar小波響應(yīng)。在一個(gè)矩形的區(qū)域內(nèi)，以特征點(diǎn)為中心，沿主方向?qū)?0s*20s的圖像劃分成4*4個(gè)子塊，每個(gè)子塊利用尺寸2s的Haar小波模板進(jìn)行響應(yīng)計(jì)算，然后對(duì)響應(yīng)值進(jìn)行統(tǒng)計(jì) ， ， ，

9、形成的特征矢量 。 主方向5s*5s旋轉(zhuǎn)到主方向Hear小波模板第14頁(yè)，共34頁(yè)。每個(gè)子塊中又有25個(gè)采樣像素，對(duì)于每個(gè)區(qū)域內(nèi)，我們需要累加所有25個(gè)采樣像素的dx和dy，這樣形成描述符的一部分，而為了把強(qiáng)度變化的極性信息也包括今描述符中，我們還需要對(duì)dx和dy的絕對(duì)值進(jìn)行累加。這樣每個(gè)區(qū)域就可以用一個(gè)4維特征矢量表示，把所有4x4子區(qū)域組合起來(lái)，就形成了一個(gè)64維特征矢量，即surf描述符。第15頁(yè)，共34頁(yè)。標(biāo)出特征點(diǎn)的圖像第16頁(yè)，共34頁(yè)。二.特征點(diǎn)匹配第17頁(yè)，共34頁(yè)。特征點(diǎn)匹配特征點(diǎn)匹配 步驟1. 在檢測(cè)特征點(diǎn)的過(guò)程中，計(jì)算了 Hessian 矩陣的行列式，與此同時(shí)，計(jì)算得到了

10、 Hessian 矩陣的跡，矩陣的跡為對(duì)角元素之和。 按照亮度的不同，可以將特征點(diǎn)分為兩種，第一種為特征點(diǎn)及其周?chē)∴徲虻牧炼缺缺尘皡^(qū)域要亮，Hessian 矩陣的跡為正；另外一種為特征點(diǎn)及其周?chē)∴徲虻牧炼缺缺尘皡^(qū)域要暗，Hessian 矩陣為負(fù)值。根據(jù)這個(gè)特性，首先對(duì)兩個(gè)特征點(diǎn)的 Hessian 的跡進(jìn)行比較。如果同號(hào)，說(shuō)明兩個(gè)特征點(diǎn)具有相同的對(duì)比度；如果是異號(hào)的話，說(shuō)明兩個(gè)特征點(diǎn)的對(duì)比度不同，放棄特征點(diǎn)之間后續(xù)的相似性度量。第18頁(yè)，共34頁(yè)。特征點(diǎn)匹配特征點(diǎn)匹配步驟2.對(duì)于兩個(gè)特征點(diǎn)描述符的相似性度量，我們采用歐式距離進(jìn)行計(jì)算： 式中，Xik表示待配準(zhǔn)圖中第 i 個(gè)特征描述符的第 k

11、個(gè)元素， Xjk是參考圖中第 j個(gè)特征描述子的第k 個(gè)元素，n表示特征向量的維數(shù)。第19頁(yè)，共34頁(yè)。 對(duì)于待配準(zhǔn)圖上的特征點(diǎn)，計(jì)算它到參考圖像上所有特征點(diǎn)的歐氏距離，得到一個(gè)距離集合。通過(guò)對(duì)距離集合進(jìn)行比較運(yùn)算得到小歐氏距離和次最小歐式距離。設(shè)定一個(gè)閾值，一般為 0.8，當(dāng)最小歐氏距離和次最小歐式距離的比值小于該閾值時(shí)，認(rèn)為特征點(diǎn)與對(duì)應(yīng)最小歐氏距離的特征點(diǎn)是匹配的，否則沒(méi)有點(diǎn)與該特征點(diǎn)相匹配。閾值越小，匹配越穩(wěn)定，但極值點(diǎn)越少。特征點(diǎn)匹配特征點(diǎn)匹配第20頁(yè)，共34頁(yè)。特征點(diǎn)匹配后圖像第21頁(yè)，共34頁(yè)。三.構(gòu)建透視矩陣完成拼接第22頁(yè)，共34頁(yè)。三.構(gòu)建透視矩陣完成拼接在參考圖像和待拼接圖像

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

13、分別為兩幅圖像的對(duì)應(yīng)點(diǎn)坐標(biāo)，可以看出，計(jì)算透視變換矩陣H，實(shí)質(zhì)上就是計(jì)算矩陣中的8個(gè)參數(shù)。將(3.1)模型的矩陣形式進(jìn)行改寫(xiě)，得到 （3.3）第24頁(yè)，共34頁(yè)。 （3.4） 對(duì)于所有的對(duì)應(yīng)點(diǎn)對(duì)，如果要確定8個(gè)未知參數(shù)，需要使下式的值達(dá)到最?。?（3.5）通過(guò)(3.3)式和(3.4)式可以知道，選取4組對(duì)應(yīng)點(diǎn)，就能夠計(jì)算出透視變換模型的8個(gè)參數(shù)，但是隨機(jī)選取的對(duì)應(yīng)點(diǎn)不一定就能夠得到模型的準(zhǔn)確參數(shù)，所以在求其最小值的過(guò)程中采用LevenbergMarguqrdt迭代非線性最小化方法對(duì)透視變換矩陣進(jìn)行求精。第25頁(yè)，共34頁(yè)。首先對(duì)于8個(gè)未知參數(shù)m，求偏導(dǎo)數(shù)，即： （3.6）式中的Di是(3.3）

14、和(3.4)式的分母，然后計(jì)算兩個(gè)矩陣A和b，其中A中的元素為： （3.7）第26頁(yè)，共34頁(yè)。 第27頁(yè)，共34頁(yè)。總結(jié)：采用這種變換矩陣的方法可以處理圖像之間存在平移、旋轉(zhuǎn)、縮放等變化條件下的拼接。第28頁(yè)，共34頁(yè)。四.圖像融合第29頁(yè)，共34頁(yè)。四：圖像融合通過(guò)圖像匹配將兩幅圖像變換到了同一坐標(biāo)系后，得到了兩幅圖像的拼接結(jié)果。但是，由于圖像采集所帶來(lái)的光照、視野等的差異，拼接好的兩幅圖片在相結(jié)合的部分會(huì)出現(xiàn)明顯的拼接縫隙，圖像融合技術(shù)就是為了去除這種拼接縫隙的有力工具。圖像融合應(yīng)當(dāng)滿足幾個(gè)方面的要求：首先，為了消除圖像的拼接縫隙，就必須采用一種漸變的方法來(lái)將拼接的縫隙部分像素轉(zhuǎn)變?yōu)閺牡谝桓眻D片漸變?yōu)榈诙鶊D片；其次，圖像的融合應(yīng)當(dāng)只針對(duì)于拼接的結(jié)合部分有效，對(duì)于圖像的其他部分不能夠產(chǎn)生影響；最后，融合算法在算法的復(fù)雜度上不能太高，不能影響了圖像拼接的整體速度。第30頁(yè)，共34頁(yè)。加權(quán)平均法對(duì)于重疊部分的像素值不是簡(jiǎn)單的疊加求平均值，而是先進(jìn)行加權(quán)后，再進(jìn)行疊加平均。假設(shè)現(xiàn)在有兩幅圖像中的重疊部分分別定義一個(gè)權(quán)值，取為d1和d2,并且d1和d2都滿足條件屬于（0，1