SIFT

這篇文章主要介紹 SIFT 算法。希望通過(guò)對(duì) SIFT 算法的總結(jié)來(lái)更加深入地了解“尺度不變特征變換”，除此之外，也加深來(lái)對(duì) SURF 算法的理解。
附件：SIFT—Scale Invariant Feature Transform

1 SIFT 發(fā)展歷程及主要思想
SIFT算法由D.G.Lowe 1999年提出，2004年完善總結(jié)。后來(lái)Y.Ke將其描述子部分用PCA代替直方圖的方式，對(duì)其進(jìn)行改進(jìn)。是一種提取局部特征的算法，在尺度空間尋找極值點(diǎn)，提取位置，尺度，旋轉(zhuǎn)不變量。
2 SIFT算法的主要特點(diǎn)
a) SIFT特征是圖像的局部特征，其對(duì)旋轉(zhuǎn)、尺度縮放、亮度變化保持不變性，對(duì)視角變化、仿射變換、噪聲也保持一定程度的穩(wěn)定性；
b) 獨(dú)特性(Distinctiveness)好，信息量豐富，適用于在海量特征數(shù)據(jù)庫(kù)中進(jìn)行快速、準(zhǔn)確的匹配；
c) 多量性，即使少數(shù)的幾個(gè)物體也可以產(chǎn)生大量SIFT特征向量；
d) 高速性，經(jīng)優(yōu)化的SIFT匹配算法甚至可以達(dá)到實(shí)時(shí)的要求；
e) 可擴(kuò)展性，可以很方便的與其他形式的特征向量進(jìn)行聯(lián)合。
3 SIFT算法步驟：
1） 檢測(cè)尺度空間極值點(diǎn)；
2） 精確定位極值點(diǎn)；
3） 為每個(gè)關(guān)鍵點(diǎn)指定方向參數(shù)；
4） 關(guān)鍵點(diǎn)描述子的生成。
4 SIFT算法詳細(xì)
▲尺度空間的生成
尺度空間理論目的是模擬圖像數(shù)據(jù)的多尺度特征。高斯卷積核是實(shí)現(xiàn)尺度變換的唯一線性核，于是一副二維圖像的尺度空間定義為： ?

其中    是尺度可變高斯函數(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）。利用不同尺度的高斯差分核與圖像卷積生成。
DOG算子計(jì)算簡(jiǎn)單，是尺度歸一化的LoG算子的近似。
圖像金字塔的構(gòu)建：圖像金字塔共O組，每組有S層，下一組的圖像由上一組圖像降采樣得到。

▲空間極值點(diǎn)檢測(cè)
為了尋找尺度空間的極值點(diǎn)，每一個(gè)采樣點(diǎn)要和它所有的相鄰點(diǎn)比較，看其是否比它的圖像域和尺度域的相鄰點(diǎn)大或者小。如圖3所示，中間的檢測(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),如圖所示。

▲精確確定極值點(diǎn)位置
通過(guò)擬和三維二次函數(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)定性、提高抗噪聲能力。
①空間尺度函數(shù)泰勒展開(kāi)式如下:   (1)
對(duì)上式求導(dǎo),并令其為0,得到精確的位置,    (2)
②在已經(jīng)檢測(cè)到的特征點(diǎn)中,要去掉低對(duì)比度的特征點(diǎn)和不穩(wěn)定的邊緣響應(yīng)點(diǎn)。去除低對(duì)比度的點(diǎn)：把公式(2)代入公式(1)，只取前兩項(xiàng)可得：
若   ，該特征點(diǎn)就保留下來(lái)，否則丟棄。
③邊緣響應(yīng)的去除
一個(gè)定義不好的高斯差分算子的極值在橫跨邊緣的地方有較大的主曲率，而在垂直邊緣的方向有較小的主曲率。主曲率通過(guò)一個(gè)2×2 的Hessian矩陣H求出:

導(dǎo)數(shù)由采樣點(diǎn)相鄰差估計(jì)得到。D的主曲率和H的特征值成正比，令為最大特征值，為最小的特征值， 令   則：

(r + 1)2/r的值在兩個(gè)特征值相等的時(shí)候最小，隨著r的增大而增大，因此，為了檢測(cè)主曲率是否在某域值r下，只需檢測(cè)  在Lowe的文章中，取r＝10。

▲關(guān)鍵點(diǎn)方向分配
利用關(guān)鍵點(diǎn)鄰域像素的梯度方向分布特性為每個(gè)關(guān)鍵點(diǎn)指定方向參數(shù)，使算子具備旋轉(zhuǎn)不變性。 
上式為(x,y)處梯度的模值和方向公式。其中L所用的尺度為每個(gè)關(guān)鍵點(diǎn)各自所在的尺度。
在實(shí)際計(jì)算時(shí)，我們?cè)谝躁P(guān)鍵點(diǎn)為中心的鄰域窗口內(nèi)采樣，并用直方圖統(tǒng)計(jì)鄰域像素的梯度方向。梯度直方圖的范圍是0～360度，其中每10度一個(gè)柱，總共36個(gè)柱。直方圖的峰值則代表了該關(guān)鍵點(diǎn)處鄰域梯度的主方向，即作為該關(guān)鍵點(diǎn)的方向。
在梯度方向直方圖中，當(dāng)存在另一個(gè)相當(dāng)于主峰值80%能量的峰值時(shí)，則將這個(gè)方向認(rèn)為是該關(guān)鍵點(diǎn)的輔方向。一個(gè)關(guān)鍵點(diǎn)可能會(huì)被指定具有多個(gè)方向（一個(gè)主方向，一個(gè)以上輔方向），這可以增強(qiáng)匹配的魯棒性。 至此，圖像的關(guān)鍵點(diǎn)已檢測(cè)完畢，每個(gè)關(guān)鍵點(diǎn)有三個(gè)信息：位置、所處尺度、方向。由此可以確定一個(gè)SIFT特征區(qū)域（在實(shí)驗(yàn)章節(jié)用橢圓或箭頭表示）。

▲特征點(diǎn)描述子生成
首先將坐標(biāo)軸旋轉(zhuǎn)為關(guān)鍵點(diǎn)的方向，以確保旋轉(zhuǎn)不變性。圖 由關(guān)鍵點(diǎn)鄰域梯度信息生成特征向量

接下來(lái)以關(guān)鍵點(diǎn)為中心取8×8的窗口。圖左部分的中央黑點(diǎn)為當(dāng)前關(guān)鍵點(diǎn)的位置，每個(gè)小格代表關(guān)鍵點(diǎn)鄰域所在尺度空間的一個(gè)像素，利用公式求得每個(gè)像素的梯度幅值與梯度方向，箭頭方向代表該像素的梯度方向，箭頭長(zhǎng)度代表梯度模值，然后用高斯窗口對(duì)其進(jìn)行加權(quán)運(yùn)算,每個(gè)像素對(duì)應(yīng)一個(gè)向量，長(zhǎng)度為，為該像素點(diǎ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ò)性。
實(shí)際計(jì)算過(guò)程中，為了增強(qiáng)匹配的穩(wěn)健性，Lowe建議對(duì)每個(gè)關(guān)鍵點(diǎn)使用4×4共16個(gè)種子點(diǎn)來(lái)描述，這樣對(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)特征向量的歐式距離來(lái)作為兩幅圖像中關(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)生的無(wú)匹配關(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)系圖，這樣才有說(shuō)服力)作者建議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)。
5 對(duì)SIFT算法的總的概述：
SIFT算法中的鄰域方向性信息聯(lián)合的思想能夠增強(qiáng)算法的抗噪聲能力,同時(shí)對(duì)于含有定位誤差的特征匹配也提供了較好的容錯(cuò)性,并且SIFT特征是圖像的局部特征,其對(duì)圖像旋轉(zhuǎn)、尺度縮放、亮度變化保持不變性,對(duì)視角變化、仿射變換、噪聲也保持一定程度的穩(wěn)定性,它具有很好的獨(dú)特性和豐富的信息量,適用于海量特征數(shù)據(jù)庫(kù)的圖像匹配。
SIFT圖像特征的許多屬性適合于對(duì)不同圖像或場(chǎng)景中同一目標(biāo)進(jìn)行匹配。這些特征對(duì)于圖像尺度、旋轉(zhuǎn)、亮度和3D視點(diǎn)都具有不變性,而且有很高的獨(dú)特性,能使單獨(dú)一個(gè)特征從很大的特征數(shù)據(jù)庫(kù)中被高概率正確地匹配出來(lái),減小了由遮擋、混亂或噪音所造成的錯(cuò)誤概率。
SIFT算法基于圖像特征尺度選擇的思想，建立圖像的多尺度空間，在不同尺度下檢測(cè)到同一個(gè)特征點(diǎn)，確定特征點(diǎn)位置的同時(shí)確定其所在尺度，以達(dá)到尺度抗縮放的目的，剔出一些對(duì)比度較低的點(diǎn)以及邊緣響應(yīng)點(diǎn)，并提取旋轉(zhuǎn)不變特征描述符以達(dá)到抗仿射變換的目的。該算法主要包含4個(gè)步驟:
(1)建立尺度空間,尋找候選點(diǎn)；
(2)精確確定關(guān)鍵點(diǎn),剔除不穩(wěn)定點(diǎn)；
(3)確定關(guān)鍵點(diǎn)的方向；
(4)提取特征描述符。
利用一組連續(xù)的高斯卷積核與原圖像進(jìn)行卷積，生成一系列尺度空間的圖像，相鄰尺度的圖像相減就得到一組DOG圖像，然后將圖像縮小2倍并重復(fù)以上過(guò)程,直至圖像尺寸小于某一范圍(例如32×32)。
SIFT特征描述子以基于梯度位置和方向的三維直方圖來(lái)描述圖像局部特征，其中每個(gè)位置和方向上的描述子分量由梯度幅值的加權(quán)和計(jì)算求得，這種梯度位置和方向的量化使得SIFT特征描述子對(duì)圖像中細(xì)小的幾何畸變以及特征提取過(guò)程中微小的定位誤差具有非常好的抗干擾性。