SIFT特征提取分析
SIFT特征提取分析
SIFT（Scale-invariant feature transform）是一種檢測(cè)局部特征的算法，該算法通過求一幅圖中的特征點(diǎn)（interest points,or corner points）及其有關(guān)scale 和 orientation 的描述子得到特征并進(jìn)行圖像特征點(diǎn)匹配，獲得了良好效果，詳細(xì)解析如下：
算法描述
SIFT特征不只具有尺度不變性，即使改變旋轉(zhuǎn)角度，圖像亮度或拍攝視角，仍然能夠得到好的檢測(cè)效果。整個(gè)算法分為以下幾個(gè)部分：
1.?構(gòu)建尺度空間
這是一個(gè)初始化操作，尺度空間理論目的是模擬圖像數(shù)據(jù)的多尺度特征。
高斯卷積核是實(shí)現(xiàn)尺度變換的唯一線性核，于是一副二維圖像的尺度空間定義為：
其中 G(x,y,σ)?是尺度可變高斯函數(shù)?
（x，y）是空間坐標(biāo)，是尺度坐標(biāo)。σ大小決定圖像的平滑程度，大尺度對(duì)應(yīng)圖像的概貌特征，小尺度對(duì)應(yīng)圖像的細(xì)節(jié)特征。大的σ值對(duì)應(yīng)粗糙尺度(低分辨率)，反之，對(duì)應(yīng)精細(xì)尺度(高分辨率)。為了有效的在尺度空間檢測(cè)到穩(wěn)定的關(guān)鍵點(diǎn)，提出了高斯差分尺度空間（DOG scale-space）。利用不同尺度的高斯差分核與圖像卷積生成。
下圖所示不同σ下圖像尺度空間：
關(guān)于尺度空間的理解說明：2kσ中的2是必須的，尺度空間是連續(xù)的。在 ?Lowe的論文中 ，將第0層的初始尺度定為1.6（最模糊），圖片的初始尺度定為0.5（最清晰）. 在檢測(cè)極值點(diǎn)前對(duì)原始圖像的高斯平滑以致圖像丟失高頻信息，所以 Lowe 建議在建立尺度空間前首先對(duì)原始圖像長(zhǎng)寬擴(kuò)展一倍，以保留原始圖像信息，增加特征點(diǎn)數(shù)量。尺度越大圖像越模糊。?
圖像金字塔的建立：對(duì)于一幅圖像I,建立其在不同尺度(scale)的圖像，也成為子八度（octave），這是為了scale-invariant，也就是在任何尺度都能夠有對(duì)應(yīng)的特征點(diǎn)，第一個(gè)子八度的scale為原圖大小，后面每個(gè)octave為上一個(gè)octave降采樣的結(jié)果，即原圖的1/4（長(zhǎng)寬分別減半），構(gòu)成下一個(gè)子八度（高一層金字塔）。
尺度空間的所有取值，i為octave的塔數(shù)（第幾個(gè)塔），s為每塔層數(shù)
由圖片size決定建幾個(gè)塔，每塔幾層圖像(S一般為3-5層)。0塔的第0層是原始圖像(或你double后的圖像)，往上每一層是對(duì)其下一層進(jìn)行Laplacian變換（高斯卷積，其中σ值漸大，例如可以是σ, k*σ, k*k*σ…），直觀上看來越往上圖片越模糊。塔間的圖片是降采樣關(guān)系，例如1塔的第0層可以由0塔的第3層down sample得到，然后進(jìn)行與0塔類似的高斯卷積操作。
2.?LoG近似DoG找到關(guān)鍵點(diǎn)<檢測(cè)DOG尺度空間極值點(diǎn)>
為了尋找尺度空間的極值點(diǎn)，每一個(gè)采樣點(diǎn)要和它所有的相鄰點(diǎn)比較，看其是否比它的圖像域和尺度域的相鄰點(diǎn)大或者小。如圖所示，中間的檢測(cè)點(diǎn)和它同尺度的8個(gè)相鄰點(diǎn)和上下相鄰尺度對(duì)應(yīng)的9×2個(gè)點(diǎn)共26個(gè)點(diǎn)比較，以確保在尺度空間和二維圖像空間都檢測(cè)到極值點(diǎn)。 一個(gè)點(diǎn)如果在DOG尺度空間本層以及上下兩層的26個(gè)領(lǐng)域中是最大或最小值時(shí)，就認(rèn)為該點(diǎn)是圖像在該尺度下的一個(gè)特征點(diǎn),如圖所示。
同一組中的相鄰尺度（由于k的取值關(guān)系，肯定是上下層）之間進(jìn)行尋找
s=3的情況
?在極值比較的過程中，每一組圖像的首末兩層是無法進(jìn)行極值比較的，為了滿足尺度變化的連續(xù)性（下面有詳解） ，我們?cè)诿恳唤M圖像的頂層繼續(xù)用高斯模糊生成了?3 幅圖像，高斯金字塔有每組S+3層圖像。DOG金字塔每組有S+2層圖像.
========================================== 這里有的童鞋不理解什么叫“為了滿足尺度變化的連續(xù)性”，現(xiàn)在做仔細(xì)闡述： 假設(shè)s=3，也就是每個(gè)塔里有3層，則k=21/s=21/3，那么按照上圖可得Gauss Space和DoG space 分別有3個(gè)（s個(gè)）和2個(gè)（s-1個(gè)）分量，在DoG space中，1st-octave兩項(xiàng)分別是σ,kσ; 2nd-octave兩項(xiàng)分別是2σ,2kσ;由于無法比較極值，我們必須在高斯空間繼續(xù)添加高斯模糊項(xiàng)，使得形成σ,kσ,k2σ,k3σ,k4σ這樣就可以選擇DoG space中的中間三項(xiàng)kσ,k2σ,k3σ（只有左右都有才能有極值），那么下一octave中（由上一層降采樣獲得）所得三項(xiàng)即為2kσ,2k2σ,2k3σ，其首項(xiàng)2kσ=24/3。剛好與上一octave末項(xiàng)k3σ=23/3尺度變化連續(xù)起來，所以每次要在Gaussian space添加3項(xiàng)，每組（塔）共S+3層圖像，相應(yīng)的DoG金字塔有S+2層圖像。 ==========================================
使用Laplacian of Gaussian能夠很好地找到找到圖像中的興趣點(diǎn)，但是需要大量的計(jì)算量，所以使用Difference of Gaussian圖像的極大極小值近似尋找特征點(diǎn).DOG算子計(jì)算簡(jiǎn)單，是尺度歸一化的LoG算子的近似,有關(guān)DOG尋找特征點(diǎn)的介紹及方法詳見http://blog.csdn.net/abcjennifer/article/details/7639488，極值點(diǎn)檢測(cè)用的Non-Maximal Suppression。
3.?除去不好的特征點(diǎn)
這一步本質(zhì)上要去掉DoG局部曲率非常不對(duì)稱的像素。
通過擬和三維二次函數(shù)以精確確定關(guān)鍵點(diǎn)的位置和尺度（達(dá)到亞像素精度），同時(shí)去除低對(duì)比度的關(guān)鍵點(diǎn)和不穩(wěn)定的邊緣響應(yīng)點(diǎn)(因?yàn)镈oG算子會(huì)產(chǎn)生較強(qiáng)的邊緣響應(yīng))，以增強(qiáng)匹配穩(wěn)定性、提高抗噪聲能力，在這里使用近似Harris Corner檢測(cè)器。
①空間尺度函數(shù)泰勒展開式如下：，對(duì)上式求導(dǎo),并令其為0,得到精確的位置, 得
②在已經(jīng)檢測(cè)到的特征點(diǎn)中,要去掉低對(duì)比度的特征點(diǎn)和不穩(wěn)定的邊緣響應(yīng)點(diǎn)。去除低對(duì)比度的點(diǎn)：把公式(2)代入公式(1)，即在DoG Space的極值點(diǎn)處D(x)取值，只取前兩項(xiàng)可得：
若 ??，該特征點(diǎn)就保留下來，否則丟棄。
③邊緣響應(yīng)的去除
一個(gè)定義不好的高斯差分算子的極值在橫跨邊緣的地方有較大的主曲率，而在垂直邊緣的方向有較小的主曲率。主曲率通過一個(gè)2×2 的Hessian矩陣H求出:
導(dǎo)數(shù)由采樣點(diǎn)相鄰差估計(jì)得到。
D的主曲率和H的特征值成正比，令α為較大特征值，β為較小的特征值，則
令α=γβ，則
?(r + 1)2/r的值在兩個(gè)特征值相等的時(shí)候最小，隨著r的增大而增大，因此，為了檢測(cè)主曲率是否在某域值r下，只需檢測(cè)
if?(α+β)/?αβ> (r+1)2/r, throw it out. ??在Lowe的文章中，取r＝10。
4.?給特征點(diǎn)賦值一個(gè)128維方向參數(shù)
上一步中確定了每幅圖中的特征點(diǎn)，為每個(gè)特征點(diǎn)計(jì)算一個(gè)方向，依照這個(gè)方向做進(jìn)一步的計(jì)算，?利用關(guān)鍵點(diǎn)鄰域像素的梯度方向分布特性為每個(gè)關(guān)鍵點(diǎn)指定方向參數(shù)，使算子具備旋轉(zhuǎn)不變性。
為(x,y)處梯度的模值和方向公式。其中L所用的尺度為每個(gè)關(guān)鍵點(diǎn)各自所在的尺度。至此，圖像的關(guān)鍵點(diǎn)已經(jīng)檢測(cè)完畢，每個(gè)關(guān)鍵點(diǎn)有三個(gè)信息：位置，所處尺度、方向，由此可以確定一個(gè)SIFT特征區(qū)域。
梯度直方圖的范圍是0～360度，其中每10度一個(gè)柱，總共36個(gè)柱。隨著距 ????? 中心點(diǎn)越遠(yuǎn)的領(lǐng)域其對(duì)直方圖的貢獻(xiàn)也響應(yīng)減小.Lowe論文中還提到要使用高斯函數(shù)對(duì)直方圖進(jìn)行平滑，減少突變的影響。
在實(shí)際計(jì)算時(shí)，我們?cè)谝躁P(guān)鍵點(diǎn)為中心的鄰域窗口內(nèi)采樣，并用直方圖統(tǒng)計(jì)鄰域像素的梯度方向。梯度直方圖的范圍是0～360度，其中每45度一個(gè)柱，總共8個(gè)柱, 或者每10度一個(gè)柱，總共36個(gè)柱。Lowe論文中還提到要使用高斯函數(shù)對(duì)直方圖進(jìn)行平滑，減少突變的影響。直方圖的峰值則代表了該關(guān)鍵點(diǎn)處鄰域梯度的主方向，即作為該關(guān)鍵點(diǎn)的方向。
直方圖中的峰值就是主方向，其他的達(dá)到最大值80%的方向可作為輔助方向
由梯度方向直方圖確定主梯度方向
該步中將建立所有scale中特征點(diǎn)的描述子（128維）
Identify peak and assign orientation and sum of magnitude to key point. ? The user may choose a threshold to exclude key points based on their?assigned sum of magnitudes.
關(guān)鍵點(diǎn)描述子的生成步驟
?通過對(duì)關(guān)鍵點(diǎn)周圍圖像區(qū)域分塊，計(jì)算塊內(nèi)梯度直方圖，生成具有獨(dú)特性的向量，這個(gè)向量是該區(qū)域圖像信息的一種抽象，具有唯一性。
5. 關(guān)鍵點(diǎn)描述子的生成
首先將坐標(biāo)軸旋轉(zhuǎn)為關(guān)鍵點(diǎn)的方向，以確保旋轉(zhuǎn)不變性。以關(guān)鍵點(diǎn)為中心取8×8的窗口。
Figure.16*16的圖中其中1/4的特征點(diǎn)梯度方向及scale，右圖為其加權(quán)到8個(gè)主方向后的效果。
圖左部分的中央為當(dāng)前關(guān)鍵點(diǎn)的位置，每個(gè)小格代表關(guān)鍵點(diǎn)鄰域所在尺度空間的一個(gè)像素，利用公式求得每個(gè)像素的梯度幅值與梯度方向，箭頭方向代表該像素的梯度方向，箭頭長(zhǎng)度代表梯度模值，然后用高斯窗口對(duì)其進(jìn)行加權(quán)運(yùn)算。
圖中藍(lán)色的圈代表高斯加權(quán)的范圍（越靠近關(guān)鍵點(diǎn)的像素梯度方向信息貢獻(xiàn)越大）。然后在每4×4的小塊上計(jì)算8個(gè)方向的梯度方向直方圖，繪制每個(gè)梯度方向的累加值，即可形成一個(gè)種子點(diǎn)，如圖右部分示。此圖中一個(gè)關(guān)鍵點(diǎn)由2×2共4個(gè)種子點(diǎn)組成，每個(gè)種子點(diǎn)有8個(gè)方向向量信息。這種鄰域方向性信息聯(lián)合的思想增強(qiáng)了算法抗噪聲的能力，同時(shí)對(duì)于含有定位誤差的特征匹配也提供了較好的容錯(cuò)性。
計(jì)算keypoint周圍的16*16的window中每一個(gè)像素的梯度，而且使用高斯下降函數(shù)降低遠(yuǎn)離中心的權(quán)重。
在每個(gè)4*4的1/16象限中，通過加權(quán)梯度值加到直方圖8個(gè)方向區(qū)間中的一個(gè)，計(jì)算出一個(gè)梯度方向直方圖。
這樣就可以對(duì)每個(gè)feature形成一個(gè)4*4*8=128維的描述子，每一維都可以表示4*4個(gè)格子中一個(gè)的scale/orientation.?將這個(gè)向量歸一化之后，就進(jìn)一步去除了光照的影響。
5. 根據(jù)SIFT進(jìn)行Match
生成了A、B兩幅圖的描述子，（分別是k1*128維和k2*128維），就將兩圖中各個(gè)scale（所有scale）的描述子進(jìn)行匹配，匹配上128維即可表示兩個(gè)特征點(diǎn)match上了。
實(shí)際計(jì)算過程中，為了增強(qiáng)匹配的穩(wěn)健性，Lowe建議對(duì)每個(gè)關(guān)鍵點(diǎn)使用4×4共16個(gè)種子點(diǎn)來描述，這樣對(duì)于一個(gè)關(guān)鍵點(diǎn)就可以產(chǎn)生128個(gè)數(shù)據(jù)，即最終形成128維的SIFT特征向量。此時(shí)SIFT特征向量已經(jīng)去除了尺度變化、旋轉(zhuǎn)等幾何變形因素的影響，再繼續(xù)將特征向量的長(zhǎng)度歸一化，則可以進(jìn)一步去除光照變化的影響。?當(dāng)兩幅圖像的SIFT特征向量生成后，下一步我們采用關(guān)鍵點(diǎn)特征向量的歐式距離來作為兩幅圖像中關(guān)鍵點(diǎn)的相似性判定度量。取圖像1中的某個(gè)關(guān)鍵點(diǎn)，并找出其與圖像2中歐式距離最近的前兩個(gè)關(guān)鍵點(diǎn)，在這兩個(gè)關(guān)鍵點(diǎn)中，如果最近的距離除以次近的距離少于某個(gè)比例閾值，則接受這一對(duì)匹配點(diǎn)。降低這個(gè)比例閾值，SIFT匹配點(diǎn)數(shù)目會(huì)減少，但更加穩(wěn)定。為了排除因?yàn)閳D像遮擋和背景混亂而產(chǎn)生的無匹配關(guān)系的關(guān)鍵點(diǎn),Lowe提出了比較最近鄰距離與次近鄰距離的方法,距離比率ratio小于某個(gè)閾值的認(rèn)為是正確匹配。因?yàn)閷?duì)于錯(cuò)誤匹配,由于特征空間的高維性,相似的距離可能有大量其他的錯(cuò)誤匹配,從而它的ratio值比較高。Lowe推薦ratio的閾值為0.8。但作者對(duì)大量任意存在尺度、旋轉(zhuǎn)和亮度變化的兩幅圖片進(jìn)行匹配，結(jié)果表明ratio取值在0. 4~0. 6之間最佳，小于0. 4的很少有匹配點(diǎn)，大于0. 6的則存在大量錯(cuò)誤匹配點(diǎn)。(如果這個(gè)地方你要改進(jìn)，最好給出一個(gè)匹配率和ration之間的關(guān)系圖，這樣才有說服力)作者建議ratio的取值原則如下:
ratio=0. 4 對(duì)于準(zhǔn)確度要求高的匹配；
ratio=0. 6 對(duì)于匹配點(diǎn)數(shù)目要求比較多的匹配；?
ratio=0. 5 一般情況下。
也可按如下原則:當(dāng)最近鄰距離<200時(shí)ratio=0. 6，反之ratio=0. 4。ratio的取值策略能排分錯(cuò)誤匹配點(diǎn)。
當(dāng)兩幅圖像的SIFT特征向量生成后，下一步我們采用關(guān)鍵點(diǎn)特征向量的歐式距離來作為兩幅圖像中關(guān)鍵點(diǎn)的相似性判定度量。取圖像1中的某個(gè)關(guān)鍵點(diǎn)，并找出其與圖像2中歐式距離最近的前兩個(gè)關(guān)鍵點(diǎn)，在這兩個(gè)關(guān)鍵點(diǎn)中，如果最近的距離除以次近的距離少于某個(gè)比例閾值，則接受這一對(duì)匹配點(diǎn)。降低這個(gè)比例閾值，SIFT匹配點(diǎn)數(shù)目會(huì)減少，但更加穩(wěn)定。
?
實(shí)驗(yàn)結(jié)果：
Python+opencv實(shí)現(xiàn)：
[python]?view plaincopy
C實(shí)現(xiàn)：
[cpp]?view plaincopy
輔助資料：
===============================
Reference:
Lowe SIFT 原文：http://www.cs.ubc.ca/~lowe/papers/ijcv04.pdf
SIFT 的C實(shí)現(xiàn)：https://github.com/robwhess/opensift/blob/master/src
MATLAB 應(yīng)用Sift算子的模式識(shí)別方法：http://blog.csdn.net/abcjennifer/article/details/7372880
http://blog.csdn.net/abcjennifer/article/details/7365882
http://en.wikipedia.org/wiki/Scale-invariant_feature_transform#David_Lowe.27s_method
http://blog.sciencenet.cn/blog-613779-475881.html
http://www.cnblogs.com/linyunzju/archive/2011/06/14/2080950.html
http://www.cnblogs.com/linyunzju/archive/2011/06/14/2080951.html
http://blog.csdn.net/ijuliet/article/details/4640624
http://www.cnblogs.com/cfantaisie/archive/2011/06/14/2080917.html? (部分圖片有誤，以本文中的圖片為準(zhǔn))
原文地址：http://blog.csdn.net/abcjennifer/article/details/7639681
總結(jié)
以上是生活随笔為你收集整理的SIFT特征提取分析的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 最长的单词
- 下一篇： 神经网络 Stanford UFLDL