改進的SURF特征提取與匹配算法

張曉宇，何文思，段紅燕，魏松濤

(蘭州理工大學機電工程學院，甘肅 蘭州 730050)

在機器視覺研究領域，圖像匹配一直是其中重要的組成部分。匹配算法根據(jù)其思想可以分為兩大類：基于區(qū)域匹配方法和基于特征匹配方法，其中基于特征的匹配方法有計算速度快、魯棒性好和對圖像變形不敏感等優(yōu)點，是常用的匹配方法。

SIFT(scale-invariant feature transform)[1]是最常用的特征點檢測算法，對圖片的平移、縮放、旋轉(zhuǎn)等具有不變特性，然而SIFT算法在計算特征點描述子的時候?qū)γ總€特征點都需要構建128維特征向量，這樣就降低了運算速度。Wang和Bay等[2-3]提出的SURF(speeded up robust features)算法，繼承了SIFT的不變性，并在提取圖像的特征點運算速度上比SIFT快3倍左右[4]。然而SURF算法在求取特征點主方向時受到局部區(qū)域像素梯度方向的影響，在匹配過程中僅使用歐氏距離作為評判標準，使得匹配產(chǎn)生較大誤差。本文提出一種改進SURF算法，先利用余弦相似度進行二次匹配來去除偽特征點，再使用隨機抽樣一致算法(random sample consensus，RANSAC)進一步降低誤匹配率。

1 SURF算法原理

SURF是一種具有高效性和高魯棒性的局部特征描述算法，其不僅對圖像旋轉(zhuǎn)、縮放具有極強的適應性，而且圖像環(huán)境在光照變化、視角變化、仿射變換和噪聲的情況下也能保持一定程度的穩(wěn)定性[5]。SURF特征匹配算法可以分為3個步驟：特征點檢測、構建特征描述子和特征點匹配[6]。

1.1 特征點檢測

特征點檢測可分為3步：尺度空間極值點檢測、精確定位極值點、選取特征點主方向。

1.1.1 尺度空間極值點檢測

(1)

由于圖像中的特征點需要具備尺度無關性，所以先對特征點進行高斯濾波消除特征點的相關性，再進行Hessian的計算。L(x，t)代表不同解析度下的圖像，計算公式如式(2)、(3)所示。

L(x,t)=G(t)·I(x,t)

(2)

(3)

式中：I(x,t)為圖像函數(shù)。

Herbert Bay提出用近似值代替L(x,t)以達到簡化計算的目的，同時引入權值帶消除誤差，權值大小會隨尺度變化而發(fā)生改變，則Hessian矩陣行列式為：

det(Happrox)=LxxLyy-(0.9Lxy)2

(4)

式中：det(Happrox)為像素點的Hessian矩陣行列式；Lxx,Lyy,Lxy為高斯濾波后圖像在各個方向的二階導數(shù)。

匹配圖像具有不同的空間尺度，圖像金字塔可以將模板圖像求解出多種尺度空間以適應匹配要求。傳統(tǒng)的金字塔結構各層待檢測圖片尺寸大小發(fā)生了變化，各子層在運算過程中都需要用高斯函數(shù)進行平滑處理，降低了運算效率，如圖1所示。但在SURF算法中，各個octave層之間的待檢測圖片尺寸大小是相同的，只改變了濾波器大小。采用這種方法縮短了采樣過程所消耗的時間，處理速度得到較大提高。

圖1 金字塔結構

1.1.2 精確定位極值點

將Hessian矩陣處理過的每個像素點與其三維領域的26個點進行對比，如果是極值點則保留，反之剔除，再通過三維線性差值法獲得亞像素級的特征點，并刪除檢測特征點中小于一定閾值的點。

1.1.3 選取特征點主方向

在特征點區(qū)域內(nèi)統(tǒng)計其haar小波特征，以60°扇形為單位，統(tǒng)計扇形區(qū)域內(nèi)所有特征點的水平和垂直haar小波特征總和，然后60°扇形以一定間隔進行旋轉(zhuǎn)，旋轉(zhuǎn)一周后以小波特征最大的扇形方向作為該特征點的主方向，過程示意圖如圖2所示。

圖2 特征點主方向求取過程

1.2 生成特征描述子

在特征點周圍選取一個正方形框，邊長為20s(s為該特征點的尺度)，方向為特征點的主方向，然后把該框分成16個子區(qū)域，每個子區(qū)域統(tǒng)計25個像素的水平和垂直方向的haar小波特征，從而形成四維向量V=[∑dx∑|dx| ∑dy∑|dy|]，歸一化后形成16×4共64維SURF描述算子[8]。其中dx為水平方向haar小波特征；dy為垂直方向haar小波特征；|dx|為水平方向haar小波特征的絕對值；|dy|為垂直方向haar小波特征的絕對值。

1.3 特征點匹配

特征點匹配就是把兩幅圖像中特征點一一對應，然后計算第一幅圖像的每一個特征描述子向量與第二幅圖像的特征描述子向量的歐氏距離，計算所得的最小值即認為是那個特征的最佳匹配。

2 匹配算法的改進

SURF算法匹配過程中，如果匹配圖像局部點領域信息相近和圖像視角不同，會引起兩個不同特征點描述符的匹配程度超過同一點的特征描述符匹配程度。因此在匹配的兩幅圖像中如果出現(xiàn)形狀相似區(qū)域，就會產(chǎn)生大量誤匹配。由于歐氏距離沒有考慮各特征描述子向量之間的相關性，本文進行二次匹配，對誤匹配對進行消除。

2.1 向量空間余弦相似度匹配

判斷兩個向量相似程度的準則一般有兩種：距離測度法和相似性函數(shù)法。距離測度法是根據(jù)向量空間上存在的距離來判斷向量間的差異程度。相似性函數(shù)是用函數(shù)值的大小來表明兩向量間的差異程度。本文在歐式距離測度的基礎上再用余弦相似度作為約束，通過設定相似性函數(shù)的閾值來去除多余的匹配點對。

余弦相似度測度，即計算特征點間的相似程度，將向量根據(jù)坐標值繪制到向量空間中，求得它們的夾角，并計算出夾角所對應的余弦值，此余弦值就可以用來表征兩個特征點向量的相似性。余弦值越大，說明兩特征點向量之間的夾角越小，匹配相似度越大。

具體方法：先使用歐氏距離選取初步特征點對，然后再使用余弦相似度函數(shù)進一步篩選，如果兩個向量的余弦值大于閾值K則保留，反之刪除。K可以根據(jù)實驗得到，對于2個向量a和b，余弦相似度S(a,b)表達式為:

(5)

使用余弦相似度對產(chǎn)生縮放和旋轉(zhuǎn)、亮度對比度改變、模糊、視角變化的4類圖像進行測試，選擇平均閾值K=0.975，測試結果見表1。

表1 測試結果

2.2 改進的RANSAC算法

RANSAC算法設立一個閾值把測量數(shù)據(jù)分為內(nèi)點和外點，其中內(nèi)點數(shù)據(jù)比較準確，因此利用內(nèi)點數(shù)據(jù)進行參數(shù)估計，以便刪除不準確的數(shù)據(jù)。此算法需要事先確定3個量[9]：隨機采樣次數(shù)、誤差容忍度(內(nèi)外點距離閾值)和一致集的大小(內(nèi)點總數(shù))。

在經(jīng)典的RANSAC算法中，計算最佳模型參數(shù)是遍歷所有可能的組合，并以誤差最小的一組作為最佳參數(shù)，往往導致計算量大、運行時間長。本文采用PROSAC(the progressive sample consensus)將余弦相似度匹配的結果作為排序的依據(jù)，在采樣時根據(jù)匹配結果由高到低進行排序，如此最有可能導致最佳參數(shù)的采樣會較早出現(xiàn)，從而減少隨機采樣次數(shù)、提高運算效率。

3 實驗結果與分析

用于實驗的硬件為聯(lián)想ThinkPad E420，其CPU主頻為2.2GHz，內(nèi)存4GB；程序在Visual Studio 2010開發(fā)環(huán)境下編寫。測試用圖為經(jīng)典測試圖像，以正確匹配率作為評價標準[11]。

(6)

式中：precision為正確率；falsematches為錯誤匹配；correctmatches為正確匹配。

使用原SURF算法和改進SURF算法分別處理測試圖像，如圖3～6所示，其中(a)為使用SURF算法匹配效果圖，(b)為改進SURF匹配效果圖。圖3為旋轉(zhuǎn)45°、尺度增加2倍，圖4為經(jīng)過模糊變化，圖5為亮度有較大改變，圖6為相機視角發(fā)生變化的。表2是實驗數(shù)據(jù)。

圖3 匹配旋轉(zhuǎn)和縮小圖像

圖4 匹配模糊變化圖像

圖5 匹配亮度變化圖片

圖6 匹配視角變化的圖片

圖像處理方式算法左圖特征點數(shù)量右圖特征點數(shù)量匹配點數(shù)量正確匹配點數(shù)量正確率/%時間/s旋轉(zhuǎn)和縮放SURF61441061437360.751.13改進SURF448224313096.771.31模糊SURF1681011689657.141.02改進SURF131621919100.001.24亮度SURF127881277861.411.14改進SURF105664242100.001.36視角SURF32732232720863.611.21改進SURF225230171694.111.32

從表2可知，改進SURF算法與原SURF算法相比，改進算法在不同條件下的圖像匹配正確率都有顯著提高，誤匹配率平均降低37%，匹配時間比SURF算法增加0.1～0.2s。使用余弦相似度進行二次匹配，需要選取的特征點平均減少20%～30%，說明本文算法穩(wěn)定可靠，對圖像產(chǎn)生旋轉(zhuǎn)、縮放、模糊、亮度和視角變化等情況都有較強的適應性。

使用SURF和本文算法對隨機拍攝的一幅照片進行匹配，余弦相似度閾值K=0.975，人工對匹配結果進行校驗，發(fā)現(xiàn)誤匹配對為0對，匹配正確率為100.00%，所用時間比SURF多0.12s，在可接受的范圍之內(nèi)，如圖7所示。

圖7 匹配實驗圖片

4 結束語

本文在用SURF算法提取特征點的基礎上結合余弦相似度進行進一步提取，很好地解決了SURF算法匹配中沒有考慮特征點空間位置關系從而導致誤匹配率高的問題。本文提出的方法可以在保證正確率的基礎上對圖像的旋轉(zhuǎn)、縮放、模糊、亮度變化和視角變化具有較強的魯棒性，匹配正確率較高。但是由于旋轉(zhuǎn)和視角變化易使相近特征點方向一致，導致余弦相似度進行二次匹配對誤匹配點去除不完全，還需要做進一步的研究。