基于小生境遗传算法的粒子滤波算法

张 航，李梦丽，杨清波

1.中南大学 信息科学与工程学院，长沙 410083

2.中南大学 信息科学与工程学院 控制工程系，长沙 410083

基于小生境遗传算法的粒子滤波算法

张 航1，李梦丽2，杨清波2

1.中南大学 信息科学与工程学院，长沙 410083

2.中南大学 信息科学与工程学院 控制工程系，长沙 410083

1 引言

粒子滤波（Particle Filter，PF）[1]是一种基于Monte Carlo仿真的递推贝叶斯估计方法。因具有适用于非线性及非高斯噪声环境等优点，被广泛应用于目标跟踪、图像处理和故障检测[2-3]等诸多领域，其基本原理是根据系统状态的一组带有权值的随机样本来表示实际问题所需要的后验概率密度函数，这些样本被形象地称为“粒子”。粒子滤波最常见的问题是粒子的退化现象，对粒子进行重采样是解决粒子退化问题的一种重要方法，重采样的目的就是将权值小的粒子用权值大的粒子分解代替。当前存在多种重采样算法，如系统重采样（System Resampling，SR）[4]，残差重采样（Residual Resampling，RR）[5]，多项式重采样（Multinomial Resampling，MR）[6]等。所用的重采样过程虽然解决了粒子的退化问题，但也带来了粒子贫乏的问题。将遗传算法引入粒子重采样中，能有效增加粒子多样性，但基本遗传算法常在各个个体未达到最优解之前就收敛于一个局部最优点，从而导致样本趋于一致，即产生“早熟”现象，不能保证在粒子滤波重采样上计算效率和可靠性的要求。

为了克服这些不足，本文引入了小生境遗传机理来解决粒子滤波跟踪算法中的粒子多样性退化的问题，这种算法提高了粒子的多样性，相对于普通粒子滤波，基于小生境遗传重采样的粒子滤波仅需要较少的粒子就可以实现状态的精确估计。

2 基本原理

2.1 粒子滤波原理

若已知状态的初始概率密度函数为p(x0|z0)=p(x0)，则预测方程和更新方程为：

其中离散状态序列x1:k={x1，x2，…，xk}具有马尔可夫特性，离散测量序列zk={z1，z2，…，zk}为独立测量序列，且与各状态独立。式（1）（2）构成了状态xk的最优贝叶斯估计，但其解析解只在特定高斯条件或状态空间有限时成立。

为了计算式（1）（2），引入序贯重要性采样算法（SIS）。其核心思想是用一组带权值的随机粒子来表示并计算所需的后验概率密度，人们从建议分布q(xk|xk-1，z1:k)中采样得到一组粒子，并通过加权和的形式逼近状态后验概率密度。粒子权值计算公式为：

则后验概率密度可以近似为：

其中是归一化权值，，N表示采样粒子数目。根据大数定理，当N足够大时，可以证明式（4）就是真实的后验概率密度，则得到状态的输出为：

粒子滤波重采样的思想是通过对样本重新采样，繁殖重要性权值高的粒子，淘汰权值低的粒子，从而抑制退化，如图1所示。

图1 粒子滤波重采样示意图

2.2 Mean Shift算法原理

Mean Shift算法是一种利用数据驱动的无参估计算法，又称为核密度估计算法，主要通过均值偏移向量寻找到后验概率局部最优[7]。算法如下：

（1）确定初始帧的目标模型：

其中，xi表示目标模型的像素位置向量；x0表示目标模型中心像素位置向量，u是经过核函数加权量化以后的特征向量；h是跟踪窗口带宽；δ是冲击响应函数；C是归一化常量。

（2）确定当前帧的候选目标模型：

其中，y0是当前帧搜索窗口的中心像素位置坐标。（3）利用Mean Shift计算Bhattacharyya距离：

进而求得Mean Shift向量m(y)：

当‖m(y)‖＜ε时结束，y1就是目标的准确位置；否则，令y0←y1，转步骤（2）。

3 改进的粒子滤波算法

本文采用小生境概念的遗传算法[8]，其基本思想是：通过两两比较种群中个体之间的海明距离，当这个距离在指定的距离L之内，再比较两者之间的适应度大小，并对其中适应度较小的个体施加一个较强的罚函数，极大降低其适应度，这样对于预先指定的某一距离L之内的两个个体，其中较差的个体经处理后其适应度变得更差，它在后面的进化过程中被淘汰的概率就极大。也就是说，在距离L之内将只存在一个优良个体，从而既维护了群体的多样性，又使得各个个体之间保持一定的距离，并使得个体能够在整个约束空间分散开来，从而在克服早熟收敛方面都取得良好的效果。

本文提出基于小生境遗传算法的粒子滤波重采样算法。在跟踪的过程中，粒子滤波与Mean Shift算法同步融合，首先利用粒子滤波的建议分布函数采样N个粒子；其次利用Mean Shift搜索目标可能的位置，并在该位置附近采样Μ个粒子。在重采样部分引入小生境遗传算法处理这N+Μ个粒子。改进算法的执行过程如下：

图2 两种算法在头部快速移动下的对比图

（1）初始化。设定粒子滤波建议分布函数采样的粒子个数为N，Mean Shift采样的粒子个数为Μ。从先验分布p(x0)中采集粒子样本，

（2）粒子序列重要性采样。Fori=1，2，…，N，从建议分布中采样得到新的粒子，计算粒子的权值，并归一化粒子的权值。

（3）均值偏移。利用Mean Shift算法预测得到目标位置，并在该位置附近随机产生Μ个粒子，并计算各个粒子的权值。

（4）状态输出。由采样得到的N个粒子根据式（5）得到K时刻的目标状态的后验概率估计。

①将粒子滤波采样的N个粒子和Mean Shift产生的Μ个粒子组成粒子集，并设为初始群体，适应度为个体相对应的权值

②根据各个个体的适应度对其进行降序排列，记忆前N个个体。

③对初始群体进行遗传选择、交叉、变异操作得到子代种群。

④小生境限制竞争选择操作，将通过遗传操作的子代种群与记忆的父代种群合并，得到2N+Μ个粒子，在合并后的种群里，对相邻较近粒子中适应度低的处以罚函数加快其淘汰，使粒子更快地向高适应度方向移动。

⑤通过以上操作后，依据这2N+Μ个个体的新适应度对个体进行降序排序，记忆前N个个体，这就是重采样的结果。

⑥若种群适应度达到设定门限，则输出计算结果，否则转到步骤②。

4 实验结果分析

为了证明本文改进算法在目标跟踪方面的有效性，在一台P4 2.4 GHz，2 GB内存的计算机上进行仿真，在VC++6.0平台上，对下面两段视频作对比实验，把标准的粒子滤波算法和本文改进的算法进行比较。跟踪的结果选用矩形框进行表示。

第一个视频序列是基于头部的快速左右移动的实验。视频尺寸为128×96，两种算法的粒子数均为50，从图2（a）的结果可以看出，标准粒子滤波跟踪算法在第25帧和第43帧出现了目标丢失的现象，而从图2（b）可知本文的算法能较好地跟踪头部。图3显示了第一个视频序列水平方向位置估计误差曲线，标准粒子滤波（PF）误差较大，而本文的改进方法（NPF）误差则相对较小。

图3 水平方向位置估计误差

第二个视频序列是关于遮挡情况下的跟踪实验，视频尺寸为128×96，两种算法的粒子数均为80，脸受到了手的遮挡，而且手的颜色与脸颜色相近，这些都给跟踪带来了干扰，但可以看出，本文改进的算法依旧具有良好的跟踪性能，优于标准的粒子滤波算法，如图4所示。

两种方法的时间复杂度，通过计算每帧图像处理时间给出。图5所示为视频序列1和视频序列2的跟踪过程中本文改进算法在每一帧的耗时，可以看出视频序列1的平均耗时为38 ms，视频序列2的平均耗时为43 ms。

图4 两种算法在头部遮挡情况下的对比图

图5 时间统计

从表1中可以看出，本文的改进算法（NPF）相对于标准粒子滤波算法（PF）计算时间有所增加，因为本文的改进算法增加了算法复杂度，但由此增加的时间开销在接受范围之内，兼顾了跟踪的实时性，且跟踪更准确，可以得出结论：改进算法从总体上明显提高了系统的性能。

表1 两种跟踪方法时间对比 ms

5 总结

粒子滤波能较好地处理非线性、非高斯系统的状态估计问题，但是，标准粒子滤波算法重采样过程中的粒子多样性减弱造成了滤波精度下降。本文针对此问题，利用小生境遗传算法思想，给出了一种有效的重采样粒子滤波跟踪算法。实验证明，相对标准的粒子滤波算法，本文所给出的算法有一定的改善。

[1]Gordon N，Salmond D J，Smith A F M.Novel approach to nonlinear/non-Gaussian Bayesian state estimation[J].IEEE Proc of Radar and Signal Processing，1993，140（2）：107-113.

[2]Isaac A，Willett P，Bar-Shalom Y.Quickest detection and tracking of spawning targets using monopulse radar channel signals[J]. IEEE Trans on Signal Processing，2008，56（3）：1302-1308.

[3]Angelova D，Mihaylova L.Extended object tracking using Monte Carlo methods[J].IEEE Trans on Signal Processing，2008，56（2）.

[4]Bolic M，Djuric P，Hong S.Resampling algorithms for particle filters：a computational complexity perspective[J].EURASIP Journal on Applied Signal Processing，2004，2004：2267-2277.

[5]Bolic M，Djuric P M，Sangjin H.Resampling algorithms and architectures for distributed particle filters[C]//IEEE Transactions on Signal Processing，2005.

[6]Hol J D.Resampling in particle filters[R].Linkoping University，2004.

[7]Yimaz A.Object tracking by asymmetric kernel mean shift with automatic scale and orientation selection[C]//IEEE Conference on Computer Vision and Pattern Recognition，2007：1-6.

[8]Lee C G，Cho D H，Jung H K.Niching genetic algorithm with restricted competition selection for multimodal function optimization[J].IEEE Trans on Magn，1999，34（1）：1722-1755.

ZHANG Hang1,LI Mengli2,YANG Qingbo2

1.School of Information Science and Engineering,Central South University,Changsha 410083,China
2.Department of Control Engineering,School of Information Science and Engineering,Central South University,Changsha 410083,China

Resampling is a critical operation to solve degeneracy problem with particle filters generally.The basic idea of resampling is to discard particles which have small weights and concentrate on particles with large weights.But resampling often introduces sample impoverishment problem,especially the sample is limited under the condition,even causes the filter to disperse.This paper proposes improved particle filter algorithm.Mean Shift integrates with particle filter,and then the niching genetic algorithm is used in resampling in order to improve the variety of particles and remove the degeneracy phenomenon.The simulation results prove the proposed algorithm reduces the tracking error,and has better precision.

particle filter;Mean Shift;niching genetic algorithm;resampling

重采样是解决粒子滤波退化问题的主要方法，重采样的基本思想是采取复制保留权值较高的粒子，删除权值较低的粒子，而这导致了粒子多样性的减弱，特别是在样本受限条件下，甚至导致滤波发散。针对上述问题，提出改进的粒子滤波算法，将Mean Shift与粒子滤波融合，在重采样部分引入小生境遗传算法，提高粒子的多样性，避免粒子退化。实验表明，改进后的算法状态估计精度更高，效果更好。

粒子滤波；Mean Shift；小生境遗传算法；重采样

A

TP391

10.3778/j.issn.1002-8331.1112-0419

ZHANG Hang,LI Mengli,YANG Qingbo.Particle filter algorithm based on niching genetic algorithm.Computer Engineering and Applications,2013,49（18）：191-194.

国家自然科学基金（No.50808025）；2010年中南大学硕士研究生学位论文创新资助项目（No.2010ssxt209）。

张航（1967—），男，博士，副教授；李梦丽（1987—），女，硕士研究生，主要研究方向为图像处理、模式识别；杨清波（1986—），男，硕士研究生。E-mail：chuichui77@126.com

2011-12-21

2012-02-10

1002-8331（2013）18-0191-04

CNKI出版日期：2012-05-28 http://www.cnki.net/kcms/detail/11.2127.TP.20120528.1612.001.html