SIFT算法分析

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

2、流程圖：精選文庫(kù)4 SIFT 算法詳細(xì)1）尺度空間的生成尺度空間理論目的是模擬圖像數(shù)據(jù)的多尺度特征。高斯卷積核是實(shí)現(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）是空間坐標(biāo)， 是尺度坐標(biāo)。 大小決定圖像的平滑程度，大尺度對(duì)應(yīng)圖像的概貌特征，小尺度對(duì)應(yīng)圖像的細(xì)節(jié)特征。大的 值對(duì)應(yīng)粗糙尺度 (低分辨率 )，反之，對(duì)應(yīng)精細(xì)尺度 (高分辨率 )。為了有效的在尺度空間檢測(cè)到穩(wěn)定的關(guān)鍵點(diǎ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算子計(jì)算簡(jiǎn)單，是尺度歸一化的LoG算子的近似。圖像金字塔的構(gòu)建：圖像金字塔共O組，每組有 S層，下一組的圖像由上一組圖像降采樣得到。圖1由兩組高斯尺度空間圖像示例金字塔的構(gòu)建，第二組的第一副圖像由第一組的第一副到最后一副圖像由一個(gè)因子2降采樣得到。圖 2 DoG算子的構(gòu)建：圖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精選文庫(kù)圖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) 空間極值點(diǎn)檢測(cè)為了尋找尺度空間的極值點(diǎn)， 每一個(gè)采樣點(diǎn)要和

5、它所有的相鄰點(diǎn)比較， 看其是否比它的圖像域和尺度域的相鄰點(diǎn)大或者小。如圖 3所示，中間的檢測(cè)點(diǎn)和它同尺度的 8個(gè)相鄰點(diǎn)和上下相鄰尺度對(duì)應(yīng)的 9× 2個(gè)點(diǎn)共 26個(gè)點(diǎn)比較，以確保在尺度空間和二維圖像空間都檢測(cè)到極值點(diǎn)。 一個(gè)點(diǎn)如果在 DOG尺度空間本層以及上下兩層的 26個(gè)領(lǐng)域中是最大或最小值時(shí)， 就認(rèn)為該點(diǎn)是圖像在該尺度下的一個(gè)特征點(diǎn) ,如圖 1所示。圖 3 DoG 尺度空間局部極值檢測(cè)3) 構(gòu)建尺度空間需確定的參數(shù)尺度空間坐標(biāo)Ooctave坐標(biāo)S sub-level 坐標(biāo)和 O、 S的關(guān)系(o,s)0 2o s / S ， oomin0,.,O1, s0,., S1-3精選文庫(kù)其中

6、0 是基準(zhǔn)層尺度。 ooctave坐標(biāo)， s sub-level 坐標(biāo)。注： octaves 的索引可能是負(fù)的。第一組索引常常設(shè)為 0或者 -1,當(dāng)設(shè)為 -1的時(shí)候，圖像在計(jì)算高斯尺度空間前先擴(kuò)大一倍。空間坐標(biāo) x是組 octave的函數(shù)，設(shè) x0 是0組的空間坐標(biāo)，則x 2o x0 , o, x0 0,., N 0 1 0,., M 0 1如果 M 0 , N0 是基礎(chǔ)組 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、插值擴(kuò)大一倍（對(duì)于擴(kuò)大的圖像n1 ）。4）精確確定極值點(diǎn)位置通過(guò)擬和三維二次函數(shù)以精確確定關(guān)鍵點(diǎn)的位置和尺度（達(dá)到亞像素精度），同時(shí)去除低對(duì)比度的關(guān)鍵點(diǎn)和不穩(wěn)定的邊緣響應(yīng)點(diǎn) (因?yàn)?DoG算子會(huì)產(chǎn)生較強(qiáng)的邊緣響應(yīng) )，以增強(qiáng)匹配穩(wěn)定性、提高抗噪聲能力。空間尺度函數(shù) D ( x, y,)D( x, y, ) D x0 , y0 ,D TX1 X T2 D2 X ）泰勒展開(kāi)式如下 :X 02X 0D ( x, y, ) D x, y,D Tx1 xT2 Dxx2x2?2 D 1D對(duì)上式求導(dǎo) ,并令其為 0,得到精確的位置x?, x2xx在已經(jīng)檢測(cè)到的特征點(diǎn)中 ,要去掉低對(duì)比度的特征點(diǎn)和不穩(wěn)定的邊緣

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

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

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

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

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

13、當(dāng)兩幅圖像的 SIFT特征向量生成后，下一步我們采用關(guān)鍵點(diǎn)特征向量的歐式距離來(lái)作為兩幅圖像中關(guān)鍵點(diǎn)的相似性判定度量。取圖像1中的某個(gè)關(guān)鍵點(diǎn)，并找出其與圖像 2中歐式距離最近的前兩個(gè)關(guān)鍵點(diǎn)，在這兩個(gè)關(guān)鍵點(diǎn)中，如果最近的距離除以次近的距離少于某個(gè)比例閾值，則接受這一對(duì)匹配點(diǎn)。 降低這個(gè)比例閾值，SIFT匹配點(diǎn)數(shù)目會(huì)減少， 但更加穩(wěn)定。 為了排除因?yàn)閳D像遮擋和背景混亂而產(chǎn)生的無(wú)匹配關(guān)系的關(guān)鍵點(diǎn), 用比較最近鄰距離與次近鄰距離的方法, 距離比率 ratio 小于某個(gè)閾值的認(rèn)為是正確匹配。 因?yàn)閷?duì)于錯(cuò)誤匹配 , 由于特征空間的高維性 , 相似的距離可能有大量其他的錯(cuò)誤匹配 , 從而它的 ratio 值比

14、較高。推薦 ratio 的閾值為 0.8 。5 仿真結(jié)果分析將文件加入 matlab 目錄后，在主程序中有兩種操作：op1：尋找圖像中的 Sift 特征：image,discrips,locs=sift('scene.pgm');Finding keypoints.1021 keypoints found.>> showkeys(image,locs); Drawing SIFT keypoints .5010015020025030035050100150200250300350400450500op2：對(duì)兩幅圖中的 SIFT特征進(jìn)行匹配：match('s

15、cene.pgm','book.pgm');Finding keypoints.1021 keypoints found.Finding keypoints.882 keypoints found.Found 98 matches.-7精選文庫(kù)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精選文庫(kù)% 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精選文庫(kù)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、精選文庫(kù)% 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精選文庫(kù)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