Particle Filter

粒子滤波算法是 SIR 算法的应用。推导粒子滤波只需要证明 \(\frac{\text{target distribution}}{\text{proposal distribution}} = \frac{bel(x_{t})}{p(x_t \mid u_t, x_{t-1}) bel(x_{t-1})} \propto p(z_t \mid x_t)\) 即可。

可以认为，粒子是下面状态序列的样本：
\[x_{0:t}^{[m]} = x_{0}^{[m]},x_{1}^{[m]}, \cdots, x_{t}^{[m]}\]

记 \(bel(x_{0:t}) = p(x_{0:t} \mid u_{1:t}, z_{1:t})\) ，如果我们证明了使用粒子滤波算法时 \(x_{0:t}^{[m]}\) 是 \(bel(x_{0:t})\) 的样本，那么使用同样算法时显然 \(x_{t}^{[m]}\) 会是 \(bel(x_{t})\) 的样本。

证明使用粒子滤波算法时 \(x_{0:t}^{[m]}\) 是 \(bel(x_{0:t})\) 的样本，那么对应的 target distribution 为 \(bel(x_{0:t})\) ，proposal distribution 为 \(p(x_t \mid u_t, x_{t-1}) bel(x_{0:t-1})\) 。

所以，我们可以通过证明 \(\frac{bel(x_{0:t})}{p(x_t \mid u_t, x_{t-1}) bel(x_{0:t-1})} \propto p(z_t \mid x_t)\) ，来间接证明 \(\frac{bel(x_{t})}{p(x_t \mid u_t, x_{t-1}) bel(x_{t-1})} \propto p(z_t \mid x_t)\) 。

\[\begin{aligned} bel(x_{0:t}) & = p(x_{0:t} \mid u_{1:t}, z_{1:t}) \\ & \stackrel{\text{Bayes}}{=} \frac{p(z_t \mid x_{0:t}, u_{1:t}, z_{1:t-1})p(x_{0:t} \mid u_{1:t}, z_{1:t-1})}{p(z_t \mid u_{1:t}, z_{1:t-1})} \\ & = \eta \, p(z_t \mid x_{0:t}, u_{1:t}, z_{1:t-1})p(x_{0:t} \mid u_{1:t}, z_{1:t-1}) \\ & \stackrel{\text{Markov}}{=} \eta \, p(z_t \mid x_{t})p(x_{0:t} \mid u_{1:t}, z_{1:t-1}) \\ & = \eta \, p(z_t \mid x_{t}) p(x_t \mid x_{0:t-1}, u_{1:t}, z_{1:t-1}) p(x_{0:t-1} \mid u_{1:t}, z_{1:t-1}) \\ & \stackrel{\text{Markov}}{=} \eta \, p(z_t \mid x_{t}) p(x_t \mid x_{t-1}, u_{t}) p(x_{0:t-1} \mid u_{1:t-1}, z_{1:t-1}) \\ \end{aligned}\]

说明：上面的推荐过程和贝叶斯滤波中后验概率的推导基本上是一样的，只是贝叶斯滤波的 \(x_t\) 变成了这里的 \(x_{0:t}\) ，就是这个不同，使得贝叶斯估计里需要积分，而这里后验概率的分解形式却没有积分。

利用前面的结论，继续推导：
\[\begin{aligned} \frac{\text{target distribution}}{\text{proposal distribution}} & = \frac{bel(x_{0:t})}{p(x_t \mid u_t, x_{t-1}) bel(x_{0:t-1})} \\ &= \frac{\eta \, p(z_t \mid x_{t}) p(x_t \mid x_{t-1}, u_{t}) p(x_{0:t-1} \mid u_{1:t-1}, z_{1:t-1})}{p(x_t \mid u_t, x_{t-1}) p(x_{0:t-1} \mid u_{1:t-1}, z_{1:t-1})} \\ & = \eta \, p(z_t \mid x_{t}) \\ & \propto p(z_t \mid x_{t}) \\ \end{aligned}\]

证毕。

参考：Probabilistic Robotics, by Sebastian Thrun, 4.2.3 Mathematical Derivation of the PF

粒子滤波中，重抽样过程后，权重大的粒子会重复多个，而权重小的粒子很可能消失。这称为 Particle Deprivation Problem。
其解决办法是：A popular solution to this problem is to add a small number of randomly generated particles into the set after each resampling process.

粒子滤波还有其它不足，可参考：Probabilistic Robotics, by Sebastian Thrun, 4.2.4 Properties of the Particle Filter

粒子滤波又叫 Condensation algorithm。

OpenCV 中实现了 Condensation 算法。参考：Learning OpenCV, Chapter 10 Tracking and Motion. The Condensation Algorithm