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

袁麗英，劉 佳，王飛越

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

0 引言

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

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

1 SURF算法

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

1.1 特征點檢測

1.1.1積分圖像

SURF算法中應用積分圖像可將圖像與二階高斯微分模型卷積簡化為對圖像的加減，其中積分圖像由Viola等提出[11]。積分圖像任意一點(i,j)的積分值ii(i,j)定義為原圖像左上角到任意點相對應矩形區(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內的全部像素灰度時，可以不考慮W的大小，使用積分圖像的四個相應點(i1,j1)，(i2,j2)，(i3,j3)，(i4,j4)的值加減可得，如圖1所示，即：求取W內的像元灰度和跟W的大小不相關。W內的像元灰度和∑W即：

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

(4)

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

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

1.1.2確定特征點

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

(5)

(6)

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

(7)

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

(8)

1.2 特征點描述

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

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

(9)

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

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

(10)

(11)

當mw在窗口內的疊加值最大的時候，其角度θw對應主方向。

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

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

1.3 特征點匹配

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

1.3.1最小距離法

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

(12)

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

1.3.2最近鄰與次近鄰比值法

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

(13)

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

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

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

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

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

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

2 改進的SURF算法

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

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

2.1 特征點提取的改進

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

(14)

式(14)中，

(15)

式(15)中，x為當前位置，y∈s是以x為中心的s×s區(qū)域內的點，Ix，Iy分別代表對應的像素值，‖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ù)實際情況調節(jié)。

2.2 特征點匹配的改進

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

2.2.1閾值自適應匹配

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

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

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

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

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

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

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

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

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

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

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

當圖像旋轉時，對應的正方形也應該做出相應旋轉，則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ù)，需要設定一個閾值TKτ，當TKτ小于τ時，則此配準點對是較強的匹配對；當TKτ大于τ，則舍去配準點。TKτ的計算如下：

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

(22)

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

3 實驗結果及分析

本實驗的目的是對傳統(tǒng)的SURF算法與改進后的SURF算法進行比較，選取不同視角拍攝的圖像與變換程度不同的圖像，針對配準時間、配準率以及RMSE(均方根誤差)等方面進行分析。實驗環(huán)境為：Windows7操作系統(tǒng)，酷睿i5-3230M，CPU Intel 2.6 GHz，內存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圖像配準算法改進前后的匹配結果Fig.5 Matching results before and after improvement of surf Image Registration algorithm

表1 算法改進前后配準結果對比

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 變換程度不同的圖像配準實驗

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

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

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

表2 SURF算法改進前后配準結果對比

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

4 結論

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