单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,尺度不变特征变换匹配算法,Scale Invariant Feature Transform,（,SIFT,）,报告人：邵妍,2012,年,2,月,29,日,Sift,算法简介,Sift,是,David Lowe,于,1999,年提出的局部特征描述子，并于,2004,年进行了更深入的发展和完善。,Sift,特征匹配算法可以处理两幅图像之间发生平移、旋转、仿射变换情况下的匹配问题，具有很强的匹配能力。,SIFT,算法基于图像特征尺度选择的思想，建立图像的多尺度空间，在不同尺度下检测到同一个特征点，确定特征点位置的同时确定其所在尺度，以达到尺度抗缩放的目的，剔出一些对比度较低的点以及边缘响应点以后提取每个稳定关键点周围的局部特征，形成局部描述子并将其用在以后的匹配中。,Sift,算法简介,sift,算法特点：,SIFT,特征是图像的局部特征，其对旋转、尺度缩放、亮度变化保持不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定性。,独特性,(Distinctiveness),好，信息量丰富，适用于在海量特征数据库中进行快速、准确的匹配。,多量性，即使少数的几个物体也可以产生大量,SIFT,特征向量。,经过优化的,SIFT,算法可满足一定的速度需求。,可扩展性，可以很方便的与其他形式的特征向量进行联合。,SIFT,算法步骤：,1,）检测尺度空间极值点,2,）精确定位极值点,3,）为每个关键点指定方向参数,4,）关键点描述子的生成,Sift,算法简介,尺度空间的生成,高斯卷积核是实现尺度变换的唯一线性核，于是一幅二维图像的尺度空间定义为：,其中，是尺度可变高斯函数，并且有：,（,x,y),是空间坐标，是尺度坐标。的大小决定图像的平滑程度，大尺度对应图像的概貌特征，小尺度对应图像的细节特征。大的,值对应粗糙尺度,(,低分辨率,),，反之，对应精细尺度,(,高分辨率,),。,为了有效的在尺度空间检测到稳定的关键点，提出了高斯差分尺度空间（,DOG scale-space,）。利用不同尺度的高斯差分核与图像卷积生成。,高斯差分尺度空间,极值点检测,为了寻找尺度空间的极值点，每一个采样点要和它所有的相邻点比较，看其是否比它的图像域和尺度域的相邻点大或者小。如图,3,所示，中间的检测点和它同尺度的,8,个相邻点和上下相邻尺度对应的,92,个点共,26,个点比较，以确保在尺度空间和二维图像空间都检测到极值点。,精确定位极值点,通过上步检测出了每个尺度上的极值点，现在就需要采用拟合三维二次函数求得极值点在原图像中的位置。并且为了增强特征点匹配时的稳定性和抗噪能力还需要去除低对比度的关键点和边缘响应点,(,因为,DoG,算子会产生较强的边缘响应,),等不稳定的点。,精确定位极值点,定位极值点：,令极值点,A,对 进行泰勒展开：,（,1,）,其中，是到点,A,的偏移量。对（,1,）式求,X,的偏导数，并令偏倒为,0,，得到,（,2,）,如果 大于,0.5,，则意味着这个极值点与另一个采样点离得更近，需采用插值法求得极值点位置的估计值。,精确定位极值点,去除低对比度的关键点：,将上式（,2,）带入公式（,1,）中即可得,通过观察实验结果得出，小于,0.03,的极值点均将被丢弃。阈值 越小，则会获得越多的匹配点个数,精确定位极值点,去除边缘上的极值点：,曲面上每个点都有两个主方向，并且沿这两个主方向的法曲率（即两个主曲率）分别是曲面在该点法曲率的最大值和最小值。在边缘上的极值点，垂直于边缘的方向上，法曲率最大，沿边缘的方向上，法曲率最小。如果极值点分布在边缘上，该点的法曲率最大值和最小值之比一般情况下要比非边缘点的比值大。根据这种思想，我们可以设一个比,值的阈值，当比值大于这个阈值就认为极值点在边缘上。,精确定位极值点,去除边缘上的极值点：,首先计算待测极值点的,Hessian,矩阵：,设 是较大的特征值，是较小的特征值，则由矩阵性质知：,设 ，则可得：,判断是否是边缘点只需判断上式左边项是否在某个阈值之下即可。实验表明一般阈值取,r=10,时。,关键点方向分配,SIFT,特征实现旋转不变性的基本思想是采用,“,相对,”,的概念。先为关键点赋一个方向，定义的关键点描述子均是相对于该方向的，因而可以实现匹配时的旋转无关性。,为实现尺度无关，根据关键点所在尺度选择与该尺度最相近的高斯平滑图像,L,。对,L,上的每个点,L,（,x,，,y,），计算梯度和方向：,关键点方向分配,以关键点为中心，划定一个邻域，利用所有在此区域内的点的梯度形成一个方向直方图。直方图的横坐标是梯度方向，共,36,项，每项代表了,10,度的范围；纵坐标是梯度大小，对于归到横坐标上任一项内所有的点，将其梯度大小相加，其和作为纵坐标。下图所示：,关键点方向分配,从直方图中选出纵坐标值最大的一项的方向作为该关键点的主方向。如果存在其他方向，纵坐标的大小大于主方向纵坐标大小的,80%,，也将其作为该关键点的方向。特征点有多个方向的情况下，实际上是在此位置上有多个关键点，他们的方向不同。,描述子生成,前面已经为关键点赋予了图像位置、尺度以及方向，这一步将根据关键点周围的局部特征计算得出一个特征描述子。,如下图所示，在关键点周围取一个邻域，并对其中点的梯度做高斯加权。这个邻域分为,16,个子区域，每个子区域取八个方向。,实 验,实验一 特征匹配,实验简介：,对两幅商标图像进行高斯差分金字塔的构建，并提取出关键点，最后通过关键点特征向量的欧氏距离作为关键点的相似性度量对两幅图像的关键点进行匹配。,高斯差分金字塔构建结果,实验一 特征匹配,实验一 特征匹配,定位特征点,实验一 特征匹配,关键点匹配,图,1,：两幅相似图像的匹配结果,图二：两幅不相似图像的匹配结果,数据库：,100,幅二值商标图像，图像的分辨率为,111x111,在,100,幅图像中，大致可以分为十种商标，每种商标分别有,10,幅由旋转、缩放等处理得到的相似图像,实验二 图像检索,实验二 图像检索,待检索图像,：,检索结果：,实验二 图像检索,待检索图像：,检索结果：,实验二 图像检索,在该试验中，随机抽取,10,幅待检索图像进行检索的查全率为,92%,，根据实验结果可以看出,sift,特征具有很好的旋转和尺度不变性，但总体来说，还该实验存在一定的问题：,1.,对于那些很简单的商标图像检索不出关键点，或只能检索出很少的关键点，这样就影响了这种图像的检索正确率。,2.,还存在一定的误匹配点,实验,Thanks!,