TLD目标跟踪算法综述

杨丰瑞，杜　奎，庄　园

(1．重庆重邮信科集团股份有限公司，重庆400065；2.重庆邮电大学 通信新技术应用研究中心，重庆 400065)



TLD目标跟踪算法综述

杨丰瑞1，杜奎2，庄园2

(1．重庆重邮信科集团股份有限公司，重庆400065；2.重庆邮电大学 通信新技术应用研究中心，重庆 400065)

TLD目标跟踪算法将检测和跟踪同时加入跟踪框架，并引入半监督机器学习算法对锁定目标不断学习以捕获其最新外观，使目标无处可逃，从而实现对未知目标的长时跟踪。简要介绍了TLD算法的理论背景和系统框架，并指出其存在的主要缺陷。然后对各个缺陷所提出的改进方法进行详细地综述，并给出自己的评述。最后总结全文并展望TLD目标跟踪算法在未来几年的发展趋势。

长时目标跟踪；半监督机器学习；中直流跟踪器；随机森林分类器

目前，基于检测和半监督学习的目标跟踪算法已经成为研究的主流[1]。TLD作为一种基于检测和半监督学习的目标跟踪算法，因其具有良好的适应性和鲁棒性，自问世以来就引起了国内外学者的广泛关注。

自从Zdenek Kalal提出TLD目标跟踪算法以来，国内外学者对此提出了很多改进算法，但至今国内外还没有一篇综述对此进行详尽的阐述。本文从TLD目标跟踪算法所存在的缺陷出发对其进行全面的综述和分析。

1　TLD框架结构及原理

2009年，Zdenek Kalal先后提出了一种基于学习和分类的新型检测器[1]、PN学习器[2]和Median-Flow跟踪器[3]。2010年，在此基础上他正式提出了一种对未知目标具有长期跟踪能力的目标跟踪算法：Tracking-Learning-Detection，即TLD[4]。

1.1TLD提出的背景

传统跟踪算法对运动目标初始化后就可以快速地生成目标的运动轨迹，但传统跟踪算法由于仅仅依靠先验信息，所以其在运行时会不断累积误差，而且当目标在视野中消失后再次进入视野内，此时将直接导致跟踪失败；传统检测算法独立评估每一帧视频序列，判断每一帧中是否含有目标，如果有目标就给出目标状态信息，检测器不会因目标消失而导致检测失败，但是他们需要进行离线训练，所以无法对未知目标进行检测。

Zdenek Kalal认为传统跟踪算法或者检测算法不具备独立应对长时目标跟踪的条件，因为它们都不直接涉及跟踪框漂移后的在线处理，误差积累势必会越来越严重。Zdenek Kalal认为实现长期跟踪必须满足以下3点：

1)跟踪器具备一定的自检测能力。

2)加入半监督机器学习以实时更新目标模型。

3)检测模块与跟踪模块搭配。

1.2TLD目标跟踪系统框架

TLD算法由4个模块构成：跟踪模块、学习模块、检测模块和整合模块[4]。在TLD算法中，跟踪模块和检测模块并列运行，二者相互影响，检测模块可以重置跟踪模块，同时跟踪模块又可以通过学习模块为检测模块提供训练数据，紧接着将它们所生成的正负样本传入整合模块，整合模块生成正负样本参与半监督学习，此时负责存储具备表征当前目标外观的正负样本的目标模型得到更新，更新后的目标模型又反作用于跟踪模块和检测模块。TLD系统框架如图1所示。

图1　TLD系统框架图

2　TLD目标跟踪算法缺陷

近年来针对TLD算法存在的缺陷涌现出了相当多的改进方案。表1对TLD算法的缺陷、改进模块和对应的改进算法进行了分类归纳[6-32]。下面3个章节将从表1列出的缺陷出发，以缺陷为单位，对这些改进算法进行全面综述，并给出相应的评述。

表1TLD算法缺陷归纳

主要问题具体改进模块相关文献手动初始化检测模块[6]贪婪搜索检测模块[5,12,14,15,16,17,18,19,28]图像元方差分类器泛化能力相对较弱检测模块[12,22]目标模型样本膨胀学习模块[7,11,13,20]对相似目标辨识能力相对较弱检测模块、整合模块[13,14,15]发生严重遮挡时,目标框易漂移检测模块、整合模块[8,9,10,11,12,13,27,28,32,26]最近邻分类器耗时巨大检测模块[24,30]复杂背景下,目标框易漂移检测模块、整合模块[16,21,29,32]Median-Flow跟踪器稳定性相对较弱跟踪模块[14,23,31]目标发生大尺度形变时,目标框易漂移检测模块、跟踪模块[6,19,25]

3　针对TLD算法存在问题所提出的解决方案

3.1手动初始化

文献[6]采用运动目标检测和SIFT算法来识别出最佳匹配区域作为TLD初始跟踪区域。具体思想如下：1)利用SURF算法提取这两帧图像中匹配特征点对以完成快速注册；然后利用RANSAC算法剔除错误的匹配特征点对[6]；2)估计仿射模型得到仿射变换图像；3)借助运动直方图观察两个放射变换图像之间的差异；4)利用多帧关联技术提炼出前景跟踪框，同时剔除错误的运动目标；5)利用改进型SIFT算法来确定最优的匹配区域。目标自动初始化流程如图2所示。

图2目标自动初始化流程图

文献[6]所提出的方法确实实现了跟踪目标自动初始化，但是该方法需要在跟踪前消耗一定的时间去完整地遍历视频序列，相比原始算法，延长了初始化时间。

3.2贪婪搜索

所谓“贪婪搜索”，即TLD 中检测器是基于滑动窗口扫描的，检测器需要对图像中可能包含目标的子窗口进行扫描以确定窗口包含前景目标[12]。对一帧320×240大小的图像，检测模块大概需要遍历3万个子扫描窗口，而其中大概只有10%～25%的子窗口才包含目标[4]。

文献[5]提出ROI(Region Of Interest)理念，采用非全局搜索策略，即直接将目标框长与宽各扩大20像素，如果失败就利用背景抽离技术得到粗粒度的前景区域，然后通过模板匹配技术得到细粒度的前景区域。实验表明，该方法同时提高了帧处理速度[5]。

文献[12，14-15]均将Kalman滤波器预测区域作为目标检测区域，大同小异。

文献[16]在 TLD检测模块中加入Kalman滤波器和Meanshift算法。首先利用Meanshift算法迭代出置信度最高的目标区域，在该区域上做一外接矩形框，然后将其传给Kalman滤波器作为预测量，最后将Kalman滤波的预测区域作为Meanshift下一帧的初始搜索区域。

文献[17]提出一种检测区域自适应的方法。该方法利用双Kalman滤波器加速矫正预测区域。但该策略明显降低了TLD系统的跟踪精度。

文献[18]引入金字塔LK光流法获取目标区域，该策略具备动态生成扫描框的特性。

文献[19]引入粒子滤波，随机产生K个特征点作为运动粒子，接着利用Meanshift算法计算这些粒子在下一帧中的位置，然后计算各粒子位置加权和来得到下一帧目标所在的边界框。另外，为粒子权重设置阈值进一步弱化粒子退化产生的影响。

文献[28]利用基于帧差法的前景运动目标检测器替换图像元方差分类器。该策略在一定程度上增强了系统的实时性和鲁棒性。

产生“贪婪搜索”的主要原因就是TLD正负样本的生成策略不合理，提出新型正负样本生成方案方能从源头解决这个问题。

3.3发生严重遮挡时，目标框易漂移

基于抗遮挡的目标跟踪方法多依赖于预测理论，常见的预测手段有：Kalman滤波器、粒子滤波器和马尔科夫链。

文献[8]提出一种基于Kalman滤波的TLD跟踪算法，当TLD跟踪成功，TLD为Kalman滤波提供观测值，当TLD跟踪失败，则利用Kalman预测值取代观测值，随着递归的不断进行，最终输出目标状态[8]。

文献[9]在检测模块中加入SURF特征检测器。当目标出现快速运动、发生遮挡时，启动SURF特征检测器提取SURF特征以对目标进行二次检测，但此时不参与学习过程，防止采集不正确的正样本而导致跟踪失败。这种策略值得借鉴。

文献[10]提出一种基于参考点的TLD跟踪算法，所谓“参考点”，即在每一帧中实时地筛选出和目标具有一定联系的SURF特征点。当目标因发生部分或者完全遮挡而跟踪失败时，则可以利用参考点准确预测出目标所在区域。

文献[11]结合光电跟踪系统跟踪背景相对简单的特点，提出了适用于海空环境的TLD 算法。具体流程如图3所示。

图3目标自动初始化流程图

文献[13]使用改进的MIL跟踪器(Online MIL)替换Median-Flow跟踪器来进行目标跟踪，提高了目标在被遮挡情况下跟踪的鲁棒性。

文献[27]提出了完备的遮挡预判定的体系。遗憾的是其提出的抗遮挡解决方案相对于遮挡预判定的体系来说，过于粗略。

文献[28]提出了一种基于时空上下文目标跟踪(STC)和Kalman滤波器相结合的新型的跟踪器，并利用该跟踪器替代Median-Flow跟踪器。实验表明，该新型跟踪器对严重遮挡目标具有较强的容忍性。

文献[32]利用霍夫森林替换级联分类器。由于霍夫森林可以充分提取出目标的局部空间信息以及多通道特征，因此该策略可以有效增强系统鲁棒性。

在目标跟踪领域，对遮挡目标的跟踪始终没有强鲁棒性的算法被提出来，绝大多数的方案局限于在特定环境，将其应用在其他环境下可能就会发生限位框漂移的现象。上述文献所提出的方法依然是以特定环境为前提。

3.4目标模型样本膨胀

所谓“样本膨胀”，即目标模型更新时缺少限制样本数量的策略，随着跟踪系统的不断运行，目标模型中的正负样本数量会越来越多。导致目标模型样本冗余度高。

文献[7]通过为目标模型中正负样本总数量设定阈值来抑制正负样本膨胀，当正负样本总数量达到饱和状态时，就替换掉其内表征能力最弱的正样本或者负样本。但这种替换策略事实上违背了目标模型的数据结构。

文献[11]通过分析检测模块各级分类器的算法时间复杂度来论证：目标模型内样本数量过多会严重影响检测器的实时性。设图像块Pi(i=1，2，…，n)经过方差过滤器筛选之后剩余数量为N1，经过随机厥分类器筛选之后剩余图像块数量为N2。模型M中当前模板数量为Nt，模板像素数为Nm，则各级分类器算法时间复杂度如表2所示。

表2级联分类器时间复杂度

分类器图像元方差分类器随机厥分类器最近邻分类器复杂度O(Nb)O(N1·Nf)O(N2·Nt·Nm)

改进更新策略：从正负样本空间中剔除相似性最大的正样本数据和相似性最小的负样本数据。

对于目标模型中正负样本的限制均是基于这样一个事实：样本对当前目标外观的表征能力与加入目标模型的时间顺序成反比。

3.5相似目标辨识能力较弱

文献[13]在TLD框架内引入MIL跟踪器同时改进整合模块判决策略以此来应对具有相似干扰目标的场景。整合模块判决策略摒弃原有的权重论而是将通过比较跟踪模块与检测模块的输出置信度的大小来判决目标在下一帧的位置。另外，MIL跟踪器非常出色，但在此引入会导致框架过于复杂。

文献[14]巧妙地将马尔科夫预测器时域一致性的优点和特定场景进行融合，很好地解决了相似目标相向而行时目标框漂移的问题。

TLD检测模块在面对相似目标时容易被干扰目标同化，最有效的解决方法是通过融合前景和背景信息设计一个对相似干扰目标具有强鲁棒性的检测器。

3.6目标发生大尺度形变时，目标框易漂移

文献[6]引入综合性能优于SIFT和SURF算法的ORB描述器来增强TLD算法的跟踪器，改进型跟踪器与原始TLD跟踪器不同，在限位框内不再是均匀产生10×10个像素点，而是仅仅产生5×5个均匀像素点，剩下75个像素点是不均匀分布的ORB特征点。

文献[19]提出一种基于SAMS算法的尺度自适应策略，即使尺度跟随目标动态变化。

大尺度变换和目标遮挡长期以来被视作阻碍视觉目标跟踪发展的拦路虎。在满足实时性的前提下，目前尚没有很好的应对策略。

3.7复杂背景下，目标框易漂移

文献[16]针对在复杂场景下，目标与背景灰度差异小，方差分类器无法准确剔除背景目标。于是利用颜色特征彩色直方图替换灰度直方图，使方差分类器正常工作。

文献[21]所提出的方法依然是对引入颜色特征直方图对图像元方差分类器进行改进。总体与文献[16]大同小异。

文献[29]经实验发现，当检测器没有输出时，恰恰就是检测器中的最后一级分类器没有输出，但随机厥分类器的输出已经很接近目标位置了。于是，该文对第二级随机厥分类结果进行聚类分析，取其外接矩形框作为最终输出。

上述3篇文献介绍了TLD框架中检测模块和整合模块的缺陷，并且提出了行之有效的解决方案，实验表明，上述改进方案确实可以很好地解决复杂背景下跟踪框易漂移的问题。

3.8Median-Flow跟踪器稳定性相对较弱

导致Median-Flow跟踪器不稳定的主要因素是Lucas-Kanade光流法，Median-Flow跟踪器依赖后者产生具体的跟踪轨迹。但是光流法又是基于目标运动一致性假设的，当目标运动速度过快时，显然违背了该假设。在现实生活中，只有极少数的情景才满足目标运动一致性假设。

文献[14]所提出的跟踪器，是基于Cell FoT+算法的。跟踪器框架如图4所示。

图4　跟踪器框架

文献[23]引入粒子滤波和积分直方图来改进跟踪器。由于中值流跟踪器采用FB误差来实现跟踪自检测，其需要连续运用两次金字塔光流法跟踪特征点。显然，此举无形中增大了出错的风险。粒子滤波算法跟踪比较准确，但在长期跟踪中会面临粒子退化和粒子匮乏的问题。粒子滤波和金字塔光流法相结合的策略，不仅可以减少中值流跟踪器中累积的误差，还可以有效缓解粒子退化和粒子匮乏等现象。

在上述所述的方法中，文献[14]所提出的方法比较优秀，跟踪精度高，但是比较复杂，时间复杂度高。

3.9 最近邻分类器耗时巨大

目标模型中样本数量越大，最近邻分类器耗时越大[24]。

文献[24]将其提出的在目标遮挡和跟踪准确性上有着良好表现的MGACT算法替换最近邻分类器。MGACT 算法通过特征的压缩，在执行最后检测时，可以凭借压缩特征实现高速检测，进而大幅度提升帧处理速度。改进检测模块逻辑图见图5。

图5　改进检测模块逻辑图

文献[30]通过将前景检测、方差滤波、集成分类器和模板匹配串联起来替代原始的检测模块，如图3所示。在该新型检测模块中，前景检测依赖于背景抽离技术，在每一帧中将所有图像块与背景模型进行比较，如果两者相似度低于阈值，那么就滤除该图像块，反之将此图像块标记为正样本图像块，接着传入到下一级方法中；模板匹配技术在这4种“去噪”方法中对于负样本图像块的滤除是最严格、最有效果的，因为图像块之间的比较都是在像素级展开的，先后通过计算NCC、d(p1，p2)和d+/-，最后将这4个参数归一化为1个参数P+，以此来精确筛选出正负图像块样本。

(1)

(2)

(3)

4　总结

当前绝大多数的研究者都将注意力放在“贪婪搜索”和“目标遮挡”上。而“手动初始化”和“最近邻分类器耗时巨大”这两大缺陷却没有得到太多的关注。“手动初始化”这一缺点会在跟踪启动的时候就将误差等干扰因子引入整个系统，随着跟踪系统的不断进行，误差会不断累积，最终将导致跟踪失败；“最近邻分类器耗时巨大”这一问题，是关乎TLD系统实时性的决定性因素，亟待解决。

就目前来说，国内外对TLD的理论研究还不是很成熟，随着对TLD算法研究的不断深入，越来越多的缺陷会被挖掘，同时也会涌现出越来越多的优质高效地解决方案。

[1]KALALZ，MIKOLAJCZYKK，MATASJ.Forward-backwarderror：automaticdetectionoftrackingfailures[C]//Proc. 20thInternationalConferenceonPatternRecognition(ICPR). [S.l.]：IEEE，2010：2756-2759.

[2]KALALZ，MATASJ，MIKOLAJCZYKK.Onlinelearningofrobustobjectdetectorsduringunstabletracking[C]//Proc.IEEE12thInternationalConferenceonComputerVisionWorkshops(ICCVWorkshops) . [S.l.]：IEEE，2009：1417-1424.

[3]KALALZ，MATASJ，MIKOLAJCZYKK.Pnlearning：bootstrappingbinaryclassifiersbystructuralconstraints[C]//Proc.IEEEConferenceonComputerVisionandPatternRecognition(CVPR) . [S.l.]：IEEE，2010：49-56.

[4]KALALZ，MIKOLAJCZYKK，MATASJ.Tracking-learning-detection[J].IEEEtransactionsonpatternanalysisandmachineintelligence，2012，34(7)：1409-1422.

[5]NEMADEB，BHARADIVA.Adaptiveautomatictracking，learninganddetectionofanyrealtimeobjectinthevideostream[C]//Proc.IEEE5thInternationalConferenceonConfluenceTheNextGenerationInformationTechnologySummit(Confluence). [S.l.]：IEEE，2014： 569-575.

[6]HAILONGW，GUANGYUW，JIANXUNL.Animprovedtracking-learning-detectionmethod[C]//Proc.IEEE34thChineseControlConference(CCC). [S.l.]：IEEE，2015： 3858-3863.

[7]ZHANGP，SUNYQ，YA-LIWU，etal.AparallelimplementationofTLDalgorithmusingCUDA[C]// 2013全国高性能计算学术年会. 桂林：[出版者不详]，2013：220-224.

[8]龚小彪，何涛. 基于卡尔曼滤波的抗遮挡TLD跟踪算法[J]. 信息与电脑(理论版)，2014(4)：195-196.

[9]刘朵. 基于特征描述子的目标跟踪研究[D]. 西安：西安电子科技大学，2013.

[10]李敏敏.基于TLD模型的目标跟踪方法[D]. 西安：西安电子科技大学，2013.

[11]王建刚，李醒飞，陈诚，等. 改进TLD算法在光电跟踪中的应用[J].红外技术，2015(10)：824-830.

[12]张帅领.基于TLD的视频目标跟踪算法的研究[D]. 西安：西安电子科技大学，2014.

[13]高帆，吴国平，刑晨，等.TLD目标跟踪算法研究[J].电视技术，2013，37(11)：70-74.

[14]周鑫，钱秋朦，叶永强，等.改进后的TLD视频目标跟踪方法[J].中国图象图形学报，2013(9)：1115-1123.

[15]SUNC，ZHUS，LIUJ.FusingKalmanfilterwithTLDalgorithmfortargettracking[C]//Proc. 2015 34thChineseControlConference(CCC). [S.l.]：IEEE，2015：3736-3741.

[16]金龙，孙涵.TLD视频目标跟踪方法改进[J].计算机与现代化，2015(4)：42-46.

[17]曲海成，单晓晨，孟煜，等.检测区域动态调整的TLD目标跟踪算法[J].计算机应用，2015(10)：2985-2989.

[18]郑远力，胡志坤. 基于滑动扫描框的高速物体的图像实时跟踪算法[J]. 计算机科学，2015(10)：287-291.

[19]滕飞，刘清，朱琳. 一种快速鲁棒的内河CCTV系统船舶跟踪算法[J]. 武汉理工大学学报，2014(5)：80-85.

[20]江博.基于Kalman的TLD目标跟踪算法研究[D]. 西安：西安科技大学，2013.

[21]肖庆国，叶庆卫，周宇，等.基于Mean-Shift优化的TLD视频长时间跟踪算法[J].计算机应用研究，2015(3)：925-928.

[22]齐楠楠，揭斐然，谢熙，等.基于TLD的舰船目标跟踪方法研究[J].红外技术，2013(12)：780-787.

[23]周雅琪. 结合滤波理论的内河视频序列船舶TLD跟踪算法研究[D].武汉：武汉理工大学，2013.

[24]黄坤. 基于在线学习算法的目标跟踪技术研究[D]. 北京：北京理工大学，2015.

[25]程立英，张丹，赵姝颖，等.一种基于TLD改进的视觉跟踪算法[J].科学技术与工程，2013(9)：2382-2386.

[26]包涵，黄学航，陆星家.TLD目标追踪算法研究[J]. 宁波工程学院学报，2012(1)：52-54.

[27]杨萌，杨阳，王艺，等. 一种改进的TLD算法[J]. 传感器与微系统，2014(12)：130-133.

[28]吕枘蓬，蔡肖芋，董亮，等. 基于TLD框架的上下文目标跟踪算法[J]. 电视技术，2015，39(9)：6-9.

[29]成正国，潘广贞. 基于TLD的动态背景下视觉跟踪技术研究[J]. 电视技术，2015，39(7)：111-114.

[30]NEBEHAYG.Robustobjecttrackingbasedontracking-learning-detection[EB/OL]. [2015-12-18].http://www.gnebehay.com/publications/master_thesis/master_thesis.pdf.

[31]CHENGS，LIUG，SUNJ.Robustandfasttracking-learning-detection[C]//Proc. 2015InternationalConferenceonComputerScienceandIntelligentCommunication. [S.l.]：Atlantis，2015.

[32]李俊，谢维信，李良群. 基于空时线索的TLD视频跟踪算法[J]. 信号处理，2015，31(10)：1287-1293.

杜奎(1990— )，硕士生，主研视觉目标跟踪；

杨丰瑞(1963— )，博士，教授，主要研究方向为通信新技术应用与电信增值业务；

庄园(1990— )，女，硕士生，主研蜂窝网下D2D通信的干扰协调技术。

责任编辑：闫雯雯

Survey on TLD object tracking algorithm

YANG Fengrui1，DU Kui2，ZHUANG Yuan2

((1.ChongqingInformationTechnology(Group)Co.，Ltd.，Chongqing400065，China；2.ApplicationofNewTechnologiesofCommunicationResearchCenter，ChongqingUniversityofPostandTelecommunications，Chongqing400065，China)

In order to enable long-term tracking for unknown objects， a semi-supervized machine learning algorithm is added in object tracking based on TLD algorithm which matches traditional tracking algorithm and detection algorithm for keeping capturing the newest appearances by continuous learning. Firstly， TLD’s theoretical background， tracking framework and major defects are introduced. Then， the improvements of the original algorithm are elaborately disscussed. Finally， the propspects of object tracking based on TLD algorithm are presented.

object tracking；semi-supervized machine learning；median flow tracker；random forest classifier

TN391.41

ADOI： 10.16280/j.videoe.2016.10.021

2015年重庆市研究生科研创新项目(CYS15166)

2015-12-18

文献引用格式：杨丰瑞，杜奎，庄园. TLD目标跟踪算法综述[J].电视技术，2016，40(10)：101-106.YANG F R，DU K，ZHUANG Y. Survey on TLD object tracking algorithm [J]. Video engineering，2016，40(10)：101-106.