SIFT算法分析

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

2、一特征向愛4 SIFT算法詳細(xì)1)尺度空間的生成尺度空間理論目的是模擬圖像數(shù)據(jù)的多尺度特征。高斯卷積核是實(shí)現(xiàn)尺度變換的唯一線性核，于是一副二維圖像的尺度空間定義為：L(x,y, ) G(x, y, ) I (x, y)2-2c其中G(x,y,)是尺度可變圖斯函數(shù)，G(x, y,) 2e ( y)/22(x, y)是空間坐標(biāo)，是尺度坐標(biāo)。大小決定圖像的平滑程度，大尺度對(duì)應(yīng)圖像的概貌特征，小尺度對(duì)應(yīng)圖像的細(xì)節(jié)特征。大的值對(duì)應(yīng)粗糙尺度(低分辨率)，反之，對(duì)應(yīng)精細(xì)尺度(高分辨率)。為了有效的在尺度空間檢測到穩(wěn)定的關(guān)鍵點(diǎn)，提出了高斯差分尺度空間(DOG scale-space。利用不同尺度的高斯差分核與

3、圖像卷積生成。D(x,y, ) (G(x, y,k ) G(x, y, ) I(x,y) L(x, y,k ) L(x, y,)DOGT子計(jì)算簡單，是尺度歸一化的LoG»子的近似。圖像金字塔的構(gòu)建：圖像金字塔共 C組，每組有S層，下一組的圖像由上組圖像降采樣得到。圖1由兩組高斯尺度空間圖像示例金字塔的構(gòu)建，第二組的第一副圖像由第一組的第一副到最后一副圖像由一個(gè)因子 2降采樣得到。圖2 DoGf子的構(gòu)建：Octave 萼圖 1 Two octaves of a Gaussian scale-space image pyramid with s =2 intervals. The fir

4、st image in the second octave is created by down sampling to last image in the previousOctave 1DoG Octave 1圖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)檢測為了尋找尺度空間的極值點(diǎn)，每一個(gè)采樣點(diǎn)要和它所有的相鄰點(diǎn)比較

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

6、es的 索引可能是負(fù)的。第一組索引常常設(shè)為 0或者-1,當(dāng)設(shè)為-1的時(shí)候，圖像在計(jì)算高 斯尺度空間前先擴(kuò)大一倍?？臻g坐標(biāo)x是組octave的函數(shù)，設(shè)x0是0組的空間坐標(biāo)，則x 2°X0,o ,Xo 0,No 10,Mo 1如果Mo,No是基礎(chǔ)組o=0的分辨率，則其他組的分辨率由下式獲得：NoNo,MoMo注：在Lowe的文章中，Lowe#用了如下的參數(shù):1/S_n 0.5, 0 1.6 2 ,Omin1,S 3在組o=-1,圖像用雙線性插值擴(kuò)大一倍（對(duì)于擴(kuò)大的圖像4）精確確定極值點(diǎn)位置通過擬和三維二次函數(shù)以精確確定關(guān)鍵點(diǎn)的位置和尺度（達(dá)到亞像素精度）， 同時(shí)去除低對(duì)比度的關(guān)鍵點(diǎn)和不穩(wěn)

7、定的邊緣響應(yīng)點(diǎn) （因?yàn)镈oG算子會(huì)產(chǎn)生較強(qiáng)的 邊緣響應(yīng)），以增強(qiáng)匹配穩(wěn)定性、提高抗噪聲能力?？臻g尺度函數(shù)D（x, y,）泰勒展開式如下：T 2D-x xDT 7D(x, y, ) D Xo, y0, XX oDTD(x, y, ) D x,y, xx對(duì)上式求導(dǎo)，并令其為0曲到精確的位置,?2D 1 D在已經(jīng)檢測到的特征點(diǎn)中，要去掉低對(duì)比度的特征點(diǎn)和不穩(wěn)定的邊緣響應(yīng)點(diǎn)。去除低對(duì)比度的點(diǎn)：把公式（4）代入公式（3）,只取前兩項(xiàng)可得：八1 DT cD（X） D x, y,W2 x若D ? 0.03,該特征點(diǎn)就保留下來，否則丟棄邊緣響應(yīng)的去除一個(gè)定義不好的高斯差分算子的極值在橫跨邊緣的地方有較大的主曲

8、率，而在垂直邊緣的方向有較小的主曲率。主曲率通過一個(gè) 2x2的Hessia庶巨陣H求出：DxxDxyDxyDyy導(dǎo)數(shù)由采樣點(diǎn)相鄰差估計(jì)得到D的主曲率和H的特征值成正比，令 為最大特征值，為最小的特征值,111 Hi = Dit += c + 氏Det(H) D啦。g (Dry 產(chǎn)=rt J.令 ，則：TY(H產(chǎn)=(a + J產(chǎn)=(*3 +戶(=(+1產(chǎn)Det(H) al3廠房r(r + 1)2/r的值在兩個(gè)特征值相等的時(shí)候最小，隨著r的增大而增大，因此， 為了檢測主曲率是否在某域值r下，只需檢測D(H)2(+ 1)2Det|H) V r在Lowe的文章中，取r=10。5)關(guān)鍵點(diǎn)方向分配利用關(guān)鍵

9、點(diǎn)鄰域像素的梯度方向分布特性為每個(gè)關(guān)鍵點(diǎn)指定方向參數(shù)，使算 子具備旋轉(zhuǎn)不變性。加(2)= J(£(jc + 14) £(H TM/+ (£-J +1) - 1)產(chǎn)/工/)=atan2(£(x,y + 1)-L(xfy£(x-l,>)式(5)為(x,y)處梯度的模值和方向公式。其中L所用的尺度為每個(gè)關(guān)鍵點(diǎn)各自所 在的尺度。在實(shí)際計(jì)算時(shí)，我們?cè)谝躁P(guān)鍵點(diǎn)為中心的鄰域窗口內(nèi)采樣，并用直方圖統(tǒng)計(jì)鄰域像素的梯度方向。梯度直方圖的范圍是0360度，其中每10度一個(gè)柱，總共36 個(gè)柱。直方圖的峰值則代表了該關(guān)鍵點(diǎn)處鄰域梯度的主方向，即作為該關(guān)鍵點(diǎn)的方向。

10、圖4是采用7個(gè)柱時(shí)使用梯度直方圖為關(guān)鍵點(diǎn)確定主方向的示例。( 窗口 尺寸采用Lowe隹薦的0- X 0-)圖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)已檢測完畢，每個(gè)關(guān)鍵點(diǎn)有三個(gè)信息：位置、所處尺度、 方向。由此可以確定一個(gè)SIF%征區(qū)域（在實(shí)驗(yàn)章節(jié)用橢圓或箭頭表示）。6）特征點(diǎn)描述子生成首先將坐標(biāo)軸旋轉(zhuǎn)為關(guān)鍵點(diǎn)的方向，以確保旋轉(zhuǎn)不變性穎域嚎表方司關(guān)鋌應(yīng)號(hào)征向量圖5由關(guān)鍵點(diǎn)鄰域梯度信

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

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

13、鍵點(diǎn)特征向量的歐式距離來作為兩幅圖像中關(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è)比例閾值，SIFTS配點(diǎn)數(shù)目會(huì)減少，但更加穩(wěn)定。為了排除因?yàn)閳D像遮擋和背景混亂而產(chǎn)生的無匹配關(guān)系的關(guān)鍵點(diǎn) ,用比較最近鄰距離與次近鄰距離的方法,距離比率ratio小于某個(gè)閾值的認(rèn)為是正確匹配。因?yàn)閷?duì)于錯(cuò)誤匹配，由于特征空間的高維 性，相似的距離可能有大量其他的錯(cuò)誤匹配，從而它的ratio值比較高。推薦ratio的 閾值為。5 仿真結(jié)果分析將文件加入matlab 目錄后，

14、在主程序中有兩種操作：op1:尋找圖像中的Sift特征：image,discrips,locs=sift('');Finding keypoints.1021 keypoints found.>> showkeys(image,locs);Drawing SIFT keypoints .5010015020025030035050100150200250300350400450500op2:對(duì)兩幅圖中的SIFT!征進(jìn)行匹配:match。',"）；Finding keypoints.1021 keypoints found.Finding keypo

15、ints.882 keypoints found.Found 98 matches.501001502002506 代碼1)% im = appendimages(image1, image2)% Return a new image that appends the two images side-by-side.function im = appendimages(image1, image2)% Select the image with the fewest rows and fill in enough empty rows% to make it the same height a

16、s 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-side.im = image1 image2;2)% num = match(image1, image2)% This function reads two images, finds their SIFT features, and% displays lines

17、 connecting the matched keypoints. A match is accepted% only if its distance is less than distRatio times the distance to the% second closest match.% It returns the number of matches displayed.% Example: match('','');function num = match(image1, image2)% Find SIFT keypoints for each

18、imageim1, des1, loc1 = sift(image1);im2, des2, loc2 = sift(image2);% For efficiency in Matlab, it is cheaper to compute dot products between% unit vectors rather than Euclidean distances. Note that the ratio of% angles (acos of dot products of unit vectors) is a close approximation% to the ratio of

19、Euclidean distances for small angles.% distRatio: Only keep matches in which the ratio of vector angles from the% nearest to second nearest neighbor is less than distRatio.distRatio = ;% For each descriptor in the first image, select its match to second image.des2t = des2'% Precompute matrix tra

20、nsposefor i = 1 : size(des1,1)dotprods = des1(i,:) * des2t;% Computes vector of dot productsvals,indx = sort(acos(dotprods); % Take inverse cosine and sort results% Check if nearest neighbor has angle less than distRatio times 2nd.if (vals(1) < distRatio * vals(2)match(i) = indx(1);elsematch(i) =

21、 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(im3,1);colormap( 'gray');imagesc(im3);hold on;cols1 = size(im1,2);for i = 1: size(des1,1

22、)if (match(i) > 0)line(loc1(i,2) loc2(match(i),2)+cols1, .loc1(i,1) loc2(match(i),1), 'Color', 'c');endendhold off;num = sum(match > 0);fprintf( 'Found %d matches.n' , num);3)% showkeys(image, locs)% This function displays an image with SIFT keypoints overlayed.% Input

23、parameters:% image: the file name for the image (grayscale)% locs: matrix in which each row gives a keypoint location (row,%column, scale, orientation)function showkeys(image, locs)disp('Drawing SIFT keypoints .' );% Draw image with keypointsfigure( 'Position' , 50 50 size(image,2) s

24、ize(image,1);colormap( 'gray');imagesc(image);hold on;imsize = size(image);for i = 1: size(locs,1)% Draw an arrow, each line transformed according to keypoint parameters.TransformLine(imsize, locs(i,:), , , , ;TransformLine(imsize, locs(i,:), , , , ;TransformLine(imsize, locs(i,:), , , , ;en

25、d hold off;% Subroutine: TransformLine % Draw the given line in the image, but first translate, rotate, and% scale according to the keypoint parameters.% % Parameters:% Arrays:% imsize = rows columns of image% keypoint = subpixel_row subpixel_column scale orientation% Scalars:%x1, y1; begining of ve

26、ctor%x2, y2; ending of vectorfunction TransformLine(imsize, keypoint, x1, y1, x2, y2)% The scaling of the unit length arrow is set to approximately the radius% of the region used to compute the keypoint descriptor.len = 6 * keypoint(3);% Rotate the keypoints by 'ori' = keypoint(4)s = sin(key

27、point(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 * (c * y2 + s * x2);c2 = keypoint(2) + len * (- s * y2 + c * x2);line(c1 c2, r1 r2, 'Color' , 'c');4)% image, descriptors, locs

28、 = sift(imageFile)% This function reads an image and returns its SIFT keypoints.% Input parameters:% imageFile: the file name for the image.%Returned:% image: the image array in double format% descriptors: a K-by-128 matrix, where each row gives an invariant%descriptor for one of the K keypoints. Th

29、e descriptor is a 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, scale, orientation). The%orientation is in the range -PI, PI radians.% Credits: Thanks for initial version of this program to D. Alvaro and

30、%. Guerrero, Universidad de Zaragoza (modified by D. Lowe)function image, descriptors, locs = sift(imageFile)% Load imageimage = imread(imageFile);% If you have the Image Processing Toolbox, you can uncomment the following% lines to allow input of color images, which will be converted to grayscale.%

31、 if isrgb(image)% image = rgb2gray(image);% endrows, cols = size(image);% Convert into PGM imagefile, readable by "keypoints" executable f = fopen( '', 'w' );if f = -1error( 'Could not create file .' );endfprintf(f, 'P5n%dn%dn255n' , cols, rows);fwrite(f, image', 'uint8' );fclose(f);% Call keypoints executab