论文地址：Learning a Neural Solver for Multiple Object Tracking

Learning a Neural Solver for Multiple Object Tracking

一、摘要
二、介绍
三、图问题解释追踪
四、消息传递追踪
五、实验
补充

一、摘要

本文是一个MOT的Offline方法。

图网络引入MOT带来了一个困难，就是如何构建一个结构化域，并且在其中进行操作。大多数基于学习的框架主要工作在于如何获得更好的外貌特征从而优化网络框架。论文提出了一个模型，通过在图域上直接操作，可以对检测集进行全局推理，并预测最终的解决方案。展现了MOT学习任务不一定需要局限于特征的提取，也可以运用在数据关联方面。

创新：

提出了一个基于MPN的MOT方法，利用问题的自然图结构，进行特征学习和最终解预测。
受传统MOT图公式启发，提出一个新颖的时间感知神经信息传递迭代更新步骤。

二、介绍

图网络视角下可以将MOT的关联看作是一个图划分的任务，将每个目标看作是一个结点，结点的边表示两个目标的之间的关联，可以表示两个目标间的相似度。
可以将它分解为两个过程：

为每条边分配一个代价，用以表示两个检测属于同一目标的可能性；
这些代价被用来在图优化框架中获得最优的图划分。

过去工作主要分为两类：

专注于图公式的；
专注于边代价函数计算的。

第一种，研究者专注于通过大量的信息建立复杂图的优化结构，以便编码检测之间的高阶依赖关系，某种程度上说，这种方式的边代价通常是手工设计的。

第二种采用简单框架的优化图结构，主要集中于利用深度学习技术来提升边权的定义。利用孪生神经网络可以编码可靠的目标间的成对交互，但无法解释场景中的高阶信息。两者都陷入了一个困境：MOT是否应该专注于提升图优化框架或者是特征提取。

本论文提出了在学习特征的同时，学习通过对整个图的推理来提供的解决方案。使用MOT的经典网络流公式来定义模型，直接预测图的最终分割成轨迹。过程中使用一个消息传递网络（MPN）来在图上组合深度特征为高阶信息，因此可以解释检测间的全局交互。

三、图问题解释追踪

我们首先引入网络流的MOT公式的概述，然后解释如何利用这种框架完成数据关联。然后解释如何利用这个框架将数据关联任务重新制定为一个学习问题。

问题设置

在DBT范式中，输入目标检测集 $O = \{o_1,...,o_n\}$ ， $n$ 表示一个视频的总共的所有帧总共目标数，每个检测表示为 $o_i = (a_i,p_i,t_i)$ 。 $a_i$ 表示边界框的原始像素， $p_i$ 表示二维坐标， $t_i$ 表示时间戳。一个轨迹都可以定义为一个时间顺序的检测集合 $T_i=\{o_{i_1},…,o_{i_{n_i }}\}$ , $n_i$ 表示轨迹i包含的的检测数目。MOT的目标是找到一个能最好的解释O的一个所有轨迹的集合 $T_* = \{T_1,...,T_m\}$ 。

这个问题可以用无向图 $G = (V, E)$ 来建模， $V:=\{1,…,n\},E ⊂ V×V$ 。每个节点 $i \in V$ 代表一个独一无二的检测 $o_1∈O$ ，通过构造边缘集合 $E$ ，使得不同帧中的每一对检测节点都是连通的，从而恢复检测缺失的轨迹。将原始检测分配到轨迹的任务可以被视为图中的节点分组为互不相连的组分的任务， $T_i=\{o_{i_1},…,o_{i_{n_i }}\}$ 可以被映射为一组节点 ${i_1,...,i_{n_i }\}$ 。

网络流公式

为每条边引入二元变量，当一条边连接的结点属于相同轨迹并且在轨迹内暂时连续的设置为1，剩下的都设置为0。一个轨迹 $T_i=\{o_{i_1},…,o_{i_{n_i }}\}$ 可以由边等价表示为 $\{(i_1,i_2),\dots,(i_{n_{i-1}},i_{n_i} \} \in E$ ，对应他在图中的时间顺序的路径。不同时间戳上的每一对结点 $(i，j)\in E$ ,定义二分变量 $y_{(i,j)}$ ：
$y_{(i, j)}:=\left\{\begin{array}{cc} 1 & \exists T_{k} \in \mathcal{T}_{*} \text { s.t. }(i, j) \in T_{k} \\ 0 & \text { otherwise } \end{array}\right.$
$y_{(i,j)} = 1$ 对应的 $(i, j)$ 是正项。假设轨迹结点不相交，即一个结点只能属于一个轨迹。因此 $y$ 存在线性限制,对于每个节点 $i \in V$ ：
$\sum_{(j, i) \in E \text { s.t. } t_{i}>t_{j}} y_{(j, i)} \leq 1 \tag{1}$
$\sum_{(i, k) \in E \text { s.t. } t_{i}<t_{k}} y_{(i, k)} \leq 1 \tag{2}$

从学习代价到预测方案

标准的方式是为每个边 $y_{(i,j)}$ 赋予一个代价 $c_{(i,j)}$ ，代表为正项的可能性。最终划分可以优化为：

本方法采用直接预测图像的正项边，例如直接预测二元变量y的真实值。如此，就将任务变成了一个边上的分类问题，标签即为y。这样，引进的网络流公式就将MOT任务作为了一个全学习任务。

四、消息传递追踪

我们的基于使用图公式训练一个不一样的框架，将多目标追踪作为边分类任务训练。输入检测集合，模型训练图中每个边的二元流值 $y$ 。在本模型提出的MPN网络中，外观和几何线索在整个检测集中传播，允许我们的模型对整个图形进行全局推理。
Pipeline由四个步骤组成：

图结构
对于视频中的检测集进行构图，节点对应检测，边对应节点的连接。
特征嵌入
使用一个卷积神经网络，作用于Bbox中的图像，初始化外貌特征嵌入。使用特征计算一个向量编码边界框的相对大小，位置和时间距离，然后喂入MLP网络，返回一个几何嵌入。
神经消息传递
在图上执行几次消息传递，在每一轮消息传递中，节点与其连接边共享外观信息，边与其关联节点共享几何信息信息。依赖整体图结构，返回更新后的包含高阶信息的节点嵌入和边。
训练
使用最终的边嵌入，进行正项\非正项的二元分类任务，使用交叉熵训练。
在测试时，我们使用我们的模型的每边预测作为目标流变量的连续近似(0到1之间)。使用一个简单的舍入方案，将得分二值化，或者最终轨迹（如下图1）。

MPN 消息传递网络

图 $G = (V, E)$ 。 $h_i^{(0)}$ 为节点 $i \in V$ 的节点嵌入。 $h_{(i,j)}^{(0)}$ 为一条边 $(i, j) \in E$ 的边嵌入。MPN的目的是学习一个函数，通过图来传递保留在节点和边的信息。
传递更新分为两步，通过节点更新边 $(v \to e)$ 以及通过边来更新节点 $(e \to v)$ ，迭代更新 $L$ 次。对于每个 $l ∈ \{1,...,L\}$ ，总体更新为：

$\rightarrow e) \quad h_{(i, j)}^{(l)}=\mathcal{N}_{e}\left(\left[h_{i}^{(l-1)}, h_{j}^{(l-1)}, h_{(i, j)}^{(l-1)}\right]\right) \tag{3}$

$\rightarrow v) \quad m_{(i, j)}^{(l)}=\mathcal{N}_{v}\left(\left[h_{i}^{(l-1)}, h_{(i, j)}^{(l)}\right]\right) \tag{4}$

$h_{i}^{(l)}=\Phi\left(\left\{m_{(i, j)}^{(l)}\right\}_{j \in N_{i}}\right)\tag{5}$
$N_e$ 和 $N_v$ 代表可学习函数，[.]代表concatt， $N_i∈V$ 代表节点i的邻接节点集， $Φ$ 代表顺序不变性操作，例如求和、最大化或者最小化。可以看出 $L$ 次迭代，最多获得了距离 $L$ 的迭代信息，有点类似于CNN的接受域。

时间感知消息传递

我们的目标是在节点更新过程中编码一个具体的MOT感应偏差。

公式 $4 ， 5$ 允许节点与领域交互，通过上下文聚合更新信息。公式 $1, 2$ 体现了流结构的限制，一个结点只连接一个过去节点和一个未来节点。将所有相邻的嵌入集合在一起，使得更新后的节点嵌入很难捕捉到这些约束是否被违反。

因此将MOT图的时序信息编码加入MPN公式，有利于网络学习。因此修改公式 $4 、 5$ , 通过将聚合分解为两部分，可以感知时间的更新规则：一部分为过去节点信息，一部分为未来节点信息。使用 $N_i^{fut}$ 和 $N_i^{past}$ 分别表示节点i过去和未来帧的邻域结点，相同的定义两个不同的MLP： $N_v^{fut}$ 和 $N_v^{past}$ 。在消息迭代更新的第 $l$ 层，对于每个节点 $i \in V$ ，先对他的所有邻域节点 $j∈N_i$ 计算 $p a s t$ 和 $f u t u r e$ 边到点的嵌入：
$m_{(i, j)}^{(l)}=\left\{\begin{array}{l} \mathcal{N}_{v}^{\text {past}}\left(\left[h_{i}^{(l-1)}, h_{(i, j)}^{(l)}, h_{(i)}^{(0)}\right]\right) \text { if } \quad j \in N_{i}^{\text {past}} \\ \mathcal{N}_{v}^{\text {fut}}\left(\left[h_{i}^{(l-1)}, h_{(i, j)}^{(l)}, h_{(i)}^{(0)}\right]\right) \text { if } \quad j \in N_{i}^{f u t} \end{array}\right. \tag{6}$

其中加入初始节点是为了让模型不会忘记初始特征。然后关于他们相对于节点i的位置（未来、过去）独立的聚合特征：
$h_{i, p a s t}^{(l)}=\sum_{j \in N_{i}^{p a s t}} m_{(i, j)}^{(l)} \tag{7}$
$h_{i, f u t}^{(l)}=\sum_{j \in N_{i}^{f u t}} m_{(i, j)}^{(l)} \tag{8}$
通过concat他们，计算最终的嵌入（图2c）:
$h_{i}^{(l)}=\mathcal{N}_{v}\left(\left[h_{i, \text {past}}^{(l)}, h_{i, f u t}^{(l)}\right]\right) \tag{9}$

特征嵌入

最初的输入MPN的嵌入由其他的BP网络获得：
外貌嵌入：依赖一个CNN网络，表示为 $N_v^{enc}$ 。每个检测 $o_i∈O$ ，对应图片补丁 $a_i$ 区域。 $o_i$ 相应的节点嵌入计算： $h_i^{(0)}:=N_v^{enc}(a_i)$ 。
几何嵌入：不同时间戳 $t_i,t_j$ 的两个检测 $o_i$ 和 $o_j$ ，考虑参数化他们的边界框（左上角坐标和长，宽） $x_i,y_i,h_i,w_i)$ ， $x_j,y_j,h_j,w_j)$ ，计算相对距离：
$\left(\frac{2\left(x_{j}-x_{i}\right)}{h_{i}+h_{j}}, \frac{2\left(y_{j}-y_{i}\right)}{h_{i}+h_{j}}, \log \frac{h_{i}}{h_{j}}, \log \frac{w_{i}}{w_{j}}\right)$
将这个向量、一个时间戳距离 $t_j-t_i$ 和外貌相对距离 concat到一起喂入神经网络 $N_v^{enc}$ 获得初始边嵌入 $h_{(i,j)}^{(0)}$ 。

训练推导

训练损失：使用MLP加上一个 $s i g m o d$ 输出单元的 $N_e^{class}$ ，用以表示类别。对于每个边 $(i, j) \in E$ 。通过喂入 $N_e^{class}$ 第l层迭代结果 $h_{(i,j)}^{(l)})$ 计算预测 $\hat y_{(i,j)}^{(l)}$ 。训练时对于最后一层嵌入的预测基于真实标签 $y$ 使用二分类交叉熵：
$\mathcal{L}=\frac{-1}{|E|} \sum_{l=l_{0}}^{l=L} \sum_{(i, j) \in E} w \cdot y_{(i, j)} \log \left(\hat{y}_{(i, j)}^{(l)}\right)+\left(1-y_{(i, j)}\right) \log \left(1-\hat{y}_{(i, j)}^{(l)}\right) \tag{10}$

$l_0 ∈ {1 ,...,L}$ , $w$ 表示一个衡量参数，用以衡量正项和非正项边之间的不平衡。

推理：基于最终的指标变量 $y \in [0, 1]$ 。由于时间注意的更新步骤，设置阈值 $0.5$ 的二值化也能够很好的满足公式 $1, 2$ 的限制。最后使用一个简单的贪婪舍入方案获得一个可行的二值输出。

五、实验

1.消融实验:

2. 基准评估

补充

1.正项非正项检测：

如果一个检测是非正项，他的输入输出流应当都为0，通过将1,2式右边替换为不等式获得：
$\sum_{(j, i) \in E \text { s.t. } t_{i}>t_{j}} y_{(j, i)} \leq y_{i} \tag{11}$
$\sum_{(i, k) \in E \text { s.t. } t_{i}<t_{k}} y_{(i, k)} \leq y_{i} \tag{12}$
该式子可以看出当 $y_i=0$ （非正项）时候，节点i的两条边都为 $0$ 。 $y_i=1$ 时候，这个限制等价于公式 $1, 2$ 。

2.舍入解决方案

阅读心得：Learning a Neural Solver for Multiple Object Tracking