孫曉雨，李云天

（四川大學(xué)計算機學(xué)院，成都　610065）

基于多尺度空間約束的局部匹配算法

孫曉雨，李云天

（四川大學(xué)計算機學(xué)院，成都610065）

0　引言

圖像匹配是一個基本的步驟在許多計算機視覺的應(yīng)用中，如物體識別[1]、對象跟蹤、機器人定位和圖像檢索等[2-3]。近些年的研究中顯示，全局描述符更容易受到噪聲的影響，而局部描述符在匹配穩(wěn)定性上能夠取得更好的匹配效果。Mikolajczyk和Schmid提出一種實驗評估方法[4]，對steerable filters[5]、differential invariants[6]、moment invariants[7]、complex filters[8]、SIFT和cross-correlation of different types of interest points[9]等局部匹配算法做了詳細的比較。實驗證明：在大多數(shù)情況下SIFT算法能取得更好的效果。近些年在SIFT算法的基礎(chǔ)上，又延伸出很多算法，包括PCA-SIFT[10]、GLOH[11]、SURF[12]等，這些方法已經(jīng)被應(yīng)用到很多實際項目當中，但是對兩張拍攝視角差異較大的圖片，SIFT算法和其延伸算法的效果都很差。在SIFT的基礎(chǔ)上，為了解決這種問題，ASIFT[13]算法被提出，ASIFT算法能夠很好地解決這一問題，在文獻[12]中的實驗分析中證明，ASIFT在大多數(shù)方面優(yōu)于SIFT和其他算法。

然而，ASIFT有兩個比較大的缺點相比SIFT。首先，ASIFT算法在時間復(fù)雜度上高于 SIFT；其次，ASIFT算法提取的特征點比較多，但是經(jīng)過匹配去重以后AIST匹配的特征點相比于提取的特征點大大的減少。這是由于ASIFT沒有進行局部空間約束，在匹配過程如果出現(xiàn)一對多或者多對一的情況下，ASIFT無法判斷出來哪一對點是正確的匹配，為了提高匹配正確率，ASIFT把這些匹配全部舍棄了。本文正是對ASIFT第二個缺點提出了解決方法。本文的主要貢獻如下：①以最大和最小尺度的1/n為步長，將ASIFT匹配的特征點分成n類；②根據(jù)初始匹配的分類，為每一類特征點建立局部約束空間；③在局部約束空間中對ASIFT提取到的特征點進行重新匹配。

1　LFMC算法

用ASIFT算法模擬參考圖像和測試圖像的各個經(jīng)度角和緯度角，生成左右兩個模擬圖像集合，將兩個集合中的模擬圖像用SIFT算法提取特征點，生成兩個特征點的集合Sp和Sq。遍歷左右兩個集合的特征點，根據(jù)左右特征點的描述符的距離進行全局匹配。匹配后生成一個初始匹配集合M。

1.1確定迭代步長

假設(shè)一幅圖像中的特征點的尺度參數(shù)為scl，其中最大的尺度參數(shù)為sclmax，最小的尺度參數(shù)為sclmin，則有：

其中，k為常數(shù)，k取10是一個較為理想的值。step為特征點尺度篩選閾值變化的步長。

設(shè)定一組特征點尺度篩選閾值集合T：

其中，Ti=Ti-1-step，由以上方法得到的一組特征點尺度篩選閾值集合T是一個等差數(shù)列，其中T1最大，然后依次遞減，直到Ti＝0時為止。在一組特征點尺度篩選閾值集合T中，T1是由一幅圖像的所有圖像特征點的尺度參數(shù)估計得出的，因此T1是T這個等差數(shù)列的初始值，由T1結(jié)合步長step即可求出后續(xù)的特征點尺度篩選閾值Ti。需要進一步分析的是，如何對初始尺度篩選閾值T1進行取值才能得到比較理想的匹配效果。當T1取值過大時，會產(chǎn)生以下三種影響：

（1）在參考圖像和目標圖像中得到的特征點數(shù)量過少，減少了首次篩選后的匹配點對的數(shù)量；

（2）由于參考圖像和目標圖像中的特征點數(shù)量過少，當以特征點坐標為中心建立局部約束區(qū)域集時，會使得局部約束區(qū)域覆蓋圖像的面積過小，局部約束區(qū)域之外會存在大量特征點，而這些特征點會被剔除；

（3）會增加特征點尺度篩選閾值集中的特征點尺度篩選閾值Ti的數(shù)量，使得算法中循環(huán)次數(shù)增多，從而降低算法時效性。

當T1取值過小時，參考圖像和目標圖像中篩選得到的特征點數(shù)量過多，在以特征點坐標為中心建立局部約束區(qū)域集時，會使得局部約束區(qū)域所覆蓋的圖像區(qū)域產(chǎn)生過多重疊，從而產(chǎn)生大量重復(fù)特征點，影響特征點匹配效果，并且降低算法時效性。

從以上分析可知，T1的取值是否合理十分關(guān)鍵。因為T1的取值不僅會影響圖像特征點的首次篩選的效果，并且會影響到算法中后續(xù)處理過程各參數(shù)的取值和最終算法效果。

1.2匹配點分類

將匹配點集合中的匹配點對按step分為n類，M＝{Mi│i=1，2，3，…，n}，其中Mi中的匹配點對中的參考圖像上的特征點Pi集的尺度Si滿足：

1.3匹配

為了避免在全局圖像范圍內(nèi)對特征點進行檢測和匹配時出現(xiàn)重復(fù)匹配點對或者是一對多、多對一的情況出現(xiàn)，需要對特征點的檢測范圍進行局部區(qū)域的約束，使得特征點的檢測和匹配限定在一個較小的局部區(qū)域中。在參考圖像中可以建立很多約束區(qū)域，并且在一方限制區(qū)域便可限制另一幅對應(yīng)圖像，兩幅圖像中一一對應(yīng)的局部區(qū)域進行特征點匹配，從而提高匹配的正確率。下面詳細介紹局部約束區(qū)域的建立過程：

首先，假設(shè)一幅圖像的特征點總數(shù)為n，定義特征點Pij＝{xij，yij，sclij}，其中為（xij，yij）特征點坐標，sclij為特征點尺度。

然后，根據(jù)所有特征點的尺度sclij，計算得到特征點尺度篩選閾值集合T＝{Ti│i=1，2，3，…}，具體計算步驟如上節(jié)所示。最后，確定一個搜索特征點的局部約束區(qū)域集R，Ri＝{rij│j=1，2，3，…，m-1}，（m≤n）.其中，rij是一個以（xij，yij）為中心，lij為邊長的正方形區(qū)域，lij= sclij*k，k為常數(shù)，且有T（i-1）≥sclij≥Ti。

（1）構(gòu)造平行四邊形局部約束區(qū)域內(nèi)的特征點子集

在ASIFT算法中，圖像特征點的提取是在各個模擬圖像中完成的，這些檢測出來的特征點需要變換回原始圖像，再對所有特征點進行匹配。因為圖像的像素點坐標在從模擬圖像變換回原始圖像時發(fā)生了改變，在模擬圖像中根據(jù)各個特征點的坐標和尺度所建立的局部約束區(qū)域集Ri中的局部約束區(qū)域rij也會由模擬圖像中的正方形變換為原始圖像中的平行四邊形。

值得注意的是，不僅僅是局部約束區(qū)域集Ri需要通過仿射變換矩陣進行轉(zhuǎn)換。原始圖像中的特征點在利用局部約束區(qū)域集Ri進行篩選之前，也需要過仿射變換矩陣進行轉(zhuǎn)換。只有將兩者都轉(zhuǎn)換為同一圖像坐標系，保證了兩者的幾何對應(yīng)關(guān)系之后，才能夠正確判斷特征點是否位于局部約束區(qū)域當中。

定義初始特征點集為S0，仿射變換后的特征點集為其中局部約束區(qū)域集Ri，仿射變換后的區(qū)域點集為

首次篩選時，特征點尺度篩選閾值為T1，其中：

第i次篩選時，尺度閾值為Ti，其中：

1.4LFMC算法處理流程

從1.2節(jié)中分類好的集合M中取出一個匹配集合Mi，假設(shè)Mi={m1（p1，q1），m2（p2，q2），m3（p3，q3），…，mn（pn，qn）}，n代表集合Ti中的匹配點數(shù)目。匹配步驟如下：

（1）從集合Mi中取出一個匹配點對mi（pi，qi），將參考圖像上的特征點pi和測試圖像上的特征點qi的描述符區(qū)域從其尺度空間變換到原圖像，此時pi和qi表示的區(qū)域分別為兩個平行四邊形。

（2）遍歷用ASIFT算法提取的參考圖像的特征點集合Sp，把特征點的坐標從其尺度空間變換到原圖像，如果變換以后的坐標在pi描述符表示的平行四邊形中，將此特征點保存在集合中。

（3）遍歷用ASIFT算法提取的測試圖像的特征點集合Sq，把特征點的坐標從其尺度空間變換到原圖像，如果變換以后的坐標在qi描述符表示的平行四邊形中，將此特征點保存在集合中。

（5）遍歷集合Mi，用其中的每一對特征點描述符表示的區(qū)域限制查找范圍，重復(fù)（2），（3）。

遍歷集合N，對集合中每一個匹配點對集合Mi按以上步驟進行處理，最后去除重復(fù)匹配。

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

為了驗證本算法的有效性，將改進算法和ASIFT算法進行對比實驗，并對實驗結(jié)果進行詳細分析。為了確保實驗效果的完整性，將分別對發(fā)生不同變化的參考圖像和目標圖像進行實驗，包括旋轉(zhuǎn)縮放變化、尺度變化、光照變化和視角變化。為確保實驗結(jié)果的可對比性，本文中實驗圖片來自于Mikolajczyk標準數(shù)據(jù)集。我們選擇5個圖像集合，每個圖像集合我們選擇5張測試圖像，分別和圖像集合中的參考圖像進行匹配。其中圖像發(fā)生的形變類型在表1中列出，表2是實驗結(jié)果，在表2中，m/n給出匹配點的數(shù)量比，m表示ASIFT算法匹配的特征點數(shù)量，n代表 LFMC算法匹配的特征點數(shù)量。我們用RANSAC[14]算法對實驗結(jié)果進行處理，進行去除錯配點。最左邊一列代表圖像集合，最上邊一列代表參考圖像和測試圖像的圖像對編號，隨著數(shù)字的增大，圖像形變程度變大。表3給出ASIFT和LFMC匹配準確率。

表1

表2　

從表2中我們知道，在尺度變化和視角變換的條件下，LFMC匹配到的特征點的數(shù)量是ASIFT的兩倍左右，隨著匹配圖片的形變增大，匹配的特征點數(shù)量減少。在光照變化的條件下，LFMC匹配的特征點遠遠大于ASIFT，LFMC比ASIFT多出的匹配特征點的數(shù)量和ASIFT初始匹配到的特征點的數(shù)量也是有關(guān)的。當圖像的形變有放縮和旋轉(zhuǎn)的時候，LFMC匹配的特征點最少也是ASIFT算法的兩倍。綜上，LFMC所增加匹配的特征點數(shù)量比ASIFT有明顯的提高，和ASIFT初始匹配的特征點成反比。一些匹配結(jié)果如圖1、圖2所示。

3　結(jié)語

本文提出一種新穎的圖像匹配算法，用ASIFT完成初始匹配，根據(jù)ASIFT提取到的特征點的尺度選擇合適的步長，通過步長分類特征點，然后建立一個具有層級結(jié)構(gòu)的多尺度局部匹配模型，最后去除重復(fù)匹配和錯配點。我們用最后匹配的特征點數(shù)作為評估標準，在本文中，我們選擇了充分的測試圖像集合，實驗結(jié)果證明LMFC算法在匹配的特征點的數(shù)量上大大的增加。同樣，LMFC對將來的圖像匹配算法也有重要的意義，這種算法模型不僅僅可以應(yīng)用到ASIFT算法中，其他圖像匹配算法也可以引入這種模型來提高匹配特征點數(shù)量。然而，LMFC算法的時間復(fù)雜度高于ASIFT算法，因此，下一步的研究我們將重點放在提高LFMC算法速度上。

圖1　Boat 1 vs.5，LFMC（上），ASIFT（下）分別匹配到440和170對特征點

圖2　Leuven 1 vs.5，LFMC（上），ASIFT（下）分別匹配到1818和510對特征點

[1]D.G.Lowe.Object Recognition from Local Scale-Invariant Features.In Proceedings of International Conference on Computer Vision，1999：1150-1157.

[2]X.Luo，G.Wu，and K.Kita.Learning Distance Metrics with Feature Space Performance for Image Retrieval.in Proc.2013 Int.Conf. Elect.Inf.Technol.Rail Transp.（EITRT'13），2014：411-421.

[3]X.He，Laplacian Regularized D-optimal Design for Active Learning and Its Application to Image Retrieval，IEEE Trans.Image Process，2010,19（1）:254-263.

[4]K.Mikolajczyk,C.Schmid.A Performance Evaluation of Local Descriptors.In Proceedings of Computer Vision and Pattern Recognition，2003,June.

[5]W.T.Freeman,E.H.Adelson.The Design and Use of Steerable Filters.IEEE Trans.Pattern Analysis and Machine Intelligence，1991, 13（9）:891-906.

[6]J.Koenderink,A.van Doorn.Representation of Local Geometry in the Visual System.In Biological Cybernetics，1987,55:367-375.

[7]L.Van Gool，T.Moons，D.Ungureanu.Affine/Photometric Invariants for Planar Intensity Patterns.In Proceedings of European Conference on Computer Vision,1996.

[8]F.Schaffalitzky，A.Zisserman.Multi-View Matching for Unordered Image sets.In Proceedings of European Conference on Computer Vision，2002，1，：414-431.

[9]C.Harris，M.Stephens.A Combined Corner and Edge Detector.In Alvey Vision Conference，1988：147-151.

[10]Y.Ke，R.Sukthankar，PCA-SIFT:A More Distinctive Representation for Local Image Descriptors，in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition，2004，2：506-513.

[11]K.Mikolajczyk，C.Schmid.A Performance Evaluation of Local Descriptors，IEEE Trans.PatternAnal.Mach.Intell.，2005:1615-1630.

[12]H.Bay，T.Tuytelaars，L.Van Gool，Surf:Speeded up Robust Features，in Computer Vision—ECCV 2006，Springer-Verlag，Berlin，Heidelberg，2006：404-417.

[13]J.M.Morel，G.Yu，ASIFT:A New Framework for Fully Affine Invariant Image Comparison.Society for Industry and Applied Mathematics，2009，2（2）：438-469.

[14]Martin A.Fischler，Robert C.Bolles.Random Sample Consensus:A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography[J].Graphics and Image Processing，1981，24（6）：381.

Feature Matching;Initial Matches;Step;Scale of Interest Point;Constraint Space

Local Matching Algorithm Based on Multi-Scale Space Constraints

SUN Xiao-yu，LI Yun-tian
（College of Computer Science，Sichuan University，Chengdu 610065）

1007-1423（2016）03-0058-05

10.3969/j.issn.1007-1423.2016.03.014

孫曉雨（1987-），男，河南許昌人，在讀研究生，研究方向為計算機視覺李云天，男，江蘇徐州人，在讀研究生，研究方向為計算機視覺

2015-12-08

2016-01-10

提出一種新穎的特征匹配算法LFMC。該算法在ASIF初始匹配的基礎(chǔ)上，以特征點尺度為標準，以最大和最小尺度之差的1/n為步長，在測試圖像和參考圖像建立一個層級的匹配約束空間，然后在每個約束空間之中進行匹配。由于ASIFT算法是目前特征點匹配最多的匹配算法，在實驗部分對LFMC和ASIFT算法做詳細的比較。

特征匹配；初始匹配；步長；特征點尺度；約束空間

Presents a novel feature matching approach named LFMC.Based on the initial matches obtained by the ASIFT algorithm,this approach takes the scale of interest point as the standard,1/n of the difference between the largest and smallest scales as the step length,establishes a hierarchical matching constraint space respectively on the test image and the reference image,and at last matches among each constraint space.Because ASIFT algorithm can match more interest points than the state-of-the-art algorithms,a detailed comparison is made between LFMC and ASIFT in the experiment section.