基于深度学习的多目标跟踪算法（上）：端到端的数据关联

©PaperWeekly 原创 · 作者｜黄飘

学校｜华中科技大学硕士生

研究方向｜多目标跟踪

最近基于深度学习的多目标跟踪算法越来越多，有用于特征提取的，有改进单目标跟踪器的，也有提升数据关联的。如果真的要总结的话那就太多了，所以我准备分类别进行介绍，这次我主要介绍端到端的数据关联方法。后期我会逐步整理这部分代码到我的 Github，相关 MOT 和数据关联的基础知识可以去我的专栏查看。

DAN

论文标题：Deep Affinity Network for Multiple Object Tracking

论文作者：ShiJie Sun, Naveed Akhtar, HuanSheng Song, Ajmal Mian, Mubarak Shah

备注信息：PAMI 2019

论文链接：https://arxiv.org/abs/1810.11780

代码链接：https://github.com/shijieS/SST.git

这是一篇创作于 2017.9，并刊登于 PAMI 2019 的端到端多目标跟踪框架，对于后续几篇文章都有着启示作用。DAN 框架 [1] 很简洁新颖：

作者提出这个框架的目的是将表观特征和数据关联算法结合形状端到端的联合框架，在 NVIDIA GeForce GTX Titan 上的效率为 6.7FPS，下面我结合文章内容具体地解析算法。

1.1 数据准备与增强

要实现端到端的训练，如何将多目标跟踪数据集整理出来是第一大难关。这里作者采用了单目标跟踪算法中常用的跨帧匹配方式，允许相隔 1~30 帧的的视频帧进行跨帧数据关联，这样就可以解决 MOT 样本数量不足的问题。

然而，视频类数据集还存在一个问题，即相邻帧的信息几乎一样，使得样本缺乏多样性。因此作者采用了几类数据增强方法：

作者在文中提到了三种数据增强方法：

• 光学扰动。即先将 RGB 图像转换到 HSV 格式，然后将 S 通道的每个值随机放缩 [0.7，1.5]，最后转换到 RGB 格式，并将值域约束到 0~255 或者 0~1；
• 图像扩展放缩。本质上就是图像随机放缩，但是为了保证输入尺寸大小一致，作者在图像四周增加 [1,1.2] 倍的 padding，padding 像素值为图像均值；

• 随机裁剪。基于裁剪比例 [0.8，1] 在原图上裁剪，不过要求无论怎么裁剪，图像上所有目标框的中心点一定不能丢失，最后再放缩至指定尺寸。

而作者在代码中实际上使用了更复杂的数据增强方法：

self.augment = Compose([
                ConvertFromInts(),
                PhotometricDistort(),
                Expand(self.mean),
                RandomSampleCrop(),
                RandomMirror(),
                ToPercentCoords(),
                Resize(self.size),
                SubtractMeans(self.mean),
                ResizeShuffleBoxes(),
                FormatBoxes(),
                ToTensor()
            ])

除去一些常规的数据类型转换和归一化操作，我们可以看到还多了一个随机水平镜像的操作RandomMirror,并且以上操作的概率为 0.3。

除此之外，熟悉 MOT Challenge 数据集的人应该知道，在该数据集中，无论目标是否可见都会标注，因此作者将可视度低于 0.3 的目标视为不可见，即认为不存在。另外，端到端的框架要保证输入输出的尺寸不变，因此作者设定了每一帧中出现的目标数量上限 Nm，如 80。

1.2 特征提取器

特征提取器作为网络的第一个阶段，由上面的图示可以知道，作者利用孪生网络结构，通过特征提取器处理指定两帧中出现的所有目标框。特征提取器的结构为 VGG 网络+自定义扩展的结构组成：

为了利用多尺度多感受野信息，作者取了以上 9 层的特征图信息，得到了长度为 520 的特征向量，即 60+80+100+80+60+50+40+30+20，可以看到 520 这个数据就是 9 层特征通道之和。不过文中作者并没有介绍是如何处理这些特征的，我们通过代码来观察：

def forward_feature_extracter(self, x, l):
    '''
    extract features from the vgg layers and extra net
    :param x:
    :param l:
    :return: the features
    '''
    s = list()

    x = self.forward_vgg(x, self.vgg, s)
    x = self.forward_extras(x, self.extras, s)
    x = self.forward_selector_stacker1(s, l, self.selector)

    return x
def forward_vgg(self, x, vgg, sources):
    for k in range(16):
        x = vgg[k](x)
    sources.append(x)

    for k in range(16, 23):
        x = vgg[k](x)
    sources.append(x)

    for k in range(23, 35):
        x = vgg[k](x)
    sources.append(x)
    return x

def forward_extras(self, x, extras, sources):
    for k, v in enumerate(extras):
        x = v(x) #x = F.relu(v(x), inplace=True)        #done: relu is unnecessary.
        if k % 6 == 3:                  #done: should select the output of BatchNormalization (-> k%6==2)
            sources.append(x)
    return x

def forward_selector_stacker1(self, sources, labels, selector):
    '''
    :param sources: [B, C, H, W]
    :param labels: [B, N, 1, 1, 2]
    :return: the connected feature
    '''
    sources = [
        F.relu(net(x), inplace=True) for net, x in zip(selector, sources)
    ]

    res = list()
    for label_index in range(labels.size(1)):
        label_res = list()
        for source_index in range(len(sources)):
            # [N, B, C, 1, 1]
            label_res.append(
                # [B, C, 1, 1]
                F.grid_sample(sources[source_index],  # [B, C, H, W]
                              labels[:, label_index, :]  # [B, 1, 1, 2
                              ).squeeze(2).squeeze(2)
            )
        res.append(torch.cat(label_res, 1))

    return torch.stack(res, 1)

从代码可以看到，9 层不同分辨率的特征图都通过采样操作降维了，其中``source表示的是特征图BxCxHxW，labels`表示的是一个框中心坐标 BxNx1x1x2，也就是说每个特征图都会采样每个框的映射位置。

因此最后通过得到就是 Bx(CxN) 的输出，也就是图中的 Nmx520，这个过程的确挺出乎我意料的。

1.3 亲和度估计

亲和度估计实际上就是特征相似度计算和数据关联过程的集成，第一步我们可以看到作者将两个 520xNm 大小的特征图变成了一个 1040xNmxNm 大小的亲和度矩阵，比较难理解：

这里我们观察一下作者的代码：

def forward_stacker2(self, stacker1_pre_output, stacker1_next_output):
    stacker1_pre_output = stacker1_pre_output.unsqueeze(2).repeat(1, 1, self.max_object, 1).permute(0, 3, 1, 2)
    stacker1_next_output = stacker1_next_output.unsqueeze(1).repeat(1, self.max_object, 1, 1).permute(0, 3, 1, 2)

    stacker1_pre_output = self.stacker2_bn(stacker1_pre_output.contiguous())
    stacker1_next_output = self.stacker2_bn(stacker1_next_output.contiguous())

    output = torch.cat(
        [stacker1_pre_output, stacker1_next_output],
        1
    )

    return output

可以看到，作者的处理方式也比较特征先分别将两个 520xNm 大小的特征图分别扩展维度变成了 520x1xNm 和 520xNmx1 的矩阵，然后分别复制 Nm 次，得到两个 520xNmxNm 矩阵，最后将通道合并得到 1040xNmxNm 大小的特征矩阵。随后利用一系列 1x1 卷积降维至 NmxNm大小。

作者在这里考虑了实际过程中出现的 FP 和 FN 情况，即目标轨迹无对应观测和观测无对应目标轨迹的场景，分别为关联矩阵的行列增加了一个 x 单元，用于存储这些情况，即 L：(Nm+1)x(Nm+1)。

其中最后一行和最后一列都填充为固定值，文中作者设定的是 10.

1.4 训练

为了方便损失函数的设计，作者将 L 拆解为 row-wise 何 column-wise 两种形式：M1：Nmx(Nm+1) 和 M2：(Nm+1)xNm。并分别采用行 softmax 和列 softmax 求得各自的联合概率分布 A1 和 A2 两种分配矩阵**。

这里做一个解释，对于增加了一列的 M1 矩阵，其针对的是第 t-n 帧的目标轨迹和第 t 帧观测的匹配，通过行 softmax 可以得到每个目标属于每个观测的概率，这是一个前向的匹配过程。反之 M2 就是一个反向的匹配过程。**

基于这种假设，作者设计了四种损失函数，分别是前向/反向损失、前向反向一致性损失和联合损失：

其中 L1 和 L2 是为了保证 L 和 A1/A2 矩阵尺寸一致所裁剪行列得到的矩阵。训练算法方面，作者采用的是 multi-step 的学习率下降策略，batchsize=8，epochs=120.

1.5 推理

通过以上分析我们可以知道的是，该网络通过输入两帧的目标信息可以得到亲和度矩阵 A=max(A1, A2)，然而这个矩阵并不是关联矩阵，更像是相似度矩阵，并不能直接得到跟踪结果。然而作者并没有将相似度矩阵转换为代价矩阵输入匈牙利算法：

从文章可以看到，作者将目标轨迹i的历史帧信息与当前帧第j个目标的亲和度求和了，但是如何使用的还是没说清，这一点我们在代码里面找到了：

def get_similarity_uv(self, t, frame_index):
    res_similarity = []
    res_uv = []
    for i, f in enumerate(t.f):
        if len(t.f) == TrackerConfig.max_track_node and i == 0:
            continue

        all_iou = self.recorder.all_iou[frame_index][f]
        all_similarity = self.recorder.all_similarity[frame_index][f]
        selected_box_index = t.uv[i, i]
        if selected_box_index == -1: # cannot find box in f frame.
            res_similarity += [0]
            res_uv += [-1]
            continue

        # combine the similarity with the iou
        selected_similarity = np.copy(all_similarity[selected_box_index, :])
        delta_f = frame_index - f
        if delta_f in TrackerConfig.min_iou_frame_gap:
            iou_index = TrackerConfig.min_iou_frame_gap.index(delta_f)
            selected_iou = (all_iou[selected_box_index, :] >= TrackerConfig.min_iou[iou_index]).astype(float)
            selected_iou = np.append(selected_iou, 1.0)
            selected_similarity = selected_similarity * selected_iou

        max_index = np.argmax(selected_similarity)
        max_value = all_similarity[selected_box_index, max_index]

        if max_index == all_similarity.shape[1] - 1: # new node
            max_index = -1
        res_uv += [int(max_index)]
        res_similarity += [float(max_value)]

    # get the representation box of this frame.
    res = {}
    for uv, s in zip(res_uv, res_similarity):
        # if s < 0.5:
        #     continue
        if uv not in res:
            res[uv] = [s]
        else:
            res[uv] += [s]

    if len(res.keys()) > 0:
        max_uv = max(res.keys(), key=(lambda k: np.sum(res[k])))
    else:
        max_uv = -1

    res_similarity += [1]
    res_uv += [max_uv]

    if max_uv == -1:
        t.age += 1
    else:
        t.age = 0

    return res_similarity, res_uv

可以看到的是，除了亲和度矩阵，作者还加入了 iou 信息作为 mask，然后利用 iou_tracker 的方式，采用贪婪算法，逐行取最大相似度的匹配，这种方式以及其变种我在之前的博客详细介绍过。没有引入其他的模块，如运动信息等，效果也不错：

DeepMOT

论文标题：How To Train Your Deep Multi-Object Tracker

论文作者：Yihong Xu, Aljosa Osep, Yutong Ban, Radu Horaud, Laura Leal-Taixé, Xavier Alameda-Pineda

备注信息：ICCV 2019 Tracktor++的作者团队，CVPR 2020

论文链接：https://arxiv.org/abs/1906.06618

代码链接：https://gitlab.inria.fr/yixu/deepmot

这篇 DeepMOT [2] 文章放在了 arxiv 上，作者团队与 ICCV 2019 的 Tracktor++ [3] 团队一致，不过这篇文章的创新性很高，内容也很精彩，所以我这里也详细介绍一下。

2.1 匈牙利算法形式演化

作者一开始就交代了原始匈牙利算法的算法形式：

其中 D 表示代价矩阵，这里叫距离矩阵，A 表示 0-1 分配矩阵，匈牙利算法的核心就是在保证每个轨迹最多只有一个观测，每个观测最多只有一个目标轨迹对应的前提下，是的代价最小。

紧接着，作者以 MOT 中常用的两个指标 MOTA 和 MOTP 为例进行微分化：

对于 MOTP，作者这里没有给出原始的形式，不过我们将距离矩阵看做 iou 信息就可以啦，即 MOTP 统计的是所有跟踪正确的轨迹的 IOU 平均值。这里我们不妨直接介绍 DeepMOT 的损失函数：

可以看到，作者直接借助 MOTA 和 MOTP 指标，通过将其微分化得到了损失函数。其中要微分化就要将 FP、FN、TP 和 ID Sw.等四个指标先微分化：

这里做一个解释，作者在设计关联矩阵的时候跟 DAN一样，增加了一行一列，所以 FP 就是新增的目标观测信息被误匹配到了已存在的目标轨迹上，即最后一列的数值之和，同理可得 FN。

对于 IDS，其意义在于目标轨迹中的身份切换次数，因此作者通过上一帧的关联 0-1 矩阵和当前帧估计的匹配矩阵 C 进行相乘。示例如下：

其中距离矩阵 D 的计算是根据关联结果，利用 iou 和欧氏距离计算而来：

从上图可以得到一个有意思的信息，即关联矩阵大小可以不固定，不用预设目标数量。

2.2 DHN网络设计

DHN 网络是一个单独设计的网络框架，其输入是目标轨迹和观测量的距离矩阵，在训练的时候作者直接采用了 public detections 作为目标轨迹，gt 作为观测。可以看到的是，作者通过两个阶段的特征变换，使得两两之间的相似度信息得到了充分交互。

这里作者设计了三种流程，一种是串行的 Sequential 模式，一种是并行的 Parallel 模式，最后一种是基于 U-Net 的形式，利用卷积网络进行交互。其中 row-wise 的意思是一行行的从 NxM 的距离矩阵中取向量，得到 1x(MN) 的向量。

而对于向量中各单元的交互，作者采用了 Seq2Seq 的 BiRNN 结构：

但是我从文中不明白的是，作者如何将一个 1x(MN) 的向量，通过 Seq2Seq 转换为 2HxNxM 的矩阵的。这里我去看了一下代码：

self.lstm_row = nn.GRU(element_dim, hidden_dim, bidirectional=biDirenction, num_layers=2)
self.lstm_col = nn.GRU(512, hidden_dim, bidirectional=biDirenction, num_layers=2)

# The linear layer that maps from hidden state space to tag space
if biDirenction:
    # *2 directions * 2 ways concat
    self.hidden2tag_1 = nn.Linear(hidden_dim * 2, 256)
    self.hidden2tag_2 = nn.Linear(256, 64)
    self.hidden2tag_3 = nn.Linear(64, target_size)
else:
    # * 2 ways concat
    self.hidden2tag_1 = nn.Linear(hidden_dim, target_size)

备注：element_dim为1，hidden_dim为 256。也就是说输入一个长为 NM的序列，得到 NMx512 的输出。

可以看到基于 Sequential 流程和 GRU 结构的框架效果最好，其中 WA 指的是准确率，MA 指的是未被分配到观测信息的比例，SA 指的是分配超过一个观测信息的比例。

2.3 实现细节

对于填充行列的固定值，作者采用的是 0.5，另外，由于关联矩阵是离散且稀疏的，所以作者首先通过 sigmoid 离散化 0-1 矩阵，然后基于关联矩阵中的 0-1 数量比例进行自适应的损失加权。

采用 RMSprop 优化器，初始学习率为 3e-4，每 2w iter 降低 5% 学习率，训练 20epochs，只用 6 小时。gt 是通过匈牙利算法生成的。

作者的底层多目标跟踪框架是 Tracktor++ 构建的，在此基础上加入了 ReID head，从而实现多任务的训练模式。其中 Re-ID 分支采用 ResNet50 网络结构，通过 triplet loss 训练。

除此之外，作者还尝试利用单目标跟踪算法 SiamRPN 和 GOUTRN 作为底层跟踪器进行实现，可以发现，DeepMOT 均有所帮助。

为了降低过拟合风险，作者还将标注的目标框信息进行一定尺度的放缩和平移，增大误差，模拟实际观测误差。

DMAN

论文标题：Online Multi-Object Tracking with Dual Matching Attention Network

论文作者：Ji Zhu, Hua Yang, Nian Liu, Minyoung Kim, Wenjun Zhang, and Ming-Hsuan Yang

备注信息：ECCV 2018

论文链接：https://arxiv.org/abs/1902.00749

代码链接：https://github.com/jizhu1023/DMAN_MOT

DMAN [4] 和 FAMNet [5] 我本来准备放到下一讲 SOT 专题来讲的，但是考虑到篇幅平衡，并且这两个都可以扯到端到端的 SOT+Data Association 框架，就还是加进来了。

DMAN算法是基于以下四个方向展开的讨论：

• 通过空间注意力模块让网络更加注意前景目标：
• 基于循环网络，利用时间注意力机制分析目标轨迹中各个历史信息的权重：

• 利用SOT跟踪器，缓解MOT中由于遮挡、观测信息质量不高导致的目标丢失等情况，增强鲁棒性。

其中空间注意力模块很简单，就是深度学习中常见的 mask，利用 mask 与原特征图进行相乘。而时间注意力网络，则是将目标轨迹中的所有的历史信息与当前观测信息进行匹配，最后加权判断是否匹配成功。

而 SOT 跟踪器的底层算法是单目标跟踪中知名的 ECO 算法，不过作者考虑到背景和前景的样本不平衡问题，引入代价敏感参数 q(t) 对其进行了进一步的改进：

之所以我要将 DMAN 算做端到端的数据关联框架，是因为这个框架实现的是 1：N 的数据关联，这里有两层含义：

• 一个观测对应N个轨迹历史信息；

• 一个观测对应N条目标轨迹，这里是以batch的形式实现的，勉强沾边吧。

FAMNet

论文标题：FAMNet: Joint Learning of Feature, Affinity and Multi-Dimensional Assignment for Online Multiple Object Tracking

论文作者：Peng Chu, Haibin Ling

备注信息：ICCV 2019

论文链接：https://arxiv.org/abs/1904.04989

相比于 DMAN，FAMNet [4] 对于端到端数据关联算法的集成更加紧密：

通过观察网络可以看到，FAMNet 的流程是 SOT->Affinity->Data Association->post process，其中它的核心在于通过局部的关联形式完成了 K 帧的联合数据关联训练。

4.1 Affinity Subnet

作者将 SOT 孪生网络和亲和度网络合并，SOT backbone 作为特征提取器，SOT 输出的置信图作为亲和度依据。下面我们详细分析一下这个网络结构。

作者这里提出了一个新概念anchor candidate，这里指的是当前帧的目标，对应上图中中间部分 k=1 的分支，至于途中所提到的数字2，这里指的是当前帧中的第二个目标。

对于指定目标，通过对当前帧和前后帧扩展区域的裁剪，基于两个孪生网络进行两次 SOT 跟踪流程，从而得到上下两个置信图输出。

这其中还有三个Detection Attention Mask，初步理解就是将观测信息变成 mask，而观测信息的确定是通过目标序号来确定的，所以可以看到观测信息并非与当前目标对应。

最终得到的亲和度就是两个 SOT 置信图得到的信息和 detection mask 得到的亲和度之和，在上面的例子里面存在 3x3x3 对亲和度，但是由于两个非 `anchor frame 并没有直接参与匹配，所以图中显示的是  C222。

这里作者借鉴的是 IJCAI 2019 的一篇论文的策略 [6]：

4.2 R1TA Power Iteration Layer

对于关联假设的生成，FAMNet 采用了与前文一致的策略：

那么从亲和度矩阵到数据关联的集成，作者同样借鉴了 IJCAI 2019 的那篇论文的策略 [6]，首先将匈牙利算法进行了重构：

即将整体的数据关联 n:m，变成了 n 份小型的数据关联的联合作用，对于这个关系的转换，可以参照论文 [6]：

其中 z_212 指的是第一帧中的第二个目标、第二帧中的第一个目标和第三帧中的第二个目标的整体关联结果是否为真，其中任意一对不成立都会变成  0。然后基于 R1TA Power Iteration 过程，将这种多次 SOT 过程组成一个完整的数据关联过程：

经过我们上面的讨论，这幅图里面的大多数的示意应该能懂，但是对于 Rank-1 tensor approximation 可能还有疑惑，文中也给出了解释，我感觉这两篇几乎就是理论和实践分开投了两个顶会。

可以看到，作者通过一个连续的外积公式来近似 k 阶关联矩阵，从而转换了匈牙利算法问题形式。作者也给出了迭代算法的前向反向公式：

可以注意到的是，这里面有一个除法因子，用作 L1 norm，作者也给出了它的求导转换，这里我就不再放了。

结果如下：

MPNTracker

论文标题：Learning a Neural Solver for Multiple Object Tracking

论文作者：Brasó G, Leal-Taixé L

备注信息：ICCV 2019 Tracktor++ 的作者团队，CVPR 2020

论文链接：https://arxiv.xilesou.top/pdf/1912.07515

代码链接：https://github.com/selflein/GraphNN-Multi-Object-Tracking

MPNTracker 在 MOT Challenge 各个榜单上都位于前列，不过近期有个别算法超过去了，但是它的各项指标性能依旧很高。这个算法框架很简洁，直接借助了图卷积网络中的消息传递机制，基于 Re-ID 和位置形状信息进行特征建模，不过我暂时对于图卷积不是很了解，所以就不做详细的介绍：

对于当前帧的每个目标，其消息传递方式的节点更新部分考虑了时间信息，即针对前面的帧和后面的帧，分开计算边的累加影响，利用链接的方式结合，而非累加的方式。

可以看到，整体结构很简单，就是网络的构建和特征的建模，其中网络构建部分我在之前的博客中进行了详细的介绍。其效果也很不错：

参考文献

[1] Sun S, Akhtar N, Song H, et al. Deep affinity network for multiple object tracking[J]. IEEE transactions on pattern analysis and machine intelligence, 2019.

[2] Xu Y, Ban Y, Alameda-Pineda X, et al. DeepMOT: A Differentiable Framework for Training Multiple Object Trackers[J]. arXiv preprint arXiv:1906.06618, 2019.

[3] Bergmann P, Meinhardt T, Leal-Taixe L. Tracking without bells and whistles[C]. in: Proceedings of the IEEE International Conference on Computer Vision. 2019. 941-951.

[4] Zhu J, Yang H, Liu N, et al. Online multi-object tracking with dual matching attention networks[C]. in: Proceedings of the European Conference on Computer Vision (ECCV). 2018. 366-382.

[5] Chu P, Ling H. Famnet: Joint learning of feature, affinity and multi-dimensional assignment for online multiple object tracking[C]. in: Proceedings of the IEEE International Conference on Computer Vision. 2019. 6172-6181.

[6]X. Shi, H. Ling, Y. Pang, W. Hu, P. Chu, and J. Xing. Rank-1 tensor approximation for high-order association in multi-target tracking. IJCV, 2019.

[7] Brasó G, Leal-Taixé L. Learning a Neural Solver for Multiple Object Tracking[J]. arXiv preprint arXiv:1912.07515, 2019.

点击以下标题查看更多往期内容： 

#投 稿 通 道#

 让你的论文被更多人看到 

如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。

总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。 

PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学习心得或技术干货。我们的目的只有一个，让知识真正流动起来。

📝 来稿标准：

• 稿件确系个人原创作品，来稿需注明作者个人信息（姓名+学校/工作单位+学历/职位+研究方向） 

• 如果文章并非首发，请在投稿时提醒并附上所有已发布链接 

• PaperWeekly 默认每篇文章都是首发，均会添加“原创”标志

📬 投稿邮箱：

• 投稿邮箱：[e-mail] 

• 所有文章配图，请单独在附件中发送 

• 请留下即时联系方式（微信或手机），以便我们在编辑发布时和作者沟通

🔍

现在，在「知乎」也能找到我们了

进入知乎首页搜索「PaperWeekly」

点击「关注」订阅我们的专栏吧

关于PaperWeekly

PaperWeekly 是一个推荐、解读、讨论、报道人工智能前沿论文成果的学术平台。如果你研究或从事 AI 领域，欢迎在公众号后台点击「交流群」，小助手将把你带入 PaperWeekly 的交流群里。