sift算法

齐凯华薛虹SIFT算法小结David.Lowe，总结了现有的基于不变量技术的特征检测方法，正式提出了一种基于尺度空间的，对图像平移、旋转、缩放、甚至仿射变换保持不变性的图像局部特征，以及基于该特征的描述符。并将这种方法命名为尺度不变特征变换（ScaleInvariantFeatureTransform），简称SIFT算法。①SIFT主要思想SIFT算法是一种提取局部特征的算法，在尺度空间寻找极值点，提取位置，尺度，旋转不变量。②SIFT算法的主要特点：a)SIFT特征是图像的局部特征，其对平移、旋转、尺度缩放、亮度变化保持不变性，对对光照变化、视角变化、仿射变换、噪声也保持一定程度的稳定性。具有较强的鲁棒性。b)独特性(Distinctiveness)好，信息量丰富，适用于在海量特征数据库中进行快速、准确的匹配，在特征匹配时可以以一个很高的概率正确匹配。c)多量性，即使少数的几个物体也可以产生大量SIFT特征向量，这对于目标识别非常重要。d)高速性，经优化的SIFT匹配算法甚至可以达到实时的要求。e)可扩展性，可以很方便的与其他形式的特征向量进行联合。③SIFT算法步骤：1）检测尺度空间极值点2）精确定位极值点，得到关键点，并确定关键点的位置和所处的尺度3）为每个关键点指定方向参数（使用极值点邻域梯度的主方向作为该关键点的方向特征，以实现算子对尺度和方向的无关性）4）关键点描述子的生成利用SIFT算法从图像中提取出的特征可用于同一个物体或场景的可靠匹配。④SIFT算法的原理▲尺度空间的生成尺度空间理论目的是模拟图像数据的多尺度特征。（为了使特征具有尺度不变性，特征点的检测是在多尺度空间完）成的。尺度空间理论最早出现于计算机视觉领域时，其目的是模拟图像数据的多尺度特征。高斯卷积核是实现尺度变换的唯一变换核，并且是唯一的线性核。所以一幅二维图像的尺度空间定义为：),(),,(),,(yxIyxGyxL其中),,(yxG是尺度可变高斯函数，2)(22/21),,(22yxeyxG（x，y）是空间坐标，符号*表示卷积,（x，y）代表图像的像素位置，是尺度空间因子，值越小表示图像被平滑的越少，相应的尺度也就越小。大尺度对应于图像的概貌特征，小尺度对应于图像的细节特征。齐凯华薛虹为了有效的在尺度空间检测到稳定的关键点，提出了高斯差分尺度空间（DOGscale-space）。利用不同尺度的高斯差分核与图像卷积生成。),,(),,(),()),,(),,((),,(yxLkyxLyxIyxGkyxGyxD选择高斯差分函数主要有两个原因，第一，它计算效率高。第二，它可作为尺度归一化的拉普拉斯高斯函数G22的一种近似。DOG算子计算简单，是尺度归一化的LoG算子的近似。图像金字塔的构建：图像金字塔共O组，每组有S层，下一组的图像由上一组图像降采样得到。图1由两组高斯尺度空间图像示例金字塔的构建，第二组的第一副图像由第一组的第一副到最后一副图像由一个因子2降采样得到。图2DoG算子的构建：图1TwooctavesofaGaussianscale-spaceimagepyramidwiths=2intervals.Thefirstimageinthesecondoctaveiscreatedbydownsamplingthesecondtolastimageintheprevious图2ThedifferenceoftwoadjacentintervalsintheGaussianscale-spacepyramidcreateanintervalinthedifference-of-Gaussianpyramid(showningreen).齐凯华薛虹1994年Lindeberg研究发现高斯差分函数（DifferenceofGaussian，简称DOG算子）与尺度归一化的高斯拉普拉斯函数G22非常近似，如图1所示，图中红色曲线表示的是高斯差分算子，而蓝色曲线表示的是高斯拉普拉斯算子。2002年Mikolajczyk在详细的实验比较中发现G22的极大值和极小值同其它的特征提取函数，例如：梯度，Hessian或Harris角特征比较，能够产生最稳定的图像特征。其中),,(yxD和G22的关系可以从如下公式推导得到：GG2利用差分近似代替微分，则有：kyxGkyxGGG),,(),,(2因此有GkyxGkyxG22)1(),,(),,(其中k-1是个常数，并不影响极值点位置的求取。图1高斯拉普拉斯和高斯差分的比较图2中展示了构造),,(yxD的一种有效方法。（1）首先采用不同尺度因子的高斯核对图像进行卷积以得到图像的不同尺度空间，将这一组图像作为金子塔图像的第一层。（2）接着对第一层图像中的2倍尺度图像（相对于该层第一幅图像的2倍尺度）以2倍像素距离进行下采样来得到金子塔图像的第二层中的第一幅图像，对该图像采用不同尺度因子的高斯核进行卷积，以获得金字塔图像中第二层的一组图像。（3）再以金字塔图像中第二层中的2倍尺度图像（相对于该层第一幅齐凯华薛虹图像的2倍尺度）以2倍像素距离进行下采样来得到金字塔图像的第三层中的第一幅图像，对该图像采用不同尺度因子的高斯核进行卷积，以获得金字塔图像中第三层的一组图像。这样依次类推，从而获得了金字塔图像的每一层中的一组图像，如图2(a)所示。（4）对2(a)得到的每一层相邻的高斯图像相减，就得到了高斯差分图像，如图2(b)所示。图2(c)中的右列显示了将每组中相邻图像相减所生成的高斯差分图像的结果，限于篇幅，图中只给出了第一层和第二层高斯差分图像的计算。（5）因为高斯差分函数是归一化的高斯拉普拉斯函数的近似，所以可以从高斯差分金字塔分层结构提取出图像中的极值点作为候选的特征点。对DOG尺度空间每个点与相邻尺度和相邻位置的点逐个进行比较，得到的局部极值位置即为特征点所处的位置和对应的尺度。(a)(b)齐凯华薛虹(c)图2高斯金字塔中相邻尺度两幅高斯图像相减得到DOG尺度空间图像▲空间极值点检测为了寻找尺度空间的极值点，每一个采样点要和它所有的相邻点比较，看其是否比它的图像域和尺度域的相邻点大或者小。如图3所示，中间的检测点和它同尺度的8个相邻点和上下相邻尺度对应的9×2个点共26个点比较，以确保在尺度空间和二维图像空间都检测到极值点。因为需要同相邻尺度进行比较，所以在一组高斯差分图像中只能检测到两个尺度的极值点（如图2(c)中右图的五角星标识），而其它尺度的极值点检测则需要在图像金字塔的上一层高斯差分图像中进行。依次类推，最终在图像金字塔中不同层的高斯差分图像中完成不同尺度极值的检测。当然这样产生的极值点并不都是稳定的特征点，因为某些极值点响应较弱，而且DOG算子会产生较强的边缘响应。图3DoG尺度空间局部极值检测齐凯华薛虹▲构建尺度空间需确定的参数－尺度空间坐标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算子会产生较强的边缘响应)，以增强匹配稳定性、提高抗噪声能力。获取关键点处拟和函数，XXDXXXDDXDTT2221)(求导并让方程等于零，可以得到极值点：XDXDX212ˆ对应极值点，方程的值为：XXDDXDTˆ21)ˆ()ˆ(XD的值对于剔除低对比度的不稳定特征点十分有用，通常将03.0)ˆ(XD的极值点视为低对比度的不稳定特征点，进行剔除。同时，在此过齐凯华薛虹程中获取了特征点的精确位置以及尺度。一个定义不好的高斯差分算子的极值在横跨边缘的地方有较大的主曲率，而在垂直边缘的方向有较小的主曲率。DOG算子会产生较强的边缘响应，需要剔除不稳定的边缘响应点。获取特征点处的Hessian矩阵，主曲率通过一个2x2的Hessian矩阵H求出:yyxyxyxxDDDDH(5-10)H的特征值和代表x和y方向的梯度，-2)()(,)(xyyyxxyyxxDDDHDetDDHTr(5-11))(HTr表示矩阵H对角线元素之和，)(HDet表示矩阵H的行列式。假设是较大的特征值，而是较小的特征值，令r，则rrrrHDetHTr22222)1()()()()(xxxyxyyyDDHDD导数由采样点相邻差估计得到。D的主曲率和H的特征值成正比，令为最大特征值，为最小的特征值，则公式(r+1)2/r的值在两个特征值相等时最小，随着r的增大而增大。值越大，说明两个特征值的比值越大，即在某一个方向的梯度值越大，而在另一个方向的梯度值越小，而边缘恰恰就是这种情况。所以为了剔除边缘响应点，需要让该比值小于一定的阈值，因此，为了检测主曲率是否在某域值r下，只需检测在Lowe的文章中，取r＝10。▲关键点方向分配为了使描述符具有旋转不变性，需要利用图像的局部特征为给每一个关键点分配一个方向。利用关键点邻域像素的梯度及方向分布的特性，可以得到梯度模值和方向如下：齐凯华薛虹))),1(),1())1,()1,(((tan),())1,()1,(()),1(),1((),(122yxLyxLyxLyxLyxyxLyxLyxLyxLyxm其中，尺度L为每个关键点各自所在的尺度。在以关键点为中心的邻域窗口内采样，并用直方图统计邻域像素的梯度方向。梯度直方图的范围是0～360度，其中每10度一个方向，总共36个方向。直方图的峰值则代表了该关键点处邻域梯度的主方向，即作为该关键点的方向。在计算方向直方图时，需要用一个参数等于关键点所在尺度1.5倍的高斯权重窗对方向直方图进行加权，图4中用蓝色的圆形表示，中心处的蓝色较重，表示权值最大，边缘处颜色潜，表示权值小。如图4所示，该示例中为了简化给出了8方向的方向直方图计算结果，实际原文中采用36方向的直方图。方向直方图的峰值则代表了该特征点处邻域梯度的方向，以直方图中最大值作为该关键点的主方向。为了增强匹配的鲁棒性，只保留峰值大于主方向峰值80％的方向作为该关键点的辅方向。因此，对于同一梯度值的多个峰值的关键点位置，在相同位置和尺度将会有多个关键点被创建但方向不同。仅有15％的关键点被赋予多个方向，但可以明显的提高关键点匹配的稳定性。至此，图像的关键点已检测完毕，每个关键点有三个信息：位置、所处尺度、方向。由此可以确定一个SIFT特征区域（在实验章节用椭圆或箭头表示）。▲特征点描述子生成通过以上步骤，对于每一个关键点，拥有三个信息：位置、尺度以及方向。接下来就是为每个关键点建立一个描述符，使其不随各种变化而改变，比如光照变化、视角变化等等。并且描述符应该有较高的独特性，以便于提高特征点正确匹配的概率。首先将坐标轴旋转为关键点的方向，以确保旋转不变性。主方向齐凯华薛虹图5由关键点邻域梯度信息生成特征向量接下来以关键点为中心取8×8的窗口。图5左部分的中央黑