一种基于粒子滤波的多目标跟踪算法

许伟村，赵清杰

(北京理工大学 计算机学院，智能信息技术北京市重点实验室，北京，100081)

摘要：提出一种新的基于粒子滤波的多目标跟踪算法。该算法根据每个目标的状态估计值从全局观测空间中为其分配一个独立的子空间作为其生存空间，通过分别估计每个子空间中的后验概率分布，以更低的计算复杂度得到多模态的后验概率分布估计，从而实现多目标跟踪。另外，提出一种基于加速度估计的动态模型和基于该模型的自适应粒子数策略，能够进一步提高在非线性非高斯状况下跟踪的准确度。在实验中，使用提出的算法对实际拍摄的视频序列中的多个目标进行跟踪，并针对一种非线性非高斯系统分别采用3种不同多目标跟踪算法所用的动态模型进行实验。结果证明：所提出的算法能够在实际环境中实时稳定地实现目标数不固定的多目标跟踪，且提出的动态模型也明显优于其他2种动态模型，更加适用于非线性非高斯情况下的跟踪。

关键词：多目标；跟踪；粒子滤波；子空间

中图分类号：TP301          文献标志码：A         文章编号：1672-7207(2011)S1-0805-06

Multiple target tracking based on particle filtering method

XU Wei-cun, ZHAO Qing-jie

(Beijing Laboratory of Intelligent Information Technology, School of Computer Science and Technology,

Beijing Institute of Technology, Beijing 100081, China)

Abstract: A new multi-target tracking framework was proposed based on particle filtering. It first supplies a sub-space from the global observation space for each target according to its state value, and then computes the posterior density of every sub-space from randomly generated particles to get an approximation of global multi-modal posterior density with much lower computational complexity. A new dynamic model based on acceleration estimation and a new adaptive particle strategy based on this dynamic model were also proposed to approve the tracking precision in non-linear non-Guassian situation and decrease the computational cost. The proposed tracking algorithm was tested by tracking targets in real visual series captured in real world and the results indicate that the proposed algorithm can track multiple targets robustly almost in real time when the number of targets is not fixed and really large. Another experiment was carried out to compare the efficiency of the proposed algorithm and another multi-target tracking framework in detecting new targets and in the experiment the proposed algorithm performs much better than the other one. The dynamic model was also tested with two other different models and proved to be better than the other two models.

Key words: multi-target; track; particle filtering; sub-space

多目标跟踪可应用的范围非常广泛，传统的应用领域有公共监控系统中对人或车辆的跟踪^[1-2]、对比赛中运动员的跟踪^[3]、雷达跟踪^[4]等。近年来出现的很多高层次的研究也需要多目标跟踪系统输出的低层次数据支持，如行为分析、事件检测等。

粒子滤波算法^[5-9]由于可以简单灵活地处理非线性非高斯的模型而被广泛使用。由于粒子滤波很难保持后验概率分布的多模态而无法实现稳定多目标跟踪 ^{[1-2, 4, 10]}。研究人员提出了许多对粒子滤波算法的改进，如MPF(Mixture Particle Filter)^{[3, 11]}通过一个混合模型表示整体后验概率分布，实现后验概率分布的多模态保持。上述各种方法虽然使某些多目标跟踪问题得以实现，但是，在多目标跟踪时其计算复杂度比单目标的情况下高出很多，且并没有解决多目标跟踪中最具有挑战性的问题，即随目标数的增加算法的效率会随着所使用的粒子数指数式增长而急剧下降。

PHD滤波方法(Probability Hypothesis Density filters)^[12-14]通过估计与后验概率分布相关联的一阶矩，能够有效降低实现多目标跟踪的计算复杂度，但其缺点在于其迭代中存在无法找到闭合解的多重积分。Particle-PHD滤波^[13]和GM-PHD滤波(Gaussian Mixture PHD Filters)^[14]虽然实现了PHD迭代精确解的估计，但两者由于需要在状态转移模型和观测模型上进行线性高斯假设，因而无法广泛应用。

本文提出一种多子空间粒子滤波算法，通过在全局状态空间中为每个目标划分独立子空间的策略，将多维多目标跟踪问题转化为一维的单目标跟踪问题集合。通过估计每个子空间内的后验概率分布实现全局后验概率分布估计，从而实现多通道独立多目标跟踪，降低多目标跟踪的计算复杂度。在能够稳定保持后验概率多模态分布的前提下，产生的计算量相当于多个单目标跟踪问题的和，随目标数目增长而增长的速度非常有限。本文同时提出了一种基于加速度统计的动态模型以及一种自适应粒子数策略，从而在准确跟踪的前提下进一步有效节省计算开支。

1  粒子滤波

粒子滤波是一种基于贝叶斯连续估计的滤波方法，通过一个加权粒子集合估计状态的后验概率分布来实现目标跟踪的目的。本节对粒子滤波应用于视频跟踪的版本，即Isard和Blake提出的Condensation算法^[9]进行简要介绍，文献[9]对Condensation算法进行了详尽描述。

定义时刻t的状态向量为x_t，历史为X_t={x₁, …, x_n}。假设物体的动态模型服从马尔可夫过程，即：

         (1)

定义观测向量为y_t，历史为Y_t={y₁, …, y_n}，假设观测向量相互独立且独立于运动过程，即：

   (2)

上式可简化为：

          (3)

结合上文，可得条件概率密度P_t(x_t)=P(x_t|Y_t)随时间传播规则计算方程如下：

             (4)

式中：k_t是一个与x_t无关的归一化常数，而

    (5)

当P(x_t|Y_t-1)较复杂时，无法得到P(x_t|Y_t)的闭合解。为了在非高斯模型中对P(x_t|Y_t)进行估计，Condensation引入了因子采样技术，从用以表示上一时刻的后验概率密度P(x_t-1|Y_t-1)的集合 中，通过预测得到先验概率P(x_t|Y_t-1)，根据先验概率得到一个由N个粒子构成的加权样本集合来近似后验概率密度P(x_t|Y_t)。采样数目N是一个不变值。

Condensation的迭代过程可以进一步描述为：通过重采样步骤从集合中选择N个概率为的样本。令所有选出的N个样本进行一次相同的偏移。再通过扩散过程把样本分离开来，并最终得到集合，然后通过观测步骤从观测概率密度P(x_t|Y_t)中得到集合，以表示时刻t的状态概率密度。

2  多子空间粒子滤波算法

2.1  状态模型

用表示t时刻离开场景或者跟踪失败的目标数目，表示新目标的数目，即得到该时刻的目标数目，其中。目标跟踪以划分子空间的方式分成个独立通道进行，每个目标有独立的子空间和样本集合，某个目标离开场景或跟踪失败时，其子空间随即被销毁。

对于目标i，用表示其子空间，其中是目标i的状态在时刻t的预测值，目标相对于其子空间静止，其状态转移过程被子空间的状态转移过程的代替。子空间是以为中心，以为半径的圆形窗口，包含目标中心所有可能出现的位置。所有目标的子空间组成集合，y_t表示t时刻得到的全部观测数据。用表示t时刻目标i的状态偏移，得到子空间的状态转移方程：

              (6)

其中：

              (7)

其中：是欧几里德距离表达式。表示所有不属于任一子空间的像素点的集合，则有

              (8)

其中：。根据前文所述，可得目标i的后验分布

     (9)

而

      (10)

式中：α是常量。假设t时刻速度改变值最有可能出现于区间[0，]，表示目标i在该时刻之前的一段时间T内的加速度最大值的估计值。由于该值能够代表目标运动状态改变的活跃程度，因此称之为活性  值。实际中，该值会随着时间而改变，且与其上一时刻的值相关。根据上述推断和假设，得到eⁱ的估计方    程：

  (11)

式中：e^*是一个较大的常量，而ξ是一个不大于1的常数，决定更新速度，大小由T决定，有T= (1-ξ)^-1。在实验中，设T=4即得到ξ=0.75。设子空间实体窗口的半径，γ是一个大于1的正值。

2.2  自适应粒子数策略

在多目标跟踪中，根据每个目标的运动状态合理分配粒子数，可以在实现对目标稳定跟踪的前提下有效减少不必要的计算开支。

文献[15]中提出了根据目标搜索范围确定粒子数多寡的策略。但是其根据目标速度来确定搜索范围的方法不甚合理。在多子空间粒子滤波算法中，目标的子空间包含目标全部可能出现的区域，子空间的规模即决定了搜索范围，而决定子空间规模的量即目标的活性值。用表示跟踪目标i需要的样本(粒子)数目。计算公式为：

            (12)

式中：N^*表示全局搜索时需要的样本数，而S表示y_t的规模。根据上述方程得到的粒子数目会随着目标的活性值随时间变化而更新。

2.3  多子空间粒子滤波

多子空间粒子滤波算法中将新目标检测分为采样、观测、样本聚类和新目标初始化4个步骤。首先在不被任何目标的子空间所包含的独立区域进行采样，采样使用的样本数目是固定的，用表示，在时刻t，从中采集个粒子得到集合。采样完成后，通过观测步骤来计算集合中粒子的权重，规定一个阈值η，权重大于η的样本为有效样本。为减小计算量，保留采样得到的有效样本，舍弃其他样本。由于多子空间粒子滤波算法采取对每个目标都进行独立跟踪的策略，因此，对样本进行基于距离的聚类，将属于同一目标的样本归为同一样本集，样本集数目即时刻t的新目标数目。

在每个样本集内部归一化粒子权重，对于新目标i，初始化其偏移矩阵为O，噪声最大估计值，得到下一时刻的状态估计值。根据子空间定义为其分配子空间。

执行上述操作次，最终得到新目标的子空间集合。

目标跟踪分多个通道进行，每个跟踪中的目标的子空间代表一个跟踪通道，独立拥有一个样本集合。首先进行观测步骤，在时刻t，对于目标i和其子空间，计算其样本集合中粒子的权重。统计粒子集合中权重高于η的粒子数目，若则该目标跟踪失败，停止对其跟踪；否则对样本集合中的所有样本进行权重归一化，得到目标子空

间内的后验概率分布。随后通

过预测步骤更新目标子空间的状态。根据方程(7)计算偏移矩阵，从而得到下一时刻的目标状态估计值。根据更新方程(11)更新噪声最大值，即得到下一时刻目标i的子空间。重复上述步骤至处理完所有目标，得到跟踪失败的目标数目。

上述操作完成后即进入重采样。对于目标i，在内进行全局均匀随机采样获取新的样本集合，采样数目根据方程(12)计算。

重复上述操作，最终得到集合 i=1, 2, …, M_t+1；j=1, 2, …, 。

3  实验结果及分析

为测试多子空间粒子滤波算法的效果，我们进行了2组实验。第1组实验在实际视频序列上应用多子空间粒子滤波算法对多个目标进行跟踪。实验程序使用C++语言编写，运行于配置为IntelCore2DuoCPU的计算机上。视频序列分辨率为640×480，采集频率为25帧，共分为2组，一组拍摄于一个运动场；另一组拍摄于北京某过街天桥。实验设置e^* = 50，γ= 1.4，= 400，N^*=2 000。

共进行2组实验。第1组实验对比了本文提出的动态模型和SDV(State Dependent Variance)模型以及线性模型在仿真下的目标跟踪效果。目标的状态转移模型为x_t=x_t-1+v _t-1+r(t)，其中，v _t-1是上一时刻的目标速度，t={1, 2, …, 100}，r(t)是在时刻t随机产生的服从均匀分布的噪声。上述模型模拟实际目标跟踪中较为常见的目标运动状态，即服从恒速模型的同时，具有很大随机性，往往突然改变运动状态。

实验代码用Matlab编写，用3个不同的值5、10、15各进行1 000次独立仿真实验，不同的代表了活性不同的目标。越大，则目标活性越大，越容易突然改变运动状态。每次实验分别使用多子空间粒子滤波算法方法和PHD-MT方法使用的SDV模型和传统线性模型对仿真目标进行跟踪，并统计不同模型跟踪失败的次数，计算均值和方差。实验结果如表1和图1所示。由于能够较为准确地估计目标的加速度值分布区间，多子空间粒子滤波算法使用的动态模型在不需要人工干预的情况下表现好于其他2种模型，其跟踪效果并未随的增大而产生大的变化，具有较强的稳定性。其他2种模型随着值变大，效果变得很不理想。图1所示分别给出了取不同值时所进行的一次独立实验中前20个时刻3种模型的跟踪结果对比，图中模型加箭头表示在箭头所指的点该模型跟踪失败。

表1  动态模型跟踪效果比对

Table 1  Comparative results of different dynamic models

第二组实验通过真实数据对算法的稳定性和运行实时性进行了检测，结果显示多子空间粒子滤波算法性能较好，能够很好地处理目标数目不固定的多目标跟踪，稳定性高。在目标数较多(6个以上)时，系统处理每帧图像的平均运行时间为0.157 s，基本满足实时性需求。

图2中的3组图片显示了算法的运行情况。用圆框代表目标子空间窗口，方框代表目标的状态估计值。图2(a)所示为多子空间粒子滤波算法检测和跟踪快速运动目标的效果，其所对应的视频中目标大都在不到1 s穿过并离开场景。图2(b)和(c)所示的2组图片中，目标的数目不同，显示系统可以处理非固定目标数的情况。由于本文的目的是提出一个能够实现多目标跟踪的算法框架，而非目标检测方法，因此，实验中使用的是便于实现的背景减除法对目标进行检测。图中目标的圆形窗口大小不同，表明目标运动速度不统一，窗口较大的目标运动速度变化频繁，窗口较小说明目标运动较平稳。

图1  不同动态模型在仿真实验中的结果

Fig.1  Experimental results using different dynamic models

图2  使用多子空间粒子滤波算法进行的多目标视频跟踪实验

Fig.2  Tracking results using MSSPF method

4  结论

提出了一种多目标视频跟踪算法框架。该框架基于一种多子空间粒子滤波算法，该算法根据目标状态估计值从观测空间中划分出多个子空间，再通过分别估计每个子空间内的后验概率分布实现多目标跟踪。同时提出一种基于加速度值估计的动态模型和基于该模型的自适应粒子数策略，进一步提高了跟踪的准确性，并降低了计算开支。实验证明：多子空间粒子滤波算法能够很好地解决多目标跟踪中计算复杂度过高的问题，能够实时稳定地实现多目标跟踪，结合本文提出的动态模型和自适应粒子数策略，能够更加灵活稳定地解决多目标跟踪问题。

参考文献：

[1] Cue H, Cadre J-P L, Perez P. Tracking Multiple objects with particle filtering[J]. IEEE Trans Aerosp Electron Syst, 2002, 38(3): 791-812.

[2] Kang H, Kim D, Bang S Y. Real-time multiple people tracking using competitive condensation[J]. Pattern Recognition, 2002, 38(7): 325-328.

[3] Okuma K, Taleghan A, Freitas J F G, et al. A boosted particle filter: Multitarget detection and tracking[C]//European Conference Computer Vision. Prague: Springer, 2004: 28-39.

[4] Ke Y, Sukthankar R, Hebert M. Volumetric features for video event detection[J]. International Journal of Computer Vision, 2010, 88(3): 339-362.

[5] Doucet A. On sequential simulation-based methods for Bayesian filtering[R]. Technical report, CUED/F-INFENG/TR 310, 1998.

[6] LIU J S. Metropolized independent sampling with comparison to rejection sampling and importance sampling[J]. Stat Comput, 1996, 6(2): 113-119.

[7] Iwahori Y, Enda N, Fukui S, et al. Efficient tracking with Adaboost and particle filter under complicated background[C]// Knowledge-Based Intelligent Information and Engineering Systems. Berlin, Heidelberg: Springer, 2010: 887-894.

[8] 王法胜, 赵清杰. 一种用于解决非线性滤波问题的新型粒子滤波算法[J]. 计算机学报, 2008, 31(2): 346-352.
WANG Fa-sheng, ZHAO Qing-jie. A new particle filter for nonlinear filtering problems[J]. Chinese Journal of Computers, 2008, 31(2): 346-352.

[9] Isard M, Blake A. Condensation-Conditional density propagation for visual tracking[J]. International Journal on Computer Vision, 1998, 29(1): 5-28.

[10] Stasiak L, Pacut A, Gordon N. Particle filters for multi-face detection and tracking with automatic clustering[C]//IEEE International Workshop Imag Syst Technol. Krakow: IEEE, 2007: 1-6.

[11] Vermaak A, Doucet A, Perez P. Maintaining multi-modality through mixture tracking[C]//IEEE ICCV. 2003: 1110-1116.

[12] Xu B, Xu H, Zhu J. Ant clustering PHD filter for multiple-target tracking[J]. Applied Soft Computing, 2011, 11(1): 1074-1086.

[13] Vo B, Singh S, Doucet A. Sequential monte carlo implementation of the PHD filter for multi-target tracking[C]// Proceedings of International Conference on Information Fusion. Orlando: IEEE, 2003: 792-799.

[14] Vo B, Ma W. The gaussian mixture probability hypothesis density filter[J]. IEEE Trans Signal Process, 2006, 54(11): 4091- 4104.

[15] Zhou S K, Chellappa R, Moghaddam B. Visual tracking and recognition using appearance-adaptive models in particle filters [J]. IEEE Trans Image Process, 2004, 13(11): 1491-1505.

(编辑 袁赛前)

收稿日期：2011-04-15；修回日期：2011-06-15

基金项目：国家自然科学基金资助项目(60772063)

通信作者：许伟村(1985-)，男，山东人，博士研究生，从事目标跟踪、计算机视觉研究；电话：15801466429；E-mail: xuwcun@gmail.com