基于KCF框架的长时间视频目标跟踪算法

梁 硕，陈金勇，吴金亮，王长力

(1.中国电子科技集团公司第五十四研究所，河北 石家庄050081；2.中国人民解放军91635部队，北京102249)

基于KCF框架的长时间视频目标跟踪算法

梁 硕1，陈金勇1，吴金亮1，王长力2

(1.中国电子科技集团公司第五十四研究所，河北 石家庄050081；2.中国人民解放军91635部队，北京102249)

针对视频目标跟踪中因遮挡产生的目标丢失后无法重新自动锁定目标的问题，提出了一种能够对视频目标进行长时间跟踪的算法。基于KCF(Kernelized Correlation Filters)算法的框架，增加筛选模块，通过三重分类器的筛选，对目标重新自动锁定。实验结果表明，提出的算法能够实现对目标的稳定跟踪，并且在目标跟丢后自动重新锁定并继续跟踪，实现对目标长时间跟踪的目的。

KCF；遮挡；视频目标跟踪；长时间跟踪

0 引言

随着机器学习的不断发展，越来越多的学者提出了视频目标跟踪算法，视频目标跟踪的性能得到了极大地改善。但是，由于视频中噪声、光照变化以及遮挡等问题的存在，当前的算法只能满足于特定的约束条件，并不能够在任何条件下都满足实时性和鲁棒性的要求。其中，尤其是遮挡问题的存在，对目标的跟踪变得尤其困难。在现实世界中，遮挡是普遍存在的。目标可能被静止的物体遮挡，也可能被运动的物体遮挡；可能被遮挡一部分，也可能被全部遮挡。无论哪种情况，目标都会因遮挡而改变其外观，影响跟踪的准确性。而当遮挡消失的时候，如何能够继续对正确的目标进行跟踪，也是当前亟待解决的一个问题。

1 视频目标跟踪基本框架

视频目标跟踪是根据目标的表观特征信息和目标运动模型，在视频中估计目标的位置。因此，视频目标跟踪一般包含2个方面的内容：目标表观特征描述和目标跟踪算法。

视频中目标具有细节丰富的表观信息，需要通过相应的目标表观特征描述方法将其中相对稳定的统计特性或某些不变特性提取出来，以此对目标和背景进行区分。原始图像特征直接将目标区域的原始图像信息或经简单处理得到的底层图像特征作为对目标的描述。通常选取的特征有灰度[2]、颜色[3]及梯度[4]等。该类特征提取简单快速，但对目标特征的挖掘程度低，适应力较差。直方图特征[5]，通过统计目标区域内某种特征在每个像素位置上出现的频次，并进行归一化，构成该目标区域对应特征的概率密度函数。直方图有效描述了特征的统计特性，对于非刚体形变具有较好的鲁棒性，但对于光照变化和背景杂波有一定欠缺。稀疏表示理论[6]，通过超完备字典将目标映射为稀疏向量，作为表观描述特征，计算量小，但有一定的随机性，不能保证最优。

为了估计目标的位置和范围，需要选择合适的跟踪算法对目标进行跟踪。文献[7-9]提出贝叶斯估计理论，在所构建的状态空间模型基础上，依据目标的先验运动模型和后验观测，通过预测和更新2个步骤实现先验与后验信息的有效融合，进而得到目标的估计状态。文献[10-12]提出均值漂移理论，通过分别构建权重与核函数对样本点的特征和空间位置赋予不同的重要性，进而计算偏移均值向量，并移动到该点重新依据样本点的重要性计算新的偏移均值向量，由此迭代对目标位置进行估计。文献[13-15]采用基于机器学习的方法将目标和背景都作为样本进行训练，通过分类器对目标和背景进行区分，由此获得目标的位置。

2 KCF跟踪算法

KCF跟踪算法通过对岭回归分类器的学习来完成对目标的跟踪，具体流程如图1所示。

图1 KCF算法流程

在训练阶段，利用循环矩阵理论，对视频目标区域进行稠密采样，获取正负样本，提取方向梯度直方图[16](Histogram of Oriented Gradients，HOG)特征，将所有样本对岭回归分类器进行训练。在检测阶段，以视频前一帧目标位置为中心进行稠密采样，将得到的所有样本输入到岭回归分类器，经过岭回归分类器的分类，得到目标的位置。

2.1 稠密采样

KCF跟踪算法为了保证跟踪的准确度，引入循环矩阵理论知识，对视频目标区域采取稠密采样的策略，训练的样本是利用基样本的循环移动进行稠密采样。稠密采样的示意图如图2所示，其中，实线矩形框所包含的图像块为基样本，以x=(x1,x2…xn)表示，虚线矩形框表示在水平方向上，分别向左右2个方向移动采样的结果，移动后分别为x=(x2…xn,x1)和x=(xn,x1…xn-1)。如此在水平方向和垂直方向进行循环，则可以以基样本为中心，对其周围的所有可能图像块进行采样，由此得到完备的样本空间。

2.2 岭回归分类器

对线性岭回归分类器进行训练的目标就是找到一个函数f(x)=wTx，使得损失函数最小，即：

(1)

式中，x=(x1,x2…xn)表示样本，λ为正则项，防止过拟合，w为所求的参数。由式(1)求得一个封闭解的模式：

w=(XTX+λI)-1XTy，

(2)

式中，矩阵X为基样本组合的循环矩阵，y为每个样本的标签值的集合。针对那些不能在原始空间进行分类的样本，则需要引入核函数理论，将低维空间中线性不可分的模式通过核函数映射到高维空间实现线性可分，核函数的格式如下：

k(x,z)=φ(x)φ(z)，

(3)

式中，k(x,z)为核函数，φ(x)和φ(z)为低维空间到高维空间的映射函数。当使用核函数将样本x映射为φ(x)时，所求的分类器f(x)=wTx中的系数w转化为对偶空间中的a。由RepresenterTheorem知，系数w是样本x的线性组合，即：

(4)

(5)

由式(1)和式(5)联合求得：

a=(K+λI)-1y，

(6)

式中，K为映射之后的核矩阵，Ki,j=k(xi,xj)。在检测阶段，输入的视频经过岭回归分类器的分类来确定最终的目标位置信息，将得到的目标位置信息继续训练岭回归分类器，如此反复，完成对目标的跟踪。

3 对KCF算法的改进

KCF跟踪算法因其在准确度和速度方面的综合优势，在视频目标跟踪中获得了优异的表现。尽管如此，其仍不能够有效地抵抗遮挡，在对目标跟丢之后，也无法重新找回目标进行跟踪。针对这2个问题，对KCF算法进行了改进，增加了筛选模块，将筛选模块和跟踪得到的目标位置信息进行融合处理，最终得到准确的目标位置信息，提高准确度。具体的流程如图3所示。

图3 改进后算法流程图

3.1 筛选模块设计

筛选模块设计3个分类器，输入视频帧的样本只有通过这3次分类器的筛选才有可能成为目标区域，具体流程如图4所示。

图4 检测模块流程图

3.1.1 方差筛选

在该阶段,要检测的图像块中如果所有像素点的灰度值方差总体小于被跟踪的目标区域中所有像素点整体方差的50%，这个图像块就被方差分类器丢弃掉。图像块p中的所有像素点的灰度值方差可以用式E(p2)-E2(p)来表示，其中利用积分图来获得E(p)。经过方差筛选之后，大约能过滤掉一半与目标无关的图像块。

3.1.2 级联决策树筛选

在该阶段，由多个串联的决策树对图像块进行筛选。每个决策树i会对输入的图像块中特定位置的像素点进行灰度值检测，将输入图像块的像素点与已知灰度值进行对比，把对比的差值结果来生成一个二进制的编码x，如图5所示。决策树中某个叶子节点的后验概率Pi(y|x)用编码x代表，其中y∈(0,1)。由于决策树是相互独立的，因此要计算出各个决策树的后验概率的平均值，如果计算出的后验概率的均值大于50%，则该图像块通过筛选。

每个决策树是基于初始化时确定的一组像素点对的比较。是在离线的情况下，随机生成像素点对，并且在运行过程中，保持像素点对的稳定性。首先,用高斯卷积对要跟踪的图像进行模糊，从而使图像的鲁棒性有所加强，进而还能对图像噪声有所降低。接着按照预先生成的像素点对，在图像块中比较像素点对的差值，每个像素对比较的差值返回0或1,这些返回值顺序地连接到一起，就完成了对x的编码。

图5 图像块到二进制的转换

该阶段至关重要的条件是各个决策树是相互独立的。所以我们采取以下的措施：首先把图像块进行归一化然后把像素点的位置进行离散化处理，进而在图像块中生成所有可能的垂直和水平方向的像素点对的比较值。这些像素对的比较值，就是图像块的特征值。接下来,把像素对的比较值合并，并将合并后的像素对比较值分发到决策树中。因此,每一个决策树都可以保证是基于一组不同的特性值组合，并且所有的这些特征值结合在一起唯一地表示一个样本。

每一个决策树i维持着一个后验概率y∈(0,1)，总共有2d个后验概率。其中d是像素对比较的个数，通常像素对d取值为13个，因此对于二进制编码x就有可能8 192的编码方式，而对于所有的二进制编码x都用其各自的后验概率所代表。

3.1.3 最近邻筛选

在该阶段,将通过方差筛选和级联决策树筛选的图像块与已有的目标模板进行相似度检测。如果一个图像块与已有模板的相关相似度大于给定的阈值，即Sr(p,M)>θNN。就把这样的图像块分类为目标样本，认为其含有目标。

3.2 融合目标信息

该部分将筛选得到的结果与跟踪算法得到结果进行融合，共同输出目标位置信息。其中，存在以下几种情况：

① 当跟踪算法与筛选算法都能得到目标的位置信息(筛选算法可能得到多个目标位置信息)，并且位置信息比较接近(目标矩形框的重叠率较大)时，则将跟踪算法得到的目标位置信息与筛选算法得到的目标位置信息按10：1的权重进行加权平均，得到一个新的目标位置信息。

② 当跟踪算法与筛选算法得到的目标位置信息相差较大，并且筛选算法得到的结果更加准确时，则由筛选算法的结果为准重新初始化目标信息。

③ 当筛选算法无法得到目标信息时，以跟踪算法的结果为目标最终位置信息。

4 实验结果展示

为了验证算法的有效性，本文算法与KCF算法进行了对比。算法运行环境为Intel Core i7-3770、CPU 3.40 GHz、RAM 3.47 GB的PC机，视频图像尺寸为480*640。对比结果如图6所示，其中颜色较深的矩形框表示改进后的算法结果，颜色较亮的矩形框表示KCF跟踪算法的结果。

(a) 第7帧

(b) 第70帧

(c) 第81帧

(d) 第85帧

由对比结果展示可以看出，本文算法较之KCF算法更加鲁棒。在没有干扰的情况下，本文算法和KCF算法都能够对目标进行准确跟踪(视频第7帧和第70帧)，但当存在遮挡干扰时，KCF算法则无法抵抗遮挡，会出现跟丢目标的现象并且不会重新锁定目标，本文算法能够自动重新锁定目标继续跟踪(第81帧和第85帧)。

5 结束语

在KCF算法的基础之上，提出了一种鲁棒的能够对视频目标进行长时间跟踪的算法。在对视频目标进行跟踪时，筛选算法与KCF跟踪算法共同输出目标的位置信息。经过实验证明，提出的算法能够有效地抵抗物体遮挡的干扰，尤其是在出现跟丢目标的情况下，能够重新初始化目标的准确位置，提高了跟踪的鲁棒性。

[1] Henriques J F,Caseiro R,Martins P,et al.High-Speed Tracking with Kernelized Correlation Filters[J].IEEE Transactiongs on Pattern Analysis And Machine Intelligence,2015,37(3)：583-596.

[2] Hare S,Saffari A,Torr P H S.Struck：Structured Output Tracking with Kernels[C]∥Computer Vision,IEEE International Conference on.IEEE,2011：263-270.

[3] Kwon J,Lee K M.Tracking by Sampling Trackers[C]∥Computer Vision,IEEE International Conference on.IEEE,2011：1195-1202.

[4] Oron S,Bar-Hillel A,Levi D,et al.Locally Orderless Tracking[C]∥IEEE Conference on Computer Vision and Pattern Recognition,2012：1940-1947.

[5] Godec M,Roth P M,Bischof H.Hough-based Tracking of Non-rigid Objects[J].Computer Vision and Image Understanding,2013,117(10)：1245-1256.

[7] 张洪建.基于有限集统计学的多目标跟踪算法研究[D].上海：上海交通大学，2009.

[8] 宋骊平.被动多传感器目标跟踪方法研究[D].西安：西安电子科技大学,2008.

[9] 杨柏胜.被动多传感器探测目标跟踪技术研究[D].西安：西安电子科技大学,2008.

[10] Ning J,Zhang L,Zhang D,et al.Scale and Orientation Adaptive Mean Shift Tracking[J].IET Computer Vision,2012,6(1)：52-61.

[11] Beyan C,Temizel A.Adaptive Mean-shift for Automated Multi Object Tracking[J].IET Computer Vision,2012,6(1)：1-12.

[12] Mazinan A H,Amir-Latifi A.Improvement of Mean Shift Tracking Performance Using a Convex Kernel Function and Extracting Motion Information[J].Computers & Electrical Engineering,2012,38(6)：1595-1615.

[13] Grabner H,Grabner M,Bischof H.Real-Time Tracking via On-line Boosting[C]∥The British Machine Vision Conference,2006：47-56.

[14] Ross D,Lim J,Lin R S,et al.Incremental Learning for Robust Visual Tracking[J].International Journal of Computer Vision,2008,77(1)：125-141.

[15] Babenko B,Yang M H,Belongie S.Visual Tracking with Online Multiple Instance Learning[C]∥IEEE Conference on Computer Vision and Pattern Recognition,2009：983-990.

[16] Dalal N,Triggs B.Histograms of Oriented Gradients for Human Detection[C]∥IEEE Conference on Computer Vision and Pattern Recognition,2005：886-893.

Long-time Video Object Tracking Algorithm Based on KCF Framework

LIANG Shuo1,CHEN Jin-yong1,WU Jin-liang1,WANG Chang-li2

(1.The 54th Research Institute of CETC,Shijiazhuang Hebei 050081,China；2.Unit 91635,PLA,Beijing 102249,China)

To solve the problem of being unable to rediscover the object automatically after the loss of the object because of occlusion,an algorithm which can track the object with a long time is proposed.Based on the KCF algorithmic framework,this algorithm adds filtrating modules and can rediscover the object automatically by the three-time filtration of the classifier.Experiment results show that the proposed algorithm could track the object stably,rediscover the object automatically after the loss of the object,and keep tracking the object,which realizes the purpose of long-time tracking the object.

KCF;occlusion;video object tracking;long-time tracking

10.3969/j.issn.1003-3114.2017.02.14

梁 硕，陈金勇，吴金亮，等.基于KCF框架的长时间视频目标跟踪算法[J].无线电通信技术，2017，43(2)：55-58,82.

2016-11-08

海洋公益性科研专项资助项目(201505002)

梁 硕(1991— )，男，硕士研究生，主要研究方向：视频图像处理。陈金勇(1970—) ，男，研究员，博士生导师，主要研究方向：航天地面应用、电子信息系统。

TP391.4

A

1003-3114(2017)02-55-4