摘要：本文介绍多目标跟踪MOT算法当中的关联association模块，association模块在MOT中起到了承上启下的作用，在MOT的框图当中，如果是以kalman跟踪作为base, 那么关联模块一般位于预测之后，更新之前，如下图所示，关联构建起了track和
本文介绍多目标跟踪MOT算法当中的关联association模块，association模块在MOT中起到了承上启下的作用，在MOT的框图当中，如果是以kalman跟踪作为base, 那么关联模块一般位于预测之后，更新之前，如下图所示，关联构建起了track和measurement之间的匹配问题，是整个链路至关重要的一步：
根据应用的不同，关联算法可以分为很多种，本文聚焦于传统的rule-base的关联方案，不涉及AI-base的关联方案，AI-base的关联方案最近几年发展非常迅速，是实现整个感知模块端到端很重要的一个环节，我会考虑在后面的文章中来专门介绍这一块，此次我们讨论的重点聚焦于传统的关联算法，本文将介绍四种传统的关联算法，分别为：全局最近邻算法，联合概率数据关联，多假设跟踪，全局数据关联，这几种代表性的方案都有深厚的论文基础，如果不想过于理论地深入每一篇论文的话，可以阅读MATLAB的help center网页文档中的“Introduction to Assignment Methods in Tracking Systems”, 介绍了MATLAB中已经实现的几种关联算法总体其篇幅不大，比很多国内的知乎和CSDN要好很多，不过该文档主要是聚焦在关联中的assignment的策略，association包括两个子模块分别是gating+assignment,其中gating相对比较简单一点，说人话就是为每个track目标设置一个关联门限，在门限内的measurement才会考虑为候选的关联参与后续的assignment，常见的gating关联波门有三种，分别是扇形波门，矩形波门，圆形或球形波门，其中扇形波门主要用于设定极坐标系中的gating ROI，矩形波门主要用于设定笛卡尔坐标系中的gating ROI（扇形波门和矩形波门还是在欧式距离空间做评估）, 圆形或球星波门主要是用于衡量马氏距离中的gating ROI(马氏距离相比于欧氏距离会除以自身数据分布的协方差矩阵，相当于对原始坐标系进行了旋转和缩放，旋转操作是为了解相关，缩放是为了平衡量纲):
下面我们基于MATLAB的该文档，再次整理和对比一下上述提到的四种关联算法：
1.全局最近邻：全局最近邻GNN(global nearest neighbor)是多目标跟踪关联中最常见的方案，对应的先验约束为每一个track都有唯一的measurement与其对应，不能出现一对多或者多对一的情况，因此其在经过gating之后优化的全局最优值可以通过遍历cost matrix来实现，cost matrix中超过gating阈值的单元格，赋值为一个非常大的数值，gating内的单元格就赋值为其对应的马氏距离或者欧式距离，如下表所示：
全局遍历cost matrix寻找assignment的极值是最保险的方案，该方案的代表是Munkres算法，可以保证输出全局最优解，代价就是耗时稍长一些，MATLAB还提供了次优的方案提高效率，缺点就是可能会陷入局部最小值，比如auction以及Jonker-Volgenant算法，可以根据自己的偏好去选择。另外值得注意的是，很多MOT的描述所使用的匹配算法的时候采用的是全局最近邻，但是可能起了一个其他的名字匈牙利匹配，Kuhn-Munkres算法等，其实只要是在围绕二分图匹配来构建assignment问题的都是全局最近邻匹配。
2.联合概率数据关联：JPDA和GNN最大的区别是JPDA不再是基于二分图来构建assignment问题，在JPDA关联中一个track可以和多个measurement关联，而一个measurement也可以贡献给多个track，因此在JPDA中的关联不像GNN中那么的硬，其采用的是一种软关联的策略，即gating门限内所有的measurement都以一定的权重贡献给track，贡献的多少取决于关联概率，比如对于上图的(T1o1, o2, o3)来说，可以构成四个事件：
由于上述的四个事件构成了track T1的一个完备的事件集，因此四个事件的加和应该为1，紧接着对上述四个事件的概率做归一化，就可以得到每个事件标准化之后的关联概率，如下所示：
通过上式就可以计算出三个测量点的权重，从而可以通过加权和构建出一个全新的测量点来更新当前的track目标，但是往往我们无法直接得到上式，因为：
在gating之后，我们往往只能得到一个对关联的似然概率，可以式通过马氏距离也可以是通过其他的方式，这种释然概率是一种概率密度的表达，或者你可以把他理解成上述三个观测属于当前track的相对概率，但不是绝对概率，如下表所示：
那么能否直接使用上表的likehood释然概率带入到上式（1）中来完成JPDA权重的计算呢，答案是可以的，因为cost matrix中的值本身就是相对概率的度量，因此归一话之后就是绝对概率，但是这里面会存在一个矛盾，就是track本身就是绝对概率，是不许要参与归一化的，或者换句话说track的存在概率和measurement的likehood不是一个量纲，因此你需要对（1）式做一些修改来对齐量纲，修改之后的公式如下所示：
当然你也可以把上式中的λ当作超参，λ越大代表你对于观测参与更新的信心越弱，越小代表对于观测参与更新的信心越强，当λ==0的时候上述的三个观测点可以构建一个100%的加权测量点，如果我们直接用公式（2）来获得的权重来更新track目标，那么这个方法就叫做PDA，我们设置λ=0之后，经过PDA算法更新后的cost matrix如下：
实际上PDA算法只考虑到了cost matrix中的一行，对于其他行的信息是没有考虑到的，这一点就是其和JPDA算法的区别！
接下来我们解析JPDA我们会进一步多出哪些步骤，在上图中O3明显是一个共享的测量点，那么对于O3来讲，我们就不能够将它对应的0.08的likehood直接代入到上式（2）中，我们需要在O3的likehood前面乘上一个O3属于T1的条件概率P(O3∈T1)，这个概率怎么求呢，这里面又牵扯到关于测量点O3的一个完备事件集：
同样我们要对上述的概率做归一化，归一化的公式如下所示：
上市中的λ同样是为了对齐量纲的，然后我们采用（3）式的权重继续更新cost matrix中第三列的值，更新的公式如下所示：
为了方便后续计算我们继续令λ=0，那么经过JPDA第二次更新之后的cost matrix的结果如下所示：
至此，上述表格得到的数值就是JPDA最终使用的权重，总体的过程分为两步，第一步是基于每一行进行更新，第二步是基于每一列进行更新，第一步是为了衡量同一个track目标所关联的所有measurement, 第二步是为了衡量同一个measurement关联的所有track目标，整个过程是满足贝叶斯概率推导的，理论上来说PDA是JPDA的一种.特殊情况，GNN是PDA的一种特殊情况，具体来说cost matrix中的没有被被两个及两个以上track以上共享的测量，此时PDA==JPDA, cost matrix中既没有没有被两个及两个以上track共享的测量，也没有一个track共享两个以两个以上的测量，此时JPDA==GNN, 单从这个角度上就可以理解为什么JPDA的适用场景会比GNN要更加的广泛，其可以向下兼容GNN的场景，像多传感器融合中同一个track目标会被不同的传感器产生多个观测，因此GNN是无法很好地适配这个场景地，JPDA就成了多传感器融合地入门算法，但是不是这并不能说明，单一的传感器就就需要适用JPDA的算法了，一般来说如果场景当中的目标越拥挤，传感器观测的噪声越大，ghost越多，升级JPDA的可能性就会越大，不过有一点需要说明JPDA的嵌入是会影响到kalman的更新的，Access Denied至此，上述表格得到的数值就是JPDA最终使用的权重，总体的过程分为两步，第一步是基于每一行进行更新，第二步是基于每一列进行更新，第一步是为了衡量同一个track目标所关联的所有measurement, 第二步是为了衡量同一个measurement关联的所有track目标，整个过程是满足贝叶斯概率推导的，理论上来说PDA是JPDA的一种.特殊情况，GNN是PDA的一种特殊情况，具体来说cost matrix中的没有被被两个及两个以上track以上共享的测量，此时PDA==JPDA, cost matrix中既没有没有被两个及两个以上track共享的测量，也没有一个track共享两个以两个以上的测量，此时JPDA==GNN, 单从这个角度上就可以理解为什么JPDA的适用场景会比GNN要更加的广泛，其可以向下兼容GNN的场景，像多传感器融合中同一个track目标会被不同的传感器产生多个观测，因此GNN是无法很好地适配这个场景地，JPDA就成了多传感器融合地入门算法，但是这并不能说明，单一的传感器就就不需要适用JPDA的算法了，一般来说如果场景当中的目标越拥挤，传感器观测的噪声越大，ghost越多，升级JPDA的可能性就会越大，不过有一点需要说明JPDA的嵌入是会影响到kalman的更新的，可以参考MATLAB的correctjpda来理解JPDA卡尔曼的更新方程，JPDA的理论基础非常早最早应用在声纳跟踪中，其推导过程参考1983年的论文《Sonar Tracking of Multiple Targets Using Joint Probabilistic Data Association》，本文不再展开。
3.多假设跟踪：来源：视见奇境
