光电工程  2018, Vol. 45 Issue (8): 180030      DOI: 10.12086/oee.2018.180030     
基于动态捕获区域的DC-TLD目标跟踪算法
何俊衡 , 刘曙 , 狄红卫     
暨南大学理工学院光电工程系,广东 广州 510632
摘要:为提升TLD目标跟踪算法的处理速度,以达到在更高分辨率视频中跟踪目标的实时性要求,在TLD算法框架的基础上,提出了一种基于动态捕获区域的TLD目标跟踪算法(DC-TLD)。算法采用前一帧目标位置作为当前帧目标位置的预测值,减小了目标位置的预测误差。研究了检测区域负样本出现需满足的条件,分析了检测区域大小对算法鲁棒性的影响。针对样本的访问方式,提出基于索引的访问方法,极大地减少了访问时间。实验结果表明,该方法不仅有效降低了TLD算法的样本检测时间,而且提高了算法的鲁棒性。
关键词目标跟踪    TLD    动态捕获区域    负样本    索引访问    
TLD target tracking algorithm based on dynamic capture
He Junheng, Liu Shu, Di Hongwei     
Department of Optoelectronic Engineering, College of Science & Engineering, Jinan University, Guangzhou, Guangdong 510632, China
Abstract: In order to improve the ability of processing video image with high frame rate and meet the real-time requirement in higher resolution video tracking goal, DC-TLD target tracking algorithm, which is based on TLD algorithm and the theory of capturing sample dynamically, is proposed. Firstly, DC-TLD takes the target location of the previous frame as the predicted value of the current frame. Secondly, it calculates the threshold r of negative samples for ensuring that the number of negative samples is sufficient. Thirdly, it accesses the samples by index. The results of experiments show that DC-TLD is more robust and more efficient.
Keywords: target tracking    tracking-learning-detection    dynamic capture    negative sample    index access    

1 引言

基于计算机视觉的目标跟踪技术被广泛应用于民用领域和军事领域[1],如交通监控、安防监控、无人机跟踪和人机交互等。然而,目标跟踪在实际的应用中依然面临诸多的挑战,如目标外观变化、高速移动、遮挡消失和算法实时性等,使得大多数目标跟踪算法不能够有效地应用到实际场景中。

近年来目标跟踪算法发展迅速。目前主流的目标跟踪方法可分为三类。第一类是基于相关滤波的目标跟踪算法,如DCF(tracking with discriminative correlation filter)、KCF(tracking with kernelized correlation filters)[2]等,这类算法实时性强,但在目标被遮挡、目标形变等复杂情况下,容易丢失跟踪目标。第二类是基于深度学习的目标跟踪方法,如MDNet(multi-domain convolutional neural networks)[3]、TCNN(CNNs in a tree structure)[4]等,这类算法鲁棒性好,跟踪精度高,但由于算法和网络架构通常比较复杂,导致算法速度慢,实时性较差,且现阶段难以利用基于深度学习的目标跟踪算法进行长时间的目标跟踪。第三类是基于生成方法或判别方法的目标跟踪算法,如TLD(tracking learning detection)[5]、Struck (structured output tracking with kernels)[6]等,这类算法综合性能较强,但算法复杂度普遍较高,难以保证跟踪的实时性。考虑到TLD算法具有较好的鲁棒性,适合应用到实际跟踪过程中,本文对TLD算法进行研究并提出改进和优化。

TLD目标跟踪算法[5]是英国萨里大学Kalal提出的一种单目标长时间跟踪算法。该算法与传统跟踪算法的显著区别在于把跟踪算法和检测算法相结合来解决被跟踪目标在被跟踪过程中发生的形变、部分遮挡和快速移动等问题。同时,通过在线学习模块不断更新跟踪模块和检测模块的目标模型及相关参数,从而使得跟踪效果更加稳定、鲁棒和可靠。但TLD目标跟踪算法复杂度高,难以达到目标跟踪的实时效果。本文通过分析TLD算法特点,提出基于动态捕获区域的DC-TLD(TLD target tracking algorithm based on dynamic capture)目标跟踪算法。首先通过改变目标位置预测方法,利用前一帧的位置预测目标在当前帧的位置,减少目标样本的检测时间;然后改进样本选取方法,在尽量小的样本选取范围内获取足够的正负样本;最后改善样本访问方法,对样本进行编号,采取索引访问的方式,提高样本的访问速度。上述措施降低了TLD目标跟踪算法的复杂度,提高了算法的实时性和鲁棒性。

2 TLD目标跟踪算法原理

TLD目标跟踪算法由跟踪器、检测器、学习模型和整合器四个模块组成。算法框架如图 1所示。在算法初始化时,把视频帧数据流输入机器学习模块中,由该模块构造目标模型作为训练样本,并以此模型更新跟踪器和检测器,同时构造正负样本来更新训练集。在整个视频图像序列中,目标跟踪器和目标检测器是同时进行工作的,并把各自的结果和通过整合器返回的结果输入到机器学习模块中,学习模块通过以上数据更新目标模型,并依据目标模型更新跟踪器和检测器。最后结果通过整合器输出。

图 1 TLD算法框架[5] Fig. 1 TLD algorithm framework[5]
2.1 跟踪器

TLD的跟踪器由光流法改进而来的中值光流法[7-8]进行目标跟踪。在目标跟踪过程中,目标图像框内均匀撒点,并通过中值过滤筛选出可靠的目标像素点,然后采用前向后向误差法,即通过两次光流法有效地得出成功跟踪的像素点,从而生成成功跟踪目标的矩形框。

2.2 检测器

检测器基于滑动窗口[9]进行检测。模块采用级联分类器架构。级联分类器由方差分类器、集成分类器和最近邻分类器组成。当通过最近邻分类器的样本和目标模型的相对相似度大于一定值时,则判断样本为成功检测目标。成功检测目标将和成功跟踪目标在整合器中进行比较整合,确定当前帧的最优输出结果。

2.3 学习模型

学习模块的核心思想为P-N(posetive-negative)学习[10]。此模块通过生成正负样本来约束目标检测模块和目标跟踪模块。正样本是指包含跟踪目标的前景样本,负样本是指不包含跟踪目标的背景样本。P约束寻找视频序列中时域上的结构性特征,并假设目标的运动是按照一定的轨迹进行的。N约束寻找视频序列中空域的结构性特征,并假设目标在一个视频中只能出现在一个位置上。两种约束皆会生成正负样本,学习模块利用新生成的正负样本更新目标模型。

2.4 整合器

整合器接收目标跟踪模块和目标检测模块的结果,通过比较和目标模型的相似度,得出哪个模块的结果更可靠,并以该模块的结果为最终输出结果,同时更新目标模型。

3 基于动态捕获区域的目标跟踪算法(DC-TLD)

在逐帧视频中,跟踪目标在相邻两帧的位移一般比较小。因此,本文提出的DC-TLD目标跟踪算法主要针对检测器中跟踪目标在小位移下的情况。DC-TLD目标跟踪算法先通过利用上一帧成功跟踪目标的位置作为当前帧的目标预测位置中心,并通过目标尺寸计算获取搜索样本区间的边长,结合所得的中心与边长构造正方形搜索区间来获取正负样本,且在获取样本的过程中对样本编号,最后选择符合条件编号的样本输入检测器,算法流程如图 2所示。当跟踪目标位移较大导致目标丢失时,DC-TLD目标跟踪算法沿用TLD全屏检测的方法重新获取目标位置。

图 2 DC-TLD算法流程 Fig. 2 DC-TLD algorithm framework
3.1 目标运动状态预测

在TLD目标跟踪算法里,每帧的检测样本通过滑动窗口扫描整帧图像得到。这种方式会生成大量多余的样本,使得算法效率偏低。为了提高算法运行速率,一些研究者采用Kalman滤波的方法来预测目标在下一帧的位置[11-12]。本文提出直接利用上一帧成功跟踪到的目标位置作为当前帧的目标预测位置,在当前帧以该目标位置为中心,将一定范围内的图片样本作为当前帧需要检测的样本。

为了比较Kalman滤波方法和利用前一帧目标预测当前帧目标位置的效果,本文利用Visual Tracker Benchmark[13]中的视频集进行测试。Visual Tracker Benchmark是OTB2013的扩展,也被称为OTB2015,发表于2015TPAMI,包含100个视频序列,都经过人工标注,包含十一个跟踪难点:光照变化、尺度变化、遮挡、形变、运动模糊、快速运动、平面内旋转、平面外旋转、完全消失、背景杂波(背景相似目标干扰)和低分辨率,是目前使用最广泛最权威的数据库。下文所有测试序列均从OTB2015中获取。

图 3是BlurFace测试视频被跟踪目标位置的预测分析。其中纵坐标pixels_x和pixels_y分别表示跟踪目标在视频图像中x轴方向和y轴方向上的坐标,曲线true_t和true_t-1分别表示目标在当前帧与前一帧的真实位置,曲线Kalman表示用Kalman滤波方法预测得到的在当前帧的目标位置,曲线error_Kal表示Kalman预测的当前帧目标位置与当前帧目标真实位置的误差绝对值,error_true表示当前帧相对前一帧目标真实位置的偏移绝对值。可以看出,Kalman算法预判的位置和当前帧目标物体的真实位置有较大偏差。当直接使用前一帧成功跟踪目标所在的位置作为目标当前帧位置的预测值时,其误差(图中曲线error_true所示)远小于使用Kalman算法预判位置和真实位置的偏差(图中曲线error_Kal所示)。在图 4中的Jumping测试视频中,被跟踪目标主要在y轴上往返跳跃,所以在x轴上的位移变化相对平缓。综上所述,以前一帧成功跟踪目标所在位置为中心,在当前帧一定范围内获取检测图像样本的方法是可行且有效的。

图 3 BlurFace目标位置预测与误差 Fig. 3 BlurFace target location prediction and error

图 4 Jumping目标位置预测与误差 Fig. 4 Jumping target location prediction and error
3.2 基于临界参考点的范围选取方法

确定了下一帧目标检测中心后,再在目标检测中心附近的一定范围内获取样本。当跟踪目标在视频中的相对位置变化比较平稳时,获取样本的范围不是越小越好,而是存在一较佳临界值。当缩小获取样本范围时,算法运行速度会明显提升,但会导致鲁棒性变差。原因在于TLD目标跟踪算法是在线学习的更新算法,目标检测模块中的分类器需要正负样本来进行训练,才可以使得检测模块适应跟踪环境的变化。当目标范围选取过小时,即使仍可保证有足够多的样本,但TLD目标跟踪算法只会把和目标模型重叠率小于0.2的样本标为负样本,来进行相应的学习和更新。因此在较小范围内获取样本,会使得负样本数量不足,使得学习效果变差。下面讨论如何确定样本范围。

设两个面积均为s的样本e和e',重叠部分面积为s0,当重叠率为0.2时,有:

$ \frac{{{s_0}}}{{2s - {s_0}}} = 0.2。$ (1)

解得${s_0} = \frac{1}{3}s$

设样本e的边长分别为ab,如图 5实线矩形所示。现在考虑样本e'在其左下方的重叠情况,并将样本e左下方的顶点作为坐标轴原点建立坐标系。当样本e'和样本e的重叠率刚好为0.2时,样本e'的右上角坐标点必然满足方程:

图 5 临界点分析图 Fig. 5 Critical point analysis diagram
$ xy = \frac{1}{3}ab。$ (2)

以样本e的右上角顶点p作为观察点,来获取以样本e为中心的样本。考察选取样本从左下方与样本e重叠的情况,令这些样本的右上顶点落在以p为中心点的正方形区域,边长设为2r,如图 5中2r×2r区域。当正方形区域中有部分像素点在双曲线xy=ab/3的左下方时,则判断为重叠率小于0.2的负样本。当正方形区域和双曲线只有一个交点时,交点必然在过p点且斜率为1的直线上,即:

$ y=x−a+b。$ (3)

设交点Q的横坐标是d,则有:

$ r =a -d。$ (4)

x=d=ar代入式(2)、式(3),可得:

$ r = \frac{{a + b}}{2} - \frac{1}{2}\sqrt {{a^2} + {b^2} - \frac{2}{3}ab} 。$ (5)

因此负样本出现的阈值r可根据每一帧中跟踪到的目标区域的长宽(即ab)计算得出。

r值为基准,改变样本检测区域的范围,设改变后的正方形边长为2R。为了便于观察R值的大小对算法鲁棒性的影响,在Visual Tracker Benchmark中选取视频Fish、BlurFace、Jumping进行测试,结果如图 6所示。其中,bad_box是负样本的数量,success为算法成功跟踪目标的帧数占测试视频总帧数的百分比,error是算法跟踪目标失败的帧数占测试视频总帧数的百分比。

图 6 R/r和跟踪成功率、失败率及负样本数的关系 Fig. 6 R/r and tracking success rate, failure rate, negative sample size relationship

图 6可知,从R=0.8r开始,负样本数开始缓慢增加。当R > 0.8r时,随着R/r的增大,负样本数快速增加,成功跟踪目标的帧数和跟踪目标失败的帧数呈现出上下波动的状态。当R/r=2.9时,三个视频测试集同时出现了较高的成功率。

定义评估算法性能的品质因数Q

$ Q = \frac{{{E_{\rm{s}}}}}{{({E_{\rm{f}}}{\rm{ + 1)(}}\sqrt {{D_{\rm{s}}}} + 1)(\sqrt {{D_{\rm{f}}}} + 1)}}, $ (6)

式中:Es$ \sqrt {{D_{\rm{s}}}} $是跟踪目标成功样本的期望和标准差,Ef$ \sqrt {{D_{\rm{f}}}} $是跟踪目标失败样本的期望和标准差,为了避免出现分母等于零的情况,把分母各项因式加1,把三个视频测试集结果代入式(6)中,计算出品质因数QR/r的关系,如图 7所示。

图 7 R/r和品质因数Q的关系 Fig. 7 R/r and Q relations

图 7可得,R/r数值的大小和品质因数Q的关系曲线不是近似单调递增曲线,当R/r=2.9时,品质因数Q出现最大值。

3.3 基于索引访问的样本访问方法

选定检测范围后,可在该范围内访问和获取检测样本。TLD算法每帧涉及到数万个样本,对每一个待检测样本都需要通过计算重叠率来判断样本是否为在设定的样本选取范围内,这无疑大大增加了算法的运行时间。本文根据索引访问分析的方法来改进算法,计算效率得到较大的提高。

在TLD算法初始化阶段,会创建样本集合。本文利用算法的该特点,若每个样本都在集合中,可通过对样本进行编号,利用样本编号作为下标进行访问。样本选取时,滑动窗口每次移动的步长是样本大小的0.1倍。为了对样本进行编号,本文在算法中添加一个结构体,用以记录样本信息,如样本每一尺度的长宽、每一尺度的起始编号、滑动步长像素大小等。然后把结构体内的信息结合前一帧目标中心点的位置信息,通过计算可以直接得出相应的样本编号。DC-TLD算法则通过编号作为下标去访问集合中的样本。

为了避免每个样本都要利用计算重叠率的方式来判断样本是否为在设定的选取范围内,且考虑到当待检测样本和当前帧目标中心样本相距甚远时,它们的重叠率也会很低。因此,在算法的循环中,结合样本编号,只需要选取和当前帧目标中心样本相近的几个尺度的待检测样本即可。

运用基于索引访问的方法,选取连续的7个尺度作为检测尺度。利用Crowds、Football、Human6、Walking视频测试集对两种方法进行测试,表 1是测试结果。

表 1 重叠率方法和索引访问方法运行时间对比 Table 1 Overlap ratio method and index access method running time comparison
测试集 重叠率选取样本数No 索引访问选取样本数Ni 重叠率耗时To/ms 索引访问耗时Ti/ms 加速比γ
Crowds 2523 5278 2.79 0.0282 207
Football 3069 4054 2.87 0.0221 172
Human6 2861 7608 3.15 0.0597 140
Walking 3849 14000 3.55 0.0741 174

其中加速比γ是重叠率方法和索引访问方法选取单位样本的时间对比,即:

$ \gamma = {{\frac{{{N_{\rm{i}}}}}{{{T_{\rm{i}}}}}} / {\frac{{{N_{\rm{o}}}}}{{{T_{\rm{o}}}}}}}, $ (7)

式中:Ni是索引访问选取样本数,Ti是索引访问耗时,No是重叠率选取样本数,To是重叠率耗时。

表 1可得,基于索引访问方法可以有效提高算法效率。

4 实验结果和数据分析

本文根据以上分析提出基于动态捕获检测区域的TLD目标跟踪算法(DC-TLD)。将前一帧跟踪到的目标位置作为当前帧的检测范围的中心位置,以R=2.9r作为获取样本范围,使用基于索引访问的样本访问方法进行目标跟踪。

仿真实验的软件环境:VisualStudio 2012,OpenCV 2.4.9,Windows 10系统;硬件平台:Inter(R) Core(TM) i5-3470 CPU @ 3.20 GHz,内存:8.00 GB。实验共用了6个测试集对TLD及DC-TLD算法进行测试。

4.1 跟踪时间

以Crowds和BlurFace为测试视频,把TLD和DC-TLD进行运行对比。得到数据后,为便于观察采用了Savitzky-Golay滤波的方式对数据图像进行处理。最终结果如图 8图 9所示。

图 8 Crowds测试集算法每帧运行时间 Fig. 8 Crowds test set algorithm running time per frame

图 9 BlurFace测试集算法每帧运行时间 Fig. 9 BlurFace test set algorithm running time per frame

观察图 8图 9,由于Crowds视频测试集中第50帧前后帧和BlurFace视频测试集中第151帧前后帧中,目标特征发生了较大变化,所以两种算法曲线该处都出现了一个较大波动。但波动前后,两种算法在每帧的运行速度稳定在一个范围内,所以两种算法跟踪目标较为平稳。

分别在Crowds、Football、Jumping、Walking、Fish、BlurFace视频测试集运行TLD算法和DC-TLD算法,测试跟踪目标所需时间,表 2是测试结果。

表 2 视频测试实验跟踪时间结果 Table 2 Results of video test tracking time
测试集 视频帧数 TLD/ms DC-TLD/ms
Crowds 347 85.42 27.47
Football 312 104.37 55.28
Jumping 313 45.16 20.34
Walking 412 149.63 76.47
Fish 475 71.22 34.43
BlurFace 493 130.30 73.85

表 2可得,改进后的DC-TLD目标跟踪算法起到明显的提速效果。相对于其他测试序列,Crowds中的跟踪目标比其他测试序列的跟踪目标都要小一到两倍,算法对Crowds的提速效果最明显。因此对于跟踪较小目标而言,DC-TLD算法提速效果显著。

4.2 跟踪精确度

图 10为Football、Crowds、Walking、Jumping、Fish、BlurFace测试序列的部分截图,图 10中黄色框为本文改进算法的跟踪目标框,蓝色框为原始TLD算法跟踪到的目标框。改进后的DC-TLD算法在TLD算法跟踪失败的帧里没有出现跟踪失败的情况。

图 10 视频序列测试图。 Fig. 10 Video sequence test diagram. (a) Football;(b) Crowds;(c) Walking;(d) Jumping;(e) Fish;(f) BlurFace (a) Football; (b) Crowds; (c) Walking; (d) Jumping; (e) Fish; (f) BlurFace

表 3是测试视频精确度的结果,以成功跟踪目标帧数为算法精确度的度量。当把R值设定为2.9r时,DC-TLD成功跟踪目标的帧数比TLD有所提升。

表 3 测试视频精确度 Table 3 Test video accuracy
测试集 视频帧数 TLD成功跟踪帧数 DC-TLD成功跟踪帧数
Crowds 347 76 232
Football 312 286 288
Jumping 313 217 309
Walking 412 412 412
Fish 475 399 448
BlurFace 493 493 493
5 结论

本文对TLD目标跟踪算法中的目标检测区域选取方法进行了研究,提出了基于动态捕获区域的DC-TLD目标跟踪算法。首先采用前一帧成功跟踪的目标位置作为目标当前帧位置的预测值。然后通过分析得到负样本出现的阈值r,以r为基准,改变样本检测区域范围,得出R=2.9r时,DC-TLD算法的鲁棒性最好。最后针对检测样本的访问方式,提出了基于索引的访问方法。实验结果表明,提出的DC-TLD算法减少了时间复杂度,提高了跟踪精度。

DC-TLD算法仍存在不足之处,当跟踪目标较大时,DC-TLD算法和TLD算法的跟踪效果相近,且暂时无法对多目标进行跟踪。

参考文献
[1]
Cheng W L, Wang X J, Wan Z J, et al. Research and implementation of target tracking algorithm in compression domain on miniaturized DSP platform[J]. Opto-Electronic Engineering, 2017, 44(10): 972-982.
程卫亮, 王向军, 万子敬, 等. 压缩域目标跟踪算法在小型化DSP平台上的研究与实现[J]. 光电工程, 2017, 44(10): 972-982. DOI:10.3969/j.issn.1003-501X.2017.10.005
[2]
Henriques J F, Rui C, Martins P, et al. High-speed tracking with kernelized correlation filters[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2015, 37(3): 583-596. DOI:10.1109/TPAMI.2014.2345390
[3]
Nam H, Han B. Learning multi-domain convolutional neural networks for visual tracking[C]//Proceedings of 2016 IEEE Conference on Computer Vision and Pattern Recognition. Las Vegas: IEEE, 2016: 4293–4302. http://ieeexplore.ieee.org/document/7780834/
[4]
Nam H, Baek M, Han B. Modeling and propagating CNNs in a tree structure for visual tracking[EB/OL]. https://arxiv.org/abs/1608.07242v1, 2016.
[5]
Kalal Z, Mikolajczyk K, Matas J. Tracking-learning-detection[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(7): 1409-1422. DOI:10.1109/TPAMI.2011.239
[6]
Hare S, Saffari A, Torr P H S. Struck: structured output tracking with kernels[C]//Proceedings of 2011 IEEE International Conference on Computer Vision. Barcelona, Spain: IEEE, 2012: 263–270. http://ieeexplore.ieee.org/xpls/abs_all.jsp%3Farnumber%3D6126251
[7]
Brox T, Bruhn A, Papenberg N, et al. High accuracy optical flow estimation based on a theory for warping[C]//Proceedings of 2004 Computer Vision-ECCV. Berlin, Heidelberg: Springer, 2004: 25–36. http://link.springer.com/10.1007/978-3-540-24673-2_3
[8]
Kalal Z, Mikolajczyk K, Matas J. Forward-backward error: automatic detection of tracking failures[C]//Proceedings of 2010 20th International Conference on Pattern Recognition. Istanbul, Turkey: IEEE, 2010: 2756–2759. http://doi.ieeecomputersociety.org/10.1109/ICPR.2010.675
[9]
Viola P, Jones M. Rapid object detection using a boosted cascade of simple features[C]//Proceedings of 2011 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Kauai: IEEE, 2003. http://doi.ieeecomputersociety.org/10.1109/CVPR.2001.990517
[10]
Kalal Z, Matas J, Mikolajczyk K. P-N learning: bootstrapping binary classifiers by structural constraints[C]//Proceedings of 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. San Francisco: IEEE, 2014: 49–56. http://doi.ieeecomputersociety.org/10.1109/CVPR.2010.5540231
[11]
Jiang B. Research on TLD algorithm based on Kalman filter[D]. Xi'an: Xi'an University of Science and Technology, 2013.
江博. 基于Kalman的TLD目标跟踪算法研究[D]. 西安: 西安科技大学, 2013. http://cdmd.cnki.com.cn/Article/CDMD-10704-1014000315.htm
[12]
Wang M J, Wu X J. New IMM smoothing algorithm suitable for nonlinear maneuvering target tracking[J]. Opto-Electronic Engineering, 2016, 43(10): 18-24.
王美健, 吴小俊. 适于非线性机动目标跟踪的新IMM平滑算法[J]. 光电工程, 2016, 43(10): 18-24. DOI:10.3969/j.issn.1003-501X.2016.10.004
[13]
Wu Y, Lim J, Yang M H. Object tracking benchmark[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2015, 37(9): 1834-1848. DOI:10.1109/TPAMI.2014.2388226