《SIFT算法实现原理步骤111107》由会员分享，可在线阅读，更多相关《SIFT算法实现原理步骤111107（10页珍藏版）》请在金锄头文库上搜索。
1、SIFT 算法实现步骤 ：1 关键点检测、2 关键点描述、3 关键点匹配、4 消除错配点1 关键点检测1.1 建立尺度空间根据文献Scale-space theory: A basic tool for analysing structures at different scales我们可知，高斯核是唯一可以产生多尺度空间的核，一个图像的尺度空间，L（x,y, ) ,定义为原始图像 I(x,y)与一个可变尺度的 2 维高斯函数 G(x,y,) 卷积运算。 高斯函数高斯金字塔高斯金子塔的构建过程可分为两步：（1）对图像做高斯平滑；（2）对图像做降采样。为了让尺度体现其连续性，在简单下采样的基础上
2、加上了高斯滤波。一幅图像可以产生几组（octave）图像，一组图像包括几层（interval）图像。 高斯图像金字塔共 o 组、s 层，则有：尺度空间坐标；ssub-level 层坐标；0初始尺度；S每组层数（一般为35） 。当图像通过相机拍摄时，相机的镜头已经对图像进行了一次初始的模糊，所以根据高斯模糊的性质：-第 0 层尺度 -被相机镜头模糊后的尺度高斯金字塔的组数: M、N 分别为图像的行数和列数高斯金字塔的组内尺度与组间尺度:组内尺度是指同一组（octave）内的尺度关系，组内相邻层尺度化简为：组间尺度是指不同组直接的尺度关系，相邻组的尺度可化为：最后可将组内和组间尺度归为：21()(
3、),expiii yGxy,*,LyIO c t a v e 1O c t a v e 2O c t a v e 3O c t a v e 4O c t a v e 52480()2sSA0intitpreintpre2logmi,3O11SssA1()2sSooA2sSsSoo121(,)i nk 12Ski金字塔组数 n每组层数上一组图像的底层是由前一组图像的倒数第二层图像隔点采样生成的。这样可以保持尺度的连续性。差分高斯金字塔Lindeberg 在文献 Scale-space theory: A basic tool for analysing structures at differe
4、nt scales指出尺度规范化的 LoG 算子具有真正的尺度不变性。LoG 算子即（Laplacion of Gaussian）,可以由高斯函数梯度算子 GOG 构建尺度规范化的 GoG 算子：尺度规范化的 LoG 算子：LOG 算子与高斯核函数的关系通过推导可以看出，LOG 算子与高斯核函数的差有直接关系，由此引入一种新的算子DOG（Difference of Gaussians） ，即高斯差分算子。DoG（Difference of Gaussian）函数：DoG 在计算上只需相邻尺度高斯平滑后图像相减，因此简化了计算。对应 DOG 算子，我们要构建 DOG 金字塔22Gxy222(,)
5、(,)(,) 1ausxykausxyLOGxy,kG,*,LxyGxyI, ,DkIxyL我们可以通过高斯差分图像看出图像上的像素值变化情况。 （如果没有变化，也就没有特征。特征必须是变化尽可能多的点。 ）DOG 图像描绘的是目标的轮廓。在 Lowe 的论文中，将第 0 层的初始尺度定为 1.6，图片的初始尺度定为 0.5，则图像金字塔第 0 层的实际尺度为1.2 DoG 的局部极值点检测关键点是由 DOG 空间的局部极值点组成的。为了寻找 DoG 函数的极值点，每一个像素点要和它所有的相邻点比较，看其是否比它的图像域和尺度域的相邻点大或者小。中间的检测点和它同尺度的 8 个相邻点和上下相邻
6、尺度对应的 92 个点共 26 个点比较，以确保在尺度空间和二维图像空间都检测到极值点。 在极值比较的过程中，每一组图像的首末两层是无法进行极值比较的，为了满足尺度变化的连续性，我们在每一组图像的顶层继续用高斯模糊生成了 3 幅图像，高斯金字塔有每组 S+3 层图像。DOG 金字塔每组有 S+2 层图像。1.3 关键点精确定位由于 DoG 值对噪声和边缘较敏感,因此,在上面 DoG 尺度空间中检测到局部极值点还要经过进一步的检验才能精确定位为特征点。去除低对比度的极值点为了提高关键点的稳定性，需要对尺度空间 DoG 函数进行曲线拟合。利用 DoG 函数1.6.51.2在尺度空间的 Taylor
7、 展开式：其极值点： 在计算过程中，分别对图像的行、列及尺度三个量进行了修正，其修正结果如下：求解得为修正值。将修正后的结果代入式 上式去除那些对比度较低的不稳定极值点。Lowe 的试验显示，所有取值小于 0.04 的极值点均可抛弃（像素灰度值范围0，1 ） 。去除边缘响应仅仅去除低对比度的极值点对于极值点的对于特征点稳定性是远远不够的。DoG 函数在图像边缘有较强的边缘响应，因此我们还需要排除边缘响应DoG 函数的（欠佳的）峰值点在横跨边缘的方向有较大的主曲率，而在垂直边缘的方向有较小的主曲率。主曲率可以通过计算在该点位置尺度的 22 的 Hessian 矩阵得到，导数由采样点相邻差来估计：
8、表示 DOG 金字塔中某一尺度的图像 x 方向求导两次。D 的主曲率和 H 的特征值成正比，为了避免直接的计算这些特征值，而只是考虑它们的之间的比率。令 为最大特征值， 为最小的特征值，则在两特征值相等时达最小，随 r 的增长而增长。Lowe 论文中建议 r 取 10。时将关键点保留，反之剔除。21TTDXX,xy2TTD21()X21TTDXxyDxrxyTDxyet2221rtH21r2TrDet2 关键点描述2.1 关键点方向分配通过尺度不变性求极值点，可以使其具有缩放不变的性质，利用关键点邻域像素的梯度方向分布特性，我们可以为每个关键点指定方向参数方向，从而使描述子对图像旋转具有不变性
9、。通过求每个极值点的梯度来为极值点赋予方向。像素点的梯度表示梯度幅值：梯度方向：方向直方图的生成确定关键点的方向采用梯度直方图统计法，统计以关键点为原点，一定区域内的图像像素点对关键点方向生成所作的贡献。直方图以每 10 度方向为一个柱，共 36 个柱，柱所代表的方向为像素点梯度方向，柱的长短代表了梯度幅值。根据 Lowe 的建议，直方图统计半径采用 3*1.5*在直方图统计时，每相邻三个像素点采用高斯加权，根据 Lowe 的建议，模板采用0.25,0.5,0.25，并连续加权两次。关键点的主方向与辅方向关键点主方向：极值点周围区域梯度直方图的主峰值,也是特征点方向关键点辅方向：在梯度方向直方
10、图中，当存在另一个相当于主峰值 80%能量的峰值时，则将这个方向认为是该关键点的辅方向。这可以增强匹配的鲁棒性，Lowe 的论文指出大概有 15%关键点具有多方向，但这些点对匹配的稳定性至为关键。方向分配实现步骤1. 确定计算关键点直方图的高斯函数权重函数参数 ；2. 生成含有 36 柱的方向直方图，梯度直方图范围 0360 度，其中每 10 度一个柱。由半径为图像区域生成；3. 对方向直方图进行两次平滑；4. 求取关键点方向（可能是多个方向） ；,IgradIxy2 21,1,mLxyLxy,tan1,xyComment M&S1: 不懂5. 对方向直方图的 Taylor展开式进行二次曲线拟
11、合，精确关键点方向；图像的关键点已检测完毕，每个关键点有三个信息：位置、尺度、方向；同时也就使关键点具备平移、缩放、和旋转不变性。2.2 生成特征描述符描述的目的是在关键点计算后，用一组向量将这个关键点描述出来，这个描述子不但包括关键点，也包括关键点周围对其有贡献的像素点。用来作为目标匹配的依据，也可使关键点具有更多的不变特性，如光照变化、3D 视点变化等。通过对关键点周围图像区域分块，计算块内梯度直方图，生成具有独特性的向量，这个向量是该区域图像信息的一种抽象，具有唯一性。下图是一个 SIFT描述子事例。其中描述子由 228维向量表征，也即是 22个 8方向的方向直方图组成。左图的种子点由
12、88单元组成。每一个小格都代表了特征点邻域所在的尺度空间的一个像素，箭头方向代表了像素梯度方向，箭头长度代表该像素的幅值。然后在 44的窗口内计算 8个方向的梯度方向直方图。绘制每个梯度方向的累加可形成一个种子点，如右图所示：一个特征点由 4个种子点的信息所组成。关键点周围区域图像梯度 关键点描述子xyxy3octxytLowe 实验结果表明：描述子采用 448128 维向量表征，综合效果最优（不变性与独特性） 。128 维关键点描述子（就是特征描述符）生成步骤1. 确定计算描述子所需的图像区域描述子梯度方向直方图由关键点所在尺度的模糊图像计算产生。图像区域的半径通过下式计算：是关键点所在组（
13、octave）的组内尺度，2. 将坐标移至关键点主方向那么旋转角度后新坐标为：3.在图像半径区域内对每个像素点求其梯度幅值和方向，然后对每个梯度幅值乘以高斯权重参数，生成方向直方图。 该点与关键点的列距离该点与关键点的行距离等于描述子窗口宽度 直方图列数（取 4）的一半4.在窗口宽度为 2X2 的区域内计算 8 个方向的梯度方向直方图，绘制每个梯度方向的累加值，即可形成一个种子点。然后再在下一个 2X2 的区域内进行直方图统计，形成下一个种子点，共生成 16 个种子点。5.描述子向量元素门限化及门限化后的描述子向量规范化。321octdradiusoct 4dcosinixxyyd c1 -
14、d cd r1 - d r2,exp11krcowyweightradIyddkxyw3描述子向量元素门限化：方向直方图每个方向上梯度幅值限制在一定门限值以下（门限一般取 0.2） 。描述子向量元素规范化：为得到的 128 描述子向量为规范化后的向量关键点描述子向量的规范化正是可去除满足此模型的光照影响。对于图像灰度值整体漂移 ，图像各点的梯度是邻域像素相减得到，所以也能去除。3 关键点匹配分别对模板图（参考图，reference image）和实时图（观测图，observation image）建立关键点描述子集合。目标的识别是通过两点集内关键点描述子的比对来完成。具有128 维的关键点描述
15、子的相似性度量采用欧式距离。模板图中关键点描述子：实时图中关键点描述子：任意两描述子相似性度量：要得到配对的关键点描述子， 需满足：关键点的匹配可以采用穷举法来完成，但是这样耗费的时间太多，一般都采用一种叫kd 树的数据结构来完成搜索。搜索的内容是以目标图像的关键点为基准，搜索与目标图像的特征点最邻近的原图像特征点和次邻近的原图像特征点。Kd 树是一个平衡二叉树1218,WwLll 1/jji,218j12128,iiiRriiiSss1282,i ijijjdr,ijRSji pThresold实 时 图 中 距 离 最 近 的 点 实 时 图 中 距 离 的 次 最 近 点关键点匹配并不能标志着算法的结束，因为在匹配的过程中存在着大量的错配点。图中交叉的绿线为错配点4 消除错配点RANSAC（Random Sample Consensus，随机抽样一致 ）是一种鲁棒性的参数估计方法。RANSAC 实质上就是一个反复测试、不断迭代的过程。RANSAC 的基本思想：首先根据具体问题设计出某个目标函数，然后通
