基于簡(jiǎn)化描述符的仿射不變圖像匹配算法

李記鵬，尹顏朋

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

0 引言

圖像匹配是計(jì)算機(jī)視覺的一個(gè)重要分支，廣泛應(yīng)用于三維重建、目標(biāo)識(shí)別、圖像檢索等領(lǐng)域。基于特征的匹配方法由于計(jì)算量少、速度快得到了研究者的青睞，近年來大量的局部特征檢測(cè)子涌現(xiàn)出來，這些檢測(cè)子都具有平移不變性，Harris檢測(cè)子[11]對(duì)于旋轉(zhuǎn)也具有不變性，Harris-Laplace,Hessian-Laplace以及高斯差分區(qū)域檢測(cè)子具有尺度不變性[12-15]，其他一些區(qū)域檢測(cè)子如 Harris-affine,Hessian-affine,MSER（Maximally Sta?ble Extremal Region）對(duì)于圖像的仿射變換具有一定的適應(yīng)性[16,13,5]。Lowe提出的特征檢測(cè)方法將SIFT（Scale Invariant Feature Transform）檢測(cè)子與SIFT描述符相結(jié)合，具有尺度、平移、旋轉(zhuǎn)不變性，對(duì)光照、幾何變換有一定的適應(yīng)性。相關(guān)文獻(xiàn)表明相對(duì)于其他描述符而言，SIFT描述符性能更加穩(wěn)定[17]，因此被廣泛應(yīng)用于圖像匹配，然而SIFT特征描述符維度過高，匹配圖像的時(shí)間開銷很大而且不具備仿射不變性。YanKe等提出PCA（Principal Components Analysis）-SIFT[2]方法有效的降低了描述符的維度，提高了圖像匹配的速度，但是該方法的降維操作時(shí)間復(fù)雜度過高。ZhipingZhou等提出的 MDS（Multidimensional Scaling）-SIFT[3]方法在一定程度上克服了該問題，同時(shí)引入局部紋理特征約束提高了匹配的精度。XinminZhou[4]提出一種方法使用圓形區(qū)域替代正方形區(qū)域，然后計(jì)算每個(gè)子區(qū)域梯度方向分布，該方法極大的簡(jiǎn)化了描述符生成的過程，提高了匹配速度。上述方法雖然提高了圖像匹配的效率，但是都不具備仿射不變性。J.Matas[5]等提出一種適用于寬基線圖像匹配的方法，提取圖像的MSER特征進(jìn)行圖像匹配，WenchaoHu等將MSER特征與SIFT特征相結(jié)合提出一種對(duì)于仿射形變具有較好魯棒性的匹配算法[6]，但是這些方法依然不具有完全仿射不變的特性。J.M.Morel等將攝像機(jī)的成像過程近似為仿射變換，通過模擬攝像機(jī)位置變化產(chǎn)生的仿射形變提出一種完全仿射不變的圖像匹配算法即ASIFT（Affine-SIFT）[7]，然而該算法時(shí)間開銷太大。

本文將簡(jiǎn)化描述符與ASIFT的模擬方法相結(jié)合提出一種完全仿射不變的匹配算法，實(shí)驗(yàn)證明該方法對(duì)于仿射形變較大的圖像具有較好的魯棒性，匹配速度明顯優(yōu)于ASIFT。

1 基于簡(jiǎn)化描述符的仿射不變匹配算法

1.1 基于圓形鄰域的簡(jiǎn)化描述符

SIFT生成描述符時(shí)，為了保證旋轉(zhuǎn)不變性在統(tǒng)計(jì)梯度方向之前需要將整個(gè)采樣區(qū)域旋轉(zhuǎn)至主方向，由于SIFT采樣區(qū)域?yàn)榉叫螀^(qū)域旋轉(zhuǎn)前后無法完全重疊，尤其是角落區(qū)域的像素點(diǎn)旋轉(zhuǎn)后大部分均不在重疊區(qū)域如圖1（a）所示，因此采用相同尺寸的方形區(qū)域生成描述符肯定會(huì)產(chǎn)生很大的誤差。在實(shí)踐中相關(guān)算法為了克服該誤差往往采用更大的方形區(qū)域生成描述符，這種做法不可避免的帶來了了冗余的像素旋轉(zhuǎn)操作，增加了運(yùn)行時(shí)間。圓形區(qū)域則不相同，對(duì)于旋轉(zhuǎn)操作具有更好的不變性，旋轉(zhuǎn)前后覆蓋的像素完全一致如圖 1（b）所示。

圖1 方形區(qū)域和圓形區(qū)域比較

因此本文提出一種在圓形鄰域內(nèi)使用扇形區(qū)域生成描述符的方法，具體過程如下：

（1）使用SIFT方法在尺度空間中尋找圖像的關(guān)鍵點(diǎn)，同時(shí)確定主方向。

（2）在相應(yīng)的尺度空間中以關(guān)鍵點(diǎn)為中心產(chǎn)生一個(gè)圓形區(qū)域，計(jì)算像素梯度，將圓形區(qū)域旋轉(zhuǎn)至主方向，對(duì)梯度做高斯加權(quán)。

（3）將圓形區(qū)域分為2×2個(gè)扇形子區(qū)域，在每個(gè)扇形區(qū)域內(nèi)統(tǒng)計(jì)8個(gè)方向的梯度直方圖如圖2（b）所示。

（4）將4個(gè)扇形的梯度直方圖合并得到32維的描述符然后進(jìn)行歸一化處理，以降低光照變化對(duì)描述符的影響。

SIFT生成描述符時(shí)以關(guān)鍵點(diǎn)為中心生成一個(gè)方形鄰域，然后將其分為16個(gè)子區(qū)域，在每個(gè)在區(qū)域內(nèi)統(tǒng)計(jì)8個(gè)方向的梯度直方圖如圖2（a）所示，最終生成128維描述符。盡管本文方法也需要統(tǒng)計(jì)梯度直方圖，但是只需要在4個(gè)扇形區(qū)域上統(tǒng)計(jì)，統(tǒng)計(jì)次數(shù)比SIFT少了12次，另外本文算法的描述符維度降低了64維，在進(jìn)行描述符相似度的計(jì)算時(shí)，使用該描述符可以大大降低計(jì)算量，提高匹配效率。

圖2 描述符對(duì)比

1.2 仿射不變匹配算法

降維后的描述符與SIFT描述符一樣具有尺度，旋轉(zhuǎn)不變性并且對(duì)于光照、強(qiáng)度變化有一定的適應(yīng)性，而且匹配速度有一定提高，然而仍然不具有仿射不變性。本文受ASIFT模擬思想的啟發(fā)，通過模擬攝像機(jī)位置變化產(chǎn)生的形變克服這一缺陷，提出一種完全仿射不變的匹配算法。

在仿射相機(jī)模型中，攝像機(jī)成像過程被簡(jiǎn)化為一個(gè)仿射變換，該仿射變換存在唯一的SVD分解：

其中λ>0 λ>0,λt是A的行列式，Ri表示旋轉(zhuǎn)，與相應(yīng)的對(duì)角矩陣表示傾斜因子。該分解的幾何解釋如圖3所示，u表示扁平的物體平面，右上方的平行四邊形表示攝像機(jī)平面，θ，?分別是攝像機(jī)的緯度經(jīng)度，用來表示攝像機(jī)的位置，ψ表示攝像機(jī)平面的旋轉(zhuǎn)，λ表示放縮倍數(shù)，其中θ與公式1中的t t一一對(duì)應(yīng)，t=1/cosθ表示圖像的絕對(duì)傾斜。

假設(shè)u1=u(A(x,y))u1=u(A(x,y)),u2=u(B(x,y))u2=u(B(x,y))表示攝像機(jī)在不同視角下得到的兩幅圖像，其中A,B表示成像過程中的仿射變換，使用公式1可以定義u1到u2的變換如下：

其中τ與兩幅圖像的絕對(duì)傾斜、經(jīng)度差有關(guān)，表示圖像之間的相對(duì)傾斜，該定義的詳細(xì)信息請(qǐng)參閱文獻(xiàn)[7]。J.M.Morel在該理論的基礎(chǔ)上對(duì)每一幅圖像做仿射變換模擬攝像機(jī)位置變化產(chǎn)生的仿射形變提出一種完全仿射不變的匹配算法即ASIFT。本文將簡(jiǎn)化描述符與ASIFT模擬機(jī)制相結(jié)合在保證仿射不變的前提下，提高匹配效率，算法具體過程如下：

圖3 SVD分解的幾何解釋

（1）對(duì)每一幅圖像進(jìn)行仿射變換模擬由于攝像機(jī)位置變化產(chǎn)生的仿射形變。圖像的仿射形變主要取決于經(jīng)緯度的變化，因此在對(duì)原始圖像做仿射變換時(shí)只對(duì)攝像機(jī)的經(jīng)緯度進(jìn)行模擬，為了模擬出盡可能多的形變圖像，在對(duì)經(jīng)緯度采樣時(shí)按照如下規(guī)則進(jìn)行：

a.對(duì)緯度采樣時(shí)保證與之相關(guān)的傾斜因子t按照1,a，a2，…，an的規(guī)律變化，其中

b.對(duì)經(jīng)度采樣時(shí)?按照0,b/t，…，kb/t的規(guī)律變化，其中b=72°，k是kb/t<=180°的最大整數(shù)解。

（2）對(duì)每一幅模擬圖像使用SIFT方法檢測(cè)特征點(diǎn)，確定主方向，最后使用圓形區(qū)域生成簡(jiǎn)化的32維描述符。

（3）對(duì)左右圖像的任意一對(duì)模擬圖像使用最近距離次近距離比算法建立匹配關(guān)系如圖4所示。最近距離次近距離比算法匹配圖像時(shí)，計(jì)算左圖中每個(gè)描述符與右圖中所有描述符的歐氏距離，如果最近距離和次近距離的比值小于給定的閾值，則兩個(gè)描述符對(duì)應(yīng)的點(diǎn)匹配成功。最終的匹配結(jié)果是所有模擬圖像對(duì)匹配結(jié)果的并集，由于模擬圖像模擬了攝像機(jī)位置變化產(chǎn)生的各種仿射形變，因此該匹配結(jié)果對(duì)于圖像的仿射變換具有較好的適應(yīng)性，文獻(xiàn)[7]在理論上證明了該方法的仿射不變性。

（4）使用對(duì)極幾何的約束消除錯(cuò)誤匹配，RANSAC（Random Sample Consensus）[8]是剔除錯(cuò)配點(diǎn)常用的方法，然而該方法對(duì)于初始匹配點(diǎn)集的依賴性較大，如果初始匹配點(diǎn)集中錯(cuò)誤匹配點(diǎn)過多，將無法正確的剔除錯(cuò)配點(diǎn)，ORSA（Optimized RANSAC）[9]是基于 RANSAC改進(jìn)而來的方法，該方法有效的克服了RANSAC對(duì)于初始匹配點(diǎn)集過分依賴的缺陷，本文使用該方法消除錯(cuò)匹配得到最終的匹配結(jié)果。

圖4 仿射不變匹配算法

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

研究人員在ASIFT源代碼的基礎(chǔ)上對(duì)本文算法進(jìn)行編程實(shí)現(xiàn)，為了評(píng)價(jià)匹配性能，采用Morel圖像集[7]對(duì)本文算法進(jìn)行測(cè)試，并與ASIFT的匹配性能進(jìn)行對(duì)比。Morel圖像集分為絕對(duì)傾斜測(cè)試集和相對(duì)傾斜測(cè)試集兩部分，絕對(duì)傾斜測(cè)試集包括一幅油畫在放縮倍數(shù)為1和10的情況下拍攝的兩組圖像，以及一本雜志在放縮倍數(shù)為4的情況下拍攝的一組圖像，相對(duì)傾斜測(cè)試集包含一本雜志在絕對(duì)傾斜為2和4的情況下攝像機(jī)經(jīng)度從零度到九十度逐漸增大拍攝得到的兩組圖像。

2.1 絕對(duì)傾斜實(shí)驗(yàn)分析

本文使用放縮倍數(shù)為1的圖像集進(jìn)行絕對(duì)傾斜實(shí)驗(yàn)，將本文方法與ASIFT在匹配點(diǎn)數(shù)、匹配速度兩個(gè)方面對(duì)比，實(shí)驗(yàn)結(jié)果如表1所示，表中各列從左至右一次表示絕對(duì)傾斜值得大小，ASIFT匹配點(diǎn)數(shù)，本文算法匹配點(diǎn)數(shù)，ASIFT匹配速度，本文算法匹配速度，其中匹配速度計(jì)算公式如下：

表1 絕對(duì)傾斜實(shí)驗(yàn)結(jié)果

本文算法得到的匹配點(diǎn)數(shù)量相對(duì)于ASIFT有所減少，平均下降了10%左右。在基于圖像局部特征描述符的匹配算法中，選擇的描述符對(duì)關(guān)鍵點(diǎn)的區(qū)分能力越高，關(guān)鍵點(diǎn)的獨(dú)有特征被描述的越充分最后得到的匹配點(diǎn)的數(shù)量就會(huì)越多，然而這種描述符的生成過程往往非常復(fù)雜，在匹配時(shí)的計(jì)算量較大。本文為了提高匹配速度，在SIFT描述符的基礎(chǔ)上進(jìn)行簡(jiǎn)化操作，最后使用32維描述符執(zhí)行匹配任務(wù)，由于降維后的描述符對(duì)于關(guān)鍵點(diǎn)的區(qū)分能力相對(duì)于SIFT描述符有所下降，所以最終匹配點(diǎn)的數(shù)量有所減少，但是平均仍然保持在ASIFT 90%左右，最好的情況可以達(dá)到96%，從后續(xù)的實(shí)驗(yàn)結(jié)果中可以看到在相對(duì)傾斜較大的情況下甚至超過了ASIFT。在使用最近次近距離算法建立匹配關(guān)系時(shí)，使用本文簡(jiǎn)化后的描述符代替SIFT描述符計(jì)算歐氏距離，每一對(duì)描述符的計(jì)算次數(shù)可以減少64次，所以本文算法執(zhí)行匹配任務(wù)時(shí)大大降低了計(jì)算量，實(shí)驗(yàn)數(shù)據(jù)表明本文算法的匹配速度平均約為ASIFT的1.5倍。

表2 相對(duì)傾斜實(shí)驗(yàn)結(jié)果

2.2 相對(duì)傾斜實(shí)驗(yàn)分析

表2記錄了相對(duì)傾斜圖像集上的實(shí)驗(yàn)結(jié)果，各列含義與表1基本相同，不過此時(shí)第一列表示相對(duì)傾斜的變化。由表中數(shù)據(jù)可知，本文算法在絕對(duì)傾斜等于2的相對(duì)傾斜圖像集上得到的匹配點(diǎn)數(shù)相對(duì)于ASIFT有所減少，匹配速度明顯提高與絕對(duì)傾斜的實(shí)驗(yàn)結(jié)果規(guī)律一致，但是當(dāng)絕對(duì)傾斜增大至4時(shí)，隨著圖像之間相對(duì)傾斜的逐漸增大，本文算法得到的匹配點(diǎn)數(shù)超過了ASIFT,尤其是當(dāng)相對(duì)傾斜大于10的時(shí)候，該規(guī)律非常明顯，而且此時(shí)的匹配速度平均是ASIFT的6倍左右。隨著圖像仿射形變的增大，圖像上可以檢測(cè)到的關(guān)鍵點(diǎn)的數(shù)量會(huì)逐漸減少，而且描述符之間的相似度也會(huì)越來越大因此發(fā)生錯(cuò)誤匹配的概率也會(huì)隨之增加，另外本文算法使用的簡(jiǎn)化描述符對(duì)不同關(guān)鍵點(diǎn)的區(qū)別能力不如SIFT描述符，所以當(dāng)圖像之間的仿射形變較大時(shí)本文算法得到的錯(cuò)配點(diǎn)可能會(huì)更多。如圖7所示，本文算法得到的匹配點(diǎn)數(shù)雖然多于ASIFT,但是也引入了更多的錯(cuò)誤匹配點(diǎn)。

圖5 相對(duì)傾斜為14.3的圖像對(duì)的匹配結(jié)果

3 結(jié)語

本文針對(duì)SIFT描述符維度過高、不具備仿射不變性的缺陷，將簡(jiǎn)化描述符算法與ASIFT模擬機(jī)制相結(jié)合提出一種完全仿射不變的圖像匹配算法，實(shí)驗(yàn)數(shù)據(jù)表明該算法對(duì)于仿射形變較大的圖像依然可以穩(wěn)定工作，而且本文算法的匹配速度明顯快于ASIFT。本文算法使用的簡(jiǎn)化描述符對(duì)于圖像中關(guān)鍵點(diǎn)的區(qū)別能力不如SIFT描述符，在初次匹配結(jié)果中引入了更多的重復(fù)匹配，增加了去除重復(fù)匹配的時(shí)間開銷，不利于匹配速度的優(yōu)化，有時(shí)甚至導(dǎo)致匹配速度低于ASIFT,相對(duì)傾斜為7.7的實(shí)驗(yàn)結(jié)果便屬于此類情況。為了解決該問題，下一步考慮結(jié)合核密度估計(jì)理論建立圖像之間的匹配關(guān)系。

[1]David G Lowe,Distinctive Image Features from Scale-Invariant Keypoints,IEEE International Journal of Computer,vol 60,pp.91-110,2004.

[2]Ke Y,Sukthankar R.PCA-SIFT:A More Distinctive Representation for Local Image Descriptors.Proceedings of the 2004 IEEE Computer Society Conference on IEEE,vol.2,2004,pp.506-513.

[3]Z.Zhou,S.Cheng and Z.Li.MDS-SIFT:An Improved SIFT Matching Algorithm Based on MDS Dimensionality Reduction.2016 3rd International Conference on Systems and Informatics（ICSAI）,Shanghai,2016,pp：896-900.

[4]X.Zhou,K.Wang and J.Fu.A Method of SIFT Simplifying and Matching Algorithm Improvement.2016 International Conference on Industrial Informatics-Computing Technology,Intelligent Technology,Industrial Information Integration（ICIICII）,Wuhan,2016,pp.73-77.

[5]Matas J,Chum O,Urban M,et al.Robust Wide-Baseline Stereo from Maximally Stable Extremal Regions[J].Image and Vision Computing,2004,22（10）:761-767.

[6]W.Hu,W.Zhou and J.Guan.A Modified M-SIFT Algorithm for Matching Images with Different Viewing Angle.2016 IEEE International Conference on Signal and Image Processing（ICSIP）,Beijing,2016：247-250.

[7]Morel J M,Yu G.ASIFT:A New Framework for Fully Affine Invariant Image Comparison[J].SIAM Journal on Imaging Sciences,2009,2（2）:438-469.

[8]Fischler M A,Bolles R C.Random Sample Consensus:a Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography[J].Communications of the ACM,1981,24（6）:381-395.

[9]Moisan L,Stival B.A Probabilistic Criterion to Detect Rigid Point Matches Between Two Images and Estimate the Fundamental Matrix[J].International Journal of Computer Vision,2004,57（3）:201-218.

[10]Lindeberg T.Scale-Space Theory:A Basic Tool for Analyzing Structures at Different Scales[J].Journal of Applied Statistics,1994,21（1-2）:225-270.

[11]C.Harris and M.Stephens.A Combined Corner and Edge Detector,in Proceedings of the Fourth Alvey Vision Conference,Vol.15,1988：147-151.

[12]K.Mikolajczyk and C.Schmid,Indexing Based on Scale Invariant Interest Points,in Proceedings of the 8th International Conference on Computer Vision（ICCV）,2001：525-531.

[13]K.Mikolajczyk and C.Schmid,Scale and Affine Invariant Interest Point Detectors,Int.J.Comput.Vis.,60（2004）：63-86.

[14]D.Lowe,Distinctive Image Features from Scale-Invariant Key Points,Int.J.Comput.Vis.,60（2004）：91-110.

[15]L.F evrier,A Wide-Baseline Matching Library for Zeno,Internship Report.http://www.di.ens.fr/～fevrier/papers/2007-Internsip ReportILM.pdf（2007）.

[16]K.Mikolajczyk and C.Schmid.An Affine Invariant Interest Point Detector,in Proceedings of the Seventh European Conference on Computer Vision（ECCV）,Springer-Verlag,London,2002：128-142.

[17]K.Mikolajczyk and C.Schmid.A Performance Evaluation of Local Descriptors,in Proceedings of the International Conference on Computer Vision and Pattern Recognition,Vol.2,2003,pp.257–2.