搜索
Sift算法研究与实现摘要:本文主要对SIFT算法做了简单的介绍和分析，阐述了其原理特性，并且用C语言进行了实现。实现中调用了OPENCV的部分API以及数据结构。运用VC对算法实现进行了仿真，得到预期效果。此算法在数字图像处理中对于影响局部特征的提取，具有很高的实用价值。0引言尺度不变特征转换（Scale-invariantfeaturetransform或SIFT）是一种电脑视觉的算法用来侦测与描述影像中的局部性特征，它在空间尺度中寻找极值点，并提取出其位置、尺度、旋转不变量，此算法由DavidLowe在1999年所发表，2004年完善总结。Sift算法就是用不同尺度（标准差）的高斯函数对图像进行平滑，然后比较平滑后图像的差别，差别大的像素就是特征明显的点。什么是尺度和尺度空间呢？尺度就是受delta这个参数控制的表示。而不同的L（x,y,delta)就构成了尺度空间，实际上，具体计算的时候，即使连续的高斯函数，都要被离散为（一般为奇数大小）(2*k+1)*(2*k+1)矩阵，来和数字图像进行卷积运算。1、建立图像尺度空间DavidLowe关于Sfit算法，2004年发表在Int.JournalofComputerVision的经典论文中，对尺度空间（scalspace)是这样定义的：IthasbeenshownbyKoenderink(1984)andLindeberg(1994)thatunderavarietyofreasonableassumptionstheonlypossiblescale-spacekernelistheGaussianfunction.Therefore,thescalespaceofanimageisdefinedasafunction,L(x;y;delta)thatisproducedfromtheconvolutionofavariable-scaleGaussian,G(x;y;delta),withaninputimage,I(x;y):因此，一个图像的尺度空间，L（x,y,delta),定义为原始图像I(x,y)与一个可变尺度的2维高斯函数G(x,y,delta)卷积运算。即，原始影像I(x，y)在不同的尺度e下，与高斯滤波器G(x,y,e)进行卷积，得到L(x,y,e)，如下：L(x,y,e)=G(x,y,e)*I(x,y)其中G(x,y,e)是尺度可变高斯函数，G(x,y,e)=[1/2*pi*e2]*exp[-(x2+y2)/2e2]（x，y）是空间坐标，e是尺度坐标。为了更有效的在尺度空间检测到稳定的关键点，提出了高斯差分尺度空间（DOGscale-space）。利用不同尺度的高斯差分核与原始图像I(x,y)，卷积生成。D(x,y,e)=((G(x,y,ke)-G(x,y,e))*I(x,y)=L(x,y,ke)-L(x,y,e)DOG算子计算简单，是尺度归一化的LoG算子的近似。Gaussian卷积是有尺寸大小的，使用同一尺寸的滤波器对两幅包含有不同尺寸的同一物体的图像求局部最值将有可能出现一方求得最值而另一方却没有的情况，但是容易知道假如物体的尺寸都一致的话它们的局部最值将会相同。有了图像金字塔就可以对每一层求出局部最值，但是这样的稳定点数目将会十分可观，所以需要使用某种方法抑制去除一部分点，但又使得同一尺度下的稳定点得以保存1、高斯卷积在组建一组尺度空间后，再组建下一组尺度空间，对上一组尺度空间的最后一幅图像进行二分之一采样，得到下一组尺度空间的第一幅图像，然后进行像建立第一组尺度空间那样的操作，得到第二组尺度空间，公式定义为L(x,y,e)=G(x,y,e)*I(x,y)图像金字塔的构建：图像金字塔共O组，每组有S层，下一组的图像由上一组图像降采样得到，效果图，图A如下(左为上一组，右为下一组)：图A2、高斯差分在尺度空间建立完毕后，为了能够找到稳定的关键点，采用高斯差分的方法来检测那些在局部位置的极值点，即采用俩个相邻的尺度中的图像相减，即公式定义为：D(x,y,e)=((G(x,y,ke)-G(x,y,e))*I(x,y)=L(x,y,ke)-L(x,y,e)效果图，图B：图BSIFT的精妙之处在于采用图像金字塔的方法解决这一问题，我们可以把两幅图像想象成是连续的，分别以它们作为底面作四棱锥，就像金字塔，那么每一个截面与原图像相似，那么两个金字塔中必然会有包含大小一致的物体的无穷个截面，但应用只能是离散的，所以我们只能构造有限层，层数越多当然越好，但处理时间会相应增加，层数太少不行，因为向下采样的截面中可能找不到尺寸大小一致的两个物体的图像。咱们再来具体阐述下构造D(x,y,e)的详细步骤：1、首先采用不同尺度因子的高斯核对图像进行卷积以得到图像的不同尺度空间，将这一组图像作为金子塔图像的第一层。2、接着对第一层图像中的2倍尺度图像（相对于该层第一幅图像的2倍尺度）以2倍像素距离进行下采样来得到金子塔图像的第二层中的第一幅图像，对该图像采用不同尺度因子的高斯核进行卷积，以获得金字塔图像中第二层的一组图像。3、再以金字塔图像中第二层中的2倍尺度图像（相对于该层第一幅图像的2倍尺度）以2倍像素距离进行下采样来得到金字塔图像的第三层中的第一幅图像，对该图像采用不同尺度因子的高斯核进行卷积，以获得金字塔图像中第三层的一组图像。这样依次类推，从而获得了金字塔图像的每一层中的一组图像，如下图所示：4、对上图得到的每一层相邻的高斯图像相减，就得到了高斯差分图像，如下述第一幅图所示。下述第二幅图中的右列显示了将每组中相邻图像相减所生成的高斯差分图像的结果，图中只给出了第一层和第二层高斯差分图像的计算：5、因为高斯差分函数是归一化的高斯拉普拉斯函数的近似，所以可以从高斯差分金字塔分层结构提取出图像中的极值点作为候选的特征点。对DOG尺度空间每个点与相邻尺度和相邻位置的点逐个进行比较，得到的局部极值位置即为特征点所处的位置和对应的尺度。2、检测关键点为了寻找尺度空间的极值点，每一个采样点要和它所有的相邻点比较，看其是否比它的图像域和尺度域的相邻点大或者小。如下图，图3所示，中间的检测点和它同尺度的8个相邻点和上下相邻尺度对应的9×2个点共26个点比较，以确保在尺度空间和二维图像空间都检测到极值点。因为需要同相邻尺度进行比较，所以在一组高斯差分图像中只能检测到两个尺度的极值点（如上述第二幅图中右图的五角星标识），而其它尺度的极值点检测则需要在图像金字塔的上一层高斯差分图像中进行。依次类推，最终在图像金字塔中不同层的高斯差分图像中完成不同尺度极值的检测。当然这样产生的极值点并不都是稳定的特征点，因为某些极值点响应较弱，而且DOG算子会产生较强的边缘响应。如下为程序寻找关键点效果图：3、关键点方向的分配为了使描述符具有旋转不变性，需要利用图像的局部特征为给每一个关键点分配一个方向。利用关键点邻域像素的梯度及方向分布的特性，可以得到梯度模值和方向如下：其中，尺度为每个关键点各自所在的尺度。在以关键点为中心的邻域窗口内采样，并用直方图统计邻域像素的梯度方向。梯度直方图的范围是0～360度，其中每10度一个方向，总共36个方向。直方图的峰值则代表了该关键点处邻域梯度的主方向，即作为该关键点的方向。在计算方向直方图时，需要用一个参数等于关键点所在尺度1.5倍的高斯权重窗对方向直方图进行加权，上图中用蓝色的圆形表示，中心处的蓝色较重，表示权值最大，边缘处颜色潜，表示权值小。如下图所示，该示例中为了简化给出了8方向的方向直方图计算结果，实际sift创始人DavidLowe的原论文中采用36方向的直方图。原图对特征点的描述如下：方向直方图的峰值则代表了该特征点处邻域梯度的方向，以直方图中最大值作为该关键点的主方向。为了增强匹配的鲁棒性，只保留峰值大于主方向峰值80％的方向作为该关键点的辅方向。因此，对于同一梯度值的多个峰值的关键点位置，在相同位置和尺度将会有多个关键点被创建但方向不同。仅有15％的关键点被赋予多个方向，但可以明显的提高关键点匹配的稳定性。至此，图像的关键点已检测完毕，每个关键点有三个信息：位置、所处尺度、方向。由此可以确定一个SIFT特征区域。图给出关键点位置信息：4、特征点描述符通过以上步骤，对于每一个关键点，拥有三个信息：位置、尺度以及方向。接下来就是为每个关键点建立一个描述符，使其不随各种变化而改变，比如光照变化、视角变化等等。并且描述符应该有较高的独特性，以便于提高特征点正确匹配的概率。首先将坐标轴旋转为关键点的方向，以确保旋转不变性。领域梯度方向关键点特征向量接下来以关键点为中心取8×8的窗口。上图中左部分的中央黑点为当前关键点的位置，每个小格代表关键点邻域所在尺度空间的一个像素，箭头方向代表该像素的梯度方向，箭头长度代表梯度模值，图中蓝色的圈代表高斯加权的范围（越靠近关键点的像素梯度方向信息贡献越大）。然后在每4×4的小块上计算8个方向的梯度方向直方图，绘制每个梯度方向的累加值，即可形成一个种子点，上图右部分所示。此图中一个关键点由2×2共4个种子点组成，每个种子点有8个方向向量信息。这种邻域方向性信息联合的思想增强了算法抗噪声的能力，同时对于含有定位误差的特征匹配也提供了较好的容错性。在特征点处提取特征描述符，为特征点分配方向值运行如下图所示：实际计算过程中，为了增强匹配的稳健性，Lowe建议对每个关键点使用4×4共16个种子点来描述，这样对于一个关键点就可以产生128个数据，即最终形成128维的SIFT特征向量。此时SIFT特征向量已经去除了尺度变化、旋转等几何变形因素的影响，再继续将特征向量的长度归一化，则可以进一步去除光照变化的影响。5、相似性判定当两幅图像的SIFT特征向量生成后，下一步我们采用关键点特征向量的欧式距离来作为两幅图像中关键点的相似性判定度量。取图像A中的某个关键点，并找出其与图像B中欧式距离最近的前两个关键点，在这两个关键点中，如果最近的距离除以次近的距离少于某个比例阈值，则接受这一对匹配点。降低这个比例阈值，SIFT匹配点数目会减少，但更加稳定。6、核心代码主要算法核心代码：算法核心//本程序中，sift算法被分为以下五个步骤及其相对应的函数：//SIFT算法第一步：图像预处理CvMat*ScaleInitImage(CvMat*im);//金字塔初始化//SIFT算法第二步：建立高斯金字塔函数ImageOctaves*BuildGaussianOctaves(CvMat*image);//建立高斯金字塔//SIFT算法第三步：特征点位置检测，最后确定特征点的位置intDetectKeypoint(intnumoctaves,ImageOctaves*GaussianPyr);voidDisplayKeypointLocation(IplImage*image,ImageOctaves*GaussianPyr);//SIFT算法第四步：计算高斯图像的梯度方向和幅值，计算各个特征点的主方向voidComputeGrad_DirecandMag(intnumoctaves,ImageOctaves*GaussianPyr);intFindClosestRotationBin(intbinCount,floatangle);//进行方向直方图统计voidAverageWeakBins(double*bins,intbinCount);//对方向直方图滤波//确定真正的主方向boolInterpolateOrientation(doubleleft,doublemiddle,doubleright,double*degreeCorrection,double*peakValue);//确定各个特征点处的主方向函数voidAssignTheMainOrientation(intnumoctaves,ImageOctaves*GaussianPyr,ImageOctaves*mag_pyr,ImageOctaves*grad_pyr);