一種基于歷史特征的SURF改進算法研究

黃進勇　李哲　張天凡

摘 要： 圖像配準是數字圖像處理深度應用的基礎之一，其中基于SURF的圖像配準算法因識別率高而得到廣泛的研究與應用，但其數據量大且對計算要求較高，因此提出一種基于對象關聯的配準方法，在SURF前端提取對象ROI以檢測是否有新的對象進入檢測區域從而將新舊對象分為兩類分別處理，對于已經存在的對象可根據運動特征關聯進行進一步過濾，較大幅度地減少重復特征點的檢測和計算，也可避免依賴局部區域像素的梯度方向造成過大的誤差。實驗結果表明，改進的算法提高了配準率，減少了約20%的計算量，幀率下降至0.8左右時趨于穩定，保證了較好的實時性。

關鍵詞： SURF算法； Hessian矩陣； 運動對象識別； 匹配率

中圖分類號： TN911.73?34 文獻標識碼： A 文章編號： 1004?373X（2017）03?0038?05

Research on a SURF improved algorithm based on historical characteristics

HUANG Jinyong1， LI Zhe1， 2， ZHANG Tianfan1， 2

（1. College of Technology， Hubei Engineering University， Xiaogan 432000， China；

2. School of Automation， Northwestern Polytechnical University， Xian 710072， China）

Abstract： The image registration is one of the fundaments for further application of the digital image processing. The SURF?based image registration algorithm is widely researched and applied due to its high recognition rate， but it has large data quantity and high calculation requirement， so a registration method based on object association is proposed. The object ROI is extracted in the front end of SURF to detect whether a new object has entered into the detection area， so as to divide the old and new objects into two classes for processing. The existing objects can be further filtered according to the motion feature association to significantly reduce the detection and calculation of the repeated feature points， and avoid the excessive error caused by relying on the gradient direction of the local region pixel. The experimental results show that the improved algorithm has improved the registration rate， its calculation quantity is reduced by 20%， its frame rate trends to be stable when it is dropped to about 0.8， and the algorithm insures good real?time performance.

Keywords： SURF algorithm； Hessian matrix； moving object recognition； matching rate

0 引 言

運動目標識別一直是機器視覺領域的研究熱點。它已被廣泛應用于視頻監控、測繪、機器人導航等領域中。SURF（Speeded Up Robust Features）[1] 是近年應用廣泛的一種匹配算法，采用了Harr特征以及積分圖像概念，使得同等條件下標準的SURF算子快于典型的SIFT[2] 算子數倍，大幅度地減少了計算時間，同時在連續的圖像下也具有很好的魯棒性[3] 。在SURF的基礎上，文獻[4] 從材料的光照反射率角度提出一種能量函數進行目標匹配，對三維環境下多角度拍攝的視頻匹配有較大的改進；文獻[5]根據相鄰像素在平滑和邊緣地區可能各不相同，提出光滑能量函數，能量函數的擴散速度由梯度、線點等信息確定，從而降低深度不連續區域的失配率。文獻[6]提出一種改進的PatchMatch算法，通過積累強度差異或者顏色相異度之間連接的像素，沿路徑計算以獲得相鄰圖像之間的關聯性，從而改善匹配準確度。

由于SURF算法中主要使用相鄰幀數據進行計算，早期運動特征數據被當前較短時間的信息所取代，使得SURF只能反映當前 “瞬間”狀態，易被噪聲干擾，從而導致該算法匹配率較低。此外，基于局部區間像素的梯度方向易受主方向影響，即使是一個小角度的偏差也會導致特征匹配失誤，從而顯示錯誤的匹配結果。

針對該問題，提出一種實時更新特征點的優化方案，存儲對象ROI及該區域內特征點構建一段時間內的歷史特征，改善匹配率；通過實時更新特征點，去除重復特征，維持較低的運算率。在實驗部分，利用OpenCV3輕量及高效的特性[7]，并結合VS2015實現了該改進算法，樣本匹配率提升約15%，同期處理幀率穩定在0.8，基本能夠達到實時性處理的要求。

1 SURF特征點檢測模型

典型的SURF算法主要包括獲取對象ROI、特征點監測、特征向量的提取和匹配標記[8] ，如圖1所示。

在構建SURF算法前需要得到相應的Hessian矩陣，進而構建高斯金字塔尺度空間，然后再構建SURF特征點進行特征匹配。

1.1 構建Hessian矩陣及高斯金字塔尺度空間

1.1.1 構建Hessian矩陣

從數學的角度來講，海森矩陣（Hessian Matrix）是一個由多元函數的二階偏導數組成的方塊矩陣。對比SIFT算法，Hessian矩陣的行列式近似值圖像遠遠優于DOG圖像，SURF算法加快了檢測的速度，從而較優于SIFT。設函數[fx，y，]Hessian矩陣[H，]圖像中任意一個像素點的Hessian矩陣如下[9] ：

[Hfx，y=?2f?x2?2f?x?y?2f?x?y?2f?y2] （1）

設判別式DET對[H]矩陣的特征值進行分類，通過判別式得到的值對所有的點進行分類，并根據判別式的正負決定該點是否為極值。判別式DET如下：

[DETH=?2f?2f?x2?y2-?2f?x?y2] （2）

將圖像像素[Lx，y]代入函數[fx，y，]設置標準高斯濾波器，經過特定內核卷積計算二階偏導數，得到[H]矩陣的三個矩陣元素[Lxx，][Lxy，][Lyy]。計算[H]矩陣：

[H（x，σ）=Lxx（x，σ）Lxy（x，σ）Lxy（x，σ）Lyy（x，σ）] （3）

1.1.2 高斯平滑處理

構造Hessian矩陣前必須確定特征點在尺度上無噪聲，通過高斯濾波處理可以有效地降低特征點噪聲。經過濾波后的Hessian計算公式如下：

[L（x，t）=G（t）?I（x，t）] （4）

式中[L（x，t）]為一幅圖像對應不同程度解析下的圖像，可用于高斯核[G（t）]和圖像函數[I（x）]在點[x]的卷積來實現，其中高斯核[G（t）]的計算公式如下：

[G（t）=?2g（t）?x2] （5）

式中：[g（x）]為高斯函數；[t]為高斯方差。根據該方法可以計算出圖像任意像素的決定值，并用該方法確定特征點。

由于求Hessian時需要先高斯平滑再求二階導數，所以在這里離散的像素點用模板卷積形成，這兩種操作步驟用一個模板代替即可。

1.1.3 建立相關金字塔結構

經過變換后得到一張類似于SIFT中DOG圖的近似Hessian的行列式圖。在金字塔結構中，圖像被分為多個層，每層被稱為octave，每個octave有幾個不同尺度的圖片。在SURF中，圖片的大小始終不變，而不同octave層中用到的高斯模板尺度也不相同。該算法可以同時處理多幅圖像的尺度空間，而不需要進行圖像的雙采樣，從而提高計算性能。

與SIFT算法類似，SURF算法將Hessian矩陣處理的像素點與其三維領域的點逐一比較，如某一像素點是該矩陣像素中的極值，則保留下來作為初始特征點。最后，使用相應大小的濾波器進行檢測。

如圖2所示為[3×3]的濾波器，對模糊圖像九個像素點的特征點進行檢測，并將剩下的八個模糊層與上下兩模糊層九個像素對應比較。圖中標記“◆”的特征值大于周圍像素，可以確定為該區域的特征點。

1.2 篩選關鍵點集合

通過三維線性插值法對關鍵點的位置和尺度進行采集，得到圖像中SURF候選特征點集合[X0，]從中選擇具有穩定性的點作為該圖像的SURF特征點，設其組成的集合為[X，]由于[X0]中有部分點容易受到對比度的影響而成為噪聲點，同時位于圖像中邊緣的點難以定位，所以出于SURF算法的穩定性考慮，這兩種點需要去除。

1.2.1 剔除對比度低的點

將候選特征點[x]的偏移量定義為[Δx，]其對比度為[H（x）]的絕對值，對[x]的Hessian表達式進行泰勒級數展開：

[H（x）=H+?HT?xΔx+12ΔxT?2HT?x2Δx] （6）

由于[x]為Hessian計算公式的極值點，所以[?H（x）?x=0，]解方程得：

[Δx=-?2H-1?x2??H（x）?x] （7）

通過迭代多次后得到穩定的特征點的位置及尺度[x，]將其代入公式求得[Hx，]求其絕對值可得[Hx]。設對比度閾值為[T，]則對比度點的剔除公式為：

[x∈XH（x）≥Tc，x∈X0x∈XH（x）

1.2.2 剔除邊緣點

由于邊緣梯度方向上的主曲率值較大，而邊緣方向上曲率較小，在邊緣上得到的Hessian的極值點與非邊緣區域的點相比，其主曲率比較大，因此可以將主曲率比較值大于一定閾值的點視為邊緣上的點，將其剔除。由于候選點Hessian的[H（x）]的主曲率與[2×2]的Hessian矩陣[H]的特征值成正比：

[H=LxxLxyLxyLyy] （9）

式中：[Lxx，][Lxy，][Lyy]為候選點領域對應位置的像素差分；令[α]為[H]的最大特征值，[β]為[H]的最新特征值，令[γ=αβ，]則[H（x）]的主曲率比值與[γ]成正比。由[H]的幾何行列式的值可得：

[Tr（H）=Lxx+Lyy=α+β] （10）

[DET（H）=LxxLyy-（Lxy）2=αβ] （11）

[Tr（H）2DET（H）=（α+β）2αβ=（γβ+β）2γβ2=（γ+1）2γ] （12）

式中：[（γ+1）2γ]只與兩特征值之比有關，與特征值自身大小無關，隨著[γ]的增大而增大；設主曲率比值閾值為[T，]則邊緣點的剔除公式為：

[x∈XTr（H）2DET（H）≤（Tγ+1）2Tγ，x∈X0x?XTr（H）2DET（H）>（Tγ+1）2Tγ，x∈X0] （13）

剔除低對比度和邊緣點后所剩特征點如圖3所示。

1.3 SURF特征描述算子

1.3.1 選取特征點的主方向

SURF在生成特征矢量時，為保證特征矢量具有選擇不變性，需要對每個特征點分配一個主方向。因此，SURF算法以特征點為中心，對6 s（s為特征尺度單位）的半徑圓形區圖像的Harr小波響應進行運算。與SIFT在求取特征點主方向不同，SIFT是以特征點為中心，在以[1.6?]為半徑的領域內計算梯度方向直方圖[10] 。如圖4所示，在求取特征點主方向時，兩種算法都以帶寬模板的Harr小波為考慮要素，而圖像區域的梯度實際是一樣的。

針對Harr小波的響應值，以[σ=2 s]為參數進行高斯加權，并設計了一個以特征點為中心，滑動[π3]的扇形窗口，得到特征點的主方向，如圖5所示。

如圖5所示，與約0.2的[Harr]旋轉的滑動窗口的步長和圖像的小波響應值[dx，][dy]進行圖像的滑窗積累，得到矢量[（mω，θω）]：

[mω=ωdx+ωdyθω=arctanωdxωdy] （14）

[Harr]響應累計值對應最高的方向為主方向，這是最長的向量對應的方向，即：

[θ=θωmaxmω] （15）

1.3.2 構造SURF特征點描述子

生成特征點描述算子與確定特征點的方向類似，需要對圖像的Harr小波響應進行計算。但與圓形計算區域不同，需要在一個矩形區域內計算Harr小波響應。以特征點為中心，將20×20圖像特征點的主方向分成4×4的子塊，利用[Harr]小波響應計算各塊模板尺寸，然后對響應值進行統計，[dx，][dx，][dy，][dy]形成特征矢量，如圖6所示。

圖6中以特征點為中心，以20 s為邊長的矩形窗口為特征描述算子計算使用的窗口，特征點到矩形邊框的線段表示特征點的主方向。將20 s的窗口劃分為4×4的子窗口，每個子窗口中有5×5個像元，使用尺度為2 s的[Harr]小波對子窗口圖像進行響應值計算，共進行25次采樣，得到與主方向一致的矢量[dy]和對應初值方向的矢量[dx。]然后以特征點為中心，對[dx，][dy]進行高斯加權計算，其中[σ=3.3 s]。最后，得到每個子塊的響應值，并得到每個子塊的矢量：

[V子塊=dx，dx，dy，dy] （16）

2 針對視頻問題的優化

在SURF算法應用中，對于圖像與圖像間的匹配有著不錯的匹配率，但在視頻中單以SURF算法進行暴力匹配的話，會有匹配率低的問題，而其主要的問題是，其匹配模板中包含的人物特征點具有一定的局限性：不是全方位的特征，與其他特征點有重復等問題。針對上述問題，對人物特征點處理進行優化，其流程圖如圖7所示。

圖7中，實線部分為原有的SURF對視頻的處理過程，而虛線部分則是對視頻問題的優化。將每一幀的特征點進行收集，增加特征點集的特征點數解決人物特征點的局限性，提升匹配成功率。

3 測試結果分析

在算法測試結果中，通過靜態圖像對比測試和視頻圖像對比測試兩方面對SURF算法進行測試分析。其中，測試部分所用的圖像與視頻皆來自于作者實驗室實際拍攝的視頻源，測試結果圖中顯示的為其中所有測試結果的一部分。測試硬件環境為Windows 7，Intel i5?4440 3.1 GHz，內存16 GB，軟件環境為Visual Studio 2015，OpenCV 3。

3.1 靜態圖像測試

如圖8所示，取視頻片段進行測試。以圖8（a），圖8（b）中的人物作為匹配模板，并以該模板對自身進行匹配測試，測試匹配結果顯示為吻合。在圖8（c），圖8（d）中，以圖8（a），圖8（b）的模板進行配，圖8（c）匹配結果吻合，但圖8（d）中有個別錯誤匹配連接。

以上述人物模型為匹配模板，對視頻片段中連續的100幅靜態圖像進行匹配測試，將匹配率按10%分割為10個匹配端統計，其測試結果如圖9所示。結果顯示，只用SURF對不同圖像進行人物匹配，穩定匹配率在40%～49%之間。

3.2 視頻圖像測試

采用之前對連續不同幀匹配率偏低問題的優化方案對視頻進行測試，其結果如圖10所示。

圖10（a）～圖10（c）中對緩慢行走的人物進行匹配，可以穩定地顯示其人物編號0。圖10（d）～圖10（f）中對快速奔跑的人物進行匹配，可以穩定地顯示其人物編號1。圖10（g）～圖10（i）中分別出現了人物0和人物1，可以看到能準確地進行識別。

上述測試結果表明，本文進一步優化了SURF對連續幀匹配率低的問題。但是在實驗中，連續處理了一段時間的視頻數據后，有計算速度明顯下降的趨勢。所以又對連續幀匹配時的幀率進行統計測試，其結果如圖11所示。

結果顯示，在連續幀處理時，隨著時間的增加，幀率呈現一種下降趨勢，直到指數為0.8時才穩定下來。當指數在1以上時視頻能穩定地顯示結果，而當指數低于1時，則會顯得卡頓。

4 結 論

本文對連續不同幀匹配率偏低的問題提出了優化方案，并結合視頻進行測試，雖然幀率仍然會出現下降，但隨著計算時間的推移逐步趨于穩定，而且由于使用了對象歷史特征信息從而能夠較好地避免依賴局部區域像素的梯度方向造成過大的誤差。同期算法對數據存儲空間的要求維持在較高水平，因此可以進一步從同一對象相關特征點的檢測、匹配和重復性檢測方面進行改進，進一步提高算法效率。

參考文獻

[1] BAY H， ESS A， TUYTELAARS T， et al. Speeded?up robust features （SURF） [J]. Computer vision and image understanding， 2008， 110（3）： 346?359.

[2] LOWE D G. Object recognition from local scale?invariant features [C]// Proceedings of 1999 International Conference on Computer Vision. Washington， D. C.： IEEE， 1999： 1150?1157.

[3] 張銳娟，張建奇，楊翠.基于SURF的圖像配準方法研究[J].紅外與激光工程，2009，38（1）：160?165.

[4] YANG Menglong， LIU Yiguang， CAI Ying， et al. Stereo mat?ching based on classification of materials [J]. Neurocomputing， 2016， 194（C）： 308?316.

[5] ZHOU Zhiyu， WU Dichong， ZHU Zefei. Stereo matching using dynamic programming based on differential smoothing [J]. Optik?international journal for light and electron optics， 2016， 127（4）： 2287?2293.

[6] JIANG Yutong， SUN Changming， TAN Xiao， et al. Orientation?guided geodesic weighting for PatchMatch?based stereo mat?ching [J]. Information sciences， 2016， 334/335： 293?306.

[7] 李建，孔令寅.基于OpenCV的立體匹配算法的研究與實現[J].計算機工程與設計，2013，34（2）：566?569.

[8] 時磊，謝曉方，喬勇軍.基于SURF算法的人臉跟蹤技術研究[J].計算機仿真，2010，27（12）：227?231.

[9] 包加桐，宋愛國，郭晏，等.基于SURF特征跟蹤的動態手勢識別算法[J].機器人，2011，33（4）：482?489.

[10] 趙璐璐，耿國華，李康，等.基于SURF和快速近似最近鄰搜索的圖像匹配算法[J].計算機應用研究，2013，30（3）：921?923.