SIFT特征的生成一般包括以下几个步骤.docx

基本概念：
降采样：对于一幅图像而言的降采样就是每隔几行、几列取一点，组成一个新的图像。对比例因子为2的降采样来说：就是对一幅图像每隔一行一列取一点。对于n×n的图像就变为n/2×n/2的图像了。
升采样：其实一种插值，就是在一幅图像里利用相关的插值运算得到一幅大的图像！比例因子为2的升采样就是每个相邻像素点插值种出一个像素（这里包括X、Y两个方向）。对于n×n的图像就变为2n×2n的图像了。顺便说下插值，就是一种利用已有数据对位置数据的估计。比如我第10秒走了12米，第20秒走了30米，那么我用线性插值估计我第15秒走了（30-12）/2+12=21米，当然插值的方法有很多！
图像金字塔：简单的说是一个图像集，由一个原始图像经过降采样得到一幅图像，再对新的图像做降采样，重复多次构成的一组集合。如果形象的把这些图像摞起来就想一个金字塔，故此得名。
卷积：这个概念我感觉是最不好解释的，他就是一个积分，两个函数（其中一个带参数）对应点的乘积，然后把乘积函数求积分！大致我理解就是这样，但是具体的还是请大家去查书。但是这里我想说卷积再图像里的运算。卷积是一种无限的积分运算，但是因为在一个二维平面（X轴对应一个卷积函数，Y轴对应一个卷积函数！），一般境况下围绕某一点的卷积运算距离卷几点一定远的运算对最后结果很小，所以通常忽略！这样卷积运算就变成了一种模板运算！例如3×3的一种模板运算，就是把离他最近的9个点（包括它本身9个点）分别乘以按一定的加权函数所对应的权值后加到这个中心点上成为该点的新值。那么对于3×3的模板运算每一点要做9个乘法9个加法。那么对于1000个像素的图像做模板运算就要做9000个乘法，9000加法！如果模板再大，计算次数会更多。
高斯卷积：就是权函数为高斯函数的卷积模板运算，高斯卷积有一次和二次...。通常做高斯卷积后的图像会比原图像平滑但也会模糊，所以又称高斯模糊！因为这不能写公式，很多的细节可以看下面的附件里的图片！
高斯金字塔：高斯金字塔里有两个概念：组（Octave）和层（Level或Interval），每组里有若干层！高斯金字塔的构造是这样的，第一组的第一层为原图像，然后将图像做一次高斯平滑（高斯卷积、高斯模糊）高斯平滑里有一个参数σ（详见附件图片），在SIFT里作者取1.6然后将σ乘一个比例系数k作为新的平滑因子来平滑第一组第二层得到第三层。重复若干次，得到L层他们分别对应的平滑参数为：0，σ，kσ，k2σ....。然后将最后一幅图像做比例因此为2的降采样得到第二组的第一层，然后对第二组的第一层做参数是σ的高斯平滑，对第二层做kσ的平滑得到第三层.....这里一定注意：每组对应的平滑因子是一样的！而不是像有的资料上说的持续递增。这样反复形成了O组L层。一般模糊的高斯模板长宽都约为6σ（这里σ为当次的平滑因子，就是可能是kσ，k2σ..）
DoG（Difference of Gaussian）金字塔：他是由高斯金字塔构造出来的，他的第一组第一层是由高斯金字塔的第一组第二层减第一组第一层，他的第一组第二层是由高斯金字塔的第一组第三层减第一组第二层得到，（说的这么繁琐是为了大家能理解的直观点）。没组都这样就生成了DoG金字塔。顺便说一下，DoG金字塔每组图像几乎都是一片黑，但仔细看你能看出轮廓的。
两个金字塔在SIFT算法里的特殊说明：1、在SIFT里高斯金字塔的第一组第一层通常是由一个原图像长宽扩大一倍开始的，这样做是为了可以得到更多的特征点2、大家可以发现如果用每组5层的高斯金字塔构造一个DoG金字塔的的话，DoG的每组的层数是4。3、对于DoG金字塔，特征点的搜索从每组的二层到倒数第二层的（后面说明为什么），所以如果实际用n层那么DoG金字塔应该有n+2层，那么对应的高斯金字塔应该有n+3层。4、由于这样所以高斯金字塔从第二组开始的每组第一层是由上一组的倒数第二层降采样得到的。
梯度：就是一个有方向和长度的向量，它的意义是一个函数的某一点上数值变化最大的方向和变化量。在图像中一个像素点的梯度是由它周围的8个点计算得到的。（公式见附件的图）
K-d树：一种数据结构，用于搜索高维最邻近点，他是一种二叉树，每个节点是一个高维向量。对于他的具体说明我没仔细看呢，如果做到最后需要请大家参考这个：顺便说下维基百科不错！！
 尺度：这个概念最让我郁闷，现在弄的不是很清楚。我现在的理解就是（这不是它的概念）：1、表示同一事物所用到的图像像素量，用的多尺度就小，用的少尺度就大（说没说反？嘿嘿！）。2、它和图像的清晰程度有关，如上面说的高斯模糊，那么因子σ越大得到的图像越模糊，那么尺度越大！3、图像的旋转、平移尺度是不变的，但是放大、缩小、模糊就变了。
尺度空间理论
　　尺度空间理论目的是模拟图像数据的多尺度特征。
其基本思想是在视觉信息、图像信息处理模型中引入一个被视为尺度的参数，通过连续变化尺度参数获得不同尺度下的视觉处理信息，然后综合这些信息以深入地挖掘图像的本质特征。
尺度空间表示的主要思想是，由原始信号（例如一幅图像）生成一系列信号，并用这些信号来表示原始信号，这个过程中，精细尺度的信息被逐步的平滑掉（可以认为是细节信息被丢弃）。
尺度空间理论是多尺度图像表示的框架，其基本思想是描述自然界目标的多尺度特性，即观测尺度的不同导致对目标特性感知的不同。在无法获得感兴趣尺度的先验信息下，面向未知场景的图像解译算法需要同时考虑多尺度的图像表示。2维图像函数f(x，y)的尺度空间表示L定义为
Lx，y;σ=(x-ξy-η)φξ，η;σ2dξdη
式中φ表示尺度参数为σ的高斯核。在图像的多尺度表示基础上，通过基于尺度空间归一化导数最大化的自动尺度选择，可以实现图像特征提取的尺度不变特性。特征提取算法可以适应不同尺寸的目标、局部结构或目标与成像系统之间距离变化等因素导致的未知尺度变化。
描述子生成的细节
　　以极值点为中心点，并且以此点所处于的高斯尺度sigma值作为半径因子。对于远离中心点的梯度值降低对其所处区域的直方图的贡献，防止一些突变的影响。每个极值点对其进行三线性插值，这样可以把此极值点的贡献均衡的分到直方图中相邻的柱子上
归一化处理
　　在求出4×4×8的128维特征向量后，此时SIFT特征向量已经去除了尺度变化、旋转等几何变形因素的影响。而图像的对比度变化相当于每个像素点乘上一个因子，光照变化是每个像素点加上一个值，但这些对图像归一化的梯度没有影响。因此将特征向量的长度归一化，则可以进一步去除光照变化的影响。对于一些非线性的光照变化，SIFT并不具备不变性，但由于这类变化影响的主要是梯度的幅值变化，对梯度的方向影响较小，因此作者通过限制梯度幅值的值来减少这类变化造成的影响。
1. 哪些点是SIFT中要查找的关键点（特征点）？
这些点是一些十分突出的点不会因光照条件的改变而消失，比如角点、边缘点、暗区域的亮点以及亮区域的暗点，既然两幅图像中有相同的景物，那么使用某种方法分别提取各自的稳定点，这些点之间会有相互对应的匹配点。
所谓关键点，就是在不同尺度空间的图像下检测出的具有方向信息的局部极值点。
根据归纳，我们可以看出特征点具有的三个特征：尺度、方向、大小
2. 什么是尺度空间（scale space ）？
我们要精确表示的物体都是通过一定的尺度来反映的。现实世界的物体也总是通过不同尺度的观察而得到不同的变化。
尺度空间理论最早在1962年提出，其主要思想是通过对原始图像进行尺度变换，获得图像多尺度下的尺度空间表示序列，对这些序列进行尺度空间主轮廓的提取，并以该主轮廓作为一种特征向量，实现边缘、角点检测和不同分辨率上的特征提取等。
尺度空间中各尺度图像的模糊程度逐渐变大，能够模拟人在距离目标由近到远时目标在视网膜上的形成过程。
尺度越大图像越模糊。
根据文献《Scale-space theory: A basic tool for analysing structures at different scales》我们可知，高斯核是唯一可以产生多尺度空间的核，一个图像的尺度空间，L（x，y，σ) ，定义为原始图像I(x，y)与一个可变尺度的2维高斯函数G(x，y，σ) 卷积运算。
3. 高斯模糊
高斯模糊是在Adobe Photoshop等图像处理软件中广泛使用的处理效果，通常用它来减小图像噪声以及降低细节层次。这种模糊技术生成的图像的视觉效果是好像经过一个半透明的屏幕观察图像。

SIFT算法的实质可以归为在不同尺度空间上查找特征点（关键点）的问题。
SIFT算法实现物体识别主要有四大工序：
1.关键点检测
2.关键点描述
3.关键点匹配
4.消除错配点

SIFT算法步骤：
1） 检测尺度空间极值点；
2） 精确定位极值点；
3） 为每个关键点指定方向参数；
4） 关键点描述子的生成。
3 算法详解
主要步骤 
　　 1）、尺度空间的生成；
  　　2）、检测尺度空间极值点；
 　　3）、精确定位极值点；
 　　4）、为每个关键点指定方向参数；
 　　5）、关键点描述子的生成。
1）、尺度空间的生成；
尺度空间理论的目的是模拟图像数据的多尺度特征，高斯卷积核是实现尺度变换的唯一线性核，于是一副二维图像的尺度空间定义为：Lx，y，σ=Gx，y，σ⊗Ix，y
图像的尺度空间表示成一个函数Lx，y，σ，它是由一个变化尺度的高斯函数Gx，y，σ与图像Ix，y卷积生成的。其中⊗代表卷积操作，而Gx，y，σ为：
Gx，y，σ=12πσ2e-(x2+y2)2σ2 (1)
(x，y)是空间坐标，σ是尺度坐标。σ的大小决定图像的平滑尺度，大尺度对应图像的概貌特征，小尺度对应图像的细节特征。大的σ值对应粗糙尺度（低分辨率），反之，对应精细尺度（高分辨率）。
构造高斯差分尺度空间（DOG scale-space）：
Dx，y，σ=Gx，y，kσ-Gx，y，σ⊗Ix，y= Lx，y，kσ-Lx，y，σ (2)
式中，k为两相邻尺度空间倍数的常数。

　　　　　　　　　　　　Lx，y，σ， σ= 1.6

　　　　　　　　　　　　  Dx，y，σ， σ= 1.6
接下来是在如何计算DoG。首先是构建图像的高斯金字塔。将图像金字塔共分O组，一组称为一个Octave，每组又分为多层，层间隔数为S，因此有S+3(S+1+2，2代表在上下再各添一层图像，搜索极值只在中间的S+1层图像上搜索)层图像，下一组的第一层图像由上一组的倒数第三层（如果层索引从0开始，则为第S层）图像按照隔点采样得到，这样做的目的是为了减少卷积运算的工作量。DoG是通过高斯金字塔中的每组上下相邻两层的高斯尺度空间图像相减得到。如下图：

在高斯金字塔中，σ和o， s的关系如下：
σo，s=σ02o+sS o∈0，…，O-1，s∈0，…，S+2 (6)
其中，σ0是基准层尺度，o为组Octave的索引，s为组里图像的层索引。
我们认为初始图像有一个初始的σ=0.5的高斯模糊（为了防止显著的混淆效应）。从上式可以看出，（2）式中的k=21s。
在最开始建立高斯金字塔时，要预先模糊输入图像来作为第0个组的第0层的图像，这时相当于丢弃了最高的空域的采样率。因此通常的做法是先将图像的尺度扩大一倍来生成第0组。我们假定初始的输入图像为了抗击混淆现象，已经对其进行σn=0.5的高斯模糊，如果输入图像的尺寸用双线性插值扩大一倍，那么相当于σn=1.0。因此，实际σo，s=σ2o，s-σn2 (7)
下面是尺度空间表示的一个例子：

  　　2）尺度空间极值点检测
兴趣点的初步探查是通过同一组内各DoG相邻层之间比较完成的。为了寻找尺度空间的极值点，每一个采样点要和它的相邻点进行比较，看其是否比它的图像域和尺度域的相邻点大或者小。如下图所示：

上图中表示×的检测点和它同尺度的8个相邻点和上下相邻尺度对应的9×2个点共26个点进行比较，以确保在尺度空间和二维图像位置空间都检测到极值点。如果一个点在DOG尺度空间本层以及上下两层的26个领域中是最大或最小值时，就认为该点是图像在该尺度下的一个特征点。搜索过程从每组的第二层开始，也就是从层索引为1的那一层开始，到层索引为S的层结束。
下面是局部极值检测的结果：

 　　3）、精确定位极值点
通过拟合三维二次函数以精确确定关键点的位置和尺度（达到亚像素精度），同时去除低对比度的关键点和不稳定的边缘响应点（因为DOG算子会产生较强的边缘响应），以增强匹配稳定性、提高抗噪声能力。
a) 对空间尺度函数根据泰勒级数展开
Dx，y，σ=Dx，y，σ+∂DT∂x+12xT∂2D∂x2x （1）
求导，并令其为0，得到精确的位置x，x=-∂2D-1∂x2∂D∂x （2）
b) 在已经检测到的特征点中，要去掉低对比度的特征点和不稳定的边缘响应点。去除低对比度的点：把公式（2）带入公式（1），只取前两项可得：Dx=Dx，y，σ+12∂DT∂xx
若|Dx|≥0.03，该特征点就保留下来，否则丢弃。（x=(x，y，σ)T）
下面是移除Dx绝对值较小的关键点的结果：

c)  为了得到稳定的极值点，还要去除边缘的影响，因为边缘上的极值点抗噪性较差。曲面上每个点（非平点）都有两个主方向，并且沿这两个主方向的法曲率（即两个主曲率）分别是曲面在该点法曲率的最大值和最小值。在边缘上的极值点，垂直于边缘的方向上，法曲率最大，沿边缘的方向上，法曲率最小。如果极值点分布在边缘上，该点的法曲率最大值和最小值之比（即两个主曲率之比），一般情况下要比非边缘点的比值大。根据这种思想，我们可以设一个比值的阈值，当比值大于这个阈值就认为极值点在边缘上。可以采用近似的方法来求主曲率的比值。主曲率通过一个2×2的Hessian矩阵H求出：
H=DxxDxyDxyDyy
其中微分可以通过计算邻近点的差值来近似计算。H的特征值和D 的主曲率对应成比例，这里我们只需要计算H 的较大特征值与较小特征值的比例即可。设α是较大的特征值，β是较小的特征值，由矩阵性质知：
TrH=Dxx+Dyy=α+β
DetH=DxxDyy+Dxy2=αβ
其中用到了矩阵的迹和行列式。通常这里的行列式不会是负值，如果出现负值的情况，即两个主曲率不同号，我们将丢弃这个点，不将其视为极值点。设r=α/β，我们可得：
TrH2DetH=(α+β)2αβ=(rβ+β)2rβ2=(r+1)2r
当r≥1，(r +1)2 / r 是r 的单调递增函数，所以要计算主曲率的比值（即r）是否在某阈值之下，只需要判断上式左边的项是否在阈值之下即可。实验表明，阈值通常选择r = 10。
　　 　　  If ratio > （r+1）2/（r）， throw it out （SIFT uses r=10）
 　　4）、为每个关键点指定方向参数
利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数，使算子具备旋转不变性。
mx，y=(Lx+1，y-Lx-1，y)2+(Lx，y+1-Lx，y-1)2
θx，y=tan-1((Lx，y+1-Lx，y-1)/( Lx+1，y-Lx-1，y))
上式为(x，y)处梯度的模值和方向公式。其中L所用的尺度为每个关键点各自所在的尺度。
在实际计算时，我们在以关键点为中心的邻域窗口内采样，并用直方图统计邻域像素的梯度方向。梯度直方图的范围是0～360度，其中每10度一个柱，总共36个柱。直方图的峰值则代表了该关键点处邻域梯度的主方向，即作为该关键点的方向。
在梯度方向直方图中，当存在另一个相当于主峰值80%能量的峰值时，则将这个方向认为是该关键点的辅方向。一个关键点可能会被指定具有多个方向（一个主方向，一个以上辅方向），这可以增强匹配的鲁棒性。 至此，图像的关键点已检测完毕，每个关键点有三个信息：位置、所处尺度、方向。由此可以确定一个SIFT特征区域（在实验章节用椭圆或箭头表示）。

 　　5）、关键点描述子的生成
首先将坐标轴旋转为关键点的方向，以确保旋转不变性。

图 由关键点邻域梯度信息生成特征向量
接下来以关键点为中心取8×8的窗口。图左部分的中央黑点为当前关键点的位置，每个小格代表关键点邻域所在尺度空间的一个像素，利用公式求得每个像素的梯度幅值与梯度方向，箭头方向代表该像素的梯度方向，箭头长度代表梯度模值，然后用高斯窗口对其进行加权运算，每个像素对应一个向量，长度为，为该像素点的高斯权值，方向为，图中蓝色的圈代表高斯加权的范围（越靠近关键点的像素梯度方向信息贡献越大）。然后在每4×4的小块上计算8个方向的梯度方向直方图，绘制每个梯度方向的累加值，即可形成一个种子点，如图右部分示。此图中一个关键点由2×2共4个种子点组成，每个种子点有8个方向向量信息。这种邻域方向性信息联合的思想增强了算法抗噪声的能力，同时对于含有定位误差的特征匹配也提供了较好的容错性。
实际计算过程中，为了增强匹配的稳健性，Lowe建议对每个关键点使用4×4共16个种子点来描述，这样对于一个关键点就可以产生128个数据，即最终形成128维的SIFT特征向量。此时SIFT特征向量已经去除了尺度变化、旋转等几何变形因素的影响，再继续将特征向量的长度归一化，则可以进一步去除光照变化的影响。
当两幅图像的SIFT特征向量生成后，下一步我们采用关键点特征向量的欧式距离来作为两幅图像中关键点的相似性判定度量。取图像1中的某个关键点，并找出其与图像2中欧式距离最近的前两个关键点，在这两个关键点中，如果最近的距离除以次近的距离少于某个比例阈值，则接受这一对匹配点。降低这个比例阈值，SIFT匹配点数目会减少，但更加稳定。为了排除因为图像遮挡和背景混乱而产生的无匹配关系的关键点，Lowe提出了比较最近邻距离与次近邻距离的方法，距离比率ratio小于某个阈值的认为是正确匹配。因为对于错误匹配，由于特征空间的高维性，相似的距离可能有大量其他的错误匹配，从而它的ratio值比较高。Lowe推荐ratio的阈值为0.8。但作者对大量任意存在尺度、旋转和亮度变化的两幅图片进行匹配，结果表明ratio取值在0. 4~0. 6之间最佳，小于0. 4的很少有匹配点，大于0. 6的则存在大量错误匹配点。(如果这个地方你要改进，最好给出一个匹配率和ration之间的关系图，这样才有说服力)作者建议ratio的取值原则如下:
ratio=0. 4　对于准确度要求高的匹配；
ratio=0. 6　对于匹配点数目要求比较多的匹配；
ratio=0. 5　一般情况下。
也可按如下原则:当最近邻距离<200时ratio=0. 6，反之ratio=0. 4。ratio的取值策略能排分错误匹配点。

下面以一个简单的例子来解释上述k-d tree的构建过程。假设样本集为：{(2，3)， (5，4)， (9，6)， (4，7)， (8，1)， (7，2)}。构建过程如下：
（1）确定split域，6个数据点在x，y维度上的数据方差分别为39， 28.63。在x轴上方差最大，所以split域值为0（x维的序号为0）
（2）确定分裂节点，根据x维上的值将数据排序，则6个数据点再排序后位于中间的那个数据点为(7，2)，该结点就是分割超平面就是通过(7，2)并垂直于split=0(x)轴的直线x=7
（3）左子空间和右子空间，分割超面x=7将整个空间氛围两部分，x<=7的部分为左子空间，包含3个数据点{(2，3)， (5，4)， (4，7)}；另一部分为右子空间，包含2个数据点{(9，6)， (8，1)}。如下图所示
（4）分别对左子空间中的数据点和右子空间中的数据点重复上面的步骤构建左子树和右子树直到经过划分的子样本集为空。下面的图从左至右从上至下显示了构建这棵二叉树的所有步骤：

k-d tree的最近邻搜索算法