http://www.Sina.com/http://www.Sina.com /
成像的核心问题是，同一目标对应于不同时间、不同分辨率、不同照明和不同姿态创建的图像。 需要尽快提出一种传统的匹配算法多直接提取角点和边缘，对环境适应能力低，鲁棒性强，能够在适应不同照明、不同姿态等情况下有效识别目标的方法。 1999年British Columbia大学hxsdg(Davidg.lowe )教授总结了目前基于不变量技术的特征检测方法，基于尺度空间的图像在缩放、旋转、仿射变换方面保持不变性的图像局部特征描述算子——ssdg
一. SIFT简介
将图像映射(变换)为局部特征向量集； 特征向量具有平移、缩放、旋转不变性，同时光照变化、仿射及投影变换也具有一定的不变性。
算法实现步骤概述：
SIFT算法的本质可以分为在不同尺度空间寻找特征点(关键点)的问题。
1.3基于sift算法的物体识别主要有三个步骤。
1、提取关键点
2、对关键点附加详细信息(局部特征)，即所谓描述符
3、通过两个特征点(带有特征向量的关键点)的两个比较，找到几个相互匹配的特征点对，从而也建立场景之间的对应关系。
1.1 算法提出的背景：
1.2 算法思想：
比例理论基础：
这是初始化操作，尺度空间理论的目的是模拟图像数据的多尺度特征。 HDSG内核是唯一能够生成多尺度空间的内核，一个图像的尺度空间，L(x，y，)定义为原始图像I ) x，y )与一个可变尺度的二维HDSG函数g ) x，y，的卷积运算尺度自然存在，不是人为制造的！ hhdsg卷积是表征尺度空间的一种形式二. SIFT算法实现细节
其中，g(x，y，)是比例可变hhdsg函数) x，y是空间坐标，是比例坐标。 的大小决定图像的平滑度，大尺度对应图像外观的特征，小尺度对应图像的细节特征。 的值越大，越对应粗糙的比例(低分辨率)，相反对应细小的比例(高分辨率)。 为了有效地检测尺度空间中稳定的关键点，提出了hhdsg差分尺度空间(DOG scale-space )。 利用不同尺度的hhdsg差分核与图像卷积生成。
下图所示不同下的图像比例空间：
关于理解比例空间：
2k中2是必须的，尺度空间是连续的。 在Lowe的论文中，第0层的初始尺度为1.6 (最模糊)，图像的初始尺度为0.5 (最鲜明)。 检测极值点前对原始图像的hhdsg进行平滑处理，使图像失去高频信息，因此在建立尺度空间前，建议先将原始图像的长宽比扩大一倍，保持原始图像信息，增加特征点的数量。 比例越大，图像越模糊。
创建金字塔：
对于单个图像I，以不同比例创建的图像也是子倍频程。 这是为了使其可以具有比例变化，即在任何比例上具有相应的特征点。 第一个子八度音的比例是原始图像的大小，后面的每个octave从前一个octave中缩减像素采样
图size决定了要建多少座塔，每个塔要建几层。 (s通常为3-5层)。 0塔的第0层是原始图像(或你双精度的图像)，上一层是将其下一层进行Laplacian变换) hhdsg卷积，的值逐渐变大，例如、k*、k*k*…() ) ) 塔间照片为下采样关系，如1塔0层由0塔3层down sample得到，然后可以进行与0塔相似的hhdsg卷积操作。
2.1. 构建尺度空间
为了找到比例空间中的极值点，将每个采样点与其所有相邻点进行比较，以确定该图像区域和比例区域的相邻点是大于还是小于相邻点。 如图所示，将中间检测点和与其同尺度的8个相邻点与对应于上下相邻尺度的92个点共计26个点进行比较，在尺度空间和二维图像空间两者中检测极值点。 如果某一点在DOG尺度空间的基本层和上下两层的26个区域中最大或最小，则如图所示，该点被认为是该尺度下的图像的特征点。
探索同一组内的相邻尺度(根据k的取值关系，必须在上下层)之间。 极值比较过程中，各组图像的第一层和最后两层不能进行极值比较。 为了满足尺度变化的连续性，在各组图像的最上层用hhdsg持续模糊生成3幅图像。 hhdsg金字塔每组有S 3层图像。 每组DOG金字塔都有S 2层图像。 下图中s=3
现在说明尺度变化的连续性。
假设s=3，即每个塔有三层，则k=21/s=21/3，在上图中得到3个(s个)和2个(Gauss Space和DoG space )
1个）分量，在DoG space中，1st-octave两项分别是σ,kσ; 2nd-octave两项分别是2σ,2kσ;由于无法比较极值，我们必须在hhdsg空间继续添加hhdsg模糊项，使得形成σ,kσ,k2σ,k3σ,k4σ这样就可以选择DoG space中的中间三项kσ,k2σ,k3σ（只有左右都有才能有极值），那么下一octave中（由上一层降采样获得）所得三项即为2kσ,2k2σ,2k3σ，其首项2kσ=24/3。刚好与上一octave末项k3σ=23/3尺度变化连续起来，所以每次要在Gaussian space添加3项，每组（塔）共S+3层图像，相应的DoG金字塔有S+2层图像。2.3. 消除错配点
由于DoG值对噪声和边缘较敏感,因此,在上面DoG尺度空间中检测到局部极值点还要经过进一步的检验才能精确定位为特征点。为了提高关键点的稳定性，需要对尺度空间DoG函数进行曲线拟合。利用DoG函数在尺度空间的Taylor展开式：
对上式求导,并令其为0,得到精确的位置, 得
在已经检测到的特征点中,要去掉低对比度的特征点和不稳定的边缘响应点。去除低对比度的点：把上式代入其中，即在DoG Space的极值点处D(x)取值，只取前两项可得：
若
，该特征点就保留下来，否则丢弃。
边缘响应的去除
一个定义不好的hhdsg差分算子的极值在横跨边缘的地方有较大的主曲率，而在垂直边缘的方向有较小的主曲率。主曲率通过一个2×2 的Hessian矩阵H求出:
导数由采样点相邻差估计得到。D的主曲率和H的特征值成正比，令α为较大特征值，β为较小的特征值，则
令α=γβ，则
(r + 1)2/r的值在两个特征值相等的时候最小，随着r的增大而增大，因此，为了检测主曲率是否在某域值r下，只需检测
if (α+β)/ αβ> (r+1)2/r, throw it out. 在Lowe的文章中，取r＝10。
2.4. 关键点描述
上一步中确定了每幅图中的特征点，为每个特征点计算一个方向，依照这个方向做进一步的计算， 利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数，使算子具备旋转不变性。
为(x,y)处梯度的模值和方向公式。其中L所用的尺度为每个关键点各自所在的尺度。至此，图像的关键点已经检测完毕，每个关键点有三个信息：位置，所处尺度、方向，由此可以确定一个SIFT特征区域。
梯度直方图的范围是0～360度，其中每10度一个柱，总共36个柱。随着距中心点越远的领域其对直方图的贡献也响应减小.Lowe论文中还提到要使用hhdsg函数对直方图进行平滑，减少突变的影响。
在实际计算时，我们在以关键点为中心的邻域窗口内采样，并用直方图统计邻域像素的梯度方向。梯度直方图的范围是0～360度，其中每45度一个柱，总共8个柱, 或者每10度一个柱，总共36个柱。Lowe论文中还提到要使用hhdsg函数对直方图进行平滑，减少突变的影响。直方图的峰值则代表了该关键点处邻域梯度的主方向，即作为该关键点的方向。
直方图中的峰值就是主方向，其他的达到最大值80%的方向可作为辅助方向，通过对关键点周围图像区域分块，计算块内梯度直方图，生成具有独特性的向量，这个向量是该区域图像信息的一种抽象，具有唯一性。首先将坐标轴旋转为关键点的方向，以确保旋转不变性。以关键点为中心取8×8的窗口。
16*16的图中其中1/4的特征点梯度方向及scale，右图为其加权到8个主方向后的效果。图左部分的中央为当前关键点的位置，每个小格代表关键点邻域所在尺度空间的一个像素，利用公式求得每个像素的梯度幅值与梯度方向，箭头方向代表该像素的梯度方向，箭头长度代表梯度模值，然后用hhdsg窗口对其进行加权运算。
图中蓝色的圈代表hhdsg加权的范围（越靠近关键点的像素梯度方向信息贡献越大）。然后在每4×4的小块上计算8个方向的梯度方向直方图，绘制每个梯度方向的累加值，即可形成一个种子点，如图右部分示。此图中一个关键点由2×2共4个种子点组成，每个种子点有8个方向向量信息。这种邻域方向性信息联合的思想增强了算法抗噪声的能力，同时对于含有定位误差的特征匹配也提供了较好的容错性。
计算keypoint周围的16*16的window中每一个像素的梯度，而且使用hhdsg下降函数降低远离中心的权重。
在每个4*4的1/16象限中，通过加权梯度值加到直方图8个方向区间中的一个，计算出一个梯度方向直方图。这样就可以对每个feature形成一个4*4*8=128维的描述子，每一维都可以表示4*4个格子中一个的scale/orientation. 将这个向量归一化之后，就进一步去除了光照的影响。
2.5. 关键点匹配
生成了A、B两幅图的描述子，（分别是k1*128维和k2*128维），就将两图中各个scale（所有scale）的描述子进行匹配，匹配上128维即可表示两个特征点match上了。
实际计算过程中，为了增强匹配的稳健性，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的取值策略能排分错误匹配点。
当两幅图像的SIFT特征向量生成后，下一步我们采用关键点特征向量的欧式距离来作为两幅图像中关键点的相似性判定度量。取图像1中的某个关键点，并找出其与图像2中欧式距离最近的前两个关键点，在这两个关键点中，如果最近的距离除以次近的距离少于某个比例阈值，则接受这一对匹配点。降低这个比例阈值，SIFT匹配点数目会减少，但更加稳定。