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

孫曉雨，李云天

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

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

孫曉雨，李云天

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

0　引言

圖像匹配是一個(gè)基本的步驟在許多計(jì)算機(jī)視覺(jué)的應(yīng)用中，如物體識(shí)別[1]、對(duì)象跟蹤、機(jī)器人定位和圖像檢索等[2-3]。近些年的研究中顯示，全局描述符更容易受到噪聲的影響，而局部描述符在匹配穩(wěn)定性上能夠取得更好的匹配效果。Mikolajczyk和Schmid提出一種實(shí)驗(yàn)評(píng)估方法[4]，對(duì)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í)際項(xiàng)目當(dāng)中，但是對(duì)兩張拍攝視角差異較大的圖片，SIFT算法和其延伸算法的效果都很差。在SIFT的基礎(chǔ)上，為了解決這種問(wèn)題，ASIFT[13]算法被提出，ASIFT算法能夠很好地解決這一問(wèn)題，在文獻(xiàn)[12]中的實(shí)驗(yàn)分析中證明，ASIFT在大多數(shù)方面優(yōu)于SIFT和其他算法。

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

1　LFMC算法

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

1.1確定迭代步長(zhǎng)

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

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

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

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

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

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

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

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

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

1.2匹配點(diǎn)分類(lèi)

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

1.3匹配

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

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

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

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

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

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

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

首次篩選時(shí)，特征點(diǎn)尺度篩選閾值為T(mén)1，其中：

第i次篩選時(shí)，尺度閾值為T(mén)i，其中：

1.4LFMC算法處理流程

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

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

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

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

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

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

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

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

表1

表2　

從表2中我們知道，在尺度變化和視角變換的條件下，LFMC匹配到的特征點(diǎn)的數(shù)量是ASIFT的兩倍左右，隨著匹配圖片的形變?cè)龃螅ヅ涞奶卣鼽c(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)的時(shí)候，LFMC匹配的特征點(diǎn)最少也是ASIFT算法的兩倍。綜上，LFMC所增加匹配的特征點(diǎn)數(shù)量比ASIFT有明顯的提高，和ASIFT初始匹配的特征點(diǎn)成反比。一些匹配結(jié)果如圖1、圖2所示。

3　結(jié)語(yǔ)

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

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

圖2　Leuven 1 vs.5，LFMC（上），ASIFT（下）分別匹配到1818和510對(duì)特征點(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)橛?jì)算機(jī)視覺(jué)李云天，男，江蘇徐州人，在讀研究生，研究方向?yàn)橛?jì)算機(jī)視覺(jué)

2015-12-08

2016-01-10

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

特征匹配；初始匹配；步長(zhǎng)；特征點(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.