关于SIFT算法与研究

1、学专年姓院 业 级 名学年论文（本科）数学与信息科学学院信息与计算科学2010 级赵佳佳、练赛、李：林马利军、李西振、张璐论文题冃 指导教师 成 绩sift算法研究职称2012年5月27日学年论文成绩评定表评语成绩：指导教师（签名）：2012年 月日学院意见：学院院长（签名）：2012年 月 日摘要4关键词4abstract4keyword41预备知识51.1 sift特征的定义51.2 sift特征的主耍特点51.3 sift的发展历程62 sift算法的步骤62.1尺度空间的生成62.2检测尺度空间极值点92.3精确定位极值点112.4为每个极值点指定方向参数122.5关键点描述了的形成1

2、33描述符的性能测试153.1描述符对于图像旋转变化的测试153.2描述符对于图像尺度变化的测试154 sift算法的实现165应用与前景17参考文献18sift算法研究摘 要：尺度不变特征转换(scale-invariant feature transform或sift)是一种电脑 视觉的算法用来侦测与描述影像屮的局部性特征，它在空间尺度小寻找极值点，并提 取出其位置、尺度、旋转不变量，此算法由david lowe在1999年所发表，2004年 完善总结。其应用范围包含物体辨识、机器人地图感知与导航、影像缝合、3d模型 建立、手势辨识、影像追踪和动作比对。此算法有其专利，专利拥有者为英屈哥伦

3、比 亚大学。关键词：尺度不变特征转换；电脑视觉；局部性特征；极值点algorithm study for siftabstract： scale invariant feature transform (scale-invariant feature transform or sift) is a computer vision algorithm for to detect the localized features in the description of the image, looking for extreme points in the spatial scale, and e

4、xtract its location scale, rotation invariant, the algorithm by david lowe in 1999, 2004 perfect summary. its scope of application include object recognition, robot map perception and navigation, image,3d modeling, gesture recognition, image tracking and action. this algorithm has its own patent, th

5、e patent holder for the university of british columbia.keyword： scale invariant feature transform; computer vision; locality characteristics; extreme points1预备知识1.1 sift特征的定义sift特征（scaleinvariant feature transform,尺度不变特征转换）是一种电脑视觉 的算法用来侦测与描述影像屮的局部性特征，它在空间尺度小寻找极值点，并提取出 其位置、尺度、旋转不变量，此算法由david lowe在199

6、9年所发表，2004年完善 总结。其应用范围包含物体辨识、机器人地图感知与导航、影像缝合、3d模型建立、 手势辨识、影像追踪和动作比对。此算法有其专利，专利拥有者为英属哥伦比亚大 学。局部影像特征的描述与侦测可以帮助辨识物体，sift特征是基于物体上的一些 局部外观的兴趣点而与影像的大小和旋转无关。对于光线、噪声、些微视角改变的 容忍度也相当高。基于这些特性，它们是高度显著而且相对容易撷取，在母数庞大的 特征数据库屮，很容易辨识物体而且鲜有课认。使用sift特征描述对于部分物体遮 蔽的侦测率也相当高，甚至只需要3个以上的sift物体特征就足以计算出位置与方 位。在现今的电脑硬件速度下和小型的特

7、征数据库条件卜辨识速度可接近即时运算。 sift特征的信息量大，适合在海量数据库小快速准确匹配。1.2 sift特征的只要特点从理论上说，sift是一种相似不变量，即对图像尺度变化和旋转是不变量。然 而，由于构造sift特征时，在很多细节上进行了特殊处理，使得sift对图像的复朵 变形和光照变化具有了较强的适应性，同时运算速度比较快，定位精度比较高。如：在多尺度空间采用dog算了检测关键点，相比传统的基于log算了的检测方 法，运算速度大大加快；关键点的精确定位不仅提高了精度，而且大大提高了关键点的稳定性；在构造描述了时，以了区域的统计特性，而不是以单个像素作为研究对象，提高 了对图像局部变形

8、的适应能力；对于16*16的关键点邻域和4*4的子区域，在处理梯度幅度时都进行了类似于高 斯函数的加权处理，强化了屮心区域，淡化了边缘区域的影响，从而提高了算法对儿 何变形的适应性；该方法不仅对通用的线性光照模型具有不变性，而且对复杂的光照变化亦具有一 定的适应性。关于这部分内容的细节，可参看文献"distinctive image features from scale-invariant keypoints".sift算法的特点：l.sift特征是图像的局部特征，其对旋转、尺度缩放、亮度 变化保持不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定性；2.独特 性（d

9、istinctiveness）信息量丰富，适用于在海量特征数据库屮进行快速、准确的匹配；3.多量性，即使少数的儿个物休也可以产生大量的sift特征向量；4.高速性, 经优化的sift匹配算法甚至可以达到实时的要求；5.可扩展性，可以很方便的与其 他形式的特征向量进行联合。1.3 sift的发展历程sift是一种基于特征的配准方法。sift特征匹配算法是david lowe在2004年 总结了现冇的基于不变量技术的特征检测方法的基础上，提出的一种基于尺度空间 的、对图像缩放、旋转甚至仿射变换保持不变性的特征匹配算法。该算法匹配能力较 强，能提取稳定的特征，可以处理两幅图像之间发生平移、旋转、仿射

10、变换、视角变 换、光照变换情况卜的匹配问题，甚至在某种程度上对任意角度拍摄的图像也具备较 为稳定的特征匹配能力，从而可以实现差异较大的两幅图像z间的特征的匹配。mikolajczyk和schmid针对不同的场景，对光照变化、图像几何变形、分辨率差 异、旋转、模糊和图像压缩等6种情况，就多种最具代表性的描述了（如sift,矩不 变量，互相关等10种描述子）进行了实验和性能比较，结果表明，在以上各种情况下,sift描述子的性能最好。2 sift算法的步骤2.1尺度空间的生成尺度空间理论口的是模拟图像数据的多尺度特征。（为了使特征具有尺度不变性, 特征点的检测是在多尺度空间完）成的。尺度空间理论最早

11、出现于计算机视觉领域时,其n的是模拟图像数据的多尺度特征。图2的诫 对赫 首弟 像世点前ij前 大图斤其是否 打它同尺 p度空间 卜两层的尺茂2.2检测为了 比它的艮 度的8彳 和二维艮 26个领龙图 2.2.1因为需要同相邻尺度进行比较，所以在一组高斯差分图像屮只能检测到两个尺度 的极值点，而其它尺度的极值点检测则需要在图像金字塔的上一层高斯差分图像中进 行。依次类推，最终在图像金字塔小不同层的高斯差分图像小完成不同尺度极值的检 测。当然这样产生的极值点并不都是稳定的特征点，因为某些极值点响应较弱，而且 dog算子会产生较强的边缘响应。构建尺度空间需确定的参数：b尺度空间坐标ooctave

12、坐标s sub-level 坐标o和 o、s 的关系 b(o,s) = c()2(f+s/s ,o g omin +0,o l, s w 0,51 其小r()是基准层尺度。ooctave坐标，s sub-level坐标。注：octaves的索引可 能是负的。第一组索引常常设为0或者1,当设为1的时候，图像在计算高斯尺度空 间前先扩大一倍。空间坐标兀是组octave的函数，设兀(是0组的空叫坐辆，贝ijx = 2=o,o e z,x0 e-1如果(m(),n(j是基础纟鮒：()翌 翅蚩，册萨由下式获得:o八0注：在lowe的文章中,lowe使用了如 种勺参数：6=().5,% = 1.62巴缶=

13、-1,s = 3 在组o=l,图像用双线性插值扩大一倍(对于扩大的图像6=1) 2.3精确定位极值点通过拟和三维二次函数以精确确定关键点的位置和尺度(达到亚像素精度)，同 时去除低对比度的关键点和不稳定的边缘响应点(因为dog算子会产生较强的边缘 响应)，以增强匹配稳定性、获取关键点处啾黔丄»x+lx兰 x求导并让方程等于尊f可以得到崩韧2°3d对应极值点，方程%)d(x)的值对于剔除低对比度的不稳定特彳点。球有用，通常将|d(x)|< 0.03的 极值点视为低对比度的不稳定特征点，进行剔除。同时，在此过程屮获取了特征点的 精确位置以及尺度。一个定义不好的高斯差分算子

14、的极值在横跨边缘的地方有较大的主曲率，而在垂 直边缘的方向有较小的主曲率。dog算了会产生较强的边缘响脛)需要剔抄不稳定的边缘响应点。获取特征点处的hessian矩阵，主曲誓&辿个2x尹的hessianml库h求出：tr(h) = dn qq、迪"h的特征值q和0代表兀和y方嚼的梯谨v“det=d d -(d )2 =a/3 7>(h)表示矩阵h对矛线気素乙昭 仔#方)表不瞩 h?的行歹位。彳 特征值，而jw制的蠻檢垓4 邛丄 縮0 + 0)=(厂 + 1(2.3-1)=a(2.3-2)q是较大的det(h)日xx丫皆沁d yy导数由釆样点相邻差估计得到。d的主曲率和h

15、的特征值成正比，令。为最大特征值，0为最小的特征值，则公 式(i+l)7r的值在两个特征值相等时最小，随着厂的增大而增大。值越大，说明两个 特征值的比值越大，e trfh)2(r + i)2 句的梯度值越小,而边缘恰恰就是这种彳 1 < : 小于一定的阈值,因此，为了检测主曲；det (h jv在lowe的文章中，取r=10。2.4为每个关点制定方向参数为了使描述符具有旋转不变性，需要利用图像的局部特征为给每一个关键点分配个方向。利用关键点邻域像素的梯度及方向分布的特性，可以得到梯度模值和方向如而（兀,y） = j（厶（兀 + 1丿）一l（x 1,刃）？ + （厶（兀,y + 1）-厶（

16、兀,y i）2其冷,（碱f腳茯佩辭it船保蝕-1）仏（兀+1）一 * -1, y）在以关键点为屮心的邻域窗口内采样，并用直方图统计邻域像素的梯度方向。梯 度直方图的范围是0360度，其屮每10度一个方向，总共36个方向。直方图的峰值则代表了该关键点处邻域梯度的主方向，即作为该关键点的方向。 在计算方向直方图时，需要用一个参数”等于关键点所在尺度1.5倍的高斯权重窗对 方向直方图进行加权，图4屮用蓝色的圆形表示，屮心处的蓝色较重，表示权值最大, 边缘处颜色潜，表示权值小。如图4所示，该示例中为了简化给出了8方向的方向直方 图计算结果，实际原文小釆用36方向的直方图。领域梯度方司关键点埒征向量图2

17、.5.1山关键点邻域梯度信息生成特征向疑接下来以关键点为中心取血8的窗口。图2.5.1左部分的中央黑点为当而关键点的 位置每个小格代表关键点邻域所在尺度空间的一个像素箭头方向代表该像素的梯度 方向，箭头长度代表梯度模值。图屮蓝色的圈代表高斯加权的范围（越靠近关键点的 像素梯度方向信息贡献越大）。然后在每4x4的小块上计算8个方向的梯度方向直方图, 绘制每个梯度方向的累加值，即可形成一个种子点，如图5右部分所示。此图屮一个 关键点由2x2共4个种子点组成，每个种子点有8个方向向量信息。这种邻域方向性信 息联合的思想增强了算法抗噪声的能力，同时对于含有定位误差的特征匹配也提供了 较好的容错性。实际

18、计算过程屮，为了增强匹配的稳健性，lowe建议对每个关键点使用4x4共16 个种了点來描述，这样对于一个关键点就可以产生128个数据，即最终形成128维的 sift特征向量。此时sift特征向量已经去除了尺度变化、旋转等几何变形因素的影响, 再继续将特征向量的长度归一化，则可以进一步去除光照变化的影响。当两幅图像的sift特征向量生成庇 下一步我们采用关键点特征向量的欧式距 离来作为两幅图像屮关键点的相似性判定度量。取图像1屮的某个关键点，并找出其 与图像2屮欧式距离最近的前两个关键点，在这两个关键点屮，如果最近的距离除以u.om 三 qe<53&or0.70.60.5 -夫头3

19、.貝复迄3.0.4角符、重1图3.2sift描述符对于尺度变化的性能测试sift特征点是在多尺度空间提取的，因此具有良好的尺度不变性。我们仍以多 幅测试图像为例，对图像的不同尺度进行了大量的实验，结果如图3.2.1所示。从该 实验结果屮可以看出，sift描述符具有非常良好的尺度不变性，图像按照尺度因子 从1到4.5进行尺度变化，描述符的重复度仍然保持在78%以上。当图像尺度因了大 于4.5时sift描述符也能够保持较高的重复度，但是随着尺度因子的不断变大，图 像极值点检测的运算量将变得比较大(一幅256x256的图像扩大5倍后尺寸为 1280x1280),对于大量的不同图像进行测试的工作量就更

20、加庞大，因此这里并未对 大尺度因子的图像进行类似实验。从以上的实验数据屮可以看出sift描述符确实具有非常鲁棒的旋转不变性以及 尺度不变性，这些优良的特性对于图像能否止确的配准和拼接起到了至关重要的作用。当然sift描述符对于噪声的干扰、光照条件的变化以及3d视角的变化也具有较好的魯棒性。4. sift算法的实现卜湎我们一步步实现此sift算法,来看看sift算法到底是怎么实现的。1、sift算法第一步:图像预处理。扩大图像，预滤波剔除噪声，得到金字塔的最底层第一阶的第一层。cvmat *scaleinitimage(cvmat * im);金字塔初始化2、sift算法第二步：建立高斯金字塔函

21、数。给定金字塔第一阶第一层图像后， 计算高斯金字塔其他尺度图像，每一阶的数冃由变量scalesperoctave决定，给 定一个基本图像，计算它的高斯金字塔图像，返回外部向量是阶梯指针，内部向量是 每一个阶梯内部的不同尺度图像。imageoctaves* buildgaussianoctaves(cvmat * image); 建立高斯金字塔3、sift算法第三步：特征点位置检测，最后确定特征点的位置检测dog金字 塔屮的局部最大值。找到z后，述要经过两个检验才能确认为特征点：一是它必须冇 明显的差异，二是他不应该是边缘点，(也就是说，在极值点处的主曲率比应该小于 某一个阈值)。int detectkeypoint(int numoctaves, imageoctaves * gaussianpyr);4、sift算法第四步：计算高斯图像的梯度方向和幅