经典算法研究系列：九、SIFT算法研究
作者:July、二零一一年二月十五日。
推荐阅读：David G. Lowe, "Distinctive image features from scale-invariant keypoints," International Journal of Computer Vision, 60, 2 (2004), pp. 91-110———————————————
尺度不变特征转换(Scale-invariant feature transform 或 SIFT)是一种电脑视觉的算法用来侦测与描述影像中的局部性特征，它在空间尺度中寻找极值点，并提取出其位置、尺度、旋转不变量，此算法由 David Lowe 在1999年所发表，2004年完善总结。
Sift算法就是用不同尺度（标准差）的高斯函数对图像进行平滑，然后比较平滑后图像的差别，差别大的像素就是特征明显的点。
一、Sift算法的步骤Sift（Scale Invariant Feature Transform）是一个很好的图像匹配算法，同时能处理亮度、平移、旋转、尺度的变化，利用特征点来提取特征描述符，最后在特征描述符之间寻找
匹配。该算法主要包括5个步骤进行匹配：1、构建尺度空间，检测极值点，获得尺度不变性；
2、特征点过滤并进行精确定位，剔除不稳定的特征点；
3、在特征点处提取特征描述符，为特征点分配方向值；
4、生成特征描述子，利用特征描述符寻找匹配点；以特征点为中心取16*16的邻域作为采样窗口，将采样点与特征点的相对方向通过高斯加权后归入包含8个bin的方向直方图，最后获得4*4*8的128维特征描述子。示意图如下：
5、计算变换参数。当两幅图像的Sift特征向量生成以后，下一步就可以采用关键点特征向量的欧式距离来作为两幅图像中
关键点的相似性判定度量。取图1的某个关键点，通过遍历找到图像2中的距离最近的两个关键点。在这两个关键点中，如果次近距离除以最近距离小于某个阙值，则判定为一对匹配点。
最后，看下Sift 算法效果图：下图左边部分Sift算法匹配结果，右边部分是其它算法匹配结果：
二、Sift算法的描述在上述的Sift算法步骤一中，提到了尺度空间，那么什么是尺度和尺度空间呢？尺度就是受delta这个参数控制的表示。而不同的L（x,y,delta)就构成了尺度空间，实际上，具体计算的时候，即使连续的高斯函数，都要被离
散为（一般为奇数大小）(2*k+1) *(2*k+1)矩阵，来和数字图像进行卷积运算。
David Lowe关于Sfit算法，2004年发表在Int. Journal of Computer Vision的经典论文中，对尺度空间（scal space)是这样定义的 ： It has been shown by Koenderink (1984) and Lindeberg (1994) that under a variety ofreasonable assumptions the only possible scale-space kernel is the Gaussian function.
Therefore,the scale space of an image is defined as a function, L(x; y; delta) that is
produced from the convolution of a variable-scale Gaussian, G(x; y; delta), with an input
image, I(x; y):
因此 ，一个图像的尺度空间，L（x,y,delta) ,定义为原始图像I (x,y)与一个可变尺度的2维高斯函数G(x,y,delta) 卷积运算。
即，原始影像I(x，y)在不同的尺度e下，与高斯滤波器G(x,y,e)进行卷积，得到L(x,y,e)，如下：L(x,y,e) = G(x,y,e)*I(x,y)其中G(x,y,e)是尺度可变高斯函数， G(x,y,e) = [1/2*pi*e2] * exp[ -(x2 + y2)/2e2] （x，y）是空间坐标， e是尺度坐标。
为了更有效的在尺度空间检测到稳定的关键点，提出了高斯差分尺度空间（DOG scale-space）。利用不同尺度的高斯差分核与原始图像I(x,y) ，卷积生成。
D(x,y,e) = ((G(x,y,ke) – G(x,y,e)) * I(x,y) = L(x,y,ke) – L(x,y,e)DOG算子计算简单，是尺度归一化的LoG算子的近似。
Gaussian卷积是有尺寸大小的，使用同一尺寸的滤波器对两幅包含有不同尺寸的同一物体的图像求局部最值将有可能出现一方求得最值而另一方却没有的情况，但是容易知道假如物体的尺寸都一致的话它们的局部最值将会相同。
SIFT的精妙之处在于采用图像金字塔的方法解决这一问题，我们可以把两幅图像想象成是连续的，分别以它们作为底面作四棱锥，就像金字塔，那么每一个 截面与原图像相似，那么两个金字塔中必然会有包含大小一致的物体的无穷个截面，但应用只能是离散的，所以我们只能构造有限层，层数越多当然越好，但处理时 间会相应增加，层数太少不行，因为向下采样的截面中可能找不到尺寸大小一致的两个物体的图像。
有了图像金字塔就可以对每一层求出局部最值，但是这样的稳定 点数目将会十分可观，所以需要使用某种方法抑制去除一部分点，但又使得同一尺度下的稳定点得以保存图像金字塔的构建：图像金字塔共O组，每组有S层，下一组的图像由上一组图像降采样得到。如下图：
三、Sift算法的实现作为一种匹配能力较强的局部描述算子，SIFT算法的实现相当复杂，不过David Lowe到底也还是用c++实现了它，头文件里就下述两个关键函数，下面具体阐述下。
请打开窗口，让我的灵魂与你的灵魂相拥。
