李海洋,張睿哲

(1.綿陽師范學(xué)院 數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院, 四川 綿陽 621000;

2.平頂山學(xué)院 計算機(jī)科學(xué)與技術(shù)學(xué)院,河南 平頂山 467002)

?

一種改進(jìn)的基于SURF特征匹配的圖像拼接算法

李海洋1,張睿哲2

(1.綿陽師范學(xué)院 數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院, 四川 綿陽 621000;

2.平頂山學(xué)院 計算機(jī)科學(xué)與技術(shù)學(xué)院,河南 平頂山 467002)

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

關(guān)鍵詞:圖像拼接；快速魯棒特征；隨機(jī)抽樣一致；加權(quán)平滑算法；亮度均衡

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

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

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

1基于SURF 的圖像拼接算法

1.1SURF 特征點的提取與匹配

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

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

(1)

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

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

(2)

則特征點主方向為最長向量對應(yīng)的方向,即:

(3)

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

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

(4)

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

1.2圖像配準(zhǔn)

根據(jù)找到的匹配特點對,可計算出圖像間的坐標(biāo)轉(zhuǎn)換關(guān)系,即兩幅圖像之間的變換矩陣。

設(shè),圖像間的變換為投影變換，那么，

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

(5)

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

1.3誤配點剔除

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

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

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

1.4圖像融合

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

(6)

2改進(jìn)的基于SURF的圖像拼接算法

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

2.1RANSAC改進(jìn)

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

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

圖2改進(jìn)RANSAC算法流程Fig.2　Process of improved RANSAC algorithm

2.2圖像融合改進(jìn)

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

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

(7)

式中：w為任意變量。

2) 根據(jù)式(7),建立輸入圖像像素值映射關(guān)系,對圖像的每個像素進(jìn)行映射調(diào)整。

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

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

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

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

3實驗結(jié)果和分析

3.1實驗環(huán)境與數(shù)據(jù)

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

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

3.2圖像配準(zhǔn)實驗

為了證明對RANSAC改進(jìn)的有效性,本文給出了SURF+RANSAC及SURF+改進(jìn)RANSAC的圖像配準(zhǔn)實驗結(jié)果,如圖5所示。

圖5　不同算法的圖像配準(zhǔn)實驗結(jié)果Fig.5　Image matching experiment results of different algorithms

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

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

表1　RANSAC與改進(jìn)RANSAC的性能比較

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

以上結(jié)果說明了本文算法以犧牲較小的穩(wěn)定性為代價,取得了配準(zhǔn)質(zhì)量的提高,并大幅提高了配準(zhǔn)效率。

3.3圖像拼接實驗

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

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

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

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

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

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

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

Table2Runningtimesofthedifferentalgorithms

ms

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

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

4結(jié)論

筆者提出了一種改進(jìn)的基于SURF特征匹配的圖像拼接算法,通過改進(jìn)RANSAC降低了圖像配準(zhǔn)迭代次數(shù),提高了算法效率;通過改進(jìn)加權(quán)平滑算法實現(xiàn)拼接線和過渡帶的消除。實驗結(jié)果表明,改進(jìn)算法在效率有所提高情況下,能取得比經(jīng)典SURF拼接算法更優(yōu)的拼接效果。

參考文獻(xiàn)：

[1]朱琳,王瑩,劉淑云,等.基于改進(jìn)快速魯棒特征的圖像快速拼接算法[J].計算機(jī)應(yīng)用,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].測控技術(shù),2010,29(10):27-31.

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

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

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

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

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

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

[11]閆莉萍,劉寶生,周東華.一種新的圖像融合及性能評價方法[J].系統(tǒng)工程與電子技術(shù),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

文獻(xiàn)標(biāo)識碼:A

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

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

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

收稿日期：2015-05-19

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