孫曉雨，李云天

（四川大學計算機學院，成都　610065）

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

孫曉雨，李云天

（四川大學計算機學院，成都610065）

0　引言

圖像匹配是一個基本的步驟在許多計算機視覺的應用中，如物體識別[1]、對象跟蹤、機器人定位和圖像檢索等[2-3]。近些年的研究中顯示，全局描述符更容易受到噪聲的影響，而局部描述符在匹配穩定性上能夠取得更好的匹配效果。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]等局部匹配算法做了詳細的比較。實驗證明：在大多數情況下SIFT算法能取得更好的效果。近些年在SIFT算法的基礎上，又延伸出很多算法，包括PCA-SIFT[10]、GLOH[11]、SURF[12]等，這些方法已經被應用到很多實際項目當中，但是對兩張拍攝視角差異較大的圖片，SIFT算法和其延伸算法的效果都很差。在SIFT的基礎上，為了解決這種問題，ASIFT[13]算法被提出，ASIFT算法能夠很好地解決這一問題，在文獻[12]中的實驗分析中證明，ASIFT在大多數方面優于SIFT和其他算法。

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

1　LFMC算法

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

1.1確定迭代步長

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

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

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

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

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

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

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

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

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

1.2匹配點分類

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

1.3匹配

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

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

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

（1）構造平行四邊形局部約束區域內的特征點子集

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

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

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

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

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

1.4LFMC算法處理流程

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

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

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

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

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

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

2　實驗結果與分析

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

表1

表2　

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

3　結語

本文提出一種新穎的圖像匹配算法，用ASIFT完成初始匹配，根據ASIFT提取到的特征點的尺度選擇合適的步長，通過步長分類特征點，然后建立一個具有層級結構的多尺度局部匹配模型，最后去除重復匹配和錯配點。我們用最后匹配的特征點數作為評估標準，在本文中，我們選擇了充分的測試圖像集合，實驗結果證明LMFC算法在匹配的特征點的數量上大大的增加。同樣，LMFC對將來的圖像匹配算法也有重要的意義，這種算法模型不僅僅可以應用到ASIFT算法中，其他圖像匹配算法也可以引入這種模型來提高匹配特征點數量。然而，LMFC算法的時間復雜度高于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初始匹配的基礎上，以特征點尺度為標準，以最大和最小尺度之差的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.