邓 琪，陈 刚*，鲁华祥，张珊珊，陈艾东，郭祉薇

（1.中国科学院半导体研究所高速电路与神经网络实验室，北京 100083；2.中国科学院大学，北京 100089；3.北京联合大学，北京 100101）

0 引言

机动目标跟踪是雷达跟踪、视频监控、移动机器人等许多实际应用中的一项基础性和关键性任务，具有广泛的军事和民用背景［1］。目前国内外大量研究都集中在二维平面，当目标在三维空间各方向都出现强度不一致的高机动时，通过二维模型和算法的扩展已无法准确描述目标运动，因此，三维空间机动目标跟踪已成为该类问题的难点之一［2］。

机动目标跟踪本质是利用传感器的离散量测值来估计目标的连续状态，主要包括目标机动模型的建模、机动检测或机动辨识以及滤波算法［3］。粒子滤波（Particle Filter，PF）由于适用于强非线性非高斯系统，常被作为机动目标跟踪过程中的滤波算法。但粒子滤波本身存在粒子退化问题和粒子匮乏现象，且算法复杂度很大程度上依赖于粒子数目［4］。为解决该问题，多数研究都致力于改进粒子重采样步骤，通常基于传统重采样机制进行改进，如分层重采样［5］、自适应重采样［6］、确定性重采样［7］等；另一种新的发展方向是通过引入群智能优化思想增加样本多样性，如遗传算法［8］、萤火虫算法［9］、蝙蝠算法［10］等优化重采样。以上方法通过改进粒子重采样环节能一定程度上增加样本多样性，降低粒子退化程度。但当处理三维空间中的机动目标跟踪问题时，由于目标不同方向上机动方式和强度不一致，状态空间会出现某些区域的粒子分布稀疏，难以均匀覆盖，致使算法迭代时粒子加剧退化，导致样本多样性降低。随着目标运动模型复杂度增加，算法性能下降的更为明显，常需增加粒子数量来保证覆盖范围，运算时间较长，无法保证跟踪实时性和良好的跟踪精度。

针对以上问题，本文提出一种基于分治采样［11］的粒子滤波三维机动目标跟踪算法（Partition Sampling Particle Filter，PS-PF），通过分解运动空间，子空间内独立抽样粒子，降维处理目标机动，解决三维空间中粒子分布稀疏的问题，减缓粒子退化问题和粒子匮乏现象对目标跟踪造成的影响。同时为方便数据处理，加入量测信息预处理模块，实现量测信息的坐标转换。通过在多个运动模型上的仿真比较，结果表明本文所提出的算法在跟踪性能上具有显著优势。

1 三维空间运动模型

1.1 状态模型

考虑目标的状态模型如下［12］：

1.2 观测模型

笛卡尔坐标系中，目标状态在各维度中相互独立，为便于处理，考虑目标观测模型如下：

2 观测数据预处理

实际应用中，机动目标的观测数据由雷达等传感器测量获得，所得到的观测数据多基于球坐标，包括径向距离r，方位角b 和俯仰角e，可表示为［13］：

其中，vr、vb、ve分别为径向距离、方位角和俯仰角的观测噪声。

基于球坐标的观测数据具有很强的非线性，需要对观测数据进行坐标转换。假设两坐标系间存在坐标变换φ=h-1，其中h=［hr，hb，he］T，当已知系统观测值Z=［r，b，e］T，可以得出笛卡尔坐标系中的观测值：

转换后笛卡尔坐标系中的真实观测数据可表示为：

这里vx、vy、vz为转换后的观测噪声，其协方差矩阵为Rc =J（Z）×R×J（Z），J（Z）为观测量的Jacobian行列式，R 为转换前观测噪声协方差矩阵。

3 分治采样粒子滤波算法

3.1 粒子滤波

粒子滤波以贝叶斯估计为解决框架，基于蒙特卡洛方法，通过寻找一组在状态空间传播的随机样本对概率密度函数进行近似，以样本均值代替积分运算，从而获得状态最小方差。该算法不需要对系统做任何先验假设，适用于强非线性非高斯系统，具有很好的算法可扩展性和普适性。

粒子滤波算法描述如下［3-4］：

3.1.1 初始化

k=0 时，由先验概率p（X0）产生粒子集，其中。

3.1.2 更新

权值计算，根据权值更新公式计算粒子新的权值：

状态估计输出：

3.1.3 重采样

3.1.4 预测

3.2 分治采样方法

对于粒子滤波算法，状态空间维数越高意味着所需粒子数更多，从而保证粒子的空间覆盖率足够广。随着状态维数增加，算法复杂度呈指数增长。分治采样方法是将系统状态空间分割成若干个独立子空间，每个子空间用各自最佳的策略独立抽样粒子，并在低维空间预测最优子状态，最后输出为所有预测子状态的加权和。

注意到在笛卡尔坐标系中，目标在运动空间各方向的运动状态相互独立，不受其他方向上的运动影响，即运动空间是三维正交的。根据运动分解与合成思想，目标整体运动状态可以表示为各方向运动的叠加。图1 为三维空间分治采样方法结构图。

引入分治法思想，对三维运动空间进行分割，假设分别在一维子空间中采样粒子点，各方向分别采样Nx、Ny、Nz个随机样本，那么粒子总数为（Nx+Ny+Nz），总体粒子多样性能达到Nx×Ny×Nz种。若直接在三维空间中采样同样数量的粒子，粒子多样性只有（Nx+Ny+Nz）种，显然前者采样粒子的空间覆盖范围更广，能一定程度上降低粒子退化现象、提高预测精度。

下面对算法复杂度进行分析。根据本文第1 节分析，状态向量维数为9，观测向量维数为3。设粒子采样总数为N 个，滤波算法中状态一步预测时间为Tf，量测一步预测时间为Th。当采用分治采样方法，状态空间分解为3 个独立子空间，各子空间内抽取样本数相同，状态一步预测时间降低为Tf/9，量测一步预测时间降低为Th/3。对于同一个模型，传统采样滤波方法的复杂度为N×（Tf+Th），分治采样滤波方法的复杂度为N×（Tf+3Th）/9。两种方法的复杂度同阶，但分治采样方法运算时间上要小于传统方法。当Tf＞＞Th，算法复杂度由状态一步预测时间主导，随着目标状态模型复杂性上升，算法运算时间能削减至原算法的12%。

图1 三维空间分治采样方法结构图

3.3 基于分治采样的粒子滤波跟踪算法

基于分治采样粒子滤波的三维机动目标跟踪算法的基本思想，是将三维运动空间按照笛卡尔坐标系分解成3 个独立的一维状态子空间，使用粒子滤波算法在各子空间内分别按照最优采样策略采取样本点，增加粒子多样性，并结合坐标系变换后的观测数据预测子状态，最后所有子状态合成得到最终的输出状态。基于分治采样的粒子滤波跟踪算法步骤描述如下：

3.3.1 初始化

3.3.2 预测

3.3.3 输出状态合成

4 仿真与分析

为验证算法有效性，进行两个仿真实验：三维匀速运动目标跟踪和基于CS 模型的机动目标跟踪。仿真实验中将本文算法与标准粒子滤波进行对比，采用均方根误差进行评价：

4.1 三维匀速运动目标跟踪

设定传感器的采样间隔t=1 s，采样时长T=200 s，给定目标的初始状态X0=［-20 m，2 m/s，0 m/s2，10 m，1.5 m/s，0 m/s2，5 m，1 m/s，0 m/s2］T，运动模型为匀速直线运动模型（CV 模型）［14］，即：

过程噪声与观测噪声都服从N（0，1）高斯分布。

图2 三维匀速目标运动轨迹

目标运动轨迹如图2 所示。图3 为算法中采样粒子数目与算法性能变化图，增加粒子数目会提高算法跟踪精度，但当粒子数达到一定值后，算法性能将逐渐趋于平稳，即增加粒子数不会带来明显的精度提升，而是收敛到所谓的最优精度。

图3 粒子数目与匀速目标跟踪性能变化趋势

由图3 可知，标准粒子滤波在总粒子数达到160 后性能开始趋于稳定，而基于分治采样的算法在总粒子数为100 时就开始进入收敛状态。为保证实验结果可靠性，算法采用的粒子数目选择在逼近最优精度的平稳状态时所需粒子数进行重复实验，标准粒子滤波算法选取粒子总数200 个，本文所提出的算法选取粒子总数150 个，每种算法进行1 000次蒙特卡罗仿真。

表1 三维匀速目标跟踪结果对比

表1 为两种算法在匀速运动目标跟踪实验中的数据结果，由于运动模型较为简单，两种算法在跟踪精度上差距不大。其中标准粒子滤波每次需采样200 个粒子才能达到较为稳定的跟踪效果。PS-PF 引入了降维处理思想，通过划分独立的运动空间，每个运动方向只需分别采样50 个随机样本，共计150 个样本点，在保证精度一定程度提升的同时，算法运行时间降低约65%。

4.2 基于当前统计模型的三维机动运动目标跟踪

设定传感器的采样间隔t=1 s，采样时长T=200 s，同样给定目标初始状态X0=［-20 m，2 m/s，0 m/s2，10 m，1.5 m/s，0 m/s2，5 m，1 m/s，0 m/s2］T，机动目标参数［9］如表2 所示。参数设置为机动频率f=1/60，最大加速度αmax=1 m/s2，过程噪声与观测噪声同样都服从N（0，1）高斯分布。

表2 机动目标参数

三维机动目标运动轨迹如下页图4 所示，图5为两种算法中粒子数目与机动目标跟踪性能变化趋势图，为保证实验结果可靠性，算法选择在最优精度的平稳状态时所需粒子数进行重复实验，标准粒子滤波算法选取1 000 个粒子，本文算法选取150 个粒子，每种算法进行1 000 次蒙特卡罗仿真。

图4 三维机动目标运动轨迹

图5 粒子数目与机动目标跟踪性能变化趋势

当机动目标按表2 加速度变化的方式进行运动时，两种算法的跟踪结果对比如表3 所示，图6为两种算法各方向的误差分布图。标准粒子滤波算法在采样1 000 个粒子点的情况下，目标各方向跟踪位置的均方根误差达到3.8 m 左右；而采用分治采样策略的改进算法各方向只需采样50 个粒子，在总粒子数为150 的情况下，目标位置的各方向均方根误差能降低到1.9 m 左右，且算法的运行时间有了显著降低。在该仿真实验中，标准粒子滤波与分治采样粒子滤波，二者粒子数比例为6.7∶1，跟踪误差为2∶1，运行时间为14∶1。显然基于分治采样的粒子滤波相较于标准粒子滤波，精度提升了一倍，算法时间减少到原来的7%，无论跟踪精度还是运算时间上，都具有非常显著的优势。

结合以上两个仿真实验结果分析，随着运动模型复杂度的增加，标准粒子滤波算法所要采样的粒子数也随之增加，算法计算量很大程度上依赖于粒子数目，这将带来了更大的计算量。当粒子总数为1 000 个，算法运算时间长达11 s。且在复杂模型中，增加粒子数目并未使粒子的多样性达到实际所需，并存在大量冗余且无效的粒子，跟踪精度也有所下降。基于分治采样的改进粒子滤波通过划分独立子空间，在各子空间中分别抽取样本点，以此增加样本多样性，对机动目标的运动实现降维处理，在提高跟踪精度的同时大大降低了算法的单步迭代时间，更好地保证了目标跟踪的实时性和有效性。综上所述，本文所提出的基于分治采样的改进粒子滤波跟踪算法具有更高的综合效率比。

表3 三维机动目标跟踪结果对比

图6 各方向目标跟踪误差

5 结论

针对粒子滤波三维运动空间中样本多样性较低，存在运算冗余等问题，本文提出一种基于分治采样的粒子滤波跟踪算法，通过分解独立状态子空间，各子空间内分别采取最优采样策略采样粒子，对目标运动进行降维处理，解决了标准粒子滤波在三维运动空间中粒子分布稀疏的问题，有效缓解了粒子退化问题，在提高样本多样性的同时降低了算法复杂度。仿真结果表明，该算法能大大降低同等精度条件下的算法运算时间，与标准粒子滤波相比具有更好的跟踪性能，且运动模型越复杂越能突显其优势，具有较好的应用前景。