改进的核相关滤波跟踪算法

孙 健，向 伟，谭舒昆，刘云鹏

SUN Jian1，2,XIANG Wei1,TAN Shukun1,2,LIU Yunpeng1

1.中国科学院 沈阳自动化研究所，沈阳 110016

2.中国科学院大学，北京 100049

1.Shenyang Institute ofAutomation,ChineseAcademy of Sciences,Shenyang 110016,China

2.University of ChineseAcademy of Sciences,Beijing 100049,China

1 引言

目标跟踪是机器视觉领域一项重要的课题，并且有广泛的应用场景，如机器人、视频监控、智能交通等[1-4]。近年来，虽然随着机器学习的引入，目标跟踪技术有了明显提升，但是依旧面临很多挑战，如尺度变化、光照变化、目标形变、目标遮挡等[5]。

基于检测的目标跟踪算法表现出良好的跟踪性能，是近年来的主流跟踪算法。这些算法通常将跟踪过程看成一个分类问题，通过已有的视频帧离线或在线训练分类器，再用训练好的分类器来判别下一帧目标位置。如核结构化输出（Structured output tracking with kernel，Struck）[6]跟踪算法，跟踪-学习-检测（Tracking-Learning-Detection，TLD）[7]跟踪算法，多样例学习（Multiple Instance Learning，MIL）[8]跟踪算法等。这些算法的采样方式一般为稀疏采样，在跟踪精度及计算效率上都有明显不足。相关滤波器在目标检测和识别中已有广泛的应用，Bolme等[9]提出的一种最小平方误差和输出（Minimum Output Sum of Squared Error，MOSSE）跟踪算法，首次将其应用到目标跟踪领域并取得了很好效果。随后Henriques等[10]提出基于核循环结构检测跟踪（Circulant Structure of tracking-by-detection with kernel，CSK）跟踪算法，创新地采用循环结构编码密集采样并用核方法训练正则化最小二乘（RLS）非线性分类器。之后又在核相关滤波（Kernelized Correlation Filter，KCF）[11]跟踪算法中使用梯度方向直方图（Histogram of Oriented Gradients，HOG）[12]特征对CSK进行改进。Danelljan等[13]提出的区分尺度空间（Discriminative Scale Space Tracker，DSST）跟踪算法则是在MOSSE跟踪算法的基础上解决了跟踪过程中目标尺度变化问题。

因此，本文首先在KCF跟踪算法的基础上借鉴DSST跟踪算法来解决跟踪过程中目标尺度变化问题，之后针对算法不能有效处理长时间跟踪中遇到的目标大面积遮挡或丢失问题提出了一种再检测方法，解决了目标跟踪中丢失重捕问题，从而进一步提高了跟踪算法的精确度与鲁棒性。

2 KCF跟踪算法改进

KCF跟踪算法利用循环采样来训练分类器，这种密集采样的方式明显优于稀疏采样的跟踪算法，又因为将运算转换到频域进行，跟踪速度也有了提升。但在跟踪过程中跟踪框无法随着目标尺度自适应变化，在目标丢失后也无法捕获目标重新进行跟踪，从而导致跟踪性能降低。

2.1 判别式相关滤波器

KCF跟踪算法训练位移滤波器的主要思想是学习一个判别式相关滤波器来对新一帧图像目标定位。具体做法是从目标及其背景提取出一组灰度图像块x1，x2…，xt作为训练样本，其中每一个图像块都会对应一个目标输出g1，g2…，gt，一般而言gj预期输出函数为高斯函数，其峰值位于xj中心。本文在位移滤波器的基础上增加了一个尺度滤波器，尺度滤波器也是一个判别式相关滤波器，最大的不同点是通过建立目标尺度金字塔来提取训练样本。两个滤波器相互独立，选用了不同的特征用来训练。算法中使用脊回归求得最优相关滤波器hj：

根据Parseval定理，将运算转换到频域：

其中 fj，gj和ht的大小均为 M×N，为复共轭矩阵。λ≥0是正则化项，可以用来防止过拟合。于是可以得到：

2.2 密集采样

不难看出式（3）的计算量很大，因此也很大程度上影响了跟踪算法的实时性。改进方法是对目标区域进行循环采样即密集采样，这样不仅可以提高计算效率而且还可以提高跟踪精度。区别于其他算法的稀疏采样方式，相关滤波并不严格区分正负样本，算法使用变换矩阵P来对目标图像块x进行循环移位。对于一维图像，变换矩阵可以为：

变换后的图像则构成循环矩阵：

循环矩阵有一个很好的特性，即无论x是什么形式，其循环矩阵X 都可表示成 X=Fdiag(xˆ)FH，代入式（3）可大大简化计算。

2.3 滤波器响应

为了进一步简化计算，本文对式（3）的分子Aj和分母Bj分别进行更新：

可以得到鲁棒的近似结果，其中θ为学习率。因此，对于新一帧输入图像z，目标位置可以求解最大相关滤波器响应y得到：

2.4 再检测

之前提到过KCF跟踪算法在各项跟踪性能指标均有很好表现，但是对目标丢失的场景无法实现有效跟踪。那是因为KCF跟踪算法采样过程中并不明确区分正负样本，训练的分类器只是取置信值最大的点作为目标，所以，当目标被完全遮挡时采样全为负样本，导致训练的分类器失去了判别目标与背景的能力，从而使得跟踪失败。针对这一问题，本文在KCF算法的基础上，增加了一个支持向量机训练分类器，当目标丢失时可以进行再检测，从而实现跟踪目标的丢失重捕。

支持向量机是定义在特征空间上间隔最大化的二分类模型[14-15]。其基本思想是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。在机器视觉领域SVM常用来做识别及分类，训练时通常从训练图像提取特征，然后用特征向量来表示图像。当使用像素作为特征时，图像按字典顺序扫描以形成特征向量。给定N 列向量 xi∈Rd和类标签SVM分类器将找到一个超平面满足下式：

其中，上标T表示转置，w和b表示超平面（w表示超平面的法线，b为偏置），εi为松弛变量，C＞0称为惩罚参数，一般由应用问题决定，表示对误分类的惩罚程度。

在改进算法中，使用了两个阈值threshold1和threshold2。threshold1用来判断目标的遮挡程度，实验中取值为0.4，当置信值大于threshold1时，表示此帧目标未受到大面积遮挡，则这一帧图像可以用来训练SVM分类器即再检测分类器。Threshold2则用来判断是否需要进行再检测，实验中取值为0.2，当分类器响应小于threshold2时，表示检测到目标的置信度不高，需要使用SVM分类器来进行再检测。

3 改进算法流程

综合前面的算法改进分析，在KCF跟踪算法的基础上，本文构造出改进的核相关滤波跟踪算法流程如下所示：

基于SVM相关滤波目标跟踪算法

1：参数初始化；

2：读取第i帧图片序列：

3：if i＞1：

8： 使用SVM分类器检测目标。

9：根据式（6）和式（7）更新移位滤波器及尺度滤波器。

11：根据式（9）训练SVM分类器。

12：返回第2步开始下一帧跟踪。

4 实验与分析

为了验证本文算法的有效性，从文献[5]中选用了10组视频序列进行测试，这些视频序列包含光照变化、尺度变化、目标遮挡、目标丢失、旋转等问题（如表1所示）。在对比实验中，本文选取了多个优秀跟踪算法进行比较，包括Struck、TLD、MIL、KCF、DSST等。同时，将增加尺度滤波器的KCF算法（用KCF+S表示）也加入了对比实验。实验时利用作者论文中公布的代码在同一实验环境进行。

表1 视频序列

4.1 实验环境及评价指标

考虑到运行效率，本文程序采用MATLAB与C语言混编，实验软件平台为Matlab R2014b，并且配置了Opencv3.0及VLFeat两个库文件。运行环境配置为Intel Core i7-4790 CPU，主频3.6 GHz，4 GB内存。为了定量分析算法性能，实验中使用了文献[5]中的3个评价指标：中心位置误差（Center Location Error，CLE）、距离精度（Distance Precision，DP）、重叠精度（Overlap Precision，OP）。CLE是跟踪结果目标中心与人工标注的目标中心的欧氏距离，其值越小越好并以像素为单位。DP是CLE小于阈值（一般为20个像素）的帧数占视频序列帧数的百分比。OP则是跟踪得分：score=大于某一阈值（本文取0.5）的帧数占总跟踪序列长度的百分比，其中，Bt表示第t帧跟踪框，Bg表示真实标注跟踪框，⋂表示重叠区域，⋃表示总覆盖区域。

4.2 实验结果及分析

实验中，本文算法与其他优秀跟踪算法对表1中的视频序列进行测试，得到CLE、DP、OP、FPS取平均值，结果如表2所示。表中将最优的结果进行加粗处理，次优的则用下划线标出。

表2 测试结果

从表2可以看出，本文算法相对其他算法在3个评价指标上均是最优。对比KCF跟踪算法，CLE平均减少了11.1 pixel，DP平均增加了7.8%，OP平均增加了9.7%，改进效果明显。但是由于引入了尺度滤波器与再检测分类器，势必会增加运算复杂度，导致跟踪速度变慢，但仍然能保证实时跟踪。实验还绘制了6组视频的跟踪精度曲线（DP曲线），如图1所示。

图1 DP曲线

从表2的测试结果还可以看出，KCF跟踪算法的CLE、DP两个评价指标要略优于KCF+S跟踪算法，说明KCF跟踪算法的跟踪精度较好。另一方面，KCF跟踪算法的OP评价指标要略差于KCF+S跟踪算法，不仅说明KCF+S跟踪算法跟踪框和标注框重叠率高，也说明KCF+S跟踪算法对跟踪中目标尺度变化确有改进作用。

本文方法是在KCF跟踪算法的基础上进行尺度变化及目标丢失问题的解决。由于尺度变化的改进是参考DSST跟踪算法。因此，从图1的DP曲线可以看到，对于dog1、fish、dudek三组主要挑战为尺度变化、光照变化、部分遮挡等的视频序列，本文算法与DSST跟踪算法表现相近。然而，对于coke、lemming、tiger2这三组主要挑战为目标丢失的视频，本文方法的DP曲线明显优于DSST跟踪算法。这也说明本文方法不仅继承了原有算法的优点，而且进行了有效而显著的改进。

为了便于更加直观的对比，图2列出了部分帧的跟踪结果。在实验时可以观察到coke视频的第254～266帧，lemming视频的第337～362帧以及suv视频的第677～686帧均出现目标完全遮挡的情况。不难看出，本文方法在目标丢失并重新出现后能够迅速找到目标位置进行跟踪，因此在这些视频序列的表现要优于其他跟踪算法。由此说明本文算法具有再检测功能，并且能够改善算法跟踪精度。

图2 几种算法跟踪结果

5 结束语

本文在KCF跟踪算法的基础上，提出了一种改进的核相关滤波目标跟踪算法。通过在原有算法的基础上，增加了尺度滤波器及再检测分类器，解决了KCF跟踪算法尺度及目标丢失问题。在与其他几种优秀跟踪算法的比较实验表明：本文方法在各项评价指标中表现优异，并且对光照变化、尺度变化、旋转等问题有一定鲁棒性，具有一定研究及应用价值。下一步工作将优化各个分类器性能、简化运算，进一步提高算法跟踪性能。

参考文献：

[1]Chen Z，Hong Z，Tao D.An experimental survey on correlation filter-based tracking[J].arXiv preprint arXiv：1509.05520，2015.

[2]Smeulders A W M，Chu D M，Cucchiara R，et al.Visual tracking：An experimental survey[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2014，36（7）：1442-1468.

[3]Yilmaz A，Javed O，Shah M.Object tracking：A survey[J].ACM Computing Surveys，2006，38（4）：81-93.

[4]牛长锋，陈登峰，刘玉树.基于SIFT特征和粒子滤波的目标跟踪方法[J].机器人，2010，32（2）：241-247.

[5]Wu Y，Lim J，Yang M H.Object tracking benchmark[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2015，37（9）：1834-1848.

[6]Hare S，Saffari A，Torr P H S.Struck：Structured output tracking with kernels[C]//2011 IEEE International Conference on Computer Vision（ICCV），2011：263-270.

[7]Kalal Z，Mikolajczyk K，Matas J.Tracking-learning-detection[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34（7）：1409-1422.

[8]Babenko B，Yang M H，Belongie S.Robust object tracking with online multiple instance learning[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，33（8）：1619-1632.

[9]Bolme D S，Beveridge J R，Draper B A，et al.Visual object tracking using adaptive correlation filters[C]//2010 IEEE Conference on Computer Vision and Pattern Recognition（CVPR 2010），2010：2544-2550.

[10]Henriques J F，Caseiro R，Martins P，et al.Exploiting the circulant structure of tracking-by-detection with kernels[C]//European Conference on Computer Vision（ECCV 2012）.Berlin Heidelberg：Springer，2012：702-715.

[11]Henriques J F，Caseiro R，Martins P，et al.High-speed tracking with kernelized correlation filters[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2015，37（3）：583-596.

[12]Dalal N，Triggs B.Histograms of oriented gradients for human detection[C]//2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition（CVPR 2005），2005：886-893.

[13]Danelljan M，Häger G，Khan F，et al.Accurate scale estimation for robust visual tracking[C]//Proceedings of British Machine Vision Conference，Nottingham，September 1-5，2014.

[14]Rodriguez A，Boddeti V N，Kumar B V，et al.Maximum margin correlation filter：A new approach for localization and classification.[J].IEEE Transactions on Image Processing，2013，22（2）：631-643.

[15]Rodriguezperez A F.Maximum margin correlation filters[D].Carnegie Mellon University，2012.