视频图像处理|主流网络模型之目标跟踪视频图像处理|深度学习

什么是目标追踪（Visual Object Tracking）？
跟踪就是在连续的视频帧中定位某一物体。

文章图片

跟踪VS检测

1.跟踪速度比检测快
当你跟踪在上一帧中检测到的对象时，你会非常了解目标的外观。你也知道在前一帧中的位置和它的运动的方向和速度。因此，在下一帧中，可以使用所有这些信息来预测下一帧中目标的位置，并对对象的预期位置进行小范围搜索，以准确定位目标。因此，在设计高效的系统时，通常在每n帧上运行对象检测，而在其间的n-1帧中采用跟踪算法。
2.当检测失败时跟踪来帮助
3.跟踪保留身份信息
目标检测的输出是包含目标的矩形数组。但是，没有标识附加到对象。

几大难点

外观变形，光照变化，快速运动和运动模糊，背景相似干扰：

文章图片

平面外旋转，平面内旋转，尺度变化，遮挡和出视野等情况：

文章图片

数据集

OTB50 & OTB100(2013)
涉及到灰度图像和彩色图像，均可以免费下载，涉及到目标跟踪的11个属性，包括光照变化、尺度变化、遮挡、形变、运动模糊、快速运动、平面内旋转、平面外旋转、出视野、背景干扰、低像素。

VOT2013 - VOT2018 (竞赛数据集,Each Year)
每年公开的60个序列，官方会对公开序列的前10名在隐藏数据集上测试，从而选出最终的winner，难度高于OTB。

文章图片

评价指标

1、平均重叠期望（EAO）是对每个跟踪器在一个短时图像序列上的非重置重叠的期望值，是VOT评估跟踪算法精度的最重要指标。
2、准确率（Accuracy）是指跟踪器在单个测试序列下的平均重叠率（两矩形框的相交部分面积除以两矩形框的相并部分的面积。（MeanIOU）
3、鲁棒性（Robustness）是指单个测试序列下的跟踪器失败次数，当重叠率为0时即可判定为失败。

具体看一下这张图就能明白：

文章图片

目标追踪的算法分类（Common Methods）生成(generative)模型方法

生成类方法，在当前帧对目标区域建模，下一帧寻找与模型最相似的区域就是预测位置，比较著名的有卡尔曼滤波，粒子滤波，mean-shift等。举个例子，从当前帧知道了目标区域80%是红色，20%是绿色，然后在下一帧，搜索算法到处去找最符合这个颜色比例的区域。算法效果并不理想，因此现在用的很少。

判别(discriminative)模型方法

OTB50里面的大部分方法都是这一类，经典套路，图像特征+机器学习。
当前帧以目标区域为正样本，背景区域为负样本，机器学习训练分类器，下一帧用训练好的分类器找最优区域。
与生成类方法最大的区别，是分类器训练过程中用到了背景信息，这样分类器专注区分前景和背景，判别类方法普遍都比生成类好。经典判别类方法有Struck和TLD（Performace well in long-term task）。判别类方法的最新发展就是相关滤波类方法，correlation filter简称CF，或discriminative correlation filter简称DCF，和深度学习(Deep ConvNet based)类方法，而DCF+CNN的做法成为最近VOT刷榜的标配。2018年的VOT，基于全卷积孪生网络（SiamNet）的方法大崛起，凭借超越DCF方法的准确度和端到端训练的优势，成为目标追踪新的研究方向。

CF算法示意图

文章图片

下图是GitHub上发布的2018VOT系统分支结构，上述算法都含在其中了。

文章图片

北京飞搜科技&北京邮电大学代表队提交的结果（CFWCR）获得VOT 2017竞赛公开的60个评测序列中第二名。方法基于业界流行的相关滤波的框架，使用了单CNN特征的多尺度追踪方案。现有很多追踪器融合了CNN特征和传统的机器学习特征，如hog特征，CN颜色特征等。在他们的实验中，发现CNN的浅层特征具有物体轮廓的信息，高层的深度特征具有物体的语义信息，将CNN的浅层和高层特征进行融合，能使追踪器具有很好的性能。
VOT 2018 内测结果

文章图片

· 相关滤波算法（CF）
Correlation Filter 最早应用于信号处理，用来描述两个信号之间的相关性，或者说相似性，对于两个数据 f 和g，则两个信号的相关性为：

文章图片

【视频图像处理|主流网络模型之目标跟踪】其中 f?表示 f 的复共轭，这是和卷积的区别（相关性与卷积类似，区别就在于里面的共轭）。

对于图像来讲，问题描述为要找到一个滤波模版 h，与输入图像 f 求相关性，得到相关图 g。

文章图片

模板与图形的相关运算
为了加快计算速度，这里引入了傅里叶变换，根据卷积定理（correlation版本）可知，函数互相关的傅里叶变换等于函数傅里叶变换的乘积：

文章图片

CF的流程图

文章图片

· HCF（CF+CNN，Since 2015）
2015开始，深度学习开始进军跟踪领域，使用深度学习可以更好的提取目标的特征，对目标进行更好的表达。低层特征有较高的分辨率能够对目标进行精准的定位，高层特征包含更多的语义信息，能够处理较大的目标变化和防止跟踪器漂移，能够对目标进行范围定位。但是深度学习的缺点就在于网络的训练和速度，即使如HCF等使用离线的训练速度仍然慢。

文章图片

深度学习+CF

· SiamFC（Pure CNN）

文章图片

SiamFC的结构

上面一支可以看做是一个模板。其中z是第一帧所给出的目标框，φ 表示一种特征提取方法，SiamFC提取的是深度特征，经过全卷积网络后得到一个6X6X128的feature map φ(z)。
下面一支x可以看为当前帧的搜索区域，同样提取了深度特征之后得到一个22X22X128的feature map φ(x)。
两支的交汇是一个互相关层，可以看成是φ(z)在φ(x)上滑动搜索，最后得到一个响应图，图上最大值对应的点就是算法认为的目标中心所在位置。

SiamRPN & DaSiamRPN
就像DSST之前的众多相关滤波跟踪算法一样，SiamFC难以应对物体尺度的变化。SiamRPN[10]（CVPR18, B. Li et al.）则借鉴了目标检测领域常用的RPN（Region Proposal Network，区域生成网络）用于预测新图像中目标的尺度。
SiamRPN在 x 和 z 经过孪生CNN得到各自的特征图后，没有直接对二者进行互相关运算，而是将这两个特征图各自放入RPN部分的两个分支中，每个分支中的两个特征图分别经过一个CNN再进行互相关运算。RPN部分的两个分支分别用于进行目标概率的预测和目标边框的回归，并且同样借鉴了目标检测领域的anchor方法，从而降低了目标边框回归的训练难度。

文章图片

SiamRPN（图片来源：[10]）
SiamRPN之后，作者又紧接着提出了改进版——DaSiamRPN[11]（ECCV18, Z. Zhu et al.），对训练数据进行了增强以提升模型对同类别物体干扰的判别能力（一般的模型往往着重于前景与背景的判别，而对相似物体的判别性较差）。另外，DaSiamRPN加入了增量学习的Distractor-aware模块，在运行时采样并更新模型的参数。使得模型能更好的迁移到当前视频的域中。
DaSiamRPN在VOT实验上的性能超越了ECO，同时还能跑到160FPS以上的速度。深度学习单目标跟踪方法可以说得上是“风生水起”。
CIR (SiamDW)
SiamDW[12]的作者认为，较深的卷积神经网络的感受域过大，这降低了特征的判别性和定位的准确性。另外，多层的padding使得孪生网络的学习产生偏移。作者对网络主干的各种性质（padding，stride，感受域大小等）进行了系统性的研究分析，并得出了以下结论：1)孪生网络跟踪器倾向于更小的stride；2)感受域大小应取决于目标模板图像 z 的大小，一般60%到80%最佳；3)stride、感受域大小和输出响应图大小互相有很强的依赖，应当共同考虑；4)全卷积的孪生网络应当尽可能消除 x 和 z 在感知上的不一致性。
针对上述结论，作者提出了CIR（Cropping-Inside-Residial）模块以取代ResNet中的基本模块，基本做法就是下图中每个块的addition之后的crop操作，除去受padding影响的边缘部位。使用CIResNet-22作为主干的改进版SiamFC和SiamRPN都有了不小的性能提升，只是似乎这样的做法依然无法让网络变得很深？

文章图片

各种CIR block（图片来源：[12]）
SiamRPN++
SiamRPN++[13]是SiamRPN的作者在其基础上的改进。主要改进有以下四点：1)使用了微调版的ResNet-50主干，极大地优化了特征的提取；2)对ResNet-50的3、4、5阶段的特征分别使用RPN进行边框回归与目标定位，并使用带权重的融合方法结合三者的结果；3)使用了depth-wise互相关运算，减少参数量，加速了RPN部分的运算；4)最重要地，提出了一种spatial-aware的采样策略，从而打破了目标跟踪对CNN的严格平移不变性限制。
作者分析认为，只有无padding的网络才具有严格的平移不变性，而加深CNN又无法避免padding的出现。但是通过在训练样本中人工加入服从均匀分布的随机平移可一定程度上打破这种严格平移不变性限制。从模型的预测结果上来看，如果训练数据在一定范围内服从均匀分布，那么理想情况下跟踪器预测的结果也应该更接近均匀分布。作者通过定量实验发现，加入像素范围为32的随机平移后，最终得到的目标位置热图更接近均匀分布，说明预测的结果更接近实际测试目标的分布情况。

文章图片

SiamRPN++（图片来源：[13]）
加入了以上几点改进的SiamRPN++成为了OTB2015、VOT2018、UAV123、LaSOT和TrackingNet上的第一名，基于深度学习的方法终于在跟踪准确度上领先一步了。
PS：从这几年顶会的VOT论文数量看，基于深度学习方法也确实领先一步了……
PPS：除了上述的方法之外，基于深度学习的目标跟踪还有不少值得一提的文章，如MDNet[14]，TCNN[15]，SANet[16]，CREST[17]，VITAL[18]等等，恕不能一一介绍。
PPPS：以上的相关滤波方法中大部分工作都包含相当复杂的数学推导，而本文没有过多涉及，一来本人能力有限，二来篇幅也不宜过长。对其推导有兴趣的同学请参考原文。
· FlowTrack
《End-to-end Flow Correlation Tracking with Spatial-temporal Attention》（2018CVPR，商汤）
阅读笔记
背景：
①DCF方法很火（KCF、SAMF、LCT、MUSTer、SRDCF、CACF），但是应用人工设定的特征使得这一类算法精度鲁棒性都较差；
② 受深度学习影响，很多结合CNN的算法（DeepSRDCF、HCF、SiamFC）出现，它们都只应用到当前帧的信息而很少关注帧间存在的互信息,并且CNN的机制导致了tracker在目标遇到运动模糊或者部分遮挡的时候，性能只能依靠离线train的特征的质量，鲁棒性很难保证。
③ 尽管一些追踪器用到了光流特征，但是这些模型是离线的，非端到端的，所以结果是非最理想的。
本文提出FlowTrack网络，应用到flow information和appearance features，有机结合到端对端的网络中，在VOT2015和VOT2016任务中，EAO属性排名第一，速度为12FPS。

文章图片

FlowTrack的网络架构

结构是一个基于Siamese的双流训练网络。分为historical branch和current branch. 在historical branch里面，进行Flow的提取和warp操作融合阶段，作者设计了一种spatial-temporal attention的机制。在current branch，只提取feature. Siamese结构两支出来的feature送进DCF layer, 得到相应输出。总结来说，他们把Flow提取，warp操作，特征提取和融合，CF tracking都做成了网络的layer，端到端地训练它们。其中需要注意的是，wrap是指的是一种点到点的映射关系，实现flownet出来的光流图到高阶特征的映射。在从t-1到t-n的特征融合阶段，设计了一种spatial-temporal attention的机制。在spatial attention中，是对空间位置上每一个待融合的点分配权重，具体采用余弦距离衡量，结果就是和当前帧越相似分配的权重越大，反之越小；这么做的问题是当前帧的权重永远最大，所以本文借鉴SENet的思想进而设计了temporal attention，即把每一帧看做一个channel，设计一个质量判断网络。

(1)跟踪使用的特征由Feature CNN提取；
Feature CNN：由三个卷积层构成(3x3x128, 3x3x128, 3x3x96)。

文章图片

特征提取
(2)光流信息由FlowNet提取；
FlowNet：2015年被提出，是用来提取光流场的深度网络，9层卷积。

文章图片

FlowNet的9层光流提取模型
(3) Warp操作按特征通道进行：

文章图片

其中m表示通道，p表示原始图像上点的坐标，δp表示点的光流，q表示特征图上点的坐标，K是双线性插值核。

文章图片

文章图片

(4)Spatial-temporal attention给各通道特征赋予权值；
Spatial attention + Temporal attention
空间+时间

文章图片

时空提取attention模块
Spatial 的提取：
计算Spatial attention，并融合特征。其中上标e表示通过Bottleneck结构（降维到特定空间）找到的嵌入层特征，p表示原始Feature map上的点坐标。总的来说，这个部分的物理意义是，对与t-1帧特征不相似的特征赋予低权重，反之，与其相似的赋予高权重。

文章图片

文章图片

temporal的加入：Spatial Attention的问题是当前帧的权重永远最大，解决方法引入Temporal 机制，设计一个质量判断网络：从Spatial attention输出来的权重map，输入Temporal attention结构，经过一个类似SE-Net（ImageNet Classification Champion，2017，Momenta）的结构，得到通道重要性权值，可以看作是对Spatial attention的二次调整。

文章图片

实验结果

文章图片

多策略的对比

文章图片

VOT 2016 1st

文章图片

VOT 2017 2rd
DeepSort
Deep SORT是多目标跟踪(Multi-Object Tracking)中常用到的一种算法，是一个Detection Based Tracking的方法。这个算法工业界关注度非常高，在知乎上有很多文章都是使用了Deep SORT进行工程部署。笔者将参考前辈的博客，结合自己的实践(理论&代码)对Deep SORT算法进行代码层面的解析。
在之前笔者写的一篇Deep SORT论文阅读总结中，总结了DeepSORT论文中提到的核心观点，如果对Deep SORT不是很熟悉，可以先理解一下，然后再来看解读代码的部分。
由于知乎对文章篇幅有限制，所以分上下篇发。
上篇将梳理SORT、Deep SORT，以类图为主，讲解DeepSORT代码部分的各个模块。
下篇主要是梳理运行的流程，对照流程图进行代码层面理解。以及最后的总结+代码推荐。
1. MOT主要步骤
在《DEEP LEARNING IN VIDEO MULTI-OBJECT TRACKING: A SURVEY》这篇基于深度学习的多目标跟踪的综述中，描述了MOT问题中四个主要步骤：

文章图片

给定视频原始帧。
运行目标检测器如Faster R-CNN、YOLOv3、SSD等进行检测，获取目标检测框。
将所有目标框中对应的目标抠出来，进行特征提取（包括表观特征或者运动特征）。
进行相似度计算，计算前后两帧目标之间的匹配程度（前后属于同一个目标的之间的距离比较小，不同目标的距离比较大）
数据关联，为每个对象分配目标的ID。

以上就是四个核心步骤，其中核心是检测，SORT论文的摘要中提到，仅仅换一个更好的检测器，就可以将目标跟踪表现提升18.9%。
2. SORT
Deep SORT算法的前身是SORT, 全称是Simple Online and Realtime Tracking。简单介绍一下，SORT最大特点是基于Faster R-CNN的目标检测方法，并利用卡尔曼滤波算法+匈牙利算法，极大提高了多目标跟踪的速度，同时达到了SOTA的准确率。
这个算法确实是在实际应用中使用较为广泛的一个算法，核心就是两个算法：卡尔曼滤波和匈牙利算法。
卡尔曼滤波算法分为两个过程，预测和更新。该算法将目标的运动状态定义为8个正态分布的向量。
预测：当目标经过移动，通过上一帧的目标框和速度等参数，预测出当前帧的目标框位置和速度等参数。
更新：预测值和观测值，两个正态分布的状态进行线性加权，得到目前系统预测的状态。
**匈牙利算法：**解决的是一个分配问题，在MOT主要步骤中的计算相似度的，得到了前后两帧的相似度矩阵。匈牙利算法就是通过求解这个相似度矩阵，从而解决前后两帧真正匹配的目标。这部分sklearn库有对应的函数linear_assignment来进行求解。
SORT算法中是通过前后两帧IOU来构建相似度矩阵，所以SORT计算速度非常快。
下图是一张SORT核心算法流程图：

文章图片

Detections是通过目标检测器得到的目标框，Tracks是一段轨迹。核心是匹配的过程与卡尔曼滤波的预测和更新过程。
流程如下：目标检测器得到目标框Detections，同时卡尔曼滤波器预测当前的帧的Tracks, 然后将Detections和Tracks进行IOU匹配，最终得到的结果分为：

Unmatched Tracks，这部分被认为是失配，Detection和Track无法匹配，如果失配持续了次，该目标ID将从图片中删除。
Unmatched Detections, 这部分说明没有任意一个Track能匹配Detection, 所以要为这个detection分配一个新的track。
Matched Track，这部分说明得到了匹配。

卡尔曼滤波可以根据Tracks状态预测下一帧的目标框状态。
卡尔曼滤波更新是对观测值(匹配上的Track)和估计值更新所有track的状态。
3. Deep SORT
DeepSort中最大的特点是加入外观信息，借用了ReID领域模型来提取特征，减少了ID switch的次数。整体流程图如下：

文章图片

可以看出，Deep SORT算法在SORT算法的基础上增加了级联匹配(Matching Cascade)+新轨迹的确认(confirmed)。总体流程就是：

卡尔曼滤波器预测轨迹Tracks
使用匈牙利算法将预测得到的轨迹Tracks和当前帧中的detections进行匹配(级联匹配和IOU匹配)
卡尔曼滤波更新。

其中上图中的级联匹配展开如下：

文章图片

上图非常清晰地解释了如何进行级联匹配，上图由虚线划分为两部分：
上半部分中计算相似度矩阵的方法使用到了外观模型(ReID)和运动模型(马氏距离)来计算相似度，得到代价矩阵，另外一个则是门控矩阵，用于限制代价矩阵中过大的值。
下半部分中是是级联匹配的数据关联步骤，匹配过程是一个循环(max age个迭代，默认为70)，也就是从missing age=0到missing age=70的轨迹和Detections进行匹配，没有丢失过的轨迹优先匹配，丢失较为久远的就靠后匹配。通过这部分处理，可以重新将被遮挡目标找回，降低被遮挡然后再出现的目标发生的ID Switch次数。
将Detection和Track进行匹配，所以出现几种情况

Detection和Track匹配，也就是Matched Tracks。普通连续跟踪的目标都属于这种情况，前后两帧都有目标，能够匹配上。
Detection没有找到匹配的Track，也就是Unmatched Detections。图像中突然出现新的目标的时候，Detection无法在之前的Track找到匹配的目标。
Track没有找到匹配的Detection，也就是Unmatched Tracks。连续追踪的目标超出图像区域，Track无法与当前任意一个Detection匹配。
以上没有涉及一种特殊的情况，就是两个目标遮挡的情况。刚刚被遮挡的目标的Track也无法匹配Detection，目标暂时从图像中消失。之后被遮挡目标再次出现的时候，应该尽量让被遮挡目标分配的ID不发生变动，减少ID Switch出现的次数，这就需要用到级联匹配了。

视频来源：目标跟踪初探（DeepSORT）

目前主流的目标跟踪算法都是基于Tracking-by-Detecton策略，即基于目标检测的结果来进行目标跟踪。DeepSORT运用的就是这个策略，上面的视频是DeepSORT对人群进行跟踪的结果，每个bbox左上角的数字是用来标识某个人的唯一ID号。
这里就有个问题，视频中不同时刻的同一个人，位置发生了变化，那么是如何关联上的呢？答案就是匈牙利算法和卡尔曼滤波。

匈牙利算法可以告诉我们当前帧的某个目标，是否与前一帧的某个目标相同。
卡尔曼滤波可以基于目标前一时刻的位置，来预测当前时刻的位置，并且可以比传感器（在目标跟踪中即目标检测器，比如Yolo等）更准确的估计目标的位置。

匈牙利算法（Hungarian Algorithm）首先，先介绍一下什么是分配问题（Assignment Problem）：假设有N个人和N个任务，每个任务可以任意分配给不同的人，已知每个人完成每个任务要花费的代价不尽相同，那么如何分配可以使得总的代价最小。
举个例子，假设现在有3个任务，要分别分配给3个人，每个人完成各个任务所需代价矩阵（cost matrix）如下所示（这个代价可以是金钱、时间等等）：

文章图片

怎样才能找到一个最优分配，使得完成所有任务花费的代价最小呢？
匈牙利算法（又叫KM算法）就是用来解决分配问题的一种方法，它基于定理：

如果代价矩阵的某一行或某一列同时加上或减去某个数，则这个新的代价矩阵的最优分配仍然是原代价矩阵的最优分配。

算法步骤（假设矩阵为NxN方阵）：

对于矩阵的每一行，减去其中最小的元素
对于矩阵的每一列，减去其中最小的元素
用最少的水平线或垂直线覆盖矩阵中所有的0
如果线的数量等于N，则找到了最优分配，算法结束，否则进入步骤5
找到没有被任何线覆盖的最小元素，每个没被线覆盖的行减去这个元素，每个被线覆盖的列加上这个元素，返回步骤3

继续拿上面的例子做演示：
step1 每一行最小的元素分别为15、20、20，减去得到：

文章图片

step2 每一列最小的元素分别为0、20、5，减去得到：

文章图片

step3 用最少的水平线或垂直线覆盖所有的0，得到：

文章图片

step4 线的数量为2，小于3，进入下一步；
step5 现在没被覆盖的最小元素是5，没被覆盖的行（第一和第二行）减去5，得到：

文章图片

被覆盖的列（第一列）加上5，得到：

文章图片

跳转到step3，用最少的水平线或垂直线覆盖所有的0，得到：

文章图片

step4：线的数量为3，满足条件，算法结束。显然，将任务2分配给第1个人、任务1分配给第2个人、任务3分配给第3个人时，总的代价最小（0+0+0=0）：

文章图片

所以原矩阵的最小总代价为（40+20+25=85）：

文章图片

sklearn里的linear_assignment()函数以及scipy里的linear_sum_assignment()函数都实现了匈牙利算法，两者的返回值的形式不同：

import numpy as np from sklearn.utils.linear_assignment_ import linear_assignment from scipy.optimize import linear_sum_assignment cost_matrix = np.array([ [15,40,45], [20,60,35], [20,40,25] ]) matches = linear_assignment(cost_matrix) print('sklearn API result:\n', matches) matches = linear_sum_assignment(cost_matrix) print('scipy API result:\n', matches) """Outputs sklearn API result: [[0 1] [1 0] [2 2]] scipy API result: (array([0, 1, 2], dtype=int64), array([1, 0, 2], dtype=int64)) """

在DeepSORT中，匈牙利算法用来将前一帧中的跟踪框tracks与当前帧中的检测框detections进行关联，通过外观信息（appearance information）和马氏距离（Mahalanobis distance），或者IOU来计算代价矩阵。
源码解读：

#linear_assignment.py def min_cost_matching(distance_metric, max_distance, tracks, detections, track_indices=None, detection_indices=None): ...# 计算代价矩阵 cost_matrix = distance_metric(tracks, detections, track_indices, detection_indices) cost_matrix[cost_matrix > max_distance] = max_distance + 1e-5# 执行匈牙利算法，得到匹配成功的索引对，行索引为tracks的索引，列索引为detections的索引 row_indices, col_indices = linear_assignment(cost_matrix) matches, unmatched_tracks, unmatched_detections = [], [], [] # 找出未匹配的detections for col, detection_idx in enumerate(detection_indices): if col not in col_indices: unmatched_detections.append(detection_idx)# 找出未匹配的tracks for row, track_idx in enumerate(track_indices): if row not in row_indices: unmatched_tracks.append(track_idx)# 遍历匹配的(track, detection)索引对 for row, col in zip(row_indices, col_indices): track_idx = track_indices[row] detection_idx = detection_indices[col] # 如果相应的cost大于阈值max_distance，也视为未匹配成功 if cost_matrix[row, col] > max_distance: unmatched_tracks.append(track_idx) unmatched_detections.append(detection_idx) else: matches.append((track_idx, detection_idx)) return matches, unmatched_tracks, unmatched_detections

卡尔曼滤波（Kalman Filter）
卡尔曼滤波被广泛应用于无人机、自动驾驶、卫星导航等领域，简单来说，其作用就是基于传感器的测量值来更新预测值，以达到更精确的估计。
假设我们要跟踪小车的位置变化，如下图所示，蓝色的分布是卡尔曼滤波预测值，棕色的分布是传感器的测量值，灰色的分布就是预测值基于测量值更新后的最优估计。

文章图片

Kalman Filter
在目标跟踪中，需要估计track的以下两个状态：

均值(Mean)：表示目标的位置信息，由bbox的中心坐标 (cx, cy)，宽高比r，高h，以及各自的速度变化值组成，由8维向量表示为 x = [cx, cy, r, h, vx, vy, vr, vh]，各个速度值初始化为0。
协方差(Covariance )：表示目标位置信息的不确定性，由8x8的对角矩阵表示，矩阵中数字越大则表明不确定性越大，可以以任意值初始化。

卡尔曼滤波分为两个阶段：(1) 预测track在下一时刻的位置，(2) 基于detection来更新预测的位置。
下面将介绍这两个阶段用到的计算公式。（这里不涉及公式的原理推导，因为我也不清楚原理(?_?) ，只是说明一下各个公式的作用）
预测
基于track在t-1时刻的状态来预测其在t时刻的状态。

文章图片

文章图片

在公式1中，x为track在t-1时刻的均值，F称为状态转移矩阵，该公式预测t时刻的x'：

文章图片

矩阵F中的dt是当前帧和前一帧之间的差，将等号右边的矩阵乘法展开，可以得到cx'=cx+dt*vx，cy'=cy+dt*vy...，所以这里的卡尔曼滤波是一个匀速模型（Constant Velocity Model）。
在公式2中，P为track在t-1时刻的协方差，Q为系统的噪声矩阵，代表整个系统的可靠程度，一般初始化为很小的值，该公式预测t时刻的P'。
源码解读：

#kalman_filter.py def predict(self, mean, covariance): """Run Kalman filter prediction step.Parameters ---------- mean: ndarray, the 8 dimensional mean vector of the object state at the previous time step. covariance: ndarray, the 8x8 dimensional covariance matrix of the object state at the previous time step. Returns ------- (ndarray, ndarray), the mean vector and covariance matrix of the predicted state. Unobserved velocities are initialized to 0 mean. """ std_pos = [ self._std_weight_position * mean[3], self._std_weight_position * mean[3], 1e-2, self._std_weight_position * mean[3]] std_vel = [ self._std_weight_velocity * mean[3], self._std_weight_velocity * mean[3], 1e-5, self._std_weight_velocity * mean[3]]motion_cov = np.diag(np.square(np.r_[std_pos, std_vel]))# 初始化噪声矩阵Q mean = np.dot(self._motion_mat, mean)# x' = Fx covariance = np.linalg.multi_dot((self._motion_mat, covariance, self._motion_mat.T)) + motion_cov# P' = FPF(T) + Q return mean, covariance

更新
基于t时刻检测到的detection，校正与其关联的track的状态，得到一个更精确的结果。

文章图片

在公式3中，z为detection的均值向量，不包含速度变化值，即z=[cx, cy, r, h]，H称为测量矩阵，它将track的均值向量x'映射到检测空间，该公式计算detection和track的均值误差；
在公式4中，R为检测器的噪声矩阵，它是一个4x4的对角矩阵，对角线上的值分别为中心点两个坐标以及宽高的噪声，以任意值初始化，一般设置宽高的噪声大于中心点的噪声，该公式先将协方差矩阵P'映射到检测空间，然后再加上噪声矩阵R；
公式5计算卡尔曼增益K，卡尔曼增益用于估计误差的重要程度；
公式6和公式7得到更新后的均值向量x和协方差矩阵P。
源码解读：

#kalman_filter.py def project(self, mean, covariance): """Project state distribution to measurement space.Parameters ---------- mean: ndarray, the state's mean vector (8 dimensional array). covariance: ndarray, the state's covariance matrix (8x8 dimensional).Returns ------- (ndarray, ndarray), the projected mean and covariance matrix of the given state estimate. """ std = [self._std_weight_position * mean[3], self._std_weight_position * mean[3], 1e-1, self._std_weight_position * mean[3]]innovation_cov = np.diag(np.square(std))# 初始化噪声矩阵R mean = np.dot(self._update_mat, mean)# 将均值向量映射到检测空间，即Hx' covariance = np.linalg.multi_dot(( self._update_mat, covariance, self._update_mat.T))# 将协方差矩阵映射到检测空间，即HP'H^T return mean, covariance + innovation_covdef update(self, mean, covariance, measurement): """Run Kalman filter correction step.Parameters ---------- mean: ndarra, the predicted state's mean vector (8 dimensional). covariance: ndarray, the state's covariance matrix (8x8 dimensional). measurement: ndarray, the 4 dimensional measurement vector (x, y, a, h), where (x, y) is the center position, a the aspect ratio, and h the height of the bounding box. Returns ------- (ndarray, ndarray), the measurement-corrected state distribution. """ # 将mean和covariance映射到检测空间，得到Hx'和S projected_mean, projected_cov = self.project(mean, covariance) # 矩阵分解（这一步没看懂） chol_factor, lower = scipy.linalg.cho_factor(projected_cov, lower=True, check_finite=False) # 计算卡尔曼增益K（这一步没看明白是如何对应上公式5的，求线代大佬指教） kalman_gain = scipy.linalg.cho_solve( (chol_factor, lower), np.dot(covariance, self._update_mat.T).T, check_finite=False).T # z - Hx' innovation = measurement - projected_mean # x = x' + Ky new_mean = mean + np.dot(innovation, kalman_gain.T) # P = (I - KH)P' new_covariance = covariance - np.linalg.multi_dot((kalman_gain, projected_cov, kalman_gain.T))return new_mean, new_covariance

DeepSort工作流程 DeepSORT对每一帧的处理流程如下：

文章图片

检测器得到bbox → 生成detections → 卡尔曼滤波预测→ 使用匈牙利算法将预测后的tracks和当前帧中的detecions进行匹配（级联匹配和IOU匹配） → 卡尔曼滤波更新

Frame 0：检测器检测到了3个detections，当前没有任何tracks，将这3个detections初始化为tracks
Frame 1：检测器又检测到了3个detections，对于Frame 0中的tracks，先进行预测得到新的tracks，然后使用匈牙利算法将新的tracks与detections进行匹配，得到(track, detection)匹配对，最后用每对中的detection更新对应的track

检测
使用Yolo作为检测器，检测当前帧中的bbox：

#demo_yolo3_deepsort.py def detect(self): while self.vdo.grab(): ... bbox_xcycwh, cls_conf, cls_ids = self.yolo3(im)# 检测到的bbox[cx,cy,w,h]，置信度，类别id if bbox_xcycwh is not None: # 筛选出人的类别 mask = cls_ids == 0 bbox_xcycwh = bbox_xcycwh[mask] bbox_xcycwh[:, 3:] *= 1.2 cls_conf = cls_conf[mask] ...

生成detections
将检测到的bbox转换成detections：

#deep_sort.py def update(self, bbox_xywh, confidences, ori_img): self.height, self.width = ori_img.shape[:2] # 提取每个bbox的feature features = self._get_features(bbox_xywh, ori_img) # [cx,cy,w,h] -> [x1,y1,w,h] bbox_tlwh = self._xywh_to_tlwh(bbox_xywh) # 过滤掉置信度小于self.min_confidence的bbox，生成detections detections = [Detection(bbox_tlwh[i], conf, features[i]) for i,conf in enumerate(confidences) if conf > self.min_confidence] # NMS (这里self.nms_max_overlap的值为1，即保留了所有的detections) boxes = np.array([d.tlwh for d in detections]) scores = np.array([d.confidence for d in detections]) indices = non_max_suppression(boxes, self.nms_max_overlap, scores) detections = [detections[i] for i in indices] ...

卡尔曼滤波预测阶段
使用卡尔曼滤波预测前一帧中的tracks在当前帧的状态：

#track.py def predict(self, kf): """Propagate the state distribution to the current time step using a Kalman filter prediction step. Parameters ---------- kf: The Kalman filter. """ self.mean, self.covariance = kf.predict(self.mean, self.covariance)# 预测 self.age += 1# 该track自出现以来的总帧数加1 self.time_since_update += 1# 该track自最近一次更新以来的总帧数加1

匹配
首先对基于外观信息的马氏距离计算tracks和detections的代价矩阵，然后相继进行级联匹配和IOU匹配，最后得到当前帧的所有匹配对、未匹配的tracks以及未匹配的detections：

#tracker.py def _match(self, detections): def gated_metric(racks, dets, track_indices, detection_indices): """ 基于外观信息和马氏距离，计算卡尔曼滤波预测的tracks和当前时刻检测到的detections的代价矩阵 """ features = np.array([dets[i].feature for i in detection_indices]) targets = np.array([tracks[i].track_id for i in track_indices] # 基于外观信息，计算tracks和detections的余弦距离代价矩阵 cost_matrix = self.metric.distance(features, targets) # 基于马氏距离，过滤掉代价矩阵中一些不合适的项 (将其设置为一个较大的值) cost_matrix = linear_assignment.gate_cost_matrix(self.kf, cost_matrix, tracks, dets, track_indices, detection_indices) return cost_matrix# 区分开confirmed tracks和unconfirmed tracks confirmed_tracks = [i for i, t in enumerate(self.tracks) if t.is_confirmed()] unconfirmed_tracks = [i for i, t in enumerate(self.tracks) if not t.is_confirmed()]# 对confirmd tracks进行级联匹配 matches_a, unmatched_tracks_a, unmatched_detections = \ linear_assignment.matching_cascade( gated_metric, self.metric.matching_threshold, self.max_age, self.tracks, detections, confirmed_tracks)# 对级联匹配中未匹配的tracks和unconfirmed tracks中time_since_update为1的tracks进行IOU匹配 iou_track_candidates = unconfirmed_tracks + [k for k in unmatched_tracks_a if self.tracks[k].time_since_update == 1] unmatched_tracks_a = [k for k in unmatched_tracks_a if self.tracks[k].time_since_update != 1] matches_b, unmatched_tracks_b, unmatched_detections = \ linear_assignment.min_cost_matching( iou_matching.iou_cost, self.max_iou_distance, self.tracks, detections, iou_track_candidates, unmatched_detections) # 整合所有的匹配对和未匹配的tracks matches = matches_a + matches_b unmatched_tracks = list(set(unmatched_tracks_a + unmatched_tracks_b))return matches, unmatched_tracks, unmatched_detections# 级联匹配源码linear_assignment.py def matching_cascade(distance_metric, max_distance, cascade_depth, tracks, detections, track_indices=None, detection_indices=None): ... unmatched_detections = detection_indice matches = [] # 由小到大依次对每个level的tracks做匹配 for level in range(cascade_depth): # 如果没有detections，退出循环 if len(unmatched_detections) == 0: break # 当前level的所有tracks索引 track_indices_l = [k for k in track_indices if tracks[k].time_since_update == 1 + level] # 如果当前level没有track，继续 if len(track_indices_l) == 0: continue # 匈牙利匹配 matches_l, _, unmatched_detections = min_cost_matching(distance_metric, max_distance, tracks, detections, track_indices_l, unmatched_detections) matches += matches_l unmatched_tracks = list(set(track_indices) - set(k for k, _ in matches)) return matches, unmatched_tracks, unmatched_detections

卡尔曼滤波更新阶段
对于每个匹配成功的track，用其对应的detection进行更新，并处理未匹配tracks和detections：

#tracker.py def update(self, detections): """Perform measurement update and track management. Parameters ---------- detections: List[deep_sort.detection.Detection] A list of detections at the current time step. """ # 得到匹配对、未匹配的tracks、未匹配的dectections matches, unmatched_tracks, unmatched_detections = self._match(detections)# 对于每个匹配成功的track，用其对应的detection进行更新 for track_idx, detection_idx in matches: self.tracks[track_idx].update(self.kf, detections[detection_idx]) # 对于未匹配的成功的track，将其标记为丢失 for track_idx in unmatched_tracks: self.tracks[track_idx].mark_missed() # 对于未匹配成功的detection，初始化为新的track for detection_idx in unmatched_detections: self._initiate_track(detections[detection_idx]) ...

参考：
Deep Sort with PyTorch deep_sort_pytorch
Deep SORT多目标跟踪算法代码解析(上)
Deep SORT多目标跟踪算法代码解析(下)
CenterNet+ deepsort实现多目标跟踪
Centernet+deepsort代码 https://github.com/kimyoon-young/centerNet-deep-sort

CenterTrack
论文链接：https://arxiv.org/pdf/2004.01177.pdf
项目链接：https://github.com/xingyizhou/CenterTrack
研究者将其跟踪器命名为 CenterTrack，该方法对一对图像应用检测模型，并利用前一帧的检测结果。给定最小输入，CenterTrack 可以定位目标，并预测它们和前一帧的关联。CenterTrack 就是这么简单、在线（不窥探未来）、实时。
从效果上来看，CenterTrack 在 MOT17 数据集上以 22 FPS 运行，达到了 67.3% 的 MOTA 值；在 KITTI 跟踪基准上以 15 FPS 运行，取得了 89.4% 的 MOTA 值，在这两个数据集上均取得了新的当前最优结果。
此外，CenterTrack 很容易扩展到单目 3D 跟踪，只需恢复额外的 3D 属性即可。以单目视频作为输入，以 28 FPS 运行，CenterTrack 在新发布的 nuScenes 3D 跟踪基准上实现了 28.3% AMOTA@0.2，显著超过单目基线方法。
基于深度学习端到端的多目标跟踪算法。(代表性的算法有SST) 现阶段end-to-end的算法还不多，大多处于实验室刷榜阶段，有进一步落地应用的及时更新。相关论文和代码如下:
· DAN: "Deep Affinity Network for Multiple Object Tracking" [paper] [code] In TPAMI 2019.
· MCSA: "Multi-Object Tracking with Multiple Cues and Switcher-Aware Classification" [paper] In CVPR 2019.
（这篇文章没有开源，基于SiameseRPN单目标跟踪器和行人ReID的多目标跟踪算法，解决长期跟踪下的目标漂移问题。利用SiameseRPN获取短期的目标线索，利用ReID特征计算目标间的匹配置信度，基于该置信度构建二分图，求解最小费用流得到长期的跟踪结果）
上述文章参考来源：
github.com/SpyderXu/multi-object-tracking-paper-list

多目标跟踪算法对比

文章图片

最新进展

文章图片

工业界青睐的算法在学术界其实并不重视，一方面是因为开源的原因，另一方面可以看到顶会的算法都不是注重速度的，通常用了很复杂的模块和trick来提升精度。
而且这些trick不是一般意义的trick了，是针对这个数据集的或者说针对糟糕检测器的一些trick，对于实际应用几乎没有帮助。
第一篇论文是基于DeepSORT改进的，它的创新点在于引入了轨迹评分机制，时间越久的轨迹可信度就越高，基于这个评分就可以把轨迹产生的预测框和检测框放一起做一个NMS，相当于是用预测弥补了漏检。
第二篇论文是今年9月份发在arxiv上的一篇论文，它的工作是把检测网络和嵌入网络结合起来，追求的是速度和精度的trade off。