一種基于歷史特征的SURF改進(jìn)算法研究

黃進(jìn)勇　李哲　張?zhí)旆?/p>

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

關(guān)鍵詞： SURF算法； Hessian矩陣； 運(yùn)動對象識別； 匹配率

中圖分類號： TN911.73?34 文獻(xiàn)標(biāo)識碼： 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 引 言

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

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

針對該問題，提出一種實(shí)時(shí)更新特征點(diǎn)的優(yōu)化方案，存儲對象ROI及該區(qū)域內(nèi)特征點(diǎn)構(gòu)建一段時(shí)間內(nèi)的歷史特征，改善匹配率；通過實(shí)時(shí)更新特征點(diǎn)，去除重復(fù)特征，維持較低的運(yùn)算率。在實(shí)驗(yàn)部分，利用OpenCV3輕量及高效的特性[7]，并結(jié)合VS2015實(shí)現(xiàn)了該改進(jìn)算法，樣本匹配率提升約15%，同期處理幀率穩(wěn)定在0.8，基本能夠達(dá)到實(shí)時(shí)性處理的要求。

1 SURF特征點(diǎn)檢測模型

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

在構(gòu)建SURF算法前需要得到相應(yīng)的Hessian矩陣，進(jìn)而構(gòu)建高斯金字塔尺度空間，然后再構(gòu)建SURF特征點(diǎn)進(jìn)行特征匹配。

1.1 構(gòu)建Hessian矩陣及高斯金字塔尺度空間

1.1.1 構(gòu)建Hessian矩陣

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

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

設(shè)判別式DET對[H]矩陣的特征值進(jìn)行分類，通過判別式得到的值對所有的點(diǎn)進(jìn)行分類，并根據(jù)判別式的正負(fù)決定該點(diǎn)是否為極值。判別式DET如下：

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

將圖像像素[Lx，y]代入函數(shù)[fx，y，]設(shè)置標(biāo)準(zhǔn)高斯濾波器，經(jīng)過特定內(nèi)核卷積計(jì)算二階偏導(dǎo)數(shù)，得到[H]矩陣的三個矩陣元素[Lxx，][Lxy，][Lyy]。計(jì)算[H]矩陣：

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

1.1.2 高斯平滑處理

構(gòu)造Hessian矩陣前必須確定特征點(diǎn)在尺度上無噪聲，通過高斯濾波處理可以有效地降低特征點(diǎn)噪聲。經(jīng)過濾波后的Hessian計(jì)算公式如下：

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

式中[L（x，t）]為一幅圖像對應(yīng)不同程度解析下的圖像，可用于高斯核[G（t）]和圖像函數(shù)[I（x）]在點(diǎn)[x]的卷積來實(shí)現(xiàn)，其中高斯核[G（t）]的計(jì)算公式如下：

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

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

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

1.1.3 建立相關(guān)金字塔結(jié)構(gòu)

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

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

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

1.2 篩選關(guān)鍵點(diǎn)集合

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

1.2.1 剔除對比度低的點(diǎn)

將候選特征點(diǎn)[x]的偏移量定義為[Δx，]其對比度為[H（x）]的絕對值，對[x]的Hessian表達(dá)式進(jìn)行泰勒級數(shù)展開：

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

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

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

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

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

1.2.2 剔除邊緣點(diǎn)

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

[H=LxxLxyLxyLyy] （9）

式中：[Lxx，][Lxy，][Lyy]為候選點(diǎn)領(lǐng)域?qū)?yīng)位置的像素差分；令[α]為[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γ]只與兩特征值之比有關(guān)，與特征值自身大小無關(guān)，隨著[γ]的增大而增大；設(shè)主曲率比值閾值為[T，]則邊緣點(diǎn)的剔除公式為：

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

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

1.3 SURF特征描述算子

1.3.1 選取特征點(diǎn)的主方向

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

針對Harr小波的響應(yīng)值，以[σ=2 s]為參數(shù)進(jìn)行高斯加權(quán)，并設(shè)計(jì)了一個以特征點(diǎn)為中心，滑動[π3]的扇形窗口，得到特征點(diǎn)的主方向，如圖5所示。

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

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

[Harr]響應(yīng)累計(jì)值對應(yīng)最高的方向?yàn)橹鞣较?，這是最長的向量對應(yīng)的方向，即：

[θ=θωmaxmω] （15）

1.3.2 構(gòu)造SURF特征點(diǎn)描述子

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

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

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

2 針對視頻問題的優(yōu)化

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

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

3 測試結(jié)果分析

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

3.1 靜態(tài)圖像測試

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

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

3.2 視頻圖像測試

采用之前對連續(xù)不同幀匹配率偏低問題的優(yōu)化方案對視頻進(jìn)行測試，其結(jié)果如圖10所示。

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

上述測試結(jié)果表明，本文進(jìn)一步優(yōu)化了SURF對連續(xù)幀匹配率低的問題。但是在實(shí)驗(yàn)中，連續(xù)處理了一段時(shí)間的視頻數(shù)據(jù)后，有計(jì)算速度明顯下降的趨勢。所以又對連續(xù)幀匹配時(shí)的幀率進(jìn)行統(tǒng)計(jì)測試，其結(jié)果如圖11所示。

結(jié)果顯示，在連續(xù)幀處理時(shí)，隨著時(shí)間的增加，幀率呈現(xiàn)一種下降趨勢，直到指數(shù)為0.8時(shí)才穩(wěn)定下來。當(dāng)指數(shù)在1以上時(shí)視頻能穩(wěn)定地顯示結(jié)果，而當(dāng)指數(shù)低于1時(shí)，則會顯得卡頓。

4 結(jié) 論

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

參考文獻(xiàn)

[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的圖像配準(zhǔn)方法研究[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的立體匹配算法的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與設(shè)計(jì)，2013，34（2）：566?569.

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

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

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