談談SIFT、PCA

SIFT(Scale-invariant feature transform), Lowe, 2004

PCA-SIFT(Principle Component Analysis), Y.ke, 2004

SURF(Speeded Up Robust Features), Bay, 2006

這三位先后登場各有千秋，算是圖像特征點檢測領域的宋氏三姐妹了！SIFT鼻祖先宗大佬，PCA-SIFT將SIFT中直方圖方法換作主元分析法，SURF取出integral/Hessian兩樣法寶實現加速，也更易于并行。

下面，先整理SIFT思路：

1.       輸入圖像，建議做double(width*=2, height*=2, size*=4), 并高斯過濾進行平滑。

2.       由圖片size決定建幾個塔，每塔幾層圖像(一般3-5層)。0塔的第0層是原始圖像(或你double后的圖像)，往上每一層是對其下一層進行Laplacian變換（高斯卷積，其中sigma值漸大，例如可以是sigma, k*sigma, k*k*sigma…），直觀上看來越往上圖片越模糊。塔間的圖片是降采樣關系，例如1塔的第0層可以由0塔的第3層down sample得到，然后進行與0塔類似的高斯卷積操作。

3.       構建DoG金字塔。DoG金字塔由上一步生成的Gauss金字塔計算得到，塔數相同，每塔層數少1，因為DoG的每一層由Gauss的相鄰兩層相減得到。

4.       在DoG塔里進行極值點檢測，并根據用戶預設的對比度閾值、主曲率閾值去除不合法特征點。極值點檢測用的Non-Maximal Suppression，即在3*3*3個點中進行灰度值比較，最小或最大才過關。

5.       計算每個特征點的尺度。注意塔間尺度關系，sigma*2.0^(octvs+intvl/intvls)

6.       計算每個特征點的梯度模值和方向。用特征點周圍一個矩陣區域(patch)內的點來描述該特征點，用的直方圖進行模值統計并尋找主方向，主方向可以不止一個。

7.       最后要生成64D或128D的特征描述符了。對齊主方向，計算方向直方圖2D數組，假如每個直方圖有8bin，那么64D(2*2*8bin)或128D(4*4*8bin)。

大面兒上說，SURF vs. SIFT:

SURF基于integral image，利用determination of Hessian matrix來描述極值點，也就是可能的特征點。那么什么是積分圖像？在這里Hessian矩陣又是什么？怎么求得這個det(H)？它怎么樣了就是極值點了？box filter是怎么來地，什么樣兒？這里有相關文檔和源碼下載，很詳細很清晰，這里我就不八了，您佬哪里不明白，跟帖交流。我比較好奇的是，Bay是如何發現integral image * box filter與高斯卷積這層近似關系的？為什么他會想到這么做？此外，基于integral image * Haar wavelet filter進行主方向的判定及描述符的生成，這樣的卷積結果是什么？又說明了什么？是一種與鄰接點差異或變化率的反映？Integral image is so fabulous。有興趣的朋友一起討論一下？

Luo Juan對這三種算法進行了實驗比較，衡量參數有Processing time/ scale / changes/ rotation/ blur/ illumination/ affine，衡量指標有重復度或RANSAC內點概率，圖片庫來自

此外，cy513的"