反復(fù)將Speed-up Robust Feature 這篇文章看了幾遍，現(xiàn)在總算是撥開迷霧了，索性趕緊記錄一下~~
SURF，一種能進(jìn)行特征檢測(cè)與描述的方法，其主要的創(chuàng)新點(diǎn)在于基于積分圖進(jìn)行盒式濾波，相比于傳統(tǒng)的濾波方式，其計(jì)算量可以獨(dú)立于濾波器的尺寸，這一思想在論文中有兩處體現(xiàn)，一是構(gòu)建尺度空間金字塔時(shí)，保持原始圖像的尺寸不變，只改變?yōu)V波器的尺寸，用于特征點(diǎn)的檢測(cè)；二是在進(jìn)行Haar wavelet的時(shí)候，也是基于積分圖進(jìn)行卷積，用于形成特征描述子。需要注意的是，之所以可以在積分圖的基礎(chǔ)上進(jìn)行卷積操作，這與濾波器的類型有關(guān)，也就是濾波其需要是盒式濾波器，如圖1，2所示這類濾波其，這樣在計(jì)算時(shí)則只需利用各個(gè)頂點(diǎn)進(jìn)行兩次減法和一次加法再后再乘上對(duì)應(yīng)的系數(shù)即可。這種方式極大地提升了算法的運(yùn)行效率。
下面具體來說明SURF從特征點(diǎn)檢測(cè)到描述子形成以及快速匹配的具體方法:
1、特征點(diǎn)檢測(cè)：
文章利用每個(gè)像素點(diǎn)Hessian矩陣對(duì)應(yīng)的行列式的值作為每個(gè)像素點(diǎn)的強(qiáng)度響應(yīng)值大小，像素點(diǎn)的Hessian矩陣表示如下：
圖3 Hessian矩陣
可以看到，每個(gè)點(diǎn)的Hessian矩陣取決于利用對(duì)應(yīng)尺度sigma進(jìn)行二階高斯卷積（Laplacian卷積）操作后各個(gè)方向上的值構(gòu)成，但是gaussian卷積的缺點(diǎn)在于在構(gòu)建尺度空間時(shí)不夠魯棒，為此作者進(jìn)行了一個(gè)近似用盒式濾波器（如圖1）來代替二階高斯濾波器（如圖4）：
之后利用該濾波器對(duì)原圖像（灰度圖像）進(jìn)行卷積操作，以構(gòu)建尺度空間金字塔，其構(gòu)建方式為：只改變?yōu)V波器的尺寸，原圖像尺寸不變，不同于SIFT中尺度空間的構(gòu)建方式，即：下層的輸出結(jié)果需要依賴上層的圖像，SURF的這種方式可以很好地實(shí)現(xiàn)并行化操作，即每張圖像的操作可以同時(shí)進(jìn)行，以此極大地提升效率。如圖5所示：
同SIFT類似，該尺度空間也分為若干octave，每個(gè)octave中有若干層，需要注意的是，每個(gè)octave中的實(shí)際層數(shù)為原有層數(shù)+2，用于在進(jìn)行上下層極值的比較，這與SIFT中的+3是同一個(gè)思想。同時(shí)，為了加速，不同組濾波時(shí)的步伐間隔的關(guān)系可以設(shè)置為2倍的關(guān)系，即第一個(gè)octave的step=1，第二個(gè)octave的step=2，第三個(gè)octave的step=4……，每個(gè)octave中每層的step相同。每一層的box filter的尺寸的關(guān)系為：
每個(gè)size下對(duì)應(yīng)與Gaussian卷積中的一個(gè)sigma，其對(duì)應(yīng)關(guān)系為：1.2x（L/9）,其中L為濾波器的size，故有9x9對(duì)應(yīng)的s=1.2; 如下圖6所示：
分別利用x，y和xy三個(gè)方向的盒式濾波器進(jìn)行卷積后，即可得到該點(diǎn)對(duì)應(yīng)的Hessian矩陣，由此可以求出該Hessian矩陣對(duì)應(yīng)的行列式作為該像素點(diǎn)的響應(yīng)值：
之所以有0.9這個(gè)系數(shù)，是為了平衡盒式濾波近似帶來的誤差。
需要說明的時(shí)，隨著octave的增加，越高層次的octave其能檢測(cè)得到的特征點(diǎn)數(shù)會(huì)明顯減少。
構(gòu)建完成尺度空間金字塔后，與SIFT中隊(duì)DoG結(jié)構(gòu)進(jìn)行相鄰三層的局部非極大值抑制相同，比較某點(diǎn)上下相鄰的26個(gè)點(diǎn)的Hessian行列式的值，若該點(diǎn)的值大于一個(gè)閾值且是局部最大值，則該點(diǎn)為特征點(diǎn)。
2、特征點(diǎn)描述子生成
在SIFT中，是通過統(tǒng)計(jì)特征點(diǎn)鄰域的梯度信息來得到特征點(diǎn)的向量描述子，在SURF中則是通過Haar小波的方式得到x，y方向上的信息進(jìn)行統(tǒng)計(jì)。
特征點(diǎn)主方向確定：首先，以特征點(diǎn)為中心，以6s為半徑（s為該特征點(diǎn)所在曾的scale）的區(qū)域?yàn)樵撎卣鼽c(diǎn)的鄰域，以s為濾波步伐，通過Haar小波濾波器（長(zhǎng)度為4s）（如圖2）在積分圖上進(jìn)行卷積操作，之后以特征點(diǎn)為中心，為了增加魯棒性，利用Gaussian濾波（sigma=2s）確定每個(gè)點(diǎn)所對(duì)應(yīng)的權(quán)重。之后，以某一角度（默認(rèn)為pi/3）的扇形區(qū)域，計(jì)算各點(diǎn)Harr小波dx，dy之和作為該扇形區(qū)域內(nèi)的方向，以這個(gè)角度的扇形區(qū)域?yàn)榇翱趯?duì)整個(gè)原型區(qū)域進(jìn)行掃描，得到對(duì)應(yīng)窗口下的方向，則特征點(diǎn)的方向即為這些窗口對(duì)應(yīng)的方向中最大的那一個(gè)。如圖7：
注：文中說明了，很多情況下圖像時(shí)不需要考慮特征的旋轉(zhuǎn)不變情況的，所以在生成特征點(diǎn)描述子時(shí)可以忽略到上面特征點(diǎn)主方向的確定這一步，即為U-SURF(upright-SURF)。
描述子生成：在確定了特征點(diǎn)的主方向后，下面就是生成描述子（即該點(diǎn)的特征向量），以特征點(diǎn)為中心，在垂直于主方向的方向構(gòu)建一個(gè)矩形區(qū)域（大小為20s），將該區(qū)域劃分成4x4的子區(qū)域，對(duì)每個(gè)區(qū)域計(jì)算（5x5個(gè)）點(diǎn)的Harr小波（size=2s）響應(yīng)值，統(tǒng)計(jì)得到每個(gè)子區(qū)域的四個(gè)特征量，如下圖8所示（圖右側(cè)是以2x2個(gè)點(diǎn)為例進(jìn)行說明）：
同樣地，為了增加魯棒性，所計(jì)算的dx，dy的值也會(huì)以特征點(diǎn)為中心，通過Gaussian（sigma=3.3s）來賦予一定的權(quán)重。于此，便可以生成一個(gè)大小為：4x4x4=36維度大小的特征向量?？梢酝ㄟ^改變子區(qū)域的大小改變特征點(diǎn)描述子的大小，如：3x3x4=36。
注：利用Harr小波響應(yīng)相對(duì)于梯度信息的響應(yīng)，其優(yōu)點(diǎn)在于SURF是結(jié)合了子帶的梯度信息而非某個(gè)點(diǎn)的單獨(dú)梯度信息，因而其更魯棒，也更穩(wěn)定。
3、快速配準(zhǔn)
文中提出了通過像素點(diǎn)Hessian矩陣的跡（即Laplacian濾波后的符號(hào)——對(duì)比度信息）來作為檢測(cè)blob的匹配信息，若兩幅圖上特征點(diǎn)的跡值不同，則可以明確地確定這兩個(gè)特征點(diǎn)不能配對(duì)，由此只需要通過對(duì)跡值相同的特征點(diǎn)進(jìn)行匹配即可，又一次提升了算法效率。如下圖9所示：
至此，便完成了整個(gè)SURF特征檢測(cè)及特征描述子生成的步驟，可以看到，這個(gè)方法極大地提升了效率同時(shí)能夠產(chǎn)生魯棒的特征信息。另外需要注意的是，在構(gòu)建金字塔時(shí)，隨著octave數(shù)的增加，特征點(diǎn)會(huì)明顯減少，所以在自己利用該方法進(jìn)行試驗(yàn)時(shí)，可以增加通過增加層數(shù)減少octave數(shù)的方法來找到更多的特征點(diǎn)。
