Awesome

title: TLD算法学习 date: 2016/12/30 22:04:12 categories:

计算机视觉 tags:
目标跟踪
oepncv
代码
TLD

[TOC]

2010年发表的论文《Tracking-Learning-Detection》 , GitHub上有很多C++版本的TLD，比如arthurv，注释比较详细，但速度很慢。


![Paste_Image.png](http://upload-images.jianshu.io/upload_images/454341-f518840d2338852d.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

TLD算法的构成

TLD(Tracking-Learning-Detection)是英国萨里大学的一个捷克籍博士生Zdenek Kalal
在其攻读博士学位期间提出的一种新的单目标长时间（long term tracking）跟踪算法。
该算法与传统跟踪算法的显著区别在于将传统的跟踪算法和传统的检测算法相结合
来解决被跟踪目标在被跟踪过程中发生的形变、部分遮挡等问题。
同时，通过一种改进的在线学习机制不断更新跟踪模块的“显著特征点”
和检测模块的目标模型及相关参数，从而使得跟踪效果更加稳定、鲁棒、可靠。


对于长时间跟踪而言，一个关键的问题是：当目标重新出现在相机视野中时，系统应该能重新检测到它，并开始重新跟踪。
但是，长时间跟踪过程中，被跟踪目标将不可避免的发生形状变化、光照条件变化、尺度变化、遮挡等情况。
传统的跟踪算法，前端需要跟检测模块相互配合，当检测到被跟踪目标之后，就开始进入跟踪模块，
而此后，检测模块就不会介入到跟踪过程中。但这种方法有一个致命的缺陷：即，当被跟踪目标存在形状变化或遮挡时，
跟踪就很容易失败；因此，对于长时间跟踪，或者被跟踪目标存在形状变化情况下的跟踪，很多人采用检测的方法来代替跟踪。
该方法虽然在某些情况下可以改进跟踪效果，但它需要一个离线的学习过程。
即：在检测之前，需要挑选大量的被跟踪目标的样本来进行学习和训练。
这也就意味着，训练样本要涵盖被跟踪目标可能发生的各种形变和各种尺度、姿态变化和光照变化的情况。
换言之，利用检测的方法来达到长时间跟踪的目的，对于训练样本的选择至关重要，否则，跟踪的鲁棒性就难以保证。

考虑到单纯的跟踪或者单纯的检测算法都无法在长时间跟踪过程中达到理想的效果，所以，
TLD方法就考虑将两者予以结合，并加入一种改进的在线学习机制，从而使得整体的目标跟踪更加稳定、有效。

TLD算法主要由三个模块构成：追踪器（tracker），检测器（detector）和机器学习（learning）。TLD算法成功的原因就在于它将检测器和跟踪器有机的整合在一起，从而实现了长线跟踪。

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

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

检测器的作用是估计追踪器的误差，如果误差很大就改正追踪器的结果。

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

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

追踪模块

TLD使用作者自己提出的Median-Flow光流追踪算法，采用的是Lucas-Kanade追踪器

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

跟踪点的选择

前面提到TLD跟踪的不是关键点，它跟踪的是更简单的点：能稳定存在的点，那哪些点是稳定的呢？Median-Flow tracker的基本思想是，看反向跟踪后的残差，用所有点的残差中值作为稳定点的筛选条件。如上图中的黄色点就因为残差太大，被pass掉了，既然稳定点是可以筛选出来的，那么就不必煞费苦心的寻找那些关键点，可以直接将所有的点都作为初始跟踪点，好吧所，有的点毕竟还是太多了，于是作者是选取网格交叉点作为初始跟踪点（见下图框框中黄色的点点）。

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

可以用NCC（Normalized Cross Correlation，归一化互相关）和SSD（Sum-of-Squared Differences，差值平方和）作为筛选追踪点的衡量标准。(都是越小越好)

NCC:

SSD:

学习模块

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

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

样本的产生

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

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

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

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

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

检测模块

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

图像元方差分类器（Patch Variance Classifier）。计算图像元像素灰度值的方差，把方差小于原始图像元方差一半的样本标记为负。论文提到在这一步可以排除掉一半以上的样本。
集成分类器（Ensemble Classifier）。实际上是一个随机蕨分类器（Random Ferns Classifier），类似于随机森林（Random Forest），区别在于随机森林的树中每层节点判断准则不同，而随机蕨的“蕨”中每层只有一种判断准则。所以这个分类器其实不怎么行。

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

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

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

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

以上过程可以视为对分类器的训练。当有新的未标签样本加入时，假设它经过这个蕨的结果为00011（即3），然后从已知的分布中寻找后验概率最大的一个。由于样本集固定时，右下角公式的分母是相同的，所以只要找在F=3时高度最大的那一类，就是新样本的分类。只用一个蕨进行分类会有较大的偶然性。另取5个新的特征值就可以构成新的蕨。用很多个蕨对同一样本分类，投票数最大的类就作为新样本的分类，这样在很大程度上提高了分类器的准确度。

最近邻分类器（Nearest Neighbor Classifier）。计算新样本的相对相似度，如大于0.6，则认为是正样本。相似度规定如下：图像元pi和pj的相似度，公式里的N是规范化的相关系数，所以S的取值范围就在[0,1]之间，

PN学习半监督学习

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

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

TLD源码理解

TLD算法成功的原因就在于它将检测器和跟踪器有机的整合在一起，从而实现了长线跟踪。

程序的运行方式

./run_tld -p ../parameters.yml -s ../datasets/06_car/car.mpg -b ../datasets/06_car/init.txt –r

-p 后面跟的是初始化参数
-s 后面的是人工视频的位置
-b 是初始化boundingbox的位置程序用readBB来读取初始化的bounding box

程序初始化过程

在run_tld.cpp的main函数里面进行了配置文件parameters.yml的读取，

buildGrid(frame1, box);

检测器采用扫描窗口的策略：扫描窗口步长为宽高的 10%，尺度缩放系数为1.2；此函数构建全部的扫描窗口grid，并计算每一个扫描窗口与输入的目标box的重叠度；重叠度定义为两个box的交集与它们的并集的比；

为各种变量或者容器分配内存空间；

getOverlappingBoxes(box, num_closest_init);

此函数根据传入的box（目标边界框），在整帧图像中的全部扫描窗口中（由上面4.1得到）寻找与该box距离最小（即最相似，重叠度最大）的num_closest_init（10）个窗口，然后把这些窗口归入good_boxes容器。同时，把重叠度小于0.2的，归入bad_boxes容器；相当于对全部的扫描窗口进行筛选。并通过BBhull函数得到这些扫描窗口的最大边界。

classifier.prepare(scales);

准备分类器，scales容器里是所有扫描窗口的尺度，由上面的buildGrid()函数初始化；

这是一种典型的特征比较简单，分类器比较复杂的例子.

TLD的分类器有三部分：方差分类器模块、集合分类器模块和最近邻分类器模块；这三个分类器是级联的，每一个扫描窗口依次全部通过上面三个分类器，才被认为含有前景目标。这里prepare这个函数主要是初始化集合分类器模块；

集合分类器（随机森林）基于n个基本分类器（共10棵树），每个分类器（树）都是基于一个pixel comparisons（共13个像素比较集）的，也就是说每棵树有13个判断节点（组成一个pixel comparisons），输入的图像片与每一个判断节点（相应像素点）进行比较，产生0或者1，然后将这13个0或者1连成一个13位的二进制码x（有2^13种可能），每一个x对应一个后验概率P(y|x)= #p/(#p+#n) （也有2^13种可能），#p和#n分别是正和负图像片的数目。那么整一个集合分类器（共10个基本分类器）就有10个后验概率了，将10个后验概率进行平均，如果大于阈值（一开始设经验值0.65，后面再训练优化）的话，就认为该图像片含有前景目标；用的是最简单的blending的组合方法。

后验概率P(y|x)= #p/(#p+#n)的产生方法：初始化时，每个后验概率都得初始化为0；运行时候以下面方式更新：将已知类别标签的样本（训练样本）通过n个分类器进行分类，如果分类结果错误，那么相应的#p和#n就会更新，这样P(y|x)也相应更新了。

pixel comparisons的产生方法：先用一个归一化的patch去离散化像素空间，产生所有可能的垂直和水平的pixel comparisons，然后我们把这些pixel comparisons随机分配给n个分类器，每个分类器得到完全不同的pixel comparisons（特征集合），这样，所有分类器的特征组统一起来就可以覆盖整个patch了。

特征是相对于一种尺度的矩形框而言的，TLD中第s种尺度的第i个特征features[s][i] = Feature(x1, y1, x2, y2); 是两个随机分配的像素点坐标 （就是由这两个像素点比较得到0或者1的）。计算特征的方法就是求patch在这两个点上的像素的大小。每一种尺度的扫描窗口都含有 totalFeatures = nstructs * structSize个特征；nstructs为树木（由一个特征组构建，每组特征代表图像块的不同视图表示）的个数；structSize为每棵树的特征个数，也即每棵树的判断节点个数；树上每一个特征都作为一个决策节点；

prepare函数的工作就是先给每一个扫描窗口初始化了对应的pixel comparisons（两个随机分配的像素点坐标）；然后初始化后验概率为0；

generatePositiveData(frame1, num_warps_init);

此函数通过对第一帧图像的目标框box（用户指定的要跟踪的目标）进行仿射变换来合成训练初始分类器的正样本集。具体方法如下：先在距离初始的目标框最近的扫描窗口内选择10个bounding box（已经由上面的getOverlappingBoxes函数得到，存于good_boxes里面了，还记得不？），然后在每个bounding box的内部，进行±1%范围的偏移，±1%范围的尺度变化，±10%范围的平面内旋转，并且在每个像素上增加方差为5的高斯噪声（确切的大小是在指定的范围内随机选择的），那么每个box都进行20次这种几何变换，那么10个box将产生200个仿射变换的bounding box，作为正样本。具体实现如下：

getPattern(frame(best_box), pEx, mean, stdev);

此函数将frame图像best_box区域的图像片归一化为均值为0的15*15大小的patch，存于pEx（用于最近邻分类器的正样本）正样本中（最近邻的box的Pattern），该正样本只有一个。

generator(frame, pt, warped, bbhull.size(), rng);

此函数属于PatchGenerator类的构造函数，用来对图像区域进行仿射变换，先RNG一个随机因子，再调用（）运算符产生一个变换后的正样本。

classifier.getFeatures(patch, grid[idx].sidx, fern);

函数得到输入的patch的特征fern（13位的二进制代码）；

pX.push_back(make_pair(fern, 1));   //positive ferns <features, labels=1>

然后标记为正样本，存入pX（用于集合分类器的正样本）正样本库；

以上的操作会循环 num_warps * good_boxes.size()即20 * 10 次，这样，pEx就有了一个正样本，而pX有了200个正样本了；

meanStdDev(frame1(best_box), mean, stdev);

统计best_box的均值和标准差，var = pow(stdev.val[0],2) * 0.5;作为方差分类器的阈值。

generateNegativeData(frame1);

由于TLD仅跟踪一个目标，所以我们确定了目标框了，故除目标框外的其他图像都是负样本，无需仿射变换；具体实现如下：

由于之前重叠度小于0.2的，都归入 bad_boxes了，所以数量挺多，把方差大于var 0.5f的bad_boxes（使得负样本很丰富）都加入负样本，同上面一样，需要classifier.getFeatures(patch, grid[idx].sidx, fern);和nX.push_back(make_pair(fern, 0));得到对应的fern特征和标签的nX负样本（用于集合分类器的负样本）；

然后随机在上面的bad_boxes中取bad_patches（100个）个box，然后用 getPattern函数将frame图像bad_box区域的图像片归一化到15*15大小的patch，存在nEx（用于最近邻分类器的负样本）负样本中。

这样nEx和nX都有负样本了；（box的方差通过积分图像计算用于方差检测器）

然后将nEx的一半作为训练集nEx，另一半作为测试集nExT；同样，nX也拆分为训练集nX和测试集nXT；

将负样本的特征nX和正样本特征pX合并到ferns_data[]中，用于集合分类器的训练；

将上面得到的一个正样本pEx和nEx合并到nn_data[]中，用于最近邻分类器的训练；

训练

这两个训练方法就是简单的模板匹配法，集合分类器训练的是后验概率，而最近邻分类器训练的是啥

用上面的样本训练集训练集合分类器（森林）和最近邻分类器： classifier.trainF(ferns_data, 2); //bootstrap = 2

对每一个样本ferns_data[i] ，如果样本是正样本标签，先用measure_forest函数返回该样本所有树的所有特征值对应的后验概率累加值，该累加值如果小于正样本阈值（0.6* nstructs，表示平均值需要大于0.6（0.6* nstructs / nstructs）,0.6是程序初始化时定的集合分类器的阈值，为经验值，后面会用测试集来评估修改，找到最优），同时用update函数更新后验概率。

classifier.trainNN(nn_data);

对每一个样本nn_data，如果标签是正样本，通过NNConf(nn_examples[i], isin, conf, dummy);计算输入图像片与在线模型之间的相关相似度conf，如果相关相似度小于0.65 ，则认为其不含有前景目标，也就是分类错误了；这时候就把它加到正样本库。然后就通过pEx.push_back(nn_examples[i]);将该样本添加到pEx正样本库中；同样，如果出现负样本分类错误，就添加到负样本库。

分类器评价？

用测试集在上面得到的集合分类器（森林）和最近邻分类器中分类，评价并修改得到最好的分类器阈值。

classifier.evaluateTh(nXT, nExT);

对集合分类器，对每一个测试集nXT，所有基本分类器的后验概率的平均值如果大于thr_fern（0.6），则认为含有前景目标，然后取最大的平均值（如果大于thr_fern）作为该集合分类器的新的阈值。

对最近邻分类器，对每一个测试集nExT，最大相关相似度如果大于nn_fern（0.65），则认为含有前景目标，然后取最大的最大相关相似度（如果大于nn_fern）作为该最近邻分类器的新的阈值。

处理视频

processFrame(last_gray, current_gray, pts1, pts2, pbox, status, tl, bb_file);

逐帧读入图片序列，进行算法处理。processFrame共包含四个模块（依次处理）：跟踪模块、检测模块、综合模块和学习模块；

跟踪模块

http://docs.opencv.org/3.1.0/dc/d6b/group__video__track.html#ga473e4b886d0bcc6b65831eb88ed93323

其中normCrossCorrelation

其中normCrossCorrelation(img1,img2,points1,points2)是对光流法跟踪的结果不放心，因此希望通过对比前后两点周围的小块的相似性，来进一步去掉不稳定的点。这次的相似性不是相关系数，而是normalized cross-correlation (NCC)：

模板匹配 matchTemplate

opencv document matchTemplate

这个是opnecv中的一个函数模板匹配是一项在一幅图像中寻找与另一幅模板图像最匹配(相似)部分的技术.

需要2幅图像: 原图像 (I): 在这幅图像里,我们希望找到一块和模板匹配的区域模板 (T): 将和原图像比照的图像块目标是检测最匹配的区域:

通过滑动, 图像块一次移动一个像素 (从左往右,从上往下). 在每一个位置, 都进行一次度量计算来表明它是 “好” 或 “坏” 地与那个位置匹配 (或者说块图像和原图像的特定区域有多么相似). 对于 T 覆盖在 I 上的每个位置,你把度量值保存到结果图像矩阵 (R) 中. 在 R 中的每个位置 (x,y) 都包含匹配度量值(以此点开始的块的相似度)

opencv提供的模板匹配相似度计算方法有6类

标准相关匹配 method=CV_TM_CCORR_NORMED