戚海想（四川大學計算機學院，成都610065)

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

戚海想
（四川大學計算機學院，成都610065)

0　引言

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

1　SIFT算法

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

1.1極值點檢測

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

σ為高斯函數(shù)的標準差，*為卷積符號，I（x，y）表示圖像。

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

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

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

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

1.2計算特征點方向

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

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

1.3計算特征點描述子

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

1.4特征匹配

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

2　LMA算法

2.1三點對的選取

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

（xi，yi）代表特征點pi的坐標，（xj，yj）代表特征點 pj的坐標。如果pi≠pj并且 Dl

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

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

2.2計算仿射變換矩陣

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

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

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

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

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

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

其中（kx，ky）為特征點k的坐標，（kx'，ky'）為映射點的坐標。

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

2.4LMA算法處理步驟

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

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

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

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

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

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

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

3　實驗結(jié)果與分析

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

選用datasetMorelYu09圖像集[5]進行實驗測試。在datasetMorelYu09圖像集中，有絕對傾斜度圖像集和相對傾斜度圖像集。

3.1ABsolute tilt tests

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

表1　

3.2Transition tilt tests

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

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

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

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

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

表2　

4　結(jié)語

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

[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-），女，河南商丘人，在讀碩士研究生，研究方向為機器視覺

2015-12-31

2016-02-08

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