一種基于SURF、FLANN 和RANSAC 算法的圖像拼接技術(shù)*

原偉杰 文中華 彭擎宇

（1.湖南工程學(xué)院計(jì)算機(jī)與通信學(xué)院 湘潭 411104）（2.湘潭大學(xué)計(jì)算機(jī)學(xué)院網(wǎng)絡(luò)空間安全學(xué)院 湘潭 411105）

1 引言

生活中拍照需要各式各樣的相機(jī)，然而獲取視角廣闊、場(chǎng)景篇幅大的全景圖像無(wú)論是在汽車(chē)導(dǎo)航、森林火災(zāi)監(jiān)測(cè)以及軍事領(lǐng)域等方面都具有廣泛的應(yīng)用［1］。要想獲得這種要求的圖像通常需要高級(jí)的廣角鏡頭或者是超廣角鏡頭，由于其高額的費(fèi)用以及復(fù)雜的操作，圖像拼接技術(shù)就產(chǎn)生了。圖像拼接技術(shù)就是將兩幅或兩幅以上的圖像進(jìn)行拼接，組合成為一幅具有較大視野的圖像。

圖像拼接技術(shù)的兩個(gè)關(guān)鍵技術(shù)是圖像配準(zhǔn)和圖像融合。圖像融合的質(zhì)量取決于圖像配準(zhǔn)的精確度以及技術(shù)的創(chuàng)新。圖像配準(zhǔn)的常用方法有SURF［2］、SIFT、ORB 等，在此算法的基礎(chǔ)上前人進(jìn)行了很多關(guān)于圖像拼接技術(shù)的研究。董強(qiáng)等使用Haar小波響應(yīng)為每個(gè)特征點(diǎn)建立描述符，同時(shí)利用灰度信息和細(xì)節(jié)信息，大大提高了精確度［3］；魏利勝等為了獲取圖像的低頻成分，采用對(duì)圖像進(jìn)行分解的Haar 小波函數(shù)來(lái)實(shí)現(xiàn)，從而加快算法的運(yùn)行速度，利用特征點(diǎn)約束的方向一致性和單向匹配等性質(zhì)改善了拼接技術(shù)存在的問(wèn)題，提高了實(shí)時(shí)性［4］；鄒承明等提出了在幾何圖像基礎(chǔ)上配準(zhǔn)的拼接方法，提升了圖像拼接的效率［5］；盧鵬等提出了一種將SIFT 算法與時(shí)間序列相結(jié)合的拼接方法，降低了維度，縮短了時(shí)間，融合效果更好［6］；馬強(qiáng)等對(duì)RANSAC 算法進(jìn)行改進(jìn)，減少了迭代次數(shù)，加快了拼接效率［7］。本文提出了一種基于SURF算法的圖像拼接方法，首先在特征點(diǎn)提取時(shí)使用SURF 算法；再用FLANN［8～10］算法對(duì)特征點(diǎn)進(jìn)行配對(duì)［11］，并利用RANSAC算法來(lái)進(jìn)行單適應(yīng)性矩陣的計(jì)算［12］，然后剔除錯(cuò)誤的匹配點(diǎn)，最后對(duì)圖像進(jìn)行融合，實(shí)現(xiàn)圖像的拼接。

2 SURF算法

SURF（Speeded-Up Robust Features）加速穩(wěn)健特征，被廣泛應(yīng)用在特征點(diǎn)檢測(cè)以及特征匹配等方面，于2006 年首先發(fā)表在ECCV 大會(huì)上［13～14］。該算法在保持SIFT 算子優(yōu)良性能特點(diǎn)的基礎(chǔ)上，同時(shí)解決了SIFT 算法復(fù)雜度高、耗時(shí)長(zhǎng)的問(wèn)題，對(duì)特征點(diǎn)提取進(jìn)行了改進(jìn)并且在其特征向量描述方面進(jìn)行了改善，其算法效率得到了提升。具體步驟如下。

2.1 構(gòu)造Hessian矩陣，計(jì)算出特征值

式子中Lyy、Lxy、Lxx是在高斯濾波后圖像g（β）在其每個(gè)方向上的二階導(dǎo)數(shù)。其二階導(dǎo)數(shù)計(jì)算公式如下：

其中L（x）=g（h（x））（h（x）為原始圖像的灰度值，L（x）是將h（x）高斯濾波處理后的圖像）。

2.2 構(gòu)造高斯金字塔

SURF 是SIFT 改進(jìn)后的算法，主要是速度進(jìn)行了提升，主要在于跟SIFT 相比，它的每一組圖像大小都沒(méi)有發(fā)生變化，變的是高斯模板的尺寸和尺度。除此之外，SURF去除了降采樣的過(guò)程，因此提升了處理速度。

2.3 特征點(diǎn)定位

把經(jīng)過(guò)Hessian矩陣處理的每個(gè)像素點(diǎn)與其鄰域內(nèi)的26 個(gè)點(diǎn)進(jìn)行比較，找到其最大值與最小值并將其保留下來(lái)，初步定位出關(guān)鍵點(diǎn)，再經(jīng)過(guò)濾除能量比較弱的關(guān)鍵點(diǎn)以及錯(cuò)誤定位的關(guān)鍵點(diǎn)，篩選出最終的穩(wěn)定的特征點(diǎn)。

2.4 特征描述符

首先將特征點(diǎn)所在區(qū)域劃分為4*4 個(gè)矩形區(qū)域，每個(gè)區(qū)域有25 個(gè)采樣點(diǎn)，在每個(gè)區(qū)域求出Harr小波特征的水平方向與垂直方向的絕對(duì)值以及值之和。最終就會(huì)得到一個(gè)4*4*4=64的64維向量，相比于SIFT 算法減少了一半。

3 特征點(diǎn)匹配與提純

3.1 FLANN 特征點(diǎn)匹配

對(duì)于圖像的特征點(diǎn)匹配，常用的方法有BF（Brute Force）和FLANN（Fast Library for Approximate Nearest Neighbors）。

1）BF即暴力匹配。BF采用的是方法是對(duì)特征點(diǎn)進(jìn)行遍歷。首先從第一幅圖像中選取一個(gè)特征點(diǎn)，然后對(duì)待匹配的圖像中特征點(diǎn)進(jìn)行遍歷的同時(shí)并計(jì)算距離，記錄每?jī)蓴?shù)據(jù)間的距離，然后對(duì)這些距離進(jìn)行排序，最后返回距離最短的那個(gè)特征點(diǎn)，所以通常會(huì)有大量的特征點(diǎn)錯(cuò)誤匹配，后續(xù)需要對(duì)特征點(diǎn)的匹配結(jié)果進(jìn)行提純，從而提升匹配正確率［15］。

2）FLANN［16］即快速最近鄰搜索。采用的是近似法，其算法復(fù)雜度低，但是找到的結(jié)果是最近鄰近似匹配，主要通過(guò)Flann Based Mather 參數(shù)的調(diào)整來(lái)提升匹配度的精度提升或者算法速度。它可以很好地解決高維特征的問(wèn)題。

3.2 RANSAC算法提純

誤匹配點(diǎn)就是匹配過(guò)程中沒(méi)有位置上與外觀(guān)上相似的關(guān)系，因?yàn)榉纤惴▽⒛切┨卣鼽c(diǎn)匹配在一起，它的存在會(huì)影響到單應(yīng)性變換矩陣的計(jì)算并且?guī)?lái)一定的誤差。然而使用RANSAC 算法可以對(duì)匹配點(diǎn)進(jìn)行提純，提高精確度，最終計(jì)算出良好的單應(yīng)性矩陣［17］。RANSAC 算法步驟如下。

1）根據(jù)假定模型所需要的數(shù)據(jù)從匹配對(duì)數(shù)據(jù)集M 中隨機(jī)取出4對(duì)作為樣本，代入公式計(jì)算出單應(yīng)性矩陣，記為模型Q，確定好閾值；

2）計(jì)算出數(shù)據(jù)集中所有數(shù)據(jù)與模型Q 的誤差，如果其誤差小于提前設(shè)定好的閾值，就將其加入內(nèi)點(diǎn)集P；

3）計(jì)算出內(nèi)點(diǎn)在樣本容量中占得比例，如果其比例小于閾值，就選擇此時(shí)的參數(shù)矩陣Q；否則就重復(fù)上述步驟，直至符合要求。最終內(nèi)點(diǎn)最占比例最大的模型就是待求的模型。

RANSAC 算法稱(chēng)為隨機(jī)抽樣一致性，是一種擬合模型，該算法能夠在數(shù)據(jù)中存在大量噪聲（有效點(diǎn)多于噪聲）時(shí)，可以得到一個(gè)盡可能滿(mǎn)足樣本集中大部分樣本對(duì)的變換模型，保證了模型參數(shù)的準(zhǔn)確性，且該算法在大多數(shù)情況下較最小二乘法好［18］。

3.3 融合方法

3.3.1 最大值法

最大值法其重點(diǎn)就是對(duì)將要拼接的圖像［19］在重疊區(qū)域內(nèi)對(duì)像素值進(jìn)行比較，隨后將選擇將像素值最大的值來(lái)作為重合區(qū)域融合后圖像的像素值，其計(jì)算公式如下：

f代表融合后圖像，f1和f2表示待拼接圖像。

3.3.2 加權(quán)平均法

和直接平均法不同，其重點(diǎn)在加權(quán)，方法是按照兩幅圖在重疊區(qū)域內(nèi)的所占比例對(duì)像素進(jìn)行權(quán)重的分配，選取一定的權(quán)值進(jìn)行加權(quán)處理，從而實(shí)現(xiàn)像素值的平滑過(guò)渡［20］。該計(jì)算公式如下：

上述三者為公式的約束區(qū)間；w1和w2分別代表重疊區(qū)域內(nèi)兩幅圖像像素點(diǎn)的權(quán)值，同時(shí)w1和w2滿(mǎn)足關(guān)系w1+w2= 1（0＜w1＜1，0＜w2＜1）；從其計(jì)算方法來(lái)看，跟平均法差不多，主要差別在于其權(quán)重隨著重疊區(qū)域的寬度發(fā)生變化，從而實(shí)現(xiàn)融合區(qū)域像素變化的平滑性。

4 算法設(shè)計(jì)與實(shí)現(xiàn)

本算法設(shè)計(jì)主要是為了解決在圖像拼接中存在的拼接痕跡明顯，存在清晰的顏色變化等問(wèn)題。提出了基于SURF 算法，充分利用其速度優(yōu)勢(shì)，速度是SIFT 算法的3 倍；結(jié)合OpenCV 中攜帶的FLANN 算法，利用其復(fù)雜度低，搜索速度快且可以調(diào)整參數(shù)的優(yōu)點(diǎn)；加上RANSAC算法可以對(duì)誤匹配點(diǎn)進(jìn)行剔除來(lái)優(yōu)化匹配結(jié)果，最終利用加權(quán)平均法，四者結(jié)合來(lái)解決圖像拼接中存在的問(wèn)題。

SURF、FLANN、RANSAC 三者結(jié)合的圖像拼接框架圖如圖1所示。

圖1 圖像拼接流程圖

SURF、FLANN、RANSAC 三者結(jié)合的圖像拼算法流程如下。

第1～4 行是對(duì)圖片進(jìn)行輸入并進(jìn)行灰度化的一個(gè)處理；第5 行是采用SURF 算法對(duì)圖片進(jìn)行特征點(diǎn)的識(shí)別與描述；第6 行是用FLANN 算法對(duì)特征點(diǎn)進(jìn)行配對(duì)；第7 行是調(diào)用RANSAC 算法進(jìn)行誤匹配點(diǎn)的剔除并進(jìn)行單應(yīng)變換矩陣的計(jì)算；第8 行是運(yùn)用加權(quán)平均法對(duì)圖片進(jìn)行融合，最后輸出拼接圖像。

下面對(duì)SURF算法進(jìn)行解釋?zhuān)溥^(guò)程如下。

第1 行是設(shè)置海森矩陣參數(shù)，參數(shù)越大，越精準(zhǔn)；第2～5 行是對(duì)兩幅帶拼接的圖像進(jìn)行特征點(diǎn)檢測(cè)；第6～9行是對(duì)特征點(diǎn)進(jìn)行描述，其中第2行和第6行是對(duì)SURF 算法進(jìn)行調(diào)用。

下面對(duì)FLANN 與RANSAC 算法進(jìn)行解釋?zhuān)溥^(guò)程如下。

第1～3行是對(duì)FLANN 函數(shù)進(jìn)行調(diào)用；第4行是對(duì)最大值、最小值初始化并進(jìn)行賦值；第6～13 行是來(lái)遍歷尋找最大最小距離；第13～16 行是對(duì)所求的匹配點(diǎn)進(jìn)行配對(duì)，找到最有匹配對(duì)；第17 行直接調(diào)用RANSAC算法進(jìn)行單應(yīng)矩陣的計(jì)算，并將經(jīng)過(guò)單應(yīng)矩陣變換過(guò)后的圖像進(jìn)行保存。

下面對(duì)WARP算法進(jìn)行介紹，其過(guò)程如下。

第1～6 行對(duì)圖像進(jìn)行拼接，其主要是對(duì)權(quán)重進(jìn)行計(jì)算并將重合區(qū)域的像素進(jìn)行分配，盡可能好地得到結(jié)果。

5 實(shí)驗(yàn)

本實(shí)驗(yàn)的所有操作均在一臺(tái)處理器為Intel Core i5-3320 2.90GHz，內(nèi) 存8GM，操 作 系 統(tǒng) 為Win10，實(shí)驗(yàn)平臺(tái)為Visual Studio 2010 和圖像處理庫(kù)OpenCv 2.4.10。

在實(shí)驗(yàn)的匹配階段，經(jīng)過(guò)SURF 算法進(jìn)行特征點(diǎn)尋找之后，分別用BF 算法匹配和FLANN 算法進(jìn)行匹配實(shí)驗(yàn)，并對(duì)其匹配結(jié)果進(jìn)行對(duì)比，以驗(yàn)證所用方法的優(yōu)劣性，圖2 和圖3 分別是待拼接圖像1與待拼接圖像2，圖4 和圖5 分別是FLANN 特征點(diǎn)匹配結(jié)果圖與BF特征點(diǎn)匹配結(jié)果圖。

圖2 待拼接圖像1

圖3 待拼接圖像2

圖4 FLANN匹配結(jié)果圖

圖5 BF匹配結(jié)果圖

通過(guò)看匹配結(jié)果圖，可以明顯看出，基于BF的暴力匹配算法匹配方法存在大量的匹配錯(cuò)誤點(diǎn)，而FLANN 方法匹配效果良好，無(wú)明顯錯(cuò)誤，因此本文采用FLANN方法進(jìn)行特征點(diǎn)的匹配。

在融合圖像時(shí)也采用了兩種方法，分別是最大值法與加權(quán)平均法，圖6 和圖7 分別是加權(quán)平均法與最大值法的拼接效果圖。

圖6 加權(quán)平均法

圖7 最大值法

從實(shí)驗(yàn)結(jié)果可以看出：最大值法雖然能較快得到結(jié)果，但是可以發(fā)現(xiàn)有明顯的拼接痕跡，而且拼接區(qū)域出現(xiàn)了明顯的色差變化；然而加權(quán)平均法得到的結(jié)果，可以看出沒(méi)有拼接痕跡不明顯，整體看起來(lái)也自然，其拼接效果要好于最大值法。

6 結(jié)語(yǔ)

本文針對(duì)在圖像拼接過(guò)程中特征點(diǎn)匹配錯(cuò)誤率高、匹配速度慢和拼接色彩變化明顯的問(wèn)題，通過(guò)結(jié)合RANSAC 與SURF 算法，在匹配階段采用了FLANN 方法來(lái)提高匹配正確率，同時(shí)為減弱圖像融合時(shí)有顏色明顯變化以及存在的拼接痕跡，采用RANSAC 算法進(jìn)行誤匹配點(diǎn)的剔除，并且采用加權(quán)平均法進(jìn)行圖像的融合，消除了顏色的突兀變化減弱了拼接痕跡，其匹配效果更好。實(shí)驗(yàn)結(jié)果表明，本文采用的方法在匹配正確率方面良好、魯棒性強(qiáng)。