随着计算机和图像处理技术的发展，计算机视觉技术被广泛应用到各个领域。目标跟踪作为计算机视觉重点研究领域之一，在视频监控、智慧交通、人机游戏交互等领域得到了广泛应用^[1]。在实际应用中，跟踪算法的实时性、准确度以及鲁棒性都是影响其应用的核心因素。随着嵌入式处理器的发展，将目标跟踪算法应用于嵌入式平台的需求越来越多，而实时性和准确性则是主要的参数性能指标。众所周知，嵌入式处理器的处理速度达不到PC机处理的高性能指标，因此，为了得到更快更准确的跟踪效果，需要减小跟踪算法的复杂度，这是一个值得研究的课题方向。TLD框架在长时间的目标跟踪以及在准确度和鲁棒性方面做得非常优秀，而在实时性方面还可以进一步优化，以满足应用于嵌入式硬件平台要求。

本文提出了基于Camshift和TLD框架的算法用以减小TLD框架算法复杂度的问题，提出以下改进方法。首先，TLD框架的跟踪器模块使用的是基于Lucas-Kanade光流法的跟踪算法，该算法需要计算稀疏光流，需要指定一组点进行跟踪，但需要计算某些点集的光流速度场，该跟踪算法跟踪性好，但算法复杂度较高，不适用运算性能较差的嵌入式平台。而Camshift是一种利用颜色的概率信息进行运动目标跟踪的轻量级算法^[2]，它计算目标色度H分量的直方图，复杂度较低，运行效率较高；它还可以自适应调整目标窗口的大小，其缺点是当背景有相似颜色时，会出现跟踪错误的情况，需要结合TLD学习模块P-expert进行优化。其次，当跟踪失败时，需要TLD框架中的检测器模块来重新检测目标并初始化跟踪器。检测器的检测效率也直接影响到整个框架的运行效率，由于待检测子窗口数量很大，本文提出使用背景差分法确定目标待检测区域，减少子窗口数目，提高后面各种分类器的执行效率。最后，原始的TLD框架只是针对单个目标长时间跟踪，实际应用中可能会出现对多个运动目标进行跟踪的情况，因此需要对TLD进行优化扩展，因此使用多线程机制实现对多个目标实现长时间跟踪。

1 TLD算法框架

TLD是Zdenek Kalal提出的一种高效稳健的单目标长时间跟踪算法，在背景遮挡，尺度、亮度变化，实时性等方面有着良好性能表现^[3]。该框架结构如图 1所示，将目标的长时间跟踪任务清晰地分解成3个部分，即跟踪、学习和检测。跟踪器在视频连续帧中跟踪目标；检测器是将已经检测的特征进行局部化处理，并根据需要不断修正跟踪器；学习模块估计出检测器的错误和误差，并及时更新检测器，以避免后续出现误差。学习模块根据追踪器和检测器产生的正负样本，迭代训练分类器，改善检测器的精度。TLD不需要线下数据训练，仅需要在跟踪过程中在样本库中产生变化量，并实现自我学习。

1.1 跟踪模块

TLD的跟踪模块是基于金字塔L-K光流进行跟踪，并且有一个扩展的误差检测。笔者提出了误差检测包括归一化互相关(NCC)和前向后向误差(forward-backward error)。利用跟踪到的像素块计算出其在当前帧中图像块上的位置信息和这些像素点在上一帧中图像块位置的NCC值(归一化相关系数，如式(1)所示)，得到的NCC取中值，小于中值的像素点，均被舍弃掉。在剩下50%的像素点中，计算前向后向误差的中值，舍弃大于前向后向误差中值的像素点，用剩下的像素点来估计出目标边界框在当前帧中的位置。

前后向误差测量方法如图 2所示。在左图中，像素点1被跟踪点正确位于右图中对应位置，然而对于点2，因为遮挡使得相应的被跟踪点出现在错误位置。这种测量方法的前提是前后帧中跟踪点必须是可逆的。

1.2 TLD检测器模块

TLD框架的检测模块使用一个级联分类器，对从目标边界框获得的样本进行分类，而它包含3个级联的子分类器：1)图像方差分类器；2)集成分类器；3)最近邻分类器^[4]。

1.2.1 图像方差分类器

计算图像元像素灰度值的方差，如果图像块的灰度值方差小于目标图像块灰度值方差的50%，那么就可以舍弃这些图像块。对于一个图像块p,灰度值方差计算为

式中E(p)为图像块矩阵的期望，可以使用积分图方法计算得到。

1.2.2 集成分类器

集成分类器(ensemble classifier)实际上是一个随机蕨分类器(random ferns classifier)，类似于随机森林(random forest)，区别在于随机森林的树中每层节点判断准则不同，而随机蕨的“蕨”中每层只有一种判断准则，其类筛选过程如图 3。

当属于同一类的多个输入特征向量使用同一个蕨类分类器时，这是特征向量服从多项分布，得到了该类结果的分布直方图。高度代表类的先验概率P(F|C_i)，其中F代表蕨的结果，其数量由蕨类节点决定，如果蕨有S个节点，则共有1+2^s种结果。

如果只用一个蕨进行分类会造成较大的偶然性。另取5个新的特征值就可以构成新的蕨。很多个蕨对同一样本分类，投票数最大的类就作为新样本的分类，求得新分类的后验概率p(C_k|F)(如式(3)所示)，这样在很大程度上提高了分类器的准确度^[5]。

1.2.3 最近邻分类器

通过方差分类器和集合分类器的筛选，目标图像块大幅度减少，但是我们还可以通过最近邻分类器(nearest neighbor classifier)进一步筛选。计算剩余图像块之间的相似度S(p_i,M)，如式(4)所示。

式中：p_i代表待分类的图像块，N(p_i,p_j)是规范化相关系数，S(p_i,p_j)取值为[0, 1]。然后可以求得相对相似度S^r(p_i,p_j)如式(5)所示。

式中：M代表正负图像块的集合，M={p₁⁺,p₂⁺,…,p_m⁺,p₁^-,p₂^-,…,p_n^-},其中p^－,p⁺分别表示目标和背景的图像块。如果S^r(p_i,M)＞θ_NN,则p_i是正样本，被分类到目标区域，其中θ_NN=0.6^[6]，这是一个经过测试的经验值。

1.3 TLD学习模块

TLD所使用的学习模块是作者提出的P-N学习算法，这是一种半监督的机器学习算法，它针对TLD目标检测器对样本分类时产生的2种错误进行纠正，由P“专家”(P-expert)检出false negative错误)和N“专家”(N-expert)检验false positive错误^[7]。其中false negative错误是指将正样本错误地划为负样本，false positive错误正好相反，是将负样本误分类为正样本。正负样本通过使用扫描窗对图像进行逐行扫描，初始化扫描过程中，产生的样本都归为未标签样本，这就需要使用分类器进行标识分为正样本和负样本。P专家的目的是利用数据在时间上的结构性,寻找出跟踪目标出现的新的外观变化；N专家的作用是利用数据在空间上的结构性找到检测器应该被忽视的目标对象周围的背景部分。

2 基于Camshift算法与多线程改进的TLD框架 2.1 Camshift算法原理及简单优化

Camshift算法通过将图像颜色直方图转化为色彩概率的反向投影概率分布，找到最近的密度梯度峰值，通过计算零阶矩、一阶矩和二阶矩找到目标对象的质心位置。当初始选择框区域包含目标对象之外的一些像素(如背景)，在计算反向投影直方图中，二维概率密度分布图像将受到它们的频率影响。为了分配给更靠近区域中心的像素更高的权重，使用加权直方图计算目标对象直方图分布(如式(6)所示)，可以避免外部像素的错误影响。

式中k(x)是一个单调递减的核函数，该函数分配给靠近标准化后搜索框中心的像素更高的权重，最简单的用于生成背景权重的直方图的核函数为

2.2 TLD跟踪器和检测器的优化

在原TLD算法框架中，跟踪器模块采用基于金字塔L-K光流跟踪算法跟踪目标，L-K光流法针对稀疏光流^[8]，在处理视频过程中需要从图像金字塔最高层开始计算光流，然后向塔底迭代计算，工作量较大；而Camshfit算法针对视频进行跟踪，算法效率高，并可以自适应改变跟踪窗口的尺寸，从而优化了跟踪器跟踪速度。然而Camshift复杂度低，其最大缺点就是当背景颜色和目标颜色相近时，容易出现跟踪失败，根据1.3节的介绍，可以利用TLD算法中学习模块P-expert从空间轨迹上对目标进一步修正，减小背景颜色对目标跟踪影响。

TLD检测器中对图像使用滑动窗法扫描搜索，然后使用分类器判断目标是否存在。当扫描分辨率为320×240图片,待扫描子窗口数量达到50 000个。为了进一步减少待检测子窗口数量，提出扫描图像之后，采用背景差分方法^[9]识别目标存在区域，为后面的分类器减少待判断的子窗口数量，因此提升了TLD检测器模块的运行效率，改进后的检测器流程如图 4所示。

2.3 基于多线程编程的多目标跟踪

原TLD算法框架只针对单目标长时间跟踪，而通过引入多线程编程机制可以实现对多个目标实现高效跟踪。多线程技术主要是解决处理器单元内多个线程执行的问题，可以减少处理器单元的闲置时间，增加处理的吞吐能力；然而多线程机制下，线程的创建和销毁时间远大于线程执行任务的时间，所以引入线程池技术可以有效缩短或者调整线程创建和销毁的时间，提高线程执行效率^[10]。在以上2种机制下，将改进的TLD算法框架嵌入到每一个线程中，对每个目标执行学习、检测、跟踪，实现对多个运动目标的稳定跟踪，算法流程如图 5所示。

假如当N个目标需要跟踪时，建立N个线程，每个线程处理运行一个TLD框架，即TLD框架中的3个模块即跟踪器、检测器和学习模块均被复制N份，这样跟踪多目标的方式使得整体算法运算量增大，各个目标之间算法会出现计算冗余^[2]，所以将共同的计算函数和内存数据可以集中到同一内存区域，可以实现计算过程和数据的共享使用，这样既可以减少多线程过程中过多的运算量，还可以节省大量的内存空间，提高算法运行速度。

3 实验测试及分析 3.1 实验测试

再次列举了基于Camshift算法优化的TLD框架与原TLD算法测试视频数据信息及测试结果。实验测试硬件环境CPU Inter(R) Core(TM)2 Duo CPU T6500 2.10 GHz，内存3 G；软件环境为ubuntu 14.04 kylin操作系统。

实验数据主要来自TLD测试数据集，包含了单个或多个跟踪目标、光照变化、目标的部分遮挡与全遮挡、目标消失，形状变化，摄像头晃动等各种复杂场景。视频序列David中单目标跟踪下存在较多的姿态变化，Volkswagen中存在摄像头的抖动和目标半遮挡的情况；Carchase中多目标跟踪下出现较多的半遮挡和全遮挡的情况，Pedestrain中存在多目标跟踪时摄像头晃动情形。测试视频描述及截屏如图 6所示，相关信息如表 1所示。

3.2 实验结果及分析

设置改进TLD框架中的Camshift跟踪模块的收敛次数为15，目标中心误差为2个像素，设置检测器模块中最近邻分类器的相对相似度阈值为0.6。如果检测到的目标和真实目标的边界框大小的比值即重叠度大于50%，认为该检测是正确的跟踪，据此来判断准确跟踪的帧数。算法实时性评估依据跟踪视频帧序列的平均帧率来表示。图 7为本文跟踪算法结果。表 2表示原TLD算法与改进后的TLD算法框架在单目标和多目标的跟踪算法准确率对比，表 3表示2个算法在各自测试视频相应的平均帧率大小对比。

最后测试算法对于摄像头采集视频中多个人脸目标的跟踪性能。测试结果表明在多个人脸出现交叠、形态变化、长时间消失等复杂状态下均实现了准确跟踪，实时性达到11 f/s左右，实时跟踪效果良好。测试效果如图 8所示。

4 结论

本文主要做出了以下改进：1)提出了基于改进Camshift算法优化的TLD算法框架，优化了TLD算法框架中的跟踪器模块；2)利用多线程机制改进TLD算法使其应用于多目标的跟踪。经过多次试验数据测试得出，经过Camshift和多线程机制改进的TLD算法框架在对于单目标和多目标跟踪时的实时性得到较大提升，同时跟踪准确性保持稳定。该优化算法可以进一步移植到相关嵌入式平台执行多目标跟踪任务。