摘要：降采樣的目的是為了綜合所有不同清晰度的圖像進(jìn)行關(guān)鍵點(diǎn)提取，這種關(guān)鍵點(diǎn)攜帶了不同清晰度的信息，對(duì)縮放具有不變性。是對(duì)的一種改進(jìn)，主要特點(diǎn)是快速。的達(dá)到維，導(dǎo)致的比較耗時(shí)，使用哈爾小波轉(zhuǎn)換得到的方向，讓的降到維，減少了一半，提高了匹配速度。

尺度不變特征變換(Scale-invariant feature transform， 簡(jiǎn)稱SIFT)是圖像局部特征提取的現(xiàn)代方法——基于區(qū)域/圖像塊的分析。在上篇筆記里我們使用的圖像之間對(duì)應(yīng)點(diǎn)的匹配方法，不適用于不同尺度的圖像。有許多應(yīng)用場(chǎng)景需要對(duì)不同尺度（即分辨率、縮放、旋轉(zhuǎn)角度、亮度等都可能存在不同）的圖像進(jìn)行特征識(shí)別和匹配，這就需要一種特征提取方法，通過這種方法提取出來的特征描述，可以不受尺度的影響，SIFT算法就是這種方法的實(shí)現(xiàn)。SHIT算法有如下的特點(diǎn)：

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

獨(dú)特性（Distinctiveness）好，信息量豐富，適用于在海量特征數(shù)據(jù)庫(kù)中進(jìn)行快速、準(zhǔn)確的匹配；

多量性，即使少數(shù)的幾個(gè)物體也可以產(chǎn)生大量的SIFT特征向量；

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

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

SIFT算法的應(yīng)用非常廣泛，包括物體識(shí)別、機(jī)器人地圖感知與導(dǎo)航、全景拼接、3D建模、手勢(shì)識(shí)別、影像追蹤和動(dòng)作比對(duì)等,原書后面章節(jié)的算法也會(huì)多次用到它。SIFT算法的過程較復(fù)雜，本文只是粗略介紹其關(guān)鍵步驟，以便引出SURF——基于SIFT的改進(jìn)算法。

SIFT的算法還是比較復(fù)雜的，但也讓人大開眼界，權(quán)威的和詳細(xì)的介紹應(yīng)該直接看英文論文，我的筆記記錄的也只是其算法的要點(diǎn)，目的是為了理解算法的思想，為了對(duì)涉及到的數(shù)學(xué)有一個(gè)大概的了解。

降采樣或隔點(diǎn)采樣，將一幅圖像降為一半大小的圖像，連續(xù)使用幾次降采樣，每次得到的圖像大小都降為前一張大小的一半，最后得到一組降采樣的圖像。降采樣的目的是為了綜合所有不同清晰度的圖像進(jìn)行關(guān)鍵點(diǎn)提取，這種關(guān)鍵點(diǎn)攜帶了不同清晰度的信息，對(duì)縮放具有不變性。

在之前的筆記介紹過，原圖像與高斯核（2維高斯算子）作卷積（高斯濾波）的結(jié)果即為模糊圖像，實(shí)為平滑效果，高斯濾波屬于低通濾波，它可以過濾掉一定的噪聲。如果把兩張使用不同sigma的模糊圖像記為Bσ和Bkσ, DOG操作即為兩張模糊圖像之差，記：

Gσ = Bkσ - Bσ

Gσ為DOG圖像，它包含的特征是目標(biāo)的輪廓。

SIFT先對(duì)降采樣后的每張圖像使用不同的sigma進(jìn)行高斯模糊，結(jié)果是每個(gè)降采樣圖像對(duì)應(yīng)一組模糊圖像：

然后對(duì)每組模糊圖像的相鄰圖像作DOG，結(jié)果是每個(gè)降采樣圖像對(duì)應(yīng)一組DOG圖像，如圖：

把每一組圖像堆疊起來，位于塔底的是第一組（first octave），往上是第二組，第三組...每一組的圖像大小為前一組的一半，看起來像金字塔：

如圖Gaussian列（左邊）稱為高斯金字塔，DOG列（右邊）稱為DOG金字塔。

SIFT分別對(duì)每組DOG圖像提取關(guān)鍵點(diǎn)，以第一組為例，將第一組DOG圖像上下對(duì)齊疊加在一起，形成DOG空間，DOG空間有兩個(gè)域：圖像域和尺度域。圖像域指圖像本身的二維平面像素，尺度域指垂直于圖像域的第三維度構(gòu)成的像素。SIFT使用局部極值檢測(cè)來定位找到關(guān)鍵點(diǎn)，如下圖所示：

X位置所在像素即為當(dāng)前要檢測(cè)的點(diǎn)，以X為中心的周圍像素（包括圖像域和尺度域）形成了一個(gè)局部空間（像3X3魔方），如果X為此局部空間的極值（最大值或最小值），那么X即為關(guān)鍵點(diǎn)之一。

SIFT的提取的特征（關(guān)鍵點(diǎn)）需要對(duì)尺度保持不變性，所以這里講的關(guān)鍵點(diǎn)，比之前筆記介紹的角點(diǎn)和興趣點(diǎn)稍為復(fù)雜些，SIFT關(guān)鍵點(diǎn)需要攜帶尺度信息，包括縮放、方向等信息，主要由它周圍的像素來貢獻(xiàn)。如果用一個(gè)向量來存儲(chǔ)這些信息，此向量稱為關(guān)鍵點(diǎn)描述（key point descriptor，簡(jiǎn)稱KPD），KPD生成步驟：

在關(guān)鍵點(diǎn)所在圖像上，劃出以關(guān)鍵點(diǎn)為中心的16x16的矩形圖像：

將16x16矩形圖像劃分為16小格，每小格為4x4，并計(jì)算每個(gè)像素的梯度和幅度（即像素值變化的方向及大小）：

對(duì)每個(gè)小格進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)8個(gè)方向的幅度，形成幅度直方圖：

將16小格的幅度直方圖連接起來，用向量表示，即為KPD，共有128（8x16）維：

使用向量表示為： R = (r1, r2, ..., r128)

為了讓關(guān)鍵點(diǎn)對(duì)方向具有不變性，在選取16x16矩形區(qū)域的時(shí)候，將矩形的方向旋轉(zhuǎn)到與關(guān)鍵點(diǎn)主方向一致。SIFT定義關(guān)鍵點(diǎn)主方向?yàn)椋阂躁P(guān)鍵點(diǎn)為中心的周圍像素所貢獻(xiàn)的主方向。

可采用梯度直方圖統(tǒng)計(jì)法，統(tǒng)計(jì)以關(guān)鍵點(diǎn)為原點(diǎn)，一定區(qū)域內(nèi)的圖像像素點(diǎn)對(duì)關(guān)鍵點(diǎn)方向生成所作的貢獻(xiàn)，貢獻(xiàn)最大的那個(gè)方向即為關(guān)鍵點(diǎn)主方向。

關(guān)鍵點(diǎn)的匹配問題，已經(jīng)轉(zhuǎn)為KPD的匹配問題，兩KPD的相似程度，使用歐式距離進(jìn)行計(jì)算。設(shè)有兩個(gè)KPD分別為R = (r1, r2, ..., r128)和S = (s1, s2, ..., s128)，R與S的歐式距離計(jì)算公式為：

d = sqrt((r1 - s1)^2 + (r2 - s2)^2 + ... + (r128 - s128)^2)

所以，要找出兩張不同尺度圖像間的對(duì)應(yīng)點(diǎn)（具有對(duì)應(yīng)關(guān)系的關(guān)鍵點(diǎn)），分下面幾步：

分別檢測(cè)兩張圖像的關(guān)鍵點(diǎn)，并計(jì)算出每個(gè)關(guān)鍵點(diǎn)的KPD，分別得到兩個(gè)KPD集合SET1和SET2

為SET1中每個(gè)KPD，從SET2找最佳匹配（即歐式距離最小的為最佳匹配），然后反過來，為SET2每個(gè)KPD，從SET1中找最佳匹配，只有彼此認(rèn)為是最佳匹配的那些KPD對(duì)才是對(duì)應(yīng)點(diǎn)

為提高匹配準(zhǔn)確率，可以設(shè)定一個(gè)閾值，歐式距離大于此閾值的那些匹配對(duì)，將不考慮。
為提高算法效率，可以使用kd樹和RANSAC（ Random Sample Consensus， 隨機(jī)抽樣一致）方法。

SURF（Speeded Up Robust Features）是對(duì)SIFT的一種改進(jìn)，主要特點(diǎn)是快速。SURF與SIFT主要有以下幾點(diǎn)不同處理：

SIFT在構(gòu)造DOG金字塔以及求DOG局部空間極值比較耗時(shí)，SURF的改進(jìn)是使用Hessian矩陣變換圖像，極值的檢測(cè)只需計(jì)算Hessian矩陣行列式，作為進(jìn)一步優(yōu)化，使用一個(gè)簡(jiǎn)單的方程可以求出Hessian行列式近似值，使用盒狀模糊濾波（box blur）求高斯模糊近似值。

SURF不使用降采樣，通過保持圖像大小不變，但改變盒狀濾波器的大小來構(gòu)建尺度金字塔。

在計(jì)算關(guān)鍵點(diǎn)主方向以及關(guān)鍵點(diǎn)周邊像素方向的方法上，SURF不使用直方圖統(tǒng)計(jì)，而是使用哈爾(haar)小波轉(zhuǎn)換。

SIFT的KPD達(dá)到128維，導(dǎo)致KPD的比較耗時(shí)，SURF使用哈爾(haar)小波轉(zhuǎn)換得到的方向，讓SURF的KPD降到64維，減少了一半，提高了匹配速度。

SIFT算法是有專利的，正規(guī)使用是要交專利費(fèi)的，所以有人提出了一種可作為SIFT替代的算法——ORB，ORB沒有專利問題，考慮到本文篇幅過長(zhǎng)，圖片過多，此算法的介紹和示例將在下一筆記介紹。

可能也是因?yàn)閷＠麊栴}，skimage庫(kù)有ORB算法，但沒有SIFT和SURF。雖然OpenCV都包含了上述算法，但OpenCV目前不在我的學(xué)習(xí)計(jì)劃中。

原書示例使用了一個(gè)第三方實(shí)現(xiàn)的SIFT算法庫(kù)，我認(rèn)為在實(shí)際使用可能價(jià)值不高，另外，書上也沒有介紹ORB（也許是因?yàn)樵趯懘藭鴷r(shí)，ORB還沒有出來），但我認(rèn)為ORB更有研究的必要，因?yàn)闊o專利問題，它將會(huì)是一個(gè)被廣泛使用的算法，所以本文沒有給出SIFT代碼示例，但計(jì)劃在下篇筆記介紹ORB和給出示例。

你還可以看我其它的筆記。

《宋丹 10905056 尺度不變特征變換匹配算法》

《幾種局部圖像特征的提取算法的研究》