主流网络模型之目标跟踪

什么是目标追踪(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)上滑动搜索,最后得到一个响应图,图上最大值对应的点就是算法认为的目标中心所在位置。


· 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进行匹配,所以出现几种情况

  1. Detection和Track匹配,也就是Matched Tracks。普通连续跟踪的目标都属于这种情况,前后两帧都有目标,能够匹配上。
  2. Detection没有找到匹配的Track,也就是Unmatched Detections。图像中突然出现新的目标的时候,Detection无法在之前的Track找到匹配的目标。
  3. Track没有找到匹配的Detection,也就是Unmatched Tracks。连续追踪的目标超出图像区域,Track无法与当前任意一个Detection匹配。
  4. 以上没有涉及一种特殊的情况,就是两个目标遮挡的情况。刚刚被遮挡的目标的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方阵):

  1. 对于矩阵的每一行,减去其中最小的元素
  2. 对于矩阵的每一列,减去其中最小的元素
  3. 用最少的水平线或垂直线覆盖矩阵中所有的0
  4. 如果线的数量等于N,则找到了最优分配,算法结束,否则进入步骤5
  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_cov


def 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多目标跟踪算法代码解析(下)

上一篇:2021 美赛D题思路


下一篇:[Desktop Security Series] - Web Browser Tracking