尺度不變特徵轉換

尺度不變特徵轉換(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影像的formula_1 是由:formula_2formula_3 是在尺度 formula_4的條件下，由原始影像formula_5與高斯模糊formula_6進行卷積，例如 :formula_7formula_6 是尺度可變高斯函式 formula_9由上式可知DoG影像是原始影像與不同尺度倍率formula_10、formula_11的高斯模糊後之差值。SIFT演演算法為了求得在不同尺度倍率之下DoG影像的極大值，先將原始影像與不同尺度倍率的高斯模糊進行卷積，這些經高斯模糊處理後的影像依其尺度倍率以2倍為一單位分組，並且formula_10通常為一個選定後的定值，因此在每一組內經高斯模糊處理後的影像數量相同，此時將同一組相鄰的經高斯模糊處理後的影像兩兩相減可得其DoG影像。一旦得到DoG影像後，可找出DoG影像中的極大、極小值作為關鍵點。為了決定關鍵點，DoG影像中的每個畫素會跟以自己為中心周圍的八個畫素，以及在同一組DoG影像中相鄰尺度倍率相同位置的九個畫素作，一共二十六個點作比較，若此畫素為這二十六個畫素中的最大、最小值，則此稱此畫素為關鍵點。SIFT演演算法中關鍵點的偵測是一種斑點檢測(Blob detection)的一種變形，也就是使用拉普拉斯運算元來求出各個倍率及空間中的最大值。高斯差可近似為拉普拉斯運算元運算後的結果，因建立高斯金字塔的過程是一種尺寸正規化拉普拉斯運算的近似。關鍵點定位.在不同尺寸空間下可能找出過多的關鍵點，有些關鍵點可能相對不易辨識或易受雜訊幹擾。SIFT演演算法的下一步將會藉由關鍵點附近畫素的資訊、關鍵點的尺寸、關鍵點的主曲率來定位各個關鍵點，藉此消除位於邊上或是易受雜訊幹擾的關鍵點鄰近資料插補.對於各個可能的關鍵點，插補鄰近資料可決定其位置。最一開始的方法為紀錄各個關鍵點在圖片中的位置與尺度。而新開發出來的方法指出，計算極值得差補位置更能夠提供配對的準確度及可靠性，此方法使用DoG影像formula_1的二次泰勒級數，並以關鍵點作為原點，其展開式可寫成:formula_14其中D與其偏微分的值由關鍵點的位置決定，變數formula_15則是到此關鍵點的偏移量。將上式對formula_16 微分後設為零，便可求出極值formula_17的位置。若formula_17的任一項引數大於0.5，代表此時有另一關鍵點更接近極值，將捨棄此關鍵點並對新的點作插補。反之若所有引數皆小於0.5，此時將偏移量加回關鍵點中找出極值的位置。捨棄不明顯關鍵點.此步驟將計算上述二次泰勒級數formula_19在formula_17的值。若此值小於0.03，則捨棄此關鍵點。反之保留此關鍵點，並記錄其位置為formula_21，其中formula_22是一開始關鍵點的位置。消除邊緣響應.DoG函式對於偵測邊緣上的點相當敏感，即使其找出位於邊緣的關鍵點易受雜訊幹擾也會被偵測為關鍵點。因此為了增加關鍵點的可靠性，需要消除有高度邊緣響應但其位置不佳不符合需求的關鍵點。為了找出邊緣上的點，可分別計算關鍵點的主曲率，對於在邊上的關鍵點而言，因為穿過邊緣方向的主曲率會遠大於沿著邊緣方向上的主曲率，因此其主曲率比值遠大於位於角落的比值。為了算出關鍵點的主曲率，可解其二次海森矩陣矩陣的特徵值:formula_23其特徵值的比例與特徵點主曲率的比例相同，因此假設解出的特徵值為formula_24、formula_25，其中formula_26。在上述矩陣中:formula_27formula_28因此formula_29其中formula_30。由此可知當R越大，formula_24、formula_25的比例越大，此時設定一閾值formula_33，若R大於formula_34表示此關鍵點位置不合需求因此可以去除。一般來說，設定閾值formula_35方位定向.在方位定向中，關鍵點以相鄰畫素的梯度方向分佈作為指定方向引數，使關鍵點描述子能以根據此方向來表示並具備旋轉不變性。經高斯模糊處理後的影像formula_36，在formula_37尺寸下的梯度量formula_38與方向formula_39可由相鄰之畫素值計算:formula_40formula_41計算每個關鍵點與其相鄰畫素之梯度的量值與方向後，為其建立一個以10度為單位36條的直方圖。每個相鄰畫素依據其量值大小與方向加入關鍵點的直方圖中，最後直方圖中最大值的方向即為此關鍵點的方向。若最大值與區域性極大值的差在20%以內，則此判斷此關鍵點含有多個方向，因此將會再額外建立一個位置、尺寸相同方向不同的關鍵點。針對最後算出的方向還有許多最佳化步驟，為了符合人體的視覺感官，在加入梯度量值到直方圖時會乘以距離權重(高斯函式)，以減低離關鍵點較遠的影響程度。為了增加角度的解析度，不同角度在加入值方圖時也需考量線性的權重，依照其角度偏移各區間平均值的量，照比例分配於兩個區間內。最後可將值方圖以差補的方式求得某個特定的角度值，而非一固定的區間。關鍵點描述子.找到關鍵點的位置、尺寸並賦予關鍵點方向後，將可確保其移動、縮放、旋轉的不變性。此外還需要為關鍵點建立一個描述子向量，使其在不同光線與視角下皆能保持其不變性，並且能夠輕易與其他關鍵點作區分。為了使描述子在不同光線下保有不變性，需將描述子正規化為一128維的單位向量。首先每個4*4的子區域內建立一個八方向的直方圖，且在關鍵點周圍16*16的區域中——共4*4個子區域，計算每個畫素的梯度量值大小與方向後加入此子區域的直方圖中，共可產生一個128維的資料——16個子區域*8個方向。此外為了減少非線性亮度的影響，把大於0.2的向量值設為0.2，最後將正規化後的向量乘上256，且以8位元無號數儲存，可有效減少儲存空間。應用.利用SIFT特徵進行物體辨識.SIFT能夠找出獨特的關鍵點，此關鍵點不會受移動、轉動、縮放、仿射變換、亮度等外在因素的影響而改變其特性。因此能夠有效應用在物體辨識上，其步驟包含：全景圖縫合.SIFT的特徵匹配可以用於影象縫合，用於對非全景圖的全自動全景重建。從輸入影象中提取出來的SIFT特徵能夠透過每一個影象的特徵匹配K個最近相鄰影象。隨後，這種對應關係可以用於對每一個影象尋找m個候選匹配影象。匹配影象間的單應性來連結照相引數，於是全景圖就可以透過多頻段混合來描繪出來。由於SIFT啟發了全景圖拼接的目標識別方法，拼接結果的系統將會對於順序，方向，尺度和影象亮度不敏感。在這裡，輸入影象可以包含多個全景和噪聲影象，全景序列將會作為結果被識別和描繪。