Tracking-Learning-Detection原理分析

清疚 2022-08-05 15:05 132阅读 0赞

转自http://johnhany.net/2014/05/tld-the-theory/

Tracking-Learning-Detection（TLD）是[Zdenek Kalal][]提出的一种对视频中单个物体长时间跟踪的算法。我主要会根据他在2010年发表的论文《Tracking-Learning-Detection》来分析TLD算法的原理。该项目的[首页][Link 1]中有几段视频展示了TLD实时跟踪的效果和性能，其中的两个视频可以在这里下载：[similar objects][]，[human face][]。作者公布了[源代码][Link 2]，不过需要Matlab和Visual Studio交叉编译，在我的机器上没能运行。GitHub上有很多C++版本的TLD，比如[arthurv][]，注释比较详细，但速度很慢。

由于我使用的插件默认对所有图片加水印，所以本文中使用的大多数并不是我绘制的图片也加上了水印，还请谅解。

--------------------

正如名字所示，TLD算法主要由三个模块构成：追踪器（tracker），检测器（detector）和机器学习（learning）。

对于视频追踪来说，常用的方法有两种，一是使用追踪器根据物体在上一帧的位置预测它在下一帧的位置，但这样会积累误差，而且一旦物体在图像中消失，追踪器就会永久失效，即使物体再出现也无法完成追踪；另一种方法是使用检测器，对每一帧单独处理检测物体的位置，但这又需要提前对检测器离线训练，只能用来追踪事先已知的物体。

TLD是对视频中未知物体的长时间跟踪的算法。“未知物体”指的是任意的物体，在开始追踪之前不知道哪个物体是目标。“长时间跟踪”又意味着需要算法实时计算，在追踪中途物体可能会消失再出现，而且随着光照、背景的变化和由于偶尔的部分遮挡，物体在像素上体现出来的“外观”可能会发生很大的变化。从这几点要求看来，单独使用追踪器或检测器都无法胜任这样的工作。所以作者提出把追踪器和检测器结合使用，同时加入机器学习来提高结果的准确度。

[![tld][]][tld 1]

![image-568][tld]

追踪器的作用是跟踪连续帧间的运动，当物体始终可见时跟踪器才会有效。追踪器根据物体在前一帧已知的位置估计在当前帧的位置，这样就会产生一条物体运动的轨迹，从这条轨迹可以为学习模块产生正样本（Tracking->Learning）。

检测器的作用是估计追踪器的误差，如果误差很大就改正追踪器的结果。检测器对每一帧图像都做全面的扫描，找到与目标物体相似的所有外观的位置，从检测产生的结果中产生正样本和负样本，交给学习模块（Detection->Learning）。算法从所有正样本中选出一个最可信的位置作为这一帧TLD的输出结果，然后用这个结果更新追踪器的起始位置（Detection->Tracking）。

学习模块根据追踪器和检测器产生的正负样本，迭代训练分类器，改善检测器的精度（Learning->Detection）。

--------------------

追踪模块

TLD使用作者自己提出的Median-Flow追踪算法。

作者假设一个“好”的追踪算法应该具有正反向连续性（forward-backward consistency），即无论是按照时间上的正序追踪还是反序追踪，产生的轨迹应该是一样的。作者根据这个性质规定了任意一个追踪器的FB误差（forward-backward error）：从时间t的初始位置x(t)开始追踪产生时间t+p的位置x(t+p)，再从位置x(t+p)反向追踪产生时间t的预测位置x\`(t)，初始位置和预测位置之间的欧氏距离就作为追踪器在t时间的FB误差。

[![fb-error][]][fb-error 1]

![image-569][fb-error]

Median-Flow追踪算法采用的是Lucas-Kanade追踪器，也就是常说的光流法追踪器。这个追踪器的原理就不在这里解释了。只需要知道给定若干追踪点，追踪器会根据像素的运动情况确定这些追踪点在下一帧的位置。

追踪点的选择

作者给出了一种依据FB误差绘制误差图（Error Map）筛选最佳追踪点的方法，但并不适用于实时追踪任务，就不详细介绍了。这里只介绍在TLD中确定追踪点的方法。

首先在上一帧t的物体包围框里均匀地产生一些点，然后用Lucas-Kanade追踪器正向追踪这些点到t+1帧，再反向追踪到t帧，计算FB误差，筛选出FB误差最小的一半点作为最佳追踪点。最后根据这些点的坐标变化和距离的变化计算t+1帧包围框的位置和大小（平移的尺度取中值，缩放的尺度取中值。取中值的光流法，估计这也是名称Median-Flow的由来吧）。

[![tracking-points][]][tracking-points 1]

![image-570][tracking-points]

还可以用NCC（Normalized Cross Correlation，归一化互相关）和SSD（Sum-of-Squared Differences，差值平方和）作为筛选追踪点的衡量标准。作者的代码中是把FB误差和NCC结合起来的，所以筛选出的追踪点比原来一半还要少。

NCC：

[![ncc][]][ncc 1]

![image-571][ncc]

--------------------

学习模块

TLD使用的机器学习方法是作者提出的P-N学习（P-N Learning）。P-N学习是一种半监督的机器学习算法，它针对检测器对样本分类时产生的两种错误提供了两种“专家”进行纠正：

P专家（P-expert）：检出漏检（false negative，正样本误分为负样本）的正样本；

N专家（N-expert）：改正误检（false positive，负样本误分为正样本）的正样本。

样本的产生

用不同尺寸的扫描窗（scanning grid）对图像进行逐行扫描，每在一个位置就形成一个包围框（bounding box），包围框所确定的图像区域称为一个图像元（patch），图像元进入机器学习的样本集就成为一个样本。扫描产生的样本是未标签样本，需要用分类器来分类，确定它的标签。

如果算法已经确定物体在t+1帧的位置（实际上是确定了相应包围框的位置），从检测器产生的包围框中筛选出10个与它距离最近的包围框（两个包围框的交的面积除以并的面积大于0.7），对每个包围框做微小的仿射变换（平移10%、缩放10%、旋转10°以内），产生20个图像元，这样就产生200个正样本。再选出若干距离较远的包围框（交的面积除以并的面积小于0.2），产生负样本。这样产生的样本是已标签的样本，把这些样本放入训练集，用于更新分类器的参数。下图中的a图展示的是扫描窗的例子。

[![structure][]][structure 1]

![image-572][structure]

作者认为，算法的结果应该具有“结构性”：每一帧图像内物体最多只出现在一个位置；相邻帧间物体的运动是连续的，连续帧的位置可以构成一条较平滑的轨迹。比如像上图c图那样每帧只有一个正的结果，而且连续帧的结果构成了一条平滑的轨迹，而不是像b图那样有很多结果而且无法形成轨迹。还应该注意在整个追踪过程中，轨迹可能是分段的，因为物体有可能中途消失，之后再度出现。

P专家的作用是寻找数据在时间上的结构性，它利用追踪器的结果预测物体在t+1帧的位置。如果这个位置（包围框）被检测器分类为负，P专家就把这个位置改为正。也就是说P专家要保证物体在连续帧上出现的位置可以构成连续的轨迹；

N专家的作用是寻找数据在空间上的结构性，它把检测器产生的和P专家产生的所有正样本进行比较，选择出一个最可信的位置，保证物体最多只出现在一个位置上，把这个位置作为TLD算法的追踪结果。同时这个位置也用来重新初始化追踪器。

[![p-n-experts][]][p-n-experts 1]

![image-573][p-n-experts]

比如在这个例子中，目标车辆是下面的深色车，每一帧中黑色框是检测器检测到的正样本，黄色框是追踪器产生的正样本，红星标记的是每一帧最后的追踪结果。在第t帧，检测器没有发现深色车，但P专家根据追踪器的结果认为深色车也是正样本，N专家经过比较，认为深色车的样本更可信，所以把浅色车输出为负样本。第t+1帧的过程与之类似。第t+2帧时，P专家产生了错误的结果，但经过N专家的比较，又把这个结果排除了，算法仍然可以追踪到正确的车辆。

--------------------

检测模块

检测模块使用一个级联分类器，对从包围框获得的样本进行分类。级联分类器包含三个级别：

图像元方差分类器（Patch Variance Classifier）。计算图像元像素灰度值的方差，把方差小于原始图像元方差一半的样本标记为负。论文提到在这一步可以排除掉一半以上的样本。

集成分类器（Ensemble Classifier）。实际上是一个随机蕨分类器（Random Ferns Classifier），类似于随机森林（Random Forest），区别在于随机森林的树中每层节点判断准则不同，而随机蕨的“蕨”中每层只有一种判断准则。

[![random-ferns][]][random-ferns 1]

![image-574][random-ferns]

如上图所示，把左面的树每层节点改成相同的判断条件，就变成了右面的蕨。所以蕨也不再是树状结构，而是线性结构。随机蕨分类器根据样本的特征值判断其分类。从图像元中任意选取两点A和B，比较这两点的亮度值，若A的亮度大于B，则特征值为1，否则为0。每选取一对新位置，就是一个新的特征值。蕨的每个节点就是对一对像素点进行比较。

比如取5对点，红色为A，蓝色为B，样本图像经过含有5个节点的蕨，每个节点的结果按顺序排列起来，得到长度为5的二进制序列01011，转化成十进制数字11。这个11就是该样本经过这个蕨得到的结果。

[![random-ferns-2][]][random-ferns-2 1]

![image-575][random-ferns-2]

同一类的很多个样本经过同一个蕨，得到了该类结果的分布直方图。高度代表类的先验概率p(F|C)，F代表蕨的结果（如果蕨有s个节点，则共有1+2^s种结果）。

[![random-ferns-3][]][random-ferns-3 1]

![image-576][random-ferns-3]

不同类的样本经过同一个蕨，得到不同的先验概率分布。

[![random-ferns-4][]][random-ferns-4 1]

![image-577][random-ferns-4]

以上过程可以视为对分类器的训练。当有新的未标签样本加入时，假设它经过这个蕨的结果为00011（即3），然后从已知的分布中寻找后验概率最大的一个。由于样本集固定时，右下角公式的分母是相同的，所以只要找在F=3时高度最大的那一类，就是新样本的分类。

[![random-ferns-5][]][random-ferns-5 1]

![image-578][random-ferns-5]

只用一个蕨进行分类会有较大的偶然性。另取5个新的特征值就可以构成新的蕨。用很多个蕨对同一样本分类，投票数最大的类就作为新样本的分类，这样在很大程度上提高了分类器的准确度。

最近邻分类器（Nearest Neighbor Classifier）。计算新样本的相对相似度，如大于0.6，则认为是正样本。相似度规定如下：

图像元pi和pj的相似度，公式里的N是规范化的相关系数，所以S的取值范围就在\[0,1\]之间，

[![similarity-1][]][similarity-1 1]

![image-579][similarity-1]

正最近邻相似度，

[![similarity-2][]][similarity-2 1]

![image-580][similarity-2]

负最近邻相似度，

[![similarity-3][]][similarity-3 1]

![image-581][similarity-3]

相对相似度，取值范围在\[0,1\]之间，值越大代表相似度越高，

[![similarity-4][]][similarity-4 1]

![image-582][similarity-4]

--------------------

所以，检测器是追踪器的监督者，因为检测器要改正追踪器的错误；而追踪器是训练检测器时的监督者，因为要用追踪器的结果对检测器的分类结果进行监督。用另一段程序对训练过程进行监督，而不是由人来监督，这也是称P-N学习为“半监督”机器学习的原因。

TLD的工作流程如下图所示。首先，检测器由一系列包围框产生样本，经过级联分类器产生正样本，放入样本集；然后使用追踪器估计出物体的新位置，P专家根据这个位置又产生正样本，N专家从这些正样本里选出一个最可信的，同时把其他正样本标记为负；最后用正样本更新检测器的分类器参数，并确定下一帧物体包围框的位置。

[![TLD-workflow][]][TLD-workflow 1]

[Zdenek Kalal]: http://personal.ee.surrey.ac.uk/Personal/Z.Kalal/index.html
[Link 1]: http://personal.ee.surrey.ac.uk/Personal/Z.Kalal/tld.html
[similar objects]: http://pan.baidu.com/s/1eQh6J9S
[human face]: http://pan.baidu.com/s/1dDioJIx
[Link 2]: https://github.com/zk00006/OpenTLD
[arthurv]: https://github.com/arthurv/OpenTLD
[tld]: http://johnhany.net/wp-content/uploads/2014/05/tld.png
[tld 1]: http://johnhany.net/2014/05/tld-the-theory/#image-568
[fb-error]: http://johnhany.net/wp-content/uploads/2014/05/fb-error.png
[fb-error 1]: http://johnhany.net/2014/05/tld-the-theory/#image-569
[tracking-points]: http://johnhany.net/wp-content/uploads/2014/05/tracking-points.png
[tracking-points 1]: http://johnhany.net/2014/05/tld-the-theory/#image-570
[ncc]: http://johnhany.net/wp-content/uploads/2014/05/ncc.png
[ncc 1]: http://johnhany.net/2014/05/tld-the-theory/#image-571
[structure]: http://johnhany.net/wp-content/uploads/2014/05/structure.png
[structure 1]: http://johnhany.net/2014/05/tld-the-theory/#image-572
[p-n-experts]: http://johnhany.net/wp-content/uploads/2014/05/p-n-experts.png
[p-n-experts 1]: http://johnhany.net/2014/05/tld-the-theory/#image-573
[random-ferns]: http://johnhany.net/wp-content/uploads/2014/05/pic6.png
[random-ferns 1]: http://johnhany.net/2014/05/tld-the-theory/#image-574
[random-ferns-2]: http://johnhany.net/wp-content/uploads/2014/05/random-ferns-2.png
[random-ferns-2 1]: http://johnhany.net/2014/05/tld-the-theory/#image-575
[random-ferns-3]: http://johnhany.net/wp-content/uploads/2014/05/random-ferns-3.png
[random-ferns-3 1]: http://johnhany.net/2014/05/tld-the-theory/#image-576
[random-ferns-4]: http://johnhany.net/wp-content/uploads/2014/05/random-ferns-4.png
[random-ferns-4 1]: http://johnhany.net/2014/05/tld-the-theory/#image-577
[random-ferns-5]: http://johnhany.net/wp-content/uploads/2014/05/random-ferns-5.png
[random-ferns-5 1]: http://johnhany.net/2014/05/tld-the-theory/#image-578
[similarity-1]: http://johnhany.net/wp-content/uploads/2014/05/similarity-1.png
[similarity-1 1]: http://johnhany.net/2014/05/tld-the-theory/#image-579
[similarity-2]: http://johnhany.net/wp-content/uploads/2014/05/similarity-2.png
[similarity-2 1]: http://johnhany.net/2014/05/tld-the-theory/#image-580
[similarity-3]: http://johnhany.net/wp-content/uploads/2014/05/similarity-3.png
[similarity-3 1]: http://johnhany.net/2014/05/tld-the-theory/#image-581
[similarity-4]: http://johnhany.net/wp-content/uploads/2014/05/similarity-4.png
[similarity-4 1]: http://johnhany.net/2014/05/tld-the-theory/#image-582
[TLD-workflow]: http://johnhany.net/wp-content/uploads/2014/05/TLD-workflow.png
[TLD-workflow 1]: http://johnhany.net/2014/05/tld-the-theory/#image-583