教育行业A股IPO第一股（股票代码003032）
全国咨询/投诉热线：400-618-4000
前面我们介绍了Harris和Shi-Tomasi角点检测算法，这两种算法具有旋转不变性，但不具有尺度不变性，以下图为例，在左侧小图中可以检测到角点，但是图像被放大后，在使用同样的窗口，就检测不到角点了。
所以，下面我们来介绍一种计算机视觉的算法，尺度不变特征转换即SIFT(Scale-invariantfeaturetransform)。它用来侦测与描述影像中的局部性特征，它在空间尺度中寻找极值点，并提取出其位置、尺度、旋转不变量，此算法由DavidLowe在1999年所发表，2004年完善总结。应用范围包含物体辨识、机器人地图感知与导航、影像缝合、3D模型建立、手势辨识、影像追踪和动作比对等领域。
Lowe将SIFT算法分解为如下四步：
我们就沿着Lowe的步骤，对SIFT算法的实现过程进行介绍：
在不同的尺度空间是不能使用相同的窗口检测极值点，对小的关键点使用小的窗口，对大的关键点使用大的窗口，为了达到上述目的，我们使用尺度空间滤波器。
高斯核是唯一可以产生多尺度空间的核函数。-《Scale-spacetheory:Abasictoolforanalysingstructuresatdifferentscales》。
L(x,y,σ)=G(x,y,σ)?I(x,y)L(x,y,\sigma)=G(x,y,\sigma)*I(x,y)L(x,y,σ)=G(x,y,σ)?I(x,y)其中：G(x,y,σ)=12πσ2e?x2+y22σ2G(x,y,\sigma)=\frac{1}{2\pi\sigma^2}e^{-\frac{x^2+y^2}{2\sigma^2}}G(x,y,σ)=2πσ21e?2σ2x2+y2σ\sigmaσ是尺度空间因子，它决定了图像的模糊的程度。在大尺度下（σ\sigmaσ值大）表现的是图像的概貌信息，在小尺度下（σ\sigmaσ值小）表现的是图像的细节信息。
搜索过程从每组的第二层开始，以第二层为当前层，对第二层的DoG图像中的每个点取一个3×3的立方体，立方体上下层为第一层与第三层。这样，搜索得到的极值点既有位置坐标（DoG的图像坐标），又有空间尺度坐标（层坐标）。当第二层搜索完成后，再以第三层作为当前层，其过程与第二层的搜索类似。当S=3时，每组里面要搜索3层，所以在DOG中就有S+2层，在初使构建的金字塔中每组有S+3层。
由于DoG对噪声和边缘比较敏感，因此在上面高斯差分金字塔中检测到的局部极值点需经过进一步的检验才能精确定位为特征点。
使用尺度空间的泰勒级数展开来获得极值的准确位置，如果极值点的灰度值小于阈值（一般为0.03或0.04）就会被忽略掉。在OpenCV中这种阈值被称为contrastThreshold。
DoG算法对边界非常敏感，所以我们必须要把边界去除。Harris算法除了可以用于角点检测之外还可以用于检测边界。从Harris角点检测的算法中，当一个特征值远远大于另外一个特征值时检测到的是边界。那在DoG算法中欠佳的关键点在平行边缘的方向有较大的主曲率，而在垂直于边缘的方向有较小的曲率，两者的比值如果高于某个阈值（在OpenCV中叫做边界阈值），就认为该关键点为边界，将被忽略，一般将该阈值设置为10。
将低对比度和边界的关键点去除，得到的就是我们感兴趣的关键点。
经过上述两个步骤，图像的关键点就完全找到了，这些关键点具有尺度不变性。为了实现旋转不变性，还需要为每个关键点分配一个方向角度，也就是根据检测到的关键点所在高斯尺度图像的邻域结构中求得一个方向基准。
对于任一关键点，我们采集其所在高斯金字塔图像以r为半径的区域内所有像素的梯度特征（幅值和幅角），半径r为：r=3×1.5σr=3\times1.5\sigmar=3×1.5σ其中σ是关键点所在octave的图像的尺度，可以得到对应的尺度图像。
梯度的幅值和方向的计算公式为：m(x,y)=(L(x+1,y)?L(x?1,y)2+(L(x,y+1)?L(x,y?1))2m(x,y)=\sqrt{(L(x+1,y)-L(x-1,y)^2+(L(x,y+1)-L(x,y-1))^2}m(x,y)=√(L(x+1,y)?L(x?1,y)2+(L(x,y+1)?L(x,y?1))2
θ(x,y)=arctan(L(x,y+1)?L(x,y?1)L(x+1,y)?L(x?1),y)\theta(x,y)=arctan(\frac{L(x,y+1)-L(x,y-1)}{L(x+1,y)-L(x-1),y})θ(x,y)=arctan(L(x+1,y)?L(x?1),yL(x,y+1)?L(x,y?1))
获得图像关键点主方向后，每个关键点有三个信息(x,y,σ,θ)：位置、尺度、方向。由此我们可以确定一个SIFT特征区域。通常使用一个带箭头的圆或直接使用箭头表示SIFT区域的三个值：中心表示特征点位置，半径表示关键点尺度，箭头表示方向。如下图所示：
通过以上步骤，每个关键点就被分配了位置，尺度和方向信息。接下来我们为每个关键点建立一个描述符，该描述符既具有可区分性，又具有对某些变量的不变性，如光照，视角等。而且描述符不仅仅包含关键点，也包括关键点周围对其有贡献的的像素点。主要思路就是通过将关键点周围图像区域分块，计算块内的梯度直方图，生成具有特征向量，对图像信息进行抽象。
描述符与特征点所在的尺度有关，所以我们在关键点所在的高斯尺度图像上生成对应的描述符。以特征点为中心，将其附近邻域划分为d?dd*dd?d个子区域（一般取d=4)，每个子区域都是一个正方形，边长为3σ，考虑到实际计算时，需进行三次线性插值，所以特征点邻域的为3σ(d+1)?3σ(d+1)3\sigma(d+1)*3\sigma(d+1)3σ(d+1)?3σ(d+1)的范围，如下图所示：
为了保证特征点的旋转不变性，以特征点为中心，将坐标轴旋转为关键点的主方向，如下图所示：
计算子区域内的像素的梯度，并按照σ=0.5d进行高斯加权，然后插值计算得到每个种子点的八个方向的梯度，插值方法如下图所示：
每个种子点的梯度都是由覆盖其的4个子区域插值而得的。如图中的红色点，落在第0行和第1行之间，对这两行都有贡献。对第0行第3列种子点的贡献因子为dr，对第1行第3列的贡献因子为1-dr，同理，对邻近两列的贡献因子为dc和1-dc，对邻近两个方向的贡献因子为do和1-do。则最终累加在每个方向上的梯度大小为：weight=w?drk(1?dr)(1?k)dcm(1?dc)1?mdon(1?do)1?nweight=w*dr^k(1-dr)^{(1-k)}dc^m(1-dc)^{1-m}do^n(1-do)^{1-n}weight=w?drk(1?dr)(1?k)dcm(1?dc)1?mdon(1?do)1?n其中k，m，n为0或为1。如上统计4?4?8=1284*4*8=1284?4?8=128个梯度信息即为该关键点的特征向量，按照特征点的对每个关键点的特征向量进行排序，就得到了SIFT特征描述向量。
SIFT在图像的不变特征提取方面拥有无与伦比的优势，但并不完美，仍然存在实时性不高，有时特征点较少，对边缘光滑的目标无法准确提取特征点等缺陷，自SIFT算法问世以来，人们就一直对其进行优化和改进，其中最著名的就是SURF算法。