BEIJINGINSTITUTEOFTECHNOLOGY2012/3/271/60尺度不变特征变换匹配算法ScaleInvariantFeatureTransform(SIFT)ScaleInvariantFeatureTransformSIFT2012/3/2721.SIFT简介2.SIFT算法实现细节提纲3.SIFT算法的应用领域4.SIFT算法的扩展与改进ScaleInvariantFeatureTransformSIFT2012/3/273SIFT简介传统的特征提取方法•成像匹配的核心问题是将同一目标在不同时间、不同分辨率、不同光照、不同位姿情况下所成的像相对应。传统的匹配算法往往是直接提取角点或边缘,对环境的适应能力较差,急需提出一种鲁棒性强、能够适应不同光照、不同位姿等情况下能够有效识别目标的方法。ScaleInvariantFeatureTransformSIFT2012/3/274•1999年BritishColumbia大学大卫.劳伊(DavidG.Lowe)教授总结了现有的基于不变量技术的特征检测方法,并正式提出了一种基于尺度空间的、对图像缩放、旋转甚至仿射变换保持不变性的图像局部特征描述算子-SIFT(尺度不变特征变换),这种算法在2004年被加以完善。SIFT提出的目的和意义DavidG.LoweComputerScienceDepartment2366MainMallUniversityofBritishColumbiaVancouver,B.C.,V6T1Z4,CanadaE-mail:lowe@cs.ubc.caSIFT简介ScaleInvariantFeatureTransformSIFT2012/3/275SIFT简介将一幅图像映射(变换)为一个局部特征向量集;特征向量具有平移、缩放、旋转不变性,同时对光照变化、仿射及投影变换也有一定不变性。OriginalimagecourtesyofDavidLoweScaleInvariantFeatureTransformSIFT2012/3/276SIFT简介SIFT算法特点•SIFT特征是图像的局部特征,其对旋转、尺度缩放、亮度变化保持不变性,对视角变化、仿射变换、噪声也保持一定程度的稳定性。•独特性(Distinctiveness)好,信息量丰富,适用于在海量特征数据库中进行快速、准确的匹配。•多量性,即使少数的几个物体也可以产生大量SIFT特征向量。•经过优化的SIFT算法可满足一定的速度需求。•可扩展性,可以很方便的与其他形式的特征向量进行联合。ScaleInvariantFeatureTransformSIFT2012/3/277目标的自身状态、场景所处的环境和成像器材的成像特性等因素影响图像配准/目标识别跟踪的性能。而SIFT算法在一定程度上可解决:•目标的旋转、缩放、平移(RST)•图像仿射/投影变换(视点viewpoint)•光照影响(illumination)•目标遮挡(occlusion)•杂物场景(clutter)•噪声SIFT算法可以解决的问题SIFT简介BackScaleInvariantFeatureTransformSIFT2012/3/278SIFT算法实现细节SIFT算法实现步骤简述SIFT算法的实质可以归为在不同尺度空间上查找特征点(关键点)的问题。特征点检测特征点描述目标的特征点集特征点匹配目标的特征点集目标图像SIFT特征点检测特征点描述原图像SIFT匹配点矫正SIFT算法实现物体识别主要有三大工序,1、提取关键点;2、对关键点附加详细的信息(局部特征)也就是所谓的描述器;3、通过两方特征点(附带上特征向量的关键点)的两两比较找出相互匹配的若干对特征点,也就建立了景物间的对应关系。ScaleInvariantFeatureTransformSIFT2012/3/2791.关键点检测2.关键点描述3.关键点匹配4.消除错配点SIFT算法实现细节SIFT算法实现步骤ScaleInvariantFeatureTransformSIFT2012/3/2710所谓关键点,就是在不同尺度空间的图像下检测出的具有方向信息的局部极值点。根据归纳,我们可以看出特征点具有的三个特征:尺度方向大小关键点检测的相关概念1.哪些点是SIFT中要查找的关键点(特征点)?这些点是一些十分突出的点不会因光照条件的改变而消失,比如角点、边缘点、暗区域的亮点以及亮区域的暗点,既然两幅图像中有相同的景物,那么使用某种方法分别提取各自的稳定点,这些点之间会有相互对应的匹配点。ScaleInvariantFeatureTransformSIFT2012/3/2711我们要精确表示的物体都是通过一定的尺度来反映的。现实世界的物体也总是通过不同尺度的观察而得到不同的变化。尺度空间理论最早在1962年提出,其主要思想是通过对原始图像进行尺度变换,获得图像多尺度下的尺度空间表示序列,对这些序列进行尺度空间主轮廓的提取,并以该主轮廓作为一种特征向量,实现边缘、角点检测和不同分辨率上的特征提取等。尺度空间中各尺度图像的模糊程度逐渐变大,能够模拟人在距离目标由近到远时目标在视网膜上的形成过程。尺度越大图像越模糊。2.什么是尺度空间(scalespace)?关键点检测的关键点检测的相关概念ScaleInvariantFeatureTransformSIFT2012/3/2712根据文献《Scale-spacetheory:Abasictoolforanalysingstructuresatdifferentscales》我们可知,高斯核是唯一可以产生多尺度空间的核,一个图像的尺度空间,L(x,y,σ),定义为原始图像I(x,y)与一个可变尺度的2维高斯函数G(x,y,σ)卷积运算。关键点检测,,,,*,LxyGxyIxy22221()(),,exp22iiiixxyyGxy高斯函数尺度是自然存在的,不是人为创造的!高斯卷积只是表现尺度空间的一种形式…关键点检测的相关概念ScaleInvariantFeatureTransformSIFT2012/3/27133.高斯模糊高斯模糊是在AdobePhotoshop等图像处理软件中广泛使用的处理效果,通常用它来减小图像噪声以及降低细节层次。这种模糊技术生成的图像的视觉效果是好像经过一个半透明的屏幕观察图像。关键点检测关键点检测的相关概念ScaleInvariantFeatureTransformSIFT2012/3/2714关键点检测2221rrexp22G22r=xyr为模糊半径,在减小图像尺寸的场合经常使用高斯模糊。在进行欠采样的时,通常在采样之前对图像进行低通滤波处理。这样就可以保证在采样图像中不会出现虚假的高频信息。关键点检测的相关概念ScaleInvariantFeatureTransformSIFT2012/3/2715•在实际应用中,在计算高斯函数的离散近似时,在大概3σ距离之外的像素都可以看作不起作用,这些像素的计算也就可以忽略。•通常,图像处理程序只需要计算关键点检测(61)(61)高斯模板大小的选择0.000000670.000022920.000191170.000387710.000191170.000022920.000000670.000022920.000786330.006559650.013303730.006559650.000786330.000022920.000191170.006559650.054721570.110981640.054721570.006559650.000191170.000387710.013303730.110981640.225083520.110981640.013303730.000387710.000191170.006559650.054721570.110981640.054721570.006559650.000191170.000022920.000786330.006559650.013303730.006559650.000786330.000022920.000000670.000022920.000191170.000387710.000191170.000022920.00000067高斯模板关键点检测的相关概念ScaleInvariantFeatureTransformSIFT2012/3/2716•高斯模糊具有圆对称性。•高斯模糊具有线性可分的性质,也可以在二维图像上对两个独立的一维空间分别进行计算。这样可以大大减少了运算的次数。•对一幅图像进行多次连续高斯模糊的效果与一次更大的高斯模糊可以产生同样的效果,大的高斯模糊的半径是所用多个高斯模糊半径平方和的平方根。例如,使用半径分别为6和8的两次高斯模糊变换得到的效果等同于一次半径为10的高斯模糊效果,根据这个关系,使用多个连续较小的高斯模糊处理不会比单个高斯较大处理时间要少。高斯模糊的性质关键点检测226810关键点检测的相关概念ScaleInvariantFeatureTransformSIFT2012/3/2717•高斯金子塔的构建过程可分为两步:(1)对图像做高斯平滑;(2)对图像做降采样。为了让尺度体现其连续性,在简单下采样的基础上加上了高斯滤波。一幅图像可以产生几组(octave)图像,一组图像包括几层(interval)图像。4.高斯金字塔Octave1Octave2Octave3Octave4Octave5248……………关键点检测关键点检测的相关概念ScaleInvariantFeatureTransformSIFT2012/3/2718Octave1Octave2Octave3Octave4Octave5248……………•高斯图像金字塔共o组、s层,则有:关键点检测的相关概念0()2sSsσ——尺度空间坐标;s——sub-level层坐标;σ0——初始尺度;S——每组层数(一般为3~5)。ScaleInvariantFeatureTransformSIFT2012/3/2719•高斯金字塔的初始尺度当图像通过相机拍摄时,相机的镜头已经对图像进行了一次初始的模糊,所以根据高斯模糊的性质:Octave1Octave2Octave3Octave4Octave5248……………2logmin,3OMNM、N分别为图像的行数和列数0initinitprepre0initinitprepreinit——第0层尺度pre——被相机镜头模糊后的尺度•高斯金字塔的组数关键点检测的相关概念ScaleInvariantFeatureTransformSIFT2012/3/2720•高斯金字塔的组内尺度与组间尺度0()2sSsOctave1Octave2Octave3Octave4Octave5248……………组内尺度是指同一组(octave)内的尺度关系,组内相邻层尺度化简为:112Sss组间尺度是指不同组直接的尺度关系,相邻组的尺度可化为:1()2sSSoos222sSsSSoo由此可见,相邻两组的同一层尺度为2倍的关系关键点检测的相关概念ScaleInvariantFeatureTransformSIFT2012/3/2721Octave1Octave2Octave3Octave4Octave5248……………•最后可将组内和组间尺度归为:i——金字塔组数n——每一组的层数1212(,,,)inkkk12Sk关键点检测的相关概念ScaleInvariantFeatureTransformSIFT2012/3/2722关键点检测的相关概念•上一组图像的底层是由前一组图像的倒数第二层图像隔点采样生成的。这样可