尺度不變特徵轉換

尺度不變特徵轉換(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影像的 是由:

是在尺度 的條件下，由原始影像 與高斯模糊 進行卷積，例如: 。

是尺度可變高斯函數。

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

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

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

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

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

經高斯模糊處理后的影像，在 尺寸下的梯度量 與方向 可由相鄰之像素值計算:

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

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

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

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

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

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

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

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

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

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