2011年4月第4期电子测试ELECTRONIC TESTApr.2011No.4一种改进的粒子滤波重采样算法研究金玉柱，李善姬（延边大学工学院，吉林 延吉 133002）摘要：粒子滤波是基于递推的蒙特卡罗模拟方法的总称，可用于任意非线性，非高斯随机系统的状态估计。

为了减轻退化现象，引入重采样过程，但重采样过程算法复杂，计算量大，不利于硬件实现，并且会削弱粒子的多样性，从而导致滤波性能下降。

提出了一种将局部重采样和优化组合算法结合的重采样算法。

将粒子按权值大小分类，小权值的粒子抛弃，大权值的粒子进行复制，将复制的粒子和抛弃的粒子线性组合产生新的粒子，增加了粒子多样性并且只对大权值粒子进行运算，故降低了计算量利于实时系统的硬件实现。

仿真结果证明了该算法的有效性。

关键字：粒子滤波; 局部重采样; 优化组合中图分类号： TP391 文献标识码：AResearch of improved particle filter resampling algorithmJin Yuzhu, Li Shanji(College of Engineering, Yanbian University, Yanji 133002, China)Abstract: Particle filtering is a sequential Monte Carlo simulation algorithm. It can be used to estimate the state of any nonlinear, non-Gaussian system. In order to reduce the degeneracy, the resampling algorithm is adopted. But the resampling process has complex algorithm architecture, which have restricted its implementation in real-time system. Resampling process also leads to the loss of diversity of particles, and the loss makes filter’s performance worse. A new algorithm-partial resampling combined with optimizing combination resampling method is proposed. Assort the particles by their weights, the particles which have low weights are abandoned and the particles which have high weights are reproduced, and generate new particles by combining the reproduced particles and abandoned particles. This new method partly overcomes the loss of diversity and because it simply operates to the high weights particle so its calculation is simplified. And it is propitious to implement by hardware. The simulation results prove the effectiveness of the proposed method.Keywords : particle filtering; partial resampling; optimizing combination0 引言粒子滤波器，又称序贯蒙特卡罗方法。

可以有效地处理非线性、非高斯滤波问题，广泛地应用在机动目标跟踪、信号传输与压缩、金融领域数据分析、图像处理、故障诊断等领域。

所谓粒子滤波就是贝叶斯估计基于抽样理论的一种近似算法，通过非参数化的蒙特卡罗模拟方法来实现递推贝叶斯滤波，即通过一组动态状态空间上按贝叶斯准则进行更新的随机加权的样本或粒子，对未知状态的后验概率密度进行估计，其中这些粒子通过对后验密度序贯重要抽样得到，并分别对应于一组权值。

以样本均值代替积分运算，当样本容量很大时，这种蒙特卡罗描述就等价于真实的后验概率密度函数[1]。

基本的PF 算法中最重要的3个步骤是：重要性采样、权值更新以及重采样。

重要性采样步骤就是选取重要性函数，通常选择k 时刻的后验概率密度函数时为最优估计，但是最优估计很难实现，一般取后验概率密度的近似函数作为重要性函数，从中按照一定的原则选取n 个随机样本点。

逐点计算每个样本点的权值。

这种算法经过多次迭代后会产生退化现象，许多粒子的权重变得非常小，只有少数粒子具有较大权值，为了解决这个问题引入了重采样过程。

重采样算法的主要思想是：抛弃那些权值小的粒子，复制那些权值大的粒子。

这种算法很好地解决了粒子匮乏现象。

但是同时又产生了粒子多样性的丧失问题。

即直接抛弃权值小的粒子，只多次复制权值大的粒子有可能会使滤波发散[2]。

本文提出了一种新的重采样算法，将局部重采样算法和权值优化组合算法相结合。

有效地降低了算法的复杂度并且解决了粒子多样性丧失问题。

1 粒子滤波算法粒子滤波算法的核心思想就是利用一系列随机样本的加权和表示所需的后验概率密度，得到状态的估计值。

当样本点数增至无穷大时，就可无偏的估计出后验概率密度，达到最优估计。

粒子滤波算法中，用()(){}0:1,Ni i kki xw =表示系统后验概率密度函数()0:0:|k k p x z 的样本集合，其中{}()0:,1,2,...,i kxi N =是粒子集合，N 为粒子数，(){},1,2,...,i kw i N=为各个粒子相应的权值，且满足()11N i ki w ==∑。

粒子滤波算法中重要性函数()0:1:|,k k k q x x y 的设计是一个关键问题，它经常被近似以简化采样。

当重要性函数为后验概率密度函数的情况下，达到最优估计。

但最优估计很难实现，所以经常采样次优算法，令重要性函数等于先验概率密度即：()()11|,|k k k k k q x x y p x x −−=，此时由下式递归更新权值[3]。

()1|k k k k w w p y x −= （1）粒子滤波算法在递归更新权值的过程中，会产生一个问题就是许多粒子的权值会变得非常小，而少数粒子的权值变得较大。

为了解决这个问题引入重采样步骤，通过一个有效地采样尺度Neff 为：()211eff Ni ki N w ==∑， （2）当Neff 下降到一个门限值Nr 时就对粒子进行重采样，把那些权值小的粒子删除，复制那些权值较大的粒子。

重采样过程就是对现有的N 个样本进行重采样，产生新的N 个样本构成对后验概率分布的新的近似。

粒子滤波算法的具体实现步骤如下：Step0：初始化k=0 产生粒子集()1Nik i x =，定义每个粒子初始的权值为1N −。

Step1：重要性采样和权值计算k=1 从重要性函数 采样N 个粒子，通过式（1）计算每个粒子的归一化权值。

Step2：重采样通过有效采样尺度Neff，利用（2）式判别是否需要重采样。

如果需要重采样则采样重采样算法根据根据归一化权值，从集合()1Ni k i x =中用权值较大的粒子代替权值小的粒子，如果不需要重采样则转到Step3。

Step3：输出输出一组粒子()(){}1,N i i kki xw =，利用下式：()()1ˆNi i k ki x w x ==∑ （3）得到当前时间步的后验均值估计。

Step4：时间更新令1kk →+，当下一测量值到来时转到Step1。

2 重采样步骤的改进传统的重采样算法对所有的粒子进行重采样，算法复杂，不能满足算法执行时间的要求。

并且完全抛弃了权值小的粒子，所以粒子多样性的损失是不可避免的。

本文的重采样算法是为了减少计算的复杂度及处理时间并且充分利用被抛弃的权值小的粒子的基础上提出来的。

将局部重采样和权值优化组合算法结合，得到一个算法复杂度低并且没有重复的粒子的算法。

主要思想是对粒子按权值大小()()11|,|k k k k k qx x y p x x −−=分四类[4]，分为大权值粒子、中等权值粒子、小权值粒子以及可抛弃粒子。

大权值粒子重采样之后被复制并与小权值粒子线性组合[5]，中等权值粒子重采样后权值不变，小权值粒子被存入抛弃组待与大权值粒子线性组合产生新的粒子，权值过小的可抛弃粒子完全抛弃。

线性组合方式如下[6]：()n s a s x x KL x x =+− （4）其中，n x 是线性组合后产生的新采样点；s x 是被重复选取的大权值采样点；a x 是存入抛弃组的小权值采样点；K 为步长系数，调节K 的目的是为了消除()a s x x −的欧氏距离带来的影响；L 为()a s x x −方向的合适步长。

若产生的新采样点的权值比原采样点的权值小，L 减半并重新产生新的采样点。

设N 为采样点个数，m 为采样空间的维数，w 为任一采样点邻域空间内采样点的分布概率，则L 为：（5）本文所提出的重采样算法具体实现如下：首先定义初值T h 、T m 、T l 。

且T h >T m >T l 。

并对粒子按权值大小进行划分。

while i ≤ N if 当前点权值≥T m 直接接受当前采样点。

if 当前点权值≥T h复制当前采样点，并按（4）式与抛弃组的采样点线性组合产生新点。

计算新点权值，若该权值大于当前点权值则保留否则重新进行线性组合L 减半。

end ifelse if T m > 当前点权值 > T l抛弃当前点，存入抛弃组以备线性组合。

else 当前点<T l完全抛弃当前点，不存入抛弃组。

end if end while本重采样算法中转移到s x 的权值通过线性组合，重新分配给了抛弃组中的粒子，通过选取合适的K 值，总可以使重采样后的近似概率分布比单纯的局部重采样算法更加接近重采样前的概率分布。

采用按权值大小对粒子分类的方法，只对权值大的粒子进行复制运算，其他粒子或者直接接受或者抛弃粒子，不必对所有粒子进行运算，故有效地降低了算法的复杂度，利于实时系统的硬件实现。

采用优化组合的办法增加了粒子的多样性，重采样后没有重复的粒子，选取合适的K 值后可有效提高PF 算法的精度。