基于改進(jìn)SIFT和RANSAC圖像拼接算法研究

馬 強(qiáng)，項(xiàng)昭保，黃良學(xué)，王博化

(重慶郵電大學(xué) 工業(yè)物聯(lián)網(wǎng)與網(wǎng)絡(luò)化控制教育部重點(diǎn)實(shí)驗(yàn)室，重慶 400065)

基于改進(jìn)SIFT和RANSAC圖像拼接算法研究

馬 強(qiáng)，項(xiàng)昭保，黃良學(xué)，王博化

(重慶郵電大學(xué) 工業(yè)物聯(lián)網(wǎng)與網(wǎng)絡(luò)化控制教育部重點(diǎn)實(shí)驗(yàn)室，重慶 400065)

就目前圖像拼接算法復(fù)雜性和RANSAC算法迭代次數(shù)多的問題，文中提出了一種新的圖像拼接算法。通過提取特征點(diǎn)、圖像配準(zhǔn)和加權(quán)平均融合方法，對圖像進(jìn)行拼接。利用改進(jìn)算法提取特征點(diǎn)，減少了算法復(fù)雜度。此外，改進(jìn)的RANSAC算法能夠用來減少迭代次數(shù)。實(shí)驗(yàn)結(jié)果表明：該方法能夠有效減少運(yùn)算量，加快拼接速度，拼接效果較為理想。

圖像拼接；SIFT算法；RANSAC算法；圖像融合

0 引 言

近年來，圖像拼接技術(shù)得到了廣泛關(guān)注。配準(zhǔn)的好壞對圖像拼接的質(zhì)量和效率有很大影響，是圖像拼接的關(guān)鍵[1]。目前使用最廣泛的特征匹配算法是尺度不變特征變換匹配算法[2](Scale Invariant Feature Transform,SIFT)。但是SIFT提取特征點(diǎn)后，必須排除誤匹配點(diǎn)。傳統(tǒng)的隨機(jī)取樣一致性算法[3](RANdom SAmple Consensus,RANSAC)迭代次數(shù)比較多，運(yùn)行比較耗時(shí)，遠(yuǎn)遠(yuǎn)降低了圖像拼接算法的效率。

當(dāng)前主要的圖像配準(zhǔn)方法有灰度信息配準(zhǔn)方法[4]、特征配準(zhǔn)方法[5]和變換域配準(zhǔn)方法[6]。Kasar T等[7]使用歐氏距離調(diào)節(jié)最近鄰(NN)與次近鄰(SCN)距離的比值閾值，從而減少誤匹配，但也容易失去一些正確的匹配點(diǎn)，不能真正提高匹配率。鄒北驥[8]、H. Nicolas等[9]提出基于特征點(diǎn)的中值濾波算法，但該算法不能徹底排除匹配特征點(diǎn)的誤差，而且耗時(shí)。Fang Xianyong等[10]提出RANSAC的初始迭代特征點(diǎn)對用中值濾波來檢測，但誤匹配對沒有得到排除，算法效率沒有得到明顯提高。

就當(dāng)前圖像拼接算法存在復(fù)雜性和RANSAC算法迭代次數(shù)多的問題，文中提出了一種新的圖像拼接算法。采用改進(jìn)SIFT進(jìn)行特征提取，降低了算法的復(fù)雜度。改進(jìn)后的RANSAC算法，提高了算法的效率和配準(zhǔn)穩(wěn)定性。圖像融合選擇加權(quán)平均融合方法，實(shí)現(xiàn)圖像的無縫拼接。

1 SIFT特征提取

1.1 SIFT算法

2004年David G.Lowe提出一種基于尺度空間的、對圖像縮放旋轉(zhuǎn)以及仿射變換仍保持不變的圖形局部特征算子—SIFT[11]。詳細(xì)步驟如下：

(1)構(gòu)建高斯差分尺度空間。

D(x,y,σ)=(G(x,y,kσ)-G(x,y,σ))*I(x,y)=L(x,y,kσ)-L(x,y,σ)

(1)

(2)高斯差分空間中尋找極值點(diǎn)，即特征點(diǎn)。

在整合三維二次函數(shù)后，精確定位極值點(diǎn)的位置和尺度，消除了對比度低和不穩(wěn)定邊響應(yīng)點(diǎn)的點(diǎn)。邊緣響應(yīng)點(diǎn)通過式(2)去除。

(2)

式中，r為控制特征值大小的參數(shù)。

(3)為關(guān)鍵點(diǎn)分配方向。

為了讓特征點(diǎn)具有局部旋轉(zhuǎn)不變性，使用關(guān)鍵點(diǎn)鄰域梯度像素的分布特性為每一個(gè)關(guān)鍵點(diǎn)分配方向參數(shù)，梯度的模和方向見式(3)和式(4)。

m(x,y)=

(3)

(4)

(4)形成特征點(diǎn)描述符。

最初把坐標(biāo)軸旋轉(zhuǎn)成關(guān)鍵點(diǎn)的主方向來保證旋轉(zhuǎn)不變性，然后把以關(guān)鍵點(diǎn)為中心取的窗口平均分為16個(gè)小塊，在每一個(gè)小塊的8個(gè)方向梯度直方圖上繪制每一個(gè)梯度方向的累加值，構(gòu)成一個(gè)種子點(diǎn)，則每一個(gè)種子點(diǎn)含有8個(gè)方向的信息向量。描述了16個(gè)種子點(diǎn)，這是由128維矢量描述的特征點(diǎn)。

1.2 改進(jìn)的SIFT特征點(diǎn)描述符

在步驟(3)中，特征點(diǎn)被分配一個(gè)主方向，并實(shí)現(xiàn)由局部區(qū)域特征點(diǎn)的抗旋轉(zhuǎn)能力。考慮到圓具有良好的旋轉(zhuǎn)不變性，蘭視爽等[12]利用圓形區(qū)域周圍的特征點(diǎn)構(gòu)造SIFT特征描述子，當(dāng)圖像發(fā)生旋轉(zhuǎn)時(shí)，子環(huán)中的像素位置發(fā)生了變化，其余的特征保持不變。

首先，計(jì)算圓環(huán)內(nèi)每一個(gè)像素的梯度值和方向，統(tǒng)計(jì)出8個(gè)方向的梯度累加值。其次，對梯度累加值從大到小排序，確保旋轉(zhuǎn)后排序值不變。最后，對這一向量進(jìn)行歸一化處理。

改進(jìn)后的SIFT描述符自身具備旋轉(zhuǎn)不變性，不需要通過旋轉(zhuǎn)坐標(biāo)軸來保證特征描述符的旋轉(zhuǎn)不變性。同時(shí)，改進(jìn)后的篩選描述符被減小到64個(gè)維度，從而大大提高了工作效率，降低了匹配特征點(diǎn)的復(fù)雜性。

2 特征點(diǎn)匹配與篩選

圖像SIFT特征點(diǎn)提取后，從待匹配圖像中選擇正確特征點(diǎn)。林陸君等[13]采用優(yōu)先k-d樹從基準(zhǔn)圖像中查尋與該點(diǎn)歐氏距離最近的前兩個(gè)特征點(diǎn)，獲得距離最近的與次近的比值，若比值小于給定的閾值，則認(rèn)為距離最近的點(diǎn)為匹配點(diǎn)。歐氏距離公式為：

(5)

其中，m=(m1,m2,…,mp)和n=(n1,n2,…,np)分別是兩張圖的特征向量。

2.1 傳統(tǒng)的RANSAC算法

為了增強(qiáng)算法的魯棒性，周建平等[14]采用傳統(tǒng)的RANSAC算法排除誤匹配。步驟如下：

(1)按照置信概率P和數(shù)據(jù)錯(cuò)誤率ω，以及所需的最小量的數(shù)據(jù)m來計(jì)算模型參數(shù)，由式(6)計(jì)算需要選擇的抽樣數(shù)量M：

(6)

(2)隨機(jī)選擇原始數(shù)據(jù)樣本，估計(jì)每個(gè)樣本的樣本數(shù)量為模型參數(shù)所需的最小數(shù)據(jù)，并計(jì)算樣本的相應(yīng)模型參數(shù)。

(3)使用所有的原始數(shù)據(jù)來測試模型的參數(shù)，得到每個(gè)模型參數(shù)的正確數(shù)目；重復(fù)(2)、(3)步，直到完成M組抽樣的處理。

(4)找出最優(yōu)模型參數(shù)所對應(yīng)的所有inliers，并用這些數(shù)據(jù)計(jì)算最終的模型參數(shù)。

2.2 改進(jìn)的RANSAC算法

當(dāng)匹配點(diǎn)中存在較多誤匹配時(shí)，RANSAC的隨機(jī)采樣次數(shù)就會增多，造成運(yùn)行緩慢，求出的變換矩陣精度不高，要對其進(jìn)行改進(jìn)。剔除原理如下：若(Pi，Qi)和(Pj，Qj)是一對正確匹配點(diǎn)，那么Pi和Pj的距離d(Pi,Pj)與Qi和Qj的距離d(Qi,Qj)是相似的。所以，利用Pi與第一幅圖中所有感興趣點(diǎn)Pj的關(guān)系和Qi與第二幅圖中所有感興趣點(diǎn)Qj的相似性來評價(jià)兩點(diǎn)的對應(yīng)關(guān)系，提出如下評價(jià)函數(shù)：

(7)

改進(jìn)后RANSAC算法步驟如下：

(1)計(jì)算ω(i)的所有值；

(2)求出全部ω(i)的均值ω；

(3)判斷ω(i)，如果ω(i)>0.8ω,Pi和Qi是正確匹配點(diǎn)，則保留，否則刪除；

(4)將篩選出來的正確特征點(diǎn)作為RANSAC算法的初始迭代特征點(diǎn)對，求出精確的單應(yīng)性矩陣H。

3 圖像融合

圖像配準(zhǔn)好后，如果只是一個(gè)簡單的疊加，會使圖像模糊而且有明顯的縫合線，造成不好的拼接。文中選用加權(quán)平滑法。

(8)

d1和d2的計(jì)算如下：設(shè)當(dāng)前像素的橫坐標(biāo)為xi，重疊區(qū)域左右邊界的橫坐標(biāo)分別為xl和xr，那么

4 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)所用的平臺為VS2010和OpenCV，圖像大小為340×280。選用4種典型的測試圖進(jìn)行測試，如圖1所示。

特別說明的是：4組圖像中左圖為參考圖像，右圖為待拼圖像。

首先，采用SIFT算法分別對圖1中的4組圖進(jìn)行特征提取，確定圖2(a)中SIFT特征點(diǎn)個(gè)數(shù)分別為1 376和1 071，圖2(b)中的特征點(diǎn)個(gè)數(shù)分別為350和246，圖2(c)中特征點(diǎn)個(gè)數(shù)分別為839和698，以及圖2(d)的特征點(diǎn)個(gè)數(shù)分別為773和607。圖中標(biāo)注的箭頭表示特征點(diǎn)的梯度信息，其中箭頭方向表示特征點(diǎn)的梯度方向，而箭頭長度表示特征點(diǎn)的梯度幅值大小。

然后，通過k-d樹算法分別計(jì)算圖2特征點(diǎn)，得到粗匹配點(diǎn)對并標(biāo)注在測試圖中：566對(圖3(a))、121對(圖3(b))、101對(圖3(c))和230對(圖3(d))。

圖1 未提取特征點(diǎn)的測試圖

圖2 SIFT特征梯度描述

圖3 特征粗匹配點(diǎn)對(1)

最后，通過RANSAC算法消除圖3中存在的誤匹配點(diǎn)對并計(jì)算出圖像間的透視變換矩陣H，將待拼接圖像變換到參考圖像坐標(biāo)系后進(jìn)行漸進(jìn)漸出圖像融合，得到最后的拼接效果圖。

由于在DOG空間中尋找極值點(diǎn)需要在三維平面中進(jìn)行搜索并且搜索的層數(shù)較多造成圖3中檢測的特征點(diǎn)較大，搜索時(shí)間長。同樣，圖3中顯示特征點(diǎn)粗匹配數(shù)目較大，然而計(jì)算透射變換矩陣H僅需要4對特征點(diǎn)對，這導(dǎo)致RANSAC算法剔除誤匹配點(diǎn)的計(jì)算量增大，從而消耗內(nèi)存，計(jì)算時(shí)間較長。

采用文中提出的改進(jìn)的SIFT和RANSAC算法，對圖像進(jìn)行特征點(diǎn)提取，并通過設(shè)定閾值T的大小來限制圖像特征點(diǎn)的個(gè)數(shù)。經(jīng)過粗匹配后，粗匹配點(diǎn)對分別降為：199對(圖4(a))、15對(圖4(b))、18對(圖4(c))和18對(圖4(d))。

圖4 特征粗匹配點(diǎn)對(2)

采用RANSAC算法來消除誤匹配點(diǎn)對并用透視變換公式分別計(jì)算出圖3中待拼接圖像的坐標(biāo)變換矩陣H中的參數(shù)：

矩陣H的參數(shù)確定后，即分別得到了待拼接圖像的透射變換圖，將得到的透視圖與圖1中的參考圖像分別進(jìn)行漸進(jìn)漸出融合，得到圖5所示的最終融合圖像。

圖5 融合圖

表1為選用同一組測試圖所得的特征點(diǎn)個(gè)數(shù)、匹配點(diǎn)數(shù)及拼接所消耗時(shí)間。

由表可分析得出,采用所提方法的粗匹配對數(shù)、一致集的匹配對數(shù)、匹配精度和拼接耗時(shí)都有了明顯的改善。

表1 SIFT算法與改進(jìn)SIFT算法對圖像的實(shí)驗(yàn)結(jié)果

5 結(jié)束語

文中提出了一種改進(jìn)SIFT和RANSAC的圖像拼接算法，提高了配準(zhǔn)速率，相對于SIFT算法的圖像拼接有明顯的提高。由于初始配準(zhǔn)中存在錯(cuò)誤匹配點(diǎn)，采用RANSAC算法剔除誤匹配點(diǎn)來獲得準(zhǔn)確的區(qū)域匹配，和坐標(biāo)變換矩陣的特征點(diǎn)計(jì)算是正確的。這樣，既滿足了單應(yīng)性矩陣的估算精度，又具備一定的拼接效果和魯棒性。

[1] 張 琳,褚龍現(xiàn).基于全局拼接的航拍圖像拼接算法研究[J].計(jì)算機(jī)仿真,2012,29(4):282-285.

[2] 萬 雪,張祖勛,柯 濤.一種利用零交叉點(diǎn)理論的改進(jìn)SIFT特征提取算法[J].武漢大學(xué)學(xué)報(bào):信息科學(xué)版,2013,38(3):270-273.

[3] 雒偉群,高 屹.基于改進(jìn)RANSAC算法的圖像拼接方法[J].科技創(chuàng)新與應(yīng)用,2015,26(5):21-22.

[4] 廖 飛,葉瑋瓊,王鵬程,等.基于SIFT特征匹配的圖像拼接算法[J].湖南工業(yè)大學(xué)學(xué)報(bào),2014,28(1):71-75.

[5] 焦麗龍,韓 燮,李定主.改進(jìn)的基于特征點(diǎn)匹配的圖像拼接融合算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2014,35(3):918-922.

[6] 黃大坤,陸冬良,嚴(yán)志明,等.多圖無縫拼接的配準(zhǔn)算法[J].微型電腦應(yīng)用,2014,30(2):62-65.

[7]KasarT,RamakrishnaaAG.Block-basedfeaturedetectionandmatchingformosaicingofcamera-captureddocumentimages[C]//ProcofIEEEregion10conference.Taipei:IEEE,2007:1-4.

[8] 鄒北驥,阮 鵬,向 遙，等.一種精確匹配的全景圖自動(dòng)拼接算法[J].計(jì)算機(jī)工程與科學(xué),2010,32(8):60-63.

[9]NicolasH.Newmethodsfordynamicmosaicking[J].IEEETransactionsonImageProcessing,2001,10(8):1239-1251.

[10]FangXianyong,ZhangMingmin,PanZhigeng,etal.Anewmethodofmanifoldmosaicforlargedisplacementimages[J].JournalofComputerScienceandTechnology,2006,21(2):218-223.

[11] 周 穎.基于SIFT算法的圖像特征匹配[J].現(xiàn)代計(jì)算機(jī),2015(5):63-68.

[12] 蘭世爽,孫勁光.基于改進(jìn)SIFT的抗幾何攻擊的數(shù)字水印[J].計(jì)算機(jī)工程與應(yīng)用,2011,49(7):200-203.

[13] 林陸君,孫玲玲,李訓(xùn)根,等.一種改進(jìn)的基于模板匹配的顯微細(xì)胞圖像拼接算法[J].計(jì)算機(jī)應(yīng)用與軟件,2010,27(1):108-110.

[14] 周建平,楊金坤,鄭 宇.基于改進(jìn)SIFT特征匹配的視頻拼接—在倒車系統(tǒng)中的應(yīng)用[J].企業(yè)技術(shù)開發(fā),2011,30(22):70-71.

Research on Panorama Image Mosaic Algorithm Based on Improved SIFT and RANSAC

MA Qiang,XIANG Zhao-bao,HUANG Liang-xue,WANG Bo-hua

(Key Laboratory of Industrial Internet of Things & Network Control of MOE, Chongqing University of Posts and Telecommunications,Chongqing 400065,China)

In order to solve the problems of the complexity for the image mosaic algorithm and the large number of iteration for RANSAC,a panorama image mosaic algorithm is proposed in this paper.By feature points extraction,the image registration and weighted average fusion method,image stitching is conducted.The improved algorithm is used to extract the feature points,reducing the complexity of algorithm.In addition,the improved RANSAC algorithm can be used to reduce the number of iterations.Experimental results show that the improved method has lower computing load and increases the speed,besides,splicing efficiency has been significantly improved.

image mosaic;SIFT;RANSAC;image fusion

2015-09-14

2015-12-22

時(shí)間：2016-03-22

國家自然科學(xué)基金資助項(xiàng)目(60975008)；重慶市教委科學(xué)技術(shù)研究項(xiàng)目(KJ130529)

馬 強(qiáng)(1990-)，男，碩士，研究方向?yàn)閳D像處理；項(xiàng)昭保，教授，研究方向?yàn)樘烊换衔锏姆蛛x純化、結(jié)構(gòu)鑒定和結(jié)構(gòu)修飾。

http://www.cnki.net/kcms/detail/61.1450.TP.20160322.1522.104.html

TP301.6

A

1673-629X(2016)04-0061-05

10.3969/j.issn.1673-629X.2016.04.013