视频目标跟踪算法综述*

蔡荣太 ，吴元昊，王明佳，吴庆祥

（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.