孫曉雨，李云天

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

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

孫曉雨，李云天

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

0　引言

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

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

1　LFMC算法

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

1.1確定迭代步長

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

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

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

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

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

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

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

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

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

1.2匹配點(diǎn)分類

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

1.3匹配

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

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

然后，根據(jù)所有特征點(diǎn)的尺度sclij，計算得到特征點(diǎn)尺度篩選閾值集合T＝{Ti│i=1，2，3，…}，具體計算步驟如上節(jié)所示。最后，確定一個搜索特征點(diǎn)的局部約束區(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)的特征點(diǎn)子集

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

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

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

首次篩選時，特征點(diǎn)尺度篩選閾值為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中的匹配點(diǎn)數(shù)目。匹配步驟如下：

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

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

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

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

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

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

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

表1

表2　

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

3　結(jié)語

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

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

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

[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-），男，河南許昌人，在讀研究生，研究方向?yàn)橛嬎銠C(jī)視覺李云天，男，江蘇徐州人，在讀研究生，研究方向?yàn)橛嬎銠C(jī)視覺

2015-12-08

2016-01-10

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

特征匹配；初始匹配；步長；特征點(diǎn)尺度；約束空間

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.