DeepSORT算法

　　谈及DeepSORT算法之前，希望你对【SORT算法】系列之深度解读已经熟悉流程。如果还未理解SORT算法流程，建议先理解整个SORT算法流程。在解释DeepSORT算法之前，有一些相关算法希望先知悉一下。

1. 数据关联之KM算法，可以参考博客【学习总结匈牙利算法到KM算法】及其相关资料学习；

2. 状态滤波估计算法KalmanFilter，可以参考博客【OpenCV学习系列】之KalmanFilter或者【状态估计滤波学习系列】之ExtendKalmanFilter等相关资料学习；

3. SORT算法流程学习，可以参考博客【SORT算法】系列之深度解读及其相关资料进行学习；

4. 在熟悉上述相关算法后，推荐延伸理解一下数据关联概念，推荐阅读博客多目标追踪之数据关联进行学习；

　　如果你对上述列举算法熟悉之后，基本上DeepSORT算法相对比较容易很多。当然，在阅读完本文你也可以参考一下文末链接相关博文对DeepSORT算法解读。这些博文对我理解该DeepSORT算法也受益匪浅。

抛出一个问题，DeepSORT算法出现主要解决什么问题？

1. 相对于SORT算法改善目标跟踪过程中ID切换问题；

2. 通过神经网络学习出特征进行级联数据关联，提升关联准确性同时满足实时性要求；

DeepSORT算法流程图

在学习DeepSORT算法之前，我们先看看SORT算法的流程图，如下：

　　简单说下SORT算法流程，首先对Trackers使用卡尔曼滤波进行预测，然后将预测后的Trackers与检测Dets进行计算代价匹配矩阵，然后使用匈牙利算法求解出Match、UnMatch_Dets、UnMatch_Trackers。随后，对Match上使用卡尔曼滤波进行状态更新，UnMatch_Dets新建生成新的Trackers，对UnMatch_Trackers进行后处理，主要看起是否丢失很长时间。具体详细流程可参考博文【SORT算法】系列之深度解读

Now，下面我们来看看DeepSORT算法的流程图，如下：

　　上述流程图大体描述了DeepSORT算法，其中最为核心的是级联匹配环节。先采取深度外观特征进行匹配，随后进行IoU二次匹配。关于深度外观特征循环30帧迭代匹配环节，可以参考下面的问题一代码解读。至于为什么需要按照时间顺序先后排序匹配与级联IoU匹配等，在参考目录博文里面有详细解说，我这里就不在赘述了。

DeepSORT算法代码解读

知晓该算法流程之后，还需要你实践一下该代码。原因由于里面会存在很多实现细节，这样能够更加深你对该算法理解。

代码源于DeepSORT实践代码链接

代码源于DeepSORT模型训练代码链接

模型训练教程可参考：【DeepSORT系列之】Cosine Metric Learning训练与demo可视化

解读该代码中一些实现细节，及为什么如此实现？

1.级联匹配中的代码片段：解释一下这个循环功能，主要是对confirmed_tracks按照时间由近及远排序进行数据关联。这里有个要点：【追踪列表中当track变成confirmed之后，除非它的time_since_update大于max_age将会删除，否则都会在这个循环进行数据关联操作】。主要区别在于循环遍历tracks时候丢失由近及远来进行级联匹配。（就是time_since_update的值越小越优先进行关联），说到底这里还是强依赖深度特征计算距离约束区分度要高。

    for level in range(cascade_depth):
        if len(unmatched_detections) == 0:  # No detections left
            break

        track_indices_l = [
            k for k in track_indices
            if tracks[k].time_since_update == 1 + level
        ]  # 由于tracks传入的track_indices是confirmed_tracks的索引
        # 这里的confirmed_tracks可能time_since_update不是max_age的话，它的状态不会改变
        if len(track_indices_l) == 0:  # Nothing to match at this level
            continue
        # 这里可以看出，先对最近时间的confirmed_tracks进行关联，逐步到久时间的未关联的confirmed_tracks
        # 注意：这里的unmatched_detections是逐渐变少的
        matches_l, _, unmatched_detections = \
            min_cost_matching(
                distance_metric, max_distance, tracks, detections,
                track_indices_l, unmatched_detections)
        matches += matches_l # 将过去max_age帧的confirmed_tracks进行关联成功的tracks相加即可

上述级联匹配之后的cost_matrix还需要进入下面的gated_metric函数进行运动观测阈值约束。进一步提升精确关联度，同时采取马氏距离来进行计算。

        # 将tracks与dets进行深度外观特征关联与匹配生成cost_matrix.
        def gated_metric(tracks, dets, track_indices, detection_indices):
            features = np.array([dets[i].feature for i in detection_indices]) # 外观特征维度
            targets = np.array([tracks[i].track_id for i in track_indices]) # 跟踪列表目标
            cost_matrix = self.metric.distance(features, targets) # nn_matching.NearestNeighborDistanceMetric()
            cost_matrix = linear_assignment.gate_cost_matrix(
                self.kf, cost_matrix, tracks, dets, track_indices,
                detection_indices)

            return cost_matrix

2. 在_match()函数里面，级联匹配之后会进一步使用IoU进行关联匹配。为什么这里还要使用IoU进一步关联，可以参考关于 Deep Sort 的一些理解。其实主要就是通过IoU来看检测器与跟踪器之间的置信度。

        # Associate remaining tracks together with unconfirmed tracks using IOU.
        # unconfirmed_tracks与tracks列表里面time_since_update==1的进入iou候选匹配列表
        iou_track_candidates = unconfirmed_tracks + [
            k for k in unmatched_tracks_a if
            self.tracks[k].time_since_update == 1]
        # 就是未关联成功的tracks列表同时其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 = \
            # min_cost_matching使用的是iou匹配
            linear_assignment.min_cost_matching(
                iou_matching.iou_cost, self.max_iou_distance, self.tracks,
                detections, iou_track_candidates, unmatched_detections)

小结

　　关于SORT算法逐帧进行匹配会导致ID switch现象在DeepSORT算法中得到了有效的降低。究其主要原因还是在于数据关联阶段采用深度表观特征进行匹配，极大提升了前后帧直接目标匹配精度。当然，DeepSORT算法在设计流程中也采用很多有效的方式，比如级联匹配策略中余弦距离、马氏距离、IoU数据关联的先后顺序，针对丢失目标根据周期长短在级联匹配中排序等等。虽然，DeepSORT算法不是端到端的目标跟踪算法，但是，其提出极大改进目标跟踪在工业界应用。

参考

Deep sort算法代码解读
论文翻译DeepSORT
目标跟踪初探（DeepSORT）