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

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

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

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

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

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

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

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

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

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

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

Gσ = Bkσ - Bσ

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

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

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

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

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

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

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

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

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

將16x16矩形圖像劃分為16小格，每小格為4x4，并計算每個像素的梯度和幅度（即像素值變化的方向及大?。?br>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

可能也是因為專利問題，skimage庫有ORB算法，但沒有SIFT和SURF。雖然OpenCV都包含了上述算法，但OpenCV目前不在我的學(xué)習(xí)計劃中。

原書示例使用了一個第三方實現(xiàn)的SIFT算法庫，我認(rèn)為在實際使用可能價值不高，另外，書上也沒有介紹ORB（也許是因為在寫此書時，ORB還沒有出來），但我認(rèn)為ORB更有研究的必要，因為無專利問題，它將會是一個被廣泛使用的算法，所以本文沒有給出SIFT代碼示例，但計劃在下篇筆記介紹ORB和給出示例。

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

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

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