sift算法详解和应用教育课件.ppt

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,Scale Invariant Feature Transform,SIFT,BEIJING INSTITUTE,OF TECHNOLOGY,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,sift算法详解和应用PPT讲座,2025/12/10 周三,2,SIFT,简介,SIFT,算法实现细节,提纲,SIFT,算法的应用领域,SIFT,算法的扩展与改进,2025/12/10 周三,3,SIFT,简介,传统的特征提取方法,成像匹配的核心问题是将同一目标在,不同时间,、,不同分辨率,、,不同光照,、,不同位姿,情况下所成的像相对应。传统的匹配算法往往是直接提取角点或边缘，对环境的适应能力较差，急需提出一种鲁棒性强、能够适应不同光照、不同位姿等情况下能够有效识别目标的方法。,2025/12/10 周三,4,1999,年,British Columbia,大学大卫,.,劳伊（,David G.Lowe,）教授总结了现有的基于不变量技术的特征检测方法，并正式提出了一种基于尺度空间的、对图像缩放、旋转甚至仿射变换保持不变性的图像局部特征描述算子,SIFT,（尺度不变特征变换），这种算法在,2004,年被加以完善。,SIFT,提出的目的和意义,David G.Lowe,Computer Science Department2366 Main MallUniversity of British ColumbiaVancouver,B.C.,V6T 1Z4,Canada,E-mail:,lowecs.ubc.ca,SIFT,简介,2025/12/10 周三,5,SIFT,简介,将一幅图像映射（变换）为一个,局部特征向量集,；特征向量具有平移、缩放、旋转不变性，同时对光照变化、仿射及投影变换也有一定不变性。,Original image,courtesy,of David Lowe,2025/12/10 周三,6,SIFT,简介,SIFT,算法特点,SIFT,特征是图像的,局部特征,，其对旋转、尺度缩放、亮度变化保持不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定性。,独特性,(Distinctiveness),好，信息量丰富，适用于在海量特征数据库中进行快速、准确的匹配。,多量性，即使少数的几个物体也可以产生大量,SIFT,特征向量。,经过优化的,SIFT,算法可满足一定的速度需求。,可扩展性，可以很方便的与其他形式的特征向量进行联合。,2025/12/10 周三,7,目标的自身状态、场景所处的环境和成像器材的成像特性等因素影响图像配准,/,目标识别跟踪的性能。而,SIFT,算法在一定程度上可解决：,目标的旋转、缩放、平移（,RST,）,图像仿射,/,投影变换（视点,viewpoint,）,光照影响（,illumination,）,目标遮挡（,occlusion,）,杂物场景（,clutter,）,噪声,SIFT,算法可以解决的问题,SIFT,简介,Back,2025/12/10 周三,8,SIFT,算法实现细节,SIFT,算法实现步骤简述,SIFT,算法的实质可以归为在不同尺度空间上查找特征点（关键点）的问题。,SIFT,算法实现物体识别主要有三大工序，,1,、提取关键点；,2,、对关键点附加详细的信息（局部特征）也就是所谓的描述器；,3,、通过两方特征点（附带上特征向量的关键点）的两两比较找出相互匹配的若干对特征点，也就建立了景物间的对应关系。,2025/12/10 周三,9,关键点检测,关键点描述,关键点匹配,消除错配点,SIFT,算法实现细节,SIFT,算法实现步骤,2025/12/10 周三,10,所谓关键点，就是在不同,尺度空间,的图像下检测出的具有方向,信息的局部极值点。,根据归纳，我们可以看出特征点具有的三个特征：,尺度 方向 大小,关键点检测,的相关概念,1.,哪些点是,SIFT,中要查找的关键点（特征点）？,这些点是一些,十分突出的点不会因光照条件的改变而消失,，比如,角点,、,边缘点,、,暗区域的亮点,以及,亮区域的暗点,，既然两幅图像中有相同的景物，,那么使用某种方法分别提取各自的稳定点，这些点之间会有相互对应的匹配点。,2025/12/10 周三,11,我们要精确表示的物体都是通过一定的尺度来反映的。现实世界的,物体也总是通过不同尺度的观察而得到不同的变化。,尺度空间理论最早在,1962,年提出，其主要思想是通过对原始图像进,行尺度变换，获得图像多尺度下的尺度空间表示序列，对这些序列进行,尺度空间主轮廓的提取，并以该主轮廓作为一种特征向量，实现边缘、,角点检测和不同分辨率上的特征提取等。,尺度空间中各尺度图像的模糊程度逐渐变大，能够模拟人在距离目,标由近到远时目标在视网膜上的形成过程。,尺度越大图像越模糊。,2.,什么是尺度空间（,scale space,）？,关键点检测,的,关键点检测,的相关概念,2025/12/10 周三,12,根据文献,Scale-space theory:A basic tool for analysing,structures at different scales,我们可知，高斯核是唯一可以产生,多尺度空间的核，一个图像的尺度空间，,L,（,x,y,),定义为原始图像,I(x,y),与一个可变尺度的,2,维高斯函数,G(x,y,),卷积运算。,关键点检测,高斯函数,尺度是自然存在的，不是人为创造的！高斯卷积只是表现尺度空间的一种形式,关键点检测,的相关概念,2025/12/10 周三,13,3.,高斯模糊,高斯模糊是在,Adobe Photoshop,等图像处理软件中广泛使用的处理,效果，通常用它来减小图像噪声以及降低细节层次。这种模糊技术生成,的图像的视觉效果是好像经过一个半透明的屏幕观察图像。,关键点检测,关键点检测,的相关概念,2025/12/10 周三,14,关键点检测,r,为模糊半径，,在减小图像尺寸的场合经常使用高斯模糊。在进行欠采样的时，通常在采样之前对图像进行低通滤波处理。这样就可以保证在采样图像中不会出现虚假的高频信息。,关键点检测,的相关概念,2025/12/10 周三,15,在实际应用中，在计算高斯函数的离散近似时，在大概,3,距离之外的像素都可以看作不起作用，这些像素的计算也就可以忽略。,通常，图像处理程序只需要计算,关键点检测,高斯模板大小的选择,0.00000067,0.00002292,0.00019117,0.00038771,0.00019117,0.00002292,0.00000067,0.00002292,0.00078633,0.00655965,0.01330373,0.00655965,0.00078633,0.00002292,0.00019117,0.00655965,0.05472157,0.11098164,0.05472157,0.00655965,0.00019117,0.00038771,0.01330373,0.11098164,0.22508352,0.11098164,0.01330373,0.00038771,0.00019117,0.00655965,0.05472157,0.11098164,0.05472157,0.00655965,0.00019117,0.00002292,0.00078633,0.00655965,0.01330373,0.00655965,0.00078633,0.00002292,0.00000067,0.00002292,0.00019117,0.00038771,0.00019117,0.00002292,0.00000067,高斯模板,关键点检测,的相关概念,2025/12/10 周三,16,高斯模糊具有圆对称性。,高斯模糊具有,线性可分,的性质，也可以在,二维图像上对两个独立的一维空间分别进行计算,。这样可以大大,减少了运算的次数,。,对一幅图像进行多次连续高斯模糊的效果与一次更大的高斯模糊可以产生同样的效果，大的高斯模糊的半径是所用多个高斯模糊半径平方和的平方根。例如，使用半径分别为,6,和,8,的两次高斯模糊变换得到的效果等同于一次半径为,10,的高斯模糊效果，,根据这个关系，使用多个连续较小的高斯模糊处理不会比单个高斯较大处理时间要少。,高斯模糊的性质,关键点检测,关键点检测,的相关概念,2025/12/10 周三,17,高斯金子塔的构建过程可分为两步：,（,1,）对图像做高斯平滑；,（,2,）对图像做降采样。,为了让尺度体现其连续性，在简单,下采样的基础上加上了高斯滤波。,一幅图像可以产生几组（,octave,）,图像，一组图像包括几层,（,interval,）图像。,4.,高斯金字塔,关键点检测,关键点检测,的相关概念,2025/12/10 周三,18,高斯图像金字塔共,o,组、,s,层，,则有：,关键点检测,的相关概念,尺度空间坐标；,s,sub-level,层坐标；,0,初始尺度；,S,每组层数（一般为,35,）。,2025/12/10 周三,19,高斯金字塔的初始尺度,当图像通过相机拍摄时，相机的镜,头已经对图像进行了一次初始的模,糊，所以根据高斯模糊的性质：,M,、,N,分别为图像的行数和列数,第,0,层尺度,被相机镜头模糊后的尺度,高斯金字塔的组数,关键点检测,的相关概念,2025/12/10 周三,20,高斯金字塔的组内尺度与组间尺度,组内尺度是指同一组（,octave,）内的,尺度关系，组内相邻层尺度化简为：,组间尺度是指不同组直接的尺度关,系，相邻组的尺度可化为：,由此可见，相邻两组的同一层尺度为,2,倍的关系,关键点检测,的相关概念,2025/12/10 周三,21,最后可将组内和组间尺度归为：,i,金字塔组数,n,每一组的层数,关键点检测,的相关概念,2025/12/10 周三,22,关键点检测,的相关概念,上一组图像的底层是由前一组图像的倒数第二层图像隔点采样生成的。,这样可以保持尺度的连续性。,？,为啥？,2025/12/10 周三,23,关键点检测,DOG,通过研究,Lowe,教授的论文发现，所有特征点的检测都是基于了尺度不,变的特性，特征点的检测占据了论文的大部分的篇章，,具有十分重要的,意义！,Lindeberg,在文献,Scale-space theory:A basic tool for analysing,structures at different scales,指出尺度规范化的,LoG,算子具有真正,的尺度不变性。,LoG,算子即（,Laplacion of Gaussian,）,可以由高斯函数梯度算子,GOG,构建,尺度规范化的,GoG,算子,尺度规范化的,LoG,算子,2025/12/10 周三,24,LOG,算子与高斯核函数的关系,通过推导可以看出，,LOG,算子与高斯核函数的差有直接关系，,由此引入一种新的算子,DOG,（,Difference of Gaussians,），,即,高斯差分算子。,关键点检测,DOG,2025/12/10 周三,25,DoG,（,Difference of Gaussian,）函数,DoG,在计算上只需相邻尺度高斯平滑后图像相减，因此简化了计算！,关键点检测,DOG,应该是同一组内的相邻层吧？,2025/12/10 周三,26,DoG,高斯差分金字塔,对应,DOG,算子，我们要构建,DOG,金字塔,我们可以通过,高斯差分图像,看出图像上的像素值变化情况。（如果没有变化，也就没有特征。特征必须是变化尽可能多的点。）,DOG,图像描绘的是目标的轮廓。,关键点检测,DOG,2025/12/10 周三,27,关键点检测,DOG,2025/12/10 周三,28,在检测极值点前对原始图像的高斯平滑以致图像丢失高频信息，所以,Lowe,建议在建立尺度空间前首先对原始图像长宽扩展一倍，以保留原始图像信息，增加特征点数量。,在,Lowe,的论文中，将第,0,层的初始尺度定为,1.6,，图片的初始尺度定为,0.5,，,则图像金字塔第,0,层的实际尺度为,当对图像长宽扩展一倍时，便构建了,-1,层，该层尺度为,关键点检测,DOG,P.S.:,图像插值时，选用的插值函数可以是多种多样的。,2025/12/10 周三,29,中间的检测点和它同尺度的,8,个相邻点和上下相邻尺度对应的,92,个点共,26,个点比较，以确保在尺度空间和二维图像空间都检测到极值点。,DoG,的局部极值点,关键点是由,DOG,空间的局部极值点组成的。,为了寻找,DoG,函数的极值点，,每一个像素点要和它所有的相邻点比较，看其是否比它的图像域和尺度域,的相邻点大或者小。,DoG,局部极值检测,2025/12/10 周三,30,在极值比较的过程中，每一组图像的首末两层是无法进行极值比较的，为了满足尺度变化的连续性，我们在每一组图像的顶层继续用高斯模糊生成了,3,幅图像，高斯金字塔有每组,S+3,层图像。,DOG,金字塔每组有,S+2,层图像,右图为不同尺度不同层间极值检测示意图。,P.S.:,我们只牺牲了,-1,组的第,0,层和第,N,组的最高层,DoG,局部极值检测,2025/12/10 周三,31,DoG,局部极值检测,关键点精确定位,为了提高关键点的稳定性，需要对尺度空间,DoG,函数进行曲线拟合。利用,DoG,函数在尺度空间的,Taylor,展开式：,其极值点,由于,DoG,值对噪声和边缘较敏感,因此,在上面,DoG,尺度空间中检测到局部,极值点还要经过进一步的检验才能精确定位为特征点。,2025/12/10 周三,32,DoG,局部极值检测,上式去除那些对比度较低的不稳定极值点。,Lowe,的试验显示，所有取值小于,0.04,的极值点均可抛弃（,像素灰度值范围,0,，,1,）。,在计算过程中，分别对图像的行、列及尺度三个量进行了修正，其修正结果如下：,为修正值,在,Lowe,的程序中，对坐标进行了五次修正。,将修正后的结果代入式,求解得,2025/12/10 周三,33,DoG,局部极值检测,去除边缘响应,仅仅去除低对比度的极值点对于极值点的对于特征点稳定性是远远不够的。,DoG,函数在图像边缘有较强的边缘响应，因此我们还需要排除边缘响应。,DoG,函数的（欠佳的）峰值点在横跨边缘的方向有较大的主曲率，而在垂直边缘的方向有较小的主曲率。主曲率可以通过计算在该点位置尺度的,22,的,Hessian,矩阵,得到，导数由采样点相邻差来估计,：,表示,DOG,金字塔中某一尺度的图像,x,方向求导两次,2025/12/10 周三,34,在两特征值相等时达最小，随,r,的增长而增长。,Lowe,论文中建议,r,取,10,。,DoG,局部极值检测,D,的主曲率和,H,的特征值成正比，为了避免直接的计算这些特征值，而只是考虑它们的之间的比率。令为 最大特征值 ，为最小的特征值，则,时将关键点保留，反之剔除,2025/12/10 周三,35,关键点方向分配,通过尺度不变性求极值点，可以使其具有缩放不变的性质，利用关键点邻域像素的梯度方向分布特性，我们可以为每个关键点指定方向参数方向，,从而使描述子对图像旋转具有不变性。,像素点的梯度表示,梯度幅值：,梯度方向：,我们通过求每个极值点的梯度来为极值点赋予方向。,2025/12/10 周三,36,关键点方向分配,方向直方图的生成,确定关键点的方向采用梯度直方图统计法，统计以关键点为原点，一定区域内的图像像素点对关键点方向生成所作的贡献。,2025/12/10 周三,37,1.,直方图以每,10,度方向为一个柱，共,36,个柱，柱所代表的方向为像,素点梯度方向，柱的长短代表了梯度幅值。,2.,根据,Lowe,的建议，直方图统计半径采用,3*1.5*,。,3.,在直方图统计时，每相邻三个像素点采用高斯加权，根据,Lowe,的,建议，模板采用,0.25,0.5,0.25,，并连续加权两次。,关键点方向分配,关于方向直方图的几点说明,2025/12/10 周三,38,关键点方向分配,关键点,主方向,：极值点周围区域梯度直方图的,主,峰值也是特征点方向,关键点,辅方向,：,在梯度方向直方图中，当存在另一个相当于主峰值,80%能量的峰值时，则将这个方向认为是该关键点的辅方向。,这可以增强匹配的鲁棒性,，,Lowe的论文指出大概有15%关键点具有多方向，但这些点对匹配的稳定性至为关键。,关键点的主方向与辅方向,2025/12/10 周三,39,关键点方向分配,确定计算关键点直方图的高斯函数权重函数参数；,生成含有,36,柱的方向直方图，梯度直方图范围,0360,度，其中每,10,度一个柱。由半径为图像区域生成；,对方向直方图进行两次平滑；,求取关键点方向（可能是多个方向）；,对方向直方图的,Taylor,展开式进行二次曲线拟合，精确关键点方向；,方向分配实现步骤,图像的关键点已检测完毕，每个关键点有三个信息：位置、尺度、方向；同时也就使关键点具备平移、缩放、和旋转不变性。,Back,2025/12/10 周三,40,关键点描述,描述的目的,描述的思路,通过对关键点周围图像区域分块，计算块内梯度直方图，生成具有独特性的向量，这个向量是该区域图像信息的一种抽象，具有唯一性。,描述的目的是在关键点计算后，用一组向量将这个关键点描述出来，这个描述子不但包括关键点，也包括关键点周围对其有贡献的像素点。用来作为目标匹配的依据，也可使关键点具有更多的不变特性，如光照变化、,3D,视点变化等。,2025/12/10 周三,41,关键点描述,下图是一个SIFT描述子事例。其中描述子由228维向量表征，也即是22个8方向的方向,直方图组成。,左图的种子点由,8,8,单元组成。每一个小格都代表了特征点邻域所在的尺度空间的一个像素，箭头方向代表了像素梯度方向，箭头长度代表该像素的幅值。然后在,4,4,的窗口内计算,8,个方向的梯度方向直方图。绘制每个梯度方向的累加可形成一个种子点，如右图所示：一个特征点由,4,个种子点的信息所组成。,2025/12/10 周三,42,关键点描述,Lowe实验结果表明,：,描述子采用448128维向量表征,，,综合效果最优（不变性与独特性）。,2025/12/10 周三,43,关键点描述,是关键点所在组（octave）的组内尺度，,1.,确定,计算,描述子所需的图像区域,描述子梯度方向直方图由关键点所在尺度的模糊图像计算产生。图像区域的半径通过下式计算,：,128,维关键点描述子生成步骤,2025/12/10 周三,44,关键点描述,2.,将坐标移至关键点主方向,那么旋转角度后新坐标为：,2025/12/10 周三,45,：,等于描述子窗口宽度,直方图列数（取4）的一半；,关键点描述,：,该点与关键点的列距离,；,：,该点与关键点的,行,距离,；,3.,在图像半径区域内对每个像素点求其梯度幅值和方向，然后对每个梯,度幅值乘以高斯权重参数，生成方向直方图。,2025/12/10 周三,46,4.,在窗口宽度为,2X2,的区域内计算,8,个方向的梯度方向直方图，绘制每个,梯度方向的累加值，即可形成一个种子点。然后再在下一个,2X2,的区域,内进行直方图统计，形成下一个种子点，共生成,16,个种子点。,5.,描述子向量元素门限化及门限化后的描述子向量规范化。,描述子向量元素门限化：,方向直方图每个方向上梯度幅值限制在一定门限值以下（门限一般取,0.2,）。,描述子向量元素规范化：,为得到的,128,描述子向量,为规范化后的向量,关键点描述,2025/12/10 周三,47,关键点描述,关键点,描述子向量的规范化正是可去除,满足此模型的光照,影响,。,对于图像灰度值整体漂移，图像各点的梯度是邻域像素相减得到，所以也能去除。,Back,2025/12/10 周三,48,关键点匹配,分别对模板图（参考图，,reference image,）和实时图（观测图，,observation image,）建立关键点描述子集合。目标的识别是通过两点集内关键点描述子的比对来完成。具有,128,维的关键点描述子的相似性度量采用欧式距离。,2025/12/10 周三,49,关键点匹配,原图像,目标图像,穷举匹配,2025/12/10 周三,50,模板图中关键点描述子：,实时图中关键点描述子：,任意两描述子相似性度量：,要得到配对的关键点描述子，需满足：,关键点匹配,2025/12/10 周三,51,关键点的匹配可以采用穷举法来完成，但是这样耗费的时间太多，一般都采用一种叫,kd,树的数据结构来完成搜索。搜索的内容是以目标图像的关键点为基准，搜索与目标图像的特征点最邻近的原图像特征点和次邻近的原图像特征点。,关键点匹配,Kd,树是一个平衡二叉树,2025/12/10 周三,52,关键点匹配,Back,2025/12/10 周三,53,关键点匹配并不能标志着算法的结束，因为在匹配的过程中存在着大量的错配点。,消除错配点,图中交叉的绿线为错配点,2025/12/10 周三,54,消除错配点,RANSAC,（,Random Sample Consensus,，,随机抽样一致,）是一种鲁棒性的参数估计方法。,RANSAC,简介,RANSAC,实质上就是一个反复测试、不断迭代的过程。,RANSAC,的,基本思想,：,首先根据具体问题设计出某个目标函数，然后通过反复提取最小点集估计该函数中参数的初始值，利用这些初始值把所有的数据分为,“,内点,”,（,inlier,）和,“,外点,“,（,outlier,），最后用所有的内点重新计算和估计函数的参数。,2025/12/10 周三,55,消除错配点,RANSAC,事例,如何估计最佳直线？,重复进行，拟合最优直线,随机取两样本点拟合直线,拟合直线：,Back,2025/12/10 周三,56,SIFT,算法的应用,SIFT,算法目前在军事、工业和民用方面都得到了不同程度的应用，其应用已经渗透了很多领域，典型的应用如下：,物体识别,机器人定位与导航,图像拼接,三维建模,手势识别,视频跟踪,笔记鉴定,指纹与人脸识别,犯罪现场特征提取,2025/12/10 周三,57,SIFT,算法的应用,物体识别,2025/12/10 周三,58,SIFT,算法的应用,图像拼接,Demo,2025/12/10 周三,59,三维建模,SIFT,算法的应用,2025/12/10 周三,60,SIFT,算法的应用,手势识别,目前，手势识别已应用于手机等设备上。,2025/12/10 周三,61,笔记鉴定,SIFT,算法的应用,2025/12/10 周三,62,来自网友的创意,周正龙的老虎,SIFT,算法的应用,图,1,周正龙的华南虎照片与年画上的华南虎照片,12,点匹配,图,2,周正龙的华南虎照片与真实的华南虎照片,0,点匹配,Back,2025/12/10 周三,63,SIFT,算法的扩展与改进,SIFT,在图像的不变特征提取方面拥有无与伦比的优势，但其并不是完美的，仍然存在着实时性不高、有时特征点较少、对边缘模糊的目标无法准确提取特征点等缺陷。自从,1999,年，,SIFT,算法问世以来，人们从未停止对它的优化和改进。,2025/12/10 周三,64,SIFT,算法的扩展与改进,PCA-SIFT,PCA,（,Principal Component Analysis,），即主成分分析，是一种数据降维,技术。由,Y.ke 2004,年提出。,通过降维技术，可有效化简,SIFT,算子的,128,维描述子。,2025/12/10 周三,65,CSIFT,（,Colored scale invariant feature transform,）彩色尺度特,征不变变换，可以针对彩色图像进行图像的不变特征提取。由,Farag,2006,年提出。,SIFT,算法的扩展与改进,CSIFT,2025/12/10 周三,66,SIFT,算法的扩展与改进,SURF,SURF,（,SURF Speeded Up Robust Features,），号称是,SIFT,算法的增强版，,SURF,算法的计算量小，运算速度快，提取,的特征点几乎与,SIFT,相同，由,Bay 2006,年提出。,SIFT,SURF,特征点检测,用不同尺度的图片与高斯函数做卷积,用不同大小的,box filter,与原始图像,(integral image),做卷积，,易于并行,方向,特征点邻接矩形区域内，利用梯度直方图计算,特征点邻接圆域内，计算,x,、,y,方向上的,Haar,小波响应,描述符生成,20*20(,单位为,pixel),区域划分为,4*4(,或,2*2),的子区域，每个子域计算,8bin,直方图,20*20(,单位为,sigma),区域划分为,4*4,子域，每个子域计算,5*5,个采样点的,Haar,小波响,应，记录,dx,dy,|dx|,|dy|,。,2025/12/10 周三,67,SIFT,算法的扩展与改进,method,Time,Scale,Rotation,Blur,Illumination,Affine,Sift,common,best,best,common,common,good,PCA-sift,good,good,good,best,good,best,Surf,best,common,common,good,best,good,SIFT,、,PCA-SIFT,与,SURF,的对比,2025/12/10 周三,68,ASIFT,（,Affine-SIFT,）抗仿射,SIFT,变换。,两个向量空间之间的一个仿射变换或者仿射映射由一个线性变换接上一,个平移组成。,ASIFT,可以抵抗强仿射情况，提取的特征点远多于,SIFT,算,法，由,J.M.Morel 2009,年提出。,ASIFT,SIFT,算法的扩展与改进,Demo,2025/12/10 周三,69,谢 谢！,