SIFT算法分析

1、SIFT 算法分析1 SIFT 主要思想SIFT算法是一種提取局部特征的算法，在尺度空間尋找極值點，提取位置，尺度，旋轉不變量。2 SIFT 算法的主要特點：a) SIFT特征是圖像的局部特征，其對旋轉、尺度縮放、亮度變化保持不變性，對視角變化、仿射變換、噪聲也保持一定程度的穩(wěn)定性。b) 獨特性 (Distinctiveness)好，信息量豐富，適用于在海量特征數(shù)據(jù)庫中進行快速、準確的匹配。c) 多量性，即使少數(shù)的幾個物體也可以產生大量 SIFT特征向量。d) 高速性，經優(yōu)化的 SIFT匹配算法甚至可以達到實時的要求。e) 可擴展性，可以很方便的與其他形式的特征向量進行聯(lián)合。3 SIFT 算法

2、流程圖：精選文庫4 SIFT 算法詳細1）尺度空間的生成尺度空間理論目的是模擬圖像數(shù)據(jù)的多尺度特征。高斯卷積核是實現(xiàn)尺度變換的唯一線性核， 于是一副二維圖像的尺度空間定義為：L( x, y, ) G( x, y, ) I (x, y)其中 G ( x, y,) 是尺度可變高斯函數(shù)， G ( x, y, )12 e (x 2 y2 ) / 2 22（ x，y）是空間坐標， 是尺度坐標。 大小決定圖像的平滑程度，大尺度對應圖像的概貌特征，小尺度對應圖像的細節(jié)特征。大的 值對應粗糙尺度 (低分辨率 )，反之，對應精細尺度 (高分辨率 )。為了有效的在尺度空間檢測到穩(wěn)定的關鍵點，提出了高斯差分尺度空間

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) 構建尺度空間需確定的參數(shù)尺度空間坐標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的時候，圖像在計算高斯尺度空間前先擴大一倍?？臻g坐標 x是組 octave的函數(shù)，設 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使用了如下的參數(shù)：n 0.5, 0 1.6 21/ S , omin1,S 3在組 o=-1，圖像用雙線性

7、插值擴大一倍（對于擴大的圖像n1 ）。4）精確確定極值點位置通過擬和三維二次函數(shù)以精確確定關鍵點的位置和尺度（達到亞像素精度），同時去除低對比度的關鍵點和不穩(wěn)定的邊緣響應點 (因為 DoG算子會產生較強的邊緣響應 )，以增強匹配穩(wěn)定性、提高抗噪聲能力?？臻g尺度函數(shù) 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在已經檢測到的特征點中 ,要去掉低對比度的特征點和不穩(wěn)定的邊緣

8、響應點。去除低對比度的點：把公式 (4)代入公式 (3) ，只取前兩項可得：1D T?D ( x?) D x, y,x2 x若 D x? 0.03，該特征點就保留下來，否則丟棄。邊緣響應的去除一個定義不好的高斯差分算子的極值在橫跨邊緣的地方有較大的主曲率，而-4精選文庫在垂直邊緣的方向有較小的主曲率。主曲率通過一個2x2 的Hessian矩陣 H求出 :HDxxDxyDxyDyy導數(shù)由采樣點相鄰差估計得到。D的主曲率和 H的特征值成正比，令為最大特征值，為最小的特征值，則令，則：2r 的增大而增大，因此，(r + 1) /r 的值在兩個特征值相等的時候最小，隨著為了檢測主曲率是否在某域值 r

9、下，只需檢測在Lowe的文章中，取 r 10。5）關鍵點方向分配利用關鍵點鄰域像素的梯度方向分布特性為每個關鍵點指定方向參數(shù)，使算子具備旋轉不變性。式(5) 為(x,y) 處梯度的模值和方向公式。其中 L所用的尺度為每個關鍵點各自所在的尺度。在實際計算時， 我們在以關鍵點為中心的鄰域窗口內采樣， 并用直方圖統(tǒng)計鄰域像素的梯度方向。 梯度直方圖的范圍是 0 360度，其中每 10度一個柱， 總共 36 個柱。直方圖的峰值則代表了該關鍵點處鄰域梯度的主方向， 即作為該關鍵點的方向。圖 4是采用 7個柱時使用梯度直方圖為關鍵點確定主方向的示例。（ 窗口尺寸采用 Lowe推薦的 1.5 ×

10、1.5 ）-5精選文庫圖 4 由梯度方向直方圖確定主梯度方向在梯度方向直方圖中，當存在另一個相當于主峰值 80%能量的峰值時，則將這個方向認為是該關鍵點的輔方向。 一個關鍵點可能會被指定具有多個方向 （一個主方向，一個以上輔方向），這可以增強匹配的魯棒性 53 。至此，圖像的關鍵點已檢測完畢， 每個關鍵點有三個信息： 位置、所處尺度、方向。由此可以確定一個 SIFT特征區(qū)域（在實驗章節(jié)用橢圓或箭頭表示）。6）特征點描述子生成首先將坐標軸旋轉為關鍵點的方向，以確保旋轉不變性。圖 5 由關鍵點鄰域梯度信息生成特征向量接下來以關鍵點為中心取 8×8的窗口。圖 5-4 左部分的中央黑點為當前

11、關鍵點的位置，每個小格代表關鍵點鄰域所在尺度空間 ( 和關鍵點是否為一個尺度空間 ) 的一個像素，利用公式（ 5）求得每個像素 i , j 的梯度幅值 mi , j 與梯度方向 i , j ，箭頭方向代表該像素的梯度方向， 箭頭長度代表梯度模值， 然后用高斯窗口對其進行加權運算 , 每個像素對應一個向量，長度為 G ' ,i , j mi , j ， G ' , i, j 為該像素點的高斯權值， 方向為i , j ， 圖中藍色的圈代表高斯加權的范圍（越靠近關鍵點的像素梯度方向信息貢獻越大）。高斯參數(shù)取3倍特征點所在的尺度。然后在每 4×4的小塊上計算 8個方向的梯度方

12、向直方圖，繪制每個梯度方向的累加值，即可形成一個種子點， 如圖 5右部分所示。 此圖中一個關鍵點由 2×2共4個種子點組成，每個種子點有8個方向向量信息。這種鄰域方向性信息聯(lián)合的思想增強了算法抗噪聲的能力， 同時對于含有定位誤差的特征匹配也提供了較好的容錯性。實際計算過程中， 為了增強匹配的穩(wěn)健性， 對每個關鍵點使用 4× 4共 16個種子點來描述，這樣對于一個關鍵點就可以產生 128個數(shù)據(jù)，即最終形成 128維的SIFT特征向量。此時 SIFT特征向量已經去除了尺度變化、 旋轉等幾何變形因素的影響，再繼續(xù)將特征向量的長度歸一化，則可以進一步去除光照變化的影響。-6精選文庫

13、當兩幅圖像的 SIFT特征向量生成后，下一步我們采用關鍵點特征向量的歐式距離來作為兩幅圖像中關鍵點的相似性判定度量。取圖像1中的某個關鍵點，并找出其與圖像 2中歐式距離最近的前兩個關鍵點，在這兩個關鍵點中，如果最近的距離除以次近的距離少于某個比例閾值，則接受這一對匹配點。 降低這個比例閾值，SIFT匹配點數(shù)目會減少， 但更加穩(wěn)定。 為了排除因為圖像遮擋和背景混亂而產生的無匹配關系的關鍵點, 用比較最近鄰距離與次近鄰距離的方法, 距離比率 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