一文讀懂：圖像特征檢測(cè)算法！

1. 局部特征點(diǎn)

圖像特征提取是圖像分析與圖像識(shí)別的前提，它是將高維的圖像數(shù)據(jù)進(jìn)行簡(jiǎn)化表達(dá)最有效的方式，從一幅圖像的M × N × 3的數(shù)據(jù)矩陣中，我們看不出任何信息，所以我們必須根據(jù)這些數(shù)據(jù)提取出圖像中的關(guān)鍵信息，一些基本元件以及它們的關(guān)系。

局部特征點(diǎn)是圖像特征的局部表達(dá)，它只能反正圖像上具有的局部特殊性，所以它只適合于對(duì)圖像進(jìn)行匹配，檢索等應(yīng)用。對(duì)于圖像理解則不太適合。而后者更關(guān)心一些全局特征，如顏色分布，紋理特征，主要物體的形狀等。全局特征容易受到環(huán)境的干擾，光照，旋轉(zhuǎn)，噪聲等不利因素都會(huì)影響全局特征。相比而言，局部特征點(diǎn)，往往對(duì)應(yīng)著圖像中的一些線條交叉，明暗變化的結(jié)構(gòu)中，受到的干擾也少。

而斑點(diǎn)與角點(diǎn)是兩類局部特征點(diǎn)。斑點(diǎn)通常是指與周圍有著顏色和灰度差別的區(qū)域，如草原上的一棵樹或一棟房子。它是一個(gè)區(qū)域，所以它比角點(diǎn)的噪能力要強(qiáng)，穩(wěn)定性要好。而角點(diǎn)則是圖像中一邊物體的拐角或者線條之間的交叉部分。

2. 斑點(diǎn)檢測(cè)原理與舉例 2.1 LoG與DoH

斑點(diǎn)檢測(cè)的方法主要包括利用高斯拉普拉斯算子檢測(cè)的方法（LOG）,以及利用像素點(diǎn)Hessian矩陣（二階微分）及其行列式值的方法（DOH）。

LoG的方法已經(jīng)在斑點(diǎn)檢測(cè)這入篇文章里作了詳細(xì)的描述。因?yàn)槎S高斯函數(shù)的拉普拉斯核很像一個(gè)斑點(diǎn)，所以可以利用卷積來求出圖像中的斑點(diǎn)狀的結(jié)構(gòu)。

DoH方法就是利用圖像點(diǎn)二階微分Hessian矩陣：

Hessian矩陣行列式的值，同樣也反映了圖像局部的結(jié)構(gòu)信息。與LoG相比，DoH對(duì)圖像中的細(xì)長(zhǎng)結(jié)構(gòu)的斑點(diǎn)有較好的抑制作用。

無論是LoG還是DoH，它們對(duì)圖像中的斑點(diǎn)進(jìn)行檢測(cè)，其步驟都可以分為以下兩步：

1）使用不同的σ生成模板，并對(duì)圖像進(jìn)行卷積運(yùn)算；

2）在圖像的位置空間與尺度空間中搜索LoG與DoH響應(yīng)的峰值。

2.2 SIFT

詳細(xì)的算法描述參考：SIFT定位算法關(guān)鍵步驟的說明

2004年，Lowe提高了高效的尺度不變特征變換算法（SIFT）,利用原始圖像與高斯核的卷積來建立尺度空間，并在高斯差分空間金字塔上提取出尺度不變性的特征點(diǎn)。該算法具有一定的仿射不變性，視角不變性，旋轉(zhuǎn)不變性和光照不變性，所以在圖像特征提高方面得到了最廣泛的應(yīng)用。

該算法大概可以歸納為三步：1）高斯差分金字塔的構(gòu)建；2）特征點(diǎn)的搜索；3）特征描述。

在第一步中，它用組與層的結(jié)構(gòu)構(gòu)建了一個(gè)具有線性關(guān)系的金字塔結(jié)構(gòu)，讓我們可以在連續(xù)的高斯核尺度上查找特征點(diǎn)。它比LoG高明的地方在于，它用一階高斯差分來近似高斯的拉普拉斯核，大大減少了運(yùn)算量。

在第二步的特征點(diǎn)搜索中，主要的關(guān)鍵步驟是極值點(diǎn)的插值，因?yàn)樵陔x散的空間中，局部極值點(diǎn)可能并不是真正意義上的極值點(diǎn)，真正的極植點(diǎn)可以落在了離散點(diǎn)的縫隙中。所以要對(duì)這些縫隙位置進(jìn)行插值，然后再求極值點(diǎn)的坐標(biāo)位置。

第二步中另一關(guān)鍵環(huán)節(jié)是刪除邊緣效應(yīng)的點(diǎn)，因?yàn)橹缓雎阅切〥oG響應(yīng)不夠的點(diǎn)是不夠的，DoG的值會(huì)受到邊緣的影響，那些邊緣上的點(diǎn)，雖然不是斑點(diǎn)，但是它的DoG響應(yīng)也很強(qiáng)。所以我們要把這部分點(diǎn)刪除。我們利用橫跨邊緣的地方，在沿邊緣方向與垂直邊緣方向表現(xiàn)出極大與極小的主曲率這一特性。所以通過計(jì)算特征點(diǎn)處主曲率的比值即可以區(qū)分其是否在邊緣上。這一點(diǎn)在理解上可以參見Harris角點(diǎn)的求法。

最后一步，即為特征點(diǎn)的特征描述。特征點(diǎn)的方向的求法是需要對(duì)特征點(diǎn)鄰域內(nèi)的點(diǎn)的梯度方向進(jìn)行直方圖統(tǒng)計(jì)，選取直方圖中比重最大的方向?yàn)樘卣鼽c(diǎn)的主方向，還可以選擇一個(gè)輔方向。在計(jì)算特征矢量時(shí)，需要對(duì)局部圖像進(jìn)行沿主方向旋轉(zhuǎn)，然后再進(jìn)鄰域內(nèi)的梯度直方圖統(tǒng)計(jì)（4x4x8）。

2.3 SURF

詳細(xì)的算法描述參考：1. SURF算法與源碼分析、上 2. SURF算法與源碼分析、下

2006年，Bay和Ess等人基于SIFT算法的思路，提出了加速魯棒特征（SURF）,該算法主要針對(duì)于SIFT算法速度太慢，計(jì)算量大的缺點(diǎn)，使用了近似Harr小波方法來提取特征點(diǎn)，這種方法就是基于Hessian行列式（DoH）的斑點(diǎn)特征檢測(cè)方法。通過在不同的尺度上利用積分圖像可以有效地計(jì)算出近似Harr小波值，簡(jiǎn)化了二階微分模板的構(gòu)建，搞高了尺度空間的特征檢測(cè)的效率。

SURF算法在積分圖像上使用了盒子濾波器對(duì)二階微分模板進(jìn)行了簡(jiǎn)化，從而構(gòu)建了Hessian矩陣元素值，進(jìn)而縮短了特征提取的時(shí)間，提高了效率。其中SURF算法在每個(gè)尺度上對(duì)每個(gè)像素點(diǎn)進(jìn)行檢測(cè)，其近似構(gòu)建的Hessian矩陣及其行列式的值分另為：

其中D x x , D x y和D y y為利用盒子濾波器獲得的近似卷積值。如果c ( x , y , σ )大于設(shè)置的門限值，則判定該像素點(diǎn)為關(guān)鍵字。然后與SIFT算法近似，在以關(guān)鍵點(diǎn)為中心的3 × 3 × 3像素鄰域內(nèi)進(jìn)行非極大值抑制，最后通過對(duì)斑點(diǎn)特征進(jìn)行插值運(yùn)算，完成了SURF特征點(diǎn)的精確定位。

而SURF特征點(diǎn)的描述，則也是充分利用了積分圖，用兩個(gè)方向上的Harr小波模板來計(jì)算梯度，然后用一個(gè)扇形對(duì)鄰域內(nèi)點(diǎn)的梯度方向進(jìn)行統(tǒng)計(jì)，求得特征點(diǎn)的主方向。

3. 角點(diǎn)檢測(cè)的原理與舉例

角點(diǎn)檢測(cè)的方法也是極多的，其中具有代表性的算法是Harris算法與FAST算法。

這兩個(gè)算法我都有專門寫過博文來描述其算法原理。Harris角點(diǎn)和FAST特征點(diǎn)檢測(cè)。

3.1 Harris角點(diǎn)特征提取

Harris角點(diǎn)檢測(cè)是一種基于圖像灰度的一階導(dǎo)數(shù)矩陣檢測(cè)方法。檢測(cè)器的主要思想是局部自相似性/自相關(guān)性，即在某個(gè)局部窗口內(nèi)圖像塊與在各個(gè)方向微小移動(dòng)后的窗口內(nèi)圖像塊的相似性。

在像素點(diǎn)的鄰域內(nèi)，導(dǎo)數(shù)矩陣描述了數(shù)據(jù)信號(hào)的變化情況。假設(shè)在像素點(diǎn)鄰域內(nèi)任意方向上移動(dòng)塊區(qū)域，若強(qiáng)度發(fā)生了劇烈變化，則變化處的像素點(diǎn)為角點(diǎn)。定義2 × 2的Harris矩陣為：

其中，C x和C y分別為點(diǎn)x = ( x , y )在xx和y方向上的強(qiáng)度信息的一階導(dǎo)數(shù)，ω ( x , y )為對(duì)應(yīng)位置的權(quán)重。通過計(jì)算Harris矩陣的角點(diǎn)響應(yīng)值D來判斷是否為角點(diǎn)。其計(jì)算公式為：

其中，det和trace為行列式和跡的操作符，m是取值為0.04~0.06的常數(shù)。當(dāng)角點(diǎn)響應(yīng)值大于設(shè)置的門限，且為該點(diǎn)鄰域內(nèi)的局部最大值時(shí)，則把該點(diǎn)當(dāng)作角點(diǎn)。

3.2 FAST角點(diǎn)特征提取

基于加速分割測(cè)試的FAST算法可以快速地提取出角點(diǎn)特征。該算法判斷一個(gè)候選點(diǎn)p是否為角點(diǎn)，依據(jù)的是在一個(gè)像素點(diǎn)p為圓心，半徑為3個(gè)像素的離散化Bresenllam圓周上，在給定閾值t的條件下，如果在圓周上有n個(gè)連續(xù)的像素灰度值大于I ( p ) + t或小于I ( p ) ? t。

針對(duì)于上面的定義，我們可以用快速的方法來完成檢測(cè)，而不用把圓周上的所有點(diǎn)都比較一遍。首先比較上下左右四個(gè)點(diǎn)的像素值關(guān)系，至少要有3個(gè)點(diǎn)的像素灰度值大于I ( p ) + t或小于I ( p ) ? t，則p為候選點(diǎn)，然后再進(jìn)一步進(jìn)行完整的判斷。

為了加快算法的檢測(cè)速度，可以使用機(jī)器學(xué)習(xí)ID3貪心算法來構(gòu)建決策樹。這里需要說明的是，在2010年Elmar和Gregory等人提出了自適應(yīng)通用加速分割檢測(cè)（AGAST）算法，通過把FAST算法中ID3決策樹改造為二叉樹，并能夠根據(jù)當(dāng)前處理的圖像信息動(dòng)態(tài)且高效地分配決策樹，提高了算法的運(yùn)算速度。

4. 二進(jìn)制字符串特征描述子

可以注意到在兩種角點(diǎn)檢測(cè)算法里，我們并沒有像SIFT或SURF那樣提到特征點(diǎn)的描述問題。事實(shí)上，特征點(diǎn)一旦檢測(cè)出來，無論是斑點(diǎn)還是角點(diǎn)描述方法都是一樣的，可以選用你認(rèn)為最有效的特征描述子。

特征描述是實(shí)現(xiàn)圖像匹配與圖像搜索必不可少的步驟。到目前為止，人們研究了各種各樣的特征描述子，比較有代表性的就是浮點(diǎn)型特征描述子和二進(jìn)帽字符串特征描述子。

像SIFT與SURF算法里的，用梯度統(tǒng)計(jì)直方圖來描述的描述子都屬于浮點(diǎn)型特征描述子。但它們計(jì)算起來，算法復(fù)雜，效率較低，所以后來就出現(xiàn)了許多新型的特征描述算法，如BRIEF。后來很多二進(jìn)制串描述子ORB，BRISK，F(xiàn)REAK等都是在它上面的基礎(chǔ)上的改進(jìn)。

4.1 BRIEF算法

BRJEF算法的主要思想是：在特征點(diǎn)周圍鄰域內(nèi)選取若干個(gè)像素點(diǎn)對(duì)，通過對(duì)這些點(diǎn)對(duì)的灰度值比較，將比較的結(jié)果組合成一個(gè)二進(jìn)制串字符串用來描述特征點(diǎn)。最后，使用漢明距離來計(jì)算在特征描述子是否匹配。

BRIEF算法的詳細(xì)描述可以參考：BRIEF特征描述子

4.2 BRISK算法

BRISK算法在特征點(diǎn)檢測(cè)部分沒有選用FAST特征點(diǎn)檢測(cè)，而是選用了穩(wěn)定性更強(qiáng)的AGAST算法。在特征描述子的構(gòu)建中，BRISK算法通過利用簡(jiǎn)單的像素灰度值比較，進(jìn)而得到一個(gè)級(jí)聯(lián)的二進(jìn)制比特串來描述每個(gè)特征點(diǎn)，這一點(diǎn)上原理與BRIEF是一致的。BRISK算法里采用了鄰域采樣模式，即以特征點(diǎn)為圓心，構(gòu)建多個(gè)不同半徑的離散化Bresenham同心圓，然后再每一個(gè)同心圓上獲得具有相同間距的N個(gè)采樣點(diǎn)。

由于這種鄰域采樣模式在采樣時(shí)會(huì)產(chǎn)生圖像灰度混疊的影響，所以BRISK算法首先對(duì)圖像進(jìn)行了高斯平滑圖像。并且使用的高斯函數(shù)標(biāo)準(zhǔn)差σ i與各自同心圓上點(diǎn)間距成正比。

假設(shè)在( N 2 )個(gè)采樣點(diǎn)中任意選取一對(duì)采樣點(diǎn)( p i , p j )，其平滑后的灰度值分別為I ( p i , σ i )和I ( p j , σ j )，則兩點(diǎn)間的局部梯度為：

假設(shè)把所有采樣點(diǎn)對(duì)構(gòu)成的集合記為A，則

那么短距離采樣點(diǎn)對(duì)構(gòu)成的集合S以及長(zhǎng)距離采樣點(diǎn)構(gòu)成的集合L分別為：

其中，通常設(shè)置距離閾值為

δ m a x = 9.75 δ , δ m i n = 13.67 δ，其中δ為特征點(diǎn)的尺度。

由于長(zhǎng)距離采樣點(diǎn)對(duì)含有更多的特征點(diǎn)角度信息，且局部梯度相互抵消，所以可以在集合L中計(jì)算出特征點(diǎn)的特征模式方向?yàn)椋?/p>

然后將采樣模式圍繞特征點(diǎn)旋轉(zhuǎn)角度α = a r c t a n 2 ( g y , g x )，進(jìn)而特征描述子具有了旋轉(zhuǎn)不變性。

最后，在旋轉(zhuǎn)后的短距離采樣點(diǎn)集合S內(nèi)，對(duì)所有的特征點(diǎn)對(duì)( P i α , p j α )行像素灰度值比較，最終形成512比特的二進(jìn)制字符串描述子。

4.3 ORB算法

ORB算法使用FAST進(jìn)行特征點(diǎn)檢測(cè)，然后用BREIF進(jìn)行特征點(diǎn)的特征描述，但是我們知道BRIEF并沒有特征點(diǎn)方向的概念，所以O(shè)RB在BRIEF基礎(chǔ)上引入了方向的計(jì)算方法，并在點(diǎn)對(duì)的挑選上使用貪婪搜索算法，挑出了一些區(qū)分性強(qiáng)的點(diǎn)對(duì)用來描述二進(jìn)制串。ORB算法的詳細(xì)描述可以參考：ORB特征點(diǎn)檢測(cè)。

4.4 FREAK算法

Fast Retina KeyPoint，即快速視網(wǎng)膜關(guān)鍵點(diǎn)。

根據(jù)視網(wǎng)膜原理進(jìn)行點(diǎn)對(duì)采樣，中間密集一些，離中心越遠(yuǎn)越稀疏。并且由粗到精構(gòu)建描述子，窮舉貪婪搜索找相關(guān)性小的。42個(gè)感受野，一千對(duì)點(diǎn)的組合，找前512個(gè)即可。這512個(gè)分成4組，前128對(duì)相關(guān)性更小，可以代表粗的信息，后面越來越精。匹配的時(shí)候可以先看前16bytes，即代表精信息的部分，如果距離小于某個(gè)閾值，再繼續(xù)，否則就不用往下看了。

5. 應(yīng)用之圖像匹配

圖像匹配的研究目標(biāo)是精確判斷兩幅圖像之間的相似性。圖像之間的相似性的定義又隨著不同的應(yīng)用需求而改變。例如，在物體檢索系統(tǒng)中（找出含有亞伯拉罕·林肯的臉的圖像），我們認(rèn)為同一物體的不同圖像是相近的。而在物體類別檢索系統(tǒng)中（找出含有人臉的圖像），我們則認(rèn)為相同類的物體之間是相近的。

這里局部特征點(diǎn)的應(yīng)用主要表現(xiàn)在第一種相似性上，也就是說我們需要設(shè)計(jì)某種圖像匹配算法來判斷兩幅圖像是否是對(duì)同一物體或場(chǎng)景所成的圖像。理想的圖像匹配算法應(yīng)該認(rèn)為兩幅同一物體的圖像之間相似度很高，而兩幅不同物體的圖像之間相似度很低，如下圖所示。

由于成像時(shí)光照，環(huán)境，角度的不一致，我們獲取的同一物體的圖像是存在差異的，如同上圖中的兩輛小車的圖像一樣，角度不同，成像就不同。我們直接利用圖像進(jìn)行比較是無法進(jìn)行判斷小車是否為同一類的。必須進(jìn)行特征點(diǎn)的提取，再對(duì)特征點(diǎn)進(jìn)行匹配。

圖像會(huì)存在哪些變換呢？一般來說包括了光照變化與幾何變化，光照變化表現(xiàn)是圖像上是全局或局部顏色的變化，而幾何變化種類就比較多了，可以是平移、旋轉(zhuǎn)、尺度、仿射、投影變換等等。所以我們?cè)谘芯烤植刻卣鼽c(diǎn)時(shí)才要求特征點(diǎn)對(duì)這些變化具有穩(wěn)定性，同時(shí)要有很強(qiáng)的獨(dú)特性，可以讓圖像與其他類的圖像區(qū)分性強(qiáng)，即類內(nèi)距離小而類間距離大。