单目视觉多目标跟踪方法的数据关联策略综述

2021-09-23柴文光陈香远

现代计算机 2021年23期

柴文光，陈香远

（广东工业大学计算机学院，广州510006）

0 引言

目标跟踪是利用计算机视觉技术采集到的视频或图像序列进行相关处理与分析，通过对目标上下文信息采集，对目标的外观位置信息和运动信息进行预测其位置并跟踪生成连续的运动轨迹的过程。目标跟踪面临的挑战有很多，如遮挡、形变、尺度变换等问题[1]。多目标跟踪指的是对多个感兴趣的目标进行目标跟踪，但多目标跟踪遇到的问题远远比对一个目标进行跟踪要复杂。如何对检测结果与预测结果进行精确的匹配，避免如漏检、目标重叠或者遮挡等情况，正是多目标跟踪所面临的难关。

目前，大部分多目标跟踪方法的思路都是基于目标检测结果进行跟踪的，大致流程如图1所示，通过目标检测、特征提取和预测、相似度计算、数据关联4个阶段进行持续的多目标跟踪[2]。

图1 多目标跟踪的阶段

首先，检测模块对作为输入的原始视频或图片序列数据进行目标检测，生成目标的对象框，然后进行特征提取和运动预测，根据计算得到的视觉特征和运动信息进行相似度计算（即判断两个对象属于同一个目标的可能性大小），最后在数据关联的阶段为每个对象分配各自的身份标识。持续循环上述过程，从而实现对感兴趣的多个目标的跟踪。

本文主要关注的是单目视觉多目标跟踪算法的最后阶段——数据关联。

1 数据关联策略

数据关联的本质就是在目标检测的基础上寻找最优的关联目标对[3]。在多目标跟踪过程中，为了保持对目标进行持续有效的跟踪，数据关联策略显得尤为重要。本节分别从传统方法、线性匹配、离线、在线以及端对端等数据关联策略依次展开产生阐述。

1.1 传统的数据关联策略

1.1.1 最近邻数据关联

最近邻数据关联（NNDA）方法[4]指的是以前帧目标检测结果的预测值为中心形成的空间区域作为搜索子空间，在该子空间搜索离中心点最近的检测点作为目标真实位置。

如图2所示，目标i在k时刻的预测位置为搜索子空间的中心，而在k时刻检测到跟踪子空间内存在目标Z1、Z2和Z3，距离中心最近检测目标Z3将被选中作为目标i的实际位置。

图2 最近邻数据关联

最近邻数据关联策略的长处是运算量小，算法复杂度较低，只适用于稀疏目标和少杂波环境的目标跟踪系统。当在目标被频繁遮挡，杂波密度大的环境下，容易出现误跟和漏跟现象。同时，搜索子空间的范围大小直接影响关联结果，对于落在搜索子空间范围外的检测目标会出现漏检或误检现象。

1.1.2 联合概率数据关联算法

联合概率数据关联（JPDA）算法[5]的思想是将搜索子空间内的所有观测点做不同的排列联合假设，根据各个观测点与各条轨迹的关联概率，对跟踪目标当前表观信息进行加权运算，从而更新轨迹。如图3所示，需要跟踪4个目标，而在跟踪子空间内共检测出Zk1、Zk2、Zk3、Zk4、Zk5和Zk6等6个观测点。由图3可知，Zk2落在目标1和目标2的重叠区域，Zk3落在目标2和目标3的重叠区域。Zk5落在目标1、目标3和目标4的共同重叠区域。

图3 JPDA算法场景

JPDA算法存在一些不足，需要引起我们的重视的。①JPDA算法需要把跟踪场景中目标的数量作为前提条件，否则无法处理旧目标的消失及新目标的出现。②JPDA算法无法判断轨迹的起止，需要增加额外计算成本。③协方差矩阵容易在关联区域引入额外的候选观测结果，即根据所有的观测值来更新协方差矩阵的方法可能导致数据关联出错。④在目标数目大且有实时性要求的场景中使用JPDA进行数据关联容易出现“组合爆炸”现象。

随着目标检测技术的快速发展，使用以上两种传统数据关联策略的多目标跟踪算法也同样得到多目标跟踪效果的提升。为了弥补传统数据关联的缺陷，有很多研究人员对传统的数据关联策略进行相应的改进，如文献[6]为了解决处于多个搜索子空间重叠的检测目标对跟踪目标的影响，简化了计算关联概率，同时修正了对重叠部分的影响因子，使得更好地对重叠部分的检测目标的划分与对多跟踪目标的状态估计。文献[7]将JPDA算法与小波的融合既利用小波滤波能够去除机动目标的白噪声又减少JPDA计算量。文献[8]利用各个候选的目标与预测点的距离比例对两者互联概率的加权归一化处理后，再根据计算出的新的概率分布对候选的目标进行加权完成跟踪目标的数据关联。

1.1.3 基于IOU的数据关联

在多目标跟踪领域，面积交并比（IOU）是一项很重要的数据关联指标。其度量方式如下：

式子（1）表明对前后两帧检测结果a边框与目标b的边框进行IOU度量，当两者越趋向于1，a、b是同一目标的可能性就越大。

文献[9]中的方法基于一种假设，无论是高精度检测，还是使用高帧率的视频片段，检测器对每一帧被跟踪的对象产生一个检测，即在检测中没有或只有很少的“间隙”并且在连续帧中检测到的对象具有明显的高重叠(相交-联合)。

其算法流程如下所述：

（1）初始化活动跟踪Ta与最终跟踪结果Tf,并通过阈值σl对输入的检测集D进行筛选。

（2）对于每个属于活动跟踪Ta的ti寻找跟它最后位置IOU最大的检测dbest。

（3）如果满足IOU(dbest,ti)≥σIOU，将跟踪的最新位置更新到dbest，否则判断highest_score(ti)≥σh和len(ti)≥tmin来衡量是否为一个最终的跟踪。如果ti是最终跟踪集即将其添加到Tf,如果不是则终止并从Ta移除ti。

（4）对于没有被匹配的检测，将其初始化为新跟踪插入活动的跟踪列表Ta中。

（5）完成上述步骤所有帧的跟踪，使得所有未分配给现有轨道的检测将启动一个新的检测。所有没有指定检测的轨道都将消失。再一次判断每个跟踪目标对应的检测最高检测得分是否满足highest_score(ti)≥σh和跟踪的长度len(ti)≥tmin。即通过过滤长度小于tmin的所有轨道和分数高于σh的至少一次检测，性能进一步提高。

这里的基本思想可以看作是参照了Canny算法[10]中的双阈值。高阈值对于某个确定的复选框是有价值的，而低阈值包含所有可能的复选框。利用前后帧的信息来识别错过的对象框，并将其添加到已确认的检测框中。然后根据跟踪持续时间和检测到的置信度对跟踪进行滤波。同时它的不足之处在于关于依赖检测，对运动过快的目标跟踪容易失效。

文献[9]的作者在接下来发表的一篇文献采用轨迹预测进行进一步的改进，V-IoU跟踪器[11]在IoU跟踪算法的跟踪流程上，添加了一个视觉单目标跟踪器对没匹配的跟踪进行预测关联。

1.2 基于线性匹配的数据关联策略

匈牙利算法可以被认为是“尽可能多”的数据关联思想，在多目标跟踪领域中，通过求解任务分配的组合优化，处理画面前后两帧的目标匹配问题，从而有效地实现对多目标的跟踪。匈牙利算法[12]的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。它是部分图匹配最常见的算法，从而判定二分图是否完全匹配。

匈牙利算法通常用于求解二分图最大匹配的。首先初始化二分图，即将当前帧中可能与上一帧中目标匹配的检测框确认,接下来按照ID顺序依次进行匹配，首先将可能与上一帧目标相匹配的当前帧的目标进行匹配，当发现当前帧中目标与上一帧进行匹配的目标已被匹配过了，为了使上一帧目标可以匹配到目标，则返回原先已匹配的目标尝试另一个可以与其匹配的目标进行匹配，并取消原来的匹配。当没找到能够符合要求的匹配方法，即可判断上一帧的目标消失，当前帧未匹配的目标被视为新出现的目标。

简单来说就是一个递归过程，尽可能找到让上一帧与当前帧目标一对一的匹配。该算法对运动模型和表观模型要求较高，需要将置信度较高的边送入匈牙利算法进行匹配，才能得到比较好的结果。

匈牙利算法存在一个很大的问题，就是该算法将每个目标的匹配对象视为相同级别，然而在实际的跟踪任务中，肯定有些匹配的框比较接近目标，有些框与目标相差较大，这时候如果将其视为同级会影响匹配准确度，所以在匈牙利算法的基础上又提出了KM算法，这也是实际任务中比较常用的算法，KM算法[13]解决的是带权二分图的最优匹配问题，即引入了权值的概念。所以SORT[14]和Deep SORT[15]等研究或方法均使用匈牙利算法解决数据关联问题。

1.3 基于离线的数据关联策略

1.3.1 最小代价流

根据多目标跟踪任务的特点从短期来看数据关联涉及到的是一个二分图匹配问题，从长期来看就是一个图网络模型。图4为常见的图结构。

图4 常见的图结构

（1）数据关联问题可以用最短路模型来描述，进一步来说，是用K-最短不相交路线来描述，其中节点就是跟踪对象id，边代表跟踪轨迹和检测之间的代价。这是多源多汇最短路，但是最短路没有限制中间节点的可重复性。

（2）数据关联问题可以用最大流模型来描述，边容量代表跟踪轨迹和检测之间的连接可能性，边容量的值只可能是0和1。而最后，最大流量因边容量的限制而不可能重复，也就是最多可能轨迹，从这一角度看来，匈牙利算法是最大流模型的特例。

（3）数据关联问题可以用最小代价流模型来描述，需要合理设定初始流量（代表了最终有多少条轨迹），还要设定边容量，从而避免所有流都流向同一条边。

表1 流模型对比

1.3.2 基于最大化后验概率模型的网络流建图

对于最小代价流而言，最难的地方在于设定初始流量和边容量，使得跟踪轨迹不交叉，而且跟踪轨迹尽可能多而合理。最重要的是，在网络模型中哪个节点是轨迹的起点或者终点是未知的，而多目标跟踪的目的是使得代价最小，极可能最终出现每条轨迹只有一个节点的情形。

简单的最小代价流结构存在以下问题：

（1）一开始就要选定哪些节点有可能成为起点，哪些节点有可能成为终点，这做法增加了参数量。

（2）类似于最大流模型，设定边容量为1可以保证每条边最多被选择一次。但是无法确保最多只有一个节点可以连接到目标节点，即无法保证跟踪轨迹的不重叠。

针对以上问题，较为经典的实现策略是采用网络流[16]构建数据关联框架。引入过渡节点和过渡边的概念，每个节点连接一条过渡边，这样通过设定过渡边容量，可以限制每个节点的流出流量，相应地就可以限制最多只有一个节点可以连接到目标节点。并让每个节点都连接起点，每个节点的过渡节点连接终点。这里的参数有：初始流量的大小（轨迹数量）、节点属于轨迹起点/终点的概率、节点到过渡节点的补偿（选择这个节点的补偿）、过渡节点到节点的概率（匹配代价）。

Butth等人[17]把最小代价网络流与拉格朗日松弛思想相结合，假设网络的每个节点都是连续帧之间的候选目标匹配对，并引入高阶轨迹平滑约束对网络流进行优化，从而改善多目标跟踪效果。在处理目标跟踪过程可能出现的身份错误切换问题，Shitrit等人[18]通过构建多商品网络流的方式有效避免该问题对跟踪效果的影响。在处理视频多目标跟踪常见的目标遮挡和背景干扰问题，Charis等人[19]尝试通过奖惩机制对不同的交互情况的跟踪轨迹进行修正，其做法是将一种成对代价函数融入最小代价流中。

除了通过网络流的方式对多目标跟踪进行数据关联，还可以通过图模型的方式实现。Henriques等人[20]就是基于图模型对多个目标进行检测响应融合和分离来实现对多个目标的跟踪。Dehghan等人在文献[21]和[22]中分别提出GMCP和GMMCP模型来完成数据关联任务，其中GMCP将外观和运动以全局的方式结合起来,即将序列的整个时间跨度合并到数据关联问题中。为了避免处理一个极其复杂的优化问题，他们的做法是集中在一个对象上，而不是同时解决所有的对象。同时也包含了所有其他对象的隐含性。在对象域的近似比其他近似方法(如有限时间局部性)使用的限制要小得多。而GMMCP首先利用二值整数规划制定目标函数，然后加入虚拟节点以处理目标缺失的问题，再通过聚合虚拟节点加速计算。最后利用最大二值整数规划求解无向图，从而同时获得多个团，实现对多目标有效的跟踪。

在多目标跟踪方法中，基于离线数据关联策略能在有限的时间对目标遮挡、漏检等复杂情况下的多目标跟踪性能具有一定的提升，并广泛应用于离线的视频检索和分析等方面。

1.4 基于在线的数据关联策略

基于离线数据关联的多目标跟踪方法的缺点也很明显，首先它计算复杂性偏高，然后它需要掌握视频画面前后帧的信息，缺一不可，所以对大部分实时跟踪场景的未来信息无法提前预知而使得它不能实现有效的跟踪。由此可见，基于在线数据关联的策略也非常重要，通过根据跟踪目标的历史运动轨迹与当前帧检测的结果进行亲和力计算，通过矩阵完成对跟踪目标与当前帧检测目标的最优匹配。早期，基于相关滤波的多目标跟踪方法能够在一定程度上预测跟踪目标的运动轨迹从而选择实现对多目标的数据关联，例如结合卡尔曼滤波[23]。

同样的，分层思想也可以应用在多目标跟踪方法中的数据关联策略[24]。Bae等人[25]引入了置信系数的方法，把目标轨迹片段与检测目标进行置信度计算，根据置信系数的不同取值而对跟踪目标进行分层数据关联。文献[26]同样通过不同的置信系数分为用于跟踪现存目标的弱检测结果和用于目标初始化和跟踪目标的强检测结果，根据强弱检测的结果进行数据关联达，从而避免跟踪失误并实现对多目标的有效跟踪。

1.5 基于端对端的数据关联策略

随着深度学习的大热，端到端的训练和预测框架展现出一定的数据利用优势，而传统的数据关联策略基本都不满足可导可微的特性，因此出现了很多近似的端到端数据关联框架。

1.5.1 多特征输入，输出关联矩阵

这类框架完成对多个目标的匹配的数据关联策略，如SUN等人在文献[27]中的DAN网络结构，这是一种典型的输入历史帧多条跟踪轨迹的特征和当前帧多个特征序列，输出多对多的关联矩阵，这种方式是通过形式的拟合来近似数据关联。FAMNet[28]将SOT和数据关联相集成解决所有跟踪轨迹和观测的匹配交互问题，并避免多目标跟踪过程中的虚警和误检的问题。DeepMOT[29]将传统不可微的数据关联模块改造成可微的模块，使用Bi-RNN网络实现全局的关联记忆，最后将关联矩阵通过连续的数据代替0-1匹配关系，从而实现可微。

1.5.2 基于RNN的数据关联策略

在多目标跟踪领域中，循环神经网络RNN同样被用于解决数据关联问题中。RNN根据给定的跟踪目标的历史状态和可能出现的新目标的信息，在每个时间段进行预测[30]。而RNN在多目标跟踪方法的广泛使用，证明了其能够在运动预测和状态更新等方面有不错的效果，即能够解决多目标跟踪中的数据关联问题。

例如Kim等人[31]在BLSTM网络引入RNN网络筛选出特定的检测目标以及目标的表征信息，并利用了假设跟踪（MHT）解决数据关联问题，进一步完成对多目标的跟踪。

AMIR等人[32]把跟踪目标的模型比作线索，提出了一种在时间窗口上对多个线索的依赖关系进行编码的方法，而多线索是被用来计算相似度分数，即利用过去时间的跟踪记忆，基于不同目标的空间分布进行位置关系预测，从而完成对跟踪目标的数据关联。

1.5.3 基于图卷积的数据关联

近年来，图卷积神经网络在多目标跟踪也得到了应用，文献[33]利用图卷积网络的消息传递机制，模拟离线数据关联的网络图，这种方式具有可以在线学习的优点,在该图中节点表示检测，不同帧的所有节点都通过边缘连接。使用CNN初始化图中的节点嵌入，并使用MLP编码几何信息这些嵌入所包含的信息通过神经消息传递在图中传播，以便进行固定次数的迭代。一旦此过程终止，由神经消息传递产生的嵌入将用于将边缘分类为有效目标和无效目标。