基于SURF的圖像配準改進算法

袁麗英，劉 佳，王飛越

(哈爾濱理工大學自動化學院，黑龍江 哈爾濱 150080)

0 引言

在20世紀70年代，隨著美國對軍事輔助導(dǎo)彈系統(tǒng)及飛行器的研究，圖像配準的概念被首次提出[1]。目前，圖像配準算法的研究逐漸由基于像素的灰度相關(guān)的趨勢向局部特征相關(guān)發(fā)展[2]，人們已經(jīng)提出了各式各樣的局部特征算法。SIFT即尺度不變特征變換算法[3]，于1999年由D.G.Lowe等人提出，又于五年之后對此方法進行了改進[4]，該算法對尺度縮放、亮度等變化具有良好的不變性。K.Mikolajczyk提出了Harris-Laplace 算法，該算法的優(yōu)點是具有仿射不變性，但檢測到的特征點較少[5]。H.Bay等人在分析總結(jié)多種特征檢測方法的基礎(chǔ)上提出了SURF(Speeded-Up Robust Features)算法[6]，它加入了積分圖像簡化計算，減少了檢測特征點的計算量，而且它對圖像的平移、旋轉(zhuǎn)、縮放等變化具有很好的不變性[7]。SURF算法是在SIFT算法已有成果上的改進。

盡管SURF算法具有杰出的性能，但仍然存在匹配精度低的問題[8]。產(chǎn)生這種情況的原因是：該算法是直接對原圖像進行操作。原圖像受到外界環(huán)境的干擾，獲得的圖像質(zhì)量較差，提取特征變得困難，導(dǎo)致有效特征點的數(shù)量和準確度下降，從而影響匹配結(jié)果。本文針對此問題，提出了基于SURF的圖像配準改進算法。

1 SURF算法

SURF算法由特征點檢測、特征點描述和特征點匹配三部分組成[9]。通過積分圖像建立特征點檢測，選用Hessian矩陣檢測子來檢測特征點。利用特征點的Haar小波變換來尋找特征點的主方向，最終確定特征點的描述符[10]。通過描述特征向量之間的歐式距離，即相似度量以歐式距離作為準則，完成圖像特征點匹配。

1.1 特征點檢測

1.1.1積分圖像

SURF算法中應(yīng)用積分圖像可將圖像與二階高斯微分模型卷積簡化為對圖像的加減，其中積分圖像由Viola等提出[11]。積分圖像任意一點(i,j)的積分值ii(i,j)定義為原圖像左上角到任意點相對應(yīng)矩形區(qū)域灰度之和[12]，即：

(1)

式(1)中，原圖像點(i′,j′)的灰度像素的值由p(i′,j′)表示，可由式(2)、式(3)迭代得到：

S(i,j)=S(i,j-1)+p(i,j)

(2)

ii(i,j)=ii(i-1,j)+S(i,j)

(3)

式(2)中，S(i,j)表示一列的積分。對于超過邊界的值，令S(i,-1)=0，ii(-1,j)=0 。只需要對圖像所有像素掃描一遍就能求解積分圖像[13]。

當求解圖像W內(nèi)的全部像素灰度時，可以不考慮W的大小，使用積分圖像的四個相應(yīng)點(i1,j1)，(i2,j2)，(i3,j3)，(i4,j4)的值加減可得，如圖1所示，即：求取W內(nèi)的像元灰度和跟W的大小不相關(guān)。W內(nèi)的像元灰度和∑W即：

∑W=ii(i4,j4)-ii(i2,j2)-ii(i3,j3)+ii(i1,j1)

(4)

若有一幅圖像的灰度值均為1，則圖像中任意點(i,j)積分圖像的值就是從該圖像左上角到它所組成的方形區(qū)域的大小，則W組成的方形的面積為∑W。

圖1 積分圖像的計算和窗口內(nèi)像元灰度求和Fig.1 The calculation of the integral image and the pixel gray-level summation in the window

1.1.2確定特征點

尺度空間理論是特征點檢測的基礎(chǔ)。通過積分圖像加快圖像卷積來增加計算速率。然后通過計算圖像每一個像素的Hessian矩陣行列式獲得特征點的值[14]。Hessian矩陣是以二階偏導(dǎo)數(shù)矩陣組成的，給定圖像I某一點(x,y)處Hessian矩陣即：

(5)

(6)

式(6)中，?表示為卷積，二維高斯函數(shù)如下所示：

(7)

H(x,y,σ)的行列式值Det(H)如下：

(8)

1.2 特征點描述

為了確保特征點的旋轉(zhuǎn)不變性，需要給所有特征點分配主方向[15]。具體步驟為：

1) 選取特征點為圓心，在以半徑為6s(s為特征點所在的尺度)的圓形區(qū)域內(nèi)，對圖像進行Haar小波響應(yīng)運算[16]，根據(jù)間隔距離，對得到的響應(yīng)值賦，然后統(tǒng)計響應(yīng)直方圖[16]。由于使用了積分圖像，使得計算速度加快。 尺度s的計算方法如下：

(9)

式(9)中，Sizecurrent-Filter、SizeBase-Filter和ScaleBase-Filter分別表示當前濾波尺寸、基準濾波尺度和濾波尺寸。

2) 通過60°的扇形滑動窗口，以步長0.2弧度兩側(cè)，旋轉(zhuǎn)這個滑動窗口，如圖2所示。對圖像的Haar響應(yīng)的dx、dy進行疊加[16]，生成矢量(mw,θw)即：

(10)

(11)

當mw在窗口內(nèi)的疊加值最大的時候，其角度θw對應(yīng)主方向。

圖2 滑動窗口圍繞特征點轉(zhuǎn)動求取主方向Fig.2 Sliding the window around the feature point to find the main direction

3) 特征點主方向確定后，在特征點周圍20s×20s的矩形內(nèi)計算特征描述子。將此矩形化分成4×4子區(qū)域，使用尺寸為2×2模板的Haar小波計算每個子區(qū)域x方向和y方向的Haar小波響應(yīng)值。

1.3 特征點匹配

特征提取得到兩個特征點集合后，可根據(jù)特征點間的相似性度量來進行匹配，因為SURF特征向量維數(shù)不低[17]，一般都采用歐式距離作為相似性度量準則。

1.3.1最小距離法

參考圖像I1和待配準圖像I2的特征點描述符分別為x=(x1,x2,…,xi)，x′=(x1′,x2′,…,xi′)，則x和x′間的歐式距離如下：

(12)

算出待配準圖像與參考圖像的所有特征點之間的距離，選擇與之相距最小的特征點作為匹配對。圖像中所有特征點都進行同樣的操作，得到全部的特征匹配對。dmin為所有匹配點對距離的最小值，閾值設(shè)置為T=μ×dmin，剔除匹配點對中d

1.3.2最近鄰與次近鄰比值法

由式(12)計算出來的I1和I2所有特征點對間的距離，若在圖像I1內(nèi)的特征點與圖像I2內(nèi)距離最近和次近點間的距離分別為dmin，dsecond，則設(shè)定一個閾值T且滿足如下：

(13)

通常，T的取值為[0.4,0.8]，即最近點與次近點相比有更大的優(yōu)勢時才能構(gòu)成匹配對。

獲得特征點匹配對之后，使用RANSAC算法[18]求解仿射變換模型，具體分以下幾步：

1) 任意選三個特征匹配對，計算變換參數(shù)集P，初始化匹配對數(shù)matcher為零；

3) 若matcher超過某個閾值N，則終止計算，否則轉(zhuǎn)到2)；

4) 若計算完所有的特征點對時matcher都沒有超過N，那么就將matcher為最大值時的集合P作為最后的參數(shù)集合。

通常情況下，誤差d的取值范圍為1～10，若特征匹配集合的最大數(shù)量為M，閾值N與M的關(guān)系為N=4/M。事實上，若初匹配階段特征點的準確匹配率超過40%，則算法會很快收斂。

2 改進的SURF算法

本文對傳統(tǒng)的SURF圖像配準算法的特征點提取以及特征點匹配進行改進。其具體流程圖如圖3所示。

圖3 SURF圖像配準算法改進流程圖Fig.3 Flow chart of improved surf image registration algorithm

2.1 特征點提取的改進

一般的低通濾波器只考慮其中的灰度相似關(guān)系，將可能的邊緣信息和噪聲都濾掉，造成邊緣信息缺失，致使邊緣模糊。為了提取更好性能的特征點，本文預(yù)先采取雙邊濾波的形式，對圖像處理。雙邊濾波器兼顧了像素點周圍的空間鄰近、灰度相似關(guān)系，能夠解決濾除邊緣問題[19]。雙邊濾波HBL如下所示：

(14)

式(14)中，

(15)

式(15)中，x為當前位置，y∈s是以x為中心的s×s區(qū)域內(nèi)的點，Ix，Iy分別代表對應(yīng)的像素值，‖x-y‖為空間距離，Gσd，Gσr分別表示空間近鄰函數(shù)和灰度相似函數(shù)，Gσd能夠避免遠距離像素的影響，Gσr可有效避免像素值突變的干擾。具體定義分別如下所示：

(16)

(17)

式(16)中，d(x,y)為圖像兩像素點間的歐式距離，σd，σr為高斯函數(shù)標準差。式(17)中,δ(I(x),I(y))為Ix，Iy間的灰度差。σd，σr分別限定像素位置的空間和灰度變化來控制濾波效果，σd，σr決定了雙邊濾波的性能。σd，σr值的選取可以根據(jù)實際情況調(diào)節(jié)。

2.2 特征點匹配的改進

SURF特征點使用最近鄰域和次近鄰域法進行匹配時，閾值的選取會對匹配結(jié)果產(chǎn)生影響，進而匹配精度也會受到影響。

2.2.1閾值自適應(yīng)匹配

本文并沒有選取固定的閾值去完成匹配，而是通過閾值自適應(yīng)約束對初始匹配特征集合進行篩選。步驟如下：

1) 假設(shè)從基準圖和待檢測圖像中獲得的初始特征集合分別為X，Y，計算X中任意點和Y內(nèi)的全部特征點間的距離di，并將di按照從小到大的依次排列；

2) 對X中的所有點都進行第一步的操作，并分成n組；

3) 對上一步中得到的n組數(shù)據(jù)，分別計算每組中在最前面的兩個數(shù)據(jù)的大小之比Ti(i=1,2，…，n)；

4) 計算Ti的平均值Td，設(shè)正確匹配對為match=0，初始化閾值為Tr=Td(0

5)若檢測到的點的最近和次近鄰域之比小于Tr，則++match對，可能是周邊相近的比較多，為了減少誤匹配，則Tr=Tr-0.05。反之，連續(xù)幾次都沒有檢測到正確的匹配對，則Tr=Tr+0.05，直到所有的特征點檢測完成為止。

2.2.2肯德爾系數(shù)約束

初匹配得到的特征點也會有錯誤匹配，若圖像在拍攝時受到干擾，錯誤匹配會更多，對配準精度有更大的影響，所以本文采用肯德爾系數(shù)約束實現(xiàn)精匹配，從而減少誤配率。

設(shè)SURF算法通過初匹配得到的點在待配準圖像中的中心位置為K，尺度為σ，主方向為ω。給特征點定義一個半徑ρ，且半徑ρ=6σ。采用特征點為核心、建立邊長為S=round(α×ρ)的正方形，α為實驗參數(shù)[20]。

如圖4所示，設(shè)P1是圖像I1的配準點，且其中心位置點、尺度、半徑、主方向分別為K1，σ1，ρ1，ω1，其周邊正方形區(qū)域為Rec1，邊長為S1=round(α×ρ1)，同理，則對應(yīng)到圖像I2的點為P2，且K2，σ2，ρ2，ω2，S1分別對應(yīng)著P2的中心位置、尺度、半徑和主方向及P2周圍正方形區(qū)域Rec2的邊長。其中S2=round(α×ρ2)。

圖4 特征點對應(yīng)的正方形區(qū)域Fig.4 Squares corresponding to feature points

當圖像旋轉(zhuǎn)時，對應(yīng)的正方形也應(yīng)該做出相應(yīng)旋轉(zhuǎn)，則P1，P2主方向之間相差角度Δφ如下：

Δφ=ω1-ω2

(18)

(19)

Aij即可表示為如下所示：

(20)

式(20)中，Aij為0的情況有三種，第一種為：v1i-v1j=0且v2i-v2j≠0，第二種為：v1i-v1j≠0且v2i-v2j=0，第三種為：v1i-v1j=0且v2i-v2j=0。

肯德爾系數(shù)τ表示為：

(21)

式(21)中，C，D分別為Aij等于1，-1的次數(shù)，T(v1i-v1j)=0,(v2i-v2j)≠0的次數(shù)，U為(v1i-v1j)≠0,(v2i-v2j)=0的次數(shù)。

為了求解每對配準點的肯德爾系數(shù)，需要設(shè)定一個閾值TKτ，當TKτ小于τ時，則此配準點對是較強的匹配對；當TKτ大于τ，則舍去配準點。TKτ的計算如下：

TKτ=mean(Mτ)-std(Mτ)/2

(22)

式(22)中，mean(Mτ)，std(Mτ)分別對應(yīng)肯德爾系數(shù)的均值和標準差。

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

本實驗的目的是對傳統(tǒng)的SURF算法與改進后的SURF算法進行比較，選取不同視角拍攝的圖像與變換程度不同的圖像，針對配準時間、配準率以及RMSE(均方根誤差)等方面進行分析。實驗環(huán)境為：Windows7操作系統(tǒng)，酷睿i5-3230M，CPU Intel 2.6 GHz，內(nèi)存4 GB，使用Matlab2014(64位)軟件。

3.1 不同視角的圖像配準實驗

選取同一場景不同角度拍攝的兩幅圖像，分別采用傳統(tǒng)的SURF算法和改進后的SURF算法進行實驗，如圖5所示。

圖5(c)與圖5(d)對比可以得出，改進之后的SURF配準算法與原來的算法相比配準精度損失不明顯，但是明顯去掉了部分誤匹配點對，提高了匹配的精度。實驗數(shù)據(jù)記錄如表1。

根據(jù)表1，通過匹配率、匹配時間以及均方根誤差可知，改進的SURF算法匹配率提高了，證明改進的圖像配準算法能夠提高配準的精度。且改進算法的匹配時間也較短，所以改進的SURF算法實時性好。

圖5 SURF圖像配準算法改進前后的匹配結(jié)果Fig.5 Matching results before and after improvement of surf Image Registration algorithm

表1 算法改進前后配準結(jié)果對比

Tab.1 Comparison of registration results before and after the improvement of the algorithm

算法匹配率/%匹配時間/sRMSE傳統(tǒng)的SURF92.703.130.62改進的SURF98.410.510.35

3.2 變換程度不同的圖像配準實驗

選取同一場景不同變換程度的兩張大山圖片，分別使用改進前后的算法進行配準，實驗結(jié)果如圖6所示。圖6(a)、圖6(b)分別為參考圖像和待配準圖像，圖6(c)、圖6(d)分別為算法改進前后的圖像特征點匹配。

圖6 SURF圖像配準算法改進前后的匹配結(jié)果Fig.6 Matching results before and after improvement of surf Image Registration algorithm

圖6(c)中結(jié)果的重疊的部分比較明顯，造成部分信息丟失，因而得到的結(jié)果相較于圖6(d)而言，圖像信息沒有得到充分的利用，圖6(d)的配準視覺效果更佳且提高了配準的精確率。實驗數(shù)據(jù)記錄如表2。

表2 SURF算法改進前后配準結(jié)果對比

由表2可知，改進后的SURF算法匹配率接近100%，因而改進后的算法對誤配點的提純起到作用，匹配時間減少，且均方根誤差也降低，證明改進的算法提高了配準精度。

4 結(jié)論

本文提出了基于SURF的圖像配準改進算法，該算法針對SURF圖像配準算法存在配準精度低的問題，在特征點提取之前采用雙邊濾波，有效的抑制一些不相關(guān)的特征點和噪聲誤差。閾值自適應(yīng)的約束對得到的特征點進行初始匹配，提高了正確匹配對的精度?？系聽栂禂?shù)可以對誤配點進行二次剔除。實驗結(jié)果表明，改進的SURF算法配準精度與魯棒性增強，并且匹配時間減少。