基于仿射變換的局部特征匹配算法

戚海想（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065)

基于仿射變換的局部特征匹配算法

戚海想
（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065)

0　引言

圖像匹配是計(jì)算機(jī)視覺和圖像處理中一項(xiàng)非常重要的研究?jī)?nèi)容，在目標(biāo)跟蹤、模式識(shí)別、遙感圖像和醫(yī)學(xué)圖像等領(lǐng)域中有非常廣泛的應(yīng)用。發(fā)展至今，圖像匹配不斷取得顯著的研究成果，已經(jīng)有很多經(jīng)典的圖像匹配算法，例如SIFT[1]，SURF[2]，Harris[3]，MSER[4]，ASIFT[5]等。該類匹配方法首先提取兩幅待匹配圖像中的特征點(diǎn)，這些特征點(diǎn)用其空間結(jié)構(gòu)關(guān)系進(jìn)行描述，然后通過這種相似的空間結(jié)構(gòu)關(guān)系找到匹配特征點(diǎn)對(duì)。其中SIFT算法應(yīng)用最廣泛，該匹配方法取得的特征點(diǎn)對(duì)于尺度、旋轉(zhuǎn)和焦距變化具有良好的適應(yīng)性，對(duì)光照、噪聲干擾具有很強(qiáng)的魯棒性。然而該算法在匹配點(diǎn)對(duì)數(shù)量和運(yùn)算的實(shí)時(shí)性方面有一定的局限性。在本文中，提出一種改進(jìn)的基于仿射變換的局部特征匹配算法，該算法利用Lowe在SIFT算法中提出的128維描述子對(duì)特征點(diǎn)進(jìn)行描述，在特征匹配時(shí)將一幅圖片劃分成很多的小區(qū)域塊，每個(gè)小區(qū)域塊都具有不同的仿射性質(zhì)，在小區(qū)域塊中選出符合一定條件的三點(diǎn)對(duì)計(jì)算仿射變換矩陣，參考圖像上該區(qū)域內(nèi)的每個(gè)特征點(diǎn)利用仿射變換矩陣映射到測(cè)試圖像中，然后在仿射點(diǎn)鄰域進(jìn)行局部匹配，實(shí)驗(yàn)證明改進(jìn)后的算法能夠增加匹配點(diǎn)對(duì)數(shù)量，同時(shí)也能保持較高的匹配精度。

1　SIFT算法

SIFT算法是經(jīng)典的圖像匹配算法，主要包括以下處理過程。

1.1極值點(diǎn)檢測(cè)

一個(gè)二維圖像在不同尺度下的尺度空間可以用高斯函數(shù)與圖像的卷積表示：

σ為高斯函數(shù)的標(biāo)準(zhǔn)差，*為卷積符號(hào)，I（x，y）表示圖像。

尺度空間的局部空間上的最大值或最小值具有很好的穩(wěn)定性，利用LOG算子檢測(cè)極值點(diǎn)，DOG算子是歸一化的LOG算子的近似和簡(jiǎn)化，通過DOG算子檢測(cè)極值點(diǎn)將大大減小時(shí)間復(fù)雜度。DOG算子的表示如下：

D（x，y，σ）=（G（x，y，kσ）-G（x，y，σ））*I（x，y）

=L（x，y，kσ）-L（x，y，σ）（3）

在檢測(cè)極值點(diǎn)時(shí)，需要將其與同一尺度相鄰的8個(gè)像素，以及上下兩個(gè)相鄰尺度相同位置上的3×3個(gè)像素，共26個(gè)像素進(jìn)行比較，從而檢測(cè)出局部極值點(diǎn)，尺度空間中檢測(cè)到的極值點(diǎn)具有尺度不變性。在已經(jīng)檢測(cè)到的極值點(diǎn)去除一些不穩(wěn)定的點(diǎn)，即低對(duì)比度極值點(diǎn)和不滿足一定條件的邊緣響應(yīng)點(diǎn)。

1.2計(jì)算特征點(diǎn)方向

利用特征點(diǎn)鄰域內(nèi)像素點(diǎn)的梯度模值和梯度方向，最終尋找到特征點(diǎn)的主方向。梯度模值和梯度方向計(jì)算公式如下：

用直方圖統(tǒng)計(jì)特征點(diǎn)鄰域內(nèi)像素點(diǎn)的梯度方向，方向直方圖的范圍為0～360度，每10度一柱，共36柱，越遠(yuǎn)離特征點(diǎn)的像素對(duì)其貢獻(xiàn)越小，利用像素點(diǎn)的梯度幅值乘以高斯下降函數(shù)，最終生成梯度直方圖。直方圖的峰值代表該特征點(diǎn)的主方向。

1.3計(jì)算特征點(diǎn)描述子

每個(gè)特征點(diǎn)有三個(gè)信息：位置，尺度和方向，由此可以確定一個(gè)特征區(qū)域。將特征點(diǎn)的鄰域窗口分成4× 4的小方塊，在每個(gè)小方塊中形成梯度方向直方圖，每45度一柱，共有8柱，這樣就可以形成一個(gè)128維的特征描述向量。

1.4特征匹配

求參考圖像中的每個(gè)特征點(diǎn)在測(cè)試圖像的特征點(diǎn)集中最近與次近的特征點(diǎn)；若最近與次近的比率小于某個(gè)給定閾值，則認(rèn)為正確匹配，否則不匹配；這里的最近與次近定義為特征點(diǎn)的描述符向量的歐氏距離。

2　LMA算法

2.1三點(diǎn)對(duì)的選取

在三個(gè)特征點(diǎn)對(duì)計(jì)算仿射變換矩陣時(shí)，需要判斷三點(diǎn)對(duì)是否能夠計(jì)算出比較準(zhǔn)確的仿射變換矩陣。三個(gè)特征點(diǎn)形成的三角形不能太大，也不能太小和太扁，三角形太大使局部性匹配得不到很好的提現(xiàn)；太小使得三個(gè)點(diǎn)的坐標(biāo)非常相近，可以近似看成一個(gè)點(diǎn)，三角形太扁可以近似看成三點(diǎn)共線，這兩種情況都會(huì)導(dǎo)致鄰域上的特征點(diǎn)不能利用該仿射變換矩陣準(zhǔn)確找到其匹配特征點(diǎn)。基于以上情況，需要存儲(chǔ)參考圖像上任意兩個(gè)特征點(diǎn)之間的距離信息，使三個(gè)特征點(diǎn)之間的距離既不能太遠(yuǎn)又不能太近。設(shè)任意兩個(gè)特征點(diǎn)pi，pj；其歐氏距離如下：

（xi，yi）代表特征點(diǎn)pi的坐標(biāo)，（xj，yj）代表特征點(diǎn) pj的坐標(biāo)。如果pi≠pj并且 Dl

設(shè)任意三個(gè)點(diǎn)pi，pj，pk，如果它們是三點(diǎn)對(duì)在同一圖片上的三個(gè)特征點(diǎn)，則它們必須是不共線的。

并且，這三個(gè)特征點(diǎn)形成的三角形區(qū)域不能太扁平，因此三角形頂點(diǎn)之間必須滿足公式（8），在公式（8）中，T1為某一給定閾值。

2.2計(jì)算仿射變換矩陣

平面圖像上的仿射變換是一種二維坐標(biāo)到二維坐標(biāo)上的線性變換，能夠保持二維圖形的平直性和平行性，仿射變換包含一系列的原子變換，包括平移、放縮、旋轉(zhuǎn)等。仿射變換的表達(dá)式可以表示為：

（x，y）代表參考圖像上特征點(diǎn)的坐標(biāo)，（x'，y'）代表測(cè)試圖像上特征點(diǎn)的坐標(biāo)，表示放縮和旋轉(zhuǎn)，表示平移。

公式（9）也可以表示成以下形式：

最終表示為如下形式以求出仿射變換矩陣的6個(gè)參數(shù)：

2.3局部區(qū)域內(nèi)尋找匹配特征點(diǎn)

在參考圖像上，對(duì)于已經(jīng)成功找到其匹配特征點(diǎn)，并且滿足2.1所述的三點(diǎn)對(duì)求取仿射變換矩陣條件的三個(gè)特征點(diǎn)，要在其鄰域內(nèi)尋找未匹配的特征點(diǎn)。每在鄰域內(nèi)找到一個(gè)未匹配的特征點(diǎn)k，利用相應(yīng)的仿射變換矩陣計(jì)算特征點(diǎn)k映射在測(cè)試圖像上的點(diǎn)坐標(biāo)：

其中（kx，ky）為特征點(diǎn)k的坐標(biāo)，（kx'，ky'）為映射點(diǎn)的坐標(biāo)。

在測(cè)試圖像上，以映射點(diǎn)（kx'，ky'）為中心，T2為半徑的圓形區(qū)域內(nèi)尋找特征點(diǎn)，T2為某一給定閾值。將鄰域內(nèi)找到的所有特征點(diǎn)生成KD-Tree，利用SIFT的匹配策略找到特征點(diǎn)k的匹配特征點(diǎn)。

2.4LMA算法處理步驟

參考圖像上，特征點(diǎn)的集合為R，任意一特征點(diǎn)ri∈R，0

（1）在參考圖像上，訪問集合R中的一個(gè)特征點(diǎn)，若該特征點(diǎn)已經(jīng)成功匹配，則繼續(xù)訪問R中的下一個(gè)特征點(diǎn)，直到找到一個(gè)未匹配的特征點(diǎn)p。

（2）將測(cè)試圖像上的所有特征點(diǎn)生成KD-Tree，利用SIFT的特征點(diǎn)匹配策略尋找該特征點(diǎn)的匹配點(diǎn)。若未找到匹配點(diǎn)，則轉(zhuǎn)到步驟（1），若找到匹配點(diǎn)，將該匹配點(diǎn)對(duì)作為三點(diǎn)對(duì)的第一對(duì)，然后尋找另外兩對(duì)匹配點(diǎn)對(duì)，如果mark集合（mark集合中存有未作為三點(diǎn)對(duì)用來計(jì)算仿射變換矩陣的匹配點(diǎn)對(duì)）中的匹配點(diǎn)對(duì)數(shù)量少于2個(gè)，則轉(zhuǎn)至步驟（4）。

（3）在已經(jīng)成功匹配但是未形成三點(diǎn)對(duì)的mark集合中，尋找滿足三點(diǎn)對(duì)選取條件的2對(duì)匹配點(diǎn)對(duì) ，若成功找到，則將這2對(duì)匹配點(diǎn)對(duì)從mark集合中刪除，若最終未找到，則轉(zhuǎn)至步驟（4），否則轉(zhuǎn)至步驟（5）。

（4）順序訪問集合R中在步驟（1）剩下的未訪問且未找到匹配點(diǎn)的特征點(diǎn)，將測(cè)試圖像上的所有特征點(diǎn)生成KD-Tree，利用SIFT的特征點(diǎn)匹配策略尋找其匹配點(diǎn)，直到找到2個(gè)滿足三點(diǎn)對(duì)選取條件的匹配點(diǎn)對(duì)。將成功找到匹配點(diǎn)但未與特征點(diǎn)p構(gòu)成三點(diǎn)對(duì)的匹配點(diǎn)對(duì)集轉(zhuǎn)至（6）進(jìn)行處理。若未找到2個(gè)匹配點(diǎn)對(duì)與特征點(diǎn)key形成三點(diǎn)對(duì)，則轉(zhuǎn)至步驟（1），否則，與特征點(diǎn)p形成的三點(diǎn)對(duì)轉(zhuǎn)至步驟（5）。

（5）三點(diǎn)對(duì)形成的三角形鄰域內(nèi)尋找特征點(diǎn)，每找到一個(gè)特征點(diǎn)，利用該三點(diǎn)對(duì)形成的仿射變換矩陣 找到其在測(cè)試圖像上的映射點(diǎn)，以映射點(diǎn)為中心，T3為半徑的圓形區(qū)域內(nèi)尋找特征點(diǎn)，T3為某一給定閾值。將找到的所有特征點(diǎn)生成KD-Tree，利用SIFT的特征點(diǎn)匹配策略尋找匹配特征點(diǎn)。將成功找到匹配點(diǎn)的匹配點(diǎn)對(duì)集轉(zhuǎn)至步驟（6）。

（6）將匹配點(diǎn)對(duì)集形成三點(diǎn)對(duì)集，將每一個(gè)形成的三點(diǎn)對(duì)轉(zhuǎn)至步驟（5）進(jìn)行處理。嘗試將剩下的未形成三點(diǎn)對(duì)的匹配點(diǎn)對(duì)與mark集合中的匹配點(diǎn)對(duì)形成三點(diǎn)對(duì)，若能夠形成三點(diǎn)對(duì)，則刪除其中mark中的2個(gè)匹配點(diǎn)對(duì)，然后將形成的三點(diǎn)對(duì)轉(zhuǎn)至步驟（5）進(jìn)行處理，把最終未形成三點(diǎn)對(duì)的匹配點(diǎn)對(duì)放入mark集合中。轉(zhuǎn)至步驟（1）。

3　實(shí)驗(yàn)結(jié)果與分析

由于ASIFT通過考慮相機(jī)的光軸方向可能發(fā)生的所有變化帶來的仿射扭曲，將參考圖像與測(cè)試圖像生成多張模擬圖像，然后在每張模擬圖像上利用SIFT特征描述子提取關(guān)鍵點(diǎn)，最后利用SIFT算法進(jìn)行特征匹配。ASIFT是基于SIFT原理的，但是提取的關(guān)鍵點(diǎn)比SIFT算法多很多，為了更好地提現(xiàn)本文改進(jìn)算法的優(yōu)勢(shì)，我們?cè)贏SIFT算法下進(jìn)行關(guān)鍵點(diǎn)的提取和匹配，然后用RANSAC[6-7]算法進(jìn)行錯(cuò)誤匹配點(diǎn)的抑制。

選用datasetMorelYu09圖像集[5]進(jìn)行實(shí)驗(yàn)測(cè)試。在datasetMorelYu09圖像集中，有絕對(duì)傾斜度圖像集和相對(duì)傾斜度圖像集。

3.1ABsolute tilt tests

油畫圖像的拍攝光軸為zoom×1和zoom×10，雜志圖像的拍攝光軸為zoom×4。攝像機(jī)拍攝視角的變化范圍為0°到80°。表1為ASIFT算法和LMA算法下的匹配結(jié)果。

表1　

3.2Transition tilt tests

對(duì)于相對(duì)傾斜度集，我們使用圖像magazine zoom× 4。圖像傾斜度分別為t=2和t=4，旋轉(zhuǎn)角從0°到90°。表2為ASIFT算法和LMA算法的匹配結(jié)果。圖1和圖2為兩種算法的匹配效果顯示。

兩種傾斜度分別形成兩個(gè)圖像組，對(duì)于每個(gè)圖像組，第一列為旋轉(zhuǎn)角度和相對(duì)傾斜度，第二列、第三列分別為ASIFT算法與LMA算法的匹配點(diǎn)對(duì)數(shù)。

由表1和表2可以看出，相對(duì)于ASIFT算法，改進(jìn)的特征匹配算法明顯增加了特征匹配點(diǎn)的數(shù)量。并且改進(jìn)后的算法對(duì)圖像的旋轉(zhuǎn)、焦距和光照變化都有很好的適應(yīng)性和穩(wěn)定性。

圖1　 ASIFT算法的匹配結(jié)果

圖2　LMA算法的匹配結(jié)果

表2　

4　結(jié)語(yǔ)

改進(jìn)的匹配算法利用ASIFT算法提取特征點(diǎn)，然后在參考圖像的局部區(qū)域檢測(cè)特征點(diǎn)，檢測(cè)出的特征點(diǎn)利用該局部區(qū)域的仿射性質(zhì)尋找其在測(cè)試圖像上的匹配特征點(diǎn)。通過對(duì)不同光照條件、焦距、拍攝角度的圖像進(jìn)行一系列的實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明本文的改進(jìn)算法對(duì)圖像的光照、平移、旋轉(zhuǎn)變換具有顯著的改善，能夠增加較多的匹配點(diǎn)對(duì)。

[1]D.Lowe.Distinctive Image Features from Scale Invariant Keypoint[J].International Journal of Computer Vision，2004:91-110.

[2]Bay Herbert，Tuytelaars Tinne，Gool Luc Van.Speeded Up Robust Features[J].Computer Vision and Image Understanding，2008:346-359.

[3]Y.Ke，R.Sukthankar.PCA-SIFT:A More Distinctive Representation for Local Image Descriptors[C].Computer Vision and Pattern Recognition，2004:511-517.

[4]HARRIS C，STEPHENS M.A Combined Corner and Edge Detection[J].Image Vision Computing，1998:121-127.

[5]Jean-Michel Morel，Guoshen Yu.ASIFT:A New Framework for Fully Affine Invariant Image Comparison[J].SIAM Journal on Imaging Sciences，2009:438-469.

[6]Luo Juan，Oubong Gwun.A Comparison of SIFT，PCA-SIFT and SURF[J].International Journal of Image Processing，2009:143-152.

[7]M.Fischler and R.Bolles.Random Sample Consensus:A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography[C].ACM，1981:381-395.

Local Feature Matching;Affine Transformation Matrix;Space constraint;Matching Accuracy

Local Feature Matching Algorithm Based on Affine Transformation

QI Hai-xiang

（College of Computer Science,Sichuan University,Chengdu 610065）

1007-1423（2016）05-0058-05

10.3969/j.issn.1007-1423.2016.05.013

戚海想（1989-），女，河南商丘人，在讀碩士研究生，研究方向?yàn)闄C(jī)器視覺

2015-12-31

2016-02-08

針對(duì)SIFT算法中存在一對(duì)多和多對(duì)一匹配，并最終導(dǎo)致正確匹配被剔除的情況，提出一種基于仿射變換的局部特征匹配算法（LMA）。該方法基于SIFT算法下的匹配點(diǎn)對(duì)集，在圖像的不同局部區(qū)域選擇三點(diǎn)對(duì)并計(jì)算相應(yīng)的仿射變換矩陣，對(duì)于參考圖像上的每個(gè)特征點(diǎn)，通過距離其最近的仿射變換矩陣找到匹配點(diǎn)，利用RANSAC算法剔除誤差較大的匹配點(diǎn)。實(shí)驗(yàn)結(jié)果表明，通過這種空間約束，改進(jìn)算法在保證高匹配精度的同時(shí)，能夠明顯增加匹配點(diǎn)數(shù)量。

局部特征匹配；仿射變換矩陣；空間約束；匹配精度

Aiming at the situation of the ASIFT algorithm where there are one-to-many,and many-to-one matching,and eventually leading to correct matching are eliminated,proposes a local feature matching algorithm based on affine transformation(LMA).The method is based on the matching key point set under the ASIFT algorithm,in different local areas of an image,chooses three pairs of matching key point and calculates the corresponding affine transformation matrix,for every key point in the reference image,searches for matching key point by the nearest affine transformation matrix,and eliminate the matching key points which have bigger error in the matching key point set by the RANSAC algorithm.The experimental results show that by this kind of space constraint,improved algorithm can obviously increase the number of matching key points,at the same time of ensuring high matching accuracy.