朱征宇，李帥，朱威（.重慶大學(xué)計(jì)算機(jī)學(xué)院，重慶400030；2.軟件理論與技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室，重慶　400030）

基于自適應(yīng)模型的時空上下文跟蹤

朱征宇1，2，李帥1，朱威1
（1.重慶大學(xué)計(jì)算機(jī)學(xué)院，重慶400030；2.軟件理論與技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室，重慶400030）

針對當(dāng)前時空上下文目標(biāo)跟蹤算法存在的易發(fā)生模型漂移的問題，提出基于自適應(yīng)模型的時空上下文跟蹤算法。該算法通過對常規(guī)模板保存多個歷史快照模型作為多模板，當(dāng)歷史快照模板估計(jì)到比常規(guī)模板適應(yīng)性更強(qiáng)的結(jié)果時，立即對常規(guī)模板進(jìn)行回滾，可有效提升時空上下文跟蹤算法的魯棒性，在目標(biāo)快速運(yùn)動、快速旋轉(zhuǎn)、運(yùn)動模糊和嚴(yán)重遮擋的情況下依然跟蹤準(zhǔn)確。在Tracker Benchmark v1.0測試集上與原時空上下文目標(biāo)跟蹤算法的對比實(shí)驗(yàn)表明，平均正確率由38.61%提高到42.02%，并將平均中心坐標(biāo)誤差從85.57降低到62.78，而平均幀速則從45.89 fps下降到36.64 fps，依然滿足實(shí)時跟蹤的要求，表明該算法在面對多種因素干擾的場景下，仍能完成穩(wěn)定的實(shí)時跟蹤。

目標(biāo)跟蹤；實(shí)時跟蹤；時空上下文；自適應(yīng)模型；模板快照

國家科技支撐計(jì)劃重點(diǎn)項(xiàng)目（No.2011BAH25B04）、軟件理論與技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室

0　引言

視頻目標(biāo)跟蹤作為機(jī)器視覺領(lǐng)域的重要問題之一，是視頻內(nèi)目標(biāo)識別、行為識別等后續(xù)工作的基礎(chǔ)，所以目標(biāo)跟蹤有著廣闊的應(yīng)用前景，受到了世界各地研究者的高度關(guān)注。

目前實(shí)時跟蹤的熱點(diǎn)模型是基于在線學(xué)習(xí)的跟蹤，而其中又分為生成模型和判別模型兩種。生成模型以視頻目標(biāo)本身特征為考慮對象，根據(jù)目標(biāo)樣本生成模型參數(shù)，在后續(xù)幀中搜索與該模型特征最接近的圖像塊作為視頻目標(biāo)的結(jié)果。如使用顏色直方圖作為特征模板的跟蹤算法［2-3］。判別模型則將目標(biāo)與背景的區(qū)分度作為考慮對象，在特征空間中建立目標(biāo)與背景的判別函數(shù)，將后續(xù)的目標(biāo)跟蹤問題轉(zhuǎn)換成搜索具有目標(biāo)與背景具有最大區(qū)分度的視頻塊的問題。如基于SVM的光流跟蹤［4］，在線學(xué)習(xí)跟蹤［5］。目前從總體上講，判別模型相較于生成模型有一定的優(yōu)勢，由于生成模型丟棄了背景信息，而背景信息可以用來輔助判別一個樣本是否更偏離跟蹤目標(biāo)，而判別模型同時利用了目標(biāo)信息和背景信息，最終可以得到更好的跟蹤效果。

此外盡管視頻目標(biāo)跟蹤算法已經(jīng)研究發(fā)展了數(shù)十年，并且已有各式各樣的算法被提出，但是目前常見的跟蹤算法依然是基于線性結(jié)構(gòu)模型，如圖1（a）所示的時間線性結(jié)構(gòu)模型和1（b）中是貝葉斯平均結(jié)構(gòu)模型。這兩種模型都是簡單且可靠的選擇，因?yàn)樗芎芎玫剡m應(yīng)在線跟蹤類型的框架且后驗(yàn)概率密度傳播也非常簡單。但是這兩者模型過于簡單，或僅使用了前一幀結(jié)果或盲目的平均前向幀的結(jié)果，在某些場景下其估計(jì)的結(jié)果會不可靠，如突然的外觀變化、快速運(yùn)動以及遮擋等時，因此不能處理復(fù)雜環(huán)境下的目標(biāo)跟蹤。

1　時空上下文跟蹤算法

文獻(xiàn)［11］提出了一個基于時空上下文模型的快速魯棒性算法（STC）用于視頻目標(biāo)跟蹤，它本質(zhì)上是基于生成模型，但是加入了背景信息作為空間位置信息考量，用于輔助定位目標(biāo)中心，同時通過FFT加速實(shí)現(xiàn)了一個非常快速有效的跟蹤算法。

圖1　基于在線學(xué)習(xí)框架的跟蹤算法的常見圖解模型

每一個節(jié)點(diǎn)代表一幀，節(jié)點(diǎn)上的數(shù)字代表了視頻幀在時間軸上的先后順序

但是STC算法采用的結(jié)構(gòu)模型為貝葉斯平均模型，故而存在著易發(fā)生模型漂移的先天缺陷，其主要原因由于選擇了基于Markov時間平滑假設(shè)，導(dǎo)致其對每一幀的跟蹤都不加選擇地學(xué)習(xí)，極易導(dǎo)致誤差積累引起跟蹤漂移乃至失敗。如果算法能夠保存多個歷史快照模板，用于在必要時刻替換常規(guī)模板實(shí)現(xiàn)模板快照回滾即可實(shí)現(xiàn)主動丟棄掉某一段時間間隔內(nèi)的連續(xù)學(xué)習(xí)可能引入的積累誤差。另外待跟蹤目標(biāo)往往處于復(fù)雜的干擾環(huán)境，如遮擋、面內(nèi)外旋轉(zhuǎn)等，而當(dāng)這些干擾結(jié)束以后目標(biāo)將繼續(xù)變回原先之前的外觀特征，通過保存多個歷史快照模板，當(dāng)快照模板得到更好更佳的匹配，然后對常規(guī)模板進(jìn)行回滾，以便實(shí)現(xiàn)更加魯棒的跟蹤。

2　基于自適應(yīng)模型的時空上下文跟蹤

本文通過結(jié)合多模板和快照回滾的思想，提出一種適合應(yīng)用在對實(shí)時性要求較高的在線學(xué)習(xí)算法的自適應(yīng)結(jié)構(gòu)模型，如圖1（c）所示，并將之應(yīng)用在時空上下文跟蹤算法得到一種改進(jìn)的時空上下文目標(biāo)跟蹤算法（ASTC算法）。

新模型保存一定數(shù)量的歷史快照模板。每當(dāng)新的一幀到來時，同時使用快照模板和常規(guī)模板進(jìn)行預(yù)估計(jì)，當(dāng)快照模板估計(jì)到比常規(guī)模板適應(yīng)性更好的結(jié)果時，本文采納快照模板預(yù)估計(jì)得到的結(jié)果并用快照模板對常規(guī)模板進(jìn)行回滾，相當(dāng)于丟棄了從保存快照時刻開始到現(xiàn)在的這段時間間隔內(nèi)的學(xué)習(xí)積累的潛在的背景特征內(nèi)容。

針對模板快照替換準(zhǔn)則，本文提出一個適應(yīng)性公式用于判斷，其公式如下：

目前本文算法采集快照模板策略是設(shè)定一個間隔常量φ，即每間隔φ幀就對常規(guī)模板采集一次快照并加入快照模板組，其公式如下：

其中Indexframe表示視頻幀序號。

為了保證算法的實(shí)時性，須對快照組的容量進(jìn)行限制，其對應(yīng)公式為：

其中Sizesnap為快照模板組的大小，φ是常量，為快照模板組的最大容量限制。當(dāng)有新的快照模板加入且超出快照組的容量限制時，根據(jù)LRU（Least Recently Used，最近最少使用）原則進(jìn)行剔除。

本文改進(jìn)算法ASTC對應(yīng)的流程圖如圖2所示。

3　實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)中對本文算法（ASTC），Spatio-temporal Context Tracking（STC）算法［11］和Compressive Tracking（CT）算法［6］進(jìn)行了比較。三種算法對51個常見的公開測試基準(zhǔn)視頻序列（Tracker Benchmark v1.0［1］）進(jìn)行了測試，均使用C/C++進(jìn)行實(shí)現(xiàn)，并輔以O(shè)penCV 2.4.9環(huán)境，PC為一臺普通的i5，4GB內(nèi)存的計(jì)算機(jī)。對于ASTC新提出的有關(guān)適應(yīng)性公式的參數(shù)設(shè)置，其中公式（1）適應(yīng)性閾值幅度常量ξ=10%，公式（2）中的快照模板抓取間隔閾值φ=50以及快照模板組的容量上限φ=4。而STC和CT對比算法均使用原作者開源代碼的默認(rèn)參數(shù)設(shè)置。由于代碼未做優(yōu)化，同時為了利于肉眼觀看并方便幀速計(jì)算，均對每一幀的處理都加入了一定的延時，故而幀速只可作為相對參考對比，不可作為絕對參考數(shù)值。

我們使用了三個評價標(biāo)準(zhǔn)對這三個跟蹤算法進(jìn)行定量評判：分別為成功率（SR）、中心坐標(biāo)誤差（CLE）以及幀速（FPS），其中前兩者均是與手工標(biāo)注的基準(zhǔn)數(shù)據(jù)對比得出。評價標(biāo)準(zhǔn)的詳細(xì)說明可參見Wu等人在文獻(xiàn)［1］中的定義。從表1和表2展示的51個視頻序列定量分析中可以看出，本文所提出的算法無論是從成功率上還是中心坐標(biāo)誤差方面都比STC算法更好。在反映跟蹤精確性的成功率上，本文算法27次最好、STC 有22次、CT僅10次。此外在反映綜合性能平均成績上，包括Average SR（平均成功率）和Average ACLE（平均平均中心坐標(biāo)誤差），ASTC算法均為最優(yōu)秀的結(jié)果，僅在Average FPS（平均處理幀速）上低于原STC算法，但仍然達(dá)到了36.64 FPS的平均幀速，這表明本文所提出的ASTC算法是合理有效的。三種算法對部分視頻序列的跟蹤結(jié)果如圖3所示，其對應(yīng)的中心坐標(biāo)誤差曲線如圖4所示。

圖2　基于自適應(yīng)模型的時空上下文跟蹤算法流程圖

下面將通過對ASTC、STC和CT三種算法的具體實(shí)驗(yàn)效果，從多個角度分小節(jié)進(jìn)行對比分析。

3.1快速運(yùn)動、面內(nèi)旋轉(zhuǎn)及運(yùn)動模糊

如圖3（a）所示的Boy視頻序列，在該視頻中待跟蹤目標(biāo)受到了包括快速運(yùn)動、面內(nèi)旋轉(zhuǎn)以及運(yùn)動模糊等因素的干擾，給目標(biāo)跟蹤帶來相當(dāng)大的挑戰(zhàn)。在#234幀，CT算法的估計(jì)結(jié)果已經(jīng)出現(xiàn)了嚴(yán)重的漂移，之后CT算法已經(jīng)徹底丟失了目標(biāo)，因此僅實(shí)現(xiàn)了約37%的成功率。對于STC算法而言，前期跟蹤效果較好，但在#407幀附近視頻發(fā)生了一次極快速的面外旋轉(zhuǎn)和運(yùn)動模糊，STC開始出現(xiàn)漂移且之后丟失了待跟蹤的目標(biāo)，實(shí)現(xiàn)了67%的成功率。在該視頻序列中，本文所提出的ASTC算法實(shí)現(xiàn)了最好的效果，達(dá)到了95%的成功率，且僅為3.1的平均中心坐標(biāo)誤差也同時優(yōu)于CT的 85.38和STC的42。這是由于ASTC算法及時采用歷史快照模板對常規(guī)模板進(jìn)行了修正，丟棄了積累的誤差，提高了跟蹤魯棒性。

3.2運(yùn)動模糊及背景混亂

在圖3（b）所示為Deer視頻的跟蹤結(jié)果截圖，在Deer視頻序列中，目標(biāo)受到了劇烈的運(yùn)動模糊和背景混亂干擾。待跟蹤目標(biāo)為一只小鹿的頭部，而小鹿身體的其他部分和周圍干擾鹿均有一致的紋理特征，給目標(biāo)跟蹤帶來了相當(dāng)嚴(yán)峻的考驗(yàn)，因而在該視頻上實(shí)驗(yàn)結(jié)果表明包括CT和STC在內(nèi)的兩個算法的跟蹤效果均不甚理想，分別只有8%和6%的成功率，而且平均中心坐標(biāo)誤差也分別達(dá)到了150.18和374.38。而ASTC算法在這個視頻上達(dá)到了83%的成功率和9.7的平均中心坐標(biāo)誤差。此外從對應(yīng)的中心坐標(biāo)誤差曲線圖4 （b）中可以看出ASTC雖也出現(xiàn)了一定程度的漂移，但ASTC通過歷史快照模板及時進(jìn)行了矯正并恢復(fù)了正確的跟蹤。

3.3遮擋

遮擋問題是視頻跟蹤領(lǐng)域一個常見的干擾因素，并且給跟蹤算法帶來了巨大的挑戰(zhàn)，是當(dāng)前衡量一款跟蹤算法性能和魯棒性的關(guān)鍵要素。

如圖3（c）所示的FaceOcc1視頻，在該序列中，目標(biāo)不斷受到各種不同程度的遮擋，因此如何處理遮擋過程中的跟蹤以及遮擋后的恢復(fù)是跟蹤算法亟待解決的問題。由于FaceOcc1視頻序列分辨率較低，待跟蹤目標(biāo)本身較大，且CT算法限定了結(jié)果目標(biāo)框必須在視頻內(nèi)容內(nèi)，因而即便CT結(jié)果出現(xiàn)漂移也能包含部分正確目標(biāo)區(qū)域不至于導(dǎo)致中心坐標(biāo)誤差過大，導(dǎo)致CT算法在該視頻序列上意外的實(shí)現(xiàn)了75%的成功率和31.84的中心坐標(biāo)誤差。對于STC算法而言，由于長時間的遮擋，導(dǎo)致其過多的學(xué)習(xí)了背景特征，故而成功率不高，僅為25%。從對應(yīng)的中心坐標(biāo)誤差曲線4（c）可以看出STC完全丟失了目標(biāo)。對于該視頻序列，ASTC算法實(shí)現(xiàn)了最優(yōu)秀的結(jié)果，正確率和平均中心坐標(biāo)誤差分別達(dá)到了98%和12.72。究其原因在于ASTC采用了新的自適應(yīng)結(jié)構(gòu)模型，通過對STC常規(guī)模板結(jié)果進(jìn)行適應(yīng)性檢查，當(dāng)檢測到STC常規(guī)模板適應(yīng)性弱于歷史快照模板時，通過常規(guī)模板進(jìn)行回滾，使其回滾到最契合當(dāng)前狀態(tài)的歷史上的某一時刻，有效抑制了跟蹤漂移，提升了跟蹤效果。

表1　成功率（SR）（%），其中粗體字表示最好

表2　平均中心坐標(biāo)誤差（ACLE）（單位：像素），含平均幀速（FPS）

圖3　部分視頻序列的跟蹤結(jié)果截圖

圖4　部分視頻序列的跟蹤中心坐標(biāo)誤差曲線圖

對于圖3（d）中的FaceOcc2視頻序列，從#733幀、#748幀可以明顯看出STC被遮擋物所吸引出現(xiàn)漂移直至完全丟失，而CT算法雖較好的估計(jì)到正確目標(biāo)但由于不支持尺度變化導(dǎo)致其成功率并不高，僅為56%，只有本文的ASTC算法較好的完成了跟蹤，實(shí)現(xiàn)了98%的成功率。圖3（e）中的Girl視頻序列同樣包含了遮擋以及面內(nèi)外旋轉(zhuǎn)等干擾因素。從#360幀可以看出CT和STC算法均出現(xiàn)了一定程度的漂移，至#470幀時，STC已完全跟丟，而本文的ASTC則能較好的完成了跟蹤。圖3（g）中的Suv序列，#220幀附近出現(xiàn)一次部分遮擋，CT算法已被遮擋物所吸引導(dǎo)致跟蹤丟失，#795幀再次出現(xiàn)了遮擋并且更為嚴(yán)重，STC已經(jīng)完全丟失，ASTC算法則通過適應(yīng)性檢查及時修正了常規(guī)模板中積累的誤差，實(shí)現(xiàn)了最好的跟蹤，達(dá)到了86%的成功率和5.32的平均中心坐標(biāo)誤差。

3.4光照變化及面內(nèi)外旋轉(zhuǎn)

Sylvester視頻序列包含了光照變化、面內(nèi)外旋轉(zhuǎn)以及尺度縮放等多種因素的干擾。如圖3（h）所示，在#670幀和#1190幀中可以看出CT的跟蹤已發(fā)生漂移并完全丟失目標(biāo)。而STC算法也由于不能及時修正模板積累的誤差，出現(xiàn)了明顯的漂移，僅實(shí)現(xiàn)了54%的成功率。對于本文所提出的ASTC算法由于及時丟棄了常規(guī)模板中積累的誤差，有效提升了成功率，達(dá)到了85%。從對應(yīng)的中心坐標(biāo)誤差曲線4（h）也可以看出ASTC實(shí)現(xiàn)了最好的效果。

3.5跟蹤丟失后的目標(biāo)尋回

CT算法屬于局部候選搜索算法，其搜索半徑限定在上一幀目標(biāo)中心半徑25個像素距離的范圍內(nèi)；同樣的對于STC算法也是局部搜索候選搜索算法，STC算法的搜索范圍是限定在初始目標(biāo)框兩倍大小的局部上下文區(qū)域內(nèi)。因此當(dāng)目標(biāo)重新出現(xiàn)的位置超出了局部搜索范圍是無可能重新找回目標(biāo)的，如圖3（f）的Jogging2視頻序列中看出，#53幀出現(xiàn)了嚴(yán)重的遮擋，CT、STC均被遮擋物所吸引，至#65幀目標(biāo)重新完整出現(xiàn)后已完全超出了其候選目標(biāo)中心的搜索范圍，是無可能重新找回，因而CT和STC分別僅實(shí)現(xiàn)了16%和17%的成功率。同樣對于該視頻序列，ASTC的成功率達(dá)到了99%，原因在于ASTC的歷史快照模板完整保存了各項(xiàng)參數(shù)信息，包括位置估計(jì)等，有效增大了候選搜索區(qū)域，故而實(shí)現(xiàn)了最好的實(shí)驗(yàn)效果。

4　結(jié)語

本文針對當(dāng)前STC算法中存在的易發(fā)生模型漂移問題進(jìn)行了改進(jìn)，提出一種新的自適應(yīng)結(jié)構(gòu)模型，并將之應(yīng)用到STC上得到了一種改進(jìn)的上下文目標(biāo)跟蹤算法ASTC。新模型通過保存多個歷史快照模板，且同時使用歷史快照模板組和常規(guī)模板進(jìn)行預(yù)估計(jì)，當(dāng)檢測到歷史快照模板的適應(yīng)性高于常規(guī)模板時，立即對常規(guī)模板進(jìn)行回滾，丟棄之前一段時間內(nèi)學(xué)習(xí)積累的誤差，以實(shí)現(xiàn)更加魯棒的跟蹤。實(shí)驗(yàn)結(jié)果表明，本文算法在目標(biāo)受到不同程度因素干擾和遮擋條件下，跟蹤成功率以及跟蹤穩(wěn)定性都有所提高，既保證了實(shí)時性，又提高了精確率，增強(qiáng)了算法的魯棒性。

［1］Wu Y，Lim J，Yang M H.Online Object Tracking∶A Benchmark［C］.Computer Vision and Pattern Recognition（CVPR），2013 IEEE Conference on.IEEE，2013∶2411-2418.

［2］D.Comaniciu，V.Ramesh，P.Meer.Kernel-Based Object Tracking.IEEE Transactions on Pattern Analysis and Machine Intelligence，2003，25（5）∶564-577.

［3］C.Shen，J.Kim，H.Wang.Generalized Kernel-Based Visual Tracking.IEEE Transactions on Circuits and Systems for Video Technology，2010，20（1）：119-130.

［4］S.Avidan.Support Vector Tracking.IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26（8）：1064-1072.

［5］R.Collins，Y.Liu，M.Leordeanu.Online Selection of Discriminative Tracking Features.IEEE Transactions on Pattern Analysis andMachine Intelligence，2005，27（10）：1631-1643.

［6］K.Zhang，L.Zhang，M.-H.Yang.Real-Time Compressive Tracking.in Proceedings of European Conference on Computer Vision，2012：864-877.

［7］Zhang K，Zhang L，Yang M H.Fast Compressive Tracking［J］.IEEE Transactions on Pattern Analysis&Machine Intelligence，2014，36 （10）∶2002-2015.

［8］朱秋平，顏佳，張虎，等.基于壓縮感知的多特征實(shí)時跟蹤［J］.光學(xué)精密工程，2013，02（2）∶437-444.

［9］Kaihua Z，Lei Z，Ming-Hsuan Y.Real-Time Object Tracking Via Online Discriminative Feature Selection［J］.IEEE Transactions on Image Processing，2013，22（12）∶4664-4677.

［10］Zhang K，Zhang L，Yang M H，et al.Robust Object Tracking Via Active Feature Selection［J］.IEEE Transactions on Circuits&Systems for Video Technology，2013，23（11）∶1957-1967.

［11］Zhang K，Zhang L，Liu Q，et al.Fast Visual Tracking Via Dense Spatio-Temporal Context Learning［M］.Computer Vision-ECCV 2014.Springer International Publishing，2014∶127-141.

［12］Hong S，Han B.Visual tracking by Sampling Tree-Structured Graphical Models［M］.Computer Vision-ECCV 2014.Springer International Publishing，2014∶1-16.

［13］胡士強(qiáng)，敬忠良.粒子濾波算法綜述［J］，2005.

［14］宋策.基于粒子濾波的目標(biāo)跟蹤技術(shù)研究［D］.中國科學(xué)院研究生院 （長春光學(xué)精密機(jī)械與物理研究所），2014.

［15］章學(xué)靜，陳禾，楊靜.結(jié)合卡爾曼濾波和 Mean Shift的抗遮擋跟蹤算法［J］.北京理工大學(xué)學(xué)報(bào)，2013，33（10）.

［16］郭崇霄.目標(biāo)縮放和遮擋情形下在線視頻目標(biāo)跟蹤算法研究［D］.重慶大學(xué)，2014.

Object Tracking；Real-Time Tracking；Spatio-Temporal Context；Adaptive Structure Model；Snapshot Template

Visual Tracking Using Adaptive Structure Model Based on Spatio-Temporal Context

ZHU Zheng-yu1，2，LI Shuai1，ZHU Wei1
（1.College of Computer Science，Chongqing University，Chongqing 400030；2.Chongqing Key Laboratory of Software Theory and Technology，Chongqing 400030）

Object tracking is one of the basic problems in the field of computer vision.There are many algorithms presented，and STC is a quite novel one.But the STC tracking method can't deal with model drift problem.To overcome this weakness，proposes an algorithm using adaptive structure model based on STC.This algorithm takes a set number of snapshots of normal template as snapshot templates，and saves them to snapshot set.When one of the snapshot templates gets an enough better outcome than normal template，the algorithm uses the snapshot template to roll back the normal template，which can effectively enhance the tracking robustness and keep accurate even when object suffers all kinds of interferences such as fast motion，in-plane rotation，motion blur，severe occlusion and so on.The experiment on Tracker Benchmark v1.0 dataset compared to STC shows that the average accuracy is improved from 38.61%to 42.02%，the average center location error is decreased from 85.57 to 62.78 and the average frame rate decreased from 45.89 fps to 36.64 fps.It still meets the requirements of real-time tracking.In conclusion，this algorithm can accomplish the real-time tracking steadily even when disturbed by all kinds of interferences.

1007-1423（2016）20-0003-07

10.3969/j.issn.1007-1423.2016.20.001

朱征宇（1959-），男，重慶人，博士，教授，研究方向?yàn)橛?jì)算機(jī)視覺

李帥（1991-），男，山西長治人，碩士研究生，研究方向?yàn)橛?jì)算機(jī)視覺

朱威（1992-），男，湖南常德人，碩士研究生，研究方向?yàn)橛?jì)算機(jī)視覺

2016-04-19

2016-06-29