|
SIFT（Scale-invariant feature transform）是一種檢測局部特征的算法，該算法通過求一幅圖中的特征點(diǎn)（interest points,or corner points）及其有關(guān)scale 和 orientation 的描述子得到特征并進(jìn)行圖像特征點(diǎn)匹配,，獲得了良好效果,，詳細(xì)解析如下：
算法描述
SIFT特征不只具有尺度不變性，即使改變旋轉(zhuǎn)角度,，圖像亮度或拍攝視角,，仍然能夠得到好的檢測效果。整個(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ì)尺度(高分辨率)。為了有效的在尺度空間檢測到穩(wěn)定的關(guān)鍵點(diǎn),，提出了高斯差分尺度空間（DOG
scale-space）,。利用不同尺度的高斯差分核與圖像卷積生成。
下圖所示不同σ下圖像尺度空間：
關(guān)于尺度空間的理解說明：2kσ中的2是必須的,，尺度空間是連續(xù)的,。在 Lowe的論文中 ，將第0層的初始尺度定為1.6（最模糊）,，圖片的初始尺度定為0.5（最清晰）. 在檢測極值點(diǎn)前對(duì)原始圖像的高斯平滑以致圖像丟失高頻信息,，所以 Lowe 建議在建立尺度空間前首先對(duì)原始圖像長寬擴(kuò)展一倍，以保留原始圖像信息,，增加特征點(diǎn)數(shù)量,。尺度越大圖像越模糊,。 圖像金字塔的建立：對(duì)于一幅圖像I,建立其在不同尺度(scale)的圖像，也成為子八度（octave）,，這是為了scale-invariant,，也就是在任何尺度都能夠有對(duì)應(yīng)的特征點(diǎn)，第一個(gè)子八度的scale為原圖大小,，后面每個(gè)octave為上一個(gè)octave將采樣的結(jié)果,，即原圖的1/4（長寬分別減半），構(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)<檢測DOG尺度空間極值點(diǎn)> 為了尋找尺度空間的極值點(diǎn),，每一個(gè)采樣點(diǎn)要和它所有的相鄰點(diǎn)比較，看其是否比它的圖像域和尺度域的相鄰點(diǎn)大或者小,。如圖所示,，中間的檢測點(diǎn)和它同尺度的8個(gè)相鄰點(diǎn)和上下相鄰尺度對(duì)應(yīng)的9×2個(gè)點(diǎn)共26個(gè)點(diǎn)比較，以確保在尺度空間和二維圖像空間都檢測到極值點(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ù)性（下面有詳解）
,，我們在每一組圖像的頂層繼續(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ì)算簡單，是尺度歸一化的LoG算子的近似,有關(guān)DOG尋找特征點(diǎn)的介紹及方法詳見http://blog.csdn.net/abcjennifer/article/details/7639488,，極值點(diǎn)檢測用的Non-Maximal Suppression,。 3. 除去不好的特征點(diǎn)
通過擬和三維二次函數(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檢測器,。 ①空間尺度函數(shù)泰勒展開式如下： ②在已經(jīng)檢測到的特征點(diǎn)中,要去掉低對(duì)比度的特征點(diǎn)和不穩(wěn)定的邊緣響應(yīng)點(diǎn)。去除低對(duì)比度的點(diǎn)：把公式(2)代入公式(1),，即在DoG
Space的極值點(diǎn)處D(x)取值,，只取前兩項(xiàng)可得：
若 ③邊緣響應(yīng)的去除 
導(dǎo)數(shù)由采樣點(diǎn)相鄰差估計(jì)得到,。 D的主曲率和H的特征值成正比，令α為較大特征值,，β為較小的特征值,，則 令α=γβ，則
(r + 1)2/r的值在兩個(gè)特征值相等的時(shí)候最小,，隨著r的增大而增大,，因此，為了檢測主曲率是否在某域值r下,，只需檢測
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)檢測完畢,，每個(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í)，我們在以關(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è)像素的梯度幅值與梯度方向,，箭頭方向代表該像素的梯度方向，箭頭長度代表梯度模值,，然后用高斯窗口對(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ù)將特征向量的長度歸一化，則可以進(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)確度要求高的匹配；
當(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é)果：
===============================
基本概念及一些補(bǔ)充
什么是局部特征,？
局部特征從總體上說是圖像或在視覺領(lǐng)域中一些有別于其周圍的地方
局部特征通常是描述一塊區(qū)域,，使其能具有高可區(qū)分度
局部特征的好壞直接會(huì)決定著后面分類、識(shí)別是否會(huì)得到一個(gè)好的結(jié)果
局部特征需具備的特性
重復(fù)性
可區(qū)分性
準(zhǔn)確性
數(shù)量以及效率
不變性
局部特征提取算法-sift
SIFT算法由D.G.Lowe
1999年提出，2004年完善總結(jié),。后來Y.Ke將其描述子部分用PCA代替直方圖的方式,，對(duì)其進(jìn)行改進(jìn)。
SIFT算法是一種提取局部特征的算法,，在尺度空間尋找極值點(diǎn),，提取位置，尺度,，旋轉(zhuǎn)不變量
SIFT特征是圖像的局部特征,，其對(duì)旋轉(zhuǎn)、尺度縮放,、亮度變化保持不變性,，對(duì)視角變化、仿射變換,、噪聲也保持一定程度的穩(wěn)定性。
獨(dú)特性好,，信息量豐富,，適用于在海量特征數(shù)據(jù)庫中進(jìn)行快速、準(zhǔn)確的匹配,。
多量性,，即使少數(shù)的幾個(gè)物體也可以產(chǎn)生大量SIFT特征向量。
可擴(kuò)展性,，可以很方便的與其他形式的特征向量進(jìn)行聯(lián)合,。
尺度空間理論 尺度空間理論目的是模擬圖像數(shù)據(jù)的多尺度特征
其基本思想是在視覺信息圖像信息處理模型中引入一個(gè)被視為尺度的參數(shù), 通過連續(xù)變化尺度參數(shù)獲得不同尺度下的視覺處理信息,
然后綜合這些信息以深入地挖掘圖像的本質(zhì)特征。
描述子生成的細(xì)節(jié)
以極值點(diǎn)為中心點(diǎn),，并且以此點(diǎn)所處于的高斯尺度sigma值作為半徑因子,。對(duì)于遠(yuǎn)離中心點(diǎn)的梯度值降低對(duì)其所處區(qū)域的直方圖的貢獻(xiàn)，防止一些突變的影響,。
每個(gè)極值點(diǎn)對(duì)其進(jìn)行三線性插值,，這樣可以把此極值點(diǎn)的貢獻(xiàn)均衡的分到直方圖中相鄰的柱子上
歸一化處理
在求出4*4*8的128維特征向量后，此時(shí)SIFT特征向量已經(jīng)去除了尺度變化,、旋轉(zhuǎn)等幾何變形因素的影響,。而圖像的對(duì)比度變化相當(dāng)于每個(gè)像素點(diǎn)乘上一個(gè)因子，光照變化是每個(gè)像素點(diǎn)加上一個(gè)值,，但這些對(duì)圖像歸一化的梯度沒有影響,。因此將特征向量的長度歸一化，則可以進(jìn)一步去除光照變化的影響,。
對(duì)于一些非線性的光照變化,，SIFT并不具備不變性，但由于這類變化影響的主要是梯度的幅值變化,，對(duì)梯度的方向影響較小,，因此作者通過限制梯度幅值的值來減少這類變化造成的影響,。
PCA-SIFT算法
PCA-SIFT與標(biāo)準(zhǔn)SIFT有相同的亞像素位置，尺度和主方向,。但在第4步計(jì)算描述子的設(shè)計(jì),，采用的主成分分析的技術(shù)。
下面介紹一下其特征描述子計(jì)算的部分：
用特征點(diǎn)周圍的41×41的像斑計(jì)算它的主元,，并用PCA-SIFT將原來的2×39×39維的向量降成20維,，以達(dá)到更精確的表示方式。
它的主要步驟為,，對(duì)每一個(gè)關(guān)鍵點(diǎn)：在關(guān)鍵點(diǎn)周圍提取一個(gè)41×41的像斑于給定的尺度,，旋轉(zhuǎn)到它的主方向 ；計(jì)算39×39水平和垂直的梯度,，形成一個(gè)大小為3042的矢量,；用預(yù)先計(jì)算好的投影矩陣n×3042與此矢量相乘；這樣生成一個(gè)大小為n的PCA-SIFT描述子,。
輔助資料：
=============================== Reference: http://blog.csdn.net/abcjennifer/article/details/7372880 http://blog.csdn.net/abcjennifer/article/details/7365882 http://en./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)) |
|
|
,，
