圖象匹配算法SIFT

1、Distinctive Image Features from Scale-Invariant KeypointsDavid G. Lowe這是一個(gè)很好的圖象匹配算法（SIFT），同時(shí)能處理亮度、平移、旋轉(zhuǎn)、尺度的變化，利用特征點(diǎn)來提取特征描述符，最后在特征描述符之間尋找匹配。該算法主要包括5個(gè)步驟：一、建立尺度空間，尋找特征點(diǎn)（Keypoint）（也許該叫關(guān)鍵點(diǎn)）二、剔除不穩(wěn)定（暫且這么叫吧）的特征點(diǎn)三、在特征點(diǎn)處提取特征描述符（Keypoint Descriptor）四、利用特征描述符尋找匹配點(diǎn)。五、計(jì)算變換參數(shù)。下面分別進(jìn)行介紹。一、 建立尺度空間，尋找特征點(diǎn)假設(shè)待匹配的兩副圖象分別為f

2、1(x,y)和f2(x,y)，下面我只講f1(x,y)的算法操作，因?yàn)閷?duì)f2(x,y)的操作完全相同。首先要建立尺度空間(Scale Space)，這里用f1(x,y)與不同的高斯核卷積來產(chǎn)生尺度空間。由于f1(x,y)與高斯核卷積之后會(huì)丟失掉f1(x,y)的一部分信息，因此這里先將f1(x,y)利用線性插值的方法放大一倍，計(jì)為F1(x,y)，即F1的大小是f1的兩倍。（為什么要放大，下面會(huì)有解釋）下面我用MATLAB寫一下他建立尺度空間的代碼，這樣更簡潔明了.F1 = imresize(f1,2,nearest);這個(gè)就是將原圖象放大2倍，用bilinear也可以g0 = fspecial(

3、gaussian,3 3,1.5);用來對(duì)放大的原圖象卷積的一個(gè)高斯核。F1 = conv2(F1,g0,same);卷積然后利用5個(gè)不同的高斯核對(duì)F1進(jìn)行卷積。g1 = fspecial(gaussian,3 3,1.23);g2 = fspecial(gaussian,3 3,1.55);g3 = fspecial(gaussian,3 3,1.95);g4 = fspecial(gaussian,3 3,2.45);g5 = fspecial(gaussian,3 3,3.09);這是5個(gè)高斯核函數(shù)，相鄰兩個(gè)的標(biāo)準(zhǔn)差正好是1.26倍，也就是。具體怎么得出來這些方差值，我也不知道啦.拉拉拉

4、拉拉拉拉拉拉拉拉拉拉拉拉拉拉拉拉拉拉拉拉拉拉拉拉拉拉拉G1 = F1;G2 = conv2(G1,g1,same);G3 = conv2(G2,g2,same);這里是否每次都應(yīng)該和G1卷積？有點(diǎn)糊涂。G4 = conv2(G3,g3,same);G5 = conv2(G4,g4,same);G6 = conv2(G5,g5,same);由此得到6個(gè)和F1大小一樣的高斯卷積圖象，也就是一個(gè)Octave.我不知道為什么文獻(xiàn)上只畫了5副，也許是漏畫，也許是他沒把G1 = F1畫進(jìn)去。然后相鄰兩個(gè)G相減得到D1 = G2 G1;D2 = G3 G2;D3 = G4 G3;D4 = G5 G4;D5

5、= G6 G5;總共5個(gè)Difference of Gaussian圖象。得到了D之后就可以尋找特征點(diǎn)。首先在D1，D2，D3中尋找，遍歷圖象D2，如果D2(X0,Y0)是D2(X,Y)在(X0,Y0)的3*3局部極大值（或極小值），而且也是D1(X0,Y0)、D3(X0,Y0)3*3領(lǐng)域的極大值（或極小值），而且D2(X0,Y0)的絕對(duì)值必須大于一閾值，作者給出的是0.0075，（圖象都先歸一化過了）那么該點(diǎn)(X0,Y0)就是特征點(diǎn)。也就是D2(X0,Y0)要大于（或小于）D2(X0-1,Y0-1)、D2(X0-1,Y0)、D2(X0-1,Y0+1)、D2(X0,Y0-1)、D2(X0,Y0

6、+1)、D2(X0+1,Y0-1)、D2(X0+1,Y0)、D2(X0+1,Y0+1)，而且同時(shí)要大于（或小于）D1(X0-1,Y0-1)、D1(X0-1,Y0)、D1(X0-1,Y0+1)、D1(X0,Y0-1)、D1(X0,Y0)、D1(X0,Y0+1)、D1(X0+1,Y0-1)、D1(X0+1,Y0)、D1(X0+1,Y0+1)以及D3(X0-1,Y0-1)、D3(X0-1,Y0)、D3(X0-1,Y0+1)、D3(X0,Y0-1)、D3(X0,Y0)、D3(X0,Y0+1)、D3(X0+1,Y0-1)、D3(X0+1,Y0)、D3(X0+1,Y0+1)，這里的大于（或小于）就是要么D

7、2(X0,Y0)是這26領(lǐng)域的極大值，或者是這26領(lǐng)域的極小值。假設(shè)(X0,Y0)是這么一個(gè)特征點(diǎn)（并且這個(gè)點(diǎn)是穩(wěn)定的），那么就要在G2的(X0,Y0)位置處提取特征描述符（特征描述符的提取在下面講）。如果這個(gè)點(diǎn)是不穩(wěn)定的，那么就舍去這個(gè)特征點(diǎn)（穩(wěn)定不穩(wěn)定也將在接下來的內(nèi)容里講）。找出在D2中的所有特征點(diǎn)，在G2上提取出所有的特征描述符。其次，在D2，D3，D4中，以及D3，D4，D5中按上面的方法尋找特征點(diǎn)，并分別在G3，G4中提取特征描述符。因?yàn)槭紫任覀兪窃贕2中提取，而G2是先經(jīng)過模糊了的，所以丟失了原圖象的一部分信息，因此這里我們先放大一倍，為的就是彌補(bǔ)一些丟失了的信息。（東岳：將原圖

8、像A，B（大小256*256）放大兩倍的原因，我認(rèn)為可能是這樣：一： 卷積后對(duì)原圖像會(huì)有信息丟失，放大兩倍，可以減少丟失。二： A，B到底哪個(gè)大，不一定，所以除了縮小，還要放大一定的倍數(shù)。三：如果不放大，我們得到的第一個(gè)Octave里，就只有256*256，203*203。大小的圖像， 只能從相當(dāng)于203*203大小的那張圖像中開始搜索，從而露掉了256*256那張圖像。）最后將F1縮小2倍，再從“拉拉拉拉拉拉”那里開始重復(fù)同樣的動(dòng)作，直到圖象大小小于32為止。這樣就具有尺度不變性。二、 剔除不穩(wěn)定點(diǎn)個(gè)人感覺這個(gè)剔除不穩(wěn)定點(diǎn)對(duì)結(jié)果的影響并不是很大，不做這一步也不是不是以，但既然有了，也是很大的

9、一個(gè)改進(jìn)。那就講一下。1， 在特征點(diǎn)處計(jì)算如果這個(gè)值的絕對(duì)值小于等于一閾值那么將被舍棄，這一閾值應(yīng)該比上面的0.0075稍大，取為0.008，（而不是那個(gè)0.03，因?yàn)?.03太大了），這樣就是去掉對(duì)比度比較低的一些點(diǎn)。2，取r = 10，滿足上面條件的特征點(diǎn)將被保留。不滿足上述的點(diǎn)表示：他有一個(gè)很大的主曲率，和一個(gè)很小和他垂直的曲率 Dxx = Dx + 1, y + Dx - 1, y - 2.0 * Dx, y;Dyy = Dx, y + 1 + Dx, y - 1 - 2.0 * Dx, y;Dxy = 0.25 * (Dx + 1, y + 1 - Dx + 1, y - 1) -(

10、Dx - 1, y + 1 - Dx - 1, y - 1); 3，如果這個(gè)向量(dx,dy)的任何一個(gè)大于0。5，那么說明該點(diǎn)不穩(wěn)定，利用插值法進(jìn)行矯正，再將該向量加到(x,y)中。如果小于0。5，那么不做任何變動(dòng)。三、 提取特征描述符上面提到過要在G1，G2，G3的特征點(diǎn)處提取特征描述符。這里就以某一個(gè)特征點(diǎn)(X0,Y0)為例，其他所有的都按同樣的方法處理。計(jì)算G在(X0,Y0)處的方向大小。按照剃度的方向來計(jì)算。這里的L、x、y改為G、X0、Y0，（比較懶，就直接從文章里貼了），按照這個(gè)方向，選取(X0,Y0)周圍16*16的一個(gè)正方形塊，這樣就具有旋轉(zhuǎn)不變性。16*16的矩形塊分成16

11、個(gè)4*4的子塊。如下圖所示，（下圖只給出8*8的矩形塊和4個(gè)4*4的小塊，不好意思呵呵）看到了吧，左圖有4個(gè)4*4的子塊（真正的應(yīng)該是16個(gè)4*4的子塊），然后我們對(duì)每個(gè)子塊處理。每個(gè)子塊有4*4=16個(gè)點(diǎn)，計(jì)算每個(gè)點(diǎn)的方向和幅度，方向公式在上面，幅度公式如下：嘿嘿，這樣得到16個(gè)方向和幅度值。然后把這16個(gè)方向投影到0，45，90，135，180，225，270，315這8個(gè)方向上，利用幅度作為權(quán)值。這樣一個(gè)4*4的子塊可以得到8個(gè)方向描述符，如上右圖所示，16個(gè)4*4的子塊可以得到128個(gè)方向描述符，這個(gè)1*128的向量就定義為特征描述符。最后將這個(gè)1*128的特征描述符歸一化，以使其對(duì)亮

12、度變化不敏感。假設(shè)圖象有N個(gè)特征點(diǎn)，那么就有N*128的特征描述符。四、 匹配我們對(duì)f1利用上面的方法進(jìn)行處理之后得到loc1和des1兩個(gè)矩陣，假設(shè)f1總共有N1個(gè)特征點(diǎn)（即f1在所有的尺度空間上，那么多不同尺度的圖象中共找到了N1個(gè)特征點(diǎn)），那么loc1大小為N1*4，des1大小為N1*128，loc1每一維的4個(gè)表示該特征點(diǎn)的坐標(biāo)(x,y)、在尺度空間上的尺度大小、方向，des1每一維的128個(gè)分量表示該特征點(diǎn)的特征描述符，loc1和des1一個(gè)個(gè)都對(duì)應(yīng)著。同樣的，對(duì)f2進(jìn)行同樣的處理，假設(shè)它總共有特征點(diǎn)數(shù)為N2，那么loc2和des2大小分別為N2*4和N2*128。下面來匹配。取d

13、es1中的一個(gè)1*128的特征描述符，去和des2中的N2個(gè)特征描述符分別計(jì)算誤差。每一個(gè)誤差的計(jì)算如下：error = 0;for i = 1 : 128error += sum(des1 des2).2);end這樣就得到了N2個(gè)誤差，計(jì)算這N2個(gè)誤差的最小值和次小值，分別為min和secmin，如果min < 0.75 * secmin，那么des1中的該點(diǎn)和des2中的產(chǎn)生min這個(gè)誤差的點(diǎn)相匹配，利用loc1和loc2中的坐標(biāo)，在這兩點(diǎn)直接連線，表示這兩點(diǎn)匹配。這里min < 0.75 * secmin表示的意思是：如果f1中有一個(gè)和f2中的一個(gè)很可靠的匹配，那么該誤差應(yīng)

14、該比較小，而且f1中的這個(gè)特征描述符和f2中其他特征描述符的匹配誤差就應(yīng)該比較大。比如：我們要從一堆人中找一個(gè)人，已知是要找一個(gè)女人，如果這堆人中只有一個(gè)女人，其他都是男人，那么我們可以很肯定的知道這個(gè)女的就是要找的（因?yàn)榕说恼`差較小，男人的誤差都比較大）；但是如果這堆人中有好幾個(gè)女的，那么我們隨便找一個(gè)女的就不敢肯定這個(gè)人是不是要找的那個(gè)，于是可靠性就得到懷疑。（因?yàn)楹脦讉€(gè)女人，有好幾個(gè)誤差都比較?。ê俸?，這個(gè)例子是不是很土？）上面的方法就和這個(gè)例子很相似。遍歷des1中的所有特征描述符，按同樣的方法和des2中的特征描述符去匹配，這樣我們就找到了所有的匹配點(diǎn)。具體的貼圖就不貼了，各位自己下程序下來運(yùn)行。五、 計(jì)算兩副圖象的變換參數(shù)。找到了很多的匹配點(diǎn)，但是其中肯定有一些是誤配點(diǎn)存在。如果兩副圖象存在平移、旋轉(zhuǎn)、尺度的變化，那么就需要計(jì)算一個(gè)變換矩陣，而計(jì)算這個(gè)矩陣只需要3對(duì)匹配點(diǎn)（是夠了吧？）就可以了，但是這3對(duì)匹配點(diǎn)必須足夠精確，否則計(jì)算出來的變換參數(shù)可能會(huì)有較大的誤差。于是作者使用Hough變換的方法來對(duì)上面得到的初始匹配點(diǎn)進(jìn)行聚類，以找出最佳的3對(duì)匹配點(diǎn)，計(jì)算參數(shù)?？偨Y(jié)：寫的亂七八糟的，希望大家諒解。其中有一些東西，為