尺度不變特征轉換(SIFT)---轉自維基百科

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

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

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

目錄

• 1特征
• 2算法
  • 2.1尺度空間的極值偵測
  • 2.2關鍵點定位
    • 2.2.1鄰近資料插補
    • 2.2.2舍棄不明顯關鍵點
    • 2.2.3消除邊緣響應
  • 2.3方位定向
  • 2.4關鍵點描述子
• 3應用
  • 3.1利用SIFT特征進行物體辨識
  • 3.2機器人地圖感覺與導航
  • 3.3全景圖縫合
  • 3.43D掃描模組化,辨識,追蹤
  • 3.5利用3D SIFT特征進行人類行為辨識
• 4參考資料
• 5外部連結

特征

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

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

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

SIFT特征的資訊量大，适合在大量資料庫中快速準确比對。

算法

尺度空間的極值偵測

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

 是由:

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

{\displaystyle L\left(x,y,k\sigma \right)}

 是在尺度  {\displaystyle k\sigma }

的條件下，由原始影像 {\displaystyle I\left(x,y\right)}

與高斯模糊 {\displaystyle G\left(x,y,k\sigma \right)}

進行卷積，例如 : {\displaystyle L\left(x,y,k\sigma \right)=G\left(x,y,k\sigma \right)*I\left(x,y\right)}

{\displaystyle G\left(x,y,k\sigma \right)}

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

由上式可知DoG影像是原始影像與不同尺度倍率{\displaystyle k_{i}\sigma }

、{\displaystyle k_{j}\sigma }

的高斯模糊後之內插補點。 SIFT算法為了求得在不同尺度倍率之下DoG影像的極大值，先将原始影像與不同尺度倍率的高斯模糊進行卷積，這些經高斯模糊處理後的影像依其尺度倍率以2倍為一機關分組，并且{\displaystyle k_{i}\sigma }

通常為一個標明後的定值，是以在每一組内經高斯模糊處理後的影像數量相同，此時将同一組相鄰的經高斯模糊處理後的影像兩兩相減可得其DoG影像。

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

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

關鍵點定位

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

鄰近資料插補

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

而新開發出來的方法指出，計算極值得差補位置更能夠提供配對的準确度及可靠性，此方法使用DoG影像{\displaystyle D\left(x,y,\sigma \right)}

的二次泰勒級數，并以關鍵點作為原點，其展開式可寫成:

{\displaystyle 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與其偏微分的值由關鍵點的位置決定，變數{\displaystyle {\textbf {x}}=\left(x,y,\sigma \right)}

則是到此關鍵點的偏移量。

将上式對{\displaystyle {\textbf {x}}}

 微分後設為零，便可求出極值{\displaystyle {\hat {\textbf {x}}}}

的位置。若{\displaystyle {\hat {\textbf {x}}}}

的任一項參數大于0.5，代表此時有另一關鍵點更接近極值，将舍棄此關鍵點并對新的點作插補。反之若所有參數皆小于0.5，此時将偏移量加回關鍵點中找出極值的位置。

舍棄不明顯關鍵點

此步驟将計算上述二次泰勒級數{\displaystyle D({\textbf {x}})}

在{\displaystyle {\hat {\textbf {x}}}}

的值。若此值小于0.03，則舍棄此關鍵點。反之保留此關鍵點，并記錄其位置為{\displaystyle {\textbf {y}}+{\hat {\textbf {x}}}}

，其中{\displaystyle {\textbf {y}}}

是一開始關鍵點的位置。

消除邊緣響應

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

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

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

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

其特征值的比例與特征點主曲率的比例相同，是以假設解出的特征值為{\displaystyle \alpha }

、{\displaystyle \beta }

，其中{\displaystyle \alpha >\beta }

。在上述矩陣中:

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

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

是以

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

其中{\displaystyle r=\alpha /\beta }

。由此可知當R越大，{\displaystyle \alpha }

、{\displaystyle \beta }

的比例越大，此時設定一門檻值{\displaystyle r_{\text{th}}}

，若R大于{\displaystyle (r_{\text{th}}+1)^{2}/r_{\text{th}}}

表示此關鍵點位置不合需求是以可以去除。

一般來說，設定門檻值{\displaystyle r_{\text{th}}=10}

方位定向

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

經高斯模糊處理後的影像{\displaystyle L\left(x,y,\sigma \right)}

，在{\displaystyle \sigma }

尺寸下的梯度量{\displaystyle m\left(x,y\right)}

與方向{\displaystyle \theta \left(x,y\right)}

可由相鄰之像素值計算:

{\displaystyle 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}}}}

{\displaystyle \theta \left(x,y\right)=\mathrm {atan2} \left(L\left(x,y+1\right)-L\left(x,y-1\right),L\left(x+1,y\right)-L\left(x-1,y\right)\right)}

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

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

關鍵點描述子

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

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

應用

利用SIFT特征進行物體辨識

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

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

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

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

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

機器人地圖感覺與導航

全景圖縫合

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

3D掃描模組化,辨識,追蹤

利用3D SIFT特征進行人類行為辨識

參考資料

1. ^ Lowe, David G. Object recognition from local scale-invariant features. Proceedings of the International Conference on Computer Vision: 1150–1157. 1999. doi:10.1109/ICCV.1999.790410.
2. ^ Nowozin, Sebastian. autopano-sift. 2005 [2008-08-20].

外部連結

• 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

說明：中文版的維基百科由于某些原因無法正常通路，而其中有些内容還是很好的，是以我就轉載到CSND上，友善大家檢視。