1.SIFT概述

SIFT的全稱是Scale Invariant Feature Transform，尺度不變特征變換，由加拿大教授David G.Lowe提出的。SIFT特征對(duì)旋轉(zhuǎn)、尺度縮放、亮度變化等保持不變性，是一種非常穩(wěn)定的局部特征。

1.1 SIFT算法具的特點(diǎn)

1.   圖像的局部特征，對(duì)旋轉(zhuǎn)、尺度縮放、亮度變化保持不變，對(duì)視角變化、仿射變換、噪聲也保持一定程度的穩(wěn)定性。

2.   獨(dú)特性好，信息量豐富，適用于海量特征庫(kù)進(jìn)行快速、準(zhǔn)確的匹配。

3.   多量性，即使是很少幾個(gè)物體也可以產(chǎn)生大量的SIFT特征

4.   高速性，經(jīng)優(yōu)化的SIFT匹配算法甚至可以達(dá)到實(shí)時(shí)性

5.   擴(kuò)招性，可以很方便的與其他的特征向量進(jìn)行聯(lián)合。

1.2 SIFT特征檢測(cè)的步驟

有4個(gè)主要步驟

1.   尺度空間的極值檢測(cè) 搜索所有尺度空間上的圖像，通過(guò)高斯微分函數(shù)來(lái)識(shí)別潛在的對(duì)尺度和選擇不變的興趣點(diǎn)。

2.   特征點(diǎn)定位 在每個(gè)候選的位置上，通過(guò)一個(gè)擬合精細(xì)模型來(lái)確定位置尺度，關(guān)鍵點(diǎn)的選取依據(jù)他們的穩(wěn)定程度。

3.   特征方向賦值 基于圖像局部的梯度方向，分配給每個(gè)關(guān)鍵點(diǎn)位置一個(gè)或多個(gè)方向，后續(xù)的所有操作都是對(duì)于關(guān)鍵點(diǎn)的方向、尺度和位置進(jìn)行變換，從而提供這些特征的不變性。

4.   特征點(diǎn)描述 在每個(gè)特征點(diǎn)周圍的鄰域內(nèi)，在選定的尺度上測(cè)量圖像的局部梯度，這些梯度被變換成一種表示，這種表示允許比較大的局部形狀的變形和光照變換。

2. 尺度空間

在一定的范圍內(nèi)，無(wú)論物體是大還是小，人眼都可以分辨出來(lái)。然而計(jì)算機(jī)要有相同的能力卻不是那么的容易，在未知的場(chǎng)景中，計(jì)算機(jī)視覺并不能提供物體的尺度大小，其中的一種方法是把物體不同尺度下的圖像都提供給機(jī)器，讓機(jī)器能夠?qū)ξ矬w在不同的尺度下有一個(gè)統(tǒng)一的認(rèn)知。在建立統(tǒng)一認(rèn)知的過(guò)程中，要考慮的就是在圖像在不同的尺度下都存在的特征點(diǎn)。

2.1 多分辨率圖像金字塔

在早期圖像的多尺度通常使用圖像金字塔表示形式。圖像金字塔是同一圖像在不同的分辨率下得到的一組結(jié)果，其生成過(guò)程一般包括兩個(gè)步驟：

1.   對(duì)原始圖像進(jìn)行平滑

2.   對(duì)處理后的圖像進(jìn)行降采樣（通常是水平、垂直方向的1/2）
降采樣后得到一系列不斷尺寸縮小的圖像。顯然，一個(gè)傳統(tǒng)的金字塔中，每一層的圖像是其上一層圖像長(zhǎng)、高的各一半。多分辨率的圖像金字塔雖然生成簡(jiǎn)單，但其本質(zhì)是降采樣，圖像的局部特征則難以保持，也就是無(wú)法保持特征的尺度不變性。

2.2 高斯尺度空間

我們還可以通過(guò)圖像的模糊程度來(lái)模擬人在距離物體由遠(yuǎn)到近時(shí)物體在視網(wǎng)膜上成像過(guò)程，距離物體越近其尺寸越大圖像也越模糊，這就是高斯尺度空間，使用不同的參數(shù)模糊圖像（分辨率不變），是尺度空間的另一種表現(xiàn)形式。
我們知道圖像和高斯函數(shù)進(jìn)行卷積運(yùn)算能夠?qū)D像進(jìn)行模糊，使用不同的“高斯核”可得到不同模糊程度的圖像。一副圖像其高斯尺度空間可由其和不同的高斯卷積得到：

其中，是高斯核函數(shù)。

稱為尺度空間因子，它是高斯正態(tài)分布的標(biāo)準(zhǔn)差，反映了圖像被模糊的程度，其值越大圖像越模糊，對(duì)應(yīng)的尺度也就越大。

使用LoG雖然能較好的檢測(cè)到圖像中的特征點(diǎn)，但是其運(yùn)算量過(guò)大，通常可使用**DoG（差分高斯，Difference of Gaussina）**來(lái)近似計(jì)算LoG[Marrand Hidreth]。

設(shè)為相鄰兩個(gè)高斯尺度空間的比例因子，則DoG的定義：

其中，

表示高斯金字塔的層數(shù)，m，n分別是圖像的行和列。減去的系數(shù)可以在0?log2min(m,n)

其中為所在的組，為所在的層，

相鄰組之間的尺度關(guān)系

2.3 高斯金字塔構(gòu)建示例

以一個(gè)

1.   金字塔的組數(shù)，

2.   構(gòu)建第0組，將圖像的寬和高都增加一倍，變成

3.   構(gòu)建第1組，對(duì)降采樣變成

4.    ?$?$

5.   構(gòu)建第o組，第s層

高斯金字塔構(gòu)建成功后，將每一組相鄰的兩層相減就可以得到DoG金字塔.

3. DoG空間極值檢測(cè)

為了尋找尺度空間的極值點(diǎn)，每個(gè)像素點(diǎn)要和其圖像域（同一尺度空間）和尺度域（相鄰的尺度空間）的所有相鄰點(diǎn)進(jìn)行比較，當(dāng)其大于（或者小于）所有相鄰點(diǎn)時(shí)，改點(diǎn)就是極值點(diǎn)。如圖所示，中間的檢測(cè)點(diǎn)要和其所在圖像的

3.1 尺度變化的連續(xù)性

設(shè)，也就是每組有3層，則，也就是有高斯金字塔每組有層圖像，$金字塔每組有$(S-2)2層圖像。在DoG金字塔的第一組有兩層尺度分別是，第二組有兩層的尺度分別是

4. 刪除不好的極值點(diǎn)（特征點(diǎn)）

通過(guò)比較檢測(cè)得到的DoG的局部極值點(diǎn)實(shí)在離散的空間搜索得到的，由于離散空間是對(duì)連續(xù)空間采樣得到的結(jié)果，因此在離散空間找到的極值點(diǎn)不一定是真正意義上的極值點(diǎn)，因此要設(shè)法將不滿足條件的點(diǎn)剔除掉。可以通過(guò)尺度空間DoG函數(shù)進(jìn)行曲線擬合尋找極值點(diǎn)，這一步的本質(zhì)是去掉DoG局部曲率非常不對(duì)稱的點(diǎn)。
要剔除掉的不符合要求的點(diǎn)主要有兩種：

1.   低對(duì)比度的特征點(diǎn)

2.   不穩(wěn)定的邊緣響應(yīng)點(diǎn)

4.1 剔除低對(duì)比度的特征點(diǎn)

候選特征點(diǎn)x，其偏移量定義為

由于x是D(x)的極值點(diǎn)，所以對(duì)上式求導(dǎo)并令其為0，得到

然后再把求得的Δx$\Delta \mathrm{x代入到D(x)的泰勒展開式中}$

設(shè)對(duì)比度的閾值為T，若，則該特征點(diǎn)保留，否則剔除掉。

4.2 剔除不穩(wěn)定的邊緣響應(yīng)點(diǎn)

在邊緣梯度的方向上主曲率值比較大，而沿著邊緣方向則主曲率值較小。候選特征點(diǎn)的DoG函數(shù)D(x)的主曲率與2×2

其中，是候選點(diǎn)鄰域?qū)?yīng)位置的差分求得的。
為了避免求具體的值，可以使用H$H$特征值得比例。設(shè)為H的最大特征值，為H的最小特征值，則

其中，為矩陣H的跡，為矩陣H的行列式。
設(shè)表示最大特征值和最小特征值的比值，則

上式的結(jié)果與兩個(gè)特征值的比例有關(guān)，和具體的大小無(wú)關(guān)，當(dāng)兩個(gè)特征值想等時(shí)其值最小，并且隨著的增大而增大。因此為了檢測(cè)主曲率是否在某個(gè)閾值${\mathrm{下，只需檢測(cè)}}_{}$

如果上式成立，則剔除該特征點(diǎn)，否則保留。（Lowe論文中取${)}_{}$

5. 求取特征點(diǎn)的主方向

經(jīng)過(guò)上面的步驟已經(jīng)找到了在不同尺度下都存在的特征點(diǎn)，為了實(shí)現(xiàn)圖像旋轉(zhuǎn)不變性，需要給特征點(diǎn)的方向進(jìn)行賦值。利用特征點(diǎn)鄰域像素的梯度分布特性來(lái)確定其方向參數(shù)，再利用圖像的梯度直方圖求取關(guān)鍵點(diǎn)局部結(jié)構(gòu)的穩(wěn)定方向。
找到了特征點(diǎn)，也就可以得到該特征點(diǎn)的尺度，也就可以得到特征點(diǎn)所在的尺度圖像

計(jì)算以特征點(diǎn)為中心、以

計(jì)算得到梯度方向后，就要使用直方圖統(tǒng)計(jì)特征點(diǎn)鄰域內(nèi)像素對(duì)應(yīng)的梯度方向和幅值。梯度方向的直方圖的橫軸是梯度方向的角度（梯度方向的范圍是0到360度，直方圖每36度一個(gè)柱共10個(gè)柱，或者沒45度一個(gè)柱共8個(gè)柱），縱軸是梯度方向?qū)?yīng)梯度幅值的累加，在直方圖的峰值就是特征點(diǎn)的主方向。在Lowe的論文還提到了使用高斯函數(shù)對(duì)直方圖進(jìn)行平滑以增強(qiáng)特征點(diǎn)近的鄰域點(diǎn)對(duì)關(guān)鍵點(diǎn)方向的作用，并減少突變的影響。為了得到更精確的方向，通常還可以對(duì)離散的梯度直方圖進(jìn)行插值擬合。具體而言，關(guān)鍵點(diǎn)的方向可以由和主峰值最近的三個(gè)柱值通過(guò)拋物線插值得到。在梯度直方圖中，當(dāng)存在一個(gè)相當(dāng)于主峰值80%能量的柱值時(shí)，則可以將這個(gè)方向認(rèn)為是該特征點(diǎn)輔助方向。所以，一個(gè)特征點(diǎn)可能檢測(cè)到多個(gè)方向（也可以理解為，一個(gè)特征點(diǎn)可能產(chǎn)生多個(gè)坐標(biāo)、尺度相同，但是方向不同的特征點(diǎn)）。Lowe在論文中指出15%的關(guān)鍵點(diǎn)具有多方向，而且這些點(diǎn)對(duì)匹配的穩(wěn)定性很關(guān)鍵。

得到特征點(diǎn)的主方向后，對(duì)于每個(gè)特征點(diǎn)可以得到三個(gè)信息

6. 生成特征描述

通過(guò)以上的步驟已經(jīng)找到了SIFT特征點(diǎn)位置、尺度和方向信息，下面就需要使用一組向量來(lái)描述關(guān)鍵點(diǎn)也就是生成特征點(diǎn)描述子，這個(gè)描述符不只包含特征點(diǎn)，也含有特征點(diǎn)周圍對(duì)其有貢獻(xiàn)的像素點(diǎn)。描述子應(yīng)具有較高的獨(dú)立性，以保證匹配率。
特征描述符的生成大致有三個(gè)步驟：

1.   校正旋轉(zhuǎn)主方向，確保旋轉(zhuǎn)不變性。

2.   生成描述子，最終形成一個(gè)128維的特征向量

3.   歸一化處理，將特征向量長(zhǎng)度進(jìn)行歸一化處理，進(jìn)一步去除光照的影響。

為了保證特征矢量的旋轉(zhuǎn)不變性，要以特征點(diǎn)為中心，在附近鄰域內(nèi)將坐標(biāo)軸旋轉(zhuǎn)（特征點(diǎn)的主方向）角度，即將坐標(biāo)軸旋轉(zhuǎn)為特征點(diǎn)的主方向。旋轉(zhuǎn)后鄰域內(nèi)像素的新坐標(biāo)為：

旋轉(zhuǎn)后以主方向?yàn)橹行娜?nbsp;8×8

對(duì)每個(gè)關(guān)鍵點(diǎn)使用4×4

通過(guò)對(duì)特征點(diǎn)周圍的像素進(jìn)行分塊，計(jì)算塊內(nèi)梯度直方圖，生成具有獨(dú)特性的向量，這個(gè)向量是該區(qū)域圖像信息的一種抽象，具有唯一性。

7. 總結(jié)

SIFT特征以其對(duì)旋轉(zhuǎn)、尺度縮放、亮度等保持不變性，是一種非常穩(wěn)定的局部特征，在圖像處理和計(jì)算機(jī)視覺領(lǐng)域有著很重要的作用，其本身也是非常復(fù)雜的，下面對(duì)其計(jì)算過(guò)程做一個(gè)粗略總結(jié)。

1.   DoG尺度空間的極值檢測(cè)。 首先是構(gòu)造DoG尺度空間，在SIFT中使用不同參數(shù)的高斯模糊來(lái)表示不同的尺度空間。而構(gòu)造尺度空間是為了檢測(cè)在不同尺度下都存在的特征點(diǎn)，特征點(diǎn)的檢測(cè)比較常用的方法是

2.   刪除不穩(wěn)定的極值點(diǎn)。主要?jiǎng)h除兩類：低對(duì)比度的極值點(diǎn)以及不穩(wěn)定的邊緣響應(yīng)點(diǎn)。

3.   ** 確定特征點(diǎn)的主方向**。以特征點(diǎn)的為中心、以

4.   生成特征點(diǎn)的描述子。 首先將坐標(biāo)軸旋轉(zhuǎn)為特征點(diǎn)的方向，以特征點(diǎn)為中心的16×16