Distinctive Image Features from Scale-Invariant Keypoints

Distinctive Image Features from Scale-Invariant Keypoints

David G. Lowe
Computer Science Department
University of British Columbia
Vancouver, B.C., Canada
lowe@cs.ubc.ca
January 5, 2004
=================================================

這篇paper 主要是用 SIFT 當作 feature，然後用這些feature 去作 object finding或是 pattern recognition。

主要可以分為四個部分：
1. scale invariance (SIFT)
2. keypoints Accurate
3. orientation invariance
4. local descriptor
以下會針對這四個部分作說明

1.  scale invariance
paper裡先說明了取SIFT的步驟，如何才能達到 invariant to scale
這個部分有用數學來証明，因此可以說是相當地嚴謹
主要的想法是用space 跟 scale 兩種變化去作 Gaussian convolution
然後找出幾乎不會變化的octave，把這些當作keypoint candidates，這樣就能達到目的
但要決定scale size、space range及 Gaussian Sigma 的範圍在哪裡
paper裡的實驗說明如果取的範圍大就需要花費較多時間
而且某些unstable keypoints 會因為scale size 增加而 mismatch
因此範圍的決定算是一種tradeoff，paper裡有給一些實驗用較好的參數值 ex: σ = 1.6

2. keypoints Accurate
用SIFT 找到 keypoints candidates 後，要過濾掉一些不適合的keypoints
所以要detail 跟neighbor 作比對
這裡有用到 1. 部分取出的 local maxima and minima of the difference-of-Gaussian
利用threshold 去除不適合的 keypoints
paper裡有提到這樣可能會去掉一些有用的information
因為local minima 有可能是因為 low contrast，這樣的算法會受到edge response 影響
所以去掉edge response後再用threshold 去刪掉會比較好

3. orientation invariance
這些過濾之後的 keypoints descriptor 會因為rotation 而找不到
因此paper利用 region around keypoint 來算 orientation histogram
用36 bins 去表示 360°
利用 peak of histogram 來決定rotation 的角度，把它們都轉正(即轉統一的角度)

4. local descriptor
由1 跟 3 我們可以得到 keypoints 的 scale, orientation 及 location 
因此要作 feature fusion
另外paper裡提到 descriptor 可以把原本pixelwise的 image gradients 合併成一個vector
這樣在比對上速度會比較快

之後做了一些實驗在object recognition上
從最基本的keypoint matching 開始
找出跟給定的object 一樣的keypoints
為了要快速找到類似的keypoints 這裡用了一些方法
efficient nearest neighbor indexing (ex: K-D tree)  找出相似的keypoints
clustering with Hough transform 先將keypoints分群再去找

最後結論裡提到SIFT找出keypoints後再作orientation當作feature
可以有效地達到object recognition
也可以用來作object categorize
然後一些像是invariant to color and texture 也可能是之後可以研究很重要的feature

==================================

優點：
1. 取feature，invariant to scale and rotation 這部分的闡述很清楚而且很容易理解
2. 用數學式証明SIFT的一些性質，很有說服力
3. 可以作到object recognition ，甚至被擋住大部分都找得出來

缺點：
1. 實驗用的是gray-level image (在conclusion 這部分有補充)
2. 參數的取法是用實驗作的結果，取比較理想的值，比較ad-hoc，沒有一個直接方法去算出optimal或較好的值
3. paper裡提到可以作object categorize，這部分應該還要再多一些information才有辦法。因為在example裡面，作者有用屋子的牆當object，但卻不會找到另一間屋子的牆。理論上它們的color, texture 及很多pattern都很像(甚至幾乎一樣)，但卻不會被找到，所以作者實驗用的參數及辨識是very strict，這樣用在找"類似"的object時，表現可能不會如預期這麼好。