趙天云, 鹿馨, 王洪迅, 李暉暉, 胡秀華

(1.西北工業(yè)大學 自動化學院, 陜西 西安　710129; 2.空軍工程大學 航空航天工程學院, 陜西 西安　710038)

?

尺度自適應結構輸出目標跟蹤算法

趙天云1, 鹿馨1, 王洪迅2, 李暉暉1, 胡秀華1

(1.西北工業(yè)大學 自動化學院, 陜西 西安710129; 2.空軍工程大學 航空航天工程學院, 陜西 西安710038)

摘要：針對目標尺度明顯變化時采用固定尺度的結構輸出目標跟蹤算法容易出現(xiàn)跟蹤失敗的問題，提出一種改進的尺度自適應目標跟蹤算法。新算法在傳統(tǒng)結構輸出跟蹤算法基礎上，將目標運動信息引入候選樣本采集過程，通過自舉濾波器的狀態(tài)轉移模型預測目標的當前位置和尺度，生成一組多尺度候選樣本集，避免了固定尺度的密集均勻采樣，實現(xiàn)尺度自適應的同時降低了算法的計算量。實驗結果表明，所提算法在目標發(fā)生明顯尺度變化、部分遮擋以及旋轉等情況下具有較高的魯棒性，且實時性相比于傳統(tǒng)結構輸出跟蹤算法明顯提高。

關鍵詞：實時控制；目標跟蹤；尺度自適應；結構支持向量機；自舉濾波器

目標跟蹤是計算機視覺領域的研究熱點之一，在人機交互、精確制導、視頻監(jiān)控等方面具有廣泛應用。近年來，目標跟蹤技術的研究取得了顯著進展，但是當存在目標尺度變化、光照改變、遮擋及背景干擾等復雜情況時容易引起跟蹤漂移，實現(xiàn)魯棒、實時的目標跟蹤仍然面臨重大挑戰(zhàn)。

近年來，基于檢測的目標跟蹤方法得到廣泛關注，該類方法將跟蹤視為二分類問題，利用在線訓練的分類器將目標從背景中辨別出來。文獻[3]將檢測、學習和跟蹤相結合，當目標短時間丟失后又出現(xiàn)在畫面時，檢測模塊可以重新發(fā)現(xiàn)目標進而繼續(xù)跟蹤，在長時間跟蹤任務中魯棒性非常高，但該方法的跟蹤模塊采用光流法來估計特征點的運動，當光照變化時容易丟失目標。文獻[4]將壓縮感知理論應用到跟蹤算法中，首先通過稀疏投影矩陣對特征進行降維，再由樸素貝葉斯分類器進行分類，獲得了非常高的實時性，但在線訓練分類器的過程中容易出現(xiàn)誤差累積，對目標外觀變化比較敏感。文獻[5]將結構支持向量機應用于目標跟蹤，該算法在線更新一組反映目標外觀變化的支持向量集，將與該支持向量集相關性最大的候選樣本位置作為跟蹤結果，適于長時間、目標外觀多變的跟蹤任務。但文獻[5]采用固定尺度的密集采樣的方式采集候選樣本，忽略了目標的尺度問題且計算量較大，而在實際應用中目標大小會不斷改變，算法極易將背景信息與目標信息混淆從而導致跟蹤失敗。

本文在文獻[5]的基礎上提出一種尺度自適應目標跟蹤算法，新算法引入自舉濾波器對目標運動狀態(tài)進行預測并生成少量多尺度候選樣本，可有效克服密集采樣尺度單一且計算量大的缺點；由結構支持向量機直接輸出目標的估計位置，避免了在線訓練分類器易發(fā)生的漂移問題。

1傳統(tǒng)結構輸出目標跟蹤算法

文獻[5]提出利用結構支持向量機來解決目標跟蹤問題，算法實時更新一組支持向量集S，其中正支持向量保存目標的視覺特征，負支持向量保存背景中干擾物的視覺特征，在目標跟蹤過程中將結構支持向量機響應值最大的候選樣本位置定義為目標位置。

若已知一組圖像片段集{x1,…,xn}?X及其標注信息{y1,…,yn}?Y,則利用機器學習解決問題時需要學習一個映射函數(shù)f:X→Y實現(xiàn)對未知圖像片段的自動標注。在結構支持向量機框架中,引入判別函數(shù)F:X×Y→R,則可以根據(jù)(1)式得到映射函數(shù)

(1)

在結構輸出目標跟蹤算法中,若已知第(t-1)幀圖像的目標位置為pt-1,在第t幀圖像中以pt-1為中心采集一組尺度相同的候選樣本集,則第t幀圖像中的目標位置可通過(2)式得到

(2)

(3)

由(3)式可知對判別函數(shù)的更新本質上就是對支持向量集以及相關參數(shù)的更新。得到目標的當前幀位置pt后,在第t幀圖像中以pt為中心采集一組未標簽的訓練樣本集{(x1,y1),…,(xn,yn)},定義損失函數(shù)

(4)

當?shù)趇個樣本的位置yi與pt的重疊率越高,損失函數(shù)越小,引入損失函數(shù)可解決所有候選樣本被平等對待的問題。

定義梯度為

(5)

目標外觀在運動過程中不斷變化,支持向量集維數(shù)會不斷增長,為防止由此產(chǎn)生的維數(shù)災難,采用閾值策略對支持向量集的維數(shù)加以限制。當維數(shù)大于閾值時,移除引起權向量w改變最小的負支持向量(xr,y),定義如下

(6)

綜上所述,傳統(tǒng)結構輸出跟蹤算法對目標外觀變化具有較強的適應性,但由于采用固定尺度的密集采樣方式采集候選樣本,當目標大小發(fā)生明顯變化時容易跟蹤失敗。

2尺度自適應結構輸出跟蹤算法

為解決傳統(tǒng)結構輸出跟蹤算法中尺度單一的問題,所提新算法利用自舉濾波器的狀態(tài)轉移模型預測生成一組多尺度粒子集作為候選樣本集,代替了密集均勻采樣,實現(xiàn)多尺度目標跟蹤的同時可有效降低算法的計算量。

2.1自舉濾波器

假設動態(tài)系統(tǒng)的狀態(tài)方程和觀測方程為

(7)

式中向量xk、zk分別表示系統(tǒng)k時刻的狀態(tài)和觀測;g(·)、h(·)表示系統(tǒng)的狀態(tài)轉移函數(shù)和觀測函數(shù);wk、vk表示過程噪聲和觀測噪聲。粒子濾波的核心思想是利用一組具有權值的離散抽樣粒子來近似系統(tǒng)的概率分布函數(shù)p(xk|z1:k),通常包括預測和更新2個步驟:

在預測階段,假定(k-1)時刻系統(tǒng)的概率分布函數(shù)p(xk-1|z1:k-1)已知,則可利用概率系統(tǒng)轉移模型來預測k時刻的先驗概率p(xk|z1:k-1),即

(8)

式中,p(xk|xk-1)為概率轉移模型。

在更新階段,假定k時刻的觀測值zk已知,則所求概率分布函數(shù)可根據(jù)貝葉斯規(guī)則得到,即

(9)

式中，p(zk|xk)可由觀測方程得到。

在自舉濾波器框架中,k-1時刻系統(tǒng)的概率分布函數(shù)p(xk-1|z1:k-1)可由一組隨機采樣的先驗粒子集{xk-1(i):i=1,…,Ns}近似表達,即

(10)

2.2基于自舉濾波器的狀態(tài)轉移模型和觀測模型

利用自舉濾波器對目標運動狀態(tài)進行多尺度預測可以有效解決目標跟蹤中的尺度問題,定義自舉濾波器的狀態(tài)向量為xk=(rk,lk,sk),其中rk、lk表示樣本的位置,sk表示樣本的尺度。當自舉濾波器的狀態(tài)空間維數(shù)增大時,為了確保樣本分布近似于系統(tǒng)的概率分布,樣本數(shù)量將呈指數(shù)形式增長從而導致計算量顯著增長,因此本算法假定樣本的長和寬以相同的尺度sk變化。在進行目標跟蹤時,首先根據(jù)目標的初始狀態(tài)構建一組粒子集{x0(i):i=1,…,Ns},該粒子集將經(jīng)過自舉濾波器的預測步驟生成跟蹤過程中的候選樣本集。

在預測階段,對于每個粒子xk-1(i),通過二階自回歸轉移模型預測得到粒子當前的狀態(tài)xk(i)

(11)

在更新階段,利用觀測模型估計每個粒子的權值。定義粒子觀測值正比于結構支持向量機響應值

(12)

定義粒子權值如下

(13)

此時某些粒子的權值很小,在多次迭代后粒子集將無法充分表示系統(tǒng)的概率分布函數(shù)。為了避免粒子退化現(xiàn)象,在進行下一幀目標跟蹤之前,需要對粒子進行重采樣。由于粒子權值正比于該粒子的結構支持向量機響應值,所以重采樣粒子集需保留具有較高權值的粒子,并重新調整粒子的分布,即

(14)

傳統(tǒng)結構輸出跟蹤算法采用密集采樣的方式采集候選樣本,當候選區(qū)域半徑為R時,樣本集維數(shù)為(2R)2,而本算法根據(jù)目標的運動狀態(tài)構建維數(shù)較小的多尺度樣本集,可有效降低計算量。

2.3尺度自適應目標跟蹤算法

本文提出的尺度自適應結構輸出目標跟蹤算法的具體實現(xiàn)步驟如下:

步驟1初始化。讀取目標的初始位置y0,提取Haar-like特征x0,分別進行粒子集和結構支持向量機的初始化:

1) 粒子集初始化。構建初始粒子集{x0(i):i=1,…,Ns},粒子權值qi=1/Ns,粒子k、(k-1)、(k-2)時刻的位置均為y0,尺度s=1。

2) 結構支持向量機初始化。將(x0,y0)作為正支持向量,梯度值最小的訓練樣本作為負支持向量,由SMO算法更新支持向量的系數(shù)和梯度值。

步驟2多尺度目標跟蹤:

1) 粒子多尺度預測。讀取第t幀圖像,根據(jù)狀態(tài)轉移方程式(11)對目標位置、尺度進行預測得到新的多尺度粒子集{xt(i):i=1,…,Ns}。

2) 目標定位。根據(jù)公式(3)計算每個粒子的結構支持向量機響應值,根據(jù)公式(2)確定目標在當前幀的位置pt,并根據(jù)公式(12)及(13)更新粒子權值。

步驟3更新結構支持向量機:

1) 添加新支持向量。采集訓練樣本并計算梯度值,將(xt,yt)作為正支持向量,由y-=argminy∈Ygi(y)確定負支持向量,由SMO算法更新支持向量的系數(shù)和梯度。

2) 更新支持向量集。計算所有支持向量的梯度值,分別將具有最大及最小梯度的支持向量作為新的正負支持向量,然后由SMO算法更新支持向量集的系數(shù)和梯度。

3) 閾值機制。若支持向量集的維數(shù)大于閾值,則根據(jù)公式(6)移除相應的負支持向量。

4) 迭代2)、3)以提高支持向量集的準確度。

步驟4粒子重采樣。根據(jù)公式(13)得到粒子權值qi,按照公式(14)重新調整粒子的分布。

步驟5置t=t+1,返回步驟2。

3實驗結果及分析

為驗證算法的有效性,在IntelCorei5-3280M,2.5GHz、4GBRAM的計算機上利用C++、OpenCV編程實現(xiàn),軟件環(huán)境為VisualStudio2010。設置粒子數(shù)目Ns=400,狀態(tài)轉移模型參數(shù)A=1.5,B=-0.5,高斯噪聲標準差分別為5、5、0.06;高斯核函數(shù)參數(shù)σ=0.2;訓練樣本采集半徑R=20像素;支持向量集維數(shù)閾值為100,迭代次數(shù)為10。選取兩段標準視頻carScale、walking2以及一段機載相機拍攝的肇事車輛逃逸監(jiān)控視頻進行測試,由文獻[7]提出的兩種指標評價跟蹤性能:由邊界框重疊率評價準確度,重疊率越高準確度越高;由中心定位誤差評價精度,誤差越小精度越高。將本算法與傳統(tǒng)結構輸出跟蹤算法Struck[5]及跟蹤-學習-檢測算法TLD[3]進行對比,重點分析本算法與Struck算法的差異。

實驗1carScale視頻中的汽車快速行駛,尺度變化非常明顯且存在遮擋情況。圖1為carScale視頻跟蹤過程中生成的支持向量集(白色和黑色矩形框分別表示正、負支持向量),可看到正支持向量反映了目標運動過程中的外觀變化情況。圖2為3種算法對carScale視頻的跟蹤結果,圖3為3種算法的跟蹤性能曲線。表1給出了3種算法的平均重疊率、平均誤差以及平均幀率。

圖1　carScale視頻的支持向量集可視化

圖2　3種算法對carScale視頻的跟蹤結果(每行圖像從左至右依次是第79、145、172、200和238幀)

隨著目標尺度不斷增大,Struck算法所采用的固定尺度跟蹤框僅能包含目標的少部分信息,跟蹤性能隨目標尺度不斷變大而呈指數(shù)形式降低;TLD算法具有尺度自適應性,但TLD算法的跟蹤模塊采用了中值光流法,對遮擋和光照變化非常敏感,從圖3可看出第150到180幀之間發(fā)生遮擋時TLD算法的跟蹤誤差較大。在238幀前后目標的尺度發(fā)生了顯著變化,僅有本算法的跟蹤框較準確的包含了目標。由表1可見相比Struck算法,本文算法的重疊率提高了60%,誤差降低了53%。當候選區(qū)域半徑為R=20時,Struck約采集1 600個候選樣本,而本文算法采集Ns=400個多尺度樣本,大幅降低了計算量,算法實時性提高了32%。

圖3　carScale視頻的跟蹤性能曲線

方法平均重疊率平均誤差/像素平均幀率/(幀·s-1)Struck0.389235.409214.5306TLD0.474523.120710.6335本文算法0.646516.485019.2481

實驗2walking2視頻中的行人存在尺度變化和相似物干擾的情況。圖4為walking2視頻跟蹤過程中生成的支持向量集(白色和黑色矩形框分別表示正、負支持向量)。圖5為3種算法對walking2視頻的跟蹤結果，圖6為3種算法的跟蹤性能曲線。

當行人尺度逐漸縮小時，Struck算法的跟蹤框引入了大量背景信息，跟蹤性能持續(xù)降低；TLD算法對同類干擾非常敏感，在第241幀中將干擾行人誤認為目標，由圖6可見在210幀及380幀前后存在遮擋時跟蹤誤差非常大。本算法的跟蹤框始終較準確的反映了目標位置，由表2可見本文算法的邊界框重疊率相比于Struck算法提高了48%，誤差降低了76%，實時性提高了60%，跟蹤性能最好。

圖4　walking2視頻的支持向量集可視化

圖5　3種算法對walking2視頻的跟蹤結果(圖片依次為第180、206、241、373、500幀)

圖6　walking2視頻的跟蹤性能曲線

方法平均重疊率平均誤差/像素平均幀率/(幀·s-1)Struck0.511013.562610.9653TLD0.369621.425013.4998本文算法0.75913.252617.5702

實驗3選取機載相機拍攝的肇事車輛逃逸監(jiān)控視頻，視頻中的汽車不斷進行旋轉、突然加速等動作。圖7為監(jiān)控視頻跟蹤過程中生成的支持向量集(白色和黑色矩形框分別表示正、負支持向量)。圖8為3種算法對監(jiān)控視頻的跟蹤結果，圖9為3種算法的跟蹤速度對比曲線。

在73幀到290幀之間汽車發(fā)生 的轉向且尺度變大，Struck算法的跟蹤框偏離了目標的中心位置，TLD算法在汽車旋轉后仍定位到目標但跟蹤框尺度自適應性不及本算法。在367幀前后目標尺度變小，Struck算法引入了大量背景信息，而本算法比TLD算法的跟蹤框更準確的包含目標。由圖9中可見本算法速度相對于Struck算法有明顯優(yōu)勢。

圖7　監(jiān)控視頻的支持向量集可視化

圖8　3種算法對監(jiān)控視頻的跟蹤結果(每行圖像從左至右依次是第73、168、200、291和367幀)

圖9　監(jiān)控視頻的跟蹤速度對比

4結論

本文結合實際應用背景需求，提出一種尺度自適應目標跟蹤新算法。算法在傳統(tǒng)結構輸出跟蹤算法的基礎上，采用自舉濾波器對目標運動狀態(tài)進行多尺度預測，有效解決了目標尺度因距離變化或像機變焦調節(jié)等因素而變化導致的跟蹤失敗問題。同時避免了對圖像進行密集均勻采樣，降低了算法計算量。實驗結果表明，該算法在目標發(fā)生明顯尺度變化、部分遮擋等情況下，具有較高的跟蹤精度和穩(wěn)定性。

參考文獻：

[1]Matteo Munaro, Emanuele Menegatti. Fast RGB-D People Tracking for Service Robots[J]. Autonomous Robots, 2014, 37(3): 227-242

[2]Babenko B, Yang M H, Belongie S. Robust Object Tracking with Online Multiple Instance Learning[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33: 1619-1632

[3]Kalal Z, Mikolajczyk K, Matas J. Tracking-Learning-Detection[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(7): 1409-1422

[4]Zhang K, Zhang L, Yang M H. Real-Time Compressive Tracking[C]∥2012 ECCV, 2012: 864-877

[5]Hare S, Saffari A, Torr P H S. Struck: Structured Output Tracking with Kernels[C]∥2011 IEEE International Conference on Computer Vision, 2011: 263-270

[6]Platt J. Fast Training of Support Vector Machines Using Sequential Minimal Optimization[M]. Advances in Kernel Methods——Support Vector Learning, 1999: 185-208

[7]Wu Y, Lim J, Yang M H. Online Object tracking: A Benchmark[C]∥2013 IEEE Conference on Computer Vision and Pattern Recognition, 2013: 2411-2418

[8]Smeulders A W M, Chu D M, Cucchiara R, et al. Visual Tracking: An Experimental Survey[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014, 36(7): 1442-1468

[9]馬偉,陳建國,張毛磊. 基于尺度自適應和跟蹤框自轉的視頻目標跟蹤[J]. 清華大學學報, 2012,52(1): 92-95

Ma Wei, Chen Jianguo, Zhang Maolei. Video Target Tracking Based on Scale Adaptation and Tracking Box Rotations[J]. Journal of Tsinghua University, 2012, 52(1): 92-95 (in Chinese)

Structured Output Target Tracking Algorithm with Scale Adaptation

Zhao Tianyun1, Lu Xin1, Wang Hongxun2, Li Huihui1, Hu Xiuhua1

1.School of Automation, Northwestern Polytechnical University, Xi′an 710129, China2.Aeronautical and Astronautical Engineering College, Air Force Engineering University, Xi′an 710038, China

Abstract:A new multi-scale tracking algorithm is proposed to solve the problem that the structured output tracking algorithm with fixed scale often leads to failure when the size of the target change obviously. Based on the original structured output tracking algorithm, the proposed algorithm introduces the velocity information of the moving target into the sampling process of candidate samples. A state transition model of the bootstrap filter is used to estimate the current position and scale, generate a set of multi-scale samples and avoid dense sampling with fixed scale, this allow to realize scale adaptation and reduce the calculation of algorithm. Experiments show that the proposed algorithm has strong robustness when the scale of target changed obviously or target is partially occluded, and achieve higher real-time performance than original structured output tracking algorithm.

Keywords:real-time control; target tracking; scale adaptation; structured SVM; bootstrap filter

收稿日期：2016-03-08

基金項目：航空科學基金(20131953022)與西北工業(yè)大學研究生創(chuàng)業(yè)種子基金(Z2015120)資助

作者簡介：趙天云(1970—)，西北工業(yè)大學副教授，主要從事計算機視覺、圖像與信息融合等的研究。

中圖分類號：TP391

文獻標志碼：A

文章編號:1000-2758(2016)04-0677-07