基于粒子滤波的多运动目标跟踪 By：王丽春 iiec.cqu.edu.cn.

Presentation on theme: "基于粒子滤波的多运动目标跟踪 By：王丽春 iiec.cqu.edu.cn."— Presentation transcript:

1 基于粒子滤波的多运动目标跟踪 By：王丽春 iiec.cqu.edu.cn

2 目录 运动目标跟踪简介 基于粒子滤波的运动目标跟踪 基于团块分析的多运动目标跟踪框架 实验结果演示 讨论

3 运动目标跟踪简介 什么是运动目标跟踪？ 运动目标的跟踪就是在视频图像的每一幅图像中确定出感兴趣的运动目标（例如车辆、行人、动物等）的位置，并把不同帧中同一目标对应起来，形成完整的轨迹。

4 运动目标跟踪简介 运动目标检测与运动目标跟踪的区别？ 分类 运动目标检测是检测图像中的运动目标，不做目标之前的关联；
运动目标跟踪是找出同一目标在不同帧的位置，并将其关联起来。 分类 静态背景目标跟踪 动态背景目标跟踪 单目标跟踪 多目标跟踪

5 运动目标跟踪简介 运动跟踪应用领域 军事公安方面的应用：在军事方面主要用于导弹的精确制导，可疑目标的检测与跟踪公安业务图片的判读分析，指纹识别，人脸识别，不完整图片的复原，以及智能交通监控、事故分析等。 1 2 工业方面的应用：具备视觉、听觉和触觉功能的智能机器人的成功应用。 3 生物医学工程方面的应用：各种细胞的运动分析检测和判别 4 智能交通方面：通过对道路交通情况的实时监控，利用图像处理技术对各种情况作出准确的判断。 5 体育方面的应用：对运动员在比赛或者是训练中的技术动作的视频进行分析，得出精确的运动参数进行分析。

6 运动目标跟踪简介 运动目标跟踪方法概述 视频目标跟踪算法 基于对比度分析 基于匹配 核方法 运动检测 其它方法 特征匹配 贝叶斯 跟踪
Mean shift方法 光流法

7 目录 运动目标跟踪简介 基于粒子滤波的运动目标跟踪 基于团块分析的多运动目标跟踪框架 实验结果演示 讨论

8 基于粒子滤波的运动目标跟踪 动态状态空间模型
统计信号处理中的非线性滤波问题广泛存在于自动控制、跟踪、数字通信、经济统计等领域,其基本任务就是要从受噪声污染的观测量中去递推地估计不可观测的系统状态,该系统被称为动态状态空间（DSS）模型。 DSS模型至少需要两个参考模型， 即描述随时间变化的状态模型及与状态有关并带有噪声的观测模型。 状态模型： 观测模型： 该模型的目的就是要递推地在每次获得观测量 后,估计状态量 的条件概率密度

9 通过时间预测和测量更新这两步的反复迭代,就可最优地估计出
基于粒子滤波的运动目标跟踪 贝叶斯滤波器 通过时间预测和测量更新这两步的反复迭代,就可最优地估计出 缺点 最优解 仅在少数情况才是解析和有 限维的，如在模型线性以及噪声和初始状态均为高斯独立分布时，线性高斯卡尔曼滤波。 而对于一般的非线性DSS 模型,上述最优解通常并不解析,而且随着时间的推移将趋于无穷维。

10 状态维数的增高会导致运算量的迅速增大,而且滤波器传递的是一、二阶的统计信息,在非线性、非高斯特性较强时滤波性能急剧下降甚至会发散。
基于粒子滤波的运动目标跟踪 扩展卡尔曼滤波 因为“维数灾难”以及运算量和存储量的急剧膨胀而使得该最优解在物理上不可实现,在工程上也只需做某种近似即可,即寻找上述问题的次优解。用的最多的次优算法便是扩展卡尔曼滤波。 缺点 状态维数的增高会导致运算量的迅速增大,而且滤波器传递的是一、二阶的统计信息,在非线性、非高斯特性较强时滤波性能急剧下降甚至会发散。 粒子滤波器则有望克服上述方法存在的缺陷。

11 基于粒子滤波的运动目标跟踪 粒子滤波 简单来说，粒子滤波是用一个N粒子的带有权值的粒子集 的样本均值来近似替代 。
粒子滤波(Particle Filter)的思想基于蒙特卡洛方法，其核心思想是通过从后验概率中抽取的随机状态粒子来表达其分布。 简单来说，粒子滤波法是指通过寻找一组在状态空间传播的随机样本对概率密度函数进行近似，以样本均值代替积分运算，从而获得状态最小方差分布的过程。这里的样本即指粒子,当样本数量N→∝时可以逼近任何形式的概率密度分布。 简单来说，粒子滤波是用一个N粒子的带有权值的粒子集 的样本均值来近似替代 。

12 基于粒子滤波的运动目标跟踪 粒子滤波应用举例 团块信息： t-1帧 运动目标： 粒子： t帧 (红色矩形) (蓝色矩形) …… p1 p2
pn t帧

13 基于粒子滤波的运动目标跟踪 粒子滤波应用举例
第i个粒子表示为：P(i) = {x(i), y(i), w(i), h(i)},其中i = 1,2,3……N 第i个粒子权重为：w(i)，其中i = 1,2,3……N 则最终状态输出为P = {x, y, w, h},则 P = 𝑖=0 𝑁 𝑤 𝑖 ∗𝑃(𝑖) 等价于： x = 𝑖=0 𝑁 𝑤 𝑖 ∗𝑥(𝑖) y = 𝑖=0 𝑁 𝑤 𝑖 ∗𝑦(𝑖) w = 𝑖=0 𝑁 𝑤 𝑖 ∗𝑤(𝑖) h = 𝑖=0 𝑁 𝑤 𝑖 ∗ℎ(𝑖)

14 基于粒子滤波的运动目标跟踪 粒子滤波应用领域 在经济学领域，被应用在经济数据预测；
粒子滤波技术在非线性、非高斯系统表现出来的优越性，决定了它的应用范围非常广泛。国际上，粒子滤波已被应用于各个领域： 在经济学领域，被应用在经济数据预测； 在军事领域，已经被应用于雷达跟踪空中飞行物，空对空、空对地的被动式跟踪； 在交通管制领域，被应用在对车或人视频监控； 在人工智能领域，被用于机器人的全局定位。

15 基于粒子滤波的运动目标跟踪 粒子滤波算法过程 1）系统粒子初始化 2）重要性采样 3）计算粒子权重 4）重采样 5）输出状态估计 粒子初始化

16 基于粒子滤波的运动目标跟踪 Step1: 粒子初始化
初始时刻k＝0，在空间中按随机、均匀或高斯等方式抽取N个样本（即粒子） 𝑥 𝑘 𝑖 ，i＝1,…,N，每个粒子具有相同的权重1/N，建立初始状态样本集： 初始目标状态 初始粒子

17 Step2: 重要性粒子采样（粒子状态转移）
基于粒子滤波的运动目标跟踪 Step2: 重要性粒子采样（粒子状态转移） 根据粒子的重要性概率密度函数以及k-1时刻的粒子集 计算出k时刻新的粒子集 重要性粒子采样意味着在权重值较高的粒子附近取更多的粒子，在权重值较少的粒子附近取更少量的粒子。

18 基于粒子滤波的运动目标跟踪 Step3: 计算粒子权重 假设图中以空间距离为标准，则各粒子的权重如下图：
在得到预测粒子后，并不是所有的预测粒子得到k时刻观测值的概率是相等的。越是接近真实状态的粒子，当然越有可能获得观测值。k时刻的预测粒子与k-1时刻的目标状态之间的相似性越大，则粒子的权重越大。 假设图中以空间距离为标准，则各粒子的权重如下图： 0.02 0.1 K-1时刻目标状态 K时刻样本粒子 0.05 0.01

19 基于粒子滤波的运动目标跟踪 Step3: 计算粒子权重 计算出所有粒子的权重值后，归一化权重值：

20 基于粒子滤波的运动目标跟踪 Step4: 重采样
基本思想就是消除权重很小的无效粒子，复制高权值的粒子，尽量利用权重较大的粒子，形成新的粒子集。

21 基于粒子滤波的运动目标跟踪 第一步：经过系统观测后每个粒子的权重被更新，其中更符合实际情况的粒子，被赋予较大的权重（图中用面积较大的圆点表示），而偏离实际情况的粒子被赋予较小的权重（图中以面积较小的圆点表示） 第二步：即重采样过程，前一代的粒子被复制为“后代”粒子，其中权值较大的粒子被复制为更多“后代”粒子，而权值较小的粒子被复制的次数较少，一些权值特别小的粒子不会被复制，从而在重采样过程中被丢弃。所有“后代”粒子的权值都被设置为1/N。

22 基于粒子滤波的运动目标跟踪 Step5: 输出状态估计 Step6: k=k+1, 返回step2。

23 二：样本贫化(Sample Impoverishment)
基于粒子滤波的运动目标跟踪 粒子滤波算法的缺点 一：样本数量问题 需要用大量的样本数量才能很好地近似系统的后验概率密度。面临的环境越复杂，描述后验概率分布所需要的样本数量就越多，算法的复杂度就越高。 二：样本贫化(Sample Impoverishment) 重采样方法会带来粒子贫化的问题即权值大的粒子被复制较多，而权值较小的粒子被复制较少甚至没有子代。因此粒子集合的多样性减弱，不足以用来近似后验概率密度，甚至出现全部粒子都来自少数几个权值最大的粒子的情况。

24 基于粒子滤波的运动目标跟踪 粒子滤波在运动跟踪中的应用—初始化粒子 团块信息： t-1帧 运动目标： 粒子： t帧 (红色矩形)
(蓝色矩形) …… p1 p2 p3 p4 pn t帧

25 粒子滤波在运动跟踪中的应用—粒子权重计算 1) 特征选取
基于粒子滤波的运动目标跟踪 粒子滤波在运动跟踪中的应用—粒子权重计算 1) 特征选取 选取图像的RGB颜色直方图作为特征, 分别计算目标区域、每个粒子的颜色直方图。

26 粒子滤波在运动跟踪中的应用—粒子权重计算 2）相似度计算
基于粒子滤波的运动目标跟踪 粒子滤波在运动跟踪中的应用—粒子权重计算 2）相似度计算 计算每个粒子与运动目标区域的相似度，这里我们采用直方图的巴氏距离进行计算，距离越小，则表示粒子与目标区域的相似度越大，粒子权重也就越大。 颜色直方图1表示为： 颜色直方图2表示为： 则直方图之间的巴氏距离可表示为： 相似度可表示为：

27 基于粒子滤波的运动目标跟踪 粒子滤波在运动跟踪中的应用—状态输出
第i个粒子表示为：P(i) = {x(i), y(i), w(i), h(i)},其中i = 1,2,3……N 第i个粒子权重为：w(i)，其中i = 1,2,3……N 则最终状态输出为P = {x, y, w, h},则 P = 𝑖=0 𝑁 𝑤 𝑖 ∗𝑃(𝑖) 等价于： x = 𝑖=0 𝑁 𝑤 𝑖 ∗𝑥(𝑖) y = 𝑖=0 𝑁 𝑤 𝑖 ∗𝑦(𝑖) w = 𝑖=0 𝑁 𝑤 𝑖 ∗𝑤(𝑖) h = 𝑖=0 𝑁 𝑤 𝑖 ∗ℎ(𝑖)

28 基于粒子滤波的运动目标跟踪 应用中遇到的问题： 1）粒子数量问题 2）颜色直方图bin数量问题 结论
粒子数量过多，算法速度过慢，无法满足应用的实时性；粒子数量过少，算法速度快，但是算法的准确性明显下降。 2）颜色直方图bin数量问题 颜色直方图的bin的数量很大程度上影响到粒子权重计算的时间。bin数量过多，直方图维数大，计算粒子权重时耗时大；bin数量少，直方图包含的信息量少，无法很好的表征图像信息，跟踪的准确率下降。 结论 根据实际应用，选取合适的粒子数量、颜色直方图的bin数量很重要。

29 基于粒子滤波的运动目标跟踪 主要改进 1）颜色空间 RGB、HSV 2） 特征选取 各特征融合，如颜色直方图+边缘特征。
颜色直方图、边缘轮廓特征(梯度直方图)、角点等； 各特征融合，如颜色直方图+边缘特征。

30 基于粒子滤波的运动目标跟踪 主要改进 3）特征表征方式 整体和分块。 4 ）重采样方式 针对粒子贫化问题的改进

31 目录 运动目标跟踪简介 基于粒子滤波的运动目标跟踪 基于团块分析的多运动目标跟踪框架 实验结果演示 讨论

32 基于团块分析的多运动目标跟踪框架 引入团块分析的原因 提取前景团块
多运动目标跟踪时，如果对每一个目标都进行单独的预测，算法耗时过大，不是满足监控应用的实时性。因此我们需要尽量避免粒子预测，这里我们引入团块分析策略。 提取前景团块 首先我们对每一帧图像进行运动目标检测处理，常用的方法有背景差分法、帧间差分法、光流法等，目前背景差分法中的背景建模方法应用广泛，典型的有vibe、混合高斯、码本方法等。运动检测的结果一般如下：

33 基于团块分析的多运动目标跟踪框架 团块关系矩阵构建
假设前一帧图像中包含4个团块，分别是PBlob1、PBlob2、PBlob3、PBlob4 假设当前帧图像中包含4个团块，分别是CBlob1、CBlob2、CBlob3、CBlob4 假设1表示团块有重叠部分，0表示无重叠，通过对团块距离的计算，得到如下图所示的团块关系矩阵： CBlob1 CBlob2 CBlob3 CBlob4 1 PBlob1 PBlob2 PBlob3 PBlob4

34 基于团块分析的多运动目标跟踪框架 团块分类 消失的团块 新出现的团块
可分为五大类：消失的团块、新出现的团块、分裂的团块、交叉的团块、正常匹配的团块 消失的团块 行元素都为0，即前一帧中的该团块没有与当前帧中的任何团块重叠，如PBlob1；现实情况如车辆、行人离开场景等。 新出现的团块 列元素都为0，即前一帧中的任一团块都没有与当前帧的该团块重叠，如CBlob1； 现实情况如车辆、行人进入场景。

35 基于团块分析的多运动目标跟踪框架 分裂的团块 交叉的团块 正常匹配的团块
行元素至少有2个不为0，即前一帧的该团块与当前帧中的两个以上团块重叠，如PBlob2；现实情况如人群分离。 交叉的团块 列元素至少有2个不为0，即前一帧中的多个团块与当前帧的该团块重叠，如CBlob2；现实情况如行人、车辆相遇等。 正常匹配的团块 该元素所在的行列除了该元素本身外都为0，即前一帧的某一团块与当前帧的团块正常匹配。现实情况下如场景中的单一行人轨迹。

36 基于团块分析的多运动目标跟踪框架 总体思想 优点： 缺点：
1）新出现的团块、消失的团块、正常匹配的团块、分裂的团块（可以认为是新出现的团块的特例）等四种团块都可以直接跟踪； 2）对交叉的团块进行粒子滤波处理。 优点： 并不对每一个团块进行粒子滤波预测，而只是对交叉团块进行单独的处理，这样就大大减少了多目跟踪所用的时间。 缺点： 严重依赖前景检测的效果。

37 目录 运动目标跟踪简介 基于粒子滤波的运动目标跟踪 基于团块分析的多运动目标跟踪框架 实验结果演示 讨论

38 实验结果 简单场景 兰五.avi 复杂场景 十字路口.avi

39 目录 运动目标跟踪简介 基于粒子滤波的运动目标跟踪 基于团块分析的多运动目标跟踪框架 实验结果演示 讨论

40 Discussion Q & A

41 Thank You ! iiec.cqu.edu.cn