深度多目标跟踪算法综述

基于深度学习的算法在图像和视频识别任务中取得了广泛的应用和突破性的进展。从图像分类问题到行人重识别问题，深度学习方法相比传统方法表现出极大的优势。与行人重识别问题紧密相关的是行人的多目标跟踪问题。本文对深度多目标跟踪的算法进行了综述。
原文来源于SigAI

在多目标跟踪问题中，算法需要根据每一帧图像中目标的检测结果，匹配已有的目标轨迹；对于新出现的目标，需要生成新的目标；对于已经离开摄像机视野的目标，需要终止轨迹的跟踪。这一过程中，目标与检测的匹配可以看作为目标的重识别，例如，当跟踪多个行人时，把已有的轨迹的行人图像集合看作为图像库(gallery)，而检测图像看作为查询图像(query)，检测与轨迹的匹配关联过程可以看作由查询图像检索图像库的过程。如图1。

图1：把检测图像看作查询图像(query)，行人轨迹中的图像看作图像库(gallery),多目标跟踪中的匹配过程可以看作为行人重识别。

与传统的行人重识别不同的是，行人多目标跟踪中的检测与行人轨迹的匹配关联问题更加复杂，具体表现在下面三个方面：首先，多目标跟踪中的目标轨迹是频繁发生变化的，图像样本库的数量和种类并不固定。其次，检测结果中可能出现新的目标，也可能不包括已有的目标轨迹。另外，检测图像并不像传统行人重识别中的查询图像都是比较准确的检测结果，通常，行人多目标跟踪场景下的检测结果混杂了一些错误的检测(false-alarms)，而由于背景以及目标之间的交互，跟踪中的行人检测可能出现图像不对齐、多个检测对应同一目标、以及一个检测覆盖了多个目标这些情况。如图2中所示为ACF行人检测算法的结果。

如何扩展深度学习在行人重识别问题中的研究成果到多目标跟踪领域，研究适用于多目标跟踪问题的深度学习算法是具有挑战性的问题。近年来，在计算机视觉顶级会议和期刊上，研究者从各方面提出了一些解决方案，发表了一些新的算法试图解决这个问题。本文将和大家一起对基于深度学习的视觉多目标跟踪算法进行总结和归纳，以帮助理解基于深度学习框架的多目标跟踪算法的原理和相对于传统算法的优势。

图2：多目标跟踪场景下行人的检测结果。

绿色矩形框表示存在的检测结果不准确的情况。蓝色矩形框是检测结果基本准确的示例。当目标特征与检测器模型样本分布相差较大时，存在检测失败的情况。

2、基于深度学习的多目标跟踪算法分类

多目标跟踪算法按照轨迹生成的顺序可以分为离线的多目标跟踪和在线的多目标跟踪算法。离线方式的多目标跟踪算法通常构造为目标检测关系的图模型，其中设计和计算检测之间的相似度或者距离度量是决定图模型构造正确性的关键。在线方式的多目标跟踪算法根据当前检测观测，计算与已有轨迹的匹配关系，计算合适的匹配度量决定了匹配的正确性。因此，无论是离线方式的多目标跟踪还是在线方式的多目标跟踪算法，学习检测结果的特征并计算匹配相似度或者距离度量都是多目标跟踪算法的关键步骤。

基于深度学习的多目标跟踪算法的主要任务是优化检测之间相似性或距离度量的设计。根据学习特征的不同，基于深度学习的多目标跟踪可以分为表观特征的深度学习，基于相似性度量的深度学习，以及基于高阶匹配特征的深度学习(如图3)。

图3：按照深度学习目标和应用对基于深度学习的多目标跟踪算法进行分类。

利用深度神经网络学习目标检测的表观特征是简单有效的提升多目标跟踪算法的方法。例如利用图像识别或者行人重识别任务中学习到的深度特征直接替换现有多目标跟踪算法框架中的表观特征[1]，或者采用深度神经网络学习光流运动特征，计算运动相关性[2]。采用深度学习提升多目标跟踪算法更加直接的方法是学习检测之间的特征相似性，比如设计深度网络计算不同检测的距离函数，相同目标的检测距离小，不同目标的检测距离大，从而构造关于检测距离的代价函数[3]。也可以设计二类分类代价，使相同目标的检测特征匹配类型为1，而不同目标的检测特征匹配类型为0,从而学习并输出(0,1]之间的检测匹配度[4]。如果考虑已有轨迹与检测之间的匹配或者轨迹之间的匹配，采用深度学习方法可以用于设计并计算轨迹之间的匹配相似度，这种方法可以认为是基于深度学习的高阶特征匹配方法。采用深度学习计算高阶特征匹配可以学习多帧表观特征的高阶匹配相似性[5]，也可以学习运动特征的匹配相关度[6]。

下面我们对一些基于深度学习的多目标跟踪算法进行概要介绍。

3、深度视觉多目标跟踪算法介绍

3.1 基于对称网络的多目标跟踪算法

一种检测匹配度量学习方法是采用Siamese对称卷积网络，以两个尺寸相同的检测图像块作为输入，输出为这两个图像块是否属于同一个目标的判别[3]。通常有三种拓扑形式的Siamese网络结构，如图4。

图4：三种Siamese网络拓扑结构。第一种结构，输入A和B经过相同参数的网络分支，对提取的特征计算他们的距离度量作为代价函数，以使得相同对象的距离接近，而不同对象的距离变大。第二种结构，输入A和B经过部分相同参数的网络分支，对生成的特征进行合并，新的特征进行多层卷积滤波之后输入代价函数作为输出。第三种结构，对输入A和B叠加组合作为新的网络输入，通过网络滤波生成输出。

经过实验表明，第三种网络结构能够生成更好的判别结果。因此，在文献[3]中，Lealtaixe等人采用第三种拓扑形式的Siamese网络训练并计算两个检测的匹配相似度，原始的检测特征包括正则化的LUV图像I1和I2，以及具有x,y方向分量的光流图像O1和O2，把这些图像缩放到121x53，并且叠加到一起构成10个通道的网络输入特征。卷积网络由3个卷积层(Conv-Layer)、4个全连接层(FC-Layer)以及2元分类损失层(binary-softmax-loss)组成，如图5。损失函数为：

其中 Φ(d1，d2)表示两个检测d1，d2，经过卷积之后的输出特征。y表示是否对应相同目标，如果d1，d2来自同一个目标的检测，y=1；否则y=0。

为了学习这个网络，作者从真实跟踪数据中抽取训练样本，从利用检测算法得到同一个轨迹的检测对作为正样本，从不同轨迹中得到检测作为负样本，为了增加样本多样性，增强分类器的泛化能力，负样本还包括从检测周围随机采集的重叠率较小的图像块。

学习过程采用经典的带有动量的随机梯度反向传播算法。最小批大小选择为128，学习率初始为0.01。通过50个回合的训练，可以得到较为优化的网络参数。

在Siamese网络学习完成之后，作者采用第六层全连接网络的输出作为表观特征，为了融合运动信息，作者又设计了6维运动上下文特征：尺寸相对变化，位置相对变化，以及速度相对变化。通过经典的梯度下降提升算法学习集成分类器。

图5：采用Siamese对称网络学习表观特征相似度，并通过基于梯度下降提升算法的分类器融合运动特征，得到融合运动和表观特征的相似度判别。并利用线性规划优化算法得到多目标跟踪结果。

多目标跟踪的过程采用全局最优算法框架，通过对每两个检测建立连接关系，生成匹配图，计算他们的匹配状态。通过最小代价网络流转化为线性规划进行求解。

3.2 基于最小多割图模型的多目标跟踪算法

上述算法中为了匹配两个检测采用LUV图像格式以及光流图像。Tang等人在文献[2]中发现采用深度学习计算的类光流特征(DeepMatching)，结合表示能力更强的模型也可以得到效果很好的多目标跟踪结果。

在文献[2]中，作者通过观察目标跟踪问题中的检测结果，发现仅仅考虑两帧之间的检测匹配不是最佳的模型表示。如图6，由于存在很多检测不准确的情况，同时考虑图像之间以及图像内部的检测匹配关系，并建立相应的图模型比仅仅考滤帧间检测匹配的图模型具有更广泛的表示能力。

图6：上图是三帧图像中的检测结果，为了建立更准确的匹配模型，除了建立两帧之间的匹配关系，还需要考虑同一幅图像内，是否存在同一个目标对应多个检测的情况。下图是构造的帧间及帧内连接图模型。

类似于最小代价流模型求解多目标跟踪算法，这种考虑了帧内匹配的图模型可以模型化为图的最小多割问题，如下公式所示：

上式中Ce表示每个边的代价，这里用检测之间的相似度计算。x=0表示节点属于同一个目标，x=1反之。这个二元线性规划问题的约束条件表示，对于任何存在的环路，如果存在一个连接x=0，那么这个环上的其他路径都是x=0。即，对于优化结果中的0环路，他们都在同一个目标中。所以x=1表示了不同目标的分割，因此这个问题转化为了图的最小多割问题。对于最小代价多割问题的求解，可以采用KLj算法进行求解[7]。

现在的问题是如何计算帧内及帧间检测配对的匹配度量特征。作者采用了深度学习算法框架计算的光流特征(DeepMatching)作为匹配特征[8]。图7是采用DeepMatching方法计算的深度光流特征示例。

图7: 利用DeepMatching算法计算的深度光流特征，蓝色箭头表示匹配上的点对。

基于DeepMatching特征，可以构造下列5维特征：

其中MI,MU表示检测矩形框中匹配的点的交集大小以及并集大小，ξv和ξw表示检测信任度。利用这5维特征可以学习一个逻辑回归分类器。并得到是相同目标的概率Pe，从而计算公式(2)中的代价函数：

为了连接长间隔的检测匹配，增强对遮挡的处理能力，同时避免表观形似但是不同目标检测之间的连接，Tang等人在最小代价多割图模型的基础上提出了基于提升边(lifted edges)的最小代价多割图模型[9]。基本的思想是，扩展原来多割公式(2)的约束条件，把图中节点的连接分为常规边和提升边，常规边记录短期匹配状态，提升边记录长期相似检测之间的匹配关系。除了原来公式(2)中的约束，又增加了2个针对提升边的约束，即(1)对于提升边是正确匹配的，应该有常规边上正确匹配的支持；(2)对于提升边是割边的情况，也应该有常规边上连续的割边的支持。如图8。

图8: (a)和(c)是传统的最小代价多割图模型。(b)和(d)是增加了提升边(绿色边)的最小多割图模型。通过增加提升边约束，图中(b)中的提升边可以被识别为割，而(d)中的边被识别为链接。

同样，为了计算边的匹配代价，需要设计匹配特征。这里，作者采用结合姿态对齐的叠加Siamese网络计算匹配相似度，如图9，采用的网络模型StackNetPose具有最好的重识别性能。

图9: (a),(b),(c)分别为SiameseNet, StackNet, StackNetPose模型。(e)为这三种模型与ID-Net在行人重识别任务上对比。(d)为StackNetPose的结果示例。

综合StackNetPose网络匹配信任度、深度光流特征(deepMatching)和时空相关度，作者设计了新的匹配特征向量。类似于[2], 计算逻辑回归匹配概率。最终的跟踪结果取得了非常突出的进步。在MOT2016测试数据上的结果如下表：

表1：基于提升边的最小代价多割算法在MOT2016测试数据集中的跟踪性能评测结果。

3.3 通过时空域关注模型学习多目标跟踪算法

除了采用解决目标重识别问题的深度网络架构学习检测匹配特征，还可以根据多目标跟踪场景的特点，设计合适的深度网络模型来学习检测匹配特征。Chu等人对行人多目标跟踪问题中跟踪算法发生漂移进行统计分析，发现不同行人发生交互时，互相遮挡是跟踪算法产生漂移的重要原因[4]。如图10。

图10：当2个目标的运动发生交互的时候，被遮挡目标不能分辨正确匹配，导致跟踪漂移。

针对这个问题，文献[4]提出了基于空间时间关注模型(STAM)用于学习遮挡情况，并判别可能出现的干扰目标。如图11，空间关注模型用于生成遮挡发生时的特征权重，当候选检测特征加权之后，通过分类器进行选择得到估计的目标跟踪结果，时间关注模型加权历史样本和当前样本，从而得到加权的损失函数，用于在线更新目标模型。

图11：用于遮挡判别的STAM模型框架，采用空间注意模型加权检测结果的特征，通过历史样本、以及围绕当前跟踪结果采集的正、负样本，来在线更新目标模型。

在这个模型中每个目标独立管理并更新自己的空间时间关注模型以及特征模型，并选择候选检测进行跟踪，因此本质上，这种方法是对单目标跟踪算法在多目标跟踪中的扩展。为了区分不同的目标，关键的步骤是如何对遮挡状态进行建模和区分接近的不同目标。

这里空间注意模型用于对每个时刻的遮挡状态进行分析，空间关注模型如图12中下图所示。主要分为三个部分，第一步是学习特征可见图(visibility map)：

这里fvis是一个卷积层和全连接层的网络操作。wvisi是需要学习的参数。

第二步是根据特征可见图，计算空间关注图(Spatial Attention):

其中fatt是一个局部连接的卷积和打分操作。wtji是学习到的参数。

图12：采用空间注意模型网络架构学习遮挡状态，并用于每个样本特征的加权和打分。


第三步根据空间注意图加权原特征图：

对生成的加权特征图进行卷积和全连接网络操作，生成二元分类器判别是否是目标自身。最后用得到分类打分选择最优的跟踪结果。

3.4 基于循环网络判别融合表观运动交互的多目标跟踪算法

上面介绍的算法采用的深度网络模型都是基于卷积网络结构，由于目标跟踪是通过历史轨迹信息来判断新的目标状态，因此，设计能够记忆历史信息并根据历史信息来学习匹配相似性度量的网络结构来增强多目标跟踪的性能也是比较可行的算法框架。

在文献[5]中，Sadeghian等人设计了基于长短期记忆循环网络模型(LSTM)的特征融合算法来学习轨迹历史信息与当前检测之间的匹配相似度。如图13。

图13：轨迹目标与检测的匹配需要采用三种特征(表观特征、运动特征、交互特征)融合(左)，为了融合三种特征采用分层的LSTM模型(中)，最终匹配通过相似度的二部图匹配算法实现(右)。

文献[5]中，考虑从三个方面特征计算轨迹历史信息与检测的匹配：表观特征，运动特征，以及交互模式特征。这三个方面的特征融合以分层方式计算。

在底层的特征匹配计算中，三个特征都采用了长短期记忆模型(LSTM)。对于表观特征，首先采用VGG-16卷积网络生成500维的特征ϕtA，以这个特征作为LSTM的输入计算循环。

图14：基于CNN模型和LSTM模型的轨迹与检测表观特征匹配架构。

网络的输出特征ϕt，对于当前检测BBjt+1，计算同样维度的特征ϕj，连接这两个特征并通过全链接网络层计算500维特征ϕA，根据是否匹配学习分类器，并预训练这个网络(图14)。

对于运动特征，取相对位移vit为基本输入特征，直接输入LSTM模型计算没时刻的输出ϕi，对于下一时刻的检测同样计算相对位移vjt+1,通过全连接网络计算特征ϕj，类似于表观特征计算500维特征ϕm，并利用二元匹配分类器进行网络的预训练(图15)。

图15：基于LSTM模型的轨迹运动特征匹配架构。

对于交互特征，取以目标中心位置周围矩形领域内其他目标所占的相对位置映射图作为LSTM模型的输入特征，计算输出特征ϕi，对于t+1时刻的检测计算类似的相对位置映射图为特征，通过全连接网络计算特征ϕj，类似于运动模型，通过全连接网络计算500维特征ϕI，进行同样的分类训练(图16)。

图16：基于LSTM模型的目标交互特征匹配架构。

当三个特征ϕA，ϕM，ϕI都计算之后拼接为完整的特征，输入到上层的LSTM网络，对输出的向量进行全连接计算，然后用于匹配分类，匹配正确为1，否则为0。对于最后的网络结构，还需要进行微调，以优化整体网络性能。最后的分类打分看作为相似度用于检测与轨迹目标的匹配计算。最终的跟踪框架采用在线的检测与轨迹匹配方法进行计算。

3.5 基于双线性长短期循环网络模型的多目标跟踪算法

在循环网络判别融合表观运动交互的多目标跟踪算法中，作者采用LSTM作为表观模型、运动模型以及交互模型的历史信息模型表示。在对LSTM中各个门函数的设计进行分析之后，Kim等人认为仅仅用基本的LSTM模型对于表观特征并不是最佳的方案，在文献[10]中，Kim等人设计了基于双线性LSTM的表观特征学习网络模型。

如图17中，除了利用传统的LSTM进行匹配学习，或者类似[5]中的算法，拼接LSTM输出与输入特征，作者设计了基于乘法的双线性LSTM模型，利用LSTM的隐含层特征(记忆)信息与输入的乘积作为特征，进行匹配分类器的学习。

图17：三种基于LSTM的匹配模型。(a)利用隐含层(记忆信息)与输入特征乘积作为分类特征。(b)直接拼接隐含层特征与输入特征作为新的特征进行分类学习。(c)使用传统LSTM模型的隐含层进行特征学习。

这里对于隐含层特征ht-1,必须先进行重新排列(reshape)操作，然后才能乘以输入的特征向量xt,如下公式：

其中f表示非线性激活函数，mt是新的特征输入。而原始的检测图像采用ResNet50提取2048维的特征，并通过全连接降为256维。下表中对于不同网络结构、网络特征维度、以及不同LSTM历史长度时，表观特征的学习对跟踪性能的影响做了验证。 表2：(左)三种网络结构对跟踪性能的影响， Baseline1和Baseline2分别对应图17中的中间图结构和右图结构。(中)不同网络隐含层维度对性能的影响。(右)不同历史信息长度对跟踪性能的影响。

可以看出采用双线性LSTM(bilinear LSTM)的表观特征性能最好，此时的历史相关长度最佳为40，这个值远远超过文献[5]中的2-4帧历史长度。相对来说40帧历史信息影响更接近人类的直觉。

作者通过对比递推最小二乘公式建模表观特征的结果，认为双线性LSTM模型对于表观模型的长期历史特征建模比简单的LSTM更具有可解释性，而对于运动特征，原始的LSTM特征表现的更好。综合双线性LSTM表观模型和LSTM运动模型，作者提出了新的基于MHT框架的跟踪算法MHT-bLSTM，得到的性能如下表：

表3：在MOT2017和MOT2016中多目标跟踪算法比较。在IDF1评测指标上，MHT-bLSTM的性能最佳。

4、基于深度学习的视觉多目标跟踪算法讨论

上文我们讨论了视觉多目标跟踪领域中，深度学习算法近年来的发展。从直接扩展行人重识别任务中深度学习算法的网络模型，深度学习被证明在多目标跟踪领域中是确实可行的特征学习和特征匹配算法，对于提升跟踪性能可以起到非常重要的作用。目前的基于深度学习的多目标跟踪框架在以下两个方向取得了较好的进展：(1)结合多目标跟踪场景的网络设计，比如在文献[4]中考虑多目标交互的情况设计网络架构，这种考虑跟踪场景的网络设计对于跟踪结果有明显提升。(2)采用循环神经网络的深度学习应用，比如文献[5]和[10]，讨论历史信息对跟踪中轨迹特征的描述，是研究跟踪问题的一个重要方向。

从跟踪结果来看，即使采用简单的重识别网络特征以及光流特征，如果使用优化的全局跟踪框架，也能够得到比使用复杂的网络架构更好的结果。例如使用提升边建模长期链接的多割图模型，对于跟踪过程中目标的检测错误和检测不准确具有很好的补偿作用，可以提升正确检测聚类的性能。而使用循环网络模型对于运动特征的长期匹配相似度计算也是非常有效的。比较上文中讨论的两种循环网络的使用，由于缺少交互特征，基于双线性LSTM的方法比特征融合的方法具有一定的性能损失。 因此， 尝试在网络模型中加入交互特征的建模，对于多目标跟踪结果具有一定的性能提升。

5、基于深度学习的视觉多目标跟踪发展趋势

近年来，基于深度学习的单目标跟踪算法取得了长足的进步。相对来说，深度学习在多目标跟踪领域的应用，比较多的局限于匹配度量的学习。主要的原因是，在图像识别领域中，例如图像分类、行人重识别问题中，深度学习取得的进展能够较好的直接应用于多目标跟踪问题。然而，考虑对象到之间的交互以及跟踪场景复杂性，多目标跟踪问题中深度学习算法的应用还远没有达到充分的研究。随着深度学习领域理论的深入研究和发展，近年来基于生成式网络模型和基于强化学习的深度学习越来越得到大家的关注，在多目标跟踪领域中，由于场景的复杂性，研究如何采用生成式网络模型和深度强化学习来学习跟踪场景的适应性，提升跟踪算法的性能是未来深度学习多目标跟踪领域研究的趋势。

[1] C. Kim, F. Li, A. Ciptadi, and J. Rehg. Multiple Hypothesis Tracking Revisited. In ICCV, 2015.

[2] S. Tang, B. Andres, M. Andriluka, and B. Schiele. Multi-person tracking by multicut and deep matching. In ECCV Workshops, 2016.

[3] L. Lealtaixe, C. Cantonferrer, and K. Schindler, “Learning by tracking: Siamese CNN for robust target association,” in Proceedings of Computer Vision and Pattern Recognition. 2016.

[4] Q. Chu, W. Ouyang, H. Li, X. Wang, B. Liu, N. Yu. "Online Multi-Object Tracking Using CNN-based Single Object Tracker with Spatial-Temporal Attention Mechanism", ICCV 2017.

[5] A. Sadeghian, A. Alahi, and S. Savarese. "Tracking the untrackable: Learning to track multiple cues with long-term dependencies", ICCV2017.

[6] K. Fang, Y. Xiang, X. Li and S. Savarese, "Recurrent Autoregressive Networks for Online Multi-Object Tracking", In IEEE Winter Conference on Applications of Computer Vision 2018.

[7] M. Keuper, E. Levinkov, N. Bonneel, G. Lavou´e, T. Brox, B. Andres. "Efficient decomposition of image and mesh graphs by lifted multicuts", ICCV 2015.

[8] P. Weinzaepfel, J. Revaud, Z. Harchaoui, C. Schmid. "DeepFlow: large displacement optical flow with deep matching", In ICCV 2013.

[9] S. Tang, M. Andriluka, B. Andres, and B. Schiele. Multiple People Tracking with Lifted Multi-cut and Person Re-identification. In CVPR, 2017.

[10] C. Kim, F. Li, and J. M. Rehg, "Multi-object Tracking with Neural Gating Using Bilinear LSTM", in ECCV 2018.

微信公众号: 极市平台（ID: extrememart ）
每天推送最新CV干货