SIFT 全名為 Scale-Invariant Feature Transform,具有 scale-invariant 的特性,在找到 feature 之後,可以產生相對的 feature descriptor,供不同的影像間作 feature matching。

前面章節所介紹的 Harris Corner ,它具有 rotation-invariant 的特性,也就是說,即使影像旋轉了,還是可以找到相同的 feature,因為 corner 旋轉之後還是 corner,但,如果是放大、縮小呢? Corner 經過放大、縮小之後,由相同的演算法來計算,未必會仍然判斷為 corner,如下圖所示,所以 Harris Corner 不算是 scale-invariant。


SIFT 在 2004 年被提出來,具有 scale-invariant 的特性,用來取出 feature 並計算其 descriptor。

在 SIFT 演算法中,主要步驟如下:

1,Scale-space Extrema Detection

由上面 corner 的例子來看,對於不同大小的 corner 需要有不同大小的 window 來作偵測,這時就需要 scale-space filtering。
LoG (Laplacian of Gaussian) 可以用來在不同大小的影像中作 blob 的偵測,σ為 scaling parameter。舉例來說,在上圖中,小 corner 的 σ會比較小,而大的 σ值就適用於大 corner。

但由於 LoG 的計算量很大,改用 Difference of Gaussians 來取代,可以得到和 LoG 近似的結果;Difference of Gaussian 可以由同一張影像經過 σ及 kσ 的 Gaussian blurring 後取得,整個過程可以透過 Gaussian Pyramid 完成,如下圖:


在 DoG 建立完成後,local extrema 會在不同的 scale 及 space 中被搜尋,例如該像素會跟相鄰的8個像素以及上一個 scale 及下一個 scale 附近共 18 個像素比較,如果該像素的值是 local extrema ,則該區域為 potential keypoint,相關需要比較的像素位置如下圖:


論文中的相關參數經驗值為: octaves = 4, number of scale levels = 5, 初始值 σ= 1.6, k = sqrt(2)。


2, Keypoint Localization

搜尋完影像中的 potential keypoint 後,再利用 Taylor series expansion of scale space 得到 extrema 的更精確位置,而且如果 intensity of extrema 的值小於某個 threshold (論文中的值為 0.03),該 keypoint 將被剔除。這個 threshold 在 OpenCV也被稱為 contrastThreshold。

DoG 會把 edge 算進 potential keypoint,為了要移除這些 edge,會計算該 potential keypoint 的 eigen value,如果他們之間的比值超過 edgeThreshold,則該 keypoint 將被剔除,在論文中 edgeThreshold = 10。

到此,剔除了低對比 及 edge 的 keypoint,剩下來的,就是所需要的 feature point。


3, Orientation Assignment

為了要達到 rotation-invariant,要提供 orientation 給每個 keypoint,在該 keypoint 會以它周邊的像素來計算各個像素的 gradient magnitude 及 gradient direction,把 gradient direction 分成 36 種,間隔為 10°,經過累加後,找出 gradient direction 強度最強的那個方向,即為該 keypoint 的 orientation,若有其它 gradient direction 超過強度最強的 80%,則該 gradient direction 也會被納入,成為計算該 keypoint 的 orientation 的參考。

4, Keypoint Descriptor

先將在該 keypoint 周圍 16 x 16 區域的像素點,分成 16 個 4x4 的子區塊,對於每個子區塊再分別計算它們的 8 bin orientation,所以總共有 8 x 16 = 128 個 bin values,由這些值構成的向量,即為 keypoint descriptor。


補充:這 128 個 bin value,的紀錄順序可能會以第三步驟所計算的 orientation 作為根據,以達到 rotation-invariant。


5, Keypoint Matching

在兩張影像中,如果要在第二張影像搜尋第一張影像的某個 keypoint,其搜尋方式就是透過該 keypoint 的 descriptor 與第二張影像的所有 keypoints 的 descriptors 來計算距離,通常距離最近的,即為相同的 keypoint,但如果最近距離與第二近距離的比值大於 0.8,則捨棄該 keypoint,因為誤判的機率很大,該作法可以減少 90% 的誤判,然而代價是同時有 5% 的機會捨棄已經正確搜尋到的 keypoints。


有關影像的 gradient magnitude 及 gradient direction 可以參考:
Gradient Magnitude & Gradient Direction




Reference

Introduction to SIFT
What is gradient orientation and gradient magnitude
counting non directional edges from canny

文字內容 或 影像內容 部份參考、引用自網路,如有侵權,請告知,謝謝。
創作者介紹

拾人牙慧點滴

silverwind1982 發表在 痞客邦 PIXNET 留言(0) 人氣()