跟踪系统分配方法介绍- MATLAB和Simulink万博1manbetx - 万博1manbetx,s manbetx 845,万博尤文图斯

跟踪系统分配方法导论

背景

在多目标跟踪(MTT)系统中，一个或多个传感器在一次扫描中从多个目标生成多个检测。要跟踪这些目标，一个基本步骤是将这些检测正确地分配给跟踪器中维护的目标或轨迹，以便这些检测可以用于更新这些轨迹。如果目标或检测的数量很大，或者不同的分配假设之间存在冲突，分配检测是具有挑战性的。

根据赋值的维度，赋值问题可以分为:

二维赋值问题-赋值n目标米观察。例如，一个传感器在一个时间步长内生成6个检测，分配5个跟踪。
S-D赋值问题-赋值n目标到一组(米₁，米₂，米_3.，…)的观察。例如，将5个音轨分配给来自一个传感器的6次检测，同时来自另一个传感器的4次检测。这个例子是一个典型的三维分配问题。

为了说明分配问题的基本思想，考虑一个简单的二维分配例子。一家公司试图把3个工作分配给3个工人。由于工人的经验水平不同，并不是所有的工人都能以同样的效率完成每一项工作。每个工人完成每项工作的成本(以小时为单位)由表中所示的成本矩阵给出。分配规则是每个工人只能从事一项工作，一项工作只能由一个工人从事。为了保证效率，这项分配的目标是使总成本最小化。

工人	工作
工人	1	2	3.
1	41	72	39
2	22	29	49
3.	27	39	60

在这个例子中，由于工人和工作的数量都很小，所以所有可能的分配都可以通过枚举得到，并且最小成本解突出显示在带有分配对(1,3)，(2,2)和(3,1)的表中。在实践中，随着分配的规模变大，二维分配很难获得最优解。对于S-D分配问题，在实际应用中可能无法得到最优解。

多目标跟踪中的二维分配

在二维MTT分配问题中，跟踪器试图将多个航迹分配给多个检测。除了上面提到的维度挑战，还有其他一些因素可以显著改变任务的复杂性:

目标或检测分布——如果目标分布稀疏，将目标与其对应的检测相关联相对容易。然而，如果目标或检测是密集分布的，分配就会变得模糊，因为将一个目标分配给一个检测或另一个附近的检测几乎不会在成本上产生任何差异。
被发现的概率(P_d)的传感器-P_d描述如果目标在传感器的视场内，则该目标被传感器检测到的概率。如果P_d的值很小，那么在传感器扫描过程中，真正的目标可能不会引起任何检测。因此，由真实目标所代表的航迹可能会窃取其他航迹的检测。
传感器分辨率——传感器分辨率决定了传感器从两个目标中区分检测的能力。如果传感器分辨率较低，那么两个接近的目标可能只产生一次探测。这违反了通常的假设，即每个检测只能分配到一个轨道，并导致轨道之间不可解决的分配冲突。
传感器的杂波或虚警率—虚警引入了额外的可能分配，因此增加了数据分配的复杂性。

分配任务的复杂性可以决定应用哪些分配方法。在Sensor Fusion and Tracking Toolbox™工具箱中，针对三个不同的跟踪器使用了三种二维分配方法:

trackerGNN-采用全局最近的数据分配方法
trackerJPDA-采用联合概率数据关联方法
trackerTOMHT-采用面向跟踪器的多假设跟踪方法

注意，每个跟踪器顺序处理来自传感器的数据，这意味着每个跟踪器只处理每次检测一个传感器的分配问题。即使采用这种处理方法，仍然可能存在太多的分配对。为了减少需要分配的跟踪和检测对的数量，经常使用门控技术。

选通

门控是一种筛选机制，用来确定哪些观测结果是更新现有轨迹的有效候选，并利用预测轨迹的分布信息消除不可能的探测到轨迹对。为了在当前扫描时为航迹建立验证门，从前一步预测当前步骤的估计航迹。

例如，跟踪器在时间上确认一个跟踪t_k同时接收到几次检测t_k＋1．在时间上形成一个验证门t_k＋1时，跟踪器首先需要获取预测测量值为:

${\overset{＾}{y}}_{k + 1} ＝ h （ {\overset{＾}{x}}_{k + 1 | k} ）$

在哪里是否从时间上预测了轨迹估计t_k而且给定跟踪状态，输出预期测量的测量模型。观测残差向量为

$\tilde{y} ＝ y_{k + 1} - {\overset{＾}{y}}_{k + 1}$

在哪里y_k＋1是实际测量值。建立栅极边界，检测残差协方差年代用来形成一个椭球形验证门。椭球门在测量空间中建立空间椭球区域，用马氏距离定义为:

$d^{2} （ y_{k + 1} ）＝ {\tilde{y}}^{T} {年代}^{- 1} \tilde{y} \leq G$

在哪里G是门控门限，您可以根据分配要求指定它。增加阈值可以将更多的检测合并到门中。

在每个磁道的分配门建立后，每个检测的门控状态y_我（我= 1,…,n)可以通过比较其马氏距离来确定d²（y_我)与门控阈值G．如果d²（y_我) <G，然后检测y_我是门内的轨道和将考虑协会。否则，与跟踪相关联的检测的可能性被删除。在图1中，T₁表示预测的轨迹估计，并且O₁- - - - - -O₆是六次探测。根据门控结果，O₁，O₂,O_3.都在图中的验证门内。

检测和验证门

全局最近邻(GNN)方法

GNN方法是一种单假设赋值方法。对于每一个新的数据集，目标是将全局最近的观测值分配到现有的轨迹上，并为未分配的检测创建新的轨迹假设。

如果航迹之间不存在关联冲突，则可以很容易地解决GNN分配问题。跟踪器只需要将一个跟踪分配给它最近的邻居。然而，当一个航迹的验证门内有多个观测值或一个观测值位于多个航迹的门中时，就会发生冲突情况(参见图2)。为了解决这些冲突，跟踪器必须计算一个成本矩阵。

带有关联冲突的GNN

GNN方法的成本矩阵的元素包括从轨迹到检测的距离和其他你可能想要考虑的因素。例如，一种方法是定义观测之间的广义统计距离j跟踪我为:

$C_{我 j} ＝ d_{我 j} + \ln （ | {年代}_{我 j} | ）$

在哪里d_ij是马氏距离，ln(|年代_ij|)，残差协方差矩阵行列式的对数，用于惩罚预测不确定性较大的轨迹。

对于图2中给出的分配问题，下表显示了一个假设的成本矩阵。未通过门控测试的不允许的分配用x表示(实际上，不允许的分配的代价可以用较大的值表示，例如1000)。

跟踪	观察
跟踪	O₁	O₂	O_3.	O₄
T₁	9	6	X	6
T₂	X	3.	10	X
T₂	8	4	X	X

对于这个问题，可以通过枚举找到突出显示的最优解。检测O_3.未分配，因此跟踪器将使用它创建一个新的试探性跟踪。对于更复杂的GNN分配问题，需要更精确的公式和更高效的算法来获得最优或次优解。

一般的二维分配问题可以形成如下形式。给定成本矩阵元素C_ij，找一份作业Z= {z_ij}，最小化

$J ＝ \sum_{我＝ 0}^{n} \sum_{j ＝ 0}^{米} C_{我 j} z_{我 j}$

受两个限制:

$\begin{array}{l} \sum_{我＝ 0}^{米} z_{我 j} ＝ 1 ， \forall j \\ \sum_{j ＝ 0}^{n} z_{我 j} ＝ 1 ， \forall 我 \end{array}$

如果跟踪我被分配给观察j,然后z_ij= 1。否则,z_ij= 0。z_我0= 1表示跟踪的假设我不分配给任何检测。同样的,z_0j= 1表示假设观察j没有分配给任何轨道。第一个约束意味着每个检测只能分配给一个轨道。第二个约束意味着每个轨迹只能分配给一个检测。

Sensor Fusion and Tracking Toolbox提供多种功能，解决二维GNN分配问题:

assignmunkres—使用Munkres算法，保证最优解，但可能需要更多的计算操作。
assignauction—使用拍卖算法，该算法需要较少的操作，但可能会收敛到最优或次优解决方案。
assignjv-使用Joker-Volgenant算法，该算法也会收敛于最优或次优解，但通常具有更快的收敛速度。

在trackerGNN，您可以通过指定赋值财产。

2-D分配问题万博尤文图斯的K最佳解

由于分配问题的不确定性，仅获得一个解(最优或次优)可能是不够的。为了解释关于轨迹和探测之间的分配的多个假设，需要多个次优解。万博尤文图斯这些次优解称为分配问题的K个最优解万博尤文图斯。

K个最佳解通常是通过改万博尤文图斯变前面提到的任何赋值函数得到的解来获得的。然后，在下一步，K最佳解算法去除原始解中的一个轨迹到检测对，并找到下一个最佳解。例如，对于这个成本矩阵:

$［ \begin{matrix} 10 & 5 & 8 & 9 \\ 7 & \times & 20. & \times \\ \begin{array}{l} \times \\ \times \end{array} & \begin{array}{l} 21 \\ 15 \end{array} & \begin{array}{l} \times \\ 17 \end{array} & \begin{array}{l} \times \\ \times \end{array} \\ \times & \times & 16 & 22 \end{matrix} ］$

每一行表示与跟踪相关的成本，每列表示与检测相关的成本。如所强调的，最优解决方案是(7,15,16,9)，代价是47。在下一步中，删除第一对(对应于7)，次优解为(10,15,20,22)，代价为67。之后，去掉第二对(对应于15)，次优解为(7,5,16,9)，代价为51。经过几个步骤，五个最好的解决方案是:万博尤文图斯

解决方案	成本
(7、15、16、9)	47
(7、5、17、22)	51
(7、15、8、22)	52
(7,21,16,9)	53
(7、21、17、9)	53

看到使用Assignkbest找到万博尤文图斯五个最佳解决方案示例，该示例使用assignkbest函数求K个最优解。万博尤文图斯

联合概率数据关联(JPDA)方法

GNN方法对航迹进行刚性分配，而JPDA方法应用软分配，使得航迹验证门内的检测都可以根据其关联概率对航迹进行加权贡献。

例如，对于图1所示的门控结果，JPDA跟踪器计算轨迹之间关联的可能性T₁和观察O₁，O₂,O_3.．假设这三个观测值的关联概率为p₁₁，p₁₂,p₁₃，以及相对于轨迹的残差T₁是，,,分别。然后是与轨迹相关的残差的加权和T₁是:

${\tilde{y}}_{1} ＝ \sum_{j ＝ 1}^{3.} p_{1 j} {\tilde{y}}_{1 j}$

在跟踪器中，采用加权残差来更新跟踪T₁在跟踪滤波器的校正步骤中。在过滤器中，未分配的概率，p₁₀，也需要更新轨道T₁．有关更多细节，请参见离散扩展卡尔曼滤波的JPDA校正算法．

当不同轨道的作业之间有冲突时，JPDA方法需要多一个步骤。例如，在下图中，trackT₂冲突T₁关于观察的任务O_3.．因此，要计算关联概率p₁₃的联合概率T₂没有分配给O_3.(即T₂分配给O₆或未分配)必须解释。

两个验证门重叠

面向轨迹的多假设跟踪(TOMHT)方法

与JPDA方法不同(JPDA方法使用加权和组合验证门内的所有检测)，TOMHT方法基于门内的检测生成多个假设或轨迹分支，并在扫描步骤之间传播高似然分支。传播之后，可以根据新的检测集对这些假设进行测试和修剪。

例如，对于图1所示的门控场景，TOMHT跟踪器考虑以下四个假设:

不进行检测T₁产生了假设T₁₀
分配O₁来T₁产生了假设T₁₁
分配O₂来T₁产生了假设T₁₂
分配O_3.来T₁产生了假设T₁₃

给定给定的阈值，跟踪器将计算每个假设的可能性，丢弃概率低于阈值的假设。假设，如果只是p₁₀而且p₁₁都大于阈值，那么只有T₁₀而且T₁₁传播到下一步以进行检测更新。

多目标跟踪中的S-D分配

在S- d赋值问题中，赋值S的维数大于2。注意，所有三个跟踪器(trackerGNN，trackerJPDA,trackerTOMHT)顺序处理来自每个传感器的检测，这导致了二维分配问题。然而，有些应用需要跟踪器同时处理来自多个传感器扫描的同时观察，这就需要解决S-D分配问题。同时，S-D赋值在静态数据融合等跟踪应用中得到了广泛的应用，它对检测数据进行预处理，然后将其输入到跟踪器中。

静态数据融合中存在一个S-D分配问题年代同时从多个传感器对监视区域进行扫描，每次扫描由多个检测组成。检测源可以是真实目标，也可以是虚警。目标是检测未知数量的目标并估计它们的状态。例如，如图4所示，三个传感器扫描产生6个检测。相同颜色的检测属于同一扫描。由于每次扫描产生两次探测，在监视区域可能有两个目标。要在不同的分配或关联可能性之间进行选择，请评估成本矩阵。

监察区域

成本的计算可以依赖于许多因素，如检测之间的距离和每个检测的协方差分布。为了说明基本概念，假设表中给出了几个假设的分配成本[1]．

分配的假设	第一次扫描观察（O_{1 x}）	二次扫描观察（O_{2 x}）	第三次扫描观察（O_{3 x}）	成本
1	0	1	1	−10.2
2	1	2	0	−10.9
3.	1	1	1	−18.0
4	1	1	2	−14.8
5	1	2	1	−17.0
6	2	0	1	−13.2
7	2	0	2	−10.6
8	2	2	0	−11.1
9	2	1	2	−14.1
10	2	2	2	−16.7

在表中，0表示在该扫描中没有检测到相关的音轨。假设表中未显示的假设由于门控而被截断或由于成本高而被忽略。为了简洁地表示每个轨迹，使用c_ijk表示观察协会的费用我在扫描1中，j在扫描2中k扫描3。例如，对于赋值假设1，c₀₁₁= -10.2。表中有几个轨迹假设与其他假设相冲突。例如，两个最有可能的作业，c₁₁₁而且c₁₂₁不兼容，因为它们在扫描1和3中共享相同的观察结果。

解决S-D分配问题的目标是找到最可能兼容的分配假设来解释所有的检测。当年代然而，≥3时，问题就会随着跟踪和检测的数量以指数速度扩展(NP-hard)。拉格朗日松弛法通常用于求解S-D分配问题的最优或次最优解。

简要介绍三维赋值的拉格朗日松弛法

三扫描的数据有若干个米₁，米₂,米_3.分别观察。表示扫描1、2和3的观察值为我，j,k,分别。例如,我= 1, 2，…，米₁．使用z_ijk的轨迹形成假设O_1我，O_2j,O_3.k．如果假设成立，那么z_ijk= 1;否则,z_ijk= 0。正如前面提到的,c_ijk是用来表示成本的z_ijk协会。c_ijk为0表示假警报，为负数表示可能的关联。S-D优化问题可表述为:

$J （ z ）＝ \underset{我， j ， k}{最小值} \sum_{我＝ 0}^{米_{1}} \sum_{j ＝ 0}^{米_{2}} \sum_{k ＝ 0}^{米_{3.}} c_{我 j k} z_{我 j k}$

受三个限制:

$\begin{array}{l} \sum_{我＝ 0}^{米_{1}} \sum_{j ＝ 0}^{米_{2}} z_{我 j k} ＝ 1 ， \forall k ＝ 1 ， 2 ， .．. ，米_{3.} \\ \sum_{我＝ 0}^{米_{1}} \sum_{k ＝ 0}^{米_{3.}} z_{我 j k} ＝ 1 ， \forall j ＝ 1 ， 2 ， .．. ，米_{2} \\ \sum_{j ＝ 0}^{米_{2}} \sum_{k ＝ 0}^{米_{3.}} z_{我 j k} ＝ 1 ， \forall 我＝ 1 ， 2 ， .．. ，米_{1} \end{array}$

优化函数选择关联以使总成本最小化。这三个约束确保每个检测都被考虑到(包括在分配中或作为虚警报处理)。

拉格朗日松弛法通过使用拉格朗日乘子松弛第一个约束来解决这个三维分配问题。定义一个新函数l（λ):

$l （ λ ）＝ \sum_{k ＝ 0}^{米_{3.}} λ_{k} ［ \sum_{我＝ 0}^{米_{1}} \sum_{j ＝ 0}^{米_{2}} z_{我 j k} - 1 ］$

在哪里λ_k，k= 1, 2，…，米_3.是拉格朗日乘子。减去l从原始的对象函数J（z)得到一个新的对象函数，第一个约束在k是放松的。因此，三维分配问题简化为二维分配问题，可以用任意一种二维分配方法求解。有关更多细节，请参见[1]．

拉格朗日松弛法允许第一个约束被轻微违反，因此只能保证一个次优解。然而，对于大多数应用程序，这就足够了。为了指定解的精度，该方法使用解间隙，它定义了当前解和潜在乐观解之间的差异。间隙是非负的，较小的解间隙对应的解更接近最优解。

传感器融合和跟踪工具箱提供assignsd用拉格朗日松弛法求解S-D分配。类似于K最佳二维分配求解器assignkbest，工具箱还提供了一个K最佳S-D赋值求解器，assignkbestsd，用于为S-D分配问题提供多个次优解。万博尤文图斯

看到分布式同步无源传感器跟踪S-D分配在静态检测融合中的应用。

另请参阅

参考文献

[1]布莱克曼，S.和R.波波利。现代跟踪系统的设计与分析。Artech House雷达图书馆，波士顿，1999年。

[2] Musicki D.和R. Evans。联合综合概率数据协会:JIPDA。航空航天和电子系统汇刊。2004年第3期第40卷第1093 -1099页。