尺度不變特徵轉換

尺度不變特徵轉換(Scale-invariant feature transform 或 SIFT)是一種機器視覺的演算法用來偵測與描述影像中的局部性特徵，它在空間尺度中尋找極值點，並提取出其位置、尺度、旋轉不變數，此演算法由 David Lowe 在1999年所發表，2004年完善總結。 後續的論文中也有許多基於 SIFT 改進的論文，例如 SURF 將 SIFT 的許多過程近似，達到加速的效果；PCA-SIFT利用主成分分析降低描述子的維度，減少記憶體的使用並加快配對速度。

其應用範圍包含物體辨識、機器人地圖感知與導航、影像縫合、3D模型建立、手勢辨識、影像追蹤和動作比對。

此演算法有其專利，專利擁有者為 英屬哥倫比亞大學。

特徵

局部影像特徵的描述與偵測可以幫助辨識物體，SIFT 特徵是基於物體上的一些局部外觀的興趣點而與影像的大小和旋轉無關。 對於光線、雜訊、些微視角改變的容忍度也相當高。基於這些特性，它們是高度顯著而且相對容易擷取，在母數龐大的特徵資料庫中，很容易辨識物體而且鮮有誤認。

使用 SIFT 特徵描述對於部分物體遮蔽的偵測率也相當高，甚至只需要3個以上的 SIFT 物體特徵就足以計算出位置與方位。

在現今的電腦硬體速度下和小型的特徵資料庫條件下，辨識速度可接近即時運算。

SIFT 特徵的信息量大，適合在大量資料庫中快速準確匹配。

演算法

尺度空間的極值偵測

在這個階段，主要是偵測興趣點，也就是SIFT架構中的關鍵點。 影像在不同的尺度下用高斯濾波器(Gaussian filters)進行卷積(convolved)，然後利用連續高斯模糊化影像差異來找出關鍵點。關鍵點是根據不同尺度下的高斯差(Difference of Gaussians,DoG)的最大最小值。 也就是說，DoG影像的$D\left(x,y,\sigma \right)$ 是由:

$D\left(x,y,\sigma \right)=L\left(x,y,k_{i}\sigma \right)-L\left(x,y,k_{j}\sigma \right)$

$L\left(x,y,k\sigma \right)$ 是在尺度 $k\sigma$的條件下，由原始影像$I\left(x,y\right)$與高斯模糊$G\left(x,y,k\sigma \right)$進行卷積，例如 :$L\left(x,y,k\sigma \right)=G\left(x,y,k\sigma \right)*I\left(x,y\right)$

$G\left(x,y,k\sigma \right)$ 是尺度可變高斯函數 $G\left(x,y,\sigma \right)={\frac {1}{2\pi \sigma ^{2}}}e^{-(x^{2}+y^{2})/2\sigma ^{2}}$

由上式可知DoG影像是原始影像與不同尺度倍率$k_{i}\sigma$、$k_{j}\sigma$的高斯模糊後之差值。 SIFT演算法為了求得在不同尺度倍率之下DoG影像的極大值，先將原始影像與不同尺度倍率的高斯模糊進行卷積，這些經高斯模糊處理後的影像依其尺度倍率以2倍為一單位分組，並且$k_{i}\sigma$通常為一個選定後的定值，因此在每一組內經高斯模糊處理後的影像數量相同，此時將同一組相鄰的經高斯模糊處理後的影像兩兩相減可得其DoG影像。

一旦得到DoG影像後，可找出DoG影像中的極大、極小值作為關鍵點。為了決定關鍵點，DoG影像中的每個像素會跟以自己為中心周圍的八個像素，以及在同一組DoG影像中相鄰尺度倍率相同位置的九個像素作，一共二十六個點作比較，若此像素為這二十六個像素中的最大、最小值，則此稱此像素為關鍵點。

SIFT演算法中關鍵點的偵測是一種斑點檢測(Blob detection)的一種變形，也就是使用拉普拉斯運算元來求出各個倍率及空間中的最大值。高斯差可近似為拉普拉斯運算元運算後的結果，因建立高斯金字塔的過程是一種尺寸正規化拉普拉斯運算的近似。

關鍵點定位

在不同尺寸空間下可能找出過多的關鍵點，有些關鍵點可能相對不易辨識或易受雜訊干擾。SIFT演算法的下一步將會藉由關鍵點附近像素的資訊、關鍵點的尺寸、關鍵點的主曲率來定位各個關鍵點，藉此消除位於邊上或是易受雜訊干擾的關鍵點

鄰近資料插補

對於各個可能的關鍵點，插補鄰近資料可決定其位置。最一開始的方法為紀錄各個關鍵點在圖片中的位置與尺度。

而新開發出來的方法指出，計算極值得差補位置更能夠提供配對的準確度及可靠性，此方法使用DoG影像$D\left(x,y,\sigma \right)$的二次泰勒級數，並以關鍵點作為原點，其展開式可寫成:

$D({\textbf {x}})=D+{\frac {\partial D^{T}}{\partial {\textbf {x}}}}{\textbf {x}}+{\frac {1}{2}}{\textbf {x}}^{T}{\frac {\partial ^{2}D}{\partial {\textbf {x}}^{2}}}{\textbf {x}}$

其中D與其偏微分的值由關鍵點的位置決定，變數${\textbf {x}}=\left(x,y,\sigma \right)$則是到此關鍵點的偏移量。

將上式對${\textbf {x}}$ 微分後設為零，便可求出極值${\hat {\textbf {x}}}$的位置。若${\hat {\textbf {x}}}$的任一項參數大於0.5，代表此時有另一關鍵點更接近極值，將捨棄此關鍵點並對新的點作插補。反之若所有參數皆小於0.5，此時將偏移量加回關鍵點中找出極值的位置。

捨棄不明顯關鍵點

此步驟將計算上述二次泰勒級數$D({\textbf {x}})$在${\hat {\textbf {x}}}$的值。若此值小於0.03，則捨棄此關鍵點。反之保留此關鍵點，並記錄其位置為${\textbf {y}}+{\hat {\textbf {x}}}$，其中${\textbf {y}}$是一開始關鍵點的位置。

消除邊緣響應

DoG函數對於偵測邊緣上的點相當敏感，即使其找出位於邊緣的關鍵點易受雜訊干擾也會被偵測為關鍵點。 因此為了增加關鍵點的可靠性，需要消除有高度邊緣響應但其位置不佳不符合需求的關鍵點。

為了找出邊緣上的點，可分別計算關鍵點的主曲率，對於在邊上的關鍵點而言，因為穿過邊緣方向的主曲率會遠大於沿著邊緣方向上的主曲率，因此其主曲率比值遠大於位於角落的比值。

為了算出關鍵點的主曲率，可解其二次海森矩陣矩陣的特徵值:

${\textbf {H}}={\begin{bmatrix}D_{xx}&D_{xy}\\D_{xy}&D_{yy}\end{bmatrix}}$

其特徵值的比例與特徵點主曲率的比例相同，因此假設解出的特徵值為$\alpha$、$\beta$，其中$\alpha >\beta$。在上述矩陣中:

$\operatorname {Tr} ({\textbf {H}})=D_{xx}+D_{yy}=\alpha +\beta$

$\operatorname {Det} ({\textbf {H}})=D_{xx}D_{yy}-D_{xy}^{2}=\alpha \beta$

因此

${\text{R}}=\operatorname {Tr} ({\textbf {H}})^{2}/\operatorname {Det} ({\textbf {H}})=(r+1)^{2}/r$

其中$r=\alpha /\beta$。由此可知當R越大，$\alpha$、$\beta$的比例越大，此時設定一閾值$r_{\text{th}}$，若R大於$(r_{\text{th}}+1)^{2}/r_{\text{th}}$表示此關鍵點位置不合需求因此可以去除。

一般來說，設定閾值$r_{\text{th}}=10$

方位定向

在方位定向中，關鍵點以相鄰像素的梯度方向分佈作為指定方向參數，使關鍵點描述子能以根據此方向來表示並具備旋轉不變性。

經高斯模糊處理後的影像$L\left(x,y,\sigma \right)$，在$\sigma$尺寸下的梯度量$m\left(x,y\right)$與方向$\theta \left(x,y\right)$可由相鄰之像素值計算:

$m\left(x,y\right)={\sqrt {\left((L\left(x+1,y\right)-L\left(x-1,y\right)\right)^{2}+\left((L\left(x,y+1\right)-L\left(x,y-1\right)\right)^{2}}}$

$\theta \left(x,y\right)=arctan((L(x,y-1)-L(x,y+1))/(L(x-1,y)-L(x+1,y)))$

計算每個關鍵點與其相鄰像素之梯度的量值與方向後，為其建立一個以10度為單位36條的直方圖。每個相鄰像素依據其量值大小與方向加入關鍵點的直方圖中，最後直方圖中最大值的方向即為此關鍵點的方向。若最大值與局部極大值的差在20%以內，則此判斷此關鍵點含有多個方向，因此將會再額外建立一個位置、尺寸相同方向不同的關鍵點。

針對最後算出的方向還有許多優化步驟，為了符合人體的視覺感官，在加入梯度量值到直方圖時會乘以距離權重(高斯函數)，以減低離關鍵點較遠的影響程度。為了增加角度的解析度，不同角度在加入值方圖時也需考量線性的權重，依照其角度偏移各區間平均值的量，照比例分配於兩個區間內。最後可將值方圖以差補的方式求得某個特定的角度值，而非一固定的區間。

關鍵點描述子

找到關鍵點的位置、尺寸並賦予關鍵點方向後，將可確保其移動、縮放、旋轉的不變性。此外還需要為關鍵點建立一個描述子向量，使其在不同光線與視角下皆能保持其不變性，並且能夠輕易與其他關鍵點作區分。

為了使描述子在不同光線下保有不變性，需將描述子正規化為一128維的單位向量。 首先每個4*4的子區域內建立一個八方向的直方圖，且在關鍵點周圍16*16的區域中——共4*4個子區域，計算每個像素的梯度量值大小與方向後加入此子區域的直方圖中，共可產生一個128維的資料——16個子區域*8個方向。此外為了減少非線性亮度的影響，把大於0.2的向量值設為0.2，最後將正規化後的向量乘上256，且以8位元無號數儲存，可有效減少儲存空間。

應用

利用SIFT特徵進行物體辨識

SIFT能夠找出獨特的關鍵點，此關鍵點不會受移動、轉動、縮放、仿射變換、亮度等外在因素的影響而改變其特性。因此能夠有效應用在物體辨識上，其步驟包含：

• 輸入偵測物，並執行SIFT演算法找出輸入影像中不變的特徵。

• 這些特徵會與SIFT特徵資料庫作描述子配對，配對將透過最近鄰居法來完成。為了增加可信度，將會移除最近距離與第二近距離大於0.8的配對，這將能夠有效移除背景造成的錯誤配對。此外為了提升最近鄰居法的計算速度，應用best-bin-first演算法能夠有夠高機率找出最近的距離並加快搜尋速度。

• 去除錯誤的配對後，仍有不同物體的成功配對，因此需將成功的配對加以分類，將相同物體的分類分在一起並移除不同物體的分類，因此應用了霍夫變換。如此一來便能夠辨認擁有相同角度的特徵點，這些特徵點有很高機率是同一個物件的，因此能夠分出各個特徵群。

• 對於每個被挑選出來的特徵群，使用最小平方法求得輸入影像與訓練資料間最佳的仿射變換參數。運用此參數對各個特徵點作比對，調整參數直到特徵點皆能正確仿射沒有錯誤發生為止。

全景圖縫合

SIFT的特徵匹配可以用於圖像縫合，用於對非全景圖的全自動全景重建。從輸入圖像中提取出來的SIFT特徵能夠通過每一個圖像的特徵匹配K個最近相鄰圖像。隨後，這種對應關係可以用於對每一個圖像尋找m個候選匹配圖像。匹配圖像間的單應性（Homographies）可以通過使用隨機抽樣一致（RANSAC）來得出。由於對於輸入圖像沒有限制，圖像的搜索應用於匹配圖像對的連接部分。因此每一個連接部分都將會對全景圖的構建產生影響。最後，對於所有的連接部分，可以使用光束法平差（Bundle adjustment）來連結照相參數，於是全景圖就可以通過多頻段混合來描繪出來。由於SIFT啟發了全景圖拼接的目標識別方法，拼接結果的系統將會對於順序，方向，尺度和圖像亮度不敏感。在這裡，輸入圖像可以包含多個全景和噪聲圖像，全景序列將會作為結果被識別和描繪。

外部連結

• Sebastian Nowozin (C#)
• Andrea Vedaldi (Matlab/C)
• Andrea Vedaldi (C++)
• David Lowe (C/Matlab) （頁面存檔備份，存於網際網路檔案館）
• Rob Hess (C)
• Dr Krystian Mikolajczyk (C) （頁面存檔備份，存於網際網路檔案館）
• Stephan Saalfeld (Java)
• Adam Chapman / ChangChang Wu (Matlab-GPU implementation) （頁面存檔備份，存於網際網路檔案館）
• Integrating Vision Toolkit (C++) （頁面存檔備份，存於網際網路檔案館） (folder IVT/src/Features/SIFTFeatures, by Pedram Azad and Lars Pätzold)
• libsiftfast (Matlab/C++) （頁面存檔備份，存於網際網路檔案館） 針對x86 SSE 指令集最佳化並使用OpenMP進行多核心運算. (提供Linux, Windows, 和 Mac 版本). LGPL （頁面存檔備份，存於網際網路檔案館）授權
• lip-vireo （頁面存檔備份，存於網際網路檔案館） (Linux 和Windows 版本)
• SIXT Scale Invariant Something Transform