TLD目标跟踪算法（课堂PPT）

Tracking-Learning-Detection,目标跟踪算法,1,2,一、TLD算法简介二、TLD框架结构三、P-N学习四、TLD算法实现,主要内容,2,2020/5/18,一、TLD算法简介,TLD(Tracking-Learning-Detection)是英国萨里大学的一个捷克籍博士生ZdenekKalal在其攻读博士学位期间提出的一种新的单目标长时间（longtermtracking）跟踪算法。,Z.Kalal,K.Mikolajczyk,andJ.Matas,“Tracking-Learning-Detection,”PatternAnalysisandMachineIntelligence2011.Z.Kalal,K.Mikolajczyk,andJ.Matas,“Face-TLD:Tracking-Learning-DetectionAppliedtoFaces,”InternationalConferenceonImageProcessing,2010.Z.Kalal,K.Mikolajczyk,andJ.Matas,“Forward-BackwardError:AutomaticDetectionofTrackingFailures,”InternationalConferenceonPatternRecognition,2010,pp.23-26.Z.Kalal,J.Matas,andK.Mikolajczyk,“P-NLearning:BootstrappingBinaryClassifiersbyStructuralConstraints,”ConferenceonComputerVisionandPatternRecognition,2010.,作者相关文章：,ZdenekKalal,3,2020/5/18,一、TLD算法简介,长时间跟踪的一个关键的问题：,目标重新出现,重新检测,重新跟踪,TLD与传统跟踪算法的显著区别：,将传统的跟踪算法和传统的检测算法相结合，来解决被跟踪目标在被跟踪过程中发生的形变、部分遮挡、消失等问题。同时，通过一种改进的在线学习机制不断更新检测模块的目标模型及相关参数，从而使得跟踪效果更加稳定、鲁棒、可靠。,：形变、光照变化、尺度变化、遮挡、消失等情况,4,2020/5/18,一、TLD算法简介二、TLD框架结构三、P-N学习四、TLD算法实现,主要内容,5,2020/5/18,二、TLD框架结构,TLD算法框架主要由三部分组成：跟踪模块、检测模块、学习模块。,TLD架构结构图,6,2020/5/18,二、TLD框架结构,TLD算法运行机制：,跟踪模块假设相邻视频帧之间物体的运动是有限的，且被跟踪目标是可见的，以此来估计目标的运动。如果目标在相机视野中消失，将造成跟踪失败。检测模块假设每一个视帧都是彼此独立的，并且根据以往检测和学习到的目标模型，对每一帧图片进行全局搜索以定位目标可能出现的区域。学习模块根据跟踪模块的结果对检测模块的错误进行评估，并根据评估结果生成训练样本，对检测模块的目标模型及相关参数进行更新。检测模块和跟踪模块互补干涉的并行进行处理。,7,2020/5/18,一、TLD算法简介二、TLD框架结构三、P-N学习四、TLD算法实现,主要内容,8,2020/5/18,三、P-N学习,P-N学习：TLD的学习模块，是一种半监督的机器学习算法，目的是在线更新检测器，提高检测器的性能。它针对检测器对样本分类时产生的两种错误提供了两种“专家”进行纠正：,P-N学习的主要思想：检测器的错误能够被两种类型的专家（P-experts和N-experts）标识出。P-experts仅识别错误的负样本，N-experts仅识别错误的正样本。,P专家（P-expert）检出漏检（falsenegative，正样本被误分为负样本）的正样本，并将其添加到正样本集中；N专家（N-expert）改正误检（falsepositive，负样本被误分为正样本）的正样本，并将其添加到正样本集中。,9,2020/5/18,P-N学习结构图,P-N学习包含四个部分：,1.待学习的分类器,2.已标注的训练集,4.学习过程中产生正、负样本的函数,3.从训练样本集训练分类器的方法,10,2020/5/18,三、P-N学习,P-N学习的公式化（略）P-N学习的稳定性证明（略）P-N学习的仿真验证（略）,详细内容请参考：,Z.Kalal,K.Mikolajczyk,andJ.Matas,“Tracking-Learning-Detection,”PatternAnalysisandMachineIntelligence2011.Z.Kalal,J.Matas,andK.Mikolajczyk,“P-NLearning:BootstrappingBinaryClassifiersbyStructuralConstraints,”ConferenceonComputerVisionandPatternRecognition,2010.,11,2020/5/18,P-Nexperts的设计：,b）中待检测目标在一个视频帧中可能同时出现在好几个区域，并且待检测目标在相邻视频帧之间的运动没有连续性。,c）中每个视频帧中，目标只可能出现在一个区域，并且，相邻视频帧之间检测到的目标区域是连续的，构成了一个目标的运动轨迹。这种性质，我们称之为“结构性”。,a）中展示了覆盖有扫描窗格的三帧图片，每个方框定义一个图像片，图b)和c)中的红点表示正样本标签。,P-N专家的关键就是找到这种结构性的数据，从而来判别检测模块所产生的错误标签。,12,2020/5/18,P-Nexperts的设计：,P-experts寻找视频序列中的时域上的结构性特征，并且假设目标是沿着轨迹线移动的。P-experts记录目标在上一帧中的位置，并根据帧与帧之间的跟踪算法来预测目标在当前帧中的位置。如果检测模块将目标在当前帧中的位置标记为负标签，那么P-experts就产生一个正样本。,N-experts寻找视频序列中的空域上的结构性特征，并且假设目标在一个视频帧中只可能出现在一个位置。N-experts对检测模块在当前帧中的所有输出结果以及跟踪模块的输出结果进行分析，并找到置信度最高的结果。同置信度最高区域之间没有重叠的图相片被认定为负样本。另外，具有最大可能性的那个区域，被用于重新初始化跟踪模块。,13,2020/5/18,P-Nexperts的产生样本的例子：,目标是下面深色的车黑色框是检测器检测到的正样本黄色框是跟踪器产生的正样本红星标记的是每一帧最后的跟踪结果跟踪器代表产生正样本的P专家,在第t帧，检测器没有发现深色车，P专家认为深色车是正样本，N专家经过比较，认为深色车的样本更可信，所以把浅色车输出为负样本。,在第t+1帧的过程与之类似。,在第t+2帧时，P专家产生了错误的结果，但经过N专家的比较，又把这个结果排除了，算法仍然可以追踪到正确的车辆。,14,2020/5/18,一、TLD算法简介二、TLD框架结构三、P-N学习四、TLD算法实现,主要内容,15,2020/5/18,四、TLD算法实现,TLD架构详细的结构图,16,2020/5/18,(1)在任意时刻，被跟踪目标都可以用其状态属性来表示。该状态属性可以是一个方框或一个指示目标是否可见的标记。方框由它的位置和尺度来决定，有固定的长宽比。两个方框的空间相似度由重叠度来量化，定义为两个方框交集与并集之比。,(2)目标的外观用图像片p来表示，每一个图像片都是从跟踪框内部采样得到的，并被重采样到一个归一化的分辨率（15*15像素）。两个图相框pi,pj的相似度：,1.一些基本定义,NCC是一个归一化相关性系数。,17,2020/5/18,任意给定一个图像片P和目标模型M，我们定义几个量化指标：,正样本最近邻相似度负样本最近邻相似度前50%正样本的正最近邻相似度相对相似度保守相似度,1.一些基本定义,(3)目标模型是一个代表迄今为止观测到的被检测目标及其周围背景的数据结构，它是一系列正样本和负样本的集合,18,2020/5/18,2.跟踪模块-Tracker,带有失败检测（Failuredetection）的中值流（Median-Flow）跟踪算法，定义FB误差（forward-backwarderror）：,从时间t的初始位置x(t)开始追踪产生时间t+p的位置x(t+p)；再从位置x(t+p)反向追踪产生时间t的预测位置x(t)；初始位置x(t)和预测位置x(t)之间的欧氏距离就作为追踪器在t时间的FB误差。,19,2020/5/18,2.跟踪模块-Tracker,在第t帧的目标框中均匀撒点并采样作为特征点；使用金字塔LK光流法跟踪特征点在第t+1帧的对应位置。计算跟踪点的FB误差，筛选出FB误差最小的一半点作为最佳追踪点。根据这些点的坐标变化变化计算第t+1帧包围框的位置和尺度（平移和尺度的变化取中值）,中值流跟踪器,中值流跟踪器原理,20,2020/5/18,2.跟踪模块-Tracker,跟踪失败检测,跟踪模块的跟踪失败检测算法：,中值流跟踪算法的前提假设是目标是可见的，所以当目标完全被遮挡或者消失于视野，则不可避免地出现跟踪失败。,参考文献：Z.Kalal,K.Mikolajczyk,andJ.Matas,“Forward-BackwardError:AutomaticDetectionofTrackingFailures,”InternationalConferenceonPatternRecognition,2010,pp.23-26.,让表示其中某一个点的移动位移，表示位移中值，则残差可定义为。如果残差大于10个像素，那么就认为跟踪失败。这个策略能够很稳定地就确定出由剧烈移动或者遮挡所造成的跟踪失败。,21,2020/5/18,3.检测模块-Detection,检测器通过一个扫描窗口来扫描输入图像，然后判断出每一个图像块是否含有目标。在初始跟踪框的基础上，扫描窗口的参数设置为：,缩放比例的步长系数为1.2，产生20种尺度系数水平步长是宽度的10%，垂直步长是高度的10%最小的扫描窗口大小为20个像素。,如此，对于QVGA图片（240*320）来说会产生约5万个扫描方框，具体数字取决于初始框的长宽比。这是一个非常巨大的数字，每个图像块的处理必须非常高效。,22,2020/5/18,检测模块使用级联分类器（Cascsdedclassifier）来判断输入的图像块中是否还有目标，划分为三个模块：,方差分类器（PatchVariance）集成分类器（EnsembleClassifier）最近邻分类器（NNClassifier）,3.检测模块-Detection,图块1被方差分类器淘汰,图块3通过级联分类器,图块2被集成分类器淘汰,23,2020/5/18,3.1方差分类器,方差分类器淘汰所有灰度值方差（gray-valuevariance）小于初始跟踪框内图像块的50%的图像块，灰度值方差可以表示为：,一般而言，这一步会淘汰超过50%的非目标图像块（比如，天空，街道等等）。,24,2020/5/18,3.2集成分类器,经过方差分类器之后未被去除的图像块进入集成分类器。集成分类器由n(n=10)个独立的基本分类器组成，每个基本分类器对图像块进行m(m=10)组像素比较（pixelcomparisons），并产生一个二进制编码x。,每个基本分类器为树形结构（随机蕨分类器），每层的节点的判断准则相同，即,在图像元中任意选取两点A和B，比较这两点的亮度值，若A的亮度大于B，则特征值为1，否则为0。集成分类器由10棵树组成，每棵树有13层，图像块经过每棵树都会产生一个13位的二进制编码。,.,25,2020/5/18,3.2集成分类器,每棵树都对应一个关于二进制编码x的后验概率分布(|)，其中y0,1，=时表示正样本。,输入图像块经过所有基本分类器后，产生的10个后验概率值会被平均，集成分类器把平均后验概率大于0.5的图像块认为是目标。,26,2020/5/18,生成像素比较对,先用一个归一化（15*15）的patch去离散化像素空间，产生所有可能的垂直和水平的pixelcomparisons；,把这些pixelcomparisons随机分配给10个分类器，每个分类器得到不同的pixelcomparisons(特征集合，包含13组像素对）。,这样，保证了每个分类器基于一组不同的特征集合，而且所有的特征统一起来就可以覆盖整个patch了。,像素比较对的坐标离线、随机生成，并在运行过程中保持固定。,27,2020/5/18,后验概率分布,每个基本分类器的后验概率分布(|)表示为：,=#+#,#和#分别表示训练和更新过程中特征值对应的正样本和负样本的数量。,初始化及更新,在初始化阶段，所有后验概率的值均设为0。在运行时，集合分类器按如下更新：若已标注的样本被集合分类器错误分类，在更新相应的#和#，也就会更新(|)。,28,2020/5/18,3.3最近邻分类器,计算新样本的相对相似度，如大于阈值，则认为是正样本。,29,2020/5/18,4.综合模块-Integrator,跟踪器和检测器独立同步运行，各自输出预测到的目标框，而且检测器的输出结果很可能不唯一。综合器先对检测器的结果进行聚类，然后根据检测器聚类结果和跟踪器跟踪结果的置信