基于SURF的壓縮跟蹤算法研究*

李　倩,劉　坤

(上海海事大學 信息工程學院，上海 201306)

?

基于SURF的壓縮跟蹤算法研究*

李倩,劉坤

(上海海事大學 信息工程學院，上海 201306)

目標跟蹤技術(shù)作為機器視覺領(lǐng)域中的基礎(chǔ)，有著廣泛的應(yīng)用，但其仍然存在許多問題。為了解決目標在光照變化和快速移動場景下跟蹤漂移的問題,提出了基于SURF的壓縮跟蹤算法。首先選擇跟蹤目標并提取SURF特征，其次采用壓縮感知理論對SURF高維特征降維，來減少特征描述的維數(shù)和計算時間，最后篩選壓縮后的樣本特征并訓練分類器，來實現(xiàn)對多種復雜場景下目標實時準確跟蹤。通過實驗與傳統(tǒng)的SURF算法和Compressive Tracking(CT)算法的對比，證明該算法不僅大大減少了目標在跟蹤的過程中的計算量，其跟蹤的實時性和準確性相較于CT算法和SURF算法都有所提高。

目標檢測；SURF；壓縮感知；目標跟蹤

引用格式：李倩，劉坤．基于SURF的壓縮跟蹤算法研究[J].微型機與應(yīng)用，2016,35(16)：63-66，71.

0　引言

目標跟蹤技術(shù)作為機器視覺中的一個重要研究領(lǐng)域，其應(yīng)用已經(jīng)得到廣泛的普及。但目前目標跟蹤仍面臨著一些亟待解決的問題，如目標形態(tài)的改變、外界光照場景的變化、目標部分遮擋、快速移動或突然停止等。近年來目標跟蹤的主流方法多是基于特征的匹配[1]，提取目標中具有不變性的特征(角、點、邊緣等)，通過目標特征的模板匹配來實現(xiàn)目標的跟蹤過程，它的優(yōu)點是計算量較小，抗干擾能力強，但是對于一些較大尺寸的目標，仍然無法很好地實時跟蹤，且不能很好地處理目標遮擋的問題。壓縮感知理論[2-4]的引入，減少了目標跟蹤算法的計算量，同時在處理一些復雜場景上有了突破性的進展，提高了目標跟蹤的魯棒性。2012年張開華等人提出了壓縮跟蹤算法(CT)[2]，該算法提高了實時性，但是針對目標遮擋、光照變化這些問題有待提高。

本文提出了一種將SURF特征[5-6]和壓縮感知相結(jié)合的目標跟蹤算法，在目標提取的時候選取了在圖像發(fā)生平移、旋轉(zhuǎn)等情況下仍具有強大表達能力的SURF特征，通過壓縮感知理論中的稀疏測量矩陣，將高維空間的SURF特征投影到低維空間，同時通過一定的閾值對壓縮的特征篩選并訓練分類器，來實現(xiàn)目標的跟蹤。通過實驗驗證，本文提出的算法不僅克服了目標遮擋、快速移動和光照變化的問題，還有效地提高了跟蹤的實時性。

1　壓縮感知理論

壓縮感知理論[7-8]指出：如果原始圖片序列提取的特征空間維度非常高，不利于后續(xù)的跟蹤計算，那么這些特征就可以通過一個稀疏基來實現(xiàn)低維特征的投影，與此同時，投影后的低維特征仍將保留足夠的信息去重構(gòu)出高維的原始特征。

下面將從3方面來闡述壓縮感知理論。

(1)信號的稀疏表示為x=Ψs，Ψ為稀疏基N×N矩陣，s為稀疏系數(shù)；

(2)測量矩陣的設(shè)計Φ=M×N(M<

(3)重構(gòu)原始特征，將原始特征x從壓縮的特征信號y中完整重現(xiàn)、最快速的方法就是通過l0范數(shù)來求解：

(1)

然而l0范數(shù)的求解是一個很難實現(xiàn)的問題，為了能夠更好地解決這個問題，DONOHO D和LOGAN B證實了如果特征信號足夠稀疏，那么l0最小范數(shù)就可以完全等價于l1最小范數(shù)，同樣可以得到相同的解，即：

(2)

2　基于SURF的壓縮跟蹤算法

基于SURF算法的目標跟蹤能夠很好處理目標尺度變化和光照變化的場景，而壓縮感知可以用很少的采樣值幾乎完整地重構(gòu)出原始信號，故本文提出了基于SURF的壓縮跟蹤算法。該算法既保留了SURF特征的優(yōu)點，減少了目標跟蹤過程中一些冗余特征的計算，加快跟蹤的實時性，同時在目標部分被遮擋和目標快速移動的場景下，仍能穩(wěn)定地跟蹤。

圖1所示為本文算法的流程圖，算法主要分為4個步驟：(1)選取目標特征并提取SURF特征；(2)通過壓縮感知中的稀疏測量矩陣將高維的前景目標和背景特征投影到低維空間，而這些低維特征一方面幾乎保留了原始圖像中的所有信息，另一方面減少了后續(xù)跟蹤的計算量；(3)通過一定的閾值對壓縮的樣本篩選，剔除小概率的樣本，訓練和更新分類器；(4)使用樸素貝葉斯分類器對下一幀目標待測圖像進行分類，并確定其精確位置。下面將詳細闡述算法的實現(xiàn)過程。

圖1　算法流程圖

2.1SURF特征提取

在SURF特征提取的過程中，采用了積分圖實現(xiàn)特征的描述，由于積分圖運用盒狀濾波近似圖像，極大地提高了特征提取的過程，而且提取的特征還具有旋轉(zhuǎn)不變和尺度不變的特性[5，9]。

在圖像G中一點(x,y)的值為ii(x,y),則SURF特征的提取包括以下5部分。

(2)提取特征點：首先通過Hessian矩陣粗略確定特征點，其次利用非極大抑制精確確定。

(3)確定特征點的主方向：以特征點為中心，6s為半徑的圓中，通過使用haar小波，分別計算每個扇形區(qū)域中x、y方向的響應(yīng)，其中響應(yīng)模值最大的扇形方向即為特征點的主方向。

(5)特征點匹配：計算兩幅圖像中每一個特征點的歐式距離，其中d1、d2分別為最小和次小的距離值，若d1/d2≤α(文中取α為0.6),則認為這兩個距離值對應(yīng)的特征點匹配，否則剔除該點。

2.2特征壓縮

本文采用的是提取過后的SURF特征，在壓縮感知的理論基礎(chǔ)上，對所得高維的特征進行降維處理，其公式如下：

v=Rx

(3)

其中x為特征向量，R為稀疏測量矩陣，v為壓縮的特征向量。在該算法中，最核心的部分就是稀疏測量矩陣的選取，本文采用的是一個極具典型且滿足有限等距性(RIP)的測量矩陣：隨機高斯矩陣R?Rn×m，矩陣中的每一個元素rij～N(0,1)，它的定義如下：

(4)

Achlioptas證明了當ρ=1或者ρ=3時的矩陣滿足Johnson-Lindenstrauss引理[2-3]，特別是當ρ=3的時候，矩陣中大部分的元素為0，大大減少了文中特征的計算量。

2.3樣本的預處理

正負樣本的質(zhì)量會直接影響到跟蹤結(jié)果的實時性和準確性，為了改變這種現(xiàn)象，對候選的樣本進行預處理。設(shè)σ(樣本像素值方差)為預處理的閾值，σi為候選樣本的像素值方差，如果σi<0.5σ，則認為該樣本不是目標樣本。經(jīng)過這樣的篩選方法，不僅可以減少分類器分類的次數(shù)，減少計算量，加快跟蹤的速度，而且還可以訓練出能夠更好區(qū)分背景和目標的分類器，提高跟蹤的精確度。

一是推進《河湖長制宣傳“六進”方案》深入實施，持續(xù)開展河湖長制系列化、多樣化宣傳，推動形成全社會共同關(guān)心河湖、建設(shè)河湖、保護河湖的良好局面。近兩年應(yīng)重點聚焦“進機關(guān)”“進黨?！?。

2.4分類器的構(gòu)造及更新

將以上得到的低維特征向量v通過樸素貝葉斯分類器來建模，下面是樸素貝葉斯分類器的模型：

H(v)=

(5)

(6)

(7)

其中學習率λ>0，λ越小，目標模板更新速度就越快。

3　實驗結(jié)果與分析

為了驗證本文算法的跟蹤效果，分別使用本文算法、CT算法和基于SURF跟蹤算法對skating、football兩個視頻序列進行了對比跟蹤，圖2為目標跟蹤結(jié)果對比圖，其中實線框代表本文算法，虛線框代表CT，點線框代表基于 SURF跟蹤算法。

圖2　跟蹤跟蹤結(jié)果圖

[10]中給出了跟蹤精度的定義：

(8)

其中，ROIT代表實際的跟蹤框，ROIG代表真實的目標框，實際跟蹤框和真實目標框的區(qū)域的交集與兩者區(qū)域的并集的比值即為跟蹤精度。若目標跟蹤精度低于0.5，則認為跟蹤失敗。

為了更形象地說明本文所提算法相對其他兩種算法具有更高的跟蹤精度，圖3給出三者的跟蹤精度對比圖。

(1)skating序列中，如圖2(a)、圖2(c)所示，基于SURF跟蹤算法由于在跟蹤的過程中需要目標特征更新，特別是當目標快速移動和被遮擋時很容易產(chǎn)生一些模糊的特征，從而使目標跟蹤結(jié)果出現(xiàn)較大的誤差。跟蹤精度曲線圖3(a)中，25～75幀由于目標快速移動出現(xiàn)了目標漂移的現(xiàn)象，150～190幀之間由于目標排位過程中被遮擋，導致目標跟蹤跟蹤失敗。CT算法雖然對目標移動和光照變化不大的情況下跟蹤效果較好，但是在圖2(b)幀中，光線突然變暗導致目標跟蹤結(jié)果甚至比基于SURF跟蹤算法要差。然而本文算法在處理此種場景時，并沒有出現(xiàn)以上的狀況。

(2)football序列中，如圖2(d)、圖2(e)所示，由于目標的激烈爭奪，會出現(xiàn)目標快速移動、目標碰撞的現(xiàn)象，基于SURF跟蹤算法出現(xiàn)了目標漂移；如圖2(f)所示，當目標被遮擋時，基于SURF跟蹤算法和CT算法均出現(xiàn)目標丟失。在跟蹤精度曲線圖3(b)中，由于目標全程均在快速移動致使基于SURF跟蹤算法跟蹤精度不高，在280～295幀之間，目標被遮擋，基于SURF跟蹤算法和CT算法跟蹤失敗。本文算法針對以上情況均跟蹤較好。

為了衡量算法的實時性，分別度量football、skating圖像序列每秒處理的幀數(shù)，實驗結(jié)果如表1所示。文中的算法均采用MATLAB2013a運行，硬件環(huán)境為Windows 7系統(tǒng)，第二代英特爾酷睿i5-2450M處理器和2GB內(nèi)存，實時性均可以達到要求。從實驗數(shù)據(jù)中可以看出本文算法優(yōu)于CT、基于SURF的跟蹤算法。

表1　不同視頻序列每秒運行的幀數(shù)　(f/s)

本文算法將SURF特征和壓縮感知理論結(jié)合，保留了SURF特征對光照和尺度變化不敏感以及壓縮感知能夠減少運算量的特點，并在訓練分類器時對樣本進行了預處理，保留區(qū)分度高的樣本。通過實驗對比得出，本文算法在處理光照變化、目標快速移動和目標部分遮擋方面，要優(yōu)于基于SURF跟蹤算法和CT算法，同時，算法的時效性也有了明顯的提高。

4　結(jié)論

本文提出了一種基于SURF的壓縮跟蹤算法，將SURF特征所具有的位置、尺度和旋轉(zhuǎn)不變的特性融入到壓縮感知理論中，實現(xiàn)了目標的稀疏表示，并有效地減少了高維特征的計算量，大大加快了目標跟蹤的速度。在優(yōu)化分類器方面，通過閾值篩選出一些目標與背景區(qū)別度較低的樣本，不僅減少了分類器分類的次數(shù)，而且還提高了樣本的質(zhì)量。通過實驗對比可知，改進后的算法在目標快速移動、目標遮擋和光照變化的環(huán)境下有著相對良好的跟蹤效果，并且實時性也明顯有了提高。本文算法在目標提取的過程中主要針對的是固定的目標特征，研究實現(xiàn)多個特征的融合，使跟蹤算法能夠處理更為復雜的場景將是未來研究的熱點。

參考文獻

[1] 王露露,張洪 ,高忠國.基于SURF的目標跟蹤算法[J].江南大學學報(自然科學版), 2012,11(5):515-519.

[2] Zhang Kaihua, Zhang Lei, YANG M H. Fast compressive tracking[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2014, 36(10):2002-2015.

[3] Zhang Kaihua, Zhang Lei, YANG M H. Real-time compressive tracking[C]. European Conference on Computer Vision-ECCV 2012, 2012,7574(1):864-877.

[4] 馬慶濤,唐加山.基于壓縮感知的測量矩陣研究[J].微型機與應(yīng)用, 2013,32(8):64-67.

[5] Zhang Kaihua, Song Huihui. Real-time visual tracking via online weighted multiple instance learning [J]. Pattern Recognition, 2013, 46(1):397-411 .

[6] BAY H, ESS A, TUYTELAARS T, et al. Speeded-up robust features (SURF)[J]. Computer Vision & Image Understanding, 2008, 110(3):346-359.[7] Li Hanxi, Shen Chunhua, Shi Qinfeng. Real-time visual tracking using compressive sensing [J]. IEEE Conference on Computer Vision Pattern Recognition, 2011,42(7):1305-1312.

[8] JAVANMARDI M, YAZDI M, SHIRAZI M A M. Fast and robust L0-tracker using compressive sensing[C]. 2015 2nd International Conference on Pattern Recognition and Image Analysis (IPRIA), 2015:1-6.

[9] PANCHAM A, WITHEY D, BRIGHT G. Tracking image features with PCA-SURF descriptors[C]. 2015 14th IAPR International Conference on Machine Vision Applications (MVA), IEEE, 2015:365-368.

[10] EVERINGHAM M, GOOL L V, WILLIAMS C K I, et al. The pascal visual object classes (VOC) challenge[J]. International Journal of Computer Vision, 2010, 88(2):303-338.

Research of compressive tracking algorithm based on SURF

Li Qian，Liu Kun

( College of Information Engineering, Shanghai Maritime University, Shanghai 201306,China)

As the basis of machine vision, target tracking technology has been widely used, but there are still a lot of problems. In order to deal with the problem of target tracking drift under illumination change and fast-moving scenarios, the compressive tracking algorithm based on SURF is presented in this paper. Firstly, it chooses the tracking target and extracts SURF features. Then, the SURF features can be projected to a randomly chosen low-dimensional space in combination with the compressive sensing theory to reduce its dimensions and computation time. Finally, it screens the compressed sample features and trains the classifiers with the online multi-instance learning algorithm to achieve the real-time accurate tracking of object in the complex environment. From the vast contrast experimental results among the traditional SURF algorithm, compressive tracking algorithm and the algorithm proposed in this paper, we can see that the algorithm greatly reduces the calculation of the target in the process of tracking compared with the compressive tracking algorithm and SURF algorithm. Meanwhile the accuracy of tracking is improved also.

target detection;speed up robust feature;compressive sensing;object tracking

航空科學基金(2013ZC15005)

TP391

A

10.19358/j.issn.1674- 7720.2016.16.019

2016-03-25)

李倩(1991-)，通信作者，女，碩士研究生，主要研究方向：圖像處理。E-mail：liqian6522@163.com。

劉坤(1982-)，女，博士，副教授，主要研究方向：智能信息處理、圖像處理。