一種改進的基于SURF特征匹配的圖像拼接算法

李海洋,張睿哲

(1.綿陽師范學院 數學與計算機科學學院, 四川 綿陽 621000;

2.平頂山學院 計算機科學與技術學院,河南 平頂山 467002)

?

一種改進的基于SURF特征匹配的圖像拼接算法

李海洋1,張睿哲2

(1.綿陽師范學院 數學與計算機科學學院, 四川 綿陽 621000;

2.平頂山學院 計算機科學與技術學院,河南 平頂山 467002)

摘要:針對快速魯棒特征(SURF)算法的拼接結果圖像，會出現明顯的拼接線與過渡帶的問題,提出一種改進的基于SURF特征匹配的圖像拼接算法。在剔除誤配點時,采用改進的隨機抽樣一致(RANSAC)算法調整采樣概率,以更少的時間獲取正確模型,提高算法效率。在圖像融合時,先對輸入圖像進行亮度均衡預處理,然后再使用加權平滑算法進行融合,從而消除結果圖的拼接線和過渡帶,提高圖像拼接質量。實驗表明,改進算法能保持SURF算法的優良特性,進一步提高SURF算法匹配效率,并能有效消除拼接線和過渡帶,使圖像拼接質量得到顯著提高。

關鍵詞:圖像拼接；快速魯棒特征；隨機抽樣一致；加權平滑算法；亮度均衡

圖像拼接是將相互間具有重疊區域的圖像序列進行空間匹配對準,最終拼接為一幅具有較寬視角全景圖像的技術[1]。目前被廣泛應用和研究的圖像拼接技術是基于特征點的圖像拼接技術。2004 年,LOWE[2]提出了尺度不變特征描述算子(SIFT),對光照變化、幾何變形、分辨率差異、旋轉具有一定不變性；但SIFT 算法計算量大,難以滿足實時性應用的要求。2006年,BAY，et al[3]提出了SURF算法,對SIFT算法進行了改進。SURF算法不但繼承了SIFT算法的優點,而且具有更好的魯棒性和更快的計算速度,因此被廣泛應用于圖像配準。2010年,劉奇，等[4]將SURF算法應用于圖像拼接,取得了良好的拼接效果。2013年,韓天慶，等[5]基于SURF特征點匹配,采用空間約束方法,取得了較好的無人機影像拼接效果。桂振文，等[6]改進并提高了SURF算法的配準效率,并應用于智能手機,實現了對場景的實時識別。然而,以上算法仍然存在一些不足。有的算法提高了圖像拼接質量,但卻犧牲了拼接效率;有的算法提高了拼接效率,但卻降低了拼接質量。因此,如何改進SURF算法,同時獲取更好的圖像拼接質量和拼接效率,還需要進一步研究。

RANSAC是由 FISCHLER，et al[7]提出的一種采用迭代法來估計參數的數學模型,具有精度高、魯棒性強等優點,常常用于圖像配準,對誤配點進行剔除；但是,用RANSAC計算參數時,迭代次數多,運算耗時。劉坤，等[8]提出一種概率引導的RANSAC算法,通過調整每個樣本點的采樣概率,使得正確樣本和正確模型被采樣的概率得到提高,迭代次數較少,能有效提高RANSAC算法的效率。張紅民，等[9]提出一種改進的相鄰概率隨機抽樣一致性算法,在數據外點率較高的情況下,能有效減少迭代次數,縮短算法時間,從而提高了RANSAC算法效率。在圖像融合時,張亞娟[10]對平均值法、加權平滑法、最大值法等常見融合算法進行了對比分析和綜合改進,獲得了較為滿意的圖像融合結果。閆莉萍，等[11]提出一種新的目標函數, 結合亮度最大值和加權平滑法,對目標函數進行迭代尋優, 能有效改善圖像融合效果。

筆者提出了一種改進的基于SURF的圖像拼接算法。在剔除誤配點時,采用了文獻[8-9]提出的改進的概率隨機抽樣一致性算法,通過不斷調整采樣概率,從而以更少的時間獲取正確模型,提高算法效率。在圖像融合時,借鑒文獻[10-11]的思想,先對輸入圖像進行亮度均衡預處理,然后再使用加權平滑算法進行融合,從而消除結果圖的拼接線和過渡帶,提高圖像拼接質量。

1基于SURF 的圖像拼接算法

1.1SURF 特征點的提取與匹配

SURF特征點提取主要包括判斷特征點位置,建立尺度空間,確定特征點主方向,構建特征向量等步驟。

SURF在判斷特征點位置時,通過盒型濾波近似地代替二階高斯濾波,然后利用積分圖像來加速卷積速度。設Dxx，Dxy，Dyy為近似的不同方向的盒型濾波模板,w是個權重系數(一般取w=0.9),經簡化近似后,Hessian矩陣的行列式如式(1)所示：

(1)

然后,采用不同尺度的濾波模板與圖像做卷積運算,得到不同尺度下的濾波響應值,建立尺度空間。

通過對扇形滑動窗口內圖像的Haar小波的響應值進行累加,從而得到向量(mw,θw),其中,

(2)

則特征點主方向為最長向量對應的方向,即:

(3)

在構建特征向量時,首先以特征點為中心,沿特征點主方向構造一個20s×20s的矩形區域,并劃分為4×4 個子窗口,則每個子窗口中具有 5s×5s個像元。然后,每個子窗口用尺寸為2s的Haar小波模板計算其響應值。最后,統計出水平方向和豎直方向的Haar小波響應∑dx，∑|dx|，∑dy，∑|dy|,從而得到第i個子窗口的特征向量:

提取出圖像的特征點后,SURF通過計算兩個特征點描述向量的歐氏距離進行特征點匹配。設,某特征點描述符為pi,其最近和次近的兩個相鄰特征點的描述符為qi1和qi2。兩組描述符pi與qi1、pi與qi2的歐氏距離比值如式(4)所示。

(4)

設,閾值為r0,若rr0,則點對(pi,qi1) 為匹配點,否則為非匹配點。

1.2圖像配準

根據找到的匹配特點對,可計算出圖像間的坐標轉換關系,即兩幅圖像之間的變換矩陣。

設,圖像間的變換為投影變換，那么，

若p=(x,y),q=(x′,y′)是匹配的特征點對,則投影變換公式為:

(5)

由投影變換公式可計算出H的各自由度參數hi(i=0,1,2,…,7),并以此作為初始值,通過迭代精煉H,可進一步確定特征點的對應,直到對應點數目不變為止,從而完成圖像配準。

1.3誤配點剔除

RANSAC 是一種采用迭代法來估計參數的數學模型,具有可靠、穩定、精度高、魯棒性強等優點。因此,文獻[4-6,10-11]在圖像配準時,均采用RANSAC對圖像變換矩陣進行精煉,以剔除誤配點,提高圖像配準精度。使用RANSAC剔除誤配點時,首先在所有匹配點中任取兩點確定一條直線進行直線擬合,在擬合誤差距離范圍內的點稱為內點,否則為外點,如圖1所示。

圖1　RANSAC直線估計Fig.1　Linear estimates of RANSAC

然后,在內點集中重新計算出一條新的直線進行擬合,通過不斷迭代,直到找到一個最大內點數量的擬合作為擬合結果,即可剔除誤配點。

1.4圖像融合

圖像融合算法中常用的是加權平滑法。設,融合結果圖為I,兩幅待拼接圖像的重疊區為I1和I2,則加權平滑法圖像融合如式(6)所示。

(6)

2改進的基于SURF的圖像拼接算法

用RANSAC來剔除圖像配準的誤配點時,迭代次數越多,參數估計的精度越高。但是,用RANSAC計算參數時,迭代次數越多,運算越耗時。另外,由于加權平滑法在輸入圖像接合部位采用了平滑過渡,因此可以有效消除拼接線。在輸入圖像亮度一致情況下,使用加權平滑法就能達到較好的融合效果。但是,在輸入圖像亮度差異較大情況下,由于加權平滑法只是對兩幅待拼接圖像的重疊區進行平滑處理,所以仍會在重疊區形成較為明顯的過渡帶。因此,需要對經典的基于SURF的圖像拼接算法進行拼接效率和拼接質量的改進。

2.1RANSAC改進

在每次隨機選取子樣本時, RANSAC 算法的采樣概率相等,并需要多次迭代采樣才能保證至少有一次采樣獲得正確模型。所以,可以通過改進隨機采樣的過程,利用每次抽取的最小子樣本來估計模型參數, 再根據該模型調整子樣本在后面抽樣中被選取的概率。 經過不斷迭代抽取檢驗之后, 獲得正確臨時模型的概率逐漸被提高,從而花費較少的時間獲取正確模型,就能提高算法效率。

概率閾值為p;臨時內點集S, (Si,Sj)是S中任意點對,其歐氏距離d=‖Si-Sj‖,歐氏距離閾值為D。改進RANSAC算法流程[8-9]如圖2所示。

圖2改進RANSAC算法流程Fig.2　Process of improved RANSAC algorithm

2.2圖像融合改進

為了獲得自然的拼接結果圖,筆者采用直方圖均衡化方法對輸入圖像進行亮度預處理,使輸入圖像亮度達到均衡,然后再使用加權平滑法進行圖像融合,這樣既不會產生過渡帶,又能有效消除拼接線。具體操作方法如下。

1) 將重疊區圖像直方圖歸一化,獲得重疊區像素值的概率密度函數的均衡化公式。首先進行重疊區圖像直方圖計算,由于重疊區圖像直方圖表示重疊區像素值頻率,所以將其每個頻率除以重疊區總的像素就可得每個像素值出現的概率p(w),由此得到重疊區像素值的累積分布函數如下:

(7)

式中：w為任意變量。

2) 根據式(7),建立輸入圖像像素值映射關系,對圖像的每個像素進行映射調整。

設,輸入圖像為I1、I2,取直方圖較為平和的圖像(如I1)作為參考圖像,對I2的每個像素值(0≤g≤255)進行調整,使I2按I1的光照調整,如圖3所示。

圖3　圖像光照均衡的累積分布函數圖Fig.3　Cumulative distributed functionof the luminance equilibrium image

由圖3可知,參考圖和待調整圖分別在g1和g2像素值下具有相同的累積分布函數值,即:FCD(g1)=FCD(g2)。然后,把I2圖像中所有像素值為g1的像素映射為g2。按照以上類似操作,對I2所有灰度級進行調整。如果待調整圖和參考圖具有相同的累積分布函數值,則將待調整圖像素值調整為參考圖對應的像素值;如果參考圖和待調整圖沒有相同的累積分布函數值(圖3所示的長橫虛線),則待調整圖在該灰度級保持原有像素值。

3) 將調整后圖像作為輸入圖,使用加權平滑法對其進行融合。由于經過映射調整后的輸入圖具有基本一致的亮度,因此能消除拼接線和過渡帶,生成較為自然的拼接結果圖。

3實驗結果和分析

3.1實驗環境與數據

本研究在多幅圖像上對SURF算法和本文算法進行了圖像拼接實驗。實驗環境如下:CPU為IntelCorei7 @ 2.67GHz,內存4GB,顯卡NvidiaNVS3100M,操作系統Windows7,開發軟件為MatlabR2012a。下面以其中一組實驗圖像為例給出實驗結果。實驗圖像原圖如圖4所示,原圖4-a圖像大小為61KB,尺寸527*393像素;原圖4-b圖像大小為167KB,尺寸522*387像素。這一組圖像是通過手機在不同視角手持拍攝,保證了待拼接圖像在尺度和亮度上的差異。

圖4　實驗原圖Fig.4　Original images of experments

3.2圖像配準實驗

為了證明對RANSAC改進的有效性,本文給出了SURF+RANSAC及SURF+改進RANSAC的圖像配準實驗結果,如圖5所示。

圖5　不同算法的圖像配準實驗結果Fig.5　Image matching experiment results of different algorithms

其中,圖5-a是經典的SURF+RANSAC配準結果,圖5-b是本文SURF+改進RANSAC配準結果。通過這兩幅結果圖像的比較可以看出(如圖5-a中箭頭所示,誤配點已經被剔除),本文的SURF+改進RANSAC配準結果更加精確,說明了對RANSAC的改進有效,比經典RANSAC具有更好的提純效果。

為了定量說明改進RANSAC的有效性,本研究對RANSAC與改進RANSAC進行了性能比較,比較結果如表1所示。

表1　RANSAC與改進RANSAC的性能比較

從表1可以看出,相比于經典的SURF+RANSAC算法,本文算法在特征點檢測數目和匹配的點數上均略有降低,在運行時間上有大幅降低。

以上結果說明了本文算法以犧牲較小的穩定性為代價,取得了配準質量的提高,并大幅提高了配準效率。

3.3圖像拼接實驗

為了證明對本文改進融合算法的有效性,本文給出了SURF+RANSAC直接拼接(以下簡稱算法A)、經典的SURF+RANSAC+加權平滑融合(以下簡稱算法B)以及本文算法(SURF+改進RANSAC+亮度均衡+加權平滑融合)最終的圖像拼接實驗結果,如圖6所示。

圖6　三種算法實驗結果比較Fig.6　Image stitching experiment results ofthree different algorithms

圖6-a是算法A的圖像拼接結果,可以看出,算法A拼接結果存在非常明顯的拼接線,如圖6-a向右箭頭和向下箭頭所指。

圖6-b是算法B的圖像拼接結果,可以看出，算法B拼接結果消除了明顯的拼接線,但在圖像重疊區部分出現了過渡帶,如圖6-b左右箭頭所指區域。

圖6-c是本文算法的圖像拼接結果,可以看出,本文算法不但消除了算法A的拼接線,而且沒有產生算法B的過渡帶,具有自然的視覺效果。

為了進一步說明本文算法的有效性,本研究在圖像拼接實驗的同時,記錄了以上三種算法的運行時間,結果如表2所示。

表2三種算法的運行時間比較

Table2Runningtimesofthedifferentalgorithms

ms

從表2可以看出,算法A運行時間最少,本文算法次之,算法B運行時間最長。相對于算法B,本文算法運行時間較少,本文算法效率略微占優,大約提高效率10%。

綜上所述,算法A效果差而效率高;算法B效果較好但效率最低;本文算法不但效果最好,而且具有較好的效率。本文算法拼接效果優于算法B的原因在于對圖像進行加權平滑融合前,對輸入圖像進行了亮度均衡,因而提高了圖像融合質量。相對于算法B,本文算法拼接效率提高的原因在于在特征點提純時,對經典RANSAC進行了改進,能以較少的迭代次數找到正確的估計模型,因而較大幅度地提高了效率。相對于算法B,本文算法最終效率提高不大的原因在于,本文在改進圖像融合算法時進行了亮度均衡預處理,增加了圖像融合時間,需進一步加以研究改進。此外,本文算法在圖像融合前采用了直方圖均衡化方法對輸入圖像進行亮度預處理,應選擇直方圖較為平和的圖像作為參考圖像,否則容易造成最終結果圖失真,這一缺點也需要研究克服。

4結論

筆者提出了一種改進的基于SURF特征匹配的圖像拼接算法,通過改進RANSAC降低了圖像配準迭代次數,提高了算法效率;通過改進加權平滑算法實現拼接線和過渡帶的消除。實驗結果表明,改進算法在效率有所提高情況下,能取得比經典SURF拼接算法更優的拼接效果。

參考文獻：

[1]朱琳,王瑩,劉淑云,等.基于改進快速魯棒特征的圖像快速拼接算法[J].計算機應用,2014,34(10):2944-2947.

[2]LOWEDG.Distinctiveimagefeaturesfromscale-invariantkeypoints[J].InternationalJournalofComputerVision,

2004,60(2):91-110.

[3]BAYH,TUYTELAARST,GOOLLV.SURF:speededuprobustfeatures[J].ComputerVisionandImageUnderstanding,2008,110(3):346-359.

[4]劉奇,何明一.基于SURF特征匹配的圖像拼接算法[J].測控技術,2010,29(10):27-31.

[5]韓天慶,趙銀娣,劉善磊,等.空間約束的無人機影像SURF特征點匹配[J].中國圖象圖形學報,2013,18(6):669-676.

[6]桂振文,陳靖,劉越,等.一種智能手機上的場景實時識別算法[J].自動化學報,2014,40(1):83-91.

[7]FISHLERMA,BOLLESRC.Randomsampleconsensus:aparadigmformodelfittingwithapplicationstoimageanalysisandautomatedcartography[J].CommunicationsoftheACM,1981,24(6):381-395.

[8]劉坤,葛俊鋒,羅予頻,等.概率引導的隨機采樣一致性算法[J].計算機輔助設計與圖形學學報,2009(5):657-662.

[9]張紅民,曾禎.一種改進的相鄰概率隨機抽樣一致性算法[J].激光雜志,2013,34(5):29-30.

[10]張亞娟.基于SURF特征的圖像與視頻拼接技術的研究[D].西安:西安電子科技大學,2013.

[11]閆莉萍,劉寶生,周東華.一種新的圖像融合及性能評價方法[J].系統工程與電子技術,2007,29(4):509-513.

(編輯：朱倩)

An Improved Image Stitching Algorithm Based on SURF Feature Matching

LI Haiyang1,ZHANG Ruizhe2

(1.SchoolofMath&ComputerScience,MianyangNormalUniversity,MianyangSichuan621000,China;2.ComputerScienceandTechnicAcademyDepartment,PingdingshanUniversity;PingdingshanHenan467002,China)

Abstract:Speed up Robust Features(SURF) algorithm is widely used in the field of image processing owing to its excellent invariance of scale, rotation, illumination and its faster calculation speed than SIFT. However, it is still hard to meet the demands in some high real-time applications and its calculation speed still needs to be further improved. In addition, when used in image matching, its image stitching results appear obvious stitching seam and transition zone because of the differences of the luminance in the original images. In order to overcome these disadvantages, this study proposes an improved image stitching algorithm based on SURF feature matching. In image matching, the random sample consensus (RANSAC) algorithm is improved to eliminate the false matching points and to reduce the iterations,resulting in improved efficiency of algorithm. In image fusion, the weighted average algorithm is improved to eliminate the stitching seam and the transition zone, resulting in improved quality of image stitching. Experimental results show that the improved algorithm can keep up the stability of SURF and effectively eliminate the stitching seam and the transition zone while its matching efficiency is further improved. Compared with classic image stitching algorithm based on SURF, the proposed algorithm has better stitching results and higher efficiency.

Key words:image stitching;speed up robust features;random sample consensus;weighted average algorithm;luminance equalization

中圖分類號:TP391.41

文獻標識碼:A

DOI：10.16355/j.cnki.issn1007-9432tyut.2016.01.018

作者簡介：李海洋(1972-)，男，四川雙流人，副教授，主要從事圖形圖像處理、優化技術的研究，(E-mail)lhy1301@126.com

基金項目：四川省科技廳資助項目：基于色彩熵的半監督圖像檢索研究(2012JYZ013)；四川省教育廳資助項目(12ZB070)；綿陽師范學院資助項目(2013A12)

收稿日期：2015-05-19

文章編號:1007-9432(2016)01-0091-05