基于马尔科夫决策过程的多目标跟踪算法

王诗言，吴华东，余 翔

(重庆邮电大学 通信与信息工程学院，重庆 400065)

0 引 言

目标跟踪是计算机视觉中的一个重要问题。通过检测的方法进行跟踪已广泛用于异常行为分析和智能交通等许多领域。在多目标跟踪(multiple object tracking，MOT)中，关键是如何有效处理目标遮挡和数据关联问题。解决此问题的经典解决方案是提取目标的单个特征，例如运动特征[1-2]，然后计算特征的相似度，以此来确定两个目标是否属于同一轨迹。该方法具有计算简单，速度快的特点，但跟踪成功率不高，实际应用效果较差。为了弥补该方法的不足，更好地描述目标，研究人员通过结合几种不同的特征进行处理，以提高跟踪器的性能。例如，利用多特征融合的方法[3]，改善了跟踪效果，同时还减少了标识切换的总数。但是，目标遮挡问题仍然没有很好得到解决。

随着机器学习的兴起，结合了机器学习方法的目标跟踪算法蓬勃发展，并逐渐超越传统方法，特别是在提取目标特征的处理方法上，具有更大优势。文献[4]通过训练卷积网络模型，身份交换(ID switch)的次数减少了45%。同样，通过卷积网络提取人体不同部位的特征，然后将其组合，可以获得对人体外观的更好描述[5]。虽然精度得到了进一步提高，但是跟踪速度太慢而不能满足实时要求的问题也很明显。为了处理数据关联问题，文献[6]将两个图像片段直接输入到孪生神经网络(siamese network)中，并直接输出两个目标是否属于同一轨迹的结论，但跟踪效果和速度都不太令人满意。而最近的评估结果表明，基于边界框跟踪的性能提升趋近饱和，而基于低层信息(像素级别)的跟踪有望进一步提升跟踪器性能[7-9]。

基于上述研究，在多目标跟踪领域，不仅要处理单个目标的消失、遮挡等情况，更要解决多个目标之间互相干扰的问题。跟踪算法能否捕捉目标状态的改变决定着跟踪性能的好坏。而马尔科夫模型能够有效预测多个状态的转移概率，该模型的特点正好能解决多目标跟踪问题中的关键难点。由此出发，本文提出一种基于马尔科夫决策过程(Markov decision process，MDP)的多目标跟踪算法，利用目标不同状态之间的转移关系，学习每个状态特有的策略，解决了多目标跟踪中遮挡和快速运动的问题。图1为所提算法的流程图。其中，对不同状态下的MDP策略和分类器训练是本文提出算法的重点。在多目标跟踪领域，能否有效捕捉目标状态改变等信息，很大程度决定了跟踪器的性能。因为马尔科夫模型能够有效解决状态之间的转移问题，因此可将其运用到本文提出的算法中来。本文将在线多目标跟踪建模成马尔科夫过程中的决策模型，将一个目标在视频中从出现到消失的过程建模成MDP，如图2。在每个MDP中的每一个状态，都学习对应的策略来决定状态的改变。本文用超像素度量因子和重叠率来计算轨迹之间的关联程度。将数据关联中的学习相似性函数看作是MDP中的学习策略。另外，本文还将目标的出现和消失看作是马尔科夫决策过程中的状态转移，然后使用现有的单目标跟踪方法来处理这类问题。通过2DMOT2015基准测试表明，在多目标跟踪精度(multide object tracking accuracy,MOTA)这一指标上，本文提出的算法与其他对比算法相比，具有更高的得分，同时在跟踪速度上也有更好的效果。与此同时，本文提出的算法也能有效解决遮挡和快速运动问题。

图1 算法流程图Fig.1 Algorithm flowchart

图2 多目标跟踪问题转化为马尔科夫决策过程Fig.2 Multi-target tracking transformed into Markov decision process

1 在线多目标跟踪模型框架

1.1 MDP定义

将每一个目标从出现到消失的整个过程建模成一个马尔科夫决策过程，该决策过程由以下元组构成(S,A,T(·),R(·))：

1)s∈S，其中s表示目标的状态；

2)a∈A，其中a表示目标执行操作，A表示动作集合；

3)T:S×A→S，其中T表示状态转移函数，描述了在每个目标状态将要执行的操作和将到达的下一个状态；

4)R:S×A→，其中R表示奖励函数，定义了在状态s情况下，执行了操作a后的回报。

状态转移。把MDP中的状态分为4个子集：S=S活跃∪S已跟踪∪S丢失∪S不活跃。图3为4个子集之间的状态转移关系。“活跃”状态是每个目标的初始状态，当检测到目标即进入该状态。“活跃”状态可以转换到“已跟踪”或“不活跃”状态。理想情况下，从目标检测器得到正确结果后，目标将进入“已跟踪”状态，当发生错报、误报即进入“不活跃”状态。进入到“已跟踪”状态的目标可以继续保持该状态，若发生遮挡、从视野中消失等情况，就会暂时进入“丢失”状态。同理，“丢失”状态的目标或者继续保持该状态，或者因为再次出现在视野中而进入“已跟踪”状态，或者由于已经丢失足够长的时间而进入到“不活跃”状态。最终，“不活跃”状态就是每个目标的终止状态，且不能跳出。

图3 4个子集的状态转移图Fig.3 State transition diagram of four subsets

状态转移函数。各个目标状态间有7个可能的转移，图3所示为各个状态和转移关系。在MDP中，所有的转移都是确定性的。例如，在“丢失”状态上执行转移a6，目标就会进入到“已跟踪”状态：T(s丢失,a6)=s已跟踪。

奖励函数。在提出的MDP框架中，对奖励函数根据不同状态进行差异化设计，其具体参数由已标注的训练样本通过不同的方法学习得到。

1.2 MDP策略

在马尔科夫决策过程中，策略π是一个从状态集合S到动作集合A的映射，例如π:S→A。给定目标的当前状态，不同的策略会决定采取何种状态转移动作。而在MDP中，策略的学习就是为了最大化奖励函数。

1.2.1 “活跃”状态下的策略

在“活跃”状态下，MDP需要做出决策：将目标检测保持在“活跃”状态或者转移到“不活跃”状态。这个决策可以被理解为跟踪之前的预处理步骤。通常使用诸如非最大抑制或阈值检测分数之类的策略。用归一化特征向量φ活跃(s)离线训练一个二进制的支持向量机(support vector machine)，训练样本是已标注的训练数据集。其中，φ活跃(s)包含目标的二维坐标、宽、高和检测得分，定义“活跃”状态下的奖励函数为

(1)

(1)式中：(w活跃,b活跃)定义为SVM的超平面；当a=a1时，y(a)=+1；当a=a2时，y(a)=-1。

1.2.2 “已跟踪”状态下的策略

在“已跟踪”状态下，MDP需要判定是继续保持这个状态还是转移到“丢失”状态。只要目标没有发生遮挡或者始终保持在相机的视野范围内，就应该判定继续保持“已跟踪”状态，否则就应该标记为“丢失”状态。在这个状态下的决策选择，类似于单目标跟踪[10]。建立一个基于超像素的表观模型来定义目标的置信图，通过定义前后帧目标的置信图重叠率和全局平均置信图来进行判别，当该表观模型能在下一帧成功跟踪目标，表明目标继续处于“已跟踪”状态，否则进入“丢失”状态。

(2)

(2)式中，Vobcv(i)∈[-1,+1]，那么基于超像素的表观模型由4个因子共同构建：聚类置信值Vobcv(i)，聚类中心fc(i)，聚类半径rc(i)和所属该聚类的所有超像素。每一个聚类里面的超像素的置信值为

(3)

(3)式中,

∀r=1,…,Nt；i=1,…,n

(4)

(4)式中，O0和V0为阈值，当a=a3时，y(a)=+1；当a=a4时，y(a)=-1。因此，仅当Vavg和O(t,t-1)同时大于设定的阈值时，目标继续保持“已跟踪”状态，否则就进入到“丢失”状态。在实验过程中，阈值的设定会对实验结果产生较大影响。阈值过高，可能出现漏检，阈值过低，会造成误检。本文通过大量实验测试得出，当两个阈值均为0.85时，跟踪效果最佳。

图4 置信图流程图Fig.4 Confidence diagram flow chart

1.2.3 “丢失”状态下的策略

在“丢失”状态下，MDP需要判定目标是保持现有状态，还是转移到“已跟踪”状态，或者是“不活跃”状态。假定目标处于“丢失”状态的时间大于T丢失，那么就标记为“不活跃”状态并结束本次跟踪。在此状态下策略选择的难点，是在转移到“已跟踪”和保持“丢失”之间做出决定。将上述难点视为数据关联(data association)问题[11]:为了将“丢失”的目标转换到“已跟踪”状态，需要将目标和检测器检测到的结果进行关联检测，否则目标就保持“丢失”状态。

(5)

(5)式中：k是M个潜在检测的索引；当a=a6时，y(a)=+1；当a=a5时，则y(a)=-1。综上，在“丢失”状态下进行策略学习的任务简化为学习决策函数中的参数(w,b)。

2 基于马尔科夫决策过程的多目标跟踪算法

将MDP的策略/奖励应用于多目标跟踪问题。在多目标跟踪问题中，将每一个目标建模成一个MDP，并用学习到的策略来跟踪目标。给定一个新的输入视频帧，算法根据每个MDP所处的不同状态做差异性处理。首先，处于“已跟踪”状态的目标，根据已学习好的策略判定其跳跃状态：继续保持“已跟踪”状态还是转换到“丢失”状态。其次，对于“丢失”状态的目标，若其检测值Vodk与任意一个“已跟踪”的目标没有交集(也就证明该检测框不属于“已跟踪”)，就利用公式f(Tlt,Vod)=wΤφ(Tlt,Vod)+b计算“丢失”状态与上述检测值的相似性得分。再次，利用匈牙利算法[12]对所求得的相似性分数来获得检测和“丢失”目标之间的分配。根据分配，与某些目标检测Vodk具有相关性的丢失目标Tlt将转移到“已跟踪”状态。否则，他们会继续处于“丢失”状态。最后，如果视频中检测到新目标，其检测值为Vodk时，用该检测值作为新目标t的初始值。如果根据所学策略执行了a1，就进入“已跟踪”状态，否则进入“不活跃”状态。算法1详细介绍了使用MDP的多目标跟踪算法。需要指出的是，处于“已跟踪”状态的目标比处“丢失”状态的目标具有更高的优先级。

算法1 整体算法流程

1.初始化：Tra←∅

2.for视频序列v中的第l帧

3.for轨迹Tra中的“已跟踪”目标ti

4.根据策略，将ti转移到下一个状态

5.end

6.for轨迹Tra中的“丢失”目标ti

7.for与跟踪目标没有任何重叠的检测值Vodk

8.f(Tlti,Vodi)=wΤφ(Tlti,Vodi)+b

9.end

10.end

11.使用匈牙利算法对“丢失”目标记性数据关联

12.for轨迹Tra中的“丢失”目标ti

13.根据分配的值，将ti转移到下一个状态

14.end

15.for出现新目标t，其检测值为Vodk

16.为新目标t用检测值Vodk初始化MDP

17.if跟踪策略执行了状态动作a1

18.将目标t转移到“已跟踪”

19.Tra←Tra∪{t}

20.else

21.将目标t转移到“不活跃”

22.end

23.end

24.end

3 实验结果与分析

本文实验在MOT15[13]基准测试数据集中评估了跟踪器的性能。该基准测试评估具有测试序列的跟踪性能，包括带有移动摄像头的正面视图场景下的监控设置。评估指标如表1(表中lower表示越低越好，higher表示越高越好)。其中，MOTA包含误报数量、丢失目标数量和身份交换次数信息，这项指标能够有效反映跟踪器性能。

表1 多目标跟踪的评价指标Tab.1 Evaluation for multi-target tracking

图5是跟踪结果的可视化图像。在图5中，按照红橙黄绿青蓝紫的顺序分别对应目标1，目标2，…，目标7。在序列ADL-Rundle-1中，在第40帧和第90帧，目标4(绿色框)与周围目标1(红色框)的距离较近。LMF和文献[15]的算法，由于未能正确进行数据关联，不同目标之间的信息相互干扰，导致跟踪框有所偏移。而本文提出的算法，利用超像素度量因子和重叠率因子作为衡量标准，能够始终保证跟踪准确。在第40，202帧，目标6(蓝色框)、目标7(紫色框)与周围目标具有相似外观，与本文对比的两种算法相比均有不同程度的漂移，甚至跟错了目标。

图5 跟踪结果可视化Fig.5 Visualization of tracking results

遮挡方面，在序列TUD-Campus中，目标1经过目标6遮挡后，对比算法未能在目标1再次出现时跟踪上，最终跟错目标。对于发生遮挡的目标，其状态如何改变难以确定。而本文提出的算法，将目标建模成一个马尔科夫决策过程，充分考虑了状态之间的关联，并且利用学习策略进行状态转移，能够有效处理目标遮挡的情况。

本文算法结合历史图像信息，建立了基于超像素的表观模型，在目标快速移动时，同样有较好的表现。在序列ETH-Crossing中，对于快速移动的目标4，提出的算法出现少许偏移，但是相较于对比算法还是更具鲁棒性。

表2展示了本文算法在MOT15数据集中对目标跟踪任务的9项指标对比结果。总的来说，本文提出的算法将目标建模成马尔科夫决策过程，并在决策阶段加入了基于超像素的表观模型，同时引入了全局平均置信值Vavg和置信图重叠率O(t,t-1)，成功地提升了模型的性能。在MOTA指标上，本文算法能够达到36.5，高于其他对比算法。同时返回较少数量的身份切换，保持具有竞争性的False Negatives。仿真的跟踪准确性主要受到大量False Negatives的影响。鉴于对MOTA 得分的总体影响，检测应用更大的置信度阈值可能会增加所述算法的大幅度余量。然而，对跟踪输出的视觉检查表明，这些False Negatives主要是由静态场景的目标检测器响应产生的。同时，实验中没有观察到经常在False Negatives 之间变化的轨迹。

表2 4种算法的多目标跟踪评价指标对比Tab.2 Comparison of multi-target tracking evaluation indexes of four algorithms

4 结束语

本文提出了一种基于马尔可夫决策过程的多目标跟踪算法。视频序列中的每一个目标都建模成具有4个子状态空间(“活跃”，“已跟踪”，“丢失”，“不活跃”)的MDP。目标的出现-消失-出现过程对应MDP中的状态转移过程。作为策略学习的一部分，利用增强学习方法来学习用于数据关联的相似性度量函数。所提出的算法在MOT15基准数据上进行了测试验证，能够有效处理遮挡和快速运动的情况，在速度和准确性上实现了较好的提升。