基于顯著區域檢測的SURF特征匹配優化算法

陳 謙，吳 清

(1.河北工業大學 計算機科學與軟件學院；2.河北省大數據計算重點實驗室，天津 300401)

基于顯著區域檢測的SURF特征匹配優化算法

陳 謙1,2，吳 清1,2

(1.河北工業大學 計算機科學與軟件學院；2.河北省大數據計算重點實驗室，天津 300401)

針對傳統SURF匹配算法在特征點選取階段選取了大量不符合匹配預期的特征點，增加了后期匹配的運算復雜度，提出一種SURF算子和顯著區域檢測相結合的方法。為使檢測出的極值點和預期匹配的目標更加接近，用SURF算子構建出尺度空間圖像后對該空間作顯著區域檢測，再對特征點賦顯著度權值并通過孤立點剔除和局部冗余篩選出目標點，篩選后的特征點比傳統方法得到的特征點數量明顯減少，在降低時間復雜度的同時匹配精度提高了18%。特征匹配時引入RANSAC算法剔除誤匹配點對，對匹配結果作進一步修正。實驗表明，與傳統SURF算法比較，改進算法在實時性和匹配精度方面均更優。

SURF算法；顯著區域檢測；尺度空間；特征值；匹配精度；RANSAC算法

0 引言

隨著圖像處理、機器視覺等相關領域技術的快速發展，特征匹配得到了廣泛應用。在圖像匹配方法中，特征點的提取及匹配方法已有很多研究成果。 Forstner算子[1]、Harris算子[2]、Moravec算子[3]、SIFT(scale invariant feature transform)算子[4]等都是比較常用的特征點提取算子。其中，SIFT算子是由David G·Lowe提出的一種基于局部特征的描述方法，但許多研究實驗表明SIFT算法存在著128維的特征描述符，計算復雜度較高、實時性差、誤匹配較多。SURF(speeded up robust features)算法[5]是SIFT算法的快速改進方法，雖然都具有對尺度和旋轉的魯棒性[6]，但相關實驗表明，SURF算法采用二維Haar小波響應、積分圖像和Hession矩陣相結合實現算法加速，比SIFT算法效率提升了3～5倍。

但是上述方法都存在特征點提取準確度低和誤匹配的問題，為了減少不符合匹配預期特征點的個數，使提取的特征點與人眼觀察的特征點相近。本文主要開展了以下幾方面的工作：為了提高SURF算子主方向精度，提出了為Haar小波響應增加梯度權值來改變扇形區域內各特征點的價值貢獻度；為了改善特征點選取，刪除信息含量較低和冗余的點，提出了基于顯著圖、孤立點剔除、局部冗余三級特征點價值評價策略；為了降低匹配錯誤率，對匹配結果進行了RANSAC匹配檢驗。

1 SURF特征點提取與匹配

SURF描述子包含兩個主要部分：檢測關鍵點和計算特征。檢測關鍵點采用快速Hession檢測算法，特征描述采用Haar小波圓形區域方向直方圖特征作為主特征，通過建立特征點附近區域內的信息作為細節描述子。

1.1 Hession矩陣檢測特征點

設圖像I(X)的某一像素點為X=(x，y)，則尺度為σ的Hessian矩陣H(X，σ)定義為[7]：

(1)

其中，Lxx(X，σ)是二階高斯濾波?2/?x2g(σ)與圖像點X的卷積。同理，可計算Lxy(X，σ) 和Lyy(X，σ)。但是在實際處理中，離散化高斯濾波器會有一些走樣，所以采用 Bay等提出的盒濾波來近似高斯濾波。

如圖1所示，采用該方法計算卷積時，其計算量與濾波器大小無關，可以極大程度地提高算法執行速度。圖1第一行中x、y和xy方向的離散二階斯導數用Lxx、Lyy和Lxy表示；第二行中x、y和xy方向的加權盒濾波器近似用Dxx、Dyy和Dxy表示。

當用σ= 1.2的高斯二階微分濾波，模板尺寸為99最為最小的尺度空間值對圖像進行濾波和斑點檢測，Hession矩陣的行列式可作如下簡化：

(2)

另外，響應值還要根據濾波器大小進行歸一化處理，以保證任意大小濾波器的F范數是統一的。

圖1 利用盒濾波器來近似高斯濾波器

1.2 構造SURF特征主方向和描述子

利用非極大值抑制初步確定特征點，然后采用三維線性插值法得到亞像素級的特征點。再統計特征點鄰域內的Haar小波特征，選取最大值扇形的方向作為該特征點的主方向。最后在特征點周圍取一個帶方向正方形框，然后把該框分為16個子區域，每個子區域統計25個像素的水平方向dx和垂直方向dy的Haar小波特征。原理如圖2所示。

圖2 特征點描述算子構造

2 頻率調諧顯著區域檢測算法

為了和SURF算法進行有機結合，本文選擇復雜度較低的頻率調諧顯著檢測算法[8]，算法中使用的高斯濾波器和尺度空間每一層使用的濾波器均相同，并隨著層數的增加，不斷擴大濾波器的尺寸。算法主要步驟如下：

(1)設輸入圖像為Iw×h，其中w為圖像寬度，h為圖像高度。用高斯濾波器對圖像進行平滑處理，得到新的圖像Ig，其計算公式如下：

(3)

(2)將圖像Ig從RGB模型轉換到Lab模型。對每個特征分別計算其整體均值得到均值圖像Iμ=[Lμ,aμ,bμ],同時對各特征高斯平滑，得到平滑后的圖像為：

(4)

(3)計算得到顯著圖區域，即最終的顯著圖S(x,y)：

(5)

算法過程如圖3所示。

3 融合顯著區域檢測的SURF算法

單純的SURF匹配算法存在特征點過選取的問題，為此本文融合顯著區域檢測的方法，可以有效減少SURF算法中無意義的特征點，使匹配效率得到大幅提升。

圖3 頻率調諧顯著圖檢測步驟

3.1 構建尺度空間

首先構建Hessian矩陣，利用式(2)得到近似Hessian矩陣行列式，使用該近似行列式來表示圖像中某一點x處的斑點響應值，遍歷圖像中所有的像元點，形成在該尺度下所有點檢測的響應圖像。在建立金字塔圖像空間時，采用不斷增大的盒子濾波器模板尺寸，形成多尺度斑點響應的金字塔圖像，利用這一金字塔圖像，基于文獻[9]中的思想進行斑點響應極值點搜索[9]。設金字塔濾波器響應長度l、濾波器尺寸S、組索引o、層索引t和尺度σ，有：

(6)

(7)

(8)

在進行尺度分析的情況下，隨著尺度不斷增大，被檢測到的斑點數量迅速衰減。本文實驗中的金字塔只建立到第三層，由于粗尺度上選取特征點的數量通常相對較少，所以在第二層和第三層可以采用隔點濾波，從而進一步加快運算效率。

3.2 顯著區域檢測及特征點精確定位

通過顯著區域檢測使特征點分布更加趨近顯著區，但是依然存在特征點數量大和質量差的問題。為此，本文建立了以下三級價值評價策略，可以不斷優化特征點數目，提高匹配精度。

3.2.1 基于顯著圖的特征點價值評價策略

SURF算子拋棄了SIFT算子中圖像金字塔構建過程中輸入圖像反復與高斯函數的核卷積，并反復對其進行二次抽樣，可避免大量的重復操作。

在此基礎上，本文通過對各級尺度空間圖像上作顯著性區域檢測得到尺度空間顯著圖，結合基于顯著圖的特征點價值評價策略為每個提取到的特征點分配相應的權值。具體處理過程可分為以下兩步：首先，對顯著性區域檢測后的顯著圖作灰度圖歸一化；其次利用提取到的特征點響應值和歸一化灰度圖中該點的灰度值相乘，得到新的特征值作為評價標準。基于該策略使得處于顯著區域的特征點特征得到增強，處于背景區的特征點特征被削弱。

3.2.2 基于孤立點剔除的特征點價值評價策略

雖然通過顯著圖可以篩去大量處于背景中的特征點，但仍有一部分顯著區外特征值較低的離散特征點無法去除。為此，本文采用基于孤立點剔除的策略解決這一問題。在特征點方向分配中，以特征點為中心，計算半徑為6s(s為特征點所在的尺度值)的鄰域內的點在x、y方向的Haar小波響應，在此Haar小波邊長取4s[10]。

孤立點是在低密度區域中的特征點，且認為一個數據集中若存在孤立點，那么孤立點的密度會小于平均密度[11]。下面定義每個對象密度的計算方法，標準化原始數據集后，計算n個對象兩兩之間的距離di,j，形成距離矩陣R：

(9)

設所有對象的平均距離為D，為與平均密度的定義保持一致，在計算每個對象i的對象密度時，將有效直徑延長至原來的3倍，以3D為單位封閉區間的面積，掃描數據矩陣R，計算每個對象單位封閉區間的對象數Ci，也就是與對象i間距離小于3D/2的對象點數目。因此，每個對象i的對象密度為：

(10)

但是復雜的對象密度計算犧牲了大量時間復雜度，影響了算法整體效率，在此對算法作以下簡化：

(1)計算出單位面積圖像中特征點密度d。

(2)統計以特征點Si為中心，半徑6s(s為特征點所在的尺度值)的范圍內特征點數量m。

當該特征點為孤立點時剔除該孤立點，否則保留，如圖4所示d1～d5五個孤立點將被剔除。

圖4 孤立特征點檢測示意圖

3.2.3 基于局部冗余的特征點價值評價策略

以特征點為中心，張角為的扇形區域滑動，計算窗口內的Harr小波響應值dx、dy的累加，在累加過程中由于距離中心越遠的點對特征點的影響越小，實驗中通過為Haar小波響應增加梯度權值使得主方向的計算更加精準。

生成特征描述子后，特征點在顯著區域分布較為緊密，匹配時互相干擾太大，為此需進一步對局部冗余的特征點進行篩除。將以特征點為中心，M(可根據圖片分辨率和期望獲得的特征點個數確定，本文M取3s)為半徑范圍內的特征點全部去除，確保局部只有一個有效特征點，降低了相似點之間的干擾，提高了匹配精度。

3.3 RANSAC算法剔除誤匹配點

RANSAC算法的基本假設是樣本數據中包含正確數據，也包含異常數據，即數據集中含有噪聲[12]。這些異常數據可能是由于多種因素導致，包括錯誤的測量、假設或計算等產生的。SURF匹配算法中，這些異常數據可能由 SURF算法進行預匹配產生的錯誤或者誤差比較大的匹配導致的。

3.3.1 RANSAC算法

本文采用RANSAC算法，實現步驟如下：

(1)通過選取總數為n的最小抽樣集(n為初始化所需最小樣本數)和樣本集P(P樣本集大于n)，在P樣本集中隨機選取n個樣本數據，得到P的子集S，用來對模型M進行初始化。

(2)得到的余集為SC=P/S，此樣本集與模型M的誤差小于某一閾值t(t為預設值)的樣本集合與S構成集合S*。S*是內點集，它們構成S的一致集。

(3)如果#(S*)>=N，認為模型參數正確，并利用集S*，采用最小二乘法重新計算新的模型M*。重新隨機抽取新的子集S，并重復以上操作。

(4)反復對樣本進行抽樣，一定次數后如果沒有找到一致集，則算法失敗；反之，根據最大一致集判斷內外點，直到算法結束。

3.3.2 SURF算法與 RANSAC算法結合

為了通過RANSAC算法可以有效剔除誤匹配點，具體過程如下：首先，從SURF算法預匹配結果中隨機取出一些特征匹配點對，計算出變換矩陣；再根據得到的變換矩陣遍歷預匹配中得到的所有匹配對，計算所有預匹配對中在特定閾值下滿足該變換矩陣模型的百分比。重復上面的過程n次，比較每個變換矩陣下滿足該模型的匹配對百分比，選取對應百分比最大的矩陣作為最終得到的最佳變換矩陣。將在該最佳變換下誤差大于特定閾值的特征匹配對去除。再用去除后的特征匹配對重復上述步驟m次。

匹配過程具體參數設置如下：a是通過SURF算法預匹配后得到的特征匹配點對數；b是通過RANSAC算法進行去污匹配后所剩下的特征匹配點對數。當滿足式(11)關系時放棄所有的匹配點對，整個過程找出來的匹配點對數則為0[13]。

(11)

整個匹配過程如下：分別讀入兩幅圖像，對兩個圖像進行特征點匹配，當兩個圖像中找到的匹配點正好為對方的時候匹配成功，否則匹配失敗，然后用RANSAC算法去除預匹配中的誤匹配。

4 實驗結果分析

本文算法用MATLAB R2012a實現。本文考慮了光照、旋轉、縮放等多種因素，選擇了大量的實驗圖片，比較了傳統SURF算法與本文算法在特征點匹配性能上的差異。

4.1 頻率調諧顯著區域檢測實驗結果

頻率調諧算法處理過程簡單有效，圖5給出了所做實驗中幾幅圖像的處理結果，其中(a)、(c)為原圖，(b)、(d)為顯著性檢測后的結果。可以看出頻率調諧算法有很好的特征區域提取效果。為了避免在Lab空間3個均值圖像分量進行特征融合時，灰度值有可能超過有效顯示范圍的問題，本文對顯著圖的結果進行了歸一化處理。

圖5 顯著圖檢測結果

4.2 本文算法得到的特征點結果

基于得到的顯著圖，利用本文提出的分級篩選機制，對特征點進行提取實驗。圖6所示為其中的一幅圖像的實驗結果，其中，(a)為原圖，(b)為傳統方法得到的特征點，(c)為通過顯著圖篩選后的特征點，(d)為通過孤立點剔除篩選后的特征點，(e)為通過局部冗余篩選后的特征點。可以看出，隨著特征點分布的不斷優化，沒有分布在顯著區域中的缺少匹配價值的點、處在背景區里孤立的點、相似度較高的冗余點相繼被篩除，留下了最具有匹配價值的點，從而使特征點的精度和質量得到提高。另外，由于特征點的減少，計算時間和最終匹配效率都得到了優化。

圖6 特征點篩選結果

由表1可以得出，提取的特征點越多，所用的時間越多。因此采用本文算法來減少特征點提取個數在時間效率方面有很大改善。

表1 SURF算法時間分配比較

4.3 融合后的SURF匹配

特征點選取直接影響SURF算法的運算復雜度，如圖7所示，其中，(a)為傳統的SURF匹配結果，(b)為本文改進的SURF方法匹配結果。本文提出的算法更加優化了特征點的選擇，特征點數量得到了控制，減少了特征點描述子生成的時間。而且進一步的匹配實驗結果表明，通過本文算法可以最大程度保證特征點落在視覺更加顯著的有效區域內。

圖7 實驗結果對比

在特征向量匹配時，采用最簡單的兩向量內積最大值為最匹配的點，設定閾值n，只有當這個最大值大于該閾值方可認為兩特征點匹配，通過優化后的匹配點選擇，找到了相似性更高的匹配點，降低了誤匹配。最后再通過RANSAC算法對特征匹配點對進行檢測，篩選出錯誤的匹配，進一步優化匹配效果。

根據表2可得，傳統SURF算法的效率和準確率都有缺陷，本文算法在這兩方面都進行了優化，尤其是在匹配準確率上得到了較大的優化，比傳統算法平均準確率提升了18%以上。

表2 本文算法與傳統SURF匹配對比結果

5 結語

傳統SURF匹配算法存在的不足，通過本文提出的方法得到了有效解決。顯著性區域檢測和特征點篩選使得特征點的數量有效減少，特征描述子和匹配速度得到了一定提升，RANSAC算法檢測使得匹配過程中出現的誤匹配進一步得到優化。但是實驗結果對顯著區域檢測結果有一定的依賴，所以本文提出的方法在目標相對顯著的圖像中能夠達到更好的效果。

[1] FRSTNER W,GLCH E. A fast operator for detection and precise location of distinct points, corners and circular features[C]. ISPRS intercommission conference on fast processing of photogrammetric data，1987:281-305.

[2] HARRIS C.A combined corner and edge detector[C].Alvey Vision Conference,1988:147-151.

[3] MOREVEC H P. Towards automatic visual obstacle avoidance[C].International Joint Conference on Artificial Intelligence.1977:584-584.

[4] LOWE D G. Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision,2004,60(60):91-110.

[5] BAY H,TUYTELAARS T,GOOL L V. SURF:speeded up robust features[J].Computer Vision & Image Understanding,2006,110(3):404-417.

[6] CECCARELLI M,MUSACCHIA F,PETROSINO A.A fuzzy scale-space approach to feature-based image representation and retrieval[M].Brain, Vision, and Artificial Intelligence. Springer Berlin Heidelberg, 2005:377-385.

[7] SCHLEICHER J,TYGEL M,HUBRAL P I.Hessian matrices[M].Society of Exploration Geophysicists, 2007.

[8] ACHANTA R, HEMAMI S, ESTRADA F, et al. Frequency-tuned salient region detection[C].IEEE International Conference on Computer Vision and Pattern Recognition (CVPR 2009).2009:1597-1604.

[9] CHEUNG W,HAMARNEH G.Dimensional scale invariant feature transform[J].IEEE Transactions on Image Processing,2009,18(9):2012-2021.

[10] NANDI S,GUHA P,VENKATESH K S.Objects from animacy:joint discovery in shape and haar feature space[C].Computer Vision, Graphics & Image Processing, 2008. ICVGIP '08. Sixth Indian Conference on. 2008:730-737.

[11] 陸聲鏈, 林士敏. 基于距離的孤立點檢測及其應用[J]. 計算機與數字工程, 2004, 32(5):94-97.

[12] LEBEDA K,MATAS J,CHUM O.Fixing the locally optimized RANSAC[C].British Machine Vision Conference,2012.

[13] 陳藝蝦,孫權森,徐煥宇,等.SURF算法和RANSAC算法相結合的遙感圖像匹配方法[J].計算機科學與探索,2012,6(9):822-828.

(責任編輯：陳福時)

河北省自然科學基金項目(F2015202239)；天津市科技計劃項目(14RCGFGX00846)

陳謙(1991-)，男，陜西興平人，河北工業大學計算機科學與軟件學院碩士研究生，研究方向為圖像處理和模式識別；吳清(1965-)，女，湖北鐘祥人，博士，河北工業大學計算機科學與軟件學院教授，研究方向為圖像處理和模式識別。

10.11907/rjdk.162587

TP312

A

1672-7800(2017)003-0022-04