改进YOLOv3和Deep Sort的多目标跟踪算法

胡 漫，曹继华，李士心，彭芙蓉

（天津职业技术师范大学电子工程学院，天津 300222）

随着计算机和人工智能的发展，目标检测和跟踪成为人们关注的热点，在自动驾驶、智能交通和视频监测等场景有着越来越重要的作用。目标检测是在图像中确定目标物体的位置和类别。传统的目标检测算法是在图像上先作选择区域，再人为设定特征提取，最后根据提取的特征进行目标分类。而基于深度学习的目标检测则是通过神经网络来提取特征。神经网络在训练学习后有很强大的特征提取能力，使得检测精度更高。基于神经网络的目标检测包含一阶段目标检测（One-stage）和两阶段目标检测（Two-stage）。Onestage中经典的算法有SSD、CornerNet、YOLO系列等，Two-stage中经典的算法有R-CNN、Faster R-CNN、Fast R-CNN等。目标跟踪是估计视频序列中的目标运动状态，得到目标在每一帧即每个时刻的位置。随着目标检测精度的提高，目标跟踪也得到发展。基于检测的目标跟踪分为2步：通过目标检测，检测出每一帧图像中的目标物体；用数据关联算法将目标物体跟踪预测的边界框（bounding BOX，BBOX）和目标检测出的目标物体边界框相关联，之后用检测的边界框代表成功跟踪的物体。

近年来，单目标跟踪算法已发展得相对成熟，但在实际的场景中，如交通、自动驾驶、智能监控中跟踪算法是多目标问题，多目标跟踪算法还面临着许多问题，如目标间的遮挡导致遮挡后目标发生变换，即目标ID切换，目标漏检或误检，未知的目标类别等。针对多目标跟踪问题，Bewley等[1]提出了SORT算法，该算法用卡尔曼和匈牙利算法实现多目标跟踪，但在有遮挡情况下效果较差；Wojke等[2-3]提出DeepSort算法，在SORT算法基础上加入了关联匹配，改善了遮挡问题，但依然存在漏检追踪不到的问题。YOLO系列在检测方面也得到了很大发展，李珣等[4]通过对道路场景分析改进YOLO-voc网络，改善目标检测率低的问题；黎洲等[5]改进YOLOv2解决检测实时性问题；刘军等[6]加强了Ting YOLOv3网络，并与卡尔曼和匈牙利算法结合实现跟踪；柳长源等[7]把YOLOv3的主干轻量化并重新K-means聚类提高检测效率。针对现实场景中有遮挡检测时目标漏检和跟踪时目标ID切换现象，本文对YOLOv3进行改进，用完全交并比（complete intersection over union，CIOU）损失代替原算法中的边界框损失函数，同时对先验框（Anchor BOX）用K-means++算法重新聚类选取适合的Anchor BOX；将DeepSort算法中第二次匹配的交并比（intersection over union，IOU）匹配用广义交并比（generalized intersection over union，CIOU）匹配代替，提高匹配性能；将改进的YOLOv3与DeepSort结合，实现目标跟踪，减少遮挡时目标ID切换现象。

1 YOLOv3算法及改进

1.1 YOLOv3算法

YOLO是一种端到端的目标检测，将检测目标简化成回归问题，求解包含有目标的框和目标分类的概率。YOLOv2是YOLO的改进，YOLOv3在YOLOv2的基础上融合添加了特征金字塔网络（feature pyramid network，FPN）[8]和残差网络（ResNet）[9]等提高分类准确度和速度。

YOLOv3主要由特征提取网络和预测网络构成。YOLOv2使用Darknet-19网络提取特征，YOLOv3的特征提取网络是在YOLOv2的基础上加入残差网络中的残差（residual）结构。该特征提取网络中加入了直连（shortcut）并使用了许多3×3和1×1的卷积层连接，结构复杂。因为总体有53个卷积层，所以其也被称为Darknet-53，其和CNN网络结构的不同之处在于Darknet-53是一个全卷积网络。在YOLOv3的前向传播中，通过变换卷积核的步长来改变张量的尺寸，卷积步长为2，每卷积一次图像边长减少1/2，Darknet-53中有5次卷积，特征图经过5次卷积后减小到原来的1/32。

在预测方面，YOLOv3使用多尺度结合的方式把一个图片分为13×13、26×26、52×52的网格，各网格负责自身网格范围的检测。预测任务输出的特征大小为N×N×[3×（4+1+C）]，其中：N为网格大小；3为每个网格的边界框数目；4为边界框的坐标数目；1为目标预测的值；C为预测的类别数目。类别预测上YOLOv3把单标签分类的softmax层变为多标签分类的逻辑回归层，使用逻辑回归分类器中sigmoid函数将输出范围限制到0～1，对各个类做二分类处理，当输出值＞0.5表示检测的物体属于目标类。

YOLOv3沿用了YOLOv2预测的方法，利用Kmeans聚类的方法在训练集中聚类出9个先验框作为初始边框。边界框是通过回归得到4个偏移值tx、ty、tw、th后在先验框的基础上进行变换得到的边框。变换公式为

式中：bx、by为边界框在特征图中心点的坐标；bw、bh分别为边界框的高和宽；cx、cy为特征图现在中心左上角的网格高和宽；pw、ph分别为Anchor Box的高和宽；σ（）为sigmoid函数。

YOLOv3的损失函数是把YOLOv2中分类损失变成二分交叉熵。损失函数由中心坐标误差、宽高坐标误差、置信度误差和分类误差4部分组成。损失函数为

式中：第1项为中心坐标误差；λcoord为5，表示边界框损失的权重；k×k为网格的大小，即13×13、26×26和52×52；M为3表示候选框的个数；Iijobj为第i个网格中第j个先验框是否负责检测目标，负责Iijobj为1，否则为0；xi、yi为横纵坐标。第2项为宽高坐标误差，wi、hi为高度和宽度。第3项和第4项为置信度误差，λnoobj为0.5，表示置信度损失的函数；为真实值，取值决定于边界框是否负责预测目标，若是则取1，否则为0；Iijnoobj与Iijobj相反，为第i个网格中第j个先验框不负责检测目标。最后一项为分类误差，pi为类别预测值，为其真实值。

1.2 改进的YOLOv3

1.2.1 先验框改进

YOLOv3共使用9组Anchor Box进行预测，当数据集变化时，Anchor Box的尺寸也需变化以更好地检测目标，提高检测精度。初始YOLOv3中的Anchor Box是针对COCO数据集聚类得到的，因为COCO数据集有80类且大小不一，所以聚类出来的Anchor Box形状不同。初始YOLOv3使用K-means算法聚类Anchor Box，但K-means算法初始点的选择对聚类结果有很大的影响，不能保证是全局最优。为降低初始点选取对结果的影响，本文采用K-means++[10]算法对初始点选取进行改进，逐个选取初始点，对KITTI数据集中行人和车辆2类重新聚类先验框。K-means++算法的步骤为：①从输入的数据集Y中随机选个样本点当作开始的聚类中心Cj；②对每一个样本点Yj分别计算其与已选取聚类中心的距离D（Yj），D（Yj）=1-GIOU（Yj，Cj）；③按轮盘法选取新的聚类中心，距离即D（Yj）大的点被选取的概率较大；④重复迭代步骤②和步骤③，直到选出9个聚类中心点；⑤利用选出的9个聚类中心点作为初始点运行K-means算法。

1.2.2 边界框损失函数改进

YOLOv3算法中用IOU来评价2个边界框的相似程度，IOU为2个边界宽度交并比，表达式为

式中：A、B分别为预测框和真实框。

YOLOv3对1和IOU的差值梯度回归表达式为

该损失函数能有效训练网络，但当预测框和真实框没有交集时，不能表示2个框的远近，此时没有梯度回传不能进行训练。针对该问题Rezatofighi等[11]提出了GIOU的新方法，在IOU的基础上为2个框加上了最小外接矩形，从而避免了IOU的缺点。GIOU首先计算预测框、真实框和其最小外接矩形的面积S及其IOU，再用最小外接面积减去2个框的并集的差除以S，最后用IOU减去除数，即

GIOU依然依赖IOU导致GIOU在2个垂直方向上误差大，难以收敛，回归效果差。Zheng等[12]提出了距离交并比（distance intersection over union，DIOU）的想法，与GIOU相比，用DIOU最小化预测框和真实框中心点的距离来加速收敛过程，表达式为式中：d2（A，B）为两框中心点之间的欧氏距离的平方；C为能同时包含2个框的最小区域的对角线的距离。

DIOU直接最小化预测框和真实框的距离，所以收敛速度很快。但是，DIOU没有考虑预测框和真实框的纵横比。文章还提出CIOU LOSS，即在DIOU的基础上添加一个αv因子，把预测框横纵比拟合真实框横纵比将框的横纵比考虑进去，提高了精度。表达式为

综上对比，本文选用CIOU损失函数来改进边界框损失函数。完整CIOU损失函数为

改进后的YOLOv3损失函数为

2 DeepSort目标跟踪

DeepSort跟踪算法框架如图1所示。在YOLOv3检测出目标后使用卡尔曼滤波算法预测跟踪目标，使用匈牙利算法进行计算，关联匹配时融合运动特征和外观特征。

图1 跟踪算法框架

2.1 卡尔曼滤波和匈牙利算法

卡尔曼滤波可以基于当前帧的目标位置来预测下一帧的目标位置。在任一视频帧中将状态向量

X=[u，v，r，h，u′，v′，r′，h′]作为目标轨迹模型，其中：u、v分别为目标边界框中心的水平和垂直位置；r、h分别为目标边界框的长宽比和高度；其余4个参数为对应的速度信息。通过卡尔曼滤波器进行预测和更新，预测是利用上一帧检测框和运动速度等预测当前帧相应信息，预测方程和协方差方程为

式中：X（k|k-1）为k-1时预测到k时的状态向量；X（k-1|k-1）为k-1时刻的最优状态向量；P（k|k-1）和P（k-1|k-1）分别为前者的协方差矩阵；Q为噪声的协方差。更新是对预测值和观测值线性加权来得到接近真实状态的预测值。更新k时刻的协方差，使更新重复运行，表达式为

式中：X（k|k）为k时刻协方差的更新结果；Kk为k时刻卡尔曼增益矩阵。

匈牙利算法主要解决检测目标和预测目标的匹配，该算法对融合运动特征和外观特征级联匹配整合得到代价矩阵求解得到线性匹配，从而完成上下2帧检测和预测目标的匹配。

2.2 融入外观特征的关联匹配

目标跟踪的一个关键问题便是将检测目标与跟踪预测目标进行关联匹配，本文的关联匹配融合了运动特征，即空间坐标信息和外观特征。

对于运动特征，采用马氏距离计算改进YOLOv3网络检测得到的目标和卡尔曼跟踪预测目标之间的距离为

采用二值函数公式如式（13）对式（12）进行匹配限制，当二者间距离≤特定阈值时，表示关联匹配成功。

由于跟踪过程中，目标容易被遮挡或出现目标交叉而导致跟踪目标丢失或发生错配，只用运动特征来关联匹配，很大可能会出现目标丢失或错配，需加入外观特征来减少这种情况。

对于外观特征，由于同一个物体在不同图像中生成的特征向量间余弦值很小，所以采用余弦度量距离计算第i个跟踪预测目标的所有特征向量和第j个检测目标特征向量间余弦距离的最小值，余弦度量计算式为

同样采用二值函数公式（15）对式（14）作匹配限制，当最小值≤特定阈值时，表示关联匹配成功。

对运动特征和外观特征进行线性加权作为最终的关联匹配，表达式为

2.3 GIOU匹配

在关联匹配后，把未成功匹配和没有匹配的预测目标放在一起与未匹配的检测目标继续GIOU匹配，用来减少因动作突然变化或一部分被遮挡而造成的匹配错误。由于是在关联匹配后继续防止匹配错误，使用GIOU加入最小外接矩形面积匹配可以达到较好的效果。首先计算预测框和检测框间的GIOU如式（5），经过1-GIOU后得到1个代价矩阵，然后将代价矩阵输入匈牙利算法，从而得出线性匹配的结果。最后筛选匹配结果，删去GIOU较小的区域。合并关联匹配和GIOU匹配的结果为最终的匹配结果。

3 实验与分析

3.1 实验准备

选用KITTI数据集[13]作为本文的检测数据集，KITTI是当前自动驾驶场景下最全面的数据集，包含市区、高速公路、乡村等地方采集的数据。其中，KITTI目标检测数据集中训练集、测试集分别包含7 481张和7 518张图片；KITTI目标跟踪集中，训练集有21个视频序列，测试集有29个视频序列。目标检测数据集 中 原 有 标 签 为8类，即Car、Van、Truck、Tram、Pedestrain、Person（sit-ting）、Cyclist、Misc；根据本文需要，把这8类合并为车辆和行人2类，将Misc类删除。训练集按8∶2分为训练集和测试集。实验使用Windiows 10操作系统、Pycharm软件、Python语言、TensorFlow框架搭建环境完成。

3.2 评价指标

目标检测选用均值平均精度（mean Average Precision，mAP）和F1-score（F1）来评价。mAP计算前需知精确率P和召回率R这2个指标，计算式为

精确率代表其中1类在预测目标时，预测正确的样本占总体正确样本的比例，召回率代表其中1类预测目标时，正确样本占总预测样本的比例。AP为用准精确率作纵坐标、召回率作横坐标画出的P-R曲线。AP为曲线下的面积，mAP为AP的平均值，本文数据集中只包含2个类别，mAP计算式为

F1-score为对精准度和召回率的调和平均，该值能够更好地表示模型的好坏。

3.3 实验结果分析

选取KITTI-Tracking中序号00中的80～100帧图像、序号02中100～120帧图像、序号15中110～135帧图像，因为这些序号的视频段中车辆行人较多且有不同程度的遮挡。将图像合成视频输入到整个算法中，检测跟踪并把输出的结果视频分解为帧照片。图2为原YOLOv3与改进后的算法检测对比图。

图2 算法检测对比

图2（a）中左面白色汽车和右方黄色汽车没有被检测到，而图2（b）中改进后算法能够检测出图2（a）中未检测到的车辆。

序列15的原YOLOv3-DeepSort的跟踪结果与序列15的改进后算法的跟踪结果分别如图3和图4所示。

图3 原YOLOv3-DeepSort跟踪检测结果

图4 改进后算法跟踪检测结果

对比图3、图4可知，由于长时间遮挡，图3（b）中2个行人在跟踪时丢失1个，只匹配跟踪到1人，而改进后的算法在同一帧时依然能够匹配跟踪到2个行人，没有丢失目标。

图5为序列02的原YOLOv3-DeepSort的跟踪结果，图6为序列02的改进后算法的跟踪结果。

图5 原YOLOv3-DeepSort跟踪检测结果

图6 改进后算法跟踪检测结果

对比图5、图6可知，由于两车交汇遮挡，图5（b）中的车辆17没有被匹配跟踪到而丢失目标，而图6（b）中改进后算法依然能够匹配跟踪到车辆没有丢失目标。

改进后的算法与原YOLO算法的实验数据对比结果如表1所示。

表1 改进后算法与原YOLO算法的实验数据对比

从表1可知，改进的YOLOv3比原YOLOv3在KITTI数据集的mAP提高2.19%，F1提高1.23%。

4 结语

本文提出一种基于改进YOLOv3和DeepSort的跟踪算法，用于提高现实场景有遮挡情况中检测跟踪车辆、行人等目标的漏检和目标ID切换的误检。通过使用K-means++算法重新聚类选取适合的先验框，改变边界框损失函数对YOLOv3改进提高精度，再结合DeepSort算法，将未成功匹配及未匹配的检测结果用GIOU匹配代替IOU匹配。最终算法在KITTI数据集上的mAP提高2.19%，F1-score提高1.23%，能够在部分遮挡时，较少漏检和目标ID切换的误检。本文虽在此方面取得一定的成果，但仍有继续研究的地方，如考虑复杂场景（雨雪大雾天气）中的检测跟踪，可结合暗通道去雾算法或其他方法。