CN114002667B - 一种基于随机矩阵法的多近邻扩展目标跟踪算法 - Google Patents

Abstract

本发明公开了一种基于随机矩阵法的多近邻扩展目标跟踪算法，包括：接收初始时刻的量测数据，并初始化航迹；利用随机矩阵法对航迹假设进行状态和扩展形态一步预测；利用波门聚类法和层次聚类法分别进行量测聚类；将聚类得到的量测群与航迹假设相关联，生成数据关联假设；采用全局最近邻法选出最优假设；利用随机矩阵法对航迹假设进行状态和扩展形态更新；对航迹进行管理以生成、筛选、删除航迹，并输出航迹。本发明能够应用于智能交通、自动驾驶等领域，对存在多个扩展目标、目标间距离很近、目标运动模式多样、目标大小不同的环境下的多近邻扩展目标进行准确跟踪，解决目标距离很近造成的量测聚类易混淆，多目标的状态、扩展形态、目标数量联合估计等问题。

Description

一种基于随机矩阵法的多近邻扩展目标跟踪算法

技术领域

本发明涉及多近邻扩展目标跟踪技术，特别是一种针对于多个扩展目标、目标间距离很近、目标运动模式多样、目标大小不同的多扩展目标跟踪算法。

背景技术

目标跟踪是十分重要的支撑技术，对诸多面向高级复杂应用背景的信息处理系统至关重要，并在导弹制导及反导系统、自动驾驶系统等军事及民用领域中得到了广泛的应用与发展，具有重要的应用价值。

用于目标跟踪的传感器，包括雷达、声呐、光学仪器等，可提供关于目标数目、位置、速度等特征的带不确定性干扰的量测数据。相较于其他传感器，毫米波雷达可全天候全天时工作、性能稳定、受天气影响小、抗干扰反隐身、价格低廉，是目标跟踪领域内对中远距离目标探测的首要选择。

毫米波雷达回波数少、杂波密集、无成像能力。基于毫米波雷达的目标跟踪面临两大难点：目标层面和量测层面。目标层面包括(1)机动目标跟踪：目标运动模式多样；(2)多目标跟踪：目标个数时变且未知。量测层面包括(1)数据关联：雷达量测来源(车辆、行人、建筑物)未知，对正确的数据关联形成挑战；(2)干扰去除：跟踪场景复杂，存在海量杂波干扰；(3)扩展目标跟踪：单个目标可能产生多个量测，且量测个数未知，如何利用多个量测联合估计该目标的状态和形态是一大挑战。

以上难点可概括为复杂环境密集场景下的多扩展目标跟踪问题，即需要实时跟踪多个目标，联合推断出目标的数目、运动状态(位置、速度、加速度)及扩展形态(大小、朝向)。然而传统的目标跟踪理论与技术往往针对多个点目标或单个扩展目标，不能直接用于解决多扩展目标跟踪问题。因此要在传统的目标跟踪技术的基础上，提出新的多扩展目标跟踪算法。

多扩展目标跟踪问题的一大难点在于数据关联。实际场景存在海量的干扰量测，这些干扰可来自于建筑物、树木、马路等，对正确的数据关联构成挑战。即便没有这些干扰，若目标间距离较近，传统聚类算法如层次聚类法、k-means法、DB-scans等难以准确聚类，会导致目标状态的估计出现较大误差。

因此，提供一种针对于多个扩展目标、目标间距离很近、目标运动模式多样、目标大小不同的多扩展目标跟踪算法成为目前亟待解决的技术问题。

发明内容

本发明的目的在于解决现有跟踪算法无法实现多扩展目标跟踪、量测聚类与数据关联极易出错等问题。本发明提出一种新的基于波门的聚类算法用于数据关联，提升了近邻目标量测聚类的准确性，降低了目标状态的估计误差；本发明结合随机矩阵法与全局最近邻法，构建了一个融合了扩展目标跟踪技术和多目标跟踪技术的算法框架，实现了多扩展目标跟踪，联合推断出目标的数目、运动状态(位置、速度、加速度)及扩展形态(大小、朝向)。本发明最终实现了对存在多个扩展目标、目标间距离很近、目标运动模式多样、目标大小不同环境下的多近邻扩展目标进行准确跟踪。

本发明是通过下述技术方案来实现的。

本发明提供的一种基于随机矩阵法的多近邻扩展目标跟踪算法，包括以下步骤：

S101：接收初始时刻的量测数据，初始化航迹；

S102：利用随机矩阵法对上一个时刻的航迹假设进行状态和扩展形态的一步预测；

S103：接收当前时刻的量测数据，采用波门聚类法和层次聚类法分别进行量测聚类；

S104：将当前时刻的量测群与上一个时刻的航迹假设相关联，生成若干数据关联假设；

S105：采用全局最近邻法选出最优航迹假设；

S106：利用随机矩阵法对当前时刻的航迹假设进行状态和形态更新；

S107：航迹管理与输出。

对于上述技术方案，本发明还有进一步优选的方案：

优选的，所述步骤S101包括如下步骤：

11)将初始时刻的极坐标系下的传感器量测转换到直角坐标系下；

12)采用层次聚类法对传感器量测进行聚类，得到若干个量测群，每一个量测群包括若干个量测点；

13)每一个量测群代表一个可能的目标，根据量测数据和先验信息初始化目标的状态、形态参数和生命值。

进一步，步骤12)中，层次聚类法包括如下步骤：

121)对于k时刻n_k个量测数据，计算每两个量测间的距离；

122)将量测数据分组到一个二进制的分层聚类树中，依据两个类之间的最短、最长、平均距离或是核距离进行分组；

123)根据设定的阈值分割聚类树，将量测数据分为若干类。

优选的，所述步骤S102包括如下步骤：

21)利用随机矩阵法对上一个时刻的航迹假设进行状态一步预测；

22)利用随机矩阵法对上一个时刻的航迹假设进行扩展形态一步预测。

优选的，所述步骤S103包括如下步骤：

31)将k时刻的极坐标系下的传感器量测转换到直角坐标系下；

32)采用波门聚类法处理k时刻的传感器量测，得到若干个量测群；

33)采用层次聚类法处理上一步中未被聚类的，即处于任意波门之外的k时刻的传感器量测，再得到若干个量测群。

进一步，步骤32)中，波门聚类法步骤如下：

基于k-1时刻的目标状态与形态，得到k时刻目标的预测状态与预测形态；

根据k时刻目标的预测状态与预测形态生成波门；

根据波门划分k时刻的量测数据，落在同一个波门内的量测即聚为同一类。

33)采用层次聚类法处理上一步中未被聚类的，即处于任意波门之外的k时刻的传感器量测，再得到若干个量测群。

优选的，所述步骤S104包括如下步骤：

41)采用椭形跟踪门确定量测群是否与航迹关联上；

42)若量测群进入某个模型的波门，则认为量测群与航迹关联上了，并生成一个相应的数据关联假设。其中，有可能存在某一个航迹不与任何量测群关联，即该航迹在当前时刻没有对应的量测；也可能存在某一个量测群不与任何航迹关联，即该量测群代表一个新生目标，则按照步骤一所述方式进行初始化得到新航迹。

优选的，所述步骤S105包括如下步骤：

51)计算量测群中所有量测的均值和量测的个数；

52)对于一个假设，定义量测与目标预测位置间的距离为新息向量的加权范数；

53)数据关联：选择全局最优假设，使得全局统计距离最小，同时满足条件：一条航迹最多与一个量测群关联，一个量测群最多与一条航迹关联。可以通过线性规划来完成选择。

优选的，所述步骤S106包括如下步骤：

61)利用随机矩阵法对当前时刻的航迹假设进行状态更新；

62)利用随机矩阵法对当前时刻的航迹假设进行扩展形态更新。

优选的，所述步骤S107包括如下步骤：

71)若某个航迹在当前时刻没有与任何量测群关联，将其生命值减一；

72)遍历航迹，若航迹生命值为0，则将航迹终止标志置为1，否则将航迹终止标志置为0；

73)对于航迹终止标志为0的航迹删除，不再进行输出；

74)对于航迹终止标志为1的航迹，若航迹历史关联次数小于3次，则暂时将航迹进行保留，但不输出；

75)对于航迹终止标志为1的航迹，若航迹历史关联次数大于等于3次，则将航迹输出。

本发明由于采取以上技术方案，其具有以下有益效果：

本发明提出一种新的基于波门的聚类算法用于数据关联，提升了对近邻目标的聚类准确性，降低了目标状态的估计误差；本发明结合随机矩阵法与全局最近邻法，创造性地提出一个融合了扩展目标跟踪技术和多目标跟踪技术的算法框架，实现了多扩展目标跟踪，联合推断出目标的数目、运动状态(位置、速度、加速度)及扩展形态(大小、朝向)。

附图说明

此处所说明的附图用来提供对本发明的进一步理解，构成本申请的一部分，并不构成对本发明的不当限定，在附图中：

图1为基于随机矩阵法的多近邻扩展目标跟踪算法流程图；

图2为仿真场景示意图；

图3(a)-3(f)为仿真场景下是否采用波门聚类法的多近邻扩展目标跟踪算法的结果比较示意图；

其中图3(a)-3(b)为只使用层次聚类法的某两个时刻的聚类和估计结果，图3(c)-3(d)为以波门聚类法为主、层次聚类法为辅的某两个时刻的聚类和估计结果，图3(e)只使用层次聚类法的跟踪算法整体结果，图3(f)为以波门聚类法为主、层次聚类法为辅的跟踪算法整体结果；

图4为实测场景示意图；

图5为雷达坐标系下的无干扰的回波数据示意图；

图6(a)-6(f)为实测场景下是否采用波门聚类法的多近邻扩展目标跟踪算法的结果比较示意图；

其中图6(a)-6(b)为只使用层次聚类法的某两个时刻的聚类和估计结果，图6(c)-6(d)为以波门聚类法为主、层次聚类法为辅的某两个时刻的聚类和估计结果，图6(e)为只使用层次聚类法的跟踪算法整体结果，图6(f)为以波门聚类法为主、层次聚类法为辅的跟踪算法整体结果。

具体实施方式

下面将结合附图以及具体实施例来详细说明本发明，在此本发明的示意性实施例以及说明用来解释本发明，但并不作为对本发明的限定。

如图1所示，本发明实施例提供一种基于随机矩阵法的多近邻扩展目标跟踪算法，包括以下步骤：

S101：接收初始时刻的量测数据，初始化航迹。

具体包括如下步骤：

11)将初始时刻的极坐标系下的传感器量测转换到直角坐标系下；

12)采用层次聚类法对传感器量测进行聚类，得到若干个量测群，每一个量测群包括若干个量测点。

其中，层次聚类法步骤如下：

121)对于k时刻n_k个量测数据计算每两个量测与(i≠j)间的距离；距离有多种计算方式：欧氏距离、马氏距离、街区距离、闵可夫斯基距离、切比雪夫距离、汉明距离等；此处可采用欧氏距离或马氏距离；

122)将量测数据分组到一个二进制的分层聚类树中；分组的依据可以是两个类之间的最短、最长、平均距离或是核距离；在多扩展目标跟踪中可以根据实际应用场景来选择合适的分组依据；

123)根据设定的阈值分割聚类树，将量测数据分为若干类；阈值的选择应充分考虑实际目标的大小、目标间的距离等先验信息。

13)每一个量测群代表一个可能的目标，根据量测数据和先验信息初始化以下目标的状态、形态参数和生命值。

其中，初始化方式具体如下：

每一个量测群代表一个可能的目标，根据量测数据和先验信息初始化以下目标的状态和形态参数：目标的初始状态目标的初始状态的协方差矩阵P₀，目标的初始扩展形态目标的初始扩展形态的自由度目标的初始状态包括位置和速度信息，具体为：

其中，为量测群中位置量测的均值，为真正的量测噪声的位置项，为过程噪声的速度项，T为量测的更新周期；另外，可以设置为定值，并使表示的椭圆大致符合目标的先验形态信息；另外，每条航迹初始化其生命值为一个正整数，例如初始生命值为3。

S102：利用随机矩阵法对上一个时刻的航迹假设进行状态和扩展形态的一步预测；

具体包括如下步骤：

21)利用随机矩阵法对上一个时刻的航迹假设进行状态一步预测；运动状态的运动模型如下：

式中，x_k为k时刻的运动状态，Φ_k为状态转移矩阵，x_k-1为k-1时刻的运动状态，w_k为过程噪声，为均值为0，方差为的高斯分布，D_k为一维物理空间模型中的过程噪声的协方差矩阵，为Kronecker乘积，X_k为扩展形态；

其中，F_k为一维物理空间上的状态转移矩阵，I_d为单位矩阵，d为物理空间的维度； 为单维方向上加速度的方差，为参数矩阵；

令表示k时刻的n_k个量测数据组成的集合，令表示k-1时刻及之前的量测信息；

运动状态的一步预测为：

式中，为对k时刻的目标状态的一步预测值，为k-1时刻的运动状态的估计值，P_k|k-1为对k时刻的目标状态的协方差的一步预测值，F_k为一维物理空间上的状态转移矩阵；

22)利用随机矩阵法对上一个时刻的航迹假设进行扩展形态一步预测；形态演化模型描述和刻画了目标的形态随着时间的变化

式中，X_k为k时刻的扩展形态，X_k-1为k-1时刻的扩展形态，为Wishart分布，δ_k为演化分布的自由度，A_k为形态演化矩阵；

扩展形态的一步预测为：

式中：为对k时刻的目标扩展形态的一步预测，为对k-1时刻的目标扩展形态的估计值，为对k时刻的目标扩展形态的自由度的一步预测，为对k-1时刻的目标扩展形态的自由度的估计值，d为物理空间的维度，λ_k-1为中间变量。

S103：接收当前时刻的量测数据，采用波门聚类法和层次聚类法分别进行量测聚类；

具体包括如下步骤：

31)将k时刻的极坐标系下的传感器量测转换到直角坐标系下；

32)采用波门聚类法处理k时刻的传感器量测，得到若干个量测群；

其中，波门聚类法步骤如下：

321)基于k-1时刻的目标状态与形态P_k-1，得到k时刻目标的预测状态与预测形态

322)根据k时刻目标的预测状态与预测形态生成波门波门定义为：

式中，z为量测点，为对k时刻的目标的量测的预测值；为k时刻目标的扩展形态的一步预测，S_k为关于波门大小的参数，γ²为阈值；

S_k按如下计算得到：

式中，P_k|k-1为对k时刻的目标状态的协方差的一步预测值，H_k为量测矩阵，B_k为形态观测矩阵，d为物理空间的维度；

γ²按如下计算得到：

式中，P_G为门限概率，为对k时刻的目标扩展形态的自由度的一步预测；

323)根据波门划分k时刻的量测数据落在同一个波门内的量测即聚为同一类；

33)采用层次聚类法处理上一步中未被聚类的，即处于任意波门之外的k时刻的传感器量测，再得到若干个量测群。

S104：将当前时刻的量测群与上一个时刻的航迹假设相关联，生成若干数据关联假设；

具体包括如下步骤：

41)采用椭形跟踪门确定量测群是否与航迹关联上，跟踪门定义为：

式中，z为量测点，为对k时刻的目标的量测的预测值；为k时刻目标的扩展形态的一步预测，G为设定的阈值；

S_k按如下计算得到：

式中，P_k|k-1为对k时刻的目标状态的协方差的一步预测值，H_k为量测矩阵，B_k为形态观测矩阵，d为物理空间的维度，n_k为k时刻的量测的个数；

42)若量测群进入某个模型的波门，则认为量测群与航迹关联上了，并生成一个相应的数据关联假设，记为假设H_ij，其中1≤i≤n_k表示当前时刻的量测群，1≤j≤t_k-1表示上一个时刻的航迹；其中，存在某一个航迹不与任何量测群关联，即该航迹在当前时刻没有对应的量测；或存在某一个量测群不与任何航迹关联，即该量测群代表一个新生目标。

S105：采用全局最近邻法选出最优假设；

具体包括如下步骤：

51)计算量测群i中所有量测的均值记为量测的个数为n_k,i；

52)对于一个假设H_ij，定义量测与目标预测位置间的距离为新息向量的加权范数：

式中，为量测与目标预测位置间的距离，为量测群i中所有量测的均值，为假设H_ij对应的目标的量测的预测值，为假设H_ij对应的目标的扩展形态的一步预测的一个参数；

其中，H_k为量测矩阵，I_d为单位矩阵，为Kronecker乘积，d为物理空间的维度，为假设H_ij对应的目标的运动状态的一步预测，S_k,ij为关于波门大小的参数；

S_k,ij按如下计算得到：

式中，P_k|k-1,ij为假设H_ij对应的对k时刻的目标状态的协方差的一步预测值，B_k为形态观测矩阵，n_k,i为k时刻的量测群i中量测的个数；

53)数据关联：选择全局最优假设，使得全局统计距离最小，同时满足条件：一条航迹最多与一个量测群关联，一个量测群最多与一条航迹关联；可以通过线性规划来完成选择；目标函数为：

式中，n_k为k时刻的量测的个数，t_k-1为k-1时刻的航迹个数，i表示量测序号，j表示航迹序号，x_ij表示假设H_ij是否被选中；

约束条件为：

得到最优解为X^*＝{x_ij}，其中

S106：利用随机矩阵法对当前时刻的航迹假设进行状态和形态更新；

具体包括如下步骤：

61)利用随机矩阵法对当前时刻的航迹假设进行状态更新；设k时刻量测值集合为n_k为k时刻量测值的个数；在随机矩阵的框架下，给出如下的量测模型结构：

式中，为量测，为系统的量测矩阵，x_k为k时刻的运动状态，为独立高斯白噪声；

其中，H_k为一维物理空间中将状态向量转化为位置标量的线性矩阵，I_d为单位矩阵，为Kronecker乘积，d为物理空间的维度，的分布为均值为0，方差为的高斯分布，B_k是形态观测矩阵，X_k为k时刻的扩展形态。

运动状态的更新为：

式中，为k时刻的运动状态的估计值，为对k时刻的目标状态的一步预测值，K_k为滤波增益，I_d为单位矩阵，为Kronecker乘积，G_k为估计误差，P_k为k时刻的运动状态的协方差的估计值，P_k|k-1为对k时刻的目标状态的协方差的一步预测值，S_k为新息协方差矩阵；

其中，新息协方差矩阵S_k按如下计算：

滤波增益K_k按如下计算：

估计误差G_k按如下计算：

式中，为k时刻量测数据的均值；

根据正态分布的性质可以得到即对k时刻的目标状态的跟踪结果；

62)利用随机矩阵法对当前时刻的航迹假设进行扩展形态更新；基于量测模型结构，可以得到扩展形态的更新为：

式中，为对k时刻的目标扩展形态的估计值，为对k时刻的目标扩展形态的一步预测，B_k为形态观测矩阵，为k时刻量测数据的协方差的n_k-1倍，n_k为k时刻的量测的个数，为对k时刻的目标扩展形态的自由度的估计值，为对k时刻的目标扩展形态的自由度的一步预测；

根据逆Wishart分布的性质可以得到即对k时刻的目标扩展形态的跟踪结果。

S107：航迹管理与输出；

具体包括如下步骤：

71)若某个航迹在当前时刻没有与任何量测群关联，将其生命值减一；

72)遍历航迹，若航迹生命值为0，则将航迹终止标志置为1，否则将航迹终止标志置为0；

73)对于航迹终止标志为0的航迹删除，不再进行输出；

74)对于航迹终止标志为1的航迹，若航迹历史关联次数小于3次，则暂时将航迹进行保留，但不输出；

75)对于航迹终止标志为1的航迹，若航迹历史关联次数大于等于3次，则将航迹进行输出。

下面通过具体实施例来进一步说明本发明。

S101：接收起始时刻的毫米波雷达量测，并将其转换到以毫米波雷达为原点的传感器直角坐标系下，然后再视情况基于传感器的位置、位姿转换到绝对直角坐标系下；然后以层次聚类法处理雷达量测，得到若干量测群；最后按照航迹初始化方法，以一个量测群代表一个可能的目标初始化若干条航迹；

S102：初始化之后，根据运动模型和形态演化模型，利用随机矩阵法对上一个时刻的航迹假设进行状态和扩展形态一步预测，得到各假设下的航迹在k时刻的状态预测参数P_k|k-1和形态预测参数

S103：接收k时刻的毫米波雷达量测，并将其转换到以毫米波雷达为原点的传感器直角坐标系下，然后再视情况基于传感器的位置、位姿转换到绝对直角坐标系下；然后基于k时刻的状态预测状态预测误差协方差P_k|k-1、形态预测参数生成波门并以波门划分量测，落在同一个波门内的量测即聚为同一类；最后，由于波门并不能完全圈住所有的量测，对于剩下的量测，采用层次聚类法处理，再得到若干个量测群；最终将k时刻的毫米波雷达量测分为若干量测群；

S104：基于k时刻的状态预测状态预测误差协方差P_k|k-1、形态预测参数生成椭形跟踪门(考虑到目标机动、量测噪声及估计不准确等情况，这里的跟踪门可以较大)，排除与航迹距离较远的量测群，从而减少生成的假设数，减小计算量；若量测群进入某个模型的波门，则认为量测群与航迹关联上了，并生成一个相应的数据关联假设；其中，有可能存在某一个航迹不与任何量测群关联，即该航迹在当前时刻没有对应的量测；也可能存在某一个量测群不与任何航迹关联，即该量测群代表一个新生目标，则按照航迹初始化方法得到一条新航迹；

S105：按照定义计算量测与目标预测位置间的距离；然后在满足假设一条航迹最多与一个量测群关联，一个量测群最多与一条航迹关联的情况下，利用线性规划等优化方法，选择全局最优假设，使得全局统计距离最小；

S106：选取最优假设后，即可得到每个目标在k时刻对应的毫米波雷达量测，并根据量测模型，利用随机矩阵法对上一个时刻的航迹假设进行状态和扩展形态更新，得到各目标在k时刻的状态估计参数P_k和形态估计参数并根据正态分布和逆Wishart分布的性质可以得到E[x_k|Z_k]和E[X_k|Z_k]，即k时刻每个目标的状态和扩展形态的估计结果；

S107：若某个航迹在当前时刻没有与任何量测群关联，将其生命值减一；遍历航迹，若航迹生命值为0，则将航迹终止标志置为1，否则将航迹终止标志置为0；对于航迹终止标志为0的航迹删除，不再进行输出；对于航迹终止标志为1的航迹，若航迹历史关联次数小于3次，则暂时将航迹进行保留，但不输出；对于航迹终止标志为1的航迹，若航迹历史关联次数大于等于3次，则将航迹进行输出；然后转到S102，重复后续过程直至达到终止条件，如系统结束工作。

图2所示仿真场景中，有3个扩展目标(长4.5m、宽2m的矩形，与普通轿车大小相当)在二维平面内运动。初始时目标相隔较远，随后不断靠近(目标1通过转弯靠近目标2，目标3速度较慢并逐渐被目标1、2追上)，最后并排前行。目标1、2运动速率为10m/s，目标3运动速率为9m/s。无噪声量测均匀采样自目标的形态。量测噪声服从高斯分布，其均值为零，方差为R_k＝diag([0.5²,0.5²])m²。采样间隔T＝0.1s，每个采样时刻每个目标的量测个数服从均值为5的泊松分布。跟踪全过程时长7s，共70个采样时刻。

图3(a)-3(b)显示了仿真场景下只使用层次聚类法的某两个时刻的聚类和估计结果。第26步三个目标初步接近时，层次聚类法虽能勉强分出3个不同的类，但聚类结果的误差很大，导致目标的状态、形态的估计结果不准确。第56步时，三个目标进一步靠近，层次聚类法错误地将来自于两个真实目标的量测判断为一个目标的，导致目标的个数估计错误，状态、形态估计不准确。

图3(c)-3(d)显示了仿真场景下以波门聚类法为主、层次聚类法为辅的某两个时刻的聚类和估计结果。与只使用层次聚类法相比，波门聚类法正确地将3个目标的量测分为3类，准确性大幅提升，同时目标的状态、形态的估计误差也大幅减小。

图3(e)显示了仿真场景下只使用层次聚类法的跟踪算法整体结果，图3(f)显示了仿真场景下以波门聚类法为主、层次聚类法为辅的跟踪算法整体结果。在目标密集且间距较小的应用场景中，只使用层次聚类法的跟踪算法最后错误地将三个真实目标估计为一个目标T3，无法正确推断目标的个数和状态信息。而以波门聚类法为主、层次聚类法为辅的跟踪算法实现了多个近邻目标的精准跟踪。

图4所示实测场景中，只关注距离较近的5辆车，其中3辆前行、1辆左转弯、1辆右转弯。使用一辆搭载前向摄像头和前向毫米波雷达的小汽车跟踪这5辆车。

图5显示了雷达坐标系下这些目标车辆在某一时刻的毫米波雷达回波数据(已去除杂波)。由图很难看出毫米波雷达探测到了几个目标，且难以判断每个目标分别所对应的量测。

图6(a)-6(b)显示了实测场景下只使用层次聚类法的某两个时刻的聚类和估计结果。尽管在第8步，层次聚类法效果尚可，但在第14步，层次聚类法错误地将来自于两个真实目标的量测判断为一个目标的，导致目标的个数估计错误，状态、形态估计不准确。

图6(c)-6(d)显示了实测场景下以波门聚类法为主、层次聚类法为辅的某两个时刻的聚类和估计结果。可见波门聚类法大幅提升了聚类的准确性，为多个目标的精准跟踪提供了保障。

图6(e)显示了实测场景下只使用层次聚类法的跟踪算法整体结果，图6(f)为显示了实测场景下波门聚类法为主、层次聚类法为辅的跟踪算法整体结果。可见，层次聚类法将不同目标的量测误判为同一类，严重影响了算法的跟踪性能；而波门聚类法一直保持着聚类的准确性，算法的估计结果更加稳定、准确。

以上实验结果验证了本发明提升了对近邻目标的聚类准确性，在目标间距离较近的场景中实现了多个扩展目标的精准跟踪，具有重大的理论和实践价值。

本发明并不局限于上述实施例，在本发明公开的技术方案的基础上，本领域的技术人员根据所公开的技术内容，不需要创造性的劳动就可以对其中的一些技术特征作出一些替换和变形，这些替换和变形均在本发明的保护范围内。

Claims (9)

1.一种基于随机矩阵法的多近邻扩展目标跟踪算法，其特征在于，包括以下步骤：

S101：接收初始时刻的量测数据，初始化航迹；

S102：利用随机矩阵法对上一个时刻的航迹假设进行状态和扩展形态的一步预测；

S103：接收当前时刻的量测数据，采用波门聚类法和层次聚类法分别进行量测聚类；

S104：将当前时刻的量测群与上一个时刻的航迹假设相关联，生成若干数据关联假设；

S105：采用全局最近邻法选出最优航迹假设；

S106：利用随机矩阵法对当前时刻的航迹假设进行状态和形态更新；

S107：航迹管理与输出；

所述步骤S102包括如下步骤：

21)利用随机矩阵法对上一个时刻的航迹假设进行状态一步预测；

22)利用随机矩阵法对上一个时刻的航迹假设进行扩展形态一步预测；

所述步骤S103包括如下步骤：

31)将k时刻的极坐标系下的传感器量测转换到直角坐标系下；

32)采用波门聚类法处理k时刻的传感器量测，得到若干个量测群；

33)采用层次聚类法处理上一步中未被聚类的，即处于任意波门之外的k时刻的传感器量测，再得到若干个量测群；

步骤32)中，波门聚类法步骤如下：

基于k-1时刻的目标状态与形态，得到k时刻目标的预测状态与预测形态；

根据k时刻目标的预测状态与预测形态生成波门；

根据波门划分k时刻的量测数据，落在同一个波门内的量测即聚为同一类；

33)采用层次聚类法处理上一步中未被聚类的，即处于任意波门之外的k时刻的传感器量测，再得到若干个量测群；

所述步骤S104包括如下步骤：

41)采用椭形跟踪门确定量测群是否与航迹关联上；

42)若量测群进入某个模型的波门，则认为量测群与航迹关联上了，并生成一个相应的数据关联假设；其中，有可能存在某一个航迹不与任何量测群关联，即该航迹在当前时刻没有对应的量测；也可能存在某一个量测群不与任何航迹关联，即该量测群代表一个新生目标，则按照步骤S101进行初始化得到新航迹；

所述步骤S105包括如下步骤：

51)计算量测群中所有量测的均值和量测的个数；

52)对于一个假设，定义量测与目标预测位置间的距离为新息向量的加权范数；

53)数据关联：选择全局最优假设，使得全局统计距离最小，同时满足条件：一条航迹最多与一个量测群关联，一个量测群最多与一条航迹关联；通过线性规划来完成选择；

所述步骤S106包括如下步骤：

61)利用随机矩阵法对当前时刻的航迹假设进行状态更新；

62)利用随机矩阵法对当前时刻的航迹假设进行扩展形态更新。

2.根据权利要求1所述的算法，其特征在于，所述步骤S101包括如下步骤：

11)将初始时刻的极坐标系下的传感器量测转换到直角坐标系下；

12)采用层次聚类法对传感器量测进行聚类，得到若干个量测群，每一个量测群包括若干个量测点；

13)每一个量测群代表一个可能的目标，根据量测数据和先验信息初始化目标的状态、形态参数和生命值。

3.根据权利要求2所述的算法，其特征在于，步骤12)中，层次聚类法包括如下步骤：

121)对于k时刻n_k个量测数据，计算每两个量测间的距离；

122)将量测数据分组到一个二进制的分层聚类树中，依据两个类之间的最短、最长、平均距离或是核距离进行分组；

123)根据设定的阈值分割聚类树，将量测数据分为若干类。

4.根据权利要求1所述的算法，其特征在于，所述步骤S102包括如下步骤：

21)利用随机矩阵法对上一个时刻的航迹假设进行状态一步预测；

运动状态的运动模型如下：

式中，x_k为k时刻的运动状态，φ_k为状态转移矩阵，x_k-1为k-1时刻的运动状态，w_k为过程噪声，为均值为0，方差为的高斯分布，D_k为一维物理空间模型中的过程噪声的协方差矩阵，为Kronecker乘积，X_k为k时刻的扩展形态；

令表示k时刻的n_k个量测数据组成的集合，令表示k-1时刻及之前的量测信息；

运动状态的一步预测为：

式中，为对k时刻的目标状态的一步预测值，为k-1时刻的运动状态的估计值，P_k|k-1为对k时刻的目标状态的协方差的一步预测值，F_k为一维物理空间上的状态转移矩阵，P_k-1为k-1时刻的运动状态的协方差的估计值；

22)利用随机矩阵法对上一个时刻的航迹假设进行扩展形态一步预测；

形态演化模型为

式中，X_k为k时刻的扩展形态，X_k-1为k-1时刻的扩展形态，为Wishart分布，δ_k为演化分布的自由度，A_k为形态演化矩阵；

扩展形态的一步预测为：

式中：为对k时刻的目标扩展形态的一步预测，为对k-1时刻的目标扩展形态的估计值，为对k时刻的目标扩展形态的自由度的一步预测，为对k-1时刻的目标扩展形态的自由度的估计值，d为物理空间的维度，λ_k-1为中间变量。

5.根据权利要求1所述的算法，其特征在于，步骤32)中，波门聚类法步骤如下：

321)基于k-1时刻的目标状态与形态P_k-1，得到k时刻目标的预测状态与预测形态

322)根据k时刻目标的预测状态与预测形态生成波门

波门定义为：

式中，z为量测点，为对k时刻的目标的量测的预测值；为k时刻目标的扩展形态的一步预测，S_k为关于波门大小的参数，γ²为阈值；

S_k按如下计算得到：

式中，P_k|k-1为对k时刻的目标状态的协方差的一步预测值，H_k为量测矩阵，B_k为形态观测矩阵，d为物理空间的维度；

γ²按如下计算得到：

式中，P_G为门限概率，为对k时刻的目标扩展形态的自由度的一步预测；

323)根据波门划分k时刻的量测数据，落在同一个波门内的量测即聚为同一类。

6.根据权利要求5所述的算法，其特征在于，所述步骤S104包括如下步骤：

41)采用椭形跟踪门确定量测群是否与航迹关联上，跟踪门定义为：

式中，G为设定的阈值；

S_k按如下计算得到：

式中，n_k为k时刻的量测的个数；

42)若量测群进入某个模型的波门，则认为量测群与航迹关联上了，并生成一个相应的数据关联假设，记为假设H_ij，其中1≤i≤n_k表示当前时刻的量测群，1≤j≤t_k-1表示上一个时刻的航迹；

其中，存在某一个航迹不与任何量测群关联，即该航迹在当前时刻没有对应的量测；或存在某一个量测群不与任何航迹关联，即该量测群代表一个新生目标。

7.根据权利要求1所述的算法，其特征在于，所述步骤S105包括如下步骤：

51)计算量测群i中所有量测的均值记为量测的个数为n_k,i；

52)对于一个假设H_ij，定义量测与目标预测位置间的距离为新息向量的加权范数：

式中，为量测与目标预测位置间的距离，为量测群i中所有量测的均值，为假设H_ij对应的目标的量测的预测值，为假设H_ij对应的目标的扩展形态的一步预测，S_k,ij为关于波门大小的参数，S_k,ij按如下计算得到：

式中，P_k|k-1,ij为假设H_ij对应的对k时刻的目标状态的协方差的一步预测值，H_k为量测矩阵，B_k为形态观测矩阵，d为物理空间的维度，n_k,i为k时刻的量测群i中量测的个数；

53)数据关联：选择全局最优假设，使得全局统计距离最小，同时满足条件：一条航迹最多与一个量测群关联，一个量测群最多与一条航迹关联；通过线性规划来完成选择，线性规划目标函数为：

式中，n_k为k时刻的量测的个数，t_k-1为k-1时刻的航迹个数，i表示量测序号，j表示航迹序号，x_ij表示假设H_ij是否被选中；

线性规划约束条件为：

得到最优解为X^*＝{x_ij}，其中

8.根据权利要求1所述的算法，其特征在于，所述步骤S106包括如下步骤：

61)利用随机矩阵法对当前时刻的航迹假设进行状态更新；

设k时刻量测值集合为n_k为k时刻量测值的个数，在随机矩阵的框架下，给出如下的量测模型结构：

式中，为量测，为系统的量测矩阵，x_k为k时刻的运动状态，为独立高斯白噪声；

运动状态的更新为：

式中，为k时刻的运动状态的估计值，为对k时刻的目标状态的一步预测值，K_k为滤波增益，I_d为单位矩阵，为Kronecker乘积，G_k为估计误差，P_k为k时刻的运动状态的协方差的估计值，P_k|k-1为对k时刻的目标状态的协方差的一步预测值，S_k为新息协方差矩阵；

根据正态分布的性质可以得到E[x_k|Z_k]，即对k时刻的目标状态的跟踪结果；

62)利用随机矩阵法对当前时刻的航迹假设进行扩展形态更新；

基于量测模型结构，可以得到扩展形态的更新为：

式中，为对k时刻的目标扩展形态的估计值，为对k时刻的目标扩展形态的一步预测，B_k为形态观测矩阵，为k时刻量测数据的协方差的n_k-1倍，n_k为k时刻的量测的个数，为对k时刻的目标扩展形态的自由度的估计值，为对k时刻的目标扩展形态的自由度的一步预测；

根据逆威沙特分布的性质可以得到E[X_k|Z_k]，即对k时刻的目标扩展形态的跟踪结果。

9.根据权利要求1所述的算法，其特征在于，所述步骤S107具体如下：

71)若某个航迹在当前时刻没有与任何量测群关联，将其生命值减一；

72)遍历航迹，若航迹生命值为0，则将航迹终止标志置为1，否则将航迹终止标志置为0；

73)对于航迹终止标志为0的航迹删除，不再进行输出；

74)对于航迹终止标志为1的航迹，若航迹历史关联次数小于3次，则暂时将航迹进行保留，但不输出；

75)对于航迹终止标志为1的航迹，若航迹历史关联次数大于等于3次，则将航迹输出。