局部特征(1)——入門篇

????局部特征?（local features），是近來研究的一大熱點。大家都了解全局特征（global features），就是方差、顏色直方圖等等。如果用戶對整個圖像的整體感興趣，而不是前景本身感興趣的話，全局特征用來描述總是比較合適的。但是無法分辨出前景和背景卻是全局特征本身就有的劣勢，特別是在我們關注的對象受到遮擋等影響的時候，全局特征很有可能就被破壞掉了。而所謂局部特征，顧名思義就是一些局部才會出現的特征，這個局部，就是指一些能夠穩定出現并且具有良好的可區分性的一些點了。這樣在物體不完全受到遮擋的情況下，一些局部特征依然穩定存在，以代表這個物體（甚至這幅圖像），方便接下來的分析。我們可以看下面這個圖，左邊一列是完整圖像，中間一列是一些角點（就是接下來我們要講的局部特征），右邊一列則是除去角點以外的線段。不知道你會不會也覺得你看中間一列的時候能更敏感地把他們想象成左邊一列的原始物品呢？一方面說，如果我們用這些穩定出現的點來代替整幅圖像，可以大大降低圖像原有攜帶的大量信息，起到減少計算量的作用。另一方面，當物體受到干擾時，一些冗余的信息（比如顏色變化平緩的部分和直線）即使被遮擋了，我們依然能夠從未被遮擋的特征點上還原重要的信息。

??? 把局部特征說的這么好聽，你也許會問怎樣的特征能夠被當做局部特征點呢？我們不妨來看下面的這幅圖：

??? 我們選擇了3個部分：邊緣的點、邊緣的線、變化緩慢的天空，當我在左邊的圖像中選擇哪個部分的時候，你最有可能從右邊的圖像中找到對應的部分來呢？很顯然是邊緣的點吧-------天空，那么多都是一樣的；而邊緣，一條直線往左看往右看都是差不多的，你讓我選哪個點（這也叫做aperture problem）；而頂點相比之下更具有唯一性，所以局部特征最初的研究也就是從角點開始的（比如Harris Corner）。

??? 一種定量的檢測方法，就是通過SSD去比較兩個塊區域以定義一個相似度，值越小，兩個塊越相似：

??? 當然我們應該知道，檢測出的塊應該和周圍有一定的區分性，如何體現這種區分性，不妨做個試驗：當前塊和它的鄰域做匹配，顯然自己和自己匹配的時候值最小，而如果周圍一定范圍的值都特別小，那我們豈不是自己和自己都無法找到匹配，那還拿他當特征干啥？所以如果下式有明顯極值，就可以把它當做特征點了。（式中的Δu表示當前塊與比較鄰域之間的位移）

??? 這個過程就是早期的Harris Corner的核心思想(如果讀者想了解Harris Corner的具體細節，請參見該系列的下一篇博客)。

??? 總結一下，好的特征應該具有以下幾個特點：

?????? 1、重復性：不同圖像相同的區域應該能被重復檢測到，而且不受到旋轉、模糊、光照等因素的影響；

?????? 2、可區分性：不同的檢測子，應該可以被區分出來，而為了區分它們，應運而生的就是與檢測對應的描述子了；

?????? 3、數量適宜：檢測子可別太多，不然啥阿貓阿狗都能出來混，但也不能太少，要求太高可就招不到人才了；

?????? 4、高定位（尺度和位置）：是在哪出現的，最好就在哪被找到，可別跑偏了；

???????5、有效性：檢測速度越快越好。

??? 在接下來的幾篇文章里，我主要針對局部特征，特別是目前使用的特別火熱的SIFT特征和SURF特征進行一些描述和總結。這兩個特征都是魯棒性特別好的局部特征，被廣泛應用在模式識別方面。

? ? 關于局部特征的更多介紹，請見http://download.csdn.net/download/jiang1st2010/4343689?，下載ppt查看（免積分）。

?

局部特征(2)——Harris角點

??在入門篇中偶爾談到了Harris Corner，在這里我們就重點聊一聊Harris Corner。

???????Harris Corner是最典型的角點檢測子Corner Detector。角點經常被檢測在邊緣的交界處、被遮擋的邊緣、紋理性很強的部分。滿足這些條件一般都是穩定的、重復性比較高的點，所以實際上他們是不是角點并不重要（因為我們的目標就是找一些穩定、重復性高的點以作為特征點）。

Harris Corner基于二階矩陣：

這個矩陣描述了局部鄰域內梯度的分布情況。矩陣的兩個特征值可以用來描述兩個主要方向上信號的變化，因此特征值可以用來判決是否為特征點。Harris采用的判別方法是：

顯而易見，cornerness的值越大，對應的兩個特征值都應該很大，其中λ取0.04，是為了抑制比較明顯的直線。最后對整幅圖像得到的cornerness做一個非極大抑制，得到最后的特征點。Harris角點具有的優點是平移不變、旋轉不變，能克服一定光照變化。可以先從一個例子上觀察Harris Corner實現的過程：

現在有幾個問題：首先為什么3.1式矩陣的兩個特征值可以用來描述兩個主要方向上信號的變化；另外一個問題是為什么3.4式用來決定是否為角點。

要知道為什么3.1可以作為這個矩陣，我們了解一下具體怎么推出這個式子的，那這又要從Moravec算子說起，步驟如下：

0）將要判斷的點置于一個3*3或5*5的圖像塊的中心，如下圖用紅色的線環繞的圖像塊。

1）將紅色的框朝8個方向移動一格，得到藍色的框（下圖為向右上角移動）。導致一個缺點：響應是各向異性的（啥意思？）

2）將紅色的框和藍色的框的相同坐標值的點的像素值相減，并求平方和，可以得到8個值。

3）將8個值中的最小的值作為角點像素的變化值。（因為角點應該在x、y方向上變化都比較大；而在邊緣上只可能一個方向大、另一個方向小）

4）求出每一個像素點的角點像素變化值，在局部圖像塊中，該值最大的點為角點。

Harris算子將Moravec算子做了兩個推廣：

1）用像素的變化梯度代替像素值相減并引入高斯窗函數（舉個x方向上變化的例子為證）。

引入高斯窗是為了濾除噪聲的干擾。

?[-1,0,1]:x方向上的偏導，[-1,0,1]T:y方向上的偏導。

2）推廣出了一個公式這樣可以計算任意方向上的像素值變化，而不在是8個固定的方向。

（這里的u、v表示x/y方向的位移）

因為Vuv（x,y）的最小值才是這個點需要被考慮的值，因此我們重寫以上表達式：

看到M矩陣的形式了么？這就是Harris算子的那個原始矩陣，我想推到這里，你也就應該了解Harris矩陣為什么是這樣子的了。

第二個問題：為什么3.4可以用來描述是否為角點。

可以參考這樣一個圖：描述了不同紋理下α和β的取值情況：

a)沒有什么紋理的情況下，兩個值都很小（很小的正值）

b)邊緣的點，一個值大，另外一個值小（由于k取了很小的值，所以3.4的結果為一個小負值）

c)角點：兩個值都比較大（比較大的正值）

這樣，當我們把目標函數定義為3.4式的時候，得到的結果就會盡力滿足兩個特征值都比較大了。當然，除此之外，還有Harmonic mean等方式實現更理想的組合方式達到檢測出的兩個特征值都盡可能大。

檢測效果圖（右圖進行了旋轉）

局部特征(3)——SURF特征總結

第一部分：興趣點的檢測

?

1、 建立積分圖。

優點：任何一個垂直矩形區域的面積只需要進行3次 +/-法就能計算。一階的haar小波響應只要5次+/-法就能計算。計算的時間和區域大小無關。

?

2、 建立圖像的尺度空間(應該分別有Dxx、Dxy、Dyy 三個尺度金字塔)：

用box filters代替二階高斯差分模板。

保持圖像的大小不變，對box filters進行尺度變換：建立高斯金字塔，金字塔分為多個Octaves，每個Octave分為4個Scale levels。第一級的Octave的模塊大小為9、15、21、27（相差6），第二級為15、27、39、51（相差12），第三級為27、51、75、99（相差24）。每一級第一個level的大小為上一級第二個level的大小。繼續建立高斯金字塔，直到filter的大小大于原圖像的大小為止（問題是大于每一Octave的第一個mask大小還是最后一個mask的大小？）。

?

尺度變換的方法，與每個Octave第一個scale level的size（L）/3有關，例如第一個Octave的L為9，L/3=9/3=3，則對于每行/列，連續出現L/3個相同的值，則再插入2個相同的值。若某連續3行同時為1，則再插入兩行0。若只連續1行為1，則1*（2/3）=1（四舍五入）。插入的行/列要求左右/上下對稱。

?

3、 對于尺度空間中的每一個box filter，與圖像卷積，計算每一點上的D_xx、D_yy、D_xy，再計算每一點Hessian矩陣的行列式。（卷積可以用積分圖實現快速計算。）

? ? ?

其中w是因為box filters只是高斯二階差分的近似，為了使行列式的值大致相等，乘以這個權值，取0.9。注意，每Octave提高一級，計算行列式的時候，采樣的間隔提高一倍。例如第一個Octave，每個點都計算，到了第二個Octave，隔一個點計算一個……（用增大模板大小，對圖像上的點采樣計算的方法，等同于實現對圖像進行下采樣并改變模板尺度的大小。）

對于每一個Octave，對計算出行列式的值設一個閾值，大于該閾值的列為候選興趣點。對候選極值點進行非極大抑制：對于該level的周圍8個點以及上下scale level相應位置的9*2個點，一共26個點進行比較行列式的大小，若該點是周圍26個點中行列式最大的，則保留。（每一個Octave的頭尾兩個scale level是沒法計算的。）

為什么可以用Hessian矩陣來判斷極小值/極大值，請見最后。?

最后，內插子像素精確定位（具體未看）。

?

第二部分：特征描述子

?

1、 主方向的確定（U-Surf沒有此步驟）

s = 當前mask大小 * 1.2 / 9

以興趣點為中心，確定6s為半徑的圓。對圓內以s為步長的采樣點計算haar小波響應（邊長為4s）。

以興趣點為中心，對小波響應進行高斯加權（）。對一個扇形區間（比如π/3）的水平和垂直方向的小波響應分別求和。最長矢量對應的扇形方向就是主方向。（每一個扇形窗可否有重復？）

?

2、 以興趣點為中心，主方向為參考x軸方向，20s為邊長，做正方形區域，并將該區域分為4*4個子區域。（SURF-36把它分為3*3個子區域，區分性略差但速度快。）每個子區域取5*5個采樣點，計算這些采樣點上的haar小波響應dx和dy。以興趣點為中心，對響應進行高斯加權（σ=3.3s）。

?

3、 對每個子區域的dx、dy、|dx|、|dy|進行求和，歸一化為單位向量。對于4*4個子塊一共可以構成64維空間。（SURF-128在統計dx和|dx|時，把dy分為大于0時候和小于0時候兩種情況，而在統計dy和|dy|時將dx分為大于0和小于0兩種情況，這樣每個子區域是8維向量）。

附：最近的思考（2011.7.10補充）：

1、為什么Hessian矩陣可以用來判斷極大值/極小值

我的理解如下：

在x0點上，hessian矩陣是正定的，且各分量的一階偏導數為0，則x0為極小值點。

在x0點上，hessian矩陣是負定的，且各分量的一階偏導數為0，則x0為極大值點。

對于某個局部區域，若hessian矩陣是半正定的，則這個區域是凸的（反之依然成立）；若負定，則這個區域是凹的（反之依然成立）。而對于正定和負定來說，Hessian矩陣的行列式總是大于等于0的。反過來就是說：某個點若是極大值/極小值，hessian矩陣的行列式必然要大于等于0，而大于等于0如果是滿足的，這個點不一定是極大值/極小值（還要判斷一階導數）。所以后面還要進行極大值抑制。

與SURF相關的局部特征是SIFT，已經有很多專家對它討論過了，這里我也不再多談，如果大家對它感興趣的話，請看這里，而接下來的這篇博客則對SIFT和SURF做了比較

局部特征(4)——SIFT和SURF的比較

(轉載請注明來源： http://blog.csdn.net/jiang1st2010/article/details/6567452)

共同點：

SIFT/SURF為了實現不同圖像中相同場景的匹配，主要包括三個步驟：

1、尺度空間的建立；

2、特征點的提取；

3、利用特征點周圍鄰域的信息生成特征描述子

4、特征點匹配。

? ? ? 從博客上看到一片文章，http://blog.csdn.net/cy513/archive/2009/08/05/4414352.aspx，這一段的大部分內容源于這篇文章，推薦大家去看看。

? ? ? 如果兩幅圖像中的物體一般只是旋轉和縮放的關系，加上圖像的亮度及對比度的不同，要在這些條件下要實現物體之間的匹配，SIFT算法的先驅及其發明者想到只要找到多于三對物體間的匹配點就可以通過射影幾何的理論建立它們的一一對應。

? ? ? 如何找到這樣的匹配點呢？SIFT/SURF作者的想法是首先找到圖像中的一些“穩定點”，這些點是一些特殊的點，不會因為視角的改變、光照的變化、噪音的干擾而消失，比如角點、邊緣點、暗區域的亮點以及亮區域的暗點。這樣如果兩幅圖像中有相同的景物，那么這些穩定點就會在兩幅圖像的相同景物上同時出現，這樣就能實現匹配。因此，SIFT/SURF算法的基礎是穩定點。

? ? ? SIFT/SURF提取的穩定點，首先都要求是局部極值。但是，當兩個物體的大小比例不一樣時，大圖像的局部極值點在小圖像的對應位置上有可能不是極值點。于是SIFT/SURF都采用圖像金字塔的方法，每一個截面與原圖像相似，這樣兩個金字塔中就有可能包含大小最近似的兩個截面了。

? ? ? 這樣找到的特征點會比較多，經過一些處理后濾掉一些相對不穩定的點。

? ? ? 接下來如何去匹配相同物體上對應的點呢？SIFT/SURF的作者都想到以特征點為中心，在周圍鄰域內統計特征，將特征附加到穩定點上，生成特征描述子。在遇到旋轉的情況下，作者們都決定找出一個主方向，然后以這個方向為參考坐標進行后面的特征統計，就解決了旋轉的問題。

?

共同的大問題有以下幾個：

1、為什么選用高斯金字塔來作特征提取？

? ? ? 為什么是DOG的金字塔？因為它接近LOG，而LOG的極值點提供了最穩定的特征，而且DOG方便計算（只要做減法。）

? ? ? 為什么LOG的極值點提供的特征最穩定，有參考文獻，未看。

???? (7.12補充：)直觀理解：特征明顯的點經過不同尺度的高斯濾波器進行濾波后，差別較大，所以用到的是DOG。

? ? ? 但是直觀上怎么理解？如果相鄰Octave的sigma不是兩倍關系還好理解：如果兩幅圖像只是縮放的關系，那么假設第一個Octave找到了小一倍圖像的極值點，那么大一倍圖像的極值點會在下一個Octave找到相似的。但是現在，如果把大一倍圖像進行一次下采樣（這樣和小的圖像就完全一樣了），進行Gauss濾波時，兩個圖像濾波系數（sigma）是不一樣的，不就找不到一樣的極值點了么？不理解。

2、Hessian矩陣為什么能用來篩選極值點？

? ? ? SIFT先利用非極大抑制，再用到Hessian矩陣進行濾除。SURF先用Hessian矩陣，再進行非極大抑制。SURF的順序可以加快篩選速度么？（Hessian矩陣濾除的點更多？）

? ? ? 至于SURF先用Hessian矩陣，再進行非極大抑制的原因，是不管先極大值抑制還是判斷Hessian矩陣的行列式，金字塔上的點的行列式都是要計算出來的。先判斷是否大于0只要進行1次判斷，而判斷是否是極大值點或者極小值點要與周圍26個點比較，只比較1次肯定快。

? ? ? 而在SIFT中，構建的高斯金字塔只有一座（不想SURF是有3座），要進行非極大抑制可以直接用金字塔的結果進行比較。而如果計算Hessian矩陣的行列式，還要再計算Dxx、Dxy、Dyy。因此先進行非極大抑制。這兩個步驟的先后與SIFT/SURF的實際計算情況有關的，都是當前算法下的最佳順序，而不是說哪種先計算一定更好。

3、為什么采用梯度特征作為局部不變特征？

? ? ? 這與人的視覺神經相關。采用梯度作為描述子的原因是，人的視覺皮層上的神經元對特定方向和空間頻率的梯度相應很敏感，經過SIFT作者的一些實驗驗證，用梯度的方法進行匹配效果很好。

4、為什么可以采用某些特征點的局部不變特征進行整幅圖像的匹配？

? ? ? 我在一份博客上找到這樣一句話：（http://apps.hi.baidu.com/share/detail/32318290，大家可以看看這篇文章。）

從直觀的人類視覺印象來看，人類視覺對物體的描述也是局部化的，基于局部不變特征的圖像識別方法十分接近于人類視覺機理，通過局部化的特征組合，形成對目標物體的整體印象，這就為局部不變特征提取方法提供了生物學上的解釋，因此局部不變特征也得到了廣泛應用。

? ? ? 還有：

? ? ? 圖像中的每個局部區域的重要性和影響范圍并非同等重要，即特征不是同等顯著的，其主要理論來源是Marr的計算機視覺理論和Treisman的特征整合理論，一般也稱為“原子論”。該理論認為視覺的過程開始于對物體的特征性質和簡單組成部分的分析，是從局部性質到大范圍性質。

? ? ? SIFT/SURF都是對特征點的局部區域的描述，這些特征點應該是影響重要的點，對這些點的分析更加重要。所以在局部不變特征的提取和描述時也遵循與人眼視覺注意選擇原理相類似的機制，所以SIFT/SURF用于匹配有效果。

?

?

不同點的比較：

從博客上看到一個總結，我修改了一些內容。大家可以參看以下鏈接：

http://blog.csdn.net/ijuliet/archive/2009/10/07/4640624.aspx

?	SIFT	SURF
尺度空間	DOG與不同尺度的圖片卷積	不同尺度的box filters與原圖片卷積
特征點檢測	先進行非極大抑制，再去除低對比度的點。再通過Hessian矩陣去除邊緣的點	先利用Hessian矩陣確定候選點，然后進行非極大抑制
方向	在正方形區域內統計梯度的幅值的直方圖，找max對應的方向?？梢杂卸鄠€方向。	在圓形區域內，計算各個扇形范圍內x、y方向的haar小波響應，找模最大的扇形方向
特征描述子	16*16的采樣點劃分為4*4的區域，計算每個區域的采樣點的梯度方向和幅值，統計成8bin直方圖，一共4*4*8=128維	20*20s的區域劃分為4*4的子區域，每個子區域找5*5個采樣點，計算采樣點的haar小波響應，記錄∑dx,∑dy,∑|dx|,∑|dy|，一共4*4*4=64維

?SURF—金字塔僅僅是用來做特征點的檢測。在計算描述子的時候，haar小波響應是計算在原圖像（利用積分圖）。而SIFT是計算在高斯金字塔上（注意不是高斯差分金字塔。）

性能的比較：

論文：A comparison of SIFT, PCA-SIFT and SURF?對三種方法給出了性能上的比較，源圖片來源于Graffiti dataset，對原圖像進行尺度、旋轉、模糊、亮度變化、仿射變換等變化后，再與原圖像進行匹配，統計匹配的效果。效果以可重復出現性為評價指標。

比較的結果如下：

method	Time	Scale	Rotation	Blur	Illumination	Affine
Sift	common	best	best	common	common	good
Pca-sift	good	good	good	best	good	best
Surf?	best	common	common	good	best	good

?

?

?

?

?

?

??? 由此可見，SIFT在尺度和旋轉變換的情況下效果最好，SURF在亮度變化下匹配效果最好，在模糊方面優于SIFT，而尺度和旋轉的變化不及SIFT，旋轉不變上比SIFT差很多。速度上看，SURF是SIFT速度的3倍。

局部特征(5)——如何利用彩色信息 Color Descriptors

(轉載請注明出處：http://blog.csdn.net/jiang1st2010/article/details/7647766)

? ? ? ? 前面兩講中主要是針對SIFT和SURF做了一些介紹。他們的檢測子比較穩定，描述子比較魯棒，好像非常棒的樣子。但是有一點非常遺憾，就是他們在對圖像進行處理的過程中，都把圖像轉化為灰度圖像進行處理，這樣就丟失了顏色信息。而顏色，本身提供了很大的信息量，丟失了特別可惜。很多人可能就會想，如何在描述子中加入顏色信息。在這一講中，我們就重點介紹一下改進的SIFT/SURF的Color Descriptor。

? ? ? ? 這里的Descriptor，其實我們可以把它當做大家傳統上理解的特征。而特征，應該具有兩個比較重要的特點。第一就是它應該是最有區分度、最有代表性的，應該盡可能減少冗余的信息。如果對于大多數物體來說，這個變量的值非常相近，沒有什么區分性，自然不適合做特征。而另一個方面，它應該盡可能的穩定和魯棒。對于同樣的物體來說，當它因為噪聲的變化或者圖像的旋轉、尺度變換等影響時，這個變量的值應該是盡可能不變的（invariant）。?我們要評價一個描述子是否魯棒，重點就看圖像被加入噪聲后，形成的描述子是否依然穩定（也就是特征的各維是否不發生變化）。這里所謂的噪聲，無外乎以下幾種：

? ? ? ? 這里幾乎把所有可能發生的線性變化都列出來了?？梢钥紤]到，現有的灰度的SIFT/SURF特征對于1-3的變化具有不變性。這主要得益于1）他們都采用梯度的直方圖（Haar小波也是計算了梯度），這樣可以消除intensity shift。2）RGB的線性變化不影響梯度的方向。3）最終都對描述子向量做了歸一化，解決了灰度的尺度變化。這樣的話，我們需要考慮的就是如何解決4-5的顏色上的變化了。在此之前，我們先看看目前不用在SIFT/SURF上有哪些顏色特征，然后考慮把這些顏色特征放到描述子中。

? ? ? ??1、RGB histogram，最常見的顏色直方圖，你懂的，但是不具有任何不變性，想到這里以后還是換個特征用吧。

? ? ? ??2、Opponent histogram

? ? ? ? O1和O2表征了顏色信息，對lightintensity shift是不變的，不過O3這個直接與灰度相關的變量就不是了。

? ? ?? ?3、Hue histogram

? ? ? ? 這個大家也熟悉，它對灰度的尺度變化和增量變化具有不變性。所以說HSV顏色空間對于RGB顏色空間，在這一點上有著優勢。

? ??? ? 4、rg histogram

? ? ? ? 相當于對rgb分量做了一個歸一化，歸一化之后r/g分量就可以描述圖像的顏色信息。其中b分量是多余的，因為r+g+b=1。Rg直方圖對light intensity change是不變的，對于存在陰影的場景中可以嘗試用。

? ? ?? ?5、transformed colorhistogram

? ? ? ? 考慮到rgb直方圖對于灰度和顏色的線性變化不具有任何不變性，但是如果我們考慮對RGB三個通道分別做歸一化，歸一化的方法如：

? ? ? ? 這樣，通過減去均值可以抵消各通道的valueshift，通過除以方差可以抵消各通道的value scale change。（均值和方差以待統計的塊為單位進行計算。）這樣歸一化之后的直方圖對于light color change and shift是具有不變性的。

?

? ? ? ? 列舉了顏色直方圖的幾種統計方法之后，我們可以把他們用在SIFT/SURF描述子之中。因為傳統的SIFT/SURF描述子是對單通道進行統計的，當使用上述特征進行統計時，就是對多個通道分別計算描述子，最后形成一個多維的特征作為顏色描述子。重點想提一下的就是：

? ? ? ??C-SIFT：利用Opponentinformation中的 O1/O3和O2/O3作為顏色特征，這么做的目的是為了消除O1和O2中的灰度信息，但是，這樣做卻不能對intensity shift有不變性。

? ? ? ??Transformedcolor SIFT：這個特征將不僅對灰度的change和shift具有不變性，同時還對各顏色的shift和change都具有不變性;

? ? ? ??RGB-SIFT：很有意思的就是由于Transformedcolor SIFT對各通道的線性變化都具有不變性，而Transformed就是RGB特征經過線性變換而來，因此RGB-SIFT和Transformed color SIFT具有同樣的不變性（效果是一樣的）。

? ? ? ?最后，對上面介紹的所有特征的不變性做一個總結，見下表，其中“+”表示對這一變化具有不變性，“-”則表示不具有這種不變性。

轉

總結

以上是生活随笔為你收集整理的局部特征（local feature）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。