【专题技术】尺度空间理论和SIFT算法小结

尺度空间理论尺度空间(scalesPace)思想最早由Iijima于1962年提出([l])，但当时并未引起算机视觉领域研究者们的足够注意，直到上世纪八十年代，witkin([2])Koenderink([3])等人的奠基性工作使得尺度空间方法逐渐得到关注和发展。此后，随着非线性扩散方程、变分法和数学形态学等方法在计算机视觉领域中的广泛应用，尺度空间方法进入了快速发展阶段。尺度空间方法本质上是偏微分方程对图像的作用。尺度空间方法的基本思想是：在视觉信息(图像信息)处理模型中引入一个被视为尺度的参数，通过连续变化尺度参数获得不同尺度下的视觉处理信息，然后综合这些信息以深入地挖掘图像的本质特征。尺度空间方法将传统的单尺度视觉信息处理技术纳入尺度不断变化的动态分析框架中，因此更容易获得图像的本质特征。尺度空间的生成目的是模拟图像数据的多尺度特征。高斯卷积核是实现尺度变换的唯一线性核。尺度空间是一个用来控制观察尺度或表征图像数据多尺度自然特性的框架；信号的尺度空间表征是信号的特征结构集合并包含有一个连续的尺度参量(即观察尺度)。尺度空间理论[8]是通过对原始图像进行尺度变换，获得图像多尺度下的尺度空间表示序列，对这些序列进行尺度空间主轮廓的提取，并以该主轮廓作为一种特征向量，实现边缘、角点检测和不同分辨率上的特征提取等。尺度空间表示是一种基于区域而不是基于边缘的表达，它无需关于图像的先验知识。与通过减小图像尺寸而提高计算效率的其他多尺度或多分辨率表达相比，尺度空间表示由平滑获得，在多由尺度上都保持了不变的空间取样，但对同一特征而言，它在粗糙尺度上对应更多的像素点，这样就使得对这些数据的计算任务得到连续的简化。尺度空间表示的另一个重要特征，就是基于尺度的结构特性能以一种简单的方式解析的表达，不同尺度上的特征可以一种精确的方式联系起来。作为尺度空间理论中的一个重要概念，尺度空间核被定义为：inoutfKf(1)对于所有的信号inf，若它与变换核K卷积后得到的信号outf中的极值(一阶微分过零点数)不超过原图像的极值，则称K为尺度空间核，所进行的卷积变换称为尺度变换。尺度空间表示通过平滑获得,可描述为),(x空间（？y呢？），x和分别为位置参数和尺度参数。当采用不同尺度的平滑函数对同一图像进行滤波时，得到的一簇图像就是原始图像相对于该平滑函数的尺度空间，为尺度空间坐标。在高斯尺度空间，同一类型特征点和边缘在不同的尺度上具有因果性，即当尺度变化时，新的特征点可能出现，而老的特征点可能移位或消失。这种因果性带来的含糊性是固有的，不可避免的，不能企求消除，但可以减小。然而,由于高斯核[9]具有线性、平移不变性、旋转不变性和子集特性等特性，可以证明，高斯核是实现尺度变换的唯一变换核[10]。因此，利用高斯核的一阶导数将Harris角点算子变换成尺度空间的表示。[8]LindebergT.Scale-spacetheory：Abasictoolforana-lysingstructuresatdifferentscales[J].JournalAp-pliedStatistics,1994,21(2)：223261.[9]BabaudJ,WitkinAP,BaudinM,etal.UniquenessoftheGaussiankernelforscale-spacefiltering[J].IEEETransactionsonPatternAnalysisMachineIntelligence,1986,8(1)：2633.[10]吴立德.计算机视觉[M].上海：复旦大学出版社，1993.Harris角点提取方法是目前效果最好的，它不受摄像机姿态及光照的影响。然而，对于尺度变化较大的视觉系统，该方法却不能保持特征的不变性，如移动机器人视觉系统，由于移动机器人位置变化，其采集的图像不仅会有光照、位置的变化，还存在尺度变化。通常，通过大尺度观察图像，可以得到图像的粗糙画面；而从小尺度观察，能够检测到图像的细节特征。实际图像中的特征角点常常发生在不同的尺度范围上，并且每一角点的尺度信息是未知的。一般认为在较大尺度下能较可靠地消除误检和检测到真正的角点，但角点的定位不易准确。相反，在较小尺度下对真正的特征角点的定位比较准确，但误检的比例会增加。所以，可考虑先在较大尺度下检测出角点，然后在较小尺度下对真正特征角点进行较精确定位。因此，利用多尺度技术检测角点是获得理想特征角点的一种理想途径，即有效组合利用多个不同尺度的角点检测算子，同时正确地检测一幅图像内发生在各个尺度水平上的角点。某一角点检测算法的优劣可通过稳定性准则、可靠性准则和抗噪性能准则来评价[12]。这3个准则依靠改变参数、阈值或增加噪声后检测出的角点与初始检测出的角点的重复率η决定。%100,minjijiCCCC分子的含义是计算不同尺度下检测到的完全相同的角点(即横、纵坐标都相同)的数目。由式(9)可知，重复率η越大，算法的稳定性越高。[12]杨杨，张田文.角点检测算法评价方法的研究[J].哈尔滨工业大学学报，1998，30(2)：710.为了能够对特征点在不同尺度下提取的效果进行定量评价，使用以下公式[12]：%100,,2121mmmeanIIC分子表示两幅图像中重复特征点的个数，分母表示两幅图像中特征点提取个数的平均值，这个值被称为重复率。重复率越大，则说明特征点算法效果越好，即算法提取特征点的稳定性越好。[12]CSchmidRM,CBauckhage.Comparingandevaluatingin-terestpoints[A].Proceedingsofthe6thInternationalConfer-enceonComputerVision[C].Bombay,India:IEEEComputerSocietyPress,1998.230-235.视觉多尺度分析是一种新的视觉信息处理方法，其基本思想是：当我们用眼睛观察物体且物体和观察者之间的距离(将距离视为尺度参数)不断变化时，视网膜将感知到不断变化的图像信息，分析和综合这些不同尺度下的视觉信息以获得被观察物体的本质特征，这种视觉分析方法即称为视觉多尺度分析。尺度空间满足的视觉不变性：上述诸不变性定义的视觉解释如下：当我们用眼睛观察物体时，一方面，当物体所处背景的光照条件变化时，视网膜感知图像的亮度水平和对比度是不同的，因此要求尺度空间算子对图像的分析不受图像的灰度水平和对比度变化的影响，即满足灰度不变性和对比度不变性；另一方面，相对于某一固定坐标系，当观察者和物体之间的相对位置变化时，视网膜所感知的图像的位置、大小、角度和形状(三维物体投影到视网膜上的二维图像轮廓，通常对应于图像的仿射变换)是不同的，因此要求尺度空间算子对图像的分析与图像的位置、大小、角度以及仿射变换无关，即满足平移不变性、尺度不变性、欧基里德不变性以及仿射不变性。尺度空间的因果性：上述定义所叙述的锥形性意味着大尺度下的图像可以通过对小尺度图像的尺度空间算子作用而直接获得，局部对比性意味着尺度空间算子作用对图像灰度值的局部保序性，而正则性则是为导出尺度空间算子表达形式而引入的附加要求。SIFT算法小结1SIFT发展历程SIFT算法由D.G.Lowe1999年提出，2004年完善总结。后来Y.Ke将其描述子部分用PCA代替直方图的方式，对其进行改进。2SIFT主要思想SIFT算法是一种提取局部特征的算法，在尺度空间寻找极值点，提取位置，尺度，旋转不变量。3SIFT算法的主要特点：a)SIFT特征是图像的局部特征，其对旋转、尺度缩放、亮度变化保持不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定性。b)独特性(Distinctiveness)好，信息量丰富，适用于在海量特征数据库中进行快速、准确的匹配[23]。c)多量性，即使少数的几个物体也可以产生大量SIFT特征向量。d)高速性，经优化的SIFT匹配算法甚至可以达到实时的要求。e)可扩展性，可以很方便的与其他形式的特征向量进行联合。4SIFT算法步骤：1）检测尺度空间极值点2）精确定位极值点3）为每个关键点指定方向参数4）关键点描述子的生成5SIFT算法详细▲尺度空间的生成尺度空间理论目的是模拟图像数据的多尺度特征。高斯卷积核是实现尺度变换的唯一线性核[]，于是一副二维图像的尺度空间定义为：),(),,(),,(yxIyxGyxL（1）其中),,(yxG是尺度可变高斯函数，2)(22/21),,(22yxeyxG（2）（x，y）是空间坐标，是尺度坐标。大小决定图像的平滑程度，大尺度对应图像的概貌特征，小尺度对应图像的细节特征。大的值对应粗糙尺度(低分辨率)，反之，对应精细尺度(高分辨率)。为了有效的在尺度空间检测到稳定的关键点，提出了高斯差分尺度空间（DOGscale-space）。利用不同尺度的高斯差分核与图像卷积生成。),,(),,(),()),,(),,((),,(yxLkyxLyxIyxGkyxGyxD（3）DOG算子计算简单，是尺度归一化的LoG算子的近似。图像金字塔的构建：图像金字塔共O组，每组有S层，下一组的图像由上一组图像降采样得到。图1由两组高斯尺度空间图像示例金字塔的构建，第二组的第一副？？图像由第一组的第一副到最后一副图像由一个因子2降采样得到。????如何实现？？图2DoG算子的构建：图1TwooctavesofaGaussianscale-spaceimagepyramidwiths=2intervals.Thefirstimageinthesecondoctaveiscreatedbydownsamplingthesecond？？tolastimageintheprevious图2ThedifferenceoftwoadjacentintervalsintheGaussianscale-spacepyramidcreateanintervalinthedifference-of-Gaussianpyramid(showningreen).▲空间极值点检测为了寻找尺度空间的极值点，每一个采样点要和它所有的相邻点比较，看其是否比它的图像域和尺度域的相邻点大或者小。如图3所示，中间的检测点和它同尺度的8个相邻点和上下相邻尺度对应的9×2个点共26个点比较，以确保在尺度空间和二维图像空间都检测到极值点。一个点如果在DOG尺度空间本层以及上下两层的26个领域中是最大或最小值时，就认为该点是图像在该尺度下的一个特征点,如图1所示。▲构建尺度空间需确定的参数－尺度空间坐标O－octave坐标S－sub-level坐标和O、S的关系Ssoso/02),(，],1,...,0[minOoo]1,...,0[Ss其中0是基准层尺度。o－octave坐标，s－sub-level坐标。注：octaves的索引可能是负的。第一组索引常常设为0或者-1,当设为-1的时候，图像在计算高斯尺度空间前先扩大一倍。空间坐标x是组octave的函数，设0x是0组的空间坐标，则1,...,01,...,0,,20000MNxoxxo如果00,MN是基础组o=0的分辨率，则其他组的分辨率由下式获得：0000,22ooNMNM注：在Lowe的文章中，Lowe使用了如下的参数：1/0min0.5,1.62,1,3SnoS在组o=-1，图像用双线性插值扩大一倍（对于扩大的图像1n）。▲精确确定极值点位置通过拟和三维二次函数以精确确定关键点的位置和尺度（达到亚像素精度），同时去除低对比度的关键点和不稳定的边缘响应点(因为DoG算子会产生较强的边缘响应)，以增强匹配稳定性、提高抗噪声能力。图3DoG尺度空间局部极值检测①空间尺度函数),,(yxD（在局部极值点,,00yx处的，去掉这个限制不行吗？XXDXXXDyxDyx