視頻目標跟蹤算法綜述*

蔡榮太 ，吳元昊，王明佳，吳慶祥

（1.福建師范大學 物理與光電信息科技學院，福建 福州 350108；2.中國科學院 長春光學精密機械與物理研究所，吉林 長春 130033）

1 引言

目標跟蹤可分為主動跟蹤和被動跟蹤。視頻目標跟蹤屬于被動跟蹤。與無線電跟蹤測量相比，視頻目標跟蹤測量具有精度高、隱蔽性好和直觀性強的優點。這些優點使得視頻目標跟蹤測量在靶場光電測量、天文觀測設備、武器控制系統、激光通信系統、交通監控、場景分析、人群分析、行人計數、步態識別、動作識別等領域得到了廣泛的應用[1-2]。

根據被跟蹤目標信息使用情況的不同，可將視覺跟蹤算法分為基于對比度分析的目標跟蹤、基于匹配的目標跟蹤和基于運動檢測的目標跟蹤。基于對比度分析的跟蹤算法主要利用目標和背景的對比度差異，實現目標的檢測和跟蹤。基于匹配的跟蹤主要通過前后幀之間的特征匹配實現目標的定位。基于運動檢測的跟蹤主要根據目標運動和背景運動之間的差異實現目標的檢測和跟蹤。前兩類方法都是對單幀圖像進行處理，基于匹配的跟蹤方法需要在幀與幀之間傳遞目標信息，對比度跟蹤不需要在幀與幀之間傳遞目標信息。基于運動檢測的跟蹤需要對多幀圖像進行處理。除此之外，還有一些算法不易歸類到以上3類，如工程中的彈轉機跟蹤算法、多目標跟蹤算法或其他一些綜合算法。

2 基于對比度分析的目標跟蹤算法

基于對比度分析的目標跟蹤算法利用目標與背景在對比度上的差異來提取、識別和跟蹤目標。這類算法按照跟蹤參考點的不同可以分為邊緣跟蹤、形心跟蹤和質心跟蹤等。這類算法不適合復雜背景中的目標跟蹤，但在空中背景下的目標跟蹤中非常有效。邊緣跟蹤的優點是脫靶量計算簡單、響應快，在某些場合（如要求跟蹤目標的左上角或右下角等）有其獨到之處。缺點是跟蹤點易受干擾，跟蹤隨機誤差大。重心跟蹤算法計算簡便，精度較高，但容易受到目標的劇烈運動或目標被遮擋的影響。重心的計算不需要清楚的輪廓，在均勻背景下可以對整個跟蹤窗口進行計算，不影響測量精度。重心跟蹤特別適合背景均勻、對比度小的弱小目標跟蹤等一些特殊場合。圖像二值化之后，按重心公式計算出的是目標圖像的形心。一般來說形心與重心略有差別[1-2]。

3 基于匹配的目標跟蹤算法

3.1 特征匹配

特征是目標可區別與其他事物的屬性，具有可區分性、可靠性、獨立性和稀疏性。基于匹配的目標跟蹤算法需要提取目標的特征，并在每一幀中尋找該特征。尋找的過程就是特征匹配過程。

特征提取是一種變換或者編碼，將數據從高維的原始特征空間通過映射，變換到低維空間的表示。根據Marr的特征分析理論，有4種典型的特征計算理論：神經還原論、結構分解理論、特征空間論和特征空間的近似。神經還原論直接源于神經學和解剖學的特征計算理論，它與生物視覺的特征提取過程最接近，其主要技術是Gabor濾波器、小波濾波器等。結構分解理論是到目前為止唯一能夠為新樣本進行增量學習提供原則的計算理論，目前從事該理論研究的有麻省理工學院實驗組的視覺機器項目組等。特征空間論主要采用主分量分析（PCA）、獨立分量分析（ICA）、稀疏分量分析（SCA）和非負矩陣分解（NMF）等技術抽取目標的子空間特征。特征空間的近似屬于非線性方法，適合于解決高維空間上復雜的分類問題，主要采用流形、李代數、微分幾何等技術[1]。

目標跟蹤中用到的特征主要有幾何形狀、子空間特征、外形輪廓和特征點等。其中，特征點是匹配算法中常用的特征。特征點的提取算法很多，如Kanade Lucas Tomasi（KLT）算法、Harris算法、SIFT 算法以及 SURF 算法等。特征點一般是稀疏的，攜帶的信息較少，可以通過集成前幾幀的信息進行補償。目標在運動過程中，其特征（如姿態、幾何形狀、灰度或顏色分布等）也隨之變化。目標特征的變化具有隨機性，這種隨機變化可以采用統計數學的方法來描述。直方圖是圖像處理中天然的統計量，因此彩色和邊緣方向直方圖在跟蹤算法中被廣泛采用。

3.2 貝葉斯跟蹤

目標的運動往往是隨機的，這樣的運動過程可以采用隨機過程來描述。很多跟蹤算法往往建立在隨機過程的基礎之上，如隨機游走過程、馬爾科夫過程、自回歸（AR）過程等。文獻[3]和文獻[4]采用二階AR模型來跟蹤目標的運動，采用一階AR模型來跟蹤目標的尺度變化。隨機過程的處理在信號分析領域較成熟，其理論和技術（如貝葉斯濾波）可以借鑒到目標跟蹤中。

貝葉斯濾波中，最有名的是Kalman濾波（KF）。KF可以比較準確地預測平穩運動目標在下一時刻的位置，在彈道目標跟蹤中具有非常成功的應用。一般而言，KF可以用作跟蹤方法的框架，用于估計目標的位置，減少特征匹配中的區域搜索范圍，提高跟蹤算法的運行速度。KF只能處理線性高斯模型，KF算法的兩種變形EKF和UKF可以處理非線性高斯模型。兩種變形擴展了KF的應用范圍，但是不能處理非高斯非線性模型，這個時候就需要用粒子濾波（PF）。由于運動變化，目標的形變、非剛體、縮放等問題，定義一個可靠的分布函數是非常困難的，所以在PF中存在例子退化問題，于是引進了重采樣技術。事實上，貝葉斯框架下視覺跟蹤的很多工作都是在PF框架下尋找更為有效的采樣方法和建議概率分布。這些工作得到了許多不同的算法，如馬爾可夫鏈蒙特卡洛 （MCMC）方法、Unscented粒子濾波器（UPF）、Rao-Blackwellised粒子濾波器（RBPF）等。文獻[5]引入了一種新的自適應采樣方法——序貫粒子生成方法，在該方法中粒子通過重要性建議概率密度分布的動態調整順序產生。文獻[6]根據率失真理論推導了確定粒子分配最優數目的方法，該方法可以最小化視覺跟蹤中粒子濾波的整體失真。文獻[7]計算最優重要性采樣密度分布和一些重要密度分布之間的KL距離，分析了這些重要密度分布的性能。文獻[8]在粒子濾波框架下，采用概率分類器對目標觀測量進行分類，確定觀測量的可靠性，通過加強相關觀測量和抑制不相關觀測量的方法提高跟蹤性能。

除了KF和PF之外，隱馬爾科夫模型（HMMs）和動態貝葉斯模型（DBNs）[9]也是貝葉斯框架下重要的視覺跟蹤方法。HMMs和DBNs將運動目標的內部狀態和觀測量用狀態變量（向量）表示，DBNs使用狀態隨機變量（向量）集，并在它們之間建立概率關聯。HMMs將系統建模為馬爾科夫過程。這些算法的主要區別如表1所示。

表1 貝葉斯跟蹤方法

表1中每個簡單的算法都可以看成是下一行復雜算法的特例。反之，每個復雜算法都可以看成是簡單算法的擴展。其中，DBNs具有最佳的靈活性，可以處理不同的運動模型和不同的狀態變量組合。

DBNs又可以看作概率圖模型（PGMs）[9]的一個例子。PGMs的基本思想是用圖形的方式將多變量概率分布分解，統計變量用圖的節點表示，變量間的條件關系用圖的連接或邊表示。PGMs可以分為有向圖（DAGs）和無向圖（Ugs）。前者能夠處理時間模式，適合目標跟蹤和場景理解等任務。后者能很好地描述圖像像素之間的空間依賴性，適合圖像分割和圖像分析等任務。

通過組合圖理論和概率理論，PGMs可以用來處理問題描述中的不確定性。不確定性恰好符合人類視覺系統中天然的概率性和視覺模糊性（如遮擋、從3D到2D投影的信息損失）。通過規定概率模型元素之間的關系，PGMs可以有效地表示、學習和計算復雜的概率模型。PGMs能夠有效地組合目標的動態信息和外觀信息，有效解決目標的運動估計問題，為目標跟蹤提供了很好的理論框架。表1中算法都可以看成是PGMs的特殊形式。

3.3 核方法

核方法的基本思想是對相似度概率密度函數或者后驗概率密度函數采用直接的連續估計。這樣處理一方面可以簡化采樣，另一方面可以采用估計的函數梯度有效定位采樣粒子。采用連續概率密度函數可以減少高維狀態空間引起的計算量問題，還可以保證例子接近分布模式，避免粒子退化問題。核方法一般都采用彩色直方圖作為匹配特征。

Mean Shift[10]是核方法中最有代表性的算法，其含義正如其名，是“偏移的均值向量”。直觀上看，如果樣本點從一個概率密度函數中采樣得到，由于非零的概率密度梯度指向概率密度增加最大的方向，從平均上來說，采樣區域內的樣本點更多的落在沿著概率密度梯度增加的方向。因此，對應的Mean Shift向量應該指向概率密度梯度的負方向。

Mean Shift跟蹤算法反復不斷地把數據點朝向Mean Shift矢量方向進行移動，最終收斂到某個概率密度函數的極值點。在Mean Shift跟蹤算法中，相似度函數用于刻畫目標模板和候選區域所對應的兩個核函數直方圖的相似性，采用的是Bhattacharyya系數。因此，這種方法將跟蹤問題轉化為Mean Shift模式匹配問題。核函數是Mean Shift算法的核心，可以通過尺度空間差的局部最大化來選擇核尺度，若采用高斯差分計算尺度空間差，則得到高斯差分Mean Shift算法。

Mean Shift算法假設特征直方圖足夠確定目標的位置，并且足夠穩健，對其他運動不敏感。該方法可以避免目標形狀、外觀或運動的復雜建模，建立相似度的統計測量和連續優化之間的聯系。但是，Mean Shift算法不能用于旋轉和尺度運動的估計。為克服以上問題，人們提出了許多改進算法，如多核跟蹤算法、多核協作跟蹤算法和有效的最優核平移算法等。文獻[11]則針對可以獲得目標多視角信息的情況，提出了一種從目標不同視角獲得多個參考直方圖，增強Mean Shift跟蹤性能的算法。

4 基于運動檢測的目標跟蹤算法

基于運動檢測的目標跟蹤算法通過檢測序列圖像中目標和背景的不同運動來發現目標存在的區域，實現跟蹤。這類算法不需要幀間的模式匹配，不需要在幀間傳遞目標的運動參數，只需要突出目標和非目標在時域或者空域的區別即可。這類算法具有檢測多個目標的能力，可用于多目標檢測和跟蹤。這類運動目標檢測方法主要有幀間圖像差分法、背景估計法、能量積累法、運動場估計法等。

光流算法是基于運動檢測的目標跟蹤的代表性算法。光流是空間運動物體在成像面上的像素運動的瞬時速度，光流矢量是圖像平面坐標點上的灰度瞬時變化率。光流的計算利用圖像序列中的像素灰度分布的時域變化和相關性來確定各自像素位置的運動，研究圖像灰度在時間上的變化與景象中物體結構及其運動的關系。將二維速度場與灰度相聯系，引入光流約束方程，得到光流計算的基本算法。根據計算方法的不同，可以將光流算法分為基于梯度的方法、基于匹配的方法、基于能量的方法、基于相位的方法和基于神經動力學的方法。

文獻[12]提出了一種基于攝像機光流反向相關的無標記跟蹤算法，該算法利用反向攝像機消除光流中的相同成分，得到有效的跟蹤效果。文獻[13]將光流算法的亮度約束轉化為上下文約束，把上下文信息集成到目標跟蹤的運動估計里，仿照光流算法，提出了上下文流算法。文獻[14]引入了幾何流的概念，用于同時描述目標在空間上和時間上的運動，并基于李代數推導了它的矢量空間表示。幾何流在幾何約束條件下，將復雜運動建模為多個流的組合，形成一個隨機流模型。該算法在運動估計中集成了點對和幀差信息。文獻[15]介紹了使用互相關的對光照穩健的可變光流算法。文獻[16]提出了基于三角化高階相似度函數的光流算法——三角流算法。該算法采用高階條件隨機場進行光流建模，使之包含標準的光流約束條件和仿射運動先驗信息，對運動估計參數和匹配準則進行聯合推理。局部仿射形變的相似度能量函數可以直接計算，形成高階相似度函數，用三角形網格求解，形成三角流算法。

5 其他跟蹤問題

視覺跟蹤從不同的角度和應用場合出發，會遇到很多不同的問題，比如多模跟蹤、多特征跟蹤、多目標跟蹤、多攝像機跟蹤[17]、3D跟蹤[18]和特定應用的跟蹤等。

5.1 多特征跟蹤和利用上下文信息的目標跟蹤

利用多特征刻畫目標是一種非常有效的實現穩健跟蹤的方法。不同的特征可以從相同的或者不同的傳感器獲得，如彩色和輪廓[19]，彩色和梯度[20]，Haar-Like特征和邊緣[21]，角點、彩色和輪廓[22]，彩色和邊緣[6]，彩色和 Wi-Fi三角化[23]等。

在貝葉斯框架下，有三種方法可以集成多個特征：1）假設特征之間是統計獨立的，可以將多個特征以加權和的形式組合起來；2）假設多個特征之間的條件關聯服從線性約束，可以將相似度概率密度分布表示為各個特征相似度概率密度分布的線性組合；3）文獻[19]給出了一種更加復雜的方法，該方法不對各個特征施加關聯約束，用概率方法建立各個特征之間的關聯。

除了聯合使用目標的多特征之外，還可以充分采用上下文、背景和輔助目標等信息來實現穩健的目標跟蹤。如文獻[24]設計了一種考慮上下文的跟蹤算法。該算法采用數據挖掘技術在視頻中獲取輔助目標，并將輔助目標用在跟蹤中。對目標和這些輔助目標的協作跟蹤可以獲得有效的跟蹤性能。這里的輔助目標是至少在一小段時間內和目標同時出現，和目標具有相同的相關性運動并且比目標更容易跟蹤的視頻內容。文獻[25]在跟蹤算法中，同時采用目標和目標周圍背景的特征點，將目標特征點用于跟蹤，將背景特征點用于鑒別目標是否被遮擋。

5.2 多目標跟蹤

多目標跟蹤（MTVT）在每幀圖像中同時正確地對各個目標進行編號，主要算法有概率數據關聯（PDAF）、聯合概率數據關聯（JPDAF）。

文獻[26]給出了兩種新的數據關聯方法：聯合相似度濾波（JLF）和約束的聯合相似度濾波（CJLF）。前者是JPDAF算法的擴展，它增加了目標相對于攝像機的深度標志，能夠預測目標之間的遮擋，可以采用不同的特征計算相似度。后者集成了目標的剛性關聯和深度約束，能夠更好地處理大目標之間的交叉。

隨機集濾波和有限集統計算法是另外一類多目標跟蹤方法。有限集統計算法中采用概率假設密度函數，可以解決目標狀態變量和觀測向量維度變化的問題，可以比較有效地解決目標數量的增減問題[3，27，28]。

6 小結

筆者系統地介紹了基于對比度分析的目標跟蹤算法、基于匹配的目標跟蹤算法和基于運動檢測的目標跟蹤算法，重點介紹了特征匹配、貝葉斯與概率圖模型下的視覺跟蹤算法和核跟蹤算法的主要技術內容及其最新進展，對多特征跟蹤、上下文跟蹤和多目標跟蹤的進展也作了簡單介紹。由于目標跟蹤任務的復雜性，應該根據不同的應用場合選用不同的跟蹤方法。在系統設計中，應該根據具體的精度要求、穩健性要求、計算復雜度要求和實時性要求等采用不同的算法。多種技術的聯合應用可以有效克服單一技術的局限性。因此，目標跟蹤算法的方向發展為多模跟蹤、多特征融合跟蹤、基于目標所在的上下文和運動軌跡等信息的跟蹤。

[1]蔡榮太.非線性自適應濾波器在電視跟蹤中的應用[D].北京：中國科學院，2008.

[2]蔡榮太，雷凱，張旭光，等.基于.net的視頻跟蹤仿真平臺設計[J].計算機仿真，2007，24（12）：181-184.

[3]MAGGIO E，TAJ M，CAVALLARO A.Efficient multi-target visual tracking using random finite sets[J].IEEE Transactions on Circuits and Systems for Video Technology，2008，18（8）：1016-1027.

[4]XU X，LIB.Adaptive raoblackwellized particle filter and its evaluation for tracking in surveillance[J].IEEE Transactions on Image Processing，2007，16（3）：838-849.

[5]LAO Y，ZHU J，ZHENG Y.Sequential particle generation for visual tracking[J].IEEE Transactions on Circuits and Systems for Video Technology，2009，19（9）：1365-1378.

[6]PAN P，SCHONFILD D.Dynamic proposal variance and optimal particle allocation in particle filtering for video tracking[J].IEEE Transaction on Circuits and Systems for Video Technology，2008，18（9）：1268-1279.

[7]BOUAYNAYA N，SCHONFELD D.On the optimality of motionbased particle filtering [J].IEEE Transactions on Circuits and Systems for Video Technology，2009，19（7）：1068-1072.

[8]IOANNIS P，EDWIN H R.Coupled prediction classification for robust visual tracking[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32（9）：1553-1567.

[9]SOTO D A，REGAZZONI M C S.Bayesian tracking for video analytics[J].IEEE Signal Processing Magazine，2010，27（5）：46-55.

[10]王宇.基于Mean Shift的序列圖像手勢跟蹤算法[J].電視技術，2010，34（6）：99-101.

[11]LEICHTER I，LINDENBAUM M，RIVLIN E.Mean Shift tracking with multiple reference color histograms[J].Computer Vision and Image Understanding，2010，114（3）：400-408.

[12]GUPTA P，VITORIA L N，LAVIOLA J J.Markerless tracking using polar correlation of camera optical flow[C]//Proc.2010 IEEE Virtual Reality Conference.Waltham，MA，UK：IEEE Press，2010：223-226.

[13]WU Ying，FAN Jialue.Contextual flow[C]//Proc.2009 IEEE International Conference on Computer Vision，Miami，FL，USA：IEEE Press，2009：33-40.

[14]LIN D，GRIMSON E，FISHER J.Modeling and estimating persistent motion with geometric flows[C]//Proc.2010 IEEE International Conference on Computer Vision.San Francisco，CA，USA：IEEE Press，2010：1-8.

[15]MOLNAR J，CHETVERIKOV D，FAZEKAS S.Illumination-robust variational optical flow using cross-correlation[J].Computer Vision and Image Understanding，2010，114（10）：1104-1114.

[16]GLOCKER B，HEIBEL T H，NAVAB N，et al.Triangle flow：optical flow with triangulation-based higher-order likelihoods[C]//Proc.Lecture Notes in Computer Science （ECCV 2010）.Heraklion，Crete，Greece：[s.n.]，2010：272-285.

[17]ESHEL R，MOSES Y.Tracking in a dense crowd using multiple cameras[J].International Journal of Computer Vision，2010，88（1）：129-143.

[18]LIR，TIAN T，SCLAROFF S，et al.3D human motion tracking with a coordinated mixture of factor analyzers[J].International Journal of Computer Vision，2010，87（1-2）：170-190.

[19]NOGUER M F，SANFELIU A，SAMARAS D.Dependent multiple cue integration for robust tracking [J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2008，30（4）：670-685.

[20]CHANG C，ANSARI R，KHOKHAR A.Multiple object tracking with kernel particle filter[C]//Proc.IEEE Conference on Computer Vision and Pattern Recognition.San Diego，CA，USA：IEEE Press，2005：566-573.

[21]YANG C，DURAISWAMIR，DAVIS L.Fastmultiple object tracking via a hierarchical particle filter[C]//Proc.IEEE International Conference on Computer Vision.Beijing，China：IEEE Press，2005：212-219.

[22]MAKRISA，KOSMOPOULOSD，PERANTONISS，et al.Hierarchical feature fusion for visual tracking[C]//Proc.IEEE International Conference on Image Processing，San Antonio，Texas，USA：IEEE Press，2007：289-292.

[23]MIYAKI T，YAMASAKI T，AIZAWA K.Tracking persons using particle filter fusing visual and Wi-Fi localizations for widely distributed camera[C]//Proc.IEEE International Conference on Image Processing，San Antonio，Texas，USA：IEEE Press，2007：225-228.

[24]YANG M，HUA G，WU Y.Context-aware visual tracking[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2009，31（7）：1195-1209.

[25]KHAN Z H，GU I Y H.Joint feature correspondences and appearance similarity for robust visual object tracking[J].IEEE Transactions on Information Forensics and Security，2010，5（3）：591-606.

[26]RASMUSSEN C，HAGER G D.Probabilistic data association methods for tracking complex visual objects[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2001，23（6）：560-576.

[27]MAHLER R.Multi target Bayesian filter in via first-order multi target moments[J].IEEE Transactions on Aerospace and Electronic Systems，2003，39（4）：1152-1178.

[28]HUE C，CHDRE JP L，PEREZ P.Sequential Monte Carlo methods for multiple target tracking and data fusion[J].IEEE Transactions on Signal Processing，2002，50（2）：309-325.