基于改進SIFT和RANSAC圖像拼接算法研究

馬 強，項昭保，黃良學，王博化

(重慶郵電大學 工業物聯網與網絡化控制教育部重點實驗室，重慶 400065)

基于改進SIFT和RANSAC圖像拼接算法研究

馬 強，項昭保，黃良學，王博化

(重慶郵電大學 工業物聯網與網絡化控制教育部重點實驗室，重慶 400065)

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

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

0 引 言

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

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

就當前圖像拼接算法存在復雜性和RANSAC算法迭代次數多的問題，文中提出了一種新的圖像拼接算法。采用改進SIFT進行特征提取，降低了算法的復雜度。改進后的RANSAC算法，提高了算法的效率和配準穩定性。圖像融合選擇加權平均融合方法，實現圖像的無縫拼接。

1 SIFT特征提取

1.1 SIFT算法

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

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

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

(1)

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

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

(2)

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

(3)為關鍵點分配方向。

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

m(x,y)=

(3)

(4)

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

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

1.2 改進的SIFT特征點描述符

在步驟(3)中，特征點被分配一個主方向，并實現由局部區域特征點的抗旋轉能力?？紤]到圓具有良好的旋轉不變性，蘭視爽等[12]利用圓形區域周圍的特征點構造SIFT特征描述子，當圖像發生旋轉時，子環中的像素位置發生了變化，其余的特征保持不變。

首先，計算圓環內每一個像素的梯度值和方向，統計出8個方向的梯度累加值。其次，對梯度累加值從大到小排序，確保旋轉后排序值不變。最后，對這一向量進行歸一化處理。

改進后的SIFT描述符自身具備旋轉不變性，不需要通過旋轉坐標軸來保證特征描述符的旋轉不變性。同時，改進后的篩選描述符被減小到64個維度，從而大大提高了工作效率，降低了匹配特征點的復雜性。

2 特征點匹配與篩選

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

(5)

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

2.1 傳統的RANSAC算法

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

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

(6)

(2)隨機選擇原始數據樣本，估計每個樣本的樣本數量為模型參數所需的最小數據，并計算樣本的相應模型參數。

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

(4)找出最優模型參數所對應的所有inliers，并用這些數據計算最終的模型參數。

2.2 改進的RANSAC算法

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

(7)

改進后RANSAC算法步驟如下：

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

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

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

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

3 圖像融合

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

(8)

d1和d2的計算如下：設當前像素的橫坐標為xi，重疊區域左右邊界的橫坐標分別為xl和xr，那么

4 實驗結果及分析

實驗所用的平臺為VS2010和OpenCV，圖像大小為340×280。選用4種典型的測試圖進行測試，如圖1所示。

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

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

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

圖1 未提取特征點的測試圖

圖2 SIFT特征梯度描述

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

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

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

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

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

采用RANSAC算法來消除誤匹配點對并用透視變換公式分別計算出圖3中待拼接圖像的坐標變換矩陣H中的參數：

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

圖5 融合圖

表1為選用同一組測試圖所得的特征點個數、匹配點數及拼接所消耗時間。

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

表1 SIFT算法與改進SIFT算法對圖像的實驗結果

5 結束語

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

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

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

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

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

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

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

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

[8] 鄒北驥,阮 鵬,向 遙，等.一種精確匹配的全景圖自動拼接算法[J].計算機工程與科學,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].現代計算機,2015(5):63-68.

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

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

[14] 周建平,楊金坤,鄭 宇.基于改進SIFT特征匹配的視頻拼接—在倒車系統中的應用[J].企業技術開發,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

時間：2016-03-22

國家自然科學基金資助項目(60975008)；重慶市教委科學技術研究項目(KJ130529)

馬 強(1990-)，男，碩士，研究方向為圖像處理；項昭保，教授，研究方向為天然化合物的分離純化、結構鑒定和結構修飾。

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