Multi-object Tracking Using Hierarchical Data Association Based on Generalized Correlation Clustering Graphs
-
摘要: 检测跟踪是近期多目标跟踪研究的热点方向之一.目前大部分方法都是基于相邻帧之间的双向匹配，对检测点进行数据融合.本文提出的方法是，给定一个滑动时间窗口，在窗口内对某个目标每帧出现的检测点进行一次性数据融合.我们把多目标跟踪看作图的分割问题，利用广义关联聚类（Generalized correlation clustering problem，GCCP）图优化文中提出的数据融合.吸取分层数据关联的思想，把多目标跟踪分成两个阶段.首先，在时间窗口内遵循检测点，利用广义关联聚类，得到自适应长度的轨迹片段，轨迹片段长度不受窗口宽度的限制.然后，基于轨迹片段进一步数据关联，得到目标的长轨迹.在公共数据集上的实验测试表明，本文方法能够有效地实现多目标跟踪，对于遮挡处理、身份转换处理以及轨迹的生成具有很好的鲁棒性，多目标跟踪准确率（Multiple object tracking accuracy，MOTA）超过当前水平.Abstract: Tracking by detection based on data association of detections is a main research direction in the field of multi-object tracking. The majority of current methods, such as bipartite matching, solve the data association problem between adjacent frames. We propose an approach to solve data association for one object whose all detections are in a sliding temporal window at a time. The task of multi-object tracking can be considered as a graph partitioning problem that takes the form of a generalized correlation clustering problem (GCCP). The multi-object tracking problem can be divided into two phases using hierarchical data association. Firstly, adaptive length tracklets can be obtained from all detections in a sliding temporal window by using the GCCP. The length of tracklets is not restricted to the window width. Secondly, we treat tracklets as detections, using the similar method described in first phase to acquire trajectories. Experiments show that the proposed method can handle occlusion and ID-switch effectively, which makes significant improvement in multi-object tracking on the public datasets. Our multiple object tracking accuracy (MOTA) is higher than that of the-state-of-the-art.
-
多目标跟踪是计算机视觉领域的一个研究热点,是监控视频分析、 智能视频监控系统中一个基础而又关键的任务. 多目标跟踪目前已经取得了很多的成果,但是同样面临着很多严峻的问题. 尤其在复杂场景下,跟踪目标的相似外观特征容易造成身份转换,以及目标检测器的误差和频繁的遮挡(目标与目标之间,目标与背景物体之间)会引起跟踪的中断. 多目标跟踪的目的是在视频序列中克服这些困难,定位感兴趣的目标,确定它们唯一的身份并推断出它们的轨迹.
目前由于目标检测 [1-3]的性能提高,即使在很复杂的场景下同样可以得到很好的检测结果. 因此遵循检测点的数据关联多目标跟踪方法展现了很好的性能. 现在被提出的主流方法分为相邻帧的数据融合和多帧的数据融合两大类. 文献 {[4-8]} 的方法属于第一类,它们根据检测点的位置、大小、速度和外观特征建立关系模型,在局部和短时间内,对相邻帧的检测点进行数据融合. 但是当遮挡或者误检发生时,导致待匹配点丢失,该处理方法会遇到难度,出现跟踪上的漂移或者跟踪中断. 若出现具有相似外观特征的两个检测点,则容易发生误匹配现象,且不可挽回. 原因是相邻两帧之间匹配,没有保留之前的匹配信息. 另一类方法,多帧的数据融合 [9-13],利用目标在多帧的检测点同时建立关系模型,而不局限于两个相邻帧的检测点. 这样能够有效抑制误匹配和处理遮挡. 但是如果遮挡时间比多帧的数据融合需要的时间片段还长,前后检测点无法建立关系,跟踪同样会中断. 该方法跟踪前需要全部检测点信息,无法满足在线的需求,针对这个问题文献 [11] 运用滑动窗口实现在线跟踪. 其他方法,文献 [14] 建立一个条件随机场(Conditional random field algorithm,CRF)模型. 文献 [15] 提出一个全局能量函数,通过迭代使代价函数能量最小化来实现整个多目标跟踪.
为了应对多目标跟踪面临的难题,很多方法提出了应对措施. 文献 [4, 6] 为每条轨迹建立置信度. 置信度高的轨迹. 跟踪时在局部直接关联待检测点. 置信度低的轨迹,使用全局关联. 文献 [7] 提出双向匹配的方法,融合多种测量方式进行全局优化. 文献 [8] 提出基于部分模型的检测跟踪框架,并对每个目标训练一个SVM分类器,来提高行人检测的性能和处理全部遮挡和部分遮挡的能力. 文献 [4-5, 7] 采用匈牙利算法(Hungarian algorithm) [16]实现数据的匹配融合. 文献 [9, 17-18] 采用网络流的思想. 文献 [10-11] 把每个检测点看成图的一个节点,连接所有检测点得到一个完整的图,把多目标跟踪问题看作图的分解问题. 文献 [10] 提出GMCP (Generalized minimum clique graphs)算法,通过不断迭代寻找能量最小的子图,实现图的分解,解决数据融合问题. 文献 [11] 提出BIP (Binary integer program)算法,把图的分解问题看作是二进制整数规划过程. 文献 [5, 10-11, 13] 都采用分层关联的思想,把多目标跟踪分成两个阶段. 先是由检测点得出轨迹片段,然后对轨迹片段数据融合得到目标轨迹. 文献 [9-10] 在给定滑动时间窗口内,计算轨迹片段,片段长度受时间窗口的宽度限制,即轨迹片段的长度最长为时间窗口的宽度. 不同时间窗口内得到的轨迹片段之间没有任何联系,需要经过第二阶段进一步处理.
以上方法对于解决多目标跟踪问题,做出了很多贡献,但是目标遮挡,外观相似性仍是多目标跟踪需要解决的难题. 文献 [19-20] 提出了关联聚类的思想,在此基础上,本文提出一种基于广义关联聚类(Generalized correlation clustering problem,GCCP)的分层关联的方法. 其创新之处在于,首先,在分层关联的第一阶段,我们将不同时间窗口内的轨迹片段建立衔接关系,使得轨迹片段的长度能够自适应,不会受到窗口宽度的限制,同时将未被关联的轨迹片段放在第二阶段处理. 其次,我们把多目标跟踪问题看作广义关联聚类问题. 每个检测点看作是图的一个节点,连接所有节点,形成一个图,称作广义图. 对于广义图问题,通常被认为是广义网络设计问题 [21],都是一类求解广义标准子图的问题. 同一个目标的所有检测点构成一个标准子图,对应的节点属于同一类. 由广义图得到广义标准子图的过程看作是关联聚类 [19-20]的过程,得到的广义标准子图称作广义关联聚类图. 由此,本文把多目标跟踪的问题引申到广义关联聚类问题.
本文在第1节介绍GCCP的数学模型和关系权重wuv的计算. 第2节基于GCCP的分层关联多目标跟踪,先是介绍自适应轨迹片段的获取; 其次,是对缺失目标的处理;最后,介绍如何利用轨迹片段得到最终的目标轨迹. 第3节实验结果与分析. 第4节总结.
1. 广义关联聚类问题(GCCP)
本文使用GCCP来解决检测点和轨迹片段的数据融合问题,在本节中主要介绍GCCP的数学模型以及关系权重wuv的计算.
1.1 GCCP 数学模型
设V是行人检测 [3]输出结果的所有检测点组成的集合,称为节点集合. 对于单个目标 $u,v \in V$ ,用wuv来表示目标u和目标v之间的关系权重. 后面第1.2节会介绍这种关系权重的计算,这里先给出wuv的取值范围, ${w_{uv}} \in \left\{ { - \infty ,[- 1,1],+ \infty } \right\}$ . 正值表示目标u和目标v可以被关联. 负值表示两个目标相互排斥,不能被关联. 0表示两个目标无差别,能否被关联不确定. 同时在实际情况中,有些目标是否可以被关联是确定的,因此取值为无穷大. 为了更好地定义GCCP的模型,假设存在集合V的无向加权图 $G = \left( {V,E,W} \right)$ . 其中E表示边的集合,W表示边的权值的集合. 设视频序列一共有n帧,每帧内的节点集合记为 ${V_i}\left( {i = 1,2,3,\cdots,n} \right)$ ,则 ${V_1} \cup {V_2} \cup \cdots \cup {V_n} = V$ 且 ${V_i} \cap {V_j} = \emptyset \left( {i \ne j} \right)$ . 并且用vim表示在第i帧中第m个检测点,因此 ${V_i} = \{ v_i^1,v_i^2,v_i^3,\cdots\} $ . 图G中的边定义为 $E = \{ (v_i^m,v_j^n)|i \ne j\} $ ,表示在无向加权图G中,任意两个检测点,只要不属于同一帧内,就存在一条边使两者建立联系. 同时对应于每条边,都有一个边的权重,表示两个目标的关系权重,类似于边的定义,把权重定义为 $W = \{ (v_i^m,v_j^n)|i \ne j\} $ .
我们的任务是获取目标的运动轨迹,即同一个目标,在不同视频帧中,都有同一个身份标识. 因此一个可行的方法是,在每帧中选取一个节点构成图G的标准子图. 子图中的所有节点来自同一个目标. 我们称这个标准子图 为图G的一个可行解 ${G_s} = \left( {{V_s},{E_s},{W_s}} \right)$ . Vs是可行解Gs的节点集, ${V_s} = \{ v_1^a,v_2^b,v_3^c,\cdots\} $ ,表示第1帧的第a个检测点,第2帧的第b个检测点,第3帧的第c个检测点,以此类推构成集合Vs. 同时 ${E_s} = \{ E(p,q)|p \in {V_s},q \in {V_s}\} $ 和 ${W_s} = \{ W(p,q)|p \in {V_s},q \in {V_s}\} $ 分别是可行解Gs的边集合和权重集合. 如图 1 (a),每帧节点集合中不同的形状代表不同的目标,相同的形状是同一个目标出现在不同的视频帧里. 这些检测点通过虚线连接起来形成无向加权图G. 图 1 (b)中只有同一目标的检测点之间有连线,不同目标之间没有连线. 某个目标的所有检测点和这些检测点的连线就构成一个可行解Gs. 如图 1 (b)中有4个可行解,每个可行解对应一个目标. GCCP的目的就是寻找这些可行解Gs,Gs对应能量最大,即Ws集合内元素之和最大. 每个目标的所有检测点看作一个类别,对所有检测点进行关联聚类,得到无向加权图G的所有可行解Gs,从而确定每个检测点的唯一身份,完成目标的关联与跟踪.
可行解Gs求解过程可以重新阐述为如下最优化过程:
$\arg \mathop {\max }\limits_E \sum\limits_{{e_{uv}} \in E} {{w_{uv}}{e_{uv}}} $
(1) ${\rm{s}}.{\rm{t}}.\quad {e_{uv}} \in \left\{ {0,1} \right\},\quad \forall {e_{uv}} \in E$
(2) $\exists {e_{uv}} \in {E_s},\quad {e_{uv}} = 1$
(3) 式(1)的最优解E对应于图 1 (b)的实线边界. 对于式(2),当euv=1时,表示目标u和目标v之间存在边界,即属于同一个轨迹; 反之,表示目标u和目标v不属于同一轨迹. 式(3)表示在一个可行解Gs中,各个节点之间边界一定存在. 解决式(1)是一个NP-hard (Non-deterministic polynomial hard)问题,目前尚无有效的解决算法,但是提出了很多有效的近似算法. 文献[20]提出了Expand-and-explore,swap-and-explore和adaptive label iterative conditional modes (AL-ICM)三个方法优化关联聚类问题. 本文采用 (AL-ICM)方法来求解式(1). AL-ICM方法具有解决大规模数据关联的能力和速度. 给定一个标签向量 $L = {\left\{ {1,2,3,\cdots} \right\}^n}$ ,标签lv表示观测值v的类标签,最小化条件随机场(Conditional random field,CRF)的能量函数 $E\left( L \right)$ :
$E\left( L \right) = \sum\limits_{uv} {{w_{uv}} \cdot {1_{\left[ {{l_u} \ne {l_v}} \right]}}} $
(4) 其中,wuv表示观测值u,v之间的关系权重. ${1_{[p]}}$ 表示当p为真的时候为1; 否则为0. 式(4)和式(1)很相似,最小化式(4)的能量函数相当于最大化式(1). AL-ICM是一个贪婪搜索算法,随着变量的增加,耗时越来越长. 本文中根据检测点之间的距离,利用分层聚类树的方法,把整个视频区域内的检测点分成若干分区,保证在较短时间内,目标的运动轨迹属于同一分区. 每个分区内构建GCCP数学模型,利用AL-ICM求解. 把一个大规模的问题分成若干个子问题,提高了速度,整个算法能达到实时的要求. 下面一节将会介绍边界关系权重wuv的计算.
1.2 关系权重wuv的计算
设每个检测点为 $D = \left( {f,{{p}},a,{{v}}} \right)$ ,其中f表示检测点所在的当前帧数. p表示当前位置, $p = \left( {x,y} \right),\left( {x,y} \right)$ 为实际坐标值. a表示检测点的外观特征,本文采用是的HSV (Hue,saturation,value)颜色直方图特征来表示目标. 也可以采用其他的特征,例如,HOG (Histogram of oriented gradient) [1],LBP (Local binary pattern) [22]等.v表示当前检测点的速度,设在第f帧的p位置有一个检测点,在第f帧前后的m (很小的一个正整数)帧里存在 ${{{p}}_i}(|i| < m)$ 点. 计算 $\left( {{{p}},{{{p}}_i}} \right)$ 的速度 ${{{v}}_i} = ({{{{{p}}_i} - {{p}}}})/({{{f_i} - f}})$ ,若 ${{{v}}_i}$ 的值超过阈值,则舍弃,并取剩余速度的平均值作为v,如图 2.
给出两个检测点 ${D_1} = \left( {{f_1},{{{p}}_1},{a_1},{{{v}}_1}} \right)$ 和 ${D_2} = \left( {{f_2},{{{p}}_2},{a_2},{{{v}}_2}} \right)$ ,下面计算D1,D2关系权重w12:
${w_{12}} = \left\{ \matrix{ - \infty ,若{s_a}{s_{st}} = 0 \hfill \cr + \infty ,若{s_a}{s_{st}} = 1 \hfill \cr - 1 + {2 \over {1 + \exp ( - \lambda ({s_a}{s_{st}} - \mu ))}},其他 \hfill \cr} \right.$
(5) ${s_a} = \max \left[ {1 - \alpha d\left( {{a_1},{a_2}} \right),0} \right]$
(6) ${s_{st}} = \max \left[{1 - \beta \left( {e\left( {{D_1},{D_2}} \right) + e\left( {{D_2},{D_1}} \right)} \right),0} \right] $
(7) $e\left( {{D_1},{D_2}} \right) = {\left\| {{{{q}}_1} - {{{p}}_2}} \right\|_2} $
(8) ${{{q}}_1} = {{{p}}_1} + {{{v}}_1}\left( {{f_2} - {f_1}} \right) $
(9) 其中,sa,sst分别表示检测点D1,D2之间的外观相似度和时空相似度. $d\left( {{a_1},{a_2}} \right)$ 是外观空间的距离函数,本文采用的是HSV颜色直方图之间的欧氏距离. 式(8)是计算检测点D2的位置p2与检测点D1的估计位置q1之间的误差. q1可由式(9)估计得到. 本文中参数α、β的取值都为1,同时μ= 0.25,λ = 6.
通过上面的方法计算每个分区内的检测点之间的关系权重W,利用式(1)求解GCCP,获取分区内每个目标的可行解Gs,实现检测点之间的关联,得到轨迹片段. 接下来将介绍如何利用GCCP完成多目标跟踪.
2. 基于 GCCP
的分层关联多目标跟踪 本文采用分层关联多目标跟踪的思想,对每个阶段构建GCCP模型,使用AL-ICM算法获取可行解Gs,解决数据融合问题,实现多目标跟踪的任务. 多目标跟踪过程如图 3.
2.1 建立自适应轨迹片段
前面第1.1节对GCCP数学模型进行了阐述,下面将介绍如何使用GCCP估计出自适应轨迹片段(Adaptive-tracklet). 设一个视频序列有n帧,按照时间的顺序分成m个视频片段,每个片段有t帧,则第 $i\left( {i = 1,2,3,\cdots,m} \right)$ 个视频片段Fi包含的视频帧为(如图 4 (a)):
${F_i} = [( {i - 1} )t,{it} ),{\rm{\quad s}}{\rm{. t}}{\rm{. \quad}}i = 1,2,3,\cdots,m \tag{10} $
(10) 对于目标xk,在整个视频系列中存在一条轨迹Tk,Tk被分成 $r\left( {r = 1,2,3,\cdots,m} \right)$ 个轨迹片段,单个轨迹片段记为 $T_k^j \in {T_k}\left( {j = 1,2,3,\cdots,r} \right)$ . 如何从视频片段Fi获取目标的轨迹片段 $T_k^j$ ,就是分层关联多目标跟踪在第一阶段的研究问题. 目前基于分层关联数据融合思想提出了很多方法,如文献 [10-11] 等大多数采用此形式定义Fi. 在式(10)的基础上,我们做了进一步改进,现在重新改写式(10)如下:
${F_i} = [( i - 1 )t,it],{\rm{\quad s}}{\rm{. t}}{\rm{.\quad}}i = 1,2,3,\cdots,m \tag{11} $
(11) 式(11)相对于式(10)的不同地方是区间的右边界,由开区间变成闭区间. 这样做的目的是使得视频片段Fi和Fi+1在it帧重合,即视频片段Fi的最后一帧和Fi+1的第一帧是同一帧. 目标xk在视频片段Fi内的轨迹片段为Tki ,在视频片段Fi+1内的轨迹片段为Tki+1 . 根据式(10)定义的视频片段Fi和Fi+1没有任何直接的联系,则轨迹片段Tki,Tki+1也不会有直接联系. 如图 4 (a),每个轨迹片段之间是断开的,彼此没有关联. 本文的方法,轨迹片段Tki,Tki+1 存在直接联系. 若目标xk在视频片段Fi和Fi+1都能够得到完整的轨迹片段Tki,Tki+1,则在第it帧目标xk对应的检测点的位置点p是唯一的,因此轨迹片段Tki,Tki+1在p点能够实现无缝连接. 如图 4 (b),自适应轨迹片段,矩形框和椭圆框分别表示同一个检测点,这样轨迹片段首位相接,直接可以得到一个更长的轨迹片段. 以此类推得到长度自适应的轨迹片段. 采用式(10)的方法得到的轨迹片段Tki,Tki+1是两个不相关的轨迹片段,需要第二阶段轨迹片段的数据融合,来估计轨迹片段Tki,Tki+1是否可以连接起来,这样会带来一定匹配误差. 本文的方法能够对满足条件的轨迹片段Tki,Tki+1直接关联起来形成一个新的轨迹片段,有效减少匹配误差.
整个视频序列中目标xk都能得到满足条件的轨迹片段 $T_k^j \in {T_k}\left( {j = 1,2,3,\cdots,r} \right)$ ,则目标xk的整条轨迹Tk就很容易获得,不需要经过第二阶段再次处理. 然而由于目标之间的遮挡,目标外观的变化以及具有相似外观目标的影响,往往还不能得到完整的轨迹Tk. 后面章节将要介绍的轨迹片段的融合,并最终得到完整的轨迹. 实验表明,相对于其他方法,我们的方法得到的轨迹片段数明显减少,在轨迹片段融合时,减少了匹配误差,同时节省了时间,如表 1所示.
表 1 自适应轨迹片段与传统轨迹片段比较Table 1 The difference between traditional-tracklet and adaptive-trackletMethods MOTA(%) MOTP(%) IDS TC Time(s) Rcll(%) Prcsn(%) Traditional-tracklet 93.08 83.57 16 356 2.5 94.61 98.74 Adaptive-tracklet 95.11 83.04 4 77 2.34 96.31 98.88 2.2 缺失目标处理
由于误检、漏检、目标之间的遮挡以及目标具有相似外观特征的影响,导致目标在某一帧没有对应的检测点,在轨迹片段中会出现目标缺失现象. 通常认为在较短时间内(如第2.1节中假设的视频片段长度t帧),把目标的运动轨迹近似为一条直线. 运用随机抽样一致(Random sample consensus,RANSAC)估计这条直线,对缺失位置利用这条直线来估计. 设在t帧内,轨迹片段Tk所有检测点的集合是X. 由这些检测点连接起来的直线l,数学模型为 $\hat x(i) = ai + b,\hat x(i)$ 表示在第i帧的对应检测点 $x\left( i \right)$ 的估计,a,b是直线l的参数. RANSAC定义的局内点为
${X^{\rm inliers}} = \left\{ {x\left( i \right)\left| {\left| {ai + b - x\left( i \right)} \right| < \delta } \right.} \right\} $
(12) 阈值△用来判定检测点 $x\left( i \right)$ 是否属于局内点 ${X^{\rm inliers}}$ . 通过最大化局内点的个数来估计直线l的参数a,b:
$\hat a,\hat b = \arg\mathop {\max }\limits_{a,b} \left( {\# \left\{ {{X^{\rm inliers}}} \right\}} \right) $
(13) 其中, $\hat a,\hat b$ 是参数a,b的估计值. #表示集合 ${X^{\rm inliers}}$ 的基. 则用 $\hat x(i) = \hat ai + \hat b$ 来重新估计检测点.
RANSAC的一个优点是只有局内点对最后估计出的直线有影响. 通常目标的检测点波动很大,如图 2. RANSAC能够把这样的点排除在局内点之外,估计出的直线更接近实际运动轨迹. 利用 $\hat x(i) = \hat ai + \hat b$ 重新估计这些明显偏离直线的检测点,提高跟踪的准确率. 轨迹片段经过RANSAC优化后,把这些轨迹片段进一步数据融合得到目标的长轨迹.
2.3 目标轨迹的生成
这一节介绍分层关联多目标跟踪的第二个阶段. 每个轨迹片段看作无向加权图中的一个节点,所有的节点可以连接成一个新的无向加权图 $G = \left( {V,E,W} \right)$ . 把轨迹片段之间数据融合同样看作GCCP,并通过求解式(1),最终得到每个目标的长轨迹. 接下来将要介绍如何构建式(1)的关系权重w,即轨迹片段之间的关系权重.
第1.2节给出了目标检测点的数学定义,并在2.1节中介绍了轨迹片段. 现在给出轨迹片段的数学定义 $T = \left( {{f^s},{f^e},{{{p}}^s},{{{p}}^e},a,{{{v}}^s},{{{v}}^e}} \right)$ . 其中 ${f^s},{f^e},{p^s},{p^e},a,{v^s},{v^e}$ 分别表示轨迹片段的起始帧,结束帧、起始位置、 结束位置、外观特征、起始速度和结束速度. 起始速度vs,结束速度ve和目标检测点D中的v不同. 与第2.1节类似,假设视频片段长度为t帧,那么:
$\left\{ \matrix{ {v^s} = {v^e} = {{{p^e} - {p^s}} \over {{f^e} - {f^s}}},若{f^e} - {f^s} \le t \hfill \cr {v^s} = {{{q^e} - {p^s}} \over t},若{f^e} - {f^s} > t \hfill \cr {v^e} = {{{p^e} - {q^s}} \over t} \hfill \cr} \right.$
(14) 其中,qe表示第 $\left( {{f^s} + t} \right)$ 帧的检测点位置, ${{{q}}^s}$ 表示第 $\left( {{f^e} - t} \right)$ 帧的检测点位置,如图 5. 轨迹片段的长度远大于t,图中的vs,ve更能体现轨迹片段T的起始点ps和结束点pe的运动趋势,本文的方法估计出的速度更接近实际情况.
存在轨迹片段 ${T_1} = (f_1^s,f_1^e,p_1^s,p_1^e,{a_1},v_1^s,v_1^e)和{T_2} = (f_2^s,f_2^e,p_2^s,p_2^e,{a_2},v_2^s,v_2^e)$ ,采用类似于计算检测点之间的关系权重来计算轨迹片段之间的关系权重. 不同的是,计算外观相似度sa,轨迹片段的外观特征a是整个轨迹片段中所有检测点外观特征的中值. 计算时空相似度sst,类似式(7) ~ (9):
${s_{st}} = \max \left[{1 - \beta \left( {e\left( {{T_1},{T_2}} \right) + e\left( {{T_2},{T_1}} \right)} \right),0} \right] $
(15) $e\left( {{T_1},{T_2}} \right) = {\left\| {{{q}}_1^e - {{p}}_2^s} \right\|_2} $
(16) ${{q}}_1^e = {{p}}_1^e + {{v}}_1^e\left( {f_2^s - f_1^e} \right) $
(17) $e\left( {{T_2},{T_1}} \right) = {\left\| {{{q}}_2^s - {{p}}_1^e} \right\|_2} $
(18) ${{q}}_2^s = {{p}}_2^s + \left( { - {{v}}_2^s\left( {f_2^s - f_1^e} \right)} \right) $
(19) 式(16)和(18)分别表示轨迹片段的前向匹配误差和后向匹配误差. 根据式(5)计算得到轨迹片段之间的关系权重W,利用式(1)来求解GCCP,可行解Gs中的节点对应着同一个目标的不同轨迹片段,最终实现目标的轨迹,完成多目标跟踪.
3. 实验结果与分析
本文提出的多目标跟踪算法采用Matlab编程语言,并在处理器为Interl Core i7 4.00 GHz,内存8 GB,操作系统Windows7的PC机上完成了实验测试.
在PETS2009[23],Town Center[24]及Parking Lot[10]这三个标准单摄像机多目标跟踪数据集上测试了本文的算法,并且使用公共的CLEAR MOT[25]标准进行了算法评估. 多目标跟踪准确率(Multiple object tracking accuracy,MOTA)是一个使用非常广泛的多目标跟踪算法性能的评价指标. MOTA包含缺失数(False positives) ${f_p}\left( t \right)$ ,误判数(False negatives) ${f_n}(t)$ 以及身份转换数(Identity switches) $id\left( t \right)$ 三个部分,并通过下面公式计算:
${\rm MOTA} = 1 - \frac{{\sum\limits_t {\left( {{f_p}\left( t \right) + {f_n}\left( t \right) + id\left( t \right)} \right)} }}{{\sum \limits_t{g\left( t \right)} }} $
(20) 其中 $g\left( t \right)$ ,表示在第t帧图内实际目标的个数,是人为标定的结果. 多目标跟踪精确率(Multiple object tracking precision,MOTP) 是测量跟踪结果中目标的估计位置和实际位置之间的精确率,这个指标越高,说明跟踪的轨迹越接近目标实际的运动轨迹. 其他的指标还有检测的召回率(Recall,简写为Recll)和精确率(Precision,简写为Prcsn). 在表 2中,我们列出了部分当前方法的跟踪结果和本文方法的测试结果,为了公平的对比,实验中采用相同的目标检测方法和 $g\left( t \right)$ . 实验表明本文的方法对解决多目标跟踪问题有一定的优势.
表 2 跟踪结果Table 2 The results of trackingSequence Methods MOTA(%) MOTP(%) Rcll(%) Prcsn(%) Longyin[13] 92.7 72.9 94.4 98.4 Andriyenko[15] 88.3 79.6 90 98.7 PETS-S2L1 Zamir[10] 90.3 69.02 96.45 93.64 Afshin[18] 90.4 63.12 -- -- Izadinia[12] 90.7 76 95.2 96.8 Ours 95.11 83.04 96.31 98.88 Longyin[13] 62.1 52.7 71.2 90.3 PETS-S2L2 Anton[26] 56.9 59.4 65.5 89.8 Ours 52.98 68.63 57.15 93.58 Longyin[13] 88.4 81.9 90.8 98.3 Andriyenko[15] 73.1 76.5 86.8 89.4 Parking lot Zamir[10] 90.43 74.1 85.3 98.2 Guang[8] 79.3 74.1 -- -- Izadinia[12] 88.9 77.5 96.5 93.6 Ours 91.37 74.8 96.61 95.24 Zamir[10] 75.59 71.93 -- -- Guang[8] 72.9 71.3 -- -- Town center McLaughlin[6] 74.15 72.41 83.27 90.4 Izadinia[12] 75.7 71.6 81.8 93.6 Ours 79.67 70.6 84.56 93.98 在PETS2009数据集上采用的是S2L1视频序列,该序列一共有798帧,分辨率是768×576,视频帧率比较低,第2.2节中的参数△取5. 此视频序列目标相对比较稀疏,但是大部分行人做非线性运动. 运动轨迹比较复杂,其运动方向难以预测. 视频中有一个路灯柱,目标在经过时,出现遮挡,行人检测器无法检测到行人,大大增加了跟踪的难度. 从表 2中,可以看出,本文的方法在MOTA,MOTP两个指标上处于明显优势,部分跟踪结果如图 6 (a). 在实际实验中取滑动时间窗口宽度是13帧,总用时2.34 s (340 fps).
PETS2009-S2L2视频序列一共有436帧,分辨率也是768×576. 在实验中取滑动时间窗口宽度是10帧,总用时4.47 s (97 fps). 相对于S2L1序列,此序列行人密度很大,遮挡很严重,不管是对目标检测还是多目标跟踪来说,都是巨大的挑战. 为了公平比较,我们在这个序列上的实验,采用的是文献 [27] 提供的目标检测结果. 实验表明,我们的方法在MOTA上不如其他方法,原因是本文的跟踪方法是基于目标检测,然而文献 [27] 提供的目标检测结果中存在很多漏检,很多目标不能持续被检测,尤其在行人密度很大,遮挡很严重的时候,目标检测器基本上不能正常工作. 但是在其他评价指标上,本文的方法还是有明显优势.
Parking lot 视频序列有998帧,分辨率是1 920×1 080,该视频帧率比较高,第2.2节中的参数△取3. 在处理这个视频时滑动时间窗口宽度是14帧,总用时4.51 s (222 fps). Parking lot视频序列中目标的移动方向很明确,大部分目标都是线性运动. 但是目标彼此间距离很小,目标重叠现象很严重,同时很多行人的衣服颜色很相似,遮挡现象很严重,包括部分遮挡和完全遮挡,缺失目标很多,跟踪难度很大. 部分跟踪结果如图 6(b) .
Town center视频序列很长,一共有4 500帧,并且分辨率是1 920×1 080,参数△同样取3. 整个视频内目标很多,彼此之间距离很近,整个场景很拥挤,目标重叠很严重,导致遮挡很频繁且时间长. 对其进行多目标跟踪难度很大,从表 2看,当前大部分算法对Town center视频序列的跟踪结果,相对来说都不是很高. 本文的方法在MOTA上,相对于其他方法,有明显的提高. 部分跟踪结果如图 6 (c). 在实验中取20帧为滑动时间窗口宽度,处理完整个视频用时30 s (150 fps).
对比实验表明,本文方法在跟踪准确率MOTA方面相对于其他方法处于明显优势,但是跟踪精确率MOTP在某些数据集上不如别的方法. 原因是我们采用RANSAC方法处理缺失目标时,会对所有检测点的位置重新估计,从而引起检测点位置相对于实际检测的位置有一定的偏离,最终导致实验结果中MOTP下降. 然而我们采用RANSAC方法处理缺失目标,是为了提高跟踪的准确度,减少目标的身份转换,使目标的运动轨迹更连续更平滑. 实际中,持续的多目标运动轨迹更有意义.
本文第2.1节中,提出自适应轨迹片段(Adaptive-tracklet),轨迹片段的长度不受滑动时间窗口宽度的限制. 在PETS2009-S2L1数据集上进行了测试. 通过表 1显示,自适应轨迹片段对于提高多目标跟踪器的性能有明显的提高. 其中身份转换数(Identity switches,IDS)从16个减少到4个,表明自适应轨迹片段对于提高跟踪器的持续跟踪,确定目标唯一身份的能力,有明显的帮助作用. 通过采用自适应轨迹片段得到的轨迹片段的数量(Tracklets count,TC)明显减少,节省了第二阶段轨迹片段数据融合所用的时间(Time).
4. 总结
本文把多目标跟踪问题看作是广义关联聚类问题(GCCP),并采用分层数据关联的思想完成多目标跟踪的任务. 通过对比实验,本文的算法领先于当今主流算法,并且能够做到实时性. 但是本文算法同样也有很多可以改进的地方,比如关系权重可以进一步改进,使得同一目标间相似度更高,不同目标间相似度更低,建立起来的轨迹片段更可靠. 以后的工作方向是进一步提高多目标跟踪的性能,同时推广到多摄像机多目标的跟踪.
-
表 1 自适应轨迹片段与传统轨迹片段比较
Table 1 The difference between traditional-tracklet and adaptive-tracklet
Methods MOTA(%) MOTP(%) IDS TC Time(s) Rcll(%) Prcsn(%) Traditional-tracklet 93.08 83.57 16 356 2.5 94.61 98.74 Adaptive-tracklet 95.11 83.04 4 77 2.34 96.31 98.88 
下载: 导出CSV
表 2 跟踪结果
Table 2 The results of tracking
Sequence Methods MOTA(%) MOTP(%) Rcll(%) Prcsn(%) Longyin[13] 92.7 72.9 94.4 98.4 Andriyenko[15] 88.3 79.6 90 98.7 PETS-S2L1 Zamir[10] 90.3 69.02 96.45 93.64 Afshin[18] 90.4 63.12 -- -- Izadinia[12] 90.7 76 95.2 96.8 Ours 95.11 83.04 96.31 98.88 Longyin[13] 62.1 52.7 71.2 90.3 PETS-S2L2 Anton[26] 56.9 59.4 65.5 89.8 Ours 52.98 68.63 57.15 93.58 Longyin[13] 88.4 81.9 90.8 98.3 Andriyenko[15] 73.1 76.5 86.8 89.4 Parking lot Zamir[10] 90.43 74.1 85.3 98.2 Guang[8] 79.3 74.1 -- -- Izadinia[12] 88.9 77.5 96.5 93.6 Ours 91.37 74.8 96.61 95.24 Zamir[10] 75.59 71.93 -- -- Guang[8] 72.9 71.3 -- -- Town center McLaughlin[6] 74.15 72.41 83.27 90.4 Izadinia[12] 75.7 71.6 81.8 93.6 Ours 79.67 70.6 84.56 93.98
下载: 导出CSV
-
[1] Dalal N, Triggs B. Histograms of oriented gradients for human detection. In:Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR). San Diego, CA, USA:IEEE, 2005. 886-893 http://www.oalib.com/references/16879692 [2] Wu B, Nevatia R. Detection and tracking of multiple, partially occluded humans by Bayesian combination of edgelet based part detectors. International Journal of Computer Vision, 2007, 75(2):247-266 doi: 10.1007/s11263-006-0027-7 [3] Felzenszwalb P F, Girshick R B, McAllester D, Ramanan D. Object detection with discriminatively trained part-based models. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(9):1627-1645 doi: 10.1109/TPAMI.2009.167 [4] Bae S H, Yoon K J. Robust online multi-object tracking based on tracklet confidence and online discriminative appearance learning. In:Proceedings of the 2014 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Columbus, OH:IEEE, 2014. 1218-1225 http://cn.bing.com/academic/profile?id=b51a27abfe6ed8c117c6592b09704056&encoded=0&v=paper_preview&mkt=zh-cn [5] Huang C, Li Y, Nevatia R. Multiple target tracking by learning-based hierarchical association of detection responses. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(4):898-910 doi: 10.1109/TPAMI.2012.159 [6] McLaughlin N, del Rincon J M, Miller P. Online multiperson tracking with occlusion reasoning and unsupervised track motion model. In:Proceedings of the 10th IEEE International Conference on Advanced Video and Signal Based Surveillance (AVSS). Krakow:IEEE, 2013. 37-42 https://www.computer.org/csdl/proceedings/avss/2013/9999/00/index.html [7] Henriques J F, Caseiro R, Batista J. Globally optimal solution to multi-object tracking with merged measurements. In:Proceedings of the 2011 IEEE International Conference on Computer Vision (ICCV). Barcelona:IEEE, 2011. 2470-2477 http://cn.bing.com/academic/profile?id=3f2887f7ffb4e1720cf6c1b8cf6763b6&encoded=0&v=paper_preview&mkt=zh-cn [8] Shu G, Dehghan A, Oreifej O, Hand E, Shah M. Part-based multiple-person tracking with partial occlusion handling. In:Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Providence, RI:IEEE, 2012. 1815-1821 [9] Zhang L, Li Y, Nevatia R. Global data association for multi-object tracking using network flows. In:Proceedings of the 2008 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Anchorage, AK:IEEE, 2008. 1-8 [10] Zamir A R, Dehghan A, Shah M. Gmcp-tracker:global multi-object tracking using generalized minimum clique graphs. In:Proceedings of the 12th European Conference on Computer Vision (ECCV) 2012. Florence, Italy:Springer-Verlag, 2012. 343-356 [11] Ristani E, Tomasi C. Tracking multiple people online and in real time. In:Proceedings of the 12th Asian Conference on Computer Vision (ACCV) 2014. Singapore:Springer International Publishing, 2015. 444-459 http://cn.bing.com/academic/profile?id=40f7f1fb493f5c240dac436babfbf566&encoded=0&v=paper_preview&mkt=zh-cn [12] Izadinia H, Saleemi I, Li W H, Shah M. (MP)2m t:multiple people multiple parts tracker. In:Proceedings of the 12th European Conference on Computer Vision (ECCV) 2012. Florence, Italy:Springer-Verlag, 2012. 100-114 [13] Wen L, Li W, Yan J, Lei Z, Yi D, Li S Z. Multiple target tracking based on undirected hierarchical relation hypergraph. In:Proceedings of the 2014 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Columbus, OH:IEEE, 2014. 1282-1289 [14] Yang B, Nevatia R. An online learned CRF model for multi-target tracking. In:Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Providence, RI:IEEE, 2012. 2034-2041 [15] Andriyenko A, Schindler K, Roth S. Discrete-continuous optimization for multi-target tracking. In:Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Providence, RI:IEEE, 2012. 1926-1933 [16] Kuhn H W. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 1955, 2(1-2):83-97 doi: 10.1002/(ISSN)1931-9193 [17] Chari V, Lacoste-Julien S, Laptev I, Sivic J. On pairwise costs for network flow multi-object tracking. In:Proceedings of the 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Boston, MA:IEEE, 2015. 5537-5545 [18] Dehghan A, Tian Y, Torr P H S, Shah M. Target identity-aware network flow for online multiple target tracking. In:Proceedings of the 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Boston, MA:IEEE, 2015. 1146-1154 [19] Bansal N, Blum A, Chawla S. Correlation clustering. Machine Learning, 2004, 56(1-3):89-113 doi: 10.1023/B:MACH.0000033116.57574.95 [20] Bagon S, Galun M. Large scale correlation clustering optimization. arXiv:1112.2903, 2011. [21] Feremans C, Labbé M, Laporte G. Generalized network design problems. European Journal of Operational Research, 2003, 148(1):1-13 doi: 10.1016/S0377-2217(02)00404-6 [22] Ojala T, Pietikainen M, Harwood D. Performance evaluation of texture measures with classification based on Kullback discrimination of distributions. In:Proceedings of the 12th IAPR International Conference on Pattern Recognition, 1994. Vol.1-Conference A:Computer Vision & Image Processing. Jerusalem:IEEE, 1994. 582-585 [23] Ferryman J, Shahrokni A. PETS2009:dataset and challenge. In:Proceedings of the 12th IEEE International Workshop on Performance Evaluation of Tracking and Surveillance. Snowbird, UT:IEEE, 2009. 1-6 [24] Benfold B, Reid I. Stable multi-target tracking in real-time surveillance video. In:Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Providence, RI:IEEE, 2011. 3457-3464 [25] Bernardin K, Stiefelhagen R. Evaluating multiple object tracking performance:the CLEAR MOT metrics. EURASIP Journal on Image and Video Processing, 2008, 2008:Article ID 246309 [26] Milan A, Roth S, Schindler K. Continuous energy minimization for multitarget tracking. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014, 36(1):58-72 [27] Milan A, The Data. The detections and ground truth for MOT[Online], available:http://www.milanton.de/data/, April 12, 2016. -
下载:
计量
- 文章访问数: 2150
- HTML全文浏览量: 276
- PDF下载量: 1066
- 被引次数: 0
