MLT解读

简介

在很多方法都在检测上做文章的时候，能看到MLT这样一篇在Public赛道做研究并取得相当好的效果的文章是很难得的，就像论文的标题一样，它直面了MOT目前针对二维图像的一个痛点，那就是遮挡问题尤其是密集人群场景下的遮挡问题。论文提出了一种基于图的near-online跟踪方法，该方法设计了一种检测multiplexing（多路复用）技术并设计了一种多标签图（multiplex labeling graph，MLG）模型，这种一个检测框可以拥有多个ID的复用思路是本文最大的创新点之一。此外，这篇文章还引入LSTM来对构建的MLG进行优化，实验证明其在多个数据集上达到了SOTA表现，在MOT Challenge公榜（public赛道，不使用私有检测，将研究重点放在跟踪问题上）成为了新的SOTA，最新的MOT17的全榜结果如下图，其实可以看到，在整个榜单上，它MOTA距离第一不算太多，IDF1和Frag这些比较依赖跟踪性能而不是检测性能的指标上相对于其他方法都是当之无愧的SOTA。

论文标题

Multiplex Labeling Graph for Near-Online Tracking in Crowded Scenes
论文地址

https://ieeexplore.ieee.org/document/9098857

在这里插入图片描述

介绍

多目标跟踪（multiple object tracking，MOT）是计算机视觉领域一个颇受关注的话题，其对于监控分析、远程控制等工业场景应用广泛。不同于车辆跟踪，只发生在固定的车道约束内，行人的移动往往是没什么约束的。因此行人跟踪会更加困难。TBD（tracking by detection）范式是目前MOT领域最常用的框架，它的思路分为两步，先是将每一帧上的目标检测出来，然后通过一定的度量指标对帧间的目标进行数据关联。很多基于TBD范式的MOT方法在人群稀疏的场景下效果不错，然而人群密集的场景下仍旧缺少比较高效的方法。

在这里插入图片描述

密集场景下跟踪的难点其实在于行人频繁的互动遮挡，为了分析行人之间的交互问题，论文中分析并定义了三种交互模式。gathering；side by side；dispersion。含义就是字面意思，其他复杂的交互都可以由着三种基本模式组合而成，如上图所示，当行人并排走的时候，遮挡也就发生了，这给跟踪带来了严重的干扰。

当然，当多个行人发生严重的遮挡时，检测器其实很难得到多个结果，因为他们离得太近了，因此检测器只会给出一个包裹整个范围的检测框，如下图所示，先忽略其两个id的双色框，其实这个检测框（下文简称bbox）包含两个目标，只是其中一个被遮挡了。这种单框输出是检测器的选择，因为对于目标检测这个不需要考虑时序信息的空间任务而言，那么“所见即所得”，那个位置当然只有一个可见目标。然而，对于跟踪这个需要时序信息的任务而言，两个目标空间上合二为一会在关联时造成和现有轨迹的一对多匹配问题。因此，现有的跟踪器通常有一个基本假设，那就是一个bbox就对应一个目标，从而一对多的关联任务被当作冲突处理问题对待，多个轨迹只有一个被保留，其他的都被移除（这样，由于大部分MOT方法都不会立即销毁轨迹，短暂的消失之后还会匹配回来）。

在这里插入图片描述

上述这种假设单框对单目标的假设存在一个严重的问题，如本节第一张图的b所示，两个行人不是图a这种轨迹的短暂交互，而是聚集之后一直并肩移动，其中一个人一直处于另一个人的遮挡下，且他们长时间没有分离开。这种情况下，检测器当然只会反馈一个bbox，这个bbox会被赋予一个轨迹ID，而另一个轨迹就彻底消失了。为了生成两个完整的轨迹，论文引入了一种检测复用方法来解决这个一对多关联问题并提出多标签图跟踪模型（MLG）。

在MLG模型中，图中的任意一个节点可以同时表示多个目标，也就是被赋予多个ID。同时，LSTM结构用来评估检测框的相似度以进行数据关联，基于LSTM用于运动和外观建模的模型结构分别为MAN和AAN。

MLG

这一节先来介绍一下MLG这个基于图的跟踪模型是如何实现的。首先，不同于其他的基于图的方法，论文从一个新的角度重新审视了交互过程中检测冲突的问题。大部分MOT方法都基于一个基本假设，每个bbox都表示现实世界地一个目标，实际上这在三维空间中是成立的，但是三维压缩到二维图像中就不一定了，因此，在二维空间中，多个轨迹共享一个bbox的情况是有理由的。

检测器生成的bbox作为基础节点来表示目标， $D=\left\{d_{1}, d_{2}, d_{3}, \ldots, d_{n}\right\}$ 表示视频中所有的检测结果集合，对每个 $d_i$ ，它的宽高为 $w_i,h_i)$ ，位置为 $x_i,y_i)$ ， $c_i$ 表示置信度，此外， $\left(a_{i, 1}, a_{i, 2}, \ldots, a_{i, 1536}\right)$ 一个1536维CNN特征向量用来描述 $d_i$ 的外观信息，这个向量由在Market1501上训练的PCB网络产生。

图的构建

假定第t帧之前的轨迹已经生成了，MLG是一个滑窗内的有向图 $G=\{V ; E\}$ ，如下图所示，该图沿着 $t - 1$ 帧到 $t + 2$ 帧构建，此时滑窗的窗口为3（实际上算法采用的窗口大小为20时效果较好，这部分后面说明）。

在这里插入图片描述

考虑到真实世界的情况和计算效率，在所有检测之间建边是没有必要的，而且，由于检测框已经被NMS处理，因此一帧内不存在一个目标有多个bbox的情况。因此，只需要链接不同帧的bbox即可构成轨迹。将滑窗范围内所有的检测bbox形成的节点组成的集合称为Node Set，将有关联的两个不同的节点之间的有向边组成的集合称为Edge Set，显然任意有向边的出发点应该在结束点之前的帧上。示例如上图所示，显然，这个边的形成是可以跨帧存在的，这不同于二分图匹配，而是一种滑窗内部的有约束全图匹配。

通过上面的分析，其实可以看到，图 $G$ 其实可以表示为一个严格的上三角矩阵如下，其中的上三角元素 $E_{i, j}$ 是一个 $n_i\times n_j$ 的矩阵用来描述第 $i$ 帧的 $n_i$ 个检测框和第 $j$ 帧的 $n_j$ 个检测框之间的关联。下三角部分之所以都是 $0$ 矩阵是因为有向边只会在时间线上从前向后存在。

$\left[\begin{array}{cccc} 0 & E_{t-1, t} & E_{t-1, t+1} & E_{t-1, t+2} \\ 0 & 0 & E_{t, t+1} & E_{t, t+2} \\ 0 & 0 & 0 & E_{t+1, t+2} \\ 0 & 0 & 0 & 0 \end{array}\right]$

漂移（Drift）在目标跟踪中一直是一个问题，随着目标的外观变化，轨迹逐渐偏离GT是很常见的现象。论文中通过设置较高的阈值来保证通过边关联的检测来自同一个目标，阈值的确定基于目标的位置关系和目标的外观相似度。具体如下式，其中 $t_{ij}$ 是阈值指示器用来决定两个bbox是否关联到一起。两个bbox $d_i$ 和 $d_j$ 之间当前仅当 $t_{ij}=1$ 的时候构建边。阈值由两部分组成：运动和外观， $\tau_{m}$ 是一个为运动信息设置的自适应阈值，它设置为两个bbox的最大宽度 $\max \left(w_{i}, w_{j}\right)$ ；另一个阈值被设置用来描述外观相似度，采用 $a_i$ 和 $a_j$ 的余弦距离作为指标， $\tau_{a}$ 设置为 $0.9$ 以避免漂移（注意，这里的 $a_i$ 表示检测框 $d_i$ 的外观向量）。

$\begin{aligned} t_{i j} &=t_{m, i j} \cdot t_{a, i j} \\ t_{m, i j} &=\left\{\begin{array}{ll} 0, & \left\|\left(x_{i}, y_{i}\right),\left(x_{j}, y_{j}\right)\right\|_{2}>\tau_{m} \\ 1, & \left\|\left(x_{i}, y_{i}\right),\left(x_{j}, y_{j}\right)\right\|_{2} \leq \tau_{m} \end{array}\right.\\ t_{a, i j} &=\left\{\begin{array}{ll} 0, & \cos \left(a_{i}, a_{j}\right)<\tau_{a} \\ 1, & \cos \left(a_{i}, a_{j}\right) \geq \tau_{a} \end{array}\right. \end{aligned}$

多标签优化

在图构建完成之后，MOT任务其实可以视作一个给节点安排标签的图优化问题，不同于其他图方法，论文中的方法不约束每个节点优化过程只拥有一个标签（指的就是人的ID），因此MLG中每个节点同时可以拥有多个标签，这也是MLG名为multiplex labeling graph的由来。对整个视频的跟踪其实通过一个滑动窗口完成，如帧 $1$ 到帧 $k$ ，帧 $k$ 到帧 $2 k - 1$ ，这里的 $k$ 就是窗口大小，整个跟踪框架如下图所示。

在这里插入图片描述

上图描述的是跟踪的大体过程，其中彩色的实心圆表示已经确认的检测框、白色实心圆表示未确认的检测框（确不确认表示是否链接到轨迹上），虚线圆则表示误检。MLG上做跟踪其实就是在滑窗内将未确认的检测框关联到已经存在的轨迹上或者形成新的轨迹。

因为下面关于图优化的叙述比较复杂，作者这里先引入了几个概念，将节点分为如下四种，在滑窗内其定义如下：

Discrete Node，指的是没有任何关联节点的节点，它的入度和出度都是0；
Initial Node，指的是一个节点在帧 $k$ 上，它仅仅关联到 $k$ 帧后的帧上的节点，它的入度为0。窗口内第一帧上的节点不是discrete node，而是initial node。
Terminal Node，指的是一个节点在帧 $k$ 上，如果它仅仅关联到 $k$ 帧前的帧上的节点，它的出度为0。同上，窗口内最后一帧上的节点不是discrete node，而是terminal node。
Intermediate Node，指的是不属于上述三种节点的节点。

在MLG中，一个节点同时可以表示真实世界的多个目标，为了描述这个属性，为其定义了multiplex degree（多路复用度，简称MD）来表征一个节点表示的目标数目。考虑到现在的检测器精度都不低，一个bbox不可能包含太多的目标，因此设置了 $d_max$ 来表示最大多路复用度（maximum multiplex degree，MMD），来限制一个节点表示的目标数目。MLT这个方法中， $d_max$ 被设置为2且得分阈值设置为1。现在将跟踪任务定义为在MLG上找到拥有最大得分的最优路径，公式如下。

$\begin{array}{rl} \arg \max _{x} & E=\sum S_{i} x_{i} \\ & \forall v_{i} \in V, \quad D\left(v_{i}\right) \leq d_{\max } \\ & x_{i}=0,1 \end{array}$

上面这个公式中， $S_i$ 表示路径 $i$ 的得分，而 $x_i$ 表示是否路径 $i$ 被选中， $D(V_i)$ 表示节点 $v_i$ 的多路复用度（下文简称MD），MMD用 $d_max$ 表示。下图表示各种节点的转换机制，当一个检测得到的未定义节点进入窗口，它会被依据关联关系划分为不同的类型，这个类型会随着滑窗转换。

在这里插入图片描述

上图是真个MLG优化算法，它的输入是图 $G$ 而输出是轨迹集 $T$ ，算法描述相对比较直白，这里就不多解释了。下图是MLG求解的一个示例，图中共有5条轨迹形成，其中track-4是新轨迹，track-1和track-2在第 $t$ 帧共享同一个检测框，这在现实世界的表现就是这两个人在帧 $t$ 发生了遮挡，但随后两人分开了。

在这里插入图片描述

LSTM目标关联

此前提到的最优化公式中， $S$ 作为得分被安排给MLG中每个路径来评估其为真实世界轨迹的概率，这个得分（score）由两部分组成，分别是运动因子 $S_m$ 和外观因子 $S_a$ ，最终的score由两者的和 $S=S_{m}+S_{a}$ 表示。这里为候选轨迹分配score的过程实际上是一个数据关联问题，论文引入了使用LSTM的关联打分方法，不同于此前的IOU打分或者外观打分。

基于LSTM诞生了两者模型思路，分别是生成式模型和判别式模型，前者根据检测预测现有轨迹未来的位置和外观，后者则对当前帧给出每个检测框属于现有轨迹的概率。考虑到训练数据集的尺度，文中采用判别式模型的思路，构建LSTM网络进行关联度量。

由于运动信息和外观信息差别较大，因此设计了两个网络分别处理，前者为motion association network（MAN），后者为appearance association network（AAN）。首先来看MAN，它用来评估候选轨迹的运动特征，它是如下图所示的一个sequence-to-one型的网络结构，它的输入是 $n$ 个四维向量，输出是这 $n$ 个检测框属于同一个目标的概率。输入是 $n$ 个bbox的标准化的运动特征，具体对检测 $d_i$ 而言，运动特征为下式，其中 $W$ 和 $H$ 表示视频的宽高，而 $\mu$ 和 $\sigma$ 表示每个维度的均值和标准差。输出的正概率作为 $S_m$ 。

$\left(\frac{\frac{x_{i}}{W}-\mu_{x}}{\sigma_{x}}, \frac{\frac{y_{i}}{H}-\mu_{y}}{\sigma_{y}}, \frac{\frac{w_{i}}{W}-\mu_{w}}{\sigma_{w}}, \frac{\frac{h_{i}}{H}-\mu_{h}}{\sigma_{h}}\right)$

在这里插入图片描述

同样的，AAN也是一个sequence-to-one型网络，其结构如下图，输入是 $n$ 个1536维外观特征向量，输出同样是 $n$ 个检测框属于同一个目标的概率，输入的外观特征同样经过了标准化。输出的正概率作为 $S_a$ 。

在这里插入图片描述

就这样，对一个路径 $p_i$ ，依据MAN和AAN计算其得分 $S_i=S_{m,i}+S_{a,i}$ ，因此这个得分的取值范围是从0到2。

最后，作者为了训练这两个网络，使用了两个额外数据集CVPR19 challenge和PathTrack，它们的数据量比较充足，对这两个数据集作者进行了一些预处理以方便模型的训练，这部分可以参考原论文。

实验

作者主要在MOT16和MOT17上进行实验，首先验证了MLT框架的可行性，在baseline基础上的最大改进就是单节点多标签策略，采用不同的滑动窗口大小的结果如下表，实验表明，效果提升是非常显著的，而且一般MMD设置为2即可。

在这里插入图片描述

上图是作者做的一个可视化，我这里只分析第一行，图a两个目标逐渐接近，最后遮挡其中一个目标，通过多标签技术，在图b时检测框拥有两个目标ID，最后，图c上两人分开，检测框也带着ID分离。这表明，MLT对于遮挡的鲁棒性很强。

接着，对参数进行了一些分析，比如窗口大小、MMD设置数值等，结果如下。

在这里插入图片描述

最后，使用公开检测打榜，在MOT16和MOT17上结果如下，它在多个跟踪相关的指标上都实现了新的SOTA。此外，榜单上的MLT_p为使用私检的MLT版本，它在MOTA达到了70.6且IDF1为72.1，此外，MLT方法的IDSw数量大幅减小，这证明轨迹的稳定性时很强的。

在这里插入图片描述

总结

抛开速度不谈，MLT其实是一个非常具有创新性的MOT方法，它采用单检测多标签这个开创性的想法，非常针对性地处理了密集人群场景下的遮挡问题，在关于ID等跟踪方面的指标大幅度提升。MLT在视频处理领域如监控分析任务上有巨大的潜力，值得工业界的关注，尽管由于它时near-online方法几乎无法用于realtime跟踪，但是为MOT的研究开辟了新的道路。