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:

	SIFT	SURF
特征点检测	用不同尺度的图片与高斯函数做卷积	用不同大小的box filter与原始图像(integral image)做卷积，易于并行
方向	特征点邻接矩形区域内，利用梯度直方图计算	特征点邻接圆域内，计算x、y方向上的Haar小波响应
描述符生成	20*20(单位为pixel)区域划分为4*4(或2*2)的子区域，每个子域计算8bin直方图	20*20(单位为sigma)区域划分为4*4子域，每个子域计算5*5个采样点的Haar小波响应，记录∑dx, ∑dy, ∑|dx|,∑|dy|。

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内点概率，图片库来自这里。下面是大体赛况，您可以搜索"A comparison of SIFT, PCA-SIFT and SURF"看直播。

method	Time	Scale	Rotation	Blur	Illumination	Affine
Sift	common	best	best	common	common	good
PCA-sift	good	good	good	best	good	best
Surf	best	common	common	good	best	good

另外，SIFT、SURF也分别有了GPU实现，欢迎一起探讨学习！

SIFT on GPU, S.Heymann, 2005

SIFT on GPU(2), Sudipta N.Sinha, 2006

SURF on GPU, Nico Cornelis, 2008

此外，cy513的"SIFT/SURF算法的深入剖析——谈SIFT的精妙与不足"写地很棒，链过去方便大家阅读。