粒子滤波跟踪算法

1、粒子滤波跟踪算法：以下分三步理解粒子跟踪算法，第一种理解是先从形象化理解粒子算法。第二种理解是编写简单的粒子算法。附有有源码，可结合源码理解。第三种理解是从数学角度理论地理解粒子算法。第一种理解：我们看下形象化的粒子滤波跟踪算法。（以下段落为转载）1）初始化阶段-提取跟踪目标特征该阶段要人工指定跟踪目标，程序计算跟踪目标的特征，比如可以采用目标的颜色特征。具体到Rob Hess的代码，开始时需要人工用鼠标拖动出一个跟踪区域，然后程序自动计算该区域色调(Hue)空间的直方图，即为目标的特征。直方图可以用一个向量来 表示，所以目标特征就是一个N*1的向量V。2）搜索阶段-放狗好，我们已经掌握了目标

2、的特征，下面放出很多条狗，去搜索目标对象，这里的狗就是粒子particle。狗有很多种放法。比如，a)均匀的放：即在 整个图像平面均匀的撒粒子(uniform distribution)；b)在上一帧得到的目标附近按照高斯分布来放，可以理解成，靠近目标的地方多放，远离目标的地方少放。Rob Hess的代码用的是后一种方法。狗放出去后，每条狗怎么搜索目标呢？就是按照初始化阶段得到的目标特征(色调直方图，向量V)。每条狗计算它所处的位置 处图像的颜色特征，得到一个色调直方图，向量Vi，计算该直方图与目标直方图的相似性。相似性有多种度量，最简单的一种是计算sum(abs(Vi- V).每条狗算出相似

3、度后再做一次归一化，使得所有的狗得到的相似度加起来等于1.3）决策阶段我们放出去的一条条聪明的狗向我们发回报告，“一号狗处图像与目标的相似度是0.3”,“二号狗处图像与目标的相似度是0.02”,“三号狗处图像 与目标的相似度是0.0003”,“N号狗处图像与目标的相似度是0.013”.那么目标究竟最可能在哪里呢？我们做次加权平均吧。设N号狗的图像像 素坐标是(Xn,Yn),它报告的相似度是Wn,于是目标最可能的像素坐标X = sum(Xn*Wn),Y = sum(Yn*Wn).4）重采样阶段Resampling既然我们是在做目标跟踪，一般说来，目标是跑来跑去乱动的。在新的一帧图像里，目标可能在

4、哪里呢？还是让我们放狗搜索吧。但现在应该怎样放狗呢？让 我们重温下狗狗们的报告吧。“一号狗处图像与目标的相似度是0.3”,“二号狗处图像与目标的相似度是0.02”,“三号狗处图像与目标的相似度是 0.0003”,“N号狗处图像与目标的相似度是0.013”.综合所有狗的报告，一号狗处的相似度最高，三号狗处的相似度最低，于是我们要重新分布 警力，正所谓好钢用在刀刃上，我们在相似度最高的狗那里放更多条狗，在相似度最低的狗那里少放狗，甚至把原来那条狗也撤回来。这就是Sampling Importance Resampling，根据重要性重采样(更具重要性重新放狗)。(2)-(3)-(4)-(2)如是反

5、复循环，即完成了目标的动态跟踪。根据我的粗浅理解，粒子滤波的核心思想是随机采样+重要性重采样。既然我不知道目标在哪里，那我就随机的撒粒子吧。撒完粒子后，根据特征相似度计算 每个粒子的重要性，然后在重要的地方多撒粒子，不重要的地方少撒粒子。所以说粒子滤波较之蒙特卡洛滤波，计算量较小。这个思想和RANSAC算法真是不谋 而合。RANSAC的思想也是(比如用在最简单的直线拟合上)，既然我不知道直线方程是什么，那我就随机的取两个点先算个直线出来，然后再看有多少点符合 我的这条直线。哪条直线能获得最多的点的支持，哪条直线就是目标直线。想法非常简单，但效果很好。第二种理解：简单的粒子算法实现如下：1、 如

6、果要跟踪多个对象，首先要给出第一张图，在其中把这些对象用方框圈出。用颜色直方图来描述这些方框中图像特征。譬如有个跟踪对象，则对应有个方框，以及个颜色直方图信息。2、 假设，此时我们用个粒子去跟踪这个对象。那么每个对象分配个粒子。、所有对象的跟踪方法是一样的，所以我们只研究一个对象的跟踪。一个对象有5个粒子，那什么叫粒子呢？且听我道来。刚开始所有粒子其实就是跟对象方框一样大小的矩形检测器。这5个矩形检测器的位置跟对象方框重叠。假设检测开始，（1）这5个矩形检测器，会利用二阶自回归模型计算出新的位置，新的位置都是围绕在对象中心点周围。（2）新位置计算出来后，计算各个矩形检测器里面的图像的颜色直方图

7、，和对象的颜色直方图做比较，根据相似度来度量5个检测器的权值，相似度越高，权值越大。（3）用权值归一法把5个权值归一。如，5个权值的值是：0.016，0.02，0.04，0.01，0.014。权值归一就是让5个权值加起来等于1，但两两比例不变归一后的权值是：0.16，0.2，0.4，0.1，0.14。（4）权值归一后，就得进行重采样，也就是把权值低（不重要的）的检测器移到权值高的位置去检测。做法是，把权值为0.1和0.14的两个权值最低的检测器，移到跟权值为0.4的检测器一样的位置。 （5）跳到（1）去，重复（1）- （4）步骤。4、算法到此结束。 这里有些疑问。（1） 为什么二阶自回归模型可

8、以计算出新的位置。答案是：自回归过程是一种通过历史数据来预测目前状态的时间序列建模策略. 在这个模型里,目前的状态xt 是一个依赖于以前状态的确定性函数并加上随机干扰,假如确定性函数是线性的,则目前的状态依赖于以前的p 个状态,模型可以写成其中： 是自回归系数;t 是随机干扰,一般情况下是白噪声. 自回归系数既可通过学习的方法得到 ,也可以特别的方式指定 . 鉴于运动员在比赛中的惯性影响,采用持续速度模型更为适合一些,这里采用二阶自回归模型其中: A , B , C 是自回归系数, N (0 ,) 是零均值、标准方差为1 的Gaussian 噪声. 在试验中,指定系数为A = 2 , B =

9、- 1 , C = 3. （2）为什么要进行重采样？答案是：因为如果没进行重采样，则有些粒子（检测器）权值会越来越小，最后只有一个检测器的权值比较大。这种现象叫退化。它意味着要花很多时间去计算哪些权值较低的检测器，这是不希望看到的。5、算法评价（个人想法）： 该算法借鉴了粒子过滤器的思想，但比正真的粒子过滤要简单很多，其跟踪准确率相对较低，而且如果物体移动速度快的话，该算法将跟踪失败。附注：了解粒子算法，可以看下我修改过的粒子过滤跟踪算法源码工程FSTrace，该工程是别人编写，原先只能在LINUX下编译通过，我稍微改动下，现可以在Windows下编译通过并执行。第三种理解粒子算法加深。以下只

10、是个人理解。粒子人脸跟踪算法其实是一种基于概率抽样的算法。（1）人脸跟踪其实就是根据现在的人脸位置预测下一时刻人脸的位置。 那怎么预测下一时刻的人脸位置呢？ 如果能找到一个概率分布密度函数，那事情就容易办了？该函数输入参数是被检测窗口任一点的位置，输出是这点存在人脸的概率。 这意味着概率最大的点最有可能存在人脸，可直接把这一点作为下一时刻的人脸位置。概率密度函数表达式是：p(Xk | Dk)。Xk表示点信息（可以包含速率信息）。Dk是表示检测窗口所有像素点值的向量。（2）所以关键是找到概率密度函数。 对于该密度概率函数，我们要撒下一些粒子才能求到。一个N*N像素点阵就是粒子。（3） 怎么计算该

11、概率密度函数呢？我们假设检测窗口为100*100，粒子的尺寸是5*5，那么粒子数量是20 * 20 = 400。刚开始（为第一时刻，此时还没有任何影像输入）所有粒子的位置遍布整个检测窗口。它们的概率是都是1 / 400。概率密度函数是一条直线，输出也都是1 / 400。（4）此时要预测下一时刻（这时影像开始输入）的概率密度函数怎么办？我们先让所有粒子随机走动，随机走动的算法，可由以下公式表示：譬如， 。系统噪声Wk是零均值的高斯白噪声，输入的是X(k-1)，表示前一时刻的粒子位置、速度值，输出是X(k)，表示随机走动后的位置、速度值。（5） 这里有个问题，以上公式的系统噪声Wk的值怎么求得呢？

12、（注：该Wk值不同于粒子权值的Wk值。）它是在粒子周围产生的随机偏差。（6）粒子随机走动到新位置后，我们的任务就是求得下一时刻的粒子概率密度函数：p(Xk | Dk)。用以下公式我们可以近似求得， （注：该Wk值不同于粒子权值的Wk值。）这公式怎么理解呢？Wk表示粒子的权值，刚开始都相等。我们假设它们都等于1。此时，计算所有粒子和Xk对应的矩阵的相似度加权和，加权和越大，说明粒子移动到该位置的概率越大。那Xk对应的矩阵是什么呢？它是以检测窗口任一点为中心的5*5矩阵。所以公式的意义是这样的：给定检测窗口的任意一点，计算所有粒子和该点对应5*5矩阵的相似度的加权和。加权和就是目标物体（5*5像素

13、矩阵点）移动到该位置的概率。为什么要用到Wk呢？主要是考虑到上一时刻的粒子和目标物体的相似度，相似度越大Wk越大，粒子移动这时刻的Xk位置的概率越大。所以用上一时刻的历史经验Wk乘于粒子和Xk的相似度更合乎贝叶斯概率的原理（详见贝叶斯概率相关资料），也更合乎实际。（7）既然知道目标物体移动到检测窗口任一点的概率，那p(Xk | Dk)即被求得。此时从p(Xk | Dk)中随机抽出400个粒子，重复（4）-（7）步骤。注意：抽出来的400个粒子权值高的占多数，所以不用进行重采样。因为权值高的容易被抽出来。但是重采样又是怎么回事？其实在实际的编程中并不会按照（1）-（7）那样进行，而是按照上面“第

14、二种理解”的方法进行。所以重采样不可避免。以上描述的只是数学理论，理论过程跟实际过程有差异。（8） 到此似乎还有问题，权值Wk一直不变的吗？肯定不是，在第7步同时要对粒子权值进行求解。 A、如果知道粒子的理论概率分布，则可以按照以下求得Wk值。请看以下公式，表示一个状态（k时刻）下一个粒子的权值。粒子实际的概率。粒子对应直方图和参考对象直方图的相似度越大，该值越大。粒子理论的概率。即重要性密度函数。如果粒子实际的概率越接近理想的概率，则的值越大。图（1）如图（1）粒子1的概率是0.9，粒子2的概率是0.1，粒子3的概率是0.1，粒子4的概率是0.3，粒子4的概率是0.4。假设这是理想的概率分布，由函数求得粒子概率。而用求得的实际的概率分布如下，粒子1的概率是0.68，粒子2的概率是0.09，粒子3的概率是0.09，粒子4的概率是0.29，粒子4的概率是0.39。