SIFT算法分析

1、SIFT 算法分析1 SIFT 主要思想SIFT算法是一种提取局部特征的算法，在尺度空间寻找极值点，提取位置，尺度，旋转不变量。2 SIFT 算法的主要特点：a) SIFT特征是图像的局部特征，其对旋转、尺度缩放、亮度变化保持不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定性。b) 独特性 (Distinctiveness)好，信息量丰富，适用于在海量特征数据库中进行快速、准确的匹配。c) 多量性，即使少数的几个物体也可以产生大量 SIFT特征向量。d) 高速性，经优化的 SIFT匹配算法甚至可以达到实时的要求。e) 可扩展性，可以很方便的与其他形式的特征向量进行联合。3 SIFT 算法

2、流程图：精选文库4 SIFT 算法详细1）尺度空间的生成尺度空间理论目的是模拟图像数据的多尺度特征。高斯卷积核是实现尺度变换的唯一线性核， 于是一副二维图像的尺度空间定义为：L( x, y, ) G( x, y, ) I (x, y)其中 G ( x, y,) 是尺度可变高斯函数， G ( x, y, )12 e (x 2 y2 ) / 2 22（ x，y）是空间坐标， 是尺度坐标。 大小决定图像的平滑程度，大尺度对应图像的概貌特征，小尺度对应图像的细节特征。大的 值对应粗糙尺度 (低分辨率 )，反之，对应精细尺度 (高分辨率 )。为了有效的在尺度空间检测到稳定的关键点，提出了高斯差分尺度空间

3、（ DOG scale-space）。利用不同尺度的高斯差分核与图像卷积生成。D ( x, y,)(G ( x, y,k)G( x, y,)I ( x, y)L( x, y,k)L( x, y,)DOG算子计算简单，是尺度归一化的LoG算子的近似。图像金字塔的构建：图像金字塔共O组，每组有 S层，下一组的图像由上一组图像降采样得到。图1由两组高斯尺度空间图像示例金字塔的构建，第二组的第一副图像由第一组的第一副到最后一副图像由一个因子2降采样得到。图 2 DoG算子的构建：图1 Two octaves of a Gaussian scale-space image pyramid with s

4、=2 intervals. The first image in the second octave is created by down sampling to last image in the previous-2精选文库图2 The difference of two adjacent intervals in the Gaussian scale-space pyramid create an interval in the difference-of-Gaussian pyramid (shown in green).2) 空间极值点检测为了寻找尺度空间的极值点， 每一个采样点要和

5、它所有的相邻点比较， 看其是否比它的图像域和尺度域的相邻点大或者小。如图 3所示，中间的检测点和它同尺度的 8个相邻点和上下相邻尺度对应的 9× 2个点共 26个点比较，以确保在尺度空间和二维图像空间都检测到极值点。 一个点如果在 DOG尺度空间本层以及上下两层的 26个领域中是最大或最小值时， 就认为该点是图像在该尺度下的一个特征点 ,如图 1所示。图 3 DoG 尺度空间局部极值检测3) 构建尺度空间需确定的参数尺度空间坐标Ooctave坐标S sub-level 坐标和 O、 S的关系(o,s)0 2o s / S ， oomin0,.,O1, s0,., S1-3精选文库其中

6、0 是基准层尺度。 ooctave坐标， s sub-level 坐标。注： octaves 的索引可能是负的。第一组索引常常设为 0或者 -1,当设为 -1的时候，图像在计算高斯尺度空间前先扩大一倍。空间坐标 x是组 octave的函数，设 x0 是0组的空间坐标，则x 2o x0 , o, x0 0,., N 0 1 0,., M 0 1如果 M 0 , N0 是基础组 o=0的分辨率，则其他组的分辨率由下式获得：N 0N 0, M 0M 02o2o注：在 Lowe的文章中， Lowe使用了如下的参数：n 0.5, 0 1.6 21/ S , omin1,S 3在组 o=-1，图像用双线性

7、插值扩大一倍（对于扩大的图像n1 ）。4）精确确定极值点位置通过拟和三维二次函数以精确确定关键点的位置和尺度（达到亚像素精度），同时去除低对比度的关键点和不稳定的边缘响应点 (因为 DoG算子会产生较强的边缘响应 )，以增强匹配稳定性、提高抗噪声能力。空间尺度函数 D ( x, y,)D( x, y, ) D x0 , y0 ,D TX1 X T2 D2 X ）泰勒展开式如下 :X 02X 0D ( x, y, ) D x, y,D Tx1 xT2 Dxx2x2?2 D 1D对上式求导 ,并令其为 0,得到精确的位置x?, x2xx在已经检测到的特征点中 ,要去掉低对比度的特征点和不稳定的边缘

8、响应点。去除低对比度的点：把公式 (4)代入公式 (3) ，只取前两项可得：1D T?D ( x?) D x, y,x2 x若 D x? 0.03，该特征点就保留下来，否则丢弃。边缘响应的去除一个定义不好的高斯差分算子的极值在横跨边缘的地方有较大的主曲率，而-4精选文库在垂直边缘的方向有较小的主曲率。主曲率通过一个2x2 的Hessian矩阵 H求出 :HDxxDxyDxyDyy导数由采样点相邻差估计得到。D的主曲率和 H的特征值成正比，令为最大特征值，为最小的特征值，则令，则：2r 的增大而增大，因此，(r + 1) /r 的值在两个特征值相等的时候最小，随着为了检测主曲率是否在某域值 r

9、下，只需检测在Lowe的文章中，取 r 10。5）关键点方向分配利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数，使算子具备旋转不变性。式(5) 为(x,y) 处梯度的模值和方向公式。其中 L所用的尺度为每个关键点各自所在的尺度。在实际计算时， 我们在以关键点为中心的邻域窗口内采样， 并用直方图统计邻域像素的梯度方向。 梯度直方图的范围是 0 360度，其中每 10度一个柱， 总共 36 个柱。直方图的峰值则代表了该关键点处邻域梯度的主方向， 即作为该关键点的方向。图 4是采用 7个柱时使用梯度直方图为关键点确定主方向的示例。（ 窗口尺寸采用 Lowe推荐的 1.5 ×

10、1.5 ）-5精选文库图 4 由梯度方向直方图确定主梯度方向在梯度方向直方图中，当存在另一个相当于主峰值 80%能量的峰值时，则将这个方向认为是该关键点的辅方向。 一个关键点可能会被指定具有多个方向 （一个主方向，一个以上辅方向），这可以增强匹配的鲁棒性 53 。至此，图像的关键点已检测完毕， 每个关键点有三个信息： 位置、所处尺度、方向。由此可以确定一个 SIFT特征区域（在实验章节用椭圆或箭头表示）。6）特征点描述子生成首先将坐标轴旋转为关键点的方向，以确保旋转不变性。图 5 由关键点邻域梯度信息生成特征向量接下来以关键点为中心取 8×8的窗口。图 5-4 左部分的中央黑点为当前

11、关键点的位置，每个小格代表关键点邻域所在尺度空间 ( 和关键点是否为一个尺度空间 ) 的一个像素，利用公式（ 5）求得每个像素 i , j 的梯度幅值 mi , j 与梯度方向 i , j ，箭头方向代表该像素的梯度方向， 箭头长度代表梯度模值， 然后用高斯窗口对其进行加权运算 , 每个像素对应一个向量，长度为 G ' ,i , j mi , j ， G ' , i, j 为该像素点的高斯权值， 方向为i , j ， 图中蓝色的圈代表高斯加权的范围（越靠近关键点的像素梯度方向信息贡献越大）。高斯参数取3倍特征点所在的尺度。然后在每 4×4的小块上计算 8个方向的梯度方

12、向直方图，绘制每个梯度方向的累加值，即可形成一个种子点， 如图 5右部分所示。 此图中一个关键点由 2×2共4个种子点组成，每个种子点有8个方向向量信息。这种邻域方向性信息联合的思想增强了算法抗噪声的能力， 同时对于含有定位误差的特征匹配也提供了较好的容错性。实际计算过程中， 为了增强匹配的稳健性， 对每个关键点使用 4× 4共 16个种子点来描述，这样对于一个关键点就可以产生 128个数据，即最终形成 128维的SIFT特征向量。此时 SIFT特征向量已经去除了尺度变化、 旋转等几何变形因素的影响，再继续将特征向量的长度归一化，则可以进一步去除光照变化的影响。-6精选文库

13、当两幅图像的 SIFT特征向量生成后，下一步我们采用关键点特征向量的欧式距离来作为两幅图像中关键点的相似性判定度量。取图像1中的某个关键点，并找出其与图像 2中欧式距离最近的前两个关键点，在这两个关键点中，如果最近的距离除以次近的距离少于某个比例阈值，则接受这一对匹配点。 降低这个比例阈值，SIFT匹配点数目会减少， 但更加稳定。 为了排除因为图像遮挡和背景混乱而产生的无匹配关系的关键点, 用比较最近邻距离与次近邻距离的方法, 距离比率 ratio 小于某个阈值的认为是正确匹配。 因为对于错误匹配 , 由于特征空间的高维性 , 相似的距离可能有大量其他的错误匹配 , 从而它的 ratio 值比

14、较高。推荐 ratio 的阈值为 0.8 。5 仿真结果分析将文件加入 matlab 目录后，在主程序中有两种操作：op1：寻找图像中的 Sift 特征：image,discrips,locs=sift('scene.pgm');Finding keypoints.1021 keypoints found.>> showkeys(image,locs); Drawing SIFT keypoints .5010015020025030035050100150200250300350400450500op2：对两幅图中的 SIFT特征进行匹配：match('s

15、cene.pgm','book.pgm');Finding keypoints.1021 keypoints found.Finding keypoints.882 keypoints found.Found 98 matches.-7精选文库501001502002503003501002003004005006007008006 代码1） appendimages.m% im = appendimages(image1, image2)% Return a new image that appends the two images side-by-side.func

16、tionim = appendimages(image1, image2)% Select the image with the fewest rows and fill in enough empty rows% to make it the same height as the other image.rows1 = size(image1,1);rows2 = size(image2,1);if(rows1 < rows2)image1(rows2,1) = 0;elseimage2(rows1,1) = 0;end% Now append both images side-by-

17、side. im = image1 image2;2） match.m% num = match(image1, image2)% This function reads two images, finds their SIFT features, and%displayslinesconnectingthematchedkeypoints. Amatchisaccepted%onlyifitsdistanceislessthandistRatiotimesthedistancetothe-8精选文库% second closest match.% It returns the number

18、of matches displayed.% Example: match('scene.pgm','book.pgm');functionnum = match(image1, image2)% Find SIFT keypoints for each image im1, des1, loc1 = sift(image1);im2, des2, loc2 = sift(image2);% ForefficiencyinMatlab,itischeapertocomputedotproductsbetween% unitvectorsratherthanEuc

19、lideandistances. Notethattheratioof% angles(acosofdotproductsofunitvectors)isa closeapproximation% to the ratio of Euclidean distances for small angles.% distRatio: Only keep matches in which the ratio of vector angles fromthe% nearest to second nearest neighbor is less than distRatio. distRatio = 0

20、.6;% Foreachdescriptorinthefirstimage,selectitsmatchtosecondimage.des2t = des2'% Precompute matrix transposefori = 1 : size(des1,1)dotprods= des1(i,:)*des2t;% Computesvectorofdotproductsvals,indx = sort(acos(dotprods);% Take inverse cosine and sortresults% Check if nearest neighbor has angle les

21、s than distRatio times 2nd.if(vals(1) < distRatio * vals(2)match(i) = indx(1);elsematch(i) = 0;endend% Create a new image showing the two images side by side. im3 = appendimages(im1,im2);% Show a figure with lines joining the accepted matches.figure('Position', 100 100 size(im3,2) size(im

22、3,1);colormap('gray');imagesc(im3);holdon ;-9精选文库cols1 = size(im1,2);fori = 1: size(des1,1)if(match(i) > 0)line(loc1(i,2) loc2(match(i),2)+cols1,.loc1(i,1) loc2(match(i),1),'Color','c');endendholdoff;num = sum(match > 0);fprintf('Found %d matches.n', num);3） sho

23、wkeys.m% showkeys(image, locs)% This function displays an image with SIFT keypoints overlayed.% Input parameters:% image: the file name for the image (grayscale)% locs: matrix in which each row gives a keypoint location (row,% column, scale, orientation)functionshowkeys(image, locs)disp('Drawing

24、 SIFT keypoints .');% Draw image with keypointsfigure('Position', 50 50 size(image,2) size(image,1);colormap('gray');imagesc(image);holdon ;imsize = size(image);fori = 1: size(locs,1)% Draw an arrow, each line transformed according to keypoint parameters.TransformLine(imsize, loc

25、s(i,:), 0.0, 0.0, 1.0, 0.0); TransformLine(imsize, locs(i,:), 0.85, 0.1, 1.0, 0.0); TransformLine(imsize, locs(i,:), 0.85, -0.1, 1.0, 0.0);endhold off ;% - Subroutine: TransformLine -% Draw the given line in the image, but first translate, rotate, and% scale according to the keypoint parameters.%-10

26、精选文库% Parameters:% Arrays:% imsize = rows columns of image% keypoint = subpixel_row subpixel_column scale orientation% Scalars:% x1, y1; begining of vector% x2, y2; ending of vectorfunctionTransformLine(imsize, keypoint, x1, y1, x2, y2)% Thescalingoftheunitlengtharrowissettoapproximatelytheradius% o

27、f the region used to compute the keypoint descriptor. len = 6 * keypoint(3);% Rotate the keypoints by 'ori' = keypoint(4)s = sin(keypoint(4);c = cos(keypoint(4);% Apply transformr1 = keypoint(1) - len * (c * y1 + s * x1);c1 = keypoint(2) + len * (- s * y1 + c * x1);r2 = keypoint(1) - len * (

28、c * y2 + s * x2);c2 = keypoint(2) + len * (- s * y2 + c * x2);line(c1 c2, r1 r2,'Color','c');4） sift.m% image, descriptors, locs = sift(imageFile)% This function reads an image and returns its SIFT keypoints.% Input parameters:% imageFile: the file name for the image.% Returned:% ima

29、ge: the image array in double format% descriptors: a K-by-128 matrix, where each row gives an invariant%descriptorforone oftheK keypoints. Thedescriptorisa vector% of 128 values normalized to unit length.% locs: K-by-4 matrix, in which each row has the 4 values for a% keypoint location (row, column,

30、 scale, orientation). The% orientation is in the range -PI, PI radians.% Credits: Thanks for initial version of this program to D. Alvaro and% J.J. Guerrero, Universidad de Zaragoza (modified by D. Lowe)-11精选文库functionimage, descriptors, locs = sift(imageFile)% Load imageimage = imread(imageFile);%

31、IfyouhavetheImageProcessingToolbox,youcan uncommentthefollowing% lines to allow input of color images, which will be converted to grayscale.% if isrgb(image)% image = rgb2gray(image);% endrows, cols = size(image);% Convert into PGM imagefile, readable by "keypoints" executablef = fopen('tmp.pgm','w');iff = -1error('Could not create file tmp.pgm.');endfprintf(f,'P5n%dn%dn255n', cols, rows);fwrite(f, image','uint8');fclose(f);% Call keypoints executable if