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

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

獨特性（Distinctiveness）好，信息量豐富，適用于在海量特征數據庫中進行快速、準確的匹配；

多量性，即使少數的幾個物體也可以產生大量的SIFT特征向量；

高速性，經優化的SIFT匹配算法甚至可以達到實時的要求；

可擴展性，可以很方便的與其他形式的特征向量進行聯合。

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

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

SIFT算法要點

降采樣

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

高斯差分算子(Difference of Gaussians，簡稱DOG)

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

Gσ = Bkσ - Bσ

Gσ為DOG圖像，它包含的特征是目標的輪廓。

SIFT先對降采樣后的每張圖像使用不同的sigma進行高斯模糊，結果是每個降采樣圖像對應一組模糊圖像：

然后對每組模糊圖像的相鄰圖像作DOG，結果是每個降采樣圖像對應一組DOG圖像，如圖：

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

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

關鍵點檢測

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

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

關鍵點描述

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

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

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

對每個小格進行統計，統計8個方向的幅度，形成幅度直方圖：

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

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

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

可采用梯度直方圖統計法，統計以關鍵點為原點，一定區域內的圖像像素點對關鍵點方向生成所作的貢獻，貢獻最大的那個方向即為關鍵點主方向。

關鍵點匹配

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

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

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

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

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

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

SURF

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

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

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

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

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

小結

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

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

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

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

總結

以上是生活随笔為你收集整理的Programming Computer Vision with Python （学习笔记十一）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。