毕设准备做一些目标跟踪检测相关的事情，要点是使用概率计算方法实现，因此打算先研究研究常见的跟踪检测算法，然后看看哪些算法适合概率计算方法。
跟踪方法的分类
跟踪方法一般分为两类，分别是：top-down，bottom-up。
top-down，这种方法根据模型生成目标在当前帧的位置的假设，然后通过当前帧图像去验证这种假设。粒子滤波就属于这类方法。
bottom-up，这种方法把当前帧进行分割，然后尝试搜索物体的位置。Mean-shift算法就属于这类方法。
粒子滤波器
粒子滤波器是一种SIS(Sequencial Importance Sampling)方法。具体作用就是在Markov Chain上进行推导和预测，plusikid大神的这篇漫谈 HMM：Kalman/Particle Filtering对Particle Filter进行了详细的讲解和推导。
我这里用通俗的话来讲一讲粒子滤波器是干嘛用的。就拿漫谈 HMM：Forward-Backward Algorithm中的火星车来举例。
首先第一步，火星车的位置（隐藏状态）为$S_0=(x,y)$，粒子滤波器根据初始状态生成一大堆的particles（每一个权重是状态和权重组成的二元组），$$S\_samples=(s_0^{(0)},s_0^{(1)}…s_0^{(n)}), w=(w_0^{(0)},w_0^{(1)}…w_0^{(n)})$$怎么生成初始particles呢？在第一步，我们可以认为当前的隐藏状态已知，因此$s_i^{(0)}=S_0$，所有粒子的权重相同，并做归一化操作。
第二步，这时模型告诉我们，火星车向北移动了30m，用数学公式表达就是$$S=S+(0,-30)$$但是由于各种原因（火星上起风了，机器精度，火星车摔了一跤；(），因此模型中还需要加上噪声项$$S=S+(0,-30)+noise$$
在这一步中，我们把所有的particle都作这样的操作，让它们向北移动30m，$$s_1^{(i)}=s_1^{(i)}+(0,-30)+noise$$由于噪声的影响，每个粒子最终的位置都不太相同。
第三步，这时观测（GPS）告诉我们，火星车的实际位置在xxx。当然这个观测结果也并不等于火星车的实际位置，因为GPS也存在误差。但是信息越多，我们综合得到的结果肯定越准确。在这一步。就使用观测结果更新particles的权重。particle给出的位置与观测结果越相似，该particle的权重也越大，火星车越可能出现在这些大权重的particle给出的位置上。
第四部，使用particles估算火星车的位置$S=w*S\_samples$，即使用particles作加权平均。
第五步，重采样，由于某些粒子的权重过小，需要重采样，multiply大权重particle，abandon掉小权重particle。
然后重复第二步。
粒子滤波器与目标跟踪
那么粒子滤波器如何运用在目标跟踪上面呢？从上面粒子滤波器的步骤可以看出，粒子滤波器是在HMM上作推导，而HMM需要：
- 隐藏状态$x$与观察值$y$的定义
- 转移概率，即当前状态到下一个状态的转移概率函数$p(x_{t+1}|x_t)$
- 观测值与隐状态的条件概率，即$p(y_t|x_t)$
对于目标跟踪而言，隐藏状态自然是目标的位置、大小等参数。而观察值一般取目标的特征，常用的特征有Color Histogram，Histogram of oriented gradient等。
隐藏状态是目标位置，那么转移概率描述的就是目标当前帧到下一帧的位置变化。一般使用Auto-regression，$$x_{t+1}=A*x+w$$
而权重更新，一般取当前particle给出的位置上的图像的特征与目标特征模型之间的距离。这个也很好理解，当前particle给出的位置越靠近目标，则特征距离越短，该particle权重越大，反之亦然。
然后就套用上面介绍的particle filter的步骤，就可以实现目标跟踪了。
更为具体的实现步骤可以参考论文An adaptive color-based particle filter
Unscented Particle Filter
Particle Filter有一个缺陷。在第二步中，我们实际上是从转移概率$p(x_{t+1}|x_t)$中采样得到新的particles，而这样得到的particle没用使用到观察得到的信息，因此可能存在较多权重很小的particle，这些particle上的运算都浪费了。
那么能不能从$p(x_{t+1}|xt,y{t+1})$中进行采样呢？答案是可以的，unscented particle filter首先使用unscented kalman filter估计$p(x_{t+1}|xt,y{t+1})$，然后从估计的$p(x_{t+1}|xt,y{t+1})$中采样得到新的particles。这些particles的权重分布应该较为均匀，因此整个算法的效果就会好很多。
至于为什么不直接用unscented kalman filter，那是因为kalman filter不能处理非线性的转移函数，正因为此，才需要particle filter嘛。
unscented transform是一种估计非线性函数矩的方法，比如$E(f(x))$，$f(x)$是非线性函数。而且unscented transform估计一、二阶矩都是准确的。具体怎么使用unscented transform以及怎么使用unscented transform实现unscented kalman filter还没看懂，还要再努力啦。