尺度不变特征变换匹配算法.ppt

1、尺度不变特征变换匹配算法提纲提纲nSIFT算法简述算法简述nSIFT算法具体实施细节算法具体实施细节n目前进展及所遇到的问题目前进展及所遇到的问题SIFT算法简述算法简述n成像匹配的核心问题是将同一目标在不同时间、不同分辨率、不同光照、不同位姿情况下所成的像相对应。David G.Lowe在2004年总结了现有的基于不变量技术的特征检测方法，并正式提出了一种基于尺度空间的、对图像缩放、旋转甚至仿射变换保持不变性的图像局部特征描述算子SIFT（尺度不变特征变换），并将其应用与图像拼接与场景三维重建。nSIFT：Scale Invariant Feature Transform 尺度不变特征变换。

2、这种方法就是将一幅图像映射（变换）为一个局部特征向量集，而其中的特征向量具有平移、缩放、旋转不变性，同时对光照变化、仿射及3D投影也有一定不变性。目标的投影变换（视点变化）光照变化nSIFT算法属于特征级的点特征算法类，SIFT用于目标检测处理过程如下：SIFT算法的主要计算步骤 nSIFT算法首先在尺度空间进行特征检测，并确定关键点的位置和关键点处的尺度，然后使用关键点邻域梯度的主方向作为该点的方向特征，以实现算子对尺度和方向的无关性。主要计算步骤如下：n(1)尺度空间极值检测：搜索整个图像尺度空间。通过使用高斯差分函数来确定对尺度和方向具有不变性的关键点。以初步确定关键点位置和所在尺度。n

3、(2)关键点定位：在每一个候选位置，详细地模型拟合以确定位置和尺度。根据稳定性选择关键点。通过拟合三维二次函数以精确确定关键点的位置和尺度，同时消除低对比度的关键点和不稳定的边缘响应点(因为高斯差分算子会产生较强的边缘响应)，以增强匹配稳定性、提高抗噪声能力。n(3)方向分配：每一个关键点根据局部图像梯度方向分配一个或多个方向。其后所有操作都根据分配的方向、尺度、位置来进行。利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数，使算子具备旋转不变性。n(4)关键点描述：在每个关键点周围在选定的尺度下测量局部图像梯度。为了增强匹配的稳健性，对每个关键点使用44共16个种子点来描述，每个种

4、子点具有8个方向向量信息,这样对于一个关键点就可以产生128个数据，最终形成128维的SIFT特征向量。SIFT算法具体实施细节算法具体实施细节n基于尺度不变特征的目标匹配算法既然属于点特征目标识别方法，它也就满足特征识别的一般流程：特征点检测特征点描述特征点匹配目标识别跟踪。n1.特征点检测n2.特征点描述n3.特征点匹配n4.目标识别跟踪n5.实现过程目标的特征点检测特征点检测n主要包括以下几部分内容:1.图像尺度空间的构建.(1)图像高斯尺度空间的构建.(2)DoG(高斯差分)空间的构建.2.尺度空间极值点检测.(1)关键点精确定位 (2)排除边缘响应 3.特征点方向分配.特征点检测特征

5、点检测 n在计算机视觉领域，尺度空间理论用于模 拟图像数据的多尺度特征。Koendetink利 用扩散方程来描述尺度空间滤波过程，并由此证明高斯核是实现尺度变换的唯一变 换核。Lindeberg、Babaud等人通过不同的 推导进一步证明高斯核是唯一的线性核。因此，尺度空间理论的主要思想是利用高 斯核对原始图像进行尺度变换，获得图像 多尺度下的尺度空间表示序列，对这些序 列进行尺度空间特征提取。图像高斯尺度空间构建 n主要思想是利用高斯核对原始图像进行尺度变换，获得图像多尺度下的尺度空间表示序列。n二维高斯函数定义如下：22221,exp22xyG x yn一幅二维图像,在不同尺度下的尺度空间

6、的表示可由图像与高斯核卷积得到：n式中，L代表尺度空间，(x,y)代表图像的像素 位置,称为尺度空间因子，其值越小则表征 该图像被平滑得越少,相应的尺度也就越小,大 尺度对应于图像的概貌,小尺度对应于图像的 细节。对同一幅图像用不同的尺度表达后,相 当于给图像数据增加了一维新坐标,即除了一 般使用的空间分辨率外,现在又多了一个刻画 当前分辨率层次的新参数。,L x yG x yI x yDOG（Difference of Gaussian）空间。n在图像的高斯尺度空间，尺度规范化的拉普拉斯函数 具有尺度不变性，可以采用函数的极值点来表示该函数。n在SIFT算法中，引入DoG（Differenc

7、e of Gaussian）函数对其进行近似，特征点就是指DoG函数在图像的尺度空间的局部极值点。22GnLoG（Laplacian of Gaussian）函数：nDoG（Difference of Gaussian）函数：22222GGGxy,D x yG x y kG x yI x yL x y kL x ynDoG与LoG的关系：n由上式子可以看出，k的不同取值代表DoG函数的不同近似。k值越接近1，DoG函数越是逼近于 。n二者具有相同的极值，稳定、可以近似。2,G x y kG x yGGk22,1G x y kG x ykG2 2Gn在数学推导上，图像在尺度空间的表示 的自变量x

8、,y,是连续取值的，而数字图像(x,y)是离散取值的。现在讨论如何对离散化，以便于检测近似表征所需DoG函数极值点。为了保证DoG对 一定程度的近似，取下述方法对进行离散：，相邻尺度成等比增长。,L x y2,kk22G下面给出一幅图像产生高斯尺度空间和DoG的详细过程。n假设图像高斯尺度空间共有n个离散尺度，将这n个模糊图像分作o组，每组s层，即n=so，相邻组的对应层尺度成2倍关系。Lowe给出参考值s=3。而初始值，即离散尺度空间的最小尺度（图像金字塔最底层），Lowe通过大量样本试验给出参考值为1.6，组个数o的确定由下式：21,nkkk2logmin,3oM Nn其中M,N为扩展后的

9、原始图像的列和行。图像的高斯金字塔如下图所示：为何要扩展?n在检测极值点前对原始图像的高斯平滑以致图像丢失高频信息，所以David G.Lowe建议在建立尺度空间前首先对原始图像长宽扩展一倍，以保留原始图像信息，增加特征点数量。n在构建完高斯尺度空间后，DoG空间可由高斯尺度空间相邻的图像做差得到。尺度空间极值点检测 n为了寻找DoG函数的极值点，每一个像素点要和它所有的相邻点比较，看其是否比它的图像域和尺度域的相邻点大或者小。如下图中间的被检测点和它同尺度的8个相邻点和上下相邻尺度对应的92个点共26个点比较，以确保在尺度空间和二维图像空间都检测到极值点。极值点的精确定位 n由于DoG值对噪

10、声和边缘较敏感,因此,在上面DoG尺度空间中检测到局部极值点还要经过进一步的检验才能精确定位为特征点。首先需要对尺度空间DoG函数进行3D二次曲线拟合，通过这种方法可以从上一步检测到的局部极值点计算出亚像素极值的位置。n利用DoG函数在尺度空间Taylor展开式：其中，为上一步中检测到的极值点坐标。2212TTDDD XDXXXXX,TXx yn根据泰勒展开式，可以得到一个偏移 ,这个偏移可以看作局部极值的亚像素的位置，然后将 代入泰勒展开式中,如果计算出来的结果 绝对值小于0.03,就认为这个点的对比度较低。12TDD XDXXDX去处边缘响应n仅仅去除低对比度的极值点对于极值点的稳定性是远

11、远不够的。nDoG函数在图像边缘有较强的边缘响应，因此还需要排除边缘响应。n可以通过计算该点所在位置尺度周围3x3窗口内的Hessian矩阵排除边缘响应,其计算如下：xxxyxyyyDDHDDn令为最大特征值，为最小的特征值，则=r x.2221Tr HrDet Hrn 在两特征值相等时达最小，随r的增长而增长。David G.Lowe建议r取10，非边缘点必须满足：21rr221Tr HrDet Hr特征点方向分配 n利用特征点邻域像素的梯度方向分布特性，为每个特征点指定方向，特征点描述子相对于此方向表征，从而使特征点描述子对图像旋转具有不变性。n实际计算时，我们在特征点最邻近尺度 中，以特

12、征点为中心的邻域窗口内，对每个像素点的梯度幅值乘以以特征点为中心的Gaussian权重函数，并用直方图统计其邻域像素的梯度方向。其中梯度的幅度与方向计算方法如下：,L x yn梯度:n幅值:n方向:,IIgradI x yxy22,1,1,1,1mxyLxy LxyLxyLxy 1,1,1,tan1,1,L x yL x yx yL xyL xyn梯度直方图的范围是0360度，其中每10度一个柱，总共36个柱。直方图的峰值则代表了该特征点处邻域梯度的主方向，即将此方向作为该特征点的方向。下图是采用7个柱时使用梯度直方图为特征点确定主方向的示例：主方向为2/72。n在梯度方向直方图中，当存在另一

13、个相当于主峰值80%能量的峰值时，则将这个方向认为是该特征点的辅方向。一个特征点可能会被指定具有多个方向（一个主方向，一个以上辅方向），这可以增强匹配的鲁棒性。图像中一般有近15%特征点具有多方向，但这些多方向的特征点对匹配的稳定性至为关键。为了使分配的方向更为精准，可以用直方图中相邻的3个柱进行抛物线拟合求极值。n至此，图像的特征点已检测完毕，每个特征点有三个信息：位置、尺度、方向。特征点描述特征点描述 n以上已经为特征点指定了位置、尺度和方向信息。同时也就使特征点具备平移、缩放、和旋转不变性。n特征点描述的目的:特征点描述也即是通过对特征点周围图像区域计算，生成具有独特性的向量，这个向量是

14、该区域图像信息的一种抽象，具有更多的不变特性，如光照变化、3D视点变化等。n下图是一个尺度不变特征描述子例子。其中描述子由228维向量表征，也即是22个8方向的方向直方图组成。Lowe实验结果表明描述子采用448128维向量表征综合效果最优（不变性与独特性）。n左图中，以特征点为中心提取88的窗口，每一个小格都代表了特征点邻域所在的尺度空间的一个像素，箭头方向代表该像素的梯度方向，箭头长度代表该像素的幅值。然后在44的窗口内计算8个方向的梯度方向直方图，绘制每个梯度方向的累加值，即可形成一个种子点。如右图，每个特征点共由22个种子点组成，每个种子点包含8个方向向量信息。n通过这种邻域方向信息联

15、合的思想，SIFT算法获得了良好的抗噪声能力。128维描述子具体生成步骤n(1)确定生成描述子所需的图像区域:图像区域的半径通过下式计算,是关键点所在组（octave）的组内尺度，d=4为小窗口边长,32112octdradiusoctn(2)生成方向直方图。n(3)生成128维描述子向量。n(4)描述子向量元素门限化及门限化后的描述子向量规范化。n假设为 得到的128描述子向量，为规范化后的向量，则，1281iijjlww对比度的改善 n引入一种简单成像模型 相应地 为照度函数和 为反射函数。不同时刻拍摄的同一场景图像照度函数的和反射函数不尽相同，其值均与 成正比关系。所以图像各点的梯度与照

16、度函数和反射函数也成正比关系。n描述子向量的规范化可以去除这种影响。对于图像灰度值整体漂移,图像各点的梯度是邻域像素相减得到，所以也能去除。,f x yi x y r x y,i x y,r x y,fx y描述子向量元素门限化 n方向直方图每个方向上梯度幅值限制在一定门限值以下（门限一般取0.2）。这对于非线性的光照度变化，如CCD饱和或是光源位置变化（光源照射场景角度改变，使得3D物体表面不同位置方向亮度改变不等）。这就在特征点配对（欧式距离相似性度量）时，减弱了较大的梯度值的影响，而重在每个方向直方图的分布。特征点匹配特征点匹配 n通过相似性度量得到图像间的潜在匹配。n采用欧氏距离作为两

17、幅图像间的相似性度量。n获取SIFT特征向量后，采用优先k-d树进行优先搜索来查找每个特征点的近似最近邻特征点。n在这两个特征点中，如果最近的距离除以次近的距离少于某个比例阈值,则接受这一对匹配点。降低这个比例阈值，SIFT匹配点数目会减少，但更加稳定。n分别对模板图和实时图建立关键点描述子集合。目标的识别是通过两点集内关键点描述子的比对来完成。具有128维的关键点描述子的相似性度量采用欧式距离。n模板图中关键点描述子，实时图中关键点描述子，任意两个描述子相似性定义为：12128,iiiiRrrr12128,iiiiSsss12821,iiijijjdRSrsn要得到配对的特征点描述子，需满足

18、：Lowe通过实验给出阈值为0.8。ijipRSThresholdRS实时图中距离 最近的点 实时图中距离 的次最近点 n消除错配。通过相似性度量得到潜在匹配对，其中不可避免会产生一些错误匹配,因此需要根据几何限制和其它附加约束消除错误匹配，提高鲁棒性。n常用的去外点方法是RANSAC随机抽样一致性算法，常用的几何约束是极线约束关系。SIFT算法在硬件模拟平台上的实现n目前该算法已经成功移植进了硬件模拟平台中,实现了基本的目标匹配识别功能.n存在的问题:算法在硬件模拟平台上运行时间较长,目前难以达到实时性要求目标图像320 x256在硬件模拟平台中的实际处理时间n高斯尺度空间。对目标图像构建高

19、斯“金字塔”空间，在该算法中，要构建6组，每组由6幅图像构成的金字塔空间，相同组内图像大小相同，下一组的图像为上一组图像大小的1/4。考虑到金子塔顶端图像信息量比较少，特征点数量也比较少，因此只构建4组，每组6幅图像。对目标图像进行一次高斯平滑所需要时间约为10秒，一幅320 x256图像所需内存为320KB，构建整个目标图像的高斯尺度空间所需时间约68秒，所需内存约2.5MB。nDOG空间。由高斯尺度空间相同组内相邻两幅图像做差得到，在本算法中要构建6组，每组由3幅图像构成的DOG空间。存储DOG空间所需内存约1.3MB,程序运行所需时间为3秒。n极值点检测。主要包括特征点检测和排除不稳定特

20、征点并去除边缘响应三部分函数构成，检测初始特征点个数174个，时间约12秒。n特征点方向分配。该部分函数主要由四部分子函数构成，首先对每一个特征点所在的一定区域内生成该特征点的方向直方图，然后进行两次平滑处理，再求取方向直方图的最大值，最后将赋予方向信息的特征点进行存储。分配方向后，由于有较少一部分特征点具有多方向特征，特征点数量有所增加，由174个增加到204个，该部分程序运行时间约30秒。n特征点描述。该部分程序主要实现两部分功能，其中第一个主要功能是生成特征点描述子，它包括两个子函数，一个子函数的功能是确定每个特征点描述子所在区域并生成方向直方图，另一个子函数的功能是生成描述子空间。第二

21、个主要功能就是对生成的特征点描述子进行归一化和门限化。整个特征点描述程序运行时间要约60秒。目前进展及所遇到的问题目前进展及所遇到的问题 n基于尺度不变特征的图像匹配方法对目标图像的仿射变形、投影变换、光照强度、遮挡、杂物场景等问题在一定程度上有很好的解决。但是算法性能总是与其计算复杂度成正比，此算法目前难以满足成像末制导的实时性要求。在对该算法目前进行的研究中主要遇到的问题有以下几个方面：n(1)SIFT算法对于小目标检测效果不好n(2)旋转角度过大时检测效果不理想 n(3)是否对图像进行插值对检测结果影响很大 n(4)模板大小对检测效果的影响 n(5)程序运行时间较常，很难满足实时性的要求 n(6)该算法本身还有需要完善的地方 实时图像中目标较小时的匹配结果模板大小64x64 实时图像大小320 x256实时图像中目标同时具有较大旋转与缩放时的匹配结果,模板64x64 实时图像320 x256有插值放大时的匹配结果,模板大小64x64,实时图像 320 x256无插值放大的匹配结果是否进行插值对匹配结果影响很大模板为32x32大小时模板为64x64时 结束 谢谢!