1、 1引言目標跟蹤可分為主動跟蹤和被動跟蹤。視頻目標跟蹤屬于被動跟蹤。與無線電跟蹤測量相比,視頻目標跟蹤測量具有精度高、隱蔽性好和直觀性強的優(yōu)點。這些優(yōu)點使得視頻目標跟蹤測量在靶場光電測量、天文觀測設備、武器控制系統(tǒng)、激光通信系統(tǒng)、交通監(jiān)控、場景分析、人群分析、行人計數(shù)、步態(tài)識別、動作識別等領域得到了廣泛的應用1-2。根據(jù)被跟蹤目標信息使用情況的不同,可將視覺跟蹤算法分為基于對比度分析的目標跟蹤、基于匹配的目標跟蹤和基于運動檢測的目標跟蹤。基于對比度分析的跟蹤算法主要利用目標和背景的對比度差異,實現(xiàn)目標的檢測和跟蹤。基于匹配的跟蹤主要通過前后幀之間的特征匹配實現(xiàn)目標的定位。基于運動檢測的跟蹤主要

2、根據(jù)目標運動和背景運動之間的差異實現(xiàn)目標的檢測和跟蹤。前兩類方法都是對單幀圖像進行處理,基于匹配的跟蹤方法需要在幀與幀之間傳遞目標信息,對比度跟蹤不需要在幀與幀之間傳遞目標信息。基于運動檢測的跟蹤需要對多幀圖像進行處理。除此之外,還有一些算法不易歸類到以上3類,如工程中的彈轉機跟蹤算法、多目標跟蹤算法或其他一些綜合算法。2基于對比度分析的目標跟蹤算法基于對比度分析的目標跟蹤算法利用目標與背景在對比度上的差異來提取、識別和跟蹤目標。這類算法按照跟蹤參考點的不同可以分為邊緣跟蹤、形心跟蹤和質(zhì)心跟蹤等。這類算法不適合復雜背景中的目標跟蹤,但在空中背景下的目標跟蹤中非常有效。邊緣跟蹤的優(yōu)點是脫靶量計算

3、簡單、響應快,在某些場合(如要求跟蹤目標的左上角或右下角等有其獨到之處。缺點是跟蹤點易受干擾,跟蹤隨機誤差大。重心跟蹤算法計算簡便,精度較高,但容易受到目標的劇烈運動或目標被遮擋的影響。重心的計算不需要清楚的輪廓,在均勻背景下可以對整個跟蹤窗口進行計算,不影響測量精度。重心跟蹤特別適合背景均勻、對比度小的弱小目標跟蹤等一些特殊場合。圖像二值化之后,按重心公式計算出的是目標圖像的形心。一般來說形心與重心略有差別1-2。3基于匹配的目標跟蹤算法3.1特征匹配特征是目標可區(qū)別與其他事物的屬性,具有可區(qū)分性、可靠性、獨立性和稀疏性。基于匹配的目標跟蹤算法需要提取目標的特征,并在每一幀中尋找該特征。尋找

4、的文章編號:1002-8692(201012-0135-04視頻目標跟蹤算法綜述*蔡榮太1,吳元昊2,王明佳2,吳慶祥1(1.福建師范大學物理與光電信息科技學院,福建福州350108;2.中國科學院長春光學精密機械與物理研究所,吉林長春130033【摘要】介紹了視頻目標跟蹤算法及其研究進展,包括基于對比度分析的目標跟蹤算法、基于匹配的目標跟蹤算法和基于運動檢測的目標跟蹤算法。重點分析了目標跟蹤中特征匹配、貝葉斯濾波、概率圖模型和核方法的主要內(nèi)容及最新進展。此外,還介紹了多特征跟蹤、利用上下文信息的目標跟蹤和多目標跟蹤算法及其進展。【關鍵詞】目標跟蹤;特征匹配;貝葉斯濾波;概率圖模型;均值漂移;

5、粒子濾波【中圖分類號】TP391.41;TN911.73【文獻標識碼】ASurvey of Visual Object Tracking AlgorithmsCAI Rong-tai1,WU Yuan-hao2,WANG Ming-jia2,WU Qing-xiang1(1.School of Physics,Optics,Electronic Science and Technology,Fujian Normal University,Fuzhou350108,China;2.Changchun Institute of Optics,Fine Mechanics and Physics,

6、Chinese Academy of Science,Changchun130033,China【Abstract】The field of visual object tracking algorithms are introduced,including visual tracking based on contrast analysis,visual tracking based on feature matching and visual tracking based on moving detection.Feature matching,Bayesian filtering,pro

7、babilistic graphical models,kernel tracking and their recent developments are analyzed.The development of multiple cues based tracking,contexts based tracking and multi-target tracking are also discussed.【Key words】visual tracking;feature matching;Bayesian filtering;probabilistic graphical models;me

8、an shift;particle filter論文*國家“863”計劃項目(2006AA703405F;福建省自然科學基金項目(2009J05141;福建省教育廳科技計劃項目(JA09040 算法描述能力狀態(tài)表示方法拓撲結構KF 線性、高斯一個隨機變量(向量固定PF 非線性、任意分布一個隨機變量(向量固定HMMs 非線性、任意分布一個隨機變量(向量固定DBNs非線性、任意分布隨機變量(向量集可變表1貝葉斯跟蹤方法過程就是特征匹配過程。特征提取是一種變換或者編碼,將數(shù)據(jù)從高維的原始特征空間通過映射,變換到低維空間的表示。根據(jù)Marr 的特征分析理論,有4種典型的特征計算理論:神經(jīng)還原論、結構分

9、解理論、特征空間論和特征空間的近似。神經(jīng)還原論直接源于神經(jīng)學和解剖學的特征計算理論,它與生物視覺的特征提取過程最接近,其主要技術是Gabor 濾波器、小波濾波器等。結構分解理論是到目前為止唯一能夠為新樣本進行增量學習提供原則的計算理論,目前從事該理論研究的有麻省理工學院實驗組的視覺機器項目組等。特征空間論主要采用主分量分析(PCA 、獨立分量分析(ICA 、稀疏分量分析(SCA 和非負矩陣分解(NMF 等技術抽取目標的子空間特征。特征空間的近似屬于非線性方法,適合于解決高維空間上復雜的分類問題,主要采用流形、李代數(shù)、微分幾何等技術1。目標跟蹤中用到的特征主要有幾何形狀、子空間特征、外形輪廓和特

10、征點等。其中,特征點是匹配算法中常用的特征。特征點的提取算法很多,如Kanade LucasTomasi (KLT 算法、Harris 算法、SIFT 算法以及SURF 算法等。特征點一般是稀疏的,攜帶的信息較少,可以通過集成前幾幀的信息進行補償。目標在運動過程中,其特征(如姿態(tài)、幾何形狀、灰度或顏色分布等也隨之變化。目標特征的變化具有隨機性,這種隨機變化可以采用統(tǒng)計數(shù)學的方法來描述。直方圖是圖像處理中天然的統(tǒng)計量,因此彩色和邊緣方向直方圖在跟蹤算法中被廣泛采用。3.2貝葉斯跟蹤目標的運動往往是隨機的,這樣的運動過程可以采用隨機過程來描述。很多跟蹤算法往往建立在隨機過程的基礎之上,如隨機游走過

11、程、馬爾科夫過程、自回歸(AR 過程等。文獻3和文獻4采用二階AR 模型來跟蹤目標的運動,采用一階AR 模型來跟蹤目標的尺度變化。隨機過程的處理在信號分析領域較成熟,其理論和技術(如貝葉斯濾波可以借鑒到目標跟蹤中。貝葉斯濾波中,最有名的是Kalman 濾波(KF 。KF 可以比較準確地預測平穩(wěn)運動目標在下一時刻的位置,在彈道目標跟蹤中具有非常成功的應用。一般而言,KF 可以用作跟蹤方法的框架,用于估計目標的位置,減少特征匹配中的區(qū)域搜索范圍,提高跟蹤算法的運行速度。KF 只能處理線性高斯模型,KF 算法的兩種變形EKF 和UKF 可以處理非線性高斯模型。兩種變形擴展了KF 的應用范圍,但是不能

12、處理非高斯非線性模型,這個時候就需要用粒子濾波(PF 。由于運動變化,目標的形變、非剛體、縮放等問題,定義一個可靠的分布函數(shù)是非常困難的,所以在PF 中存在例子退化問題,于是引進了重采樣技術。事實上,貝葉斯框架下視覺跟蹤的很多工作都是在PF 框架下尋找更為有效的采樣方法和建議概率分布。這些工作得到了許多不同的算法,如馬爾可夫鏈蒙特卡洛(MCMC 方法、Unscented 粒子濾波器(UPF 、Rao-Blackwellised 粒子濾波器(RBPF 等。文獻5引入了一種新的自適應采樣方法序貫粒子生成方法,在該方法中粒子通過重要性建議概率密度分布的動態(tài)調(diào)整順序產(chǎn)生。文獻6根據(jù)率失真理論推導了確定

13、粒子分配最優(yōu)數(shù)目的方法,該方法可以最小化視覺跟蹤中粒子濾波的整體失真。文獻7計算最優(yōu)重要性采樣密度分布和一些重要密度分布之間的KL 距離,分析了這些重要密度分布的性能。文獻8在粒子濾波框架下,采用概率分類器對目標觀測量進行分類,確定觀測量的可靠性,通過加強相關觀測量和抑制不相關觀測量的方法提高跟蹤性能。除了KF 和PF 之外,隱馬爾科夫模型(HMMs 和動態(tài)貝葉斯模型(DBNs 9也是貝葉斯框架下重要的視覺跟蹤方法。HMMs 和DBNs 將運動目標的內(nèi)部狀態(tài)和觀測量用狀態(tài)變量(向量表示,DBNs 使用狀態(tài)隨機變量(向量集,并在它們之間建立概率關聯(lián)。HMMs 將系統(tǒng)建模為馬爾科夫過程。這些算法的

14、主要區(qū)別如表1所示。表1中每個簡單的算法都可以看成是下一行復雜算法的特例。反之,每個復雜算法都可以看成是簡單算法的擴展。其中,DBNs 具有最佳的靈活性,可以處理不同的運動模型和不同的狀態(tài)變量組合。DBNs 又可以看作概率圖模型(PGMs 9的一個例子。PGMs 的基本思想是用圖形的方式將多變量概率分布分解,統(tǒng)計變量用圖的節(jié)點表示,變量間的條件關系用圖的連接或邊表示。PGMs 可以分為有向圖(DAGs 和無向圖(Ugs 。前者能夠處理時間模式,適合目標跟蹤和場景理解等任務。后者能很好地描述圖像像素之間的空間依賴性,適合圖像分割和圖像分析等任務。通過組合圖理論和概率理論,PGMs 可以用來處理問

15、題描述中的不確定性。不確定性恰好符合人類視覺系統(tǒng)中天然的概率性和視覺模糊性(如遮擋、從3D 到2D 投影的信息損失。通過規(guī)定概率模型元素之間的關系,PGMs 可以有效地表示、學習和計算復雜的概率模型。PGMs能夠有效地組合目標的動態(tài)信息和外觀信息,有效解決目標的運動估計問題,為目標跟蹤提供了很好的理論框架。表1中算法都可以看成是PGMs的特殊形式。3.3核方法核方法的基本思想是對相似度概率密度函數(shù)或者后驗概率密度函數(shù)采用直接的連續(xù)估計。這樣處理一方面可以簡化采樣,另一方面可以采用估計的函數(shù)梯度有效定位采樣粒子。采用連續(xù)概率密度函數(shù)可以減少高維狀態(tài)空間引起的計算量問題,還可以保證例子接近分布模式

16、,避免粒子退化問題。核方法一般都采用彩色直方圖作為匹配特征。Mean Shift10是核方法中最有代表性的算法,其含義正如其名,是“偏移的均值向量”。直觀上看,如果樣本點從一個概率密度函數(shù)中采樣得到,由于非零的概率密度梯度指向概率密度增加最大的方向,從平均上來說,采樣區(qū)域內(nèi)的樣本點更多的落在沿著概率密度梯度增加的方向。因此,對應的Mean Shift向量應該指向概率密度梯度的負方向。Mean Shift跟蹤算法反復不斷地把數(shù)據(jù)點朝向Mean Shift矢量方向進行移動,最終收斂到某個概率密度函數(shù)的極值點。在Mean Shift跟蹤算法中,相似度函數(shù)用于刻畫目標模板和候選區(qū)域所對應的兩個核函數(shù)直

17、方圖的相似性,采用的是Bhattacharyya系數(shù)。因此,這種方法將跟蹤問題轉化為Mean Shift模式匹配問題。核函數(shù)是Mean Shift算法的核心,可以通過尺度空間差的局部最大化來選擇核尺度,若采用高斯差分計算尺度空間差,則得到高斯差分Mean Shift算法。Mean Shift算法假設特征直方圖足夠確定目標的位置,并且足夠穩(wěn)健,對其他運動不敏感。該方法可以避免目標形狀、外觀或運動的復雜建模,建立相似度的統(tǒng)計測量和連續(xù)優(yōu)化之間的聯(lián)系。但是,Mean Shift算法不能用于旋轉和尺度運動的估計。為克服以上問題,人們提出了許多改進算法,如多核跟蹤算法、多核協(xié)作跟蹤算法和有效的最優(yōu)核平移

18、算法等。文獻11則針對可以獲得目標多視角信息的情況,提出了一種從目標不同視角獲得多個參考直方圖,增強Mean Shift跟蹤性能的算法。4基于運動檢測的目標跟蹤算法基于運動檢測的目標跟蹤算法通過檢測序列圖像中目標和背景的不同運動來發(fā)現(xiàn)目標存在的區(qū)域,實現(xiàn)跟蹤。這類算法不需要幀間的模式匹配,不需要在幀間傳遞目標的運動參數(shù),只需要突出目標和非目標在時域或者空域的區(qū)別即可。這類算法具有檢測多個目標的能力,可用于多目標檢測和跟蹤。這類運動目標檢測方法主要有幀間圖像差分法、背景估計法、能量積累法、運動場估計法等。光流算法是基于運動檢測的目標跟蹤的代表性算法。光流是空間運動物體在成像面上的像素運動的瞬時速

19、度,光流矢量是圖像平面坐標點上的灰度瞬時變化率。光流的計算利用圖像序列中的像素灰度分布的時域變化和相關性來確定各自像素位置的運動,研究圖像灰度在時間上的變化與景象中物體結構及其運動的關系。將二維速度場與灰度相聯(lián)系,引入光流約束方程,得到光流計算的基本算法。根據(jù)計算方法的不同,可以將光流算法分為基于梯度的方法、基于匹配的方法、基于能量的方法、基于相位的方法和基于神經(jīng)動力學的方法。文獻12提出了一種基于攝像機光流反向相關的無標記跟蹤算法,該算法利用反向攝像機消除光流中的相同成分,得到有效的跟蹤效果。文獻13將光流算法的亮度約束轉化為上下文約束,把上下文信息集成到目標跟蹤的運動估計里,仿照光流算法,

20、提出了上下文流算法。文獻14引入了幾何流的概念,用于同時描述目標在空間上和時間上的運動,并基于李代數(shù)推導了它的矢量空間表示。幾何流在幾何約束條件下,將復雜運動建模為多個流的組合,形成一個隨機流模型。該算法在運動估計中集成了點對和幀差信息。文獻15介紹了使用互相關的對光照穩(wěn)健的可變光流算法。文獻16提出了基于三角化高階相似度函數(shù)的光流算法三角流算法。該算法采用高階條件隨機場進行光流建模,使之包含標準的光流約束條件和仿射運動先驗信息,對運動估計參數(shù)和匹配準則進行聯(lián)合推理。局部仿射形變的相似度能量函數(shù)可以直接計算,形成高階相似度函數(shù),用三角形網(wǎng)格求解,形成三角流算法。5其他跟蹤問題視覺跟蹤從不同的角

21、度和應用場合出發(fā),會遇到很多不同的問題,比如多模跟蹤、多特征跟蹤、多目標跟蹤、多攝像機跟蹤17、3D跟蹤18和特定應用的跟蹤等。5.1多特征跟蹤和利用上下文信息的目標跟蹤利用多特征刻畫目標是一種非常有效的實現(xiàn)穩(wěn)健跟蹤的方法。不同的特征可以從相同的或者不同的傳感器獲得,如彩色和輪廓19,彩色和梯度20,Haar-Like特征和邊緣21,角點、彩色和輪廓22,彩色和邊緣6,彩色和Wi-Fi 三角化23等。在貝葉斯框架下,有三種方法可以集成多個特征: 1假設特征之間是統(tǒng)計獨立的,可以將多個特征以加權和的形式組合起來;2假設多個特征之間的條件關聯(lián)服從線性約束,可以將相似度概率密度分布表示為各個特征相似

22、度概率密度分布的線性組合;3文獻19給出了一種更加復雜的方法,該方法不對各個特征施加關聯(lián)約束,用概率方法建立各個特征之間的關聯(lián)。除了聯(lián)合使用目標的多特征之外,還可以充分采用上下文、背景和輔助目標等信息來實現(xiàn)穩(wěn)健的目標跟蹤。如文獻24設計了一種考慮上下文的跟蹤算法。該算法采用數(shù)據(jù)挖掘技術在視頻中獲取輔助目標,并將輔助目標用在跟蹤中。對目標和這些輔助目標的協(xié)作跟蹤可以獲得有效的跟蹤性能。這里的輔助目標是至少在一小段時間內(nèi)和目標同時出現(xiàn),和目標具有相同的相關性運動并且比目標更容易跟蹤的視頻內(nèi)容。文獻25在跟蹤算法中,同時采用目標和目標周圍背景的特征點,將目標特征點用于跟蹤,將背景特征點用于鑒別目標是

23、否被遮擋。5.2多目標跟蹤多目標跟蹤(MTVT在每幀圖像中同時正確地對各個目標進行編號,主要算法有概率數(shù)據(jù)關聯(lián)(PDAF、聯(lián)合概率數(shù)據(jù)關聯(lián)(JPDAF。文獻26給出了兩種新的數(shù)據(jù)關聯(lián)方法:聯(lián)合相似度濾波(JLF和約束的聯(lián)合相似度濾波(CJLF。前者是JPDAF算法的擴展,它增加了目標相對于攝像機的深度標志,能夠預測目標之間的遮擋,可以采用不同的特征計算相似度。后者集成了目標的剛性關聯(lián)和深度約束,能夠更好地處理大目標之間的交叉。隨機集濾波和有限集統(tǒng)計算法是另外一類多目標跟蹤方法。有限集統(tǒng)計算法中采用概率假設密度函數(shù),可以解決目標狀態(tài)變量和觀測向量維度變化的問題,可以比較有效地解決目標數(shù)量的增減問

24、題3,27,28。6小結筆者系統(tǒng)地介紹了基于對比度分析的目標跟蹤算法、基于匹配的目標跟蹤算法和基于運動檢測的目標跟蹤算法,重點介紹了特征匹配、貝葉斯與概率圖模型下的視覺跟蹤算法和核跟蹤算法的主要技術內(nèi)容及其最新進展,對多特征跟蹤、上下文跟蹤和多目標跟蹤的進展也作了簡單介紹。由于目標跟蹤任務的復雜性,應該根據(jù)不同的應用場合選用不同的跟蹤方法。在系統(tǒng)設計中,應該根據(jù)具體的精度要求、穩(wěn)健性要求、計算復雜度要求和實時性要求等采用不同的算法。多種技術的聯(lián)合應用可以有效克服單一技術的局限性。因此,目標跟蹤算法的方向發(fā)展為多模跟蹤、多特征融合跟蹤、基于目標所在的上下文和運動軌跡等信息的跟蹤。參考文獻:1蔡榮

25、太.非線性自適應濾波器在電視跟蹤中的應用D.北京:中國科學院,2008.計算機仿真,2007,24(12:181-184.3MAGGIO E,TAJ M,CAVALLARO A.Efficient multi-target visualtracking using random finite setsJ.IEEE Transactions on Circuits and Systems for Video Technology,2008,18(8:1016-1027. 4XU X,LI B.Adaptive raoblackwellized particle filter and its ev

26、aluationfor tracking in surveillanceJ.IEEE Transactions on Image Processing, 2007,16(3:838-849.5LAO Y,ZHU J,ZHENG Y.Sequential particle generation for visualtrackingJ.IEEE Transactions on Circuits and Systems for Video Technology,2009,19(9:1365-1378.6PAN P,SCHONFILD D.Dynamic proposal variance and o

27、ptimalparticle allocation in particle filtering for video trackingJ.IEEE Transaction on Circuits and Systems for Video Technology,2008, 18(9:1268-1279.7BOUAYNAYA N,SCHONFELD D.On the optimality of motion-based particle filteringJ.IEEE Transactions on Circuits and Systems for Video Technology,2009,19

28、(7:1068-1072.8IOANNIS P,EDWIN H R.Coupled prediction classification forrobust visual trackingJ.IEEE Transactions on Pattern Analysis and Machine Intelligence,2010,32(9:1553-1567.9SOTO D A,REGAZZONI M C S.Bayesian tracking for videoanalyticsJ.IEEE Signal Processing Magazine,2010,27(5:46-55.10王宇.基于Mea

29、n Shift的序列圖像手勢跟蹤算法J.電視技術,2010,34(6:99-101.11LEICHTER I,LINDENBAUM M,RIVLIN E.Mean Shift trackingwith multiple reference color histogramsJ.Computer Vision and Image Understanding,2010,114(3:400-408.12GUPTA P,VITORIA L N,LAVIOLA J J.Markerless tracking usingpolar correlation of camera optical flowC/Pr

30、oc.2010IEEE Virtual Reality Conference.Waltham,MA,UK:IEEE Press,2010:223-226.13WU Ying,FAN Jialue.Contextual flowC/Proc.2009IEEEInternational Conference on Computer Vision,Miami,FL,USA:IEEE Press,2009:33-40.14LIN D,GRIMSON E,FISHER J.Modeling and estimating persistentmotion with geometric flowsC/Pro

31、c.2010IEEE International Con-ference on Computer Vision.San Francisco,CA,USA:IEEE Press, 2010:1-8.15MOLNAR J,CHETVERIKOV D,FAZEKAS S.Illumination-robustvariational optical flow using cross-correlationJ.Computer Vision and Image Understanding,2010,114(10:1104-1114.16GLOCKER B,HEIBEL T H,NAVAB N,et al

32、.Triangle flow:opticalflow with triangulation-based higher-order likelihoodsC/Proc.(下轉第142頁 Lecture Notes in Computer Science(ECCV2010.Heraklion,Crete, Greece:s.n.,2010:272-285.17ESHEL R,MOSES Y.Tracking in a dense crowd using multiplecamerasJ.International Journal of Computer Vision,2010,88(1: 129-

33、143.18LI R,TIAN T,SCLAROFF S,et al.3D human motion tracking witha coordinated mixture of factor analyzersJ.International Journalof Computer Vision,2010,87(1-2:170-190.19NOGUER M F,SANFELIU A,SAMARAS D.Dependent multiplecue integration for robust trackingJ.IEEE Transactions on Pattern Analysis and Ma

34、chine Intelligence,2008,30(4:670-685.20CHANG C,ANSARI R,KHOKHAR A.Multiple object trackingwith kernel particle filterC/Proc.IEEE Conference on Computer Vision and Pattern Recognition.San Diego,CA,USA:IEEE Press, 2005:566-573.21YANG C,DURAISWAMI R,DAVIS L.Fast multiple object trackingvia a hierarchic

35、al particle filterC/Proc.IEEE International Con-ference on Computer Vision.Beijing,China:IEEE Press,2005:212-219.22MAKRIS A,KOSMOPOULOS D,PERANTONIS S,et al.Hierarchicalfeature fusion for visual trackingC/Proc.IEEE International Con-ference on Image Processing,San Antonio,Texas,USA:IEEE Press, 2007:

36、289-292.23MIYAKI T,YAMASAKI T,AIZAWA K.Tracking persons usingparticle filter fusing visual and Wi-Fi localizations for widely distributed cameraC/Proc.IEEE International Conference on Image Processing,San Antonio,Texas,USA:IEEE Press,2007:225-228.24YANG M,HUA G,WU Y.Context-aware visual trackingJ.IE

37、EETransactions on Pattern Analysis and Machine Intelligence,2009, 31(7:1195-1209.25KHAN Z H,GU I Y H.Joint feature correspondences andappearance similarity for robust visual object trackingJ.IEEE Transactions on Information Forensics and Security,2010,5(3: 591-606.26RASMUSSEN C,HAGER G D.Probabilistic data associationmethods for tracking complex visual objectsJ.IEEE Transactions on Pattern Analysis and Machine Intelligence,2001,23(6:560-576.27MAHLER R.Multi target Bayesian filter in via first-order multitarget momentsJ.IEEE Tr