sift算法讲解课件.ppt

1、任甲元 郑舒颖 金喆 关键技术：局部特征提取局部特征：感兴趣区域检测&描述子感兴趣区域感兴趣区域描述子描述子 David LoweComputer Science Department2366 Main MallUniversity of British ColumbiaVancouver,B.C.,V6T 1Z4,Canada E-mail:lowecs.ubc.ca作者简介 SIFT算法由D.G.Lowe1999年提出，2004年完善总结。此后Y.Ke将其描述子部分用PCA代替直方图的方式，对其进行改进。定义：SIFT算法是一种提取局部特征的算法，在尺度空间寻找极 值点，提取位置、尺度、旋

2、转不变量。特点：1、SIFT特征是图像的局部特征，其对旋转、尺度缩放、亮度变化保持 不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定性。2、独特性（Distinctiveness）好，信息量丰富，适用于在海量特征数 据库中进行快速、准确的匹配。3、多量性，即使少数的几个物体也可以产生大量的SIFT特征向量。4、高速性，经优化的SIFT匹配算法甚至可以达到实时的要求。5、可扩展性，可以很方便的与其他形式的特征向量进行联合。1 1、检测尺度空间极值点。、检测尺度空间极值点。2 2、精确定位极值点。、精确定位极值点。关键点检测3 3、为每个关键点指定方向。、为每个关键点指定方向。4 4、关键点

3、描述子的生成。、关键点描述子的生成。描述子生成2 2、精确定位极值点。、精确定位极值点。关键点检测3 3、为每个关键点指定方向。、为每个关键点指定方向。4 4、关键点描述子的生成。、关键点描述子的生成。描述子生成,*,L x yG x yI x y尺度空间：二维尺度可变高斯核函数（滤波函数），高斯核和高斯微分是尺度空间分析的惟一平滑核。(本实验采用一维高斯函数),G x y222()/221,2xyG x ye(,)x y空间坐标尺度空间因子（坐标）,I x y二维图像函数高斯差分尺度空间（DOG scale-space）：(,)(,)(,)(,)(,)(,)D x yG x y kG x y

4、I x yL x y kL x y是尺度归一化LOG算子的近似高斯金字塔的构建：高斯金字塔共o(7)阶，每阶有s(6)层，下一阶的图像由上一阶图像降采样得到。归一化归一化gray0=1 3 5 7 9 10 11归一化gray0=1 3 5 7 9 10 11gray1=0 2 4 6 8 9 10 归一化gray0=1 3 5 7 9 10 11gray1=0 2 4 6 8 9 10gray2=0 2/10 4/10 6/10 8/10 9/10 1归一化gray0=1 3 5 7 9 10 11gray1=0 2 4 6 8 9 10gray2=0 2/10 4/10 6/10 8/10

5、 9/10 1 0=gray2=1放大一倍放大一倍放大一倍放大一倍 1 3 5 7 9 11 13 15 17放大一倍放大一倍 1 3 5 7 9 11 13 15 17放大一倍放大一倍 1 3 5 7 9 11 13 15 17 1 3 5 7 9 11 13 15 17放大一倍放大一倍 1 3 5 7 9 11 13 15 17 1 2 3 4 5 7 8 9 10 11 13 14 15 16 17放大一倍放大一倍 1 3 5 7 9 11 13 15 17 1 2 3 4 5 4 6 8 7 8 9 10 11 10 12 14 13 14 15 16 17放大一倍放大一倍 1 3 5

6、 7 9 11 13 15 17 1 2 3 4 5 4 5 6 7 8 7 8 9 10 11 10 11 12 13 14 13 14 15 16 17放大一倍放大一倍 1 3 5 7 9 11 13 15 17 1 2 3 4 5 5 4 5 6 7 8 8 7 8 9 10 1111 10 11 12 13 1414 13 14 15 16 1717 13 14 15 16 1717 高斯滤波高斯滤波 高斯滤波高斯滤波 高斯滤波高斯滤波 高斯滤波高斯滤波 高斯滤波高斯滤波 高斯滤波高斯滤波 高斯滤波高斯滤波 高斯滤波高斯滤波 高斯滤波高斯滤波 高斯滤波高斯滤波 高斯滤波高斯滤波 高斯滤

7、波高斯滤波 高斯滤波高斯滤波 高斯滤波高斯滤波 高斯滤波高斯滤波 高斯滤波高斯滤波 高斯滤波高斯滤波 高斯滤波高斯滤波 1 2 3 4 5 5 4 5 6 7 8 8 7 8 9 10 1111 10 11 12 13 1414 13 14 15 16 1717 13 14 15 16 17171 2 3 4 5 5 4 5 6 7 8 8 7 8 9 10 1111 10 11 12 13 1414 13 14 15 16 1717 13 14 15 16 1717 1 2 3 4 5 5 4 5 6 7 8 8 7 8 9 10 1111 10 11 12 13 1414 13 14 15

8、 16 1717 13 14 15 16 1717 1 1 23 4 5 5 4 5 6 7 8 8 7 8 9 10 1111 10 11 12 13 1414 13 14 15 16 1717 13 14 15 16 1717 1 1 2 3 4 5 5 4 5 6 7 8 8 7 8 9 10 1111 10 11 12 13 1414 13 14 15 16 1717 13 14 15 16 1717 1 3 1 2 3 45 5 4 5 6 7 8 8 7 8 9 10 1111 10 11 12 13 1414 13 14 15 16 1717 13 14 15 16 1717 1

9、 3 1 2 3 4 5 5 4 5 6 7 8 8 7 8 9 10 1111 10 11 12 13 1414 13 14 15 16 1717 13 14 15 16 1717 1 3 5 1 2 3 4 5 5 4 5 6 7 8 87 8 9 10 1111 10 11 12 13 1414 13 14 15 16 1717 13 14 15 16 1717 1 3 5 1 2 3 4 5 5 4 5 6 7 8 8 7 8 9 10 1111 10 11 12 13 1414 13 14 15 16 1717 13 14 15 16 1717 1 3 5 7 1 2 3 4 5 5

10、 4 5 6 7 8 8 7 89 10 1111 10 11 12 13 1414 13 14 15 16 1717 13 14 15 16 1717 1 3 5 7 1 2 3 4 5 5 4 5 6 7 8 8 7 8 9 10 1111 10 11 12 13 1414 13 14 15 16 1717 13 14 15 16 1717 1 3 5 7 9 1 2 3 4 5 5 4 5 6 7 8 8 7 8 9 101111 10 11 12 13 1414 13 14 15 16 1717 13 14 15 16 1717 1 3 5 7 9 1 2 3 4 5 5 4 5 6

11、7 8 8 7 8 9 10 1111 10 11 12 13 1414 13 14 15 16 1717 13 14 15 16 1717 1 3 5 7 9 11 1 2 3 4 5 5 4 5 6 7 8 8 7 8 9 10 1111 10 11 12 13 141413 14 15 16 1717 13 14 15 16 1717 1 3 5 7 9 11 1 2 3 4 5 5 4 5 6 7 8 8 7 8 9 10 1111 10 11 12 13 1414 13 14 15 16 1717 13 14 15 16 1717 1 3 5 7 9 11 13 1 2 3 4 5

12、5 4 5 6 7 8 8 7 8 9 10 1111 10 11 12 13 1414 13 1415 16 1717 13 14 15 16 1717 1 3 5 7 9 11 13 1 2 3 4 5 5 4 5 6 7 8 8 7 8 9 10 1111 10 11 12 13 1414 13 14 15 16 1717 13 14 15 16 1717 1 3 5 7 9 11 13 15 1 2 3 4 5 5 4 5 6 7 8 8 7 8 9 10 1111 10 11 12 13 1414 13 14 15 161717 13 14 15 16 1717 1 3 5 7 9

13、11 13 15 1 2 3 4 5 5 4 5 6 7 8 8 7 8 9 10 1111 10 11 12 13 1414 13 14 15 16 1717 13 14 15 16 1717 1 3 5 7 9 11 13 15 17在3x3x3 邻域内选择所有的极值中间的检测点和尺度空间共26个点比较关键点检测3 3、为每个关键点指定方向。、为每个关键点指定方向。4 4、关键点描述子的生成。、关键点描述子的生成。描述子生成1 1、检测尺度空间极值点。、检测尺度空间极值点。x采样检测到的极值实际极值两步检验：1、必须与周围的像素有明显的差异，即滤除低对比度的点。2、不能是边缘点。因为 DO

14、G算子会产生较强的边缘响应目的：增强匹配稳定性、提高抗噪声能力方法：拟合三维二次方程，找出低对比度的点泰勒序列展开式：其中：D是DOG计算的结果，x是候选关键点之一最小化的到真正的极值（偏移量）：当：则该点是低对比度的点 xxDxxxDDxDTTT2221xDxDx122 0.03D x 一个定义好的高斯差分算子的极值在横跨边缘的地方有较大的主曲率，而在垂直边缘的方向有较小的主曲率。主曲率（Hessian矩阵）：xxxyxyyyDDH=DD2DetxxyyxxyyxyTr(H)=DD(H)D D(D)D的主曲率和H的特征值成正比，令 为最大特征值，为最小的特征值arrHDetHTr22)1()

15、()(为了检测主曲率是否在某阈值r下，只需检测：22222Tr(H)()()(1)Det(H)2(1)/令 ，则 的值在两个特征值相等的时候最小，随着 的增大而增大文章中：若不满足上式，则是边缘的点1 0没进行任何处理的关键点去除了低对比度之后的点去除边界相应的点关键点检测4 4、关键点描述子的生成、关键点描述子的生成描述子生成1 1、检测尺度空间极值点。、检测尺度空间极值点。2 2、精确定位极值点、精确定位极值点选择一系列好的关键点选择每个关键点周围的一个区域去除尺度和旋转的影响采用梯度直方图来确定关键点的方向用点的尺度选择正确的图像用有限差分计算梯度的模值和方向yxIyxGyxL,*,yx

16、LyxLyxLyxLyxyxLyxLyxLyxLyxm,1,1)1,(1,tan,)1,(1,1,1,122 实际计算中，在以关键点为中心的邻域窗口内采样，并用直方图统计邻域像素的梯度方向。梯度直方图的范围是0360度，其中每10度一个柱，总共36个柱。直方图的峰值代表关键点处邻域梯度的主方向，即作为该关键点的方向。在梯度方向直方图中，当存在另一个相当于主峰值80%能量的峰值时，则将这个方向认为是该关键点的辅方向。一个关键点可能会被指定具有多个方向（一个主方向、一个以上辅方向），可以增强匹配的鲁棒性。每个关键点有三个信息：位置，所处尺度，方向。由此可以确定一个SIFT特征区域。关键点检测3 3

17、、为每个关键点指定方向、为每个关键点指定方向描述子生成1 1、检测尺度空间极值点、检测尺度空间极值点2 2、精确定位极值点、精确定位极值点1、首先将坐标轴旋转为关键点的方向，以确保旋转不 变性。2、以关键点为中心取88的窗口。3、在每44的小块上计算8个方向的梯度方向直方图，绘 制每个梯度方向的累加值，即可形成一个种子点。邻域方向性信息联合的思想增强了算法抗噪声的能力，同时对于含有定位误差的特征匹配也提供了较好的容错性。实际计算过程中，为了增强匹配的稳健性，建议对每个关键字使用44共16个种子点来描述，这样对于一个关键点就可以产生128个数据，最终形成128维SIFT特征向量。-此时SIFT特征向量已经去除了尺度变化、旋转等几何变化因素的影响，再继续将特征向量的长度归一化，则可以进一步去除光照变化的影响。当两幅图像的SIFT特征向量生成后，下一步采用关键点特征向量的欧式距离来作为两幅图像中关键点的相似性判定度量。-取图像1中的某个关键点，并找出其与图像2中欧氏距离最近的前两个关键点，在这两个关键点中，如果最近的距离除以次近的距离少于某个比例阈值，则接受这一对匹配点。降低这个阈值，SIFT匹配点数目会减少，但更加稳定。