李記鵬，尹顏朋

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

0 引言

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

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

1 基于簡化描述符的仿射不變匹配算法

1.1 基于圓形鄰域的簡化描述符

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

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

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

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

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

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

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

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

圖2 描述符對比

1.2 仿射不變匹配算法

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

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

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

假設(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的變換如下：

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

圖3 SVD分解的幾何解釋

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

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

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

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

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

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

圖4 仿射不變匹配算法

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

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

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

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

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

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

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

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

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

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

3 結(jié)語

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