SURF算法介紹

1、蒙娜麗莎的圖像匹配一-SURF算法1.圖像匹配圖像匹配的概念圖像匹配成為計(jì)算機(jī)視覺(jué)和圖像處理中的一個(gè)重要技術(shù)。其方法思想就是根據(jù)己知的圖像在其他圖像中查找出含有己知圖像的過(guò)程。圖像匹配的架構(gòu)流程如圖1.1。該技術(shù)的研究涉及到許多相關(guān)的知識(shí)領(lǐng)域,如圖像預(yù)處理、圖像采樣、特征提取等,同時(shí)將計(jì)算機(jī)視覺(jué)、多維信號(hào)處理和數(shù)值計(jì)算等緊密結(jié)合在一起。圖像匹配技術(shù)還與圖像融合、圖像匹配等研究方向系系相關(guān),為圖像理解和圖像復(fù)原等相關(guān)領(lǐng)域的研究提供基礎(chǔ)。圖像匹配技術(shù)作為圖像處理的關(guān)鍵技術(shù)之一，在國(guó)防領(lǐng)域和醫(yī)學(xué)領(lǐng)域等得到匹配結(jié)采廣泛的研究和應(yīng)用2。如果在不同視角，或是不同時(shí)間，或是使用了不同的傳感器獲取到的兩幅或多

2、幅圖像間存在共同區(qū)域，如何尋找到圖像間的共同區(qū)域，就是圖像匹配需要解決的問(wèn)題。圖像匹配的算法組成圖像匹配技術(shù)的分支很多，對(duì)圖像匹配提出的構(gòu)架也是千姿百態(tài)，根據(jù)布朗提出了圖像匹配的組成要素，將圖像匹配的要素主要分為四個(gè)方面，分別是圖像的特征空間，為求取變換參數(shù)定義的搜索空間和搜索策略，圖像匹配的相似性度量。特征空間是指在待配圖像和參考圖像上提取到的一系列特征集合。將提取到的特征進(jìn)行描述后參與最后的匹配，因此特征選取的好壞直接影響匹配的可行性和匹配的效果。好的特征是滿足自動(dòng)匹配的前提，因此選取的特征一般包含圖像的關(guān)鍵信息，此類特征存在以下特性：首先，此類特征具有公有性、唯一性和顯著性，保證匹配的順

3、利進(jìn)行和匹配的精度；其次，此類特征具有多量性，而且分布合理，保證匹配的穩(wěn)定性。合理的特征空間會(huì)降低匹配算法的計(jì)算量，提高算法的性能。相似性度量是指評(píng)判待匹配圖像和參考圖像上特征的相似程度，它很大程度上決定了參與匹配的因素，一般采用某種代價(jià)函數(shù)或者是距離函數(shù)來(lái)進(jìn)行度量。好的相似性度量不僅可以減少算法的計(jì)算量，而且對(duì)于算法的匹配性能和魯棒性起著重要的作用。搜索空間為求取圖像變換參數(shù)的空間。它為圖像間可能存在的所有變換組合的空間。搜索空間的組成取決于圖像畸變的類型，而搜索空間的取值范圍取決于圖像畸變的強(qiáng)度。假如圖像間只存在平移和旋轉(zhuǎn)變換，那么搜索空間為簡(jiǎn)單的二維空間。假如圖像間存在扭曲變形，那么搜索

4、空間為復(fù)雜的三維甚至更高維的空間。搜索空間是為了使圖像間能夠?qū)ふ业阶顑?yōu)的變換參數(shù)而建立的空間，好的搜索空間能夠得到較準(zhǔn)確的變換參數(shù)。搜索策略是指在建立的搜索空間中，以一種方法來(lái)求取圖像間的變換參數(shù)，使變換參數(shù)達(dá)到最優(yōu)。可見(jiàn)搜索策略不僅影響到圖像變換參數(shù)的求取，而且對(duì)于匹配時(shí)間也具有很大的影響。一般來(lái)說(shuō)，一種好的搜索策略都是采用搜索精度和搜索時(shí)間來(lái)評(píng)判的。較為常用的搜索策略主要包括序貫判定、層次性搜索法、窮盡搜索法、松弛算法、樹與圖匹配搜索、動(dòng)態(tài)規(guī)劃、多尺度搜索算法等。每種搜索算法都是針對(duì)具體的應(yīng)用領(lǐng)域產(chǎn)生的，不同的方法具有不同的優(yōu)勢(shì)。針對(duì)不同的要求，選擇合適的搜索策略是非常重要的。圖像匹配的四

5、要素是密切相關(guān)的，而且每個(gè)要素對(duì)匹配的最終結(jié)果都有很大的影響。針對(duì)不同的匹配需求和匹配的具體應(yīng)用，匹配要素的選取各異。首先針對(duì)圖像的類型和具體的圖像特征建立合適的特征空間；根據(jù)圖像間的畸變類型和畸變強(qiáng)度建立合適的搜索空間；通過(guò)合適的搜索算法來(lái)計(jì)算相似性度量；從而得到最優(yōu)的變換參數(shù)。2.SURF算法SURF的全稱是Speed-uprobustfeatures（加速健壯特征），SURF算法是SIFT（Scale-invariantfeaturetransformation,尺度不變特征變換）算法的加速版，SURF算法可以在適中的條件下完成兩幅圖像中物體的匹配基本實(shí)現(xiàn)了實(shí)時(shí)處理。2.1.SIFT算法

6、在計(jì)算機(jī)領(lǐng)域的圖像處理希望可以和人類視覺(jué)一樣通過(guò)程序自動(dòng)找出兩幅圖像里面相同的景物，建立它們之間的對(duì)應(yīng)，SIFT（尺度不變特征）算法提供了一種解決方法，通過(guò)這個(gè)算法可以使得滿足一定條件下兩幅圖像中相同景物的某些點(diǎn)可以匹配起來(lái)。SIFT算法實(shí)現(xiàn)物體識(shí)別主要有三大工序，1、提取關(guān)鍵點(diǎn)；2、對(duì)關(guān)鍵點(diǎn)附加詳細(xì)的信息（局部特征）也就是所謂的描述器；3、通過(guò)兩方特征點(diǎn)（附帶上特征向量的關(guān)鍵點(diǎn)）的兩兩比較找出相互匹配的若干對(duì)特征點(diǎn)，也就建立了景物間的對(duì)應(yīng)關(guān)系。日常的應(yīng)用中，多數(shù)情況是給出一幅包含物體的參考圖像，然后在另外一幅同樣含有該物體的圖像中實(shí)現(xiàn)它們的匹配。兩幅圖像中的物體一般只是旋轉(zhuǎn)和縮放的關(guān)系，加上

7、圖像的亮度及對(duì)比度的不同，這些就是最常見(jiàn)的情形?；谶@些條件下要實(shí)現(xiàn)物體之間的匹配，SIFT算法的先驅(qū)及其發(fā)明者想到只要找到多于三對(duì)物體間的匹配點(diǎn)就可以通過(guò)射影幾何的理論建立它們的一一對(duì)應(yīng)。首先在形狀上物體既有旋轉(zhuǎn)又有縮小放大的變化，如何找到這樣的對(duì)應(yīng)點(diǎn)呢？于是他們的想法是首先找到圖像中的一些“穩(wěn)定點(diǎn)”，這些點(diǎn)是一些十分突出的點(diǎn)不會(huì)因光照條件的改變而消失，比如角點(diǎn)、邊緣點(diǎn)、暗區(qū)域的亮點(diǎn)以及亮區(qū)域的暗點(diǎn)，既然兩幅圖像中有相同的景物，那么使用某種方法分別提取各自的穩(wěn)定點(diǎn)，這些點(diǎn)之間會(huì)有相互對(duì)應(yīng)的匹配點(diǎn)，正是基于這樣合理的假設(shè)，SIFT算法的基礎(chǔ)是穩(wěn)定點(diǎn)。SIFT算法找穩(wěn)定點(diǎn)的方法是找灰度圖的局部最

8、值，由于數(shù)字圖像是離散的，想求導(dǎo)和求最值的操作都是使用濾波器，而濾波器是有尺寸大小的，使用同一尺寸的濾波器對(duì)兩幅包含有不同尺寸的同一物體的圖像求局部最值將有可能出現(xiàn)一方求得最值而另一方卻沒(méi)有的情況，但是容易知道假如物體的尺寸都一致的話它們的局部最值將會(huì)相同。SIFT的精妙之處在于采用圖像金字塔的方法解決這一問(wèn)題，我們可以把兩幅圖像想象成是連續(xù)的，分別以它們作為底面作四棱錐，就像金字塔，那么每一個(gè)截面與原圖像相似，那么兩個(gè)金字塔中必然會(huì)有包含大小一致的物體的很多截面，但應(yīng)用只能是離散的，所以我們只能構(gòu)造有限層，層數(shù)越多當(dāng)然越好，但處理時(shí)間會(huì)相應(yīng)增加，層數(shù)太少不行，因?yàn)橄蛳虏蓸拥慕孛嬷锌赡苷也坏匠?/p>

9、寸大小一致的兩個(gè)物體的圖像。有了圖像金字塔就可以對(duì)每一層求出局部最值，但是這樣的穩(wěn)定點(diǎn)數(shù)目將會(huì)十分可觀，所以需要使用某種方法抑制去除一部分點(diǎn)，但又使得同一尺度下的穩(wěn)定點(diǎn)得以保存。有了穩(wěn)定點(diǎn)之后如何去讓程序明白它們之間是物體的同一位置？研究者想到以該點(diǎn)為中心挖出一小塊區(qū)域，然后找出區(qū)域內(nèi)的某些特征，讓這些特征附件在穩(wěn)定點(diǎn)上，SIFT的又一個(gè)精妙之處在于穩(wěn)定點(diǎn)附加上特征向量之后就像一個(gè)根系發(fā)達(dá)的樹根一樣牢牢的抓住它的“土地”，使之成為更穩(wěn)固的特征點(diǎn)，但是問(wèn)題又來(lái)了，遇到旋轉(zhuǎn)的情況怎么辦？發(fā)明者的解決方法是找一個(gè)“主方向”然后以它看齊，就可以知道兩個(gè)物體的旋轉(zhuǎn)夾角了。SURF算法步驟2.2.1.特征

10、點(diǎn)檢測(cè)特征點(diǎn)的檢測(cè)一般包括三個(gè)步驟，積分圖像的建立，箱式濾波器建立圖像的尺度空間，然后在建立的尺度空間上對(duì)特征點(diǎn)進(jìn)行定位。積分圖像的建立：SURF算法和其他算法相比不僅具有較好的縮放、旋轉(zhuǎn)、平移等特性，而且計(jì)算速度很快，計(jì)算速度的提升很大程度上取決于積分圖像的建立。積分圖像是對(duì)原始圖像進(jìn)行積分計(jì)算得到的圖像。積分圖像的每一點(diǎn)表示為原圖像從原點(diǎn)到該點(diǎn)的矩形區(qū)域的像素和，積分圖像的建立之所以能夠加快計(jì)算速度，是因?yàn)槲覀儗?duì)整幅圖像進(jìn)行積分圖像遍歷后，原始圖像中的任一矩形區(qū)域的像素之和就可以通過(guò)加減運(yùn)算來(lái)完成，而與矩形的面積無(wú)關(guān)，矩形越大，節(jié)省的計(jì)算時(shí)間越多。SURF算法之所以能夠采用積分圖像來(lái)計(jì)算，

11、另外一個(gè)很重要的近似就是采用箱式濾波器來(lái)近似高斯核函數(shù)。箱式濾波器的引入使得卷積模板都是框狀模板，使用積分圖像來(lái)計(jì)算就大大減少了計(jì)算量，從而提高了算法的運(yùn)算效率。箱式濾波器建立尺度空間：SURF算法采用箱式濾波器來(lái)近似代替高斯核函數(shù)，使得卷積模板均由簡(jiǎn)單的矩形構(gòu)成。積分圖像的引入解決了矩形區(qū)域快速計(jì)算的問(wèn)題，箱式濾波器的近似極大提升了計(jì)算速度。箱式濾波器近似效果如圖1.2所示：圖1.2箱式濾波器箱式濾波器建立圖像的尺度空間：為了保證圖像匹配具有尺度不變性，需要對(duì)圖像進(jìn)行分層，建立圖像的尺度空間，然后在不同尺度的圖像上來(lái)尋找特征點(diǎn)。SURF算法尺度空間的建立是保持原始圖像大小不變，通過(guò)改變箱式濾

12、波器的大小來(lái)對(duì)原始圖像計(jì)算得到的積分圖像進(jìn)行濾波，從而形成圖像的尺度空間。采用箱式濾波器建立圖像的尺度空間如圖1.3所示：圖1.3尺度空間特征點(diǎn)定位：通過(guò)上面所述的尺度空間的建立，在得到圖像的尺度空間后，在尺度空間的每一層圖像上使用快速Hessian矩陣來(lái)檢測(cè)圖像的極值點(diǎn)。對(duì)于空間的任意一點(diǎn)(x,y),對(duì)應(yīng)尺度空間中的尺度為。，則Hessian矩陣的定義如下所示：H(x,o)=L(xo)L(xo)xxxyL(xo)L(xo)xyyy其中L(xo)、L(xo)、L(xo)是圖像上的點(diǎn)分別與高斯二階偏導(dǎo)數(shù)咒Xxyyy蘭迪，辺，蘭迪卷積的結(jié)果，其中g(shù)為高斯函數(shù)。3x2dxydy2為了減少計(jì)算量，此處

13、又做了一個(gè)近似，我們采用箱式濾波模板與原始輸入圖像的卷積記為2,Dxy,Dyy來(lái)分別代替Lxx,Lxy,Lyy，把9X9的初始箱式濾波器與。等于1.2的二階高斯偏導(dǎo)近似，Hessian矩陣的行列式計(jì)算可以近似表示為：Det(Hessian)=DxxDyy-CDxy)2其中權(quán)重系數(shù)e約為0.9.對(duì)于計(jì)算得到的Hessian矩陣，設(shè)定一個(gè)閾值，只有當(dāng)det(Hessian)大于這個(gè)閾值時(shí)，才進(jìn)行下一步的判定。對(duì)于進(jìn)行下一步判定的點(diǎn)，取該點(diǎn)的上下層中對(duì)應(yīng)3*3*3的立體鄰域來(lái)進(jìn)行非極大值抑制(Non-maximumsuppression)，只有比立體近鄰內(nèi)的26個(gè)響應(yīng)值都大的點(diǎn)才被選定為特征點(diǎn)。為了

14、在得到特征點(diǎn)的穩(wěn)定位置和尺度值，需要對(duì)尺度空間進(jìn)行插值，這樣就得到了特征點(diǎn)的位置值和特征點(diǎn)的尺度值。特征描述特征描述分為兩個(gè)步驟，首先求取特征點(diǎn)的主方向，這樣可以保證算法的旋轉(zhuǎn)不變性，然后將特征點(diǎn)的鄰域旋轉(zhuǎn)到主方向，對(duì)特征點(diǎn)進(jìn)行描述。主方向描述：為了使圖像的匹配具有旋轉(zhuǎn)不變性，引入了主方向的概念。主方向的計(jì)算是以特征點(diǎn)為中心，取特征點(diǎn)周圍半徑為6s(s為特征點(diǎn)所在的尺度值)的圓形區(qū)域，計(jì)算鄰域內(nèi)的像素點(diǎn)在x，y方向上的哈爾小波響應(yīng)值。對(duì)計(jì)算得到的響應(yīng)值按距離賦予一定的權(quán)值系數(shù)，繼而對(duì)加權(quán)后的響應(yīng)值進(jìn)行直方圖統(tǒng)計(jì)。統(tǒng)計(jì)從X軸開始，對(duì)圓形區(qū)域60度范圍內(nèi)的哈爾小波響應(yīng)值相加計(jì)算得到一個(gè)新的矢量。每

15、隔5度以同樣的方法計(jì)算矢量，遍歷整個(gè)圓形區(qū)域，可以得到72個(gè)新的矢量。我們選擇最長(zhǎng)的矢量方向作為該特征點(diǎn)的主方向。對(duì)于待匹配圖像和參考圖像，提取到圖像的特征后，獲得了特征的位置坐標(biāo)和尺度值。為了使特征點(diǎn)能夠匹配，必須對(duì)特征點(diǎn)進(jìn)行描述。好的描述可以提高圖像間的匹配率。SURF算法對(duì)于檢測(cè)到的特征點(diǎn)，以特征點(diǎn)為中心，選取中心點(diǎn)鄰域范圍內(nèi)20S*20S大小的區(qū)域，然后將區(qū)域的主方向旋轉(zhuǎn)到特征點(diǎn)的主方向。為了更好的利用圖像的空間信息，將20S*20S的區(qū)域分為4*4共16個(gè)子區(qū)域，這樣每個(gè)子區(qū)域的像素值大小為5S*5S。SURF算法通過(guò)統(tǒng)計(jì)像素點(diǎn)的哈爾小波響應(yīng)值來(lái)對(duì)特征點(diǎn)進(jìn)行描述，對(duì)于每個(gè)子區(qū)域，分別

16、計(jì)算每個(gè)像素點(diǎn)的哈爾小波在X方向和Y方向的響應(yīng)值，用數(shù)學(xué)表達(dá)分別表示為，dv。統(tǒng)計(jì)尤yTOC o 1-5 h z完所有的響應(yīng)值后，為了增強(qiáng)特征點(diǎn)對(duì)亮度變化的魯棒性和定位的準(zhǔn)確性，以特征點(diǎn)為中心對(duì)計(jì)算到的，dv進(jìn)行高斯加權(quán)（o二3.3s）。對(duì)于每一個(gè)區(qū)域，得尤y到了每個(gè)像素點(diǎn)經(jīng)過(guò)加權(quán)的哈爾小波在X方向和Y方向的響應(yīng)值d”和此，對(duì)區(qū)尤y域內(nèi)所有的像素點(diǎn)的響應(yīng)值進(jìn)行求和計(jì)算Ldx,dvo建立一個(gè)四維的特征向量：尤yv=，Xdy，Y|dJ，:），將16個(gè)子區(qū)域的向量分別加入到特征向量中，就形成了一個(gè)64（4*16）維的特征向量。為了使描述子具有亮度和尺度不變性，對(duì)描述子進(jìn)行歸一化處理。特征匹配特征描述

17、子生成后，首先通過(guò)Hessian矩陣的跡來(lái)進(jìn)行初始判斷，加快匹配的速度，然后采用歐式距離來(lái)度量?jī)蓚€(gè)特征向量的匹配。照亮度的不同，可以將特征點(diǎn)分為兩種，第一種為特征點(diǎn)及其周圍小鄰域的亮度比背景區(qū)域要亮；另外一種為特征點(diǎn)及其周圍小鄰域的亮度比背景區(qū)域要暗。對(duì)于第一種特征點(diǎn)，計(jì)算得到的Hessian矩陣的跡為正，而對(duì)于第二種特征點(diǎn)恰恰相反，它們計(jì)算得到的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ù)的相似性度量。這樣可以減少匹配所用時(shí)間，而且不會(huì)影響匹配的匹

18、配率。歐式距離的相似性度量：對(duì)于待匹配圖上的特征點(diǎn)，計(jì)算它到參考圖像上所有特征點(diǎn)的歐氏距離，得到一個(gè)距離集合。通過(guò)對(duì)距離集合進(jìn)行比較運(yùn)算得到最小歐氏距離和次最小歐式距離。設(shè)定一個(gè)閾值，當(dāng)最小歐氏距離和次最小歐式距離的比值小于該閾值時(shí)，認(rèn)為特征點(diǎn)與對(duì)應(yīng)最小歐氏距離的特征點(diǎn)是匹配的，否則沒(méi)有點(diǎn)與該特征點(diǎn)相匹配。閾值設(shè)定越小，匹配點(diǎn)對(duì)越少，但匹配更穩(wěn)定。SURF算法的編程首先編寫SURF描述子特征提取實(shí)現(xiàn)函數(shù)，可以分為五個(gè)步驟來(lái)實(shí)現(xiàn)，1計(jì)算積分圖；2計(jì)算hessian矩陣；3提取興趣點(diǎn)；4計(jì)算SURF描述子；5釋放積分圖。計(jì)算積分圖，在圖像空間的積分其實(shí)就是左右象素的加減法:計(jì)算hessian矩陣采用相應(yīng)的模板。提取興趣點(diǎn)，首先定義一個(gè)二維數(shù)組，賦給初值，用來(lái)建立一個(gè)對(duì)應(yīng)表。再進(jìn)行二重循環(huán)計(jì)算興趣點(diǎn)，計(jì)算每行每列是否極值，判斷極值的條件是1是否越界；2hessian行列式的值與閾值相比；3在一個(gè)矩形領(lǐng)域內(nèi)；如果存在大于改點(diǎn)的行列式的點(diǎn)，就判定不是極值。通過(guò)極值的判定，如果是興趣點(diǎn)，就進(jìn)行插值計(jì)算精確的坐標(biāo)。計(jì)算描述子：考慮圖像會(huì)存在傾斜的情況，所以首先要對(duì)圖像興趣點(diǎn)的主方向進(jìn)行計(jì)算。再計(jì)算harr特征，計(jì)算是根據(jù)積分圖來(lái)的。對(duì)每一對(duì)x,y,以x,y為中心，將圖像旋轉(zhuǎn)到主方