论文地址：https://arxiv.org/abs/2103.07889

代码地址：https://github.com/daip13/LPC_MOT

介绍和相关工作

主要贡献：

1. 提出了一个新颖的可学习框架建模MOT为proposal的产生、打分和选择推理的过程。
2. 为proposal的生成提出了一个图聚类策略，有效减少计算的同时保证提出了proposal的质量。
3. 使用一个GCN为proposal进行打分，直接优化proposal，而非优化两两之间的匹配，通过GCN的信息聚合能力，增加预测的准确性。

遮挡问题任然是MOT中的一个任务的难题，在拥挤的环境中更加难以处理。传统的方法通过各种启发式或者手工设计的机制来处理遮挡。例如MHT方法中使用的将数据关联进行适当的延迟，保持假设有效性，直到模糊匹配消失或被解决。在基于网络流的工作中，会将数据关联建模为一个图，节点代表检测，边代表节点间的可能性连接。这样通过连接非连续的节点对来处理遮挡。但是这两种方法都需要对不同任务手工设计阈值之类的参数，相较于所有任务灵活性差。

受Faster R-CNN以及一个聚类方法的启发，作者提出了将MOT算法：1）产生proposal；2）使用GCN对proposal打分然后选择。

过程如下图所示，如下图（b）给定一小段轨迹的集合，作者提出的生成模型会产生包含覆盖所有检测的完整tracklet的proposals集合，当然其中也包含多个不同目标组成的proposal，包括污染proposal。然后如图（c）使用GCN来为所有的Proposal打分并排序。然后如图（d），对于每个proposal及其得分，使用一个推理算法产生轨迹输出，满足一个检测分配一个轨迹的原则。

除了解决检测问题，之前也有很多工作在数据关联方面做文章。但是大多数之前在优化成对的亲密度所作的工作，在得到高复杂度的计算的同时，所提升的精度并不值得。最近几个工作在整个关联算法上实现端到端优化，例如Deep Hungarian Net (DHN)将不可微的HA算法进行可微变换。

作者使用无向图来建模数据关联任务，类似于Faster RCNN的思路，提出proposal，为proposal打分，最后剪枝实现追踪。

方法

给定一系列视频帧及其相应的检测$D=\{d_1,\dots ,d_k\}$，$k$所有帧的总检测数。每个检测$d_i=(o_i,p_i,t_i)$，分别表示边界框原始像素，2D图像的坐标，时间戳。一条时间序列的轨迹表示为${\mathcal{T}}_i=\{d_{i_1},\dots ,d_{i_{n_i}}\}$,$n_i$表示形成轨迹$i$的所有检测数目，任务的目的是找到包含所有目标的最优ID分配的m个轨迹的集合${\mathcal{T}}_{\ast }=\{{\mathcal{T}}_1,\dots ,{\mathcal{T}}_m\}$。

框架

如上图所示，作者所提框架包含四个主要的阶段：

数据预处理：
为了减少proposal生成过程中的模糊性和计算复杂度，轨迹片段的生成通过连接相邻两帧的检测。这些轨迹片段作为之后任务的基础模块。

Proposal生成：
如上图b所示，采用一个图$G=(v,\epsilon )$，$v:=\{v_1,\dots ,v_n\}$,$\epsilon \subset v\times v$来表示构建的轨迹数据$\mathcal{T}$。其中图中的一个子集$P_i=\{v_i\}$就是一个Proposal，每个目标至少有一个完美的proposal。从图中探索所有的Proposal来获得最优的proposals$\{{\hat{P}}_i{\}}_{i=1}^m$太费力，作者提出了一个可替代的图聚类策略，通过模拟自下而上的聚类过程，获得proposal质量和计算力之间的平衡。

Proposal打分：
对于所有的Proposal集合$P=\{P_i\}$，需要进行计算他们的相应得分并进行排序，从而选择轨迹的最优表示。

得分可以定义为准确率和召回率的组合：$$\mathrm{score}\left({\mathcal{P}}_i\right)=\mathrm{rec}\left({\mathcal{P}}_i\right)+w\cdot \mathrm{prec}\left({\mathcal{P}}_i\right)\text{\hspace{1em}(1)}$$$$\mathrm{rec}\left({\mathcal{P}}_i\right)=\left|{\mathcal{P}}_i\cap {\hat{\mathcal{P}}}_i\right|/\left|{\hat{\mathcal{P}}}_i\right|\text{\hspace{1em}(2)}$$$$\mathrm{prec}\left({\mathcal{P}}_i\right)=\{\begin{array}{ll}1,& \text{ if }n\left({\mathcal{P}}_i\right)=1\\ 0,& \text{ otherwise }\end{array}\text{\hspace{1em}(3)}$$
$w$是权重平衡参数，${\hat{\mathcal{P}}}_i$是所有标签$major(P_i)$的检测的GT框集合，$major(P_i)$是proposal$P_i$的主要标签。$|\cdot |$代表求数量，$n(P_i)$表示Proposal$P_i$中标签的个数。准确率prec代表纯度，召回率rec代表proposal$P_i$和GT${\hat{\mathcal{P}}}_i$的匹配程度。

准确率可以通过二分交叉熵损失进行训练学习，但是召回率不遍历所有的proposal就很难学习，作者发现标准化轨迹长度$(|P_i|/C,C是标准化常数)$在准确率很高的情况下，这个参数和召回率成正相关，所以可以通过近似这个参数估计召回率，将网络集中训练提高Proposal准确率。

轨迹推理：
类似于检测中的NMS，通过排序好的proposals进行最终轨迹${\mathcal{T}}_{\ast }$的推理，这里作者采用了一种简单的去重叠算法实现。

数据预处理

作者使用tracklets $\mathcal{T}=\{{\mathcal{T}}_1,\dots ,{\mathcal{T}}_n\}$作为图构建的基础单元，n表示tracklets的数目，远少于检测数目$k$。

首先使用CNN对于每个检测$d_i$提取相应的ReID特征$a_i$。然后基于外貌时间和位置信息这三个亲密度计算两个检测或者检测和tracklets之间的总体亲密度。最终，通过基于亲密度使用匈牙利算法连接检测产生tracklets。tracklets的纯度直接影响后续的推理实验。

这里作者使用一个双向阈值策略，对于高亲密相关的使用高的阈值${\theta }_1$，使用低阈值${\theta }_2$避免关联存在相似亲密度的竞争对手。

迭代Proposal的生成

提出了一个逐渐生成所有proposal的策略，主要包括两个模块如上图：

Affinity Graph Construction 亲和图构造
每次迭代$i$，构建一个亲和图$G$建模所有顶点$V:=\{v_1,\dots ,v_n\}$间的相似度，$v_i=(a_i,t_i,p_i)$，$a_i$是一个proposa的平均ReID特征，$t_i=[t_i^s,\dots ,t_i^e]$表示proposal中检测的时间戳排序。$p_i=[p_i^s,\dots ,p_i^e]$为相应的二维图片坐标。顶点$(v_i,v_j)$之间的边的亲密度得分定义为基于时、空和外貌相似度的平均得分：
$$a_{ij}\left(v_i,v_j\right)=\left(s_{ij}^a\left({\mathbf{a}}_i,{\mathbf{a}}_j\right)+s_{ij}^t\left({\mathbf{t}}_i,{\mathbf{t}}_j\right)+s_{ij}^p\left({\mathbf{p}}_i,{\mathbf{p}}_j\right)\right)/3\text{\hspace{1em}(4)}$$$$s_{ij}^a\left({\mathbf{a}}_i,{\mathbf{a}}_j\right)=\left({\mathbf{a}}_i\cdot {\mathbf{a}}_j\right)/\left(\left|{\mathbf{a}}_i\right|\cdot \left|{\mathbf{a}}_j\right|\right)\text{\hspace{1em}(5)}$$
$$s_{ij}^t\left({\mathbf{t}}_i,{\mathbf{t}}_j\right)=\{\begin{array}{lr}\exp \left(-\mathbf{g}\left({\mathbf{t}}_i,{\mathbf{t}}_j\right)/{\sigma }_t\right)& \text{ if }\mathbf{g}\left({\mathbf{t}}_i,{\mathbf{t}}_j\right)>0\\ -inf,& \text{ otherwise }\end{array}\text{\hspace{1em}(6)}$$$$s_{ij}^p\left({\mathbf{p}}_i,{\mathbf{p}}_j\right)=\exp \left(-f\left({\mathbf{p}}_i,{\mathbf{p}}_j\right)/{\sigma }_p\right)\text{\hspace{1em}(7)}$$
$g(\cdot )$表示两定点间的最小时间距离，如果两节点在相同的时间戳上$\mathbf{g}\left({\mathbf{t}}_i,{\mathbf{t}}_j\right)=-1$，$f(\cdot )$代表顶点$v_i$的预测框中心和顶点$v_j$的开始框中心之间的欧氏距离，${\sigma }_t,{\sigma }_p$为控制参数。

Cluster Proposals
Proposals产生的基础想法是使用连接的成分来寻找聚类，为了保持早期聚类的纯度，限制聚类的最大尺存的阈值$s_{max}$。这个过程中，顶点可能会被过分碎片，分入多个聚类。第$i$个迭代产生的聚类作为下一次迭代的输入顶点节点。再这些聚类的基础上可以构建新的图，从而产生更大的聚类，最终所有的proposal$P=\{P_i\}$包括所有迭代产生的聚类。

纯度分类网络

该网络的主要目的是评估产生的Proposal $P$的准确度得分$\{prec(P_i)\}$。一个Proposal $P_i=\{v_i{\}}_{i=1}^{N_i}$有$N_i$个顶点，GCN将顶点的特征和子图的亲密度作为输入，预测$P_i$的纯净的概率，如下图，模型包括两部分：

特征编码设计：
对于每个检测$d_i$，直接使用CNN进行特征embedding $a_i$的提取。节点$v_i$的相应特征$a_i$使用其中所有检测特征的均值来表示。

每个proposal $P_i=\{v_i{\}}_{i=1}^{N_i}$都是按照每个顶点的开始时间戳进行按升序排列的，对于每对时间关联的tracklet $v_i$和$v_{i+1}$，节点$v_i$的结束时间戳和节点$v_{i+1}$的开始时间戳分别表示为$t_{e_i}$和$t_{s_i+1}$，时间戳中的边界框参数化为$(x_i,y_i,w_i,h_i)$和$(x_{i+1},y_{i+1},w_{i+1},h_{i+1})$，通过以下公式计算节点$v_i$的时空特征$s{t}_i$：

$${\mathbf{s}\mathbf{t}}_i=\{\begin{array}{rc}[\frac{2\left(x_{i+1}-x_i\right)}{w_i+w_i+1},\frac{2\left(y_{i+1}-y_i\right)}{h_i+h_{i+1}},\log \left(\frac{h_{i+1}}{h_i}\right)& \\ \log \left(\frac{w_{i+1}}{w_i}\right),\left(t_{s_{i+1}}-t_{e_i}\right)]\text{ if }i>0& \\ [1,0,0,0,0]& \text{ otherwise }\end{array}\text{\hspace{1em}(8)}$$

通过外貌特征和时刻特征，concat形成特征编码$f_i=concat(a_i,s{t}_i)$。

GCN设计：
如上获得了$P_i$的结点的特征${\mathbb{F}}_0\left({\mathcal{P}}_i\right)$。对于$P_i$的亲密度矩阵${\mathbb{A}}_0\left({\mathcal{P}}_i\right)$，使用一个全连接的$L$层图网络（图3a）计算：$${\mathbb{F}}_{l+1}\left({\mathcal{P}}_i\right)=\sigma \left(\mathbb{D}{\left({\mathcal{P}}_i\right)}^{-1}\cdot \left(\mathbb{A}\left({\mathcal{P}}_i\right)+\mathbb{I}\right)\cdot {\mathbb{F}}_l\left({\mathcal{P}}_i\right)\cdot {\mathbb{W}}_l\right)\text{\hspace{1em}(9)}$$
$\mathbb{D}\left({\mathcal{P}}_i\right)={\sum }_j{\mathbb{A}}_{ij}\left({\mathcal{P}}_i\right)$是对角的度矩阵。 ${\mathbb{F}}_l\left({\mathcal{P}}_i\right)$代表第$l$层的特征embedding。${\mathbb{W}}_l$是变换矩阵，σ是非线性激活函数。在顶层的特征embedding ${\mathbb{F}}_{\mathbb{L}}\left({\mathcal{P}}_i\right)$，$P_i$的所有顶点使用一个最大池化来获得最终结果。最终一个全连接层运用到$P_i$进行纯与不纯的分类。

公式9中所示，每层图网络就进行了计算每个顶点和其邻居的特征的带权均值和，通过${\mathbb{W}}_l$进行变换特征，最后将变换后的特征喂入激活函数三件事。如此的过程可以学习到每个proposal的内在一致性。

轨迹推理

获得了纯度分类的结果，可以通过公式1获得所有proposals的质量得分。通过一个简单的去重叠算法保证每个tracklet都可以被分配到一个独一无二的ID。

首先：对所有的proposals按照质量得分进行降序排序。
然后：从排名列表中序列化的为proposal中每个节点分配ID，并且去除所有proposal中已经被处理过的顶点。

实验