sift算法详解及应用.ppt

BEIJING INSTITUTE OF TECHNOLOGY尺度不变特征变换匹配算法 Scale Invariant Feature Transform （SIFT）宋丹 109050562024/9/211.Scale￿Invariant￿Feature￿TransformSIFT1.SIFT简介2.SIFT算法实现细节提纲3.SIFT算法的应用领域4.SIFT算法的扩展与改进2024/9/212.Scale￿Invariant￿Feature￿TransformSIFTSIFT简介l 传统的特征提取方法的特征提取方法• 成像匹配的核心成像匹配的核心问题是将同一目是将同一目标在在不同不同时间、、不同分不同分辨率辨率、、不同光照不同光照、、不同位姿不同位姿情况下所成的像相情况下所成的像相对应传统的匹配算法往往是直接提取角点或的匹配算法往往是直接提取角点或边缘，，对环境的适境的适应能力能力较差，急需提出一种差，急需提出一种鲁棒性棒性强、能、能够适适应不同光不同光照、不同位姿等情况下能照、不同位姿等情况下能够有效有效识别目目标的方法2024/9/213.Scale￿Invariant￿Feature￿TransformSIFT•19991999年年British ColumbiaBritish Columbia大学大大学大卫. .劳伊（伊（David G.LoweDavid G.Lowe）教授）教授总结了了现有的有的基于不基于不变量技量技术的特征的特征检测方法，并正式提出了一种基于尺度空方法，并正式提出了一种基于尺度空间的、的、对图像像缩放、旋放、旋转甚至仿射甚至仿射变换保持不保持不变性的性的图像局部特征描述算子－像局部特征描述算子－SIFTSIFT（尺（尺度不度不变特征特征变换），），这种算法在种算法在20042004年被加以完善。

年被加以完善l SIFT提出的目的和意提出的目的和意义David G. LoweComputer Science Department2366 Main MallUniversity of British ColumbiaVancouver, B.C., V6T 1Z4, Canada E-mail: lowe@cs.ubc.caSIFT简介2024/9/214.Scale￿Invariant￿Feature￿TransformSIFTSIFT简介l 将一幅将一幅图像映射（像映射（变换））为一个一个局部特征向量集局部特征向量集；特征向量具有平移、；特征向量具有平移、缩放、旋放、旋转不不变性，同性，同时对光照光照变化、仿射及投影化、仿射及投影变换也有一定不也有一定不变性Original image courtesy of David Lowe2024/9/215.Scale￿Invariant￿Feature￿TransformSIFTSIFT简介l SIFT算法特点算法特点• SIFT SIFT特征是特征是图像的像的局部特征局部特征，其，其对旋旋转、尺度、尺度缩放、亮度放、亮度变化化保持不保持不变性，性，对视角角变化、仿射化、仿射变换、噪声也保持一定程度的、噪声也保持一定程度的稳定性。

定性 • 独特性独特性(Distinctiveness)(Distinctiveness)好，信息量丰富，适用于在海量特征好，信息量丰富，适用于在海量特征数据数据库中中进行快速、准确的匹配行快速、准确的匹配 • 多量性，即使少数的几个物体也可以多量性，即使少数的几个物体也可以产生大量生大量SIFTSIFT特征向量特征向量• 经过优化的化的SIFTSIFT算法可算法可满足一定的速度需求足一定的速度需求•  可可扩展性，可以很方便的与其他形式的特征向量展性，可以很方便的与其他形式的特征向量进行行联合  2024/9/216.Scale￿Invariant￿Feature￿TransformSIFT 目目标的自身状的自身状态、、场景所景所处的的环境和成像器材的成像特性等因素影响境和成像器材的成像特性等因素影响图像配准像配准/ /目目标识别跟踪的性能而跟踪的性能而SIFTSIFT算法在一定程度上可解决：算法在一定程度上可解决：• 目目标的旋的旋转、、缩放、平移（放、平移（RST））• 图像仿射像仿射/投影投影变换（（视点点viewpoint））• 光照影响（光照影响（illumination））• 目目标遮遮挡（（occlusion））• 杂物物场景（景（clutter））• 噪声噪声l SIFT SIFT算法可以解决的算法可以解决的问题SIFT简介Back2024/9/217.Scale￿Invariant￿Feature￿TransformSIFTSIFT算法实现细节 l SIFT SIFT算法算法实现步步骤简述述SIFTSIFT算法的算法的实质可以可以归为在不同尺度空在不同尺度空间上上查找特征点（关找特征点（关键点）的点）的问题。

 SIFTSIFT算法算法实现物体物体识别主要有三大工序，主要有三大工序，1 1、提取关、提取关键点；点；2 2、、对关关键点附加点附加详细的信息（局部特征）也就是所的信息（局部特征）也就是所谓的描述器；的描述器；3 3、通、通过两方特征点（附两方特征点（附带上上特征向量的关特征向量的关键点）的两两比点）的两两比较找出相互匹配的若干找出相互匹配的若干对特征点，也就建立了特征点，也就建立了景物景物间的的对应关系 2024/9/218.Scale￿Invariant￿Feature￿TransformSIFT1. 关关键点点检测2. 关关键点描述点描述 3. 关关键点匹配点匹配4. 消除消除错配点配点SIFT算法实现细节l SIFT SIFT算法算法实现步步骤2024/9/219.Scale￿Invariant￿Feature￿TransformSIFT所所谓关关键点，就是在不同点，就是在不同尺度空尺度空间的的图像下像下检测出的具有方向出的具有方向信息的局部极信息的局部极值点根据根据归纳，我，我们可以看出特征点具有的三个特征：可以看出特征点具有的三个特征：                                 尺度尺度                      方向方向                          大小大小关键点检测的相关概念1. 1. 哪些点是哪些点是SIFTSIFT中要中要查找的关找的关键点（特征点）？点（特征点）？ 这些点是一些些点是一些十分突出的点不会因光照条件的改十分突出的点不会因光照条件的改变而消失而消失，比如，比如角点角点、、边缘点点、、暗区域的亮点暗区域的亮点以及以及亮区域的暗点亮区域的暗点，既然两幅，既然两幅图像中有相同的景物，像中有相同的景物，那么使用某种方法分那么使用某种方法分别提取各自的提取各自的稳定点，定点，这些点之些点之间会有相互会有相互对应的匹配的匹配点。

点 2024/9/2110.Scale￿Invariant￿Feature￿TransformSIFT 我我们要精确表示的物体都是通要精确表示的物体都是通过一定的尺度来反映的一定的尺度来反映的现实世界的世界的物体也物体也总是通是通过不同尺度的不同尺度的观察而得到不同的察而得到不同的变化 尺度空尺度空间理理论最早在最早在19621962年提出，其主要思想是通年提出，其主要思想是通过对原始原始图像像进行尺度行尺度变换，，获得得图像多尺度下的尺度空像多尺度下的尺度空间表示序列，表示序列，对这些序列些序列进行行尺度空尺度空间主主轮廓的提取，并以廓的提取，并以该主主轮廓作廓作为一种特征向量，一种特征向量，实现边缘、、角点角点检测和不同分辨率上的特征提取等和不同分辨率上的特征提取等 尺度空尺度空间中各尺度中各尺度图像的模糊程度逐像的模糊程度逐渐变大，能大，能够模模拟人在距离目人在距离目标由近到由近到远时目目标在在视网膜上的形成网膜上的形成过程 尺度越大尺度越大图像越模糊像越模糊2. 2. 什么是尺度空什么是尺度空间（（scale spacescale space ）？）？关键点检测的关键点检测的相关概念2024/9/2111.Scale￿Invariant￿Feature￿TransformSIFT 根据文献根据文献《《Scale-space theory: A basic tool for analysing Scale-space theory: A basic tool for analysing structures at different scalesstructures at different scales》》我我们可知，高斯核是唯一可以可知，高斯核是唯一可以产生生多尺度空多尺度空间的核，一个的核，一个图像的尺度空像的尺度空间，，L L（（x,y,σ) ,x,y,σ) ,定定义为原始原始图像像I(x,y)I(x,y)与一个可与一个可变尺度的尺度的2 2维高斯函数高斯函数G(x,y,σ) G(x,y,σ) 卷卷积运算。

运算 关键点检测高斯函数高斯函数尺度是自然存在的，不是人尺度是自然存在的，不是人为创造的！高斯卷造的！高斯卷积只是表只是表现尺度空尺度空间的一种形式的一种形式…关键点检测的相关概念2024/9/2112.Scale￿Invariant￿Feature￿TransformSIFT3.3.  高斯模糊高斯模糊 高斯模糊是在高斯模糊是在Adobe PhotoshopAdobe Photoshop等等图像像处理理软件中广泛使用的件中广泛使用的处理理效果，通常用它来减小效果，通常用它来减小图像噪声以及降低像噪声以及降低细节层次这种模糊技种模糊技术生成生成的的图像的像的视觉效果是好像效果是好像经过一个半透明的屏幕一个半透明的屏幕观察察图像 关键点检测关键点检测的相关概念2024/9/2113.Scale￿Invariant￿Feature￿TransformSIFT关键点检测r r为模糊半径，模糊半径，     在减小在减小图像尺寸的像尺寸的场合合经常使用高斯模糊在常使用高斯模糊在进行欠采行欠采样的的时，，通常在采通常在采样之前之前对图像像进行低通行低通滤波波处理。

理这样就可以保就可以保证在采在采样图像中不会出像中不会出现虚假的高虚假的高频信息 关键点检测的相关概念2024/9/2114.Scale￿Invariant￿Feature￿TransformSIFT•在在实际应用中，在用中，在计算高斯函数的离散近似算高斯函数的离散近似时，在大概，在大概3σ3σ距离之外距离之外的像素都可以看作不起作用，的像素都可以看作不起作用，这些像素的些像素的计算也就可以忽略算也就可以忽略•通常，通常，图像像处理程序只需要理程序只需要计算算关键点检测高斯模板大小的高斯模板大小的选择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高斯模板高斯模板关键点检测的相关概念2024/9/2115.Scale￿Invariant￿Feature￿TransformSIFT•高斯模糊具有高斯模糊具有圆对称性。

称性•高斯模糊具有高斯模糊具有线性可分性可分的性的性质，也可以在，也可以在二二维图像上像上对两个独立的一两个独立的一维空空间分分别进行行计算算这样可以大大可以大大减少了运算的次数减少了运算的次数 •对一幅一幅图像像进行多次行多次连续高斯模糊的效果与一次更大的高斯模糊可以高斯模糊的效果与一次更大的高斯模糊可以产生同生同样的效果，大的高斯模糊的半径是所用多个高斯模糊半径平方的效果，大的高斯模糊的半径是所用多个高斯模糊半径平方和的平方根例如，使用半径分和的平方根例如，使用半径分别为 6 6 和和 8 8 的两次高斯模糊的两次高斯模糊变换得得到的效果等同于一次半径到的效果等同于一次半径为 10 10 的高斯模糊效果，的高斯模糊效果， 根据根据这个关系，使用多个个关系，使用多个连续较小的高斯模糊小的高斯模糊处理不会比理不会比单个高斯个高斯较大大处理理时间要少 高斯模糊的性高斯模糊的性质关键点检测关键点检测的相关概念2024/9/2116.Scale￿Invariant￿Feature￿TransformSIFT•高斯金子塔的构建高斯金子塔的构建过程可分程可分为两步：两步：（（1 1））对图像做高斯平滑；像做高斯平滑；（（2 2））对图像做降采像做降采样。

为了了让尺度体尺度体现其其连续性，在性，在简单下采下采样的基的基础上加上了高斯上加上了高斯滤波一幅一幅图像可以像可以产生几生几组（（octaveoctave））图像，一像，一组图像包括几像包括几层（（intervalinterval））图像 4. 4. 高斯金字塔高斯金字塔关键点检测关键点检测的相关概念2024/9/2117.Scale￿Invariant￿Feature￿TransformSIFT•高斯高斯图像金字塔共像金字塔共o o组、、s s层，，则有：有：关键点检测的相关概念σσ——尺度空尺度空间坐坐标；；s s——sub-levelsub-level层坐坐标；；σσ0 0——初始尺度；初始尺度；S S——每每组层数（一般数（一般为3~5）2024/9/2118.Scale￿Invariant￿Feature￿TransformSIFT•高斯金字塔的初始尺度高斯金字塔的初始尺度当当图像通像通过相机拍相机拍摄时，相机的，相机的镜头已已经对图像像进行了一次初始的模行了一次初始的模糊，所以根据高斯模糊的性糊，所以根据高斯模糊的性质：：M M、、N N分分别为图像的行数和列数像的行数和列数——第第0 0层尺度尺度——被相机被相机镜头模糊后的尺度模糊后的尺度•高斯金字塔的高斯金字塔的组数数关键点检测的相关概念2024/9/2119.Scale￿Invariant￿Feature￿TransformSIFT•高斯金字塔的高斯金字塔的组内尺度与内尺度与组间尺度尺度组内尺度是指同一内尺度是指同一组（（octave）内的）内的尺度关系，尺度关系，组内相内相邻层尺度化尺度化简为：：组间尺度是指不同尺度是指不同组直接的尺度关直接的尺度关系，相系，相邻组的尺度可化的尺度可化为：：          由此可由此可见，相，相邻两两组的同一的同一层尺度尺度为2倍的关系倍的关系关键点检测的相关概念2024/9/2120.Scale￿Invariant￿Feature￿TransformSIFT•最后可将最后可将组内和内和组间尺度尺度归为：：i i——金字塔金字塔组数数n n——每一每一组的的层数数关键点检测的相关概念2024/9/2121.Scale￿Invariant￿Feature￿TransformSIFT关键点检测的相关概念•上一上一组图像的底像的底层是由前是由前一一组图像的倒数第二像的倒数第二层图像隔点采像隔点采样生成的。

生成的     这样可以保持尺度的可以保持尺度的连续性为啥为啥？？2024/9/2122.Scale￿Invariant￿Feature￿TransformSIFT 关键点检测——DOG通通过研究研究LoweLowe教授的教授的论文文发现，所有特征点的，所有特征点的检测都是基于了尺度不都是基于了尺度不变的特性，特征点的的特性，特征点的检测占据了占据了论文的大部分的篇章，文的大部分的篇章，具有十分重要的具有十分重要的意意义！！LindebergLindeberg在文献在文献《《Scale-space theory: A basic tool for analysing Scale-space theory: A basic tool for analysing structures at different scalesstructures at different scales》》指出尺度指出尺度规范化的范化的LoGLoG算子具有真正算子具有真正的尺度不的尺度不变性LoGLoG算子即（算子即（Laplacion of GaussianLaplacion of Gaussian））, ,可以由高斯函数梯度算子可以由高斯函数梯度算子GOGGOG构建构建尺度尺度规范化的范化的GoGGoG算子算子尺度尺度规范化的范化的LoGLoG算子算子2024/9/2123.Scale￿Invariant￿Feature￿TransformSIFTLOGLOG算子与高斯核函数的关系算子与高斯核函数的关系通通过推推导可以看出，可以看出，LOGLOG算子与高斯核函数的差有直接关系，算子与高斯核函数的差有直接关系，由此引入一种新的算子由此引入一种新的算子DOGDOG（（Difference of GaussiansDifference of Gaussians），），即即高斯差分算子。

高斯差分算子关键点检测——DOG2024/9/2124.Scale￿Invariant￿Feature￿TransformSIFTDoGDoG（（Difference of GaussianDifference of Gaussian）函数）函数DoGDoG在在计算上只需相算上只需相邻尺度高斯平滑后尺度高斯平滑后图像相减，因此像相减，因此简化了化了计算！算！关键点检测——DOG应该应该是同一是同一组组内的相内的相邻层邻层吧？吧？2024/9/2125.Scale￿Invariant￿Feature￿TransformSIFTDoGDoG高斯差分金字塔高斯差分金字塔对应DOGDOG算子，我算子，我们要构建要构建DOGDOG金字塔金字塔我我们可以通可以通过高斯差分高斯差分图像像看出看出图像上的像素像上的像素值变化情况如果没有化情况如果没有变化，化，也就没有特征特征必也就没有特征特征必须是是变化尽可能多的点化尽可能多的点DOGDOG图像描像描绘的是目的是目标的的轮廓关键点检测——DOG2024/9/2126.Scale￿Invariant￿Feature￿TransformSIFT关键点检测——DOG2024/9/2127.Scale￿Invariant￿Feature￿TransformSIFT 在在检测极极值点前点前对原始原始图像的高斯平滑以致像的高斯平滑以致图像像丢失高失高频信息，所以信息，所以LoweLowe建建议在建立尺度空在建立尺度空间前首先前首先对原始原始图像像长宽扩展一倍，以保留原始展一倍，以保留原始图像信息，像信息，增加特征点数量。

增加特征点数量 在在LoweLowe的的论文中，将第文中，将第0 0层的初始尺度定的初始尺度定为1.61.6，，图片的初始尺度定片的初始尺度定为0.50.5，，则图像金字塔第像金字塔第0 0层的的实际尺度尺度为 当当对图像像长宽扩展一倍展一倍时，便构建了，便构建了-1-1层，，该层尺度尺度为关键点检测——DOGP.S.:P.S.:图像插像插值时，，选用的插用的插值函数可以是多种多函数可以是多种多样的2024/9/2128.Scale￿Invariant￿Feature￿TransformSIFT 中中间的的检测点和它同尺度的点和它同尺度的8个相个相邻点和上下相点和上下相邻尺度尺度对应的的9×2个点个点共共26个点比个点比较，以确保在尺度空，以确保在尺度空间和二和二维图像空像空间都都检测到极到极值点 l DoG的局部极的局部极值点点 关关键点是由点是由DOGDOG空空间的局部极的局部极值点点组成的为了了寻找找DoGDoG函数的极函数的极值点，点，每一个像素点要和它所有的相每一个像素点要和它所有的相邻点比点比较，看其是否比它的，看其是否比它的图像域和尺度域像域和尺度域的相的相邻点大或者小。

点大或者小DoG局部极值检测2024/9/2129.Scale￿Invariant￿Feature￿TransformSIFT 在极在极值比比较的的过程中，每程中，每一一组图像的首末两像的首末两层是无法是无法进行极行极值比比较的，的，为了了满足尺度足尺度变化的化的连续性，我性，我们在每一在每一组图像的像的顶层继续用高斯模糊生用高斯模糊生成了成了3幅幅图像，高斯金字塔有像，高斯金字塔有每每组S+3层图像DOG金字塔每金字塔每组有有S+2层图像像 右右图为不同尺度不同不同尺度不同层间极极值检测示意示意图P.S.: P.S.: 我我们只只牺牲了牲了-1-1组的第的第0 0层和第和第N N组的最高的最高层DoG局部极值检测2024/9/2130.Scale￿Invariant￿Feature￿TransformSIFTDoG局部极值检测l 关关键点精确定位点精确定位 为了提高关了提高关键点的点的稳定性，需要定性，需要对尺度空尺度空间DoGDoG函数函数进行曲行曲线拟合利用DoGDoG函数在尺度空函数在尺度空间的的TaylorTaylor展开式：展开式：其极其极值点点 由于由于DoGDoG值对噪声和噪声和边缘较敏感敏感, ,因此因此, ,在上面在上面DoGDoG尺度空尺度空间中中检测到局部到局部极极值点点还要要经过进一步的一步的检验才能精确定位才能精确定位为特征点。

特征点2024/9/2131.Scale￿Invariant￿Feature￿TransformSIFTDoG局部极值检测 上式去除那些上式去除那些对比度比度较低的不低的不稳定极定极值点Lowe的的试验显示，所有取示，所有取值小于小于0.04的极的极值点均可抛弃（点均可抛弃（像素灰度像素灰度值范范围[0，，1]） 在在计算算过程中，分程中，分别对图像的行、列及尺度三个量像的行、列及尺度三个量进行了修正，其修正行了修正，其修正结果如下：果如下：为修正修正值在在LoweLowe的程序中，的程序中，对坐坐标进行了五次修正行了五次修正将修正后的将修正后的结果代入式果代入式 求解得求解得2024/9/2132.Scale￿Invariant￿Feature￿TransformSIFTDoG局部极值检测l 去除去除边缘响响应 仅仅去除低去除低对比度的极比度的极值点点对于极于极值点的点的对于特征点于特征点稳定性是定性是远远不不够的DoGDoG函数在函数在图像像边缘有有较强的的边缘响响应，因此我，因此我们还需要排除需要排除边缘响响应 DoGDoG函数的（欠佳的）峰函数的（欠佳的）峰值点在横跨点在横跨边缘的方向有的方向有较大的主曲率，而大的主曲率，而在垂直在垂直边缘的方向有的方向有较小的主曲率。

主曲率可以通小的主曲率主曲率可以通过计算在算在该点位置尺度点位置尺度的的2×22×2的的HessianHessian矩矩阵得到，得到，导数由采数由采样点相点相邻差来估差来估计：：表示表示DOGDOG金字塔中某一尺度的金字塔中某一尺度的图像像x x方向求方向求导两次两次2024/9/2133.Scale￿Invariant￿Feature￿TransformSIFT 在两特征在两特征值相等相等时达最小，随达最小，随r的增的增长而增而增长Lowe论文中文中建建议r取取10DoG局部极值检测 D的主曲率和的主曲率和H的特征的特征值成正比，成正比，为了避免直接的了避免直接的计算算这些特征些特征值，而只是考，而只是考虑它它们的之的之间的比率令的比率令为 最大特征最大特征值 ，， 为最小的特征最小的特征值，，则时将关将关键点保留，反之剔除点保留，反之剔除2024/9/2134.Scale￿Invariant￿Feature￿TransformSIFT关键点方向分配 通通过尺度不尺度不变性求极性求极值点，可以使其具有点，可以使其具有缩放不放不变的性的性质，利用关，利用关键点点邻域像素的梯度方向分布特性，我域像素的梯度方向分布特性，我们可以可以为每个关每个关键点指定方向参数方点指定方向参数方向，向，从而使描述子从而使描述子对图像旋像旋转具有不具有不变性。

性l 像素点的梯度表示像素点的梯度表示梯度幅值：梯度方向：我我们通通过求每个极求每个极值点的梯度来点的梯度来为极极值点点赋予方向2024/9/2135.Scale￿Invariant￿Feature￿TransformSIFT关键点方向分配l 方向直方方向直方图的生成的生成 确定关确定关键点的方向采用梯度直方点的方向采用梯度直方图统计法，法，统计以关以关键点点为原点，原点，一定区域内的一定区域内的图像像素点像像素点对关关键点方向生成所作的点方向生成所作的贡献2024/9/2136.Scale￿Invariant￿Feature￿TransformSIFT 1. 1.直方直方图以每以每1010度方向度方向为一个柱，共一个柱，共3636个柱，柱所代表的方向个柱，柱所代表的方向为像像素点梯度方向，柱的素点梯度方向，柱的长短代表了梯度幅短代表了梯度幅值 2.2.根据根据LoweLowe的建的建议，直方，直方图统计半径采用半径采用3*1.5*3*1.5*σσ 3.3.在直方在直方图统计时，每相，每相邻三个像素点采用高斯加三个像素点采用高斯加权，根据，根据LoweLowe的的建建议，模板采用，模板采用[0.25,0.5,0.25][0.25,0.5,0.25]，并，并连续加加权两次。

两次关键点方向分配关于方向直方关于方向直方图的几点的几点说明明2024/9/2137.Scale￿Invariant￿Feature￿TransformSIFT关键点方向分配• 关关键点点主方向主方向：极：极值点周点周围区域梯度直方区域梯度直方图的的主主峰峰值也是特征点方向也是特征点方向• 关关键点点辅方向方向：：在梯度方向直方在梯度方向直方图中，当存在另一个相当于主峰中，当存在另一个相当于主峰值 80%能量的峰能量的峰值时，，则将将这个方向个方向认为是是该关关键点的点的辅方向 这可以增可以增强匹配的匹配的鲁棒性棒性，，LoweLowe的的论文指出大概有文指出大概有15%15%关关键点具有多点具有多方向，但方向，但这些点些点对匹配的匹配的稳定性至定性至为关关键 关关键点的主方向与点的主方向与辅方向方向2024/9/2138.Scale￿Invariant￿Feature￿TransformSIFT关键点方向分配1.确定确定计算关算关键点直方点直方图的高斯函数的高斯函数权重函数参数重函数参数 ；；2.生成含有生成含有36柱的方向直方柱的方向直方图，梯度直方，梯度直方图范范围0~360度，其中每度，其中每10度一度一个柱。

由半径个柱由半径为图像区域生成；像区域生成；3.对方向直方方向直方图进行两次平滑；行两次平滑；4.求取关求取关键点方向（可能是多个方向）；点方向（可能是多个方向）；5.对方向直方方向直方图的的Taylor展开式展开式进行二次曲行二次曲线拟合，精确关合，精确关键点方向；点方向；l 方向分配方向分配实现步步骤 图像的关像的关键点已点已检测完完毕，每个关，每个关键点有三个信息：位置、尺度、方点有三个信息：位置、尺度、方向；同向；同时也就使关也就使关键点具点具备平移、平移、缩放、和旋放、和旋转不不变性Back2024/9/2139.Scale￿Invariant￿Feature￿TransformSIFT关键点描述l 描述的目的描述的目的l 描述的思路描述的思路 通通过对关关键点周点周围图像区域分像区域分块，，计算算块内梯度直方内梯度直方图，生成具，生成具有独特性的向量，有独特性的向量，这个向量是个向量是该区域区域图像信息的一种抽象，具有唯一像信息的一种抽象，具有唯一性 描述的目的是在关描述的目的是在关键点点计算后，用一算后，用一组向量将向量将这个关个关键点描述出点描述出来，来，这个描述子不但包括关个描述子不但包括关键点，也包括关点，也包括关键点周点周围对其有其有贡献的像献的像素点。

用来作素点用来作为目目标匹配的依据，也可使关匹配的依据，也可使关键点具有更多的不点具有更多的不变特性，特性，如光照如光照变化、化、3D视点点变化等2024/9/2140.Scale￿Invariant￿Feature￿TransformSIFT关键点描述 下下图是一个是一个SIFT描述子事例其中描述子由描述子事例其中描述子由2×2×8维向量表征，也即是向量表征，也即是2×2个个8方向的方向方向的方向直方直方图组成左左图的种子点由的种子点由8×8单元元组成每一个小格都代表成每一个小格都代表了特征点了特征点邻域所在的尺度空域所在的尺度空间的一个像素，箭的一个像素，箭头方向代表了像素梯度方向，箭方向代表了像素梯度方向，箭头长度代表度代表该像素的幅像素的幅值然后在4×4的窗口内的窗口内计算算8个方向的梯度方向直方个方向的梯度方向直方图绘制每个梯度方向的累加可形成一个种子点，如右制每个梯度方向的累加可形成一个种子点，如右图所示：一个特征点由所示：一个特征点由4个个种子点的信息所种子点的信息所组成2024/9/2141.Scale￿Invariant￿Feature￿TransformSIFT关键点描述 LoweLowe实验结果果表明表明：：描述子描述子采用采用4×4×84×4×8＝＝128128维向量表征向量表征，，综合效果最合效果最优（不（不变性与独性与独特性）。

特性）2024/9/2142.Scale￿Invariant￿Feature￿TransformSIFT关键点描述 是关是关键点所在点所在组（（octave）的）的组内尺度，内尺度，1. 确定确定计算算描述子所需的描述子所需的图像区域像区域 描述子梯度方向直方描述子梯度方向直方图由关由关键点所在尺度的模糊点所在尺度的模糊图像像计算算产生图像区域的半径通像区域的半径通过下式下式计算算：：l 128维关关键点描述子生成步点描述子生成步骤2024/9/2143.Scale￿Invariant￿Feature￿TransformSIFT关键点描述2. 将坐将坐标移至关移至关键点主方向点主方向那么旋那么旋转角度后新坐角度后新坐标为：： 2024/9/2144.Scale￿Invariant￿Feature￿TransformSIFT：等于描述子窗口宽度 ×直方图列数（取4）的一半；关键点描述：该点与关键点的列距离；：该点与关键点的行距离；3.3.在在图像半径区域内像半径区域内对每个像素点求其梯度幅每个像素点求其梯度幅值和方向，然后和方向，然后对每个梯每个梯度幅度幅值乘以高斯乘以高斯权重参数，生成方向直方重参数，生成方向直方图。

2024/9/2145.Scale￿Invariant￿Feature￿TransformSIFT4.4.在窗口在窗口宽度度为2X22X2的区域内的区域内计算算8 8个方向的梯度方向直方个方向的梯度方向直方图，，绘制每个制每个梯度方向的累加梯度方向的累加值，即可形成一个种子点然后再在下一个，即可形成一个种子点然后再在下一个2X22X2的区域的区域内内进行直方行直方图统计，形成下一个种子点，共生成，形成下一个种子点，共生成1616个种子点个种子点5.5.描述子向量元素描述子向量元素门限化及限化及门限化后的描述子向量限化后的描述子向量规范化描述子向量元素描述子向量元素门限化：限化：方向直方方向直方图每个方向上梯度幅每个方向上梯度幅值限制在一定限制在一定门限限值以下（以下（门限一般取限一般取0.20.2）描述子向量元素描述子向量元素规范化：范化：为得到的得到的128128描述子向量描述子向量, ,为规范化后的向量范化后的向量 关键点描述2024/9/2146.Scale￿Invariant￿Feature￿TransformSIFT关键点描述 关关键点点描述子向量的描述子向量的规范化正是可去除范化正是可去除满足此模型的光照足此模型的光照影响影响。

对于于图像灰度像灰度值整体漂移整体漂移 ，，图像各点的梯度是像各点的梯度是邻域像素相减得到，域像素相减得到，所以也能去除所以也能去除BackBack2024/9/2147.Scale￿Invariant￿Feature￿TransformSIFT关键点匹配 分分别对模板模板图（参考（参考图，，reference imagereference image）和）和实时图（（观测图，，observation imageobservation image）建立关）建立关键点描述子集合目点描述子集合目标的的识别是通是通过两两点集内关点集内关键点描述子的比点描述子的比对来完成具有来完成具有128128维的关的关键点描述子的相点描述子的相似性度量采用欧式距离似性度量采用欧式距离2024/9/2148.Scale￿Invariant￿Feature￿TransformSIFT关键点匹配原原图像像目目标图像像穷举匹配匹配2024/9/2149.Scale￿Invariant￿Feature￿TransformSIFT• 模板模板图中关中关键点描述子：点描述子：• 实时图中关中关键点描述子：点描述子：• 任意两描述子相似性度量：任意两描述子相似性度量： 要得到配对的关键点描述子， 需满足：关键点匹配2024/9/2150.Scale￿Invariant￿Feature￿TransformSIFT•关关键点的匹配可以采用点的匹配可以采用穷举法来完成，但是法来完成，但是这样耗耗费的的时间太多，一太多，一般都采用一种叫般都采用一种叫kdkd树的数据的数据结构来完成搜索。

搜索的内容是以目构来完成搜索搜索的内容是以目标图像的关像的关键点点为基准，搜索与目基准，搜索与目标图像的特征点最像的特征点最邻近的原近的原图像特征点像特征点和次和次邻近的原近的原图像特征点像特征点关键点匹配KdKd树是一个平衡二叉是一个平衡二叉树2024/9/2151.Scale￿Invariant￿Feature￿TransformSIFT关键点匹配Back2024/9/2152.Scale￿Invariant￿Feature￿TransformSIFT•关关键点匹配并不能点匹配并不能标志着算法的志着算法的结束，因束，因为在匹配的在匹配的过程中存在着大程中存在着大量的量的错配点消除错配点图中交叉的中交叉的绿线为错配点配点2024/9/2153.Scale￿Invariant￿Feature￿TransformSIFT消除错配点 RANSACRANSAC（（Random Sample ConsensusRandom Sample Consensus，，随机抽随机抽样一致一致 ）） 是一种是一种鲁棒性的参数估棒性的参数估计方法 RANSAC RANSAC简介介RANSACRANSAC实质上就是一个反复上就是一个反复测试、不断迭代的、不断迭代的过程。

程 RANSAC RANSAC的的基本思想基本思想：： 首先根据具体首先根据具体问题设计出某个目出某个目标函数，然后通函数，然后通过反复提取最小反复提取最小点集估点集估计该函数中参数的初始函数中参数的初始值，利用，利用这些初始些初始值把所有的数据分把所有的数据分为“内点内点”（（ inlier inlier ）和）和“外点外点“（（outlieroutlier），最后用所有的内点），最后用所有的内点重新重新计算和估算和估计函数的参数函数的参数2024/9/2154.Scale￿Invariant￿Feature￿TransformSIFT消除错配点• RANSAC RANSAC事例事例如何估计最佳直线？重复进行，拟合最优直线随机取两样本点拟合直线拟合直线：BackBack2024/9/2155.Scale￿Invariant￿Feature￿TransformSIFTSIFT算法的应用 SIFTSIFT算法目前在算法目前在军事、工事、工业和民用方面都得到了不同程度的和民用方面都得到了不同程度的应用，用，其其应用已用已经渗透了很多渗透了很多领域，典型的域，典型的应用如下：用如下：• 物体物体识别• 机器人定位与机器人定位与导航航• 图像拼接像拼接• 三三维建模建模• 手手势识别• 视频跟踪跟踪• 笔笔记鉴定定• 指指纹与人与人脸识别• 犯罪犯罪现场特征提取特征提取• … …2024/9/2156.Scale￿Invariant￿Feature￿TransformSIFTSIFT算法的应用• 物体物体识别2024/9/2157.Scale￿Invariant￿Feature￿TransformSIFTSIFT算法的应用• 图像拼接像拼接Demo2024/9/2158.Scale￿Invariant￿Feature￿TransformSIFT• 三三维建模建模SIFT算法的应用2024/9/2159.Scale￿Invariant￿Feature￿TransformSIFTSIFT算法的应用• 手手势识别目前，手目前，手势识别已已应用于等用于等设备上。

上2024/9/2160.Scale￿Invariant￿Feature￿TransformSIFT• 笔笔记鉴定定SIFT算法的应用2024/9/2161.Scale￿Invariant￿Feature￿TransformSIFT• 来自网友的来自网友的创意意——周正周正龙的老虎的老虎SIFT算法的应用图1 1周正周正龙的的华南南虎照片与年画上的虎照片与年画上的华南虎照片南虎照片1212点匹点匹配配图2 2周正周正龙的的华南南虎照片与真虎照片与真实的的华南虎照片南虎照片0 0点匹配点匹配BackBack2024/9/2162.Scale￿Invariant￿Feature￿TransformSIFTSIFT算法的扩展与改进 SIFTSIFT在在图像的不像的不变特征提取方面特征提取方面拥有无与有无与伦比的比的优势，但其并不是，但其并不是完美的，仍然存在着完美的，仍然存在着实时性不高、有性不高、有时特征点特征点较少、少、对边缘模糊的目模糊的目标无法准确提取特征点等缺陷自从无法准确提取特征点等缺陷自从19991999年，年，SIFTSIFT算法算法问世以来，人世以来，人们从未停止从未停止对它的它的优化和改化和改进。

2024/9/2163.Scale￿Invariant￿Feature￿TransformSIFTSIFT算法的扩展与改进• PCA-SIFT PCA-SIFTPCAPCA（（Principal Component AnalysisPrincipal Component Analysis），即主成分分析，是一种数据降），即主成分分析，是一种数据降维技技术由Y.ke 2004Y.ke 2004年提出通通过降降维技技术，可有效化，可有效化简SIFTSIFT算子的算子的128128维描述子2024/9/2164.Scale￿Invariant￿Feature￿TransformSIFTCSIFTCSIFT（（Colored scale invariant feature transform Colored scale invariant feature transform ）彩色尺度特）彩色尺度特征不征不变变换，可以，可以针对彩色彩色图像像进行行图像的不像的不变特征提取由特征提取由 Farag Farag 20062006年提出SIFT算法的扩展与改进• CSIFT CSIFT2024/9/2165.Scale￿Invariant￿Feature￿TransformSIFTSIFT算法的扩展与改进• SURF SURFSURFSURF（（SURF Speeded Up Robust FeaturesSURF Speeded Up Robust Features），号称是），号称是SIFTSIFT算法的增算法的增强版，版，SURFSURF算法的算法的计算量小，运算速度快，提取算量小，运算速度快，提取的特征点几乎与的特征点几乎与SIFTSIFT相同，由相同，由Bay 2006Bay 2006年提出。

年提出      SIFTSURF特征点检测用不同尺度的图片与高斯函数做卷积用不同大小的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|2024/9/2166.Scale￿Invariant￿Feature￿TransformSIFTSIFT算法的扩展与改进methodTimeScaleRotationBlurIlluminationAffineSiftcommonbestbestcommoncommongoodPCA-siftgoodgoodgoodbestgoodbestSurf bestcommoncommongoodbestgood•SIFTSIFT、、PCA-SIFT PCA-SIFT 与与 SURF SURF 的的对比比2024/9/2167.Scale￿Invariant￿Feature￿TransformSIFTASIFTASIFT（（Affine-SIFTAffine-SIFT）抗仿射）抗仿射SIFTSIFT变换。

两个向量空两个向量空间之之间的一个仿射的一个仿射变换或者仿射映射由一个或者仿射映射由一个线性性变换接上一接上一个平移个平移组成ASIFTASIFT可以抵抗可以抵抗强仿射情况，提取的特征点仿射情况，提取的特征点远多于多于SIFTSIFT算算法，由法，由J.M. Morel 2009J.M. Morel 2009年提出• ASIFT ASIFTSIFT算法的扩展与改进Demo2024/9/2168.Scale￿Invariant￿Feature￿TransformSIFT谢 谢！！2024/9/2169.。