基于分类采样的目标跟踪方法

周飞菲

(郑州升达经贸管理学院，河南 郑州 451191)

0 引 言

粒子滤波在(particle filter, PF)目标跟踪[1]、导航定位[2]等领域具有广泛应用，其中，重采样技术是克服粒子权值退化的重要手段，目前比较经典的有有残差重采样(residual resampling, RR)[2]、多项式重采样(multinomial resampling, MR)[3]和系统重采样(systematic resampling, SR)[4]。虽实现的手段不同，但采样的思想相同，都是通过丢弃小权值粒子，对大权值粒子重新分配权值获取新的粒子集合。在一定程度上缓解了样本退化的问题，但随着时间的延长，大权值粒子多次被复制，粒子集的多样性丧失。经过若干次迭代以后，用于估计的粒子集合只是部分有限状态的子代粒子，严重丧失了状态的遍历性能，特别是在系统状态分布具有严重拖尾现象的时候，迭代时间越长、精度越差[5]。随后出现了两类改进方法：一类是基于“优选建议分布函数”，通过滤波技术将最新的观测信息融入到建议分布函数中，增强当前时刻观测信息对粒子多样性的修正作用，例如，常用的扩展卡尔曼滤波(EKF)[6]、无迹卡尔曼滤波(UKF)[7]以及容积卡尔曼滤波(CKF)[8]等，通过该类滤波技术实现建议分布函数的实时估计。虽然这类基于建议分布函优化的方法一定程度上增强了最新观测信息对粒子多样性的保持作用，但是改善的精度严重依赖观测信息的估计方法，没有改善重采样的实现手段，无法避免权值衰退的产生。第二类是基于“优化重采样策略”的思想。通过智能寻优的方法改变重采样手段。Grisetti利用网格分割的思想权重的重新分配，提出了确定性重采样方法[9]，由于网格整体风格的计算量过大，限制了该技术的进一步发展。Cheng通过设置权重阈值，将权值粒子集分为两个采样集合，保留大权值粒子，并结合小权值进行分层采样[10]，每一次采样后都会摒弃大量的小权值粒子，降低了多样性。在此基础上，Zhang提出采用遗传算法对剩余粒子进行优化分析，针对大小权值粒子采取不同的遗传变异修正处理方式实现了遗传算法重采样方法(genetic algorithm resampling，GAR)[11]，提升了粒子滤波在机动目标跟踪中的滤波精度，但是每一次重采样都要对粒子集合的全体粒子操作，增加了算法本身的计算时间。

针对权值退化及样本贫化问题，本文提出了一种分类进化的重采样(classification evolution resampling，CER)粒子滤波方法。首先，通过重采样阈值的判断，对满足重采样条件的建议分布函数进行滤波估计，保证最新观测信息对粒子的修正作用；接着，对重采样粒子集合进行种群划分，依据权值大小聚类为小权值种群、保留种群和大权值裂变种群三类。在重采样过程中，首先对大权值粒子进行裂变，然后采用差分进化方法同小权值种群进行优化，通过突变、交叉、选择产生新粒子种群，避免了对历史小权值信息的丢弃。最后，针对非线性系统模型进行了详细的仿真分析和指标对比说明。

1 分类进化重采样原理分析

1.1 基本粒子滤波

非线性系统方程可以表示为[12]

(1)

其中，xt∈Rn,yt∈Rm为状态向量和观测向量，f(·)和h(·)是已知的非线性传递函数，ωt和vt是过程和量测噪声，为不相关的零均值高斯白噪声过程，协方差为Q、R，滤波的目的是在给定观测信息p(xt|y1:t)的情况下计算状态的后验概率密度。随着观测信息的不断更新，可以将系统状态的后验概率密度(PDF)表示为

(2)

条件概率密度p(yt|y1:t-1)为

(3)

PF基于蒙特卡洛仿真的思想采用权重粒子加和的方式近似计算积分，表示为

(4)

权重赋值：计算采样粒子的权值大小

(5)

重采样：随着迭代时间的增加，粒子权重的方差趋于零，出现“粒子退化”问题，需要进行重采样。文献[14]定义了有效粒子数Neff，当Neff低于阈值情况进行重采样步骤

(6)

1.2 分类进化重采样实现

为了在采样粒子中融入最新观测信息的修正作用，采用UKF方法对建议分布函数进行滤波优化。与传统方法不同的是，不是对全部的采样粒子都进行UKF滤波，而是在判断需要进行重采样步骤以后，在进行重采样的同时，进行建议分布函数的滤波估计优化。判断阈值的设置为Neff

1.3 粒子分类

为避免对所有粒子进行重采样，考虑对粒子集合进行分块处理。根据聚类的思想，基于粒子权值大小将整个粒子集合划分为小权值种群、保留种群和大权值裂变种群三类，其中初始权值阈值设置为ωthrmax和ωthrmin，其中粒子权值低于ωthrmin的粒子被划分为小权值种群需要进行重采样，权值大于ωthrmax的粒子被划分为大权值裂变种群，需要和小权值种群进行重组，获取新一代粒子。权值介于两者之间的定义为保留种群，在新一代粒子更新中保持不变。具体的分类原理如式(7)。图1展示了具体的分类过程。

(7)

图1 权值粒子集种群分类框图

从图1中可以清晰地看出三类粒子的具体划分方法。其中，第一类粒子的个数为N-P-K，第二类粒子的个数为K，第三类大权值粒子的裂变个数主要取决于粒子的权值，其具体的计算方法为

(8)

分解后的粒子权值计算为

(9)

分解后的粒子满足式(10)特性

(10)

(11)

分解后的粒子分布为高斯分布

(12)

(13)

1.4 差分进化重采样

(14)

(15)

(16)

(17)

(18)

新的种群通过突变、交叉和选择进行优化，直到达到各个种群的最大数目，获取最优的拟合值以后，迭代终止。

2 计算机仿真分析

为分析所提方法的性能，将本文提出的分类进化重采样算法(CER)与RR、MR、SR以及文献[11]提出的GAR方法进行了对比分析。仿真中采用式(19)所示的单变量增长模型进行仿真分析，该模型具有较强的非线性且噪声满足高斯噪声特性[15]。

(19)

2.1 评价指标

为定量评价不同采样方法的性能指标，给出了均方根误差(RMSE)以及RMSE的均值MeRMSE和方差VarRMSE，具体计算表达式为

(20)

(21)

2.2 仿真结果分析

实验一：粒子样本空间分布多样性分析。

通常用有效粒子数Neff度量粒子滤波算法的退化程度,其定义如式(6)所示。其中，Neff的大小与退化程度成反比关系。在采样粒子数N=100的情况下，分别对几种重采样方法进行了100次的独立运行，并取两种算法的Neff平均值来验证GFA-PF算法确实能改善粒子滤波算法中的粒子退化问题。有效粒子数Neff实验结果如表1所示。

表1 不同迭代次数的由效粒子数

从表1中可以看出，本文方法的平均有效粒子数保持了最大值，因此，本文方法能够很地解决粒子退化问题。经过重采样之后，PF算法虽然可以在一定程度上避免粒子退化问题,但是却带来了粒子贫化问题。为了度量本文方法在迭代100次以后的粒子样本分布情况，图2中绘制了由图2可以看出，图2(a)粒子分布均匀，多样性丰富，而图2(b)中的粒子出现了明显的聚集现象，单一性强，验证了GFA-PF算法在解决粒子退化问题的同时还能保证粒子的多样性,解决粒子贫化问题.

实验二：固定仿真周期T=50，分析不同采样粒子数情况下的估计效果。

为分析不同采样方法的精确性，首先对固定仿真周期、不同采样粒子数情况下的估计精度进行了分析。图2、图3和图4给出了在粒子采样数分别为300、100和20情况下的状态估计结果，EE曲线以及RMSE曲线。可以看出，随着粒子数的减少，传统的重采样方法估计精度较低，主要因为传统方法只是考虑了对粒子的权值进行重新优化分配，没有考虑观测信息的修正作用，同时舍弃了大量的小权值粒子导致。从图中可以明显看出，传统的重采样方法中RR方法的精度最低，SR的采样精度最好，原因是因为RR仅考虑了有区别粒子的采样，随着粒子遍历性能的降低，父代粒子越来越少，导致估计精度越来越差。在粒子数N=300的情况下，GAR和本文方法都保持了较好的跟踪精度，主要原因是GAR对小权值粒子进行了优化遗传重组，有效增加了粒子的多样性。但是随着粒子数的减少，GAR方法的精度明显降低，主要缺少最新观测信息的修正作用，产生了估计的累积误差效应。在粒子数N=20的情况下，本文方法的估计精度明显优于其他采样方法，并且其跟踪精度和粒子数N=100基本相近。根据本文方法的这一特性，可以明显改善粒子滤波的计算复杂度和滤波精度间的矛盾，提升高精度应用的实时性。

图2 N=300时估计精度分析

图3 N=100时估计精度分析

图4 N=20估计精度分析

实验三：固定采样粒子个数N=100，分析不同仿真周期情况下的估计效果。

为分析不同采样方法的稳定性，针对给定采样粒子数、不同仿真周期情况下的估计精度进行了仿真分析。仿真中，设置采样粒子数N=100，仿真周期T分别为50 s、100 s和500 s，并给出了100步迭代的RMSE均值MeRMSE和方差VarRMSE，具体结果如表1和表2所示。

表1 N=100时的MeRMSE

表2 N=100时的VarRMSE

从表中可以看出，随着仿真周期的增加，五种方法的估计精度都在降低，其中，RR方法的降低幅度较大，本文方法和GAR方法表现的相对平稳，在50s到500s的变化过程中，GAR方法的MeRMSE增加了0.5952，而本文方法增加了0.4008。由表2可以看出，GAR的VarRMSE波动范围为0.0977，而本文方法的波动范围为0.065。因此，本文方法不仅具有更好的估计精度，同时具有较好的稳定性。

实验四：计算复杂度分析。

计算的复杂度主要取决于采样、重采样和权值计算三个阶段。在DE中迭代数目k和粒子数目M决定着本文方法的复杂度，由于进行了粒子分类处理，需要处理的粒子不会超过全部粒子的2/3。该部分基于Matlab2015软件，在Intel Core5Duo@4GHzPC上进行了计算复杂度分析。仿真中仍然采用式(19)给定的模型，在相同参数设置情况下进行150次迭代估计。对不同采样粒子数情况下的计算复杂度进行了对比分析，结果如表3所示。可以看出，随着粒子数的增多，五种重采样方法的时间都呈递增趋势，其中，MR、GAR和CER的采样时间接近，说明本文建议分布函数的优化和粒子分类进化重采样步骤实现了计算复杂度的这种，在相同采样粒子个数情况下，计算复杂性并没有增加。

表3 计算时间消耗比较

3 结 语

针对粒子滤波方法存在的“粒子退化”及“样本贫化”问题，本文针对“重采样”的具体实现方法进行了研究，并提出了一种权值分类进化重采样方法。对传统重要性概率密度函数的优化思想进行了阈值分割，只对退化情况下的建议分布函数进行优化，既有效增强了最新观测信息对粒子的修正作用，也较好地降低了粒子状态优化的时间消耗。同时，在重采样阶段依据粒子的权值大小将采样粒子集分别聚类为小权值种群、保留种群和大权值裂变种群。对大权值粒子裂变后的粒子和小权值粒子进行差分进化，通过突变、交叉、选择产生新粒子种群，避免了对历史小权值信息的丢弃。仿真分析结果表明，本文方法有效提升了采样粒子空间分布的多样性，在合理计算复杂性的基础上，有效提升了算法的粒子多样性，在不增加运算负担的前提下提升了滤波的精度，比现有的重采样方法具有更好的精度和稳定性。但是本文在分析中对粒子的采样数是固定的，后续的研究中，需要探索研究采样粒子数同不同滤波精度需求之间的关系，构建重采样粒子数目的自适应规则，实现完整的智能重采样和自适应滤波性能，提升在模型和噪声统计特性失配情况下的滤波精度。