基于异常值检测的KCF目标丢失预警方法研究

刘延飞，何燕辉，张 薇，崔智高

火箭军工程大学，西安 710025

1 引言

视觉目标跟踪是计算机视觉领域中最具挑战的课题之一，广泛应用于视频监控、人机交互、智能汽车、医疗图像等领域[1-2]。视觉目标跟踪问题研究自20世纪80年代开始到现在经历30多年发展[2]，取得了骄人的成就，涌现出了大量的跟踪算法。尽管如此，依然不存在一种能够适应任意自然场景的跟踪算法，光照变化、目标形变、遮挡、出视野等问题仍旧是影响跟踪算法性能的主要因素，也是跟踪领域需要突破的难点问题。

视觉目标跟踪分类方法有多种，目前比较流行、公认度比较高的分类方法是根据目标外观模型的表达策略，将跟踪方法分为生成类方法和判别类方法。

生成类方法[3-8]就是在当前帧对目标区域建模，在下一帧寻找与模型最相似的区域就是预测目标的位置，比较经典的有卡尔曼滤波、粒子滤波、Mean-Shift。

判别类方法[9-19]则是将跟踪问题看作目标和背景的分类问题，此类方法同时提取目标和背景信息，增强了模板的判别力。比较经典的算法有基于核化的结构化输出（Struck）算法[20]、跟踪-学习-检测（Tracking-Learning-Detection，TLD）算法[21]等。Struck是2012年之前性能最好的算法之一；TLD将检测和学习融入到跟踪的整个过程，使得其具备长期跟踪的能力，由于每帧都需要进行检测和学习，耗时比较大，极大地影响了其跟踪的速度，尽管在实时性方面勉强能实现，但其引入学习和检测机制的思想对之后的一些算法改进提供了有益借鉴。

判别类方法的最新发展方向就是相关滤波类方法。相关滤波类方法最主要的特点是算法复杂度低，运算速度快，满足实时要求。最早将相关滤波器应用到跟踪领域的是Bolme等人，他们提出一种最小输出平方误差和（Minimum Output Sum of Squared Error，MOSSE）相关滤波器跟踪方法[22]，该算法只采用一个目标区域样本图像来训练目标外观模型，通过离散傅里叶变换将目标模型与候选区域之间的相似度计算转换到频域，显著地提升了跟踪算法的运行速度，跟踪速度达到了615 frame/s，但跟踪的精确度和成功率还有待进一步提高。Henriques等[23]提出了循环结构的检测跟踪（CSK）算法，该算法通过对基准训练样本进行循环移位的方式构造大量的训练样本，用于训练分类器，同时，利用同样的方式构造大量的待测样本，用于目标检测过程。利用循环矩阵可以傅氏对角化的性质将分类器训练和目标检测的计算转换到频域实现了快速计算。Henriques等[24]在CSK的基础上提出核相关滤波器（Kernel Correlation Filter）跟踪算法，使用方向梯度直方图（Histogram of Oriented Gradient，HOG）[25]特征代替原来的灰度值特征，将相关滤波器由单通道扩展到多通道，提升了跟踪性能。

尽管KCF算法跟踪性能得到了提升，但当目标受尺度变化、严重遮挡、相似目标干扰和出视野等因素影响时，KCF算法仍会出现目标丢失现象。一旦目标丢失，跟踪器本身无法察觉，不具有目标丢失检测的能力，这是KCF跟踪算法固有的缺陷。目前不少学者针对这一问题提出了改进的措施，主要是对响应峰值进行检测，用检测的结果判断目标是否丢失，检测方法有求取局部极小值法[26]、设定阈值法[27]等。由于峰值的相对杂乱性，检测方法都面临两个问题：一是计算的时间和空间复杂度；二是很难同时满足高检测成功率和低误检率要求。同时已有的检测方法缺乏性能分析与评估。本文在KCF的基础上，引入异常值检测方法作为目标丢失检测机制，对每帧的峰值进行检测，发现异常峰值，则判定目标丢失，解决了KCF跟踪器在跟踪过程中目标丢失不能察觉的问题，同时还引入了检测成功率和误检率作为本文方法的性能评估标准。

2 KCF跟踪算法

KCF算法的主要思想是利用循环移位的方式构造大量的训练样本和待测样本。利用训练样本训练一个核相关滤波分类器，然后通过分类器计算待测样本的响应值，选取响应值最大的待测样本为新的跟踪目标，同时利用循环矩阵可以傅氏对角化的性质，大大降低了分类器训练和检测过程中的运算量。

2.1 采集样本

KCF跟踪算法利用循环矩阵的思想，在目标区域设定的采样窗口进行循环移位，产生大量的正负样本，用以训练分类器和检测目标。设为基准样本，利用置换矩阵P对基准样本x进行循环移位，移位一次得到的样本记为，所以经过n次移位能得到n个样本，样本集合{Pux|u=0,1,…,n-1}，其中置换矩阵：

将得到的所有样本按循环矩阵的定义组合成循环矩阵 X ，如式（2）：

式（2）中，x表示基准样本，即为矩阵X的第一行。

因为循环矩阵都能够在傅氏空间中使用离散傅里叶矩阵进行对角化，所以循环矩阵X可以化简为：

其中，F为离散傅里叶变换矩阵；xˆ为向量x=[x1,x2,…,xn]T的离散傅里叶变换，也就是循环矩阵X的第一行的离散傅里叶变换；H表示矩阵共轭转置。KCF跟踪算法正是利用了循环矩阵能够傅氏对角化避免了矩阵求逆，从而大大降低了运算量。

2.2 训练分类器

对上式求导，并令导函数为0，可求得：

其中，φ(X)φ(X)T为核矩阵，用 K表示，那么就有 K=φ(X)φ(X)T。这里定义核函数 κ(x,x′)=φ(x)φ(x′)T，因此核矩阵K中的各个元素表示为：

这里以Kij为元素的核矩阵K是循环矩阵，在文献[24]的定理1中有说明，这里不做证明。因此有K=C(kxx)，其中kxx为K矩阵的第一行，将K矩阵傅氏对角化为 K=F diag(kˆxx)FH，化简式（5）得到：

2.3 目标检测

分类器训练完成后，在下一帧图像的预测框内采集基准待测样本z，由基准样本经循环移位产生大量待测样本，样本集为{zj=pjz|0,1,…,n-1}，然后计算每个待测样本的响应值，响应值最大的样本所对应的位置即为目标所在的位置。计算响应的公式如下：

其中，κ(z,xi)为核函数。令Kz为训练样本与待测样本之间的核空间的核矩阵，由文献[24]中定理1可知Kz是循环矩阵，记Kz=C(kxz)。因此式（8）写成矩阵形式为：

因为Kz是循环矩阵，根据循环矩阵的性质，可将其傅氏对角化：

其中，kxz是 Kz矩阵的第一行。将式（10）代入式（9）化简后得到：

3 目标丢失预警机制

传统的KCF算法在跟踪目标的时候，对于目标丢失的现象算法本身无法检测与判断，目标一旦丢失，跟踪器依然会将背景信息作为目标继续跟踪。之所以会出现这种情况，原因就在于KCF跟踪算法快速检测过程中总是将待测样本中响应值最大的作为目标，假设目标丢失了，不在采样窗口内或者在采样窗口内但被遮挡了，这种情况下所有待测样本中依然会有一个最大响应值，即峰值，而显然这个峰值所对应的位置并非真实目标所在的位置。

下面用一段视频序列做实验，采用OTB-2013[28]视频序列集中的一段，序列名称Jogging。视频中目标由于遮挡导致跟踪失败，目标在第72帧后丢失。

图1是视频序列Jogging部分跟踪结果及相应帧的待测样本响应值分布，从图中可以得出以下信息：

（1）目标跟踪状况良好时，峰值较大，例如第55帧，该帧的响应值分布图中只有一个驼峰，而且非常尖锐，峰值为0.453 1。

（2）由于遮挡等因素的影响导致目标跟踪状况较差时，峰值较小，例如第68帧和第72帧，峰值分别是0.310 9、0.160 1。

（3）在目标由于遮挡等因素影响导致目标丢失的过程中，峰值会急剧下降，例如从第68帧到第72帧的峰值变化可以看出。

图1 视频序列部分跟踪结果及响应值分布图

（4）目标丢失后，跟踪器会错将背景信息作为目标继续进行跟踪，峰值会逐渐变大，例如第84帧，此时峰值是0.429 8。

由上述实验可知目标丢失与响应峰值的变化有关联，因此本文想利用每帧响应峰值的变化情况来评判目标是否丢失。图2是利用视频序列Jogging得到的跟踪响应峰值序列图，横坐标表示帧数，纵坐标表示每帧对应的峰值。从图中可以更直观地看出，在目标发生跟丢的第72帧附近峰值出现了急剧下降，之后峰值逐渐升高（峰值之所以升高是跟踪器将背景信息作为目标继续进行跟踪的原因导致的）。因此可以将此处附近急剧下降的峰值视为异常值，利用异常值检测原理对跟踪过程中每帧的响应峰值进行检测，如若发现峰值异常，则判断目标丢失或即将丢失。

图2 峰值序列图

具体的检测方法如下：

令Vpre为当前帧的响应峰值，集合{Vi|i=1,2,…,n}表示当前帧之前一段时期内的峰值集合。

其中，u表示当前帧之前一段时期内峰值的平均值；σ表示其标准差。如果当前帧的峰值距离均值u超过了λσ，那么这个值就可以被简单地标记为一个异常值，此时可以判断目标已丢失或即将丢失。

4 实验与分析

为了验证本文目标丢失检测方法的有效性，本文选取OTB-2013[28]中20段视频序列进行测试。视频序列参数如表1所示。实验平台为Matlab R2012a，KCF目标跟踪及跟踪过程中得到的峰值数据的处理均使用Matlab R2012a平台，实验所用电脑配置：CPU是Intel Core i5，主频2.0 GHz，内存4 GB。实验中，KCF算法参数保持不变，式（12）中n取50。

4.1 评估标准

为了能够更加科学准确地评估本文目标丢失检测方法的有效性，本文采用了检测成功率和误检率作为评估标准。检测成功率就是检测到目标丢失的次数占实际目标丢失次数的百分比；所谓误检就是检测算法错误地判断目标丢失，而实际上目标并没有丢失，误检率就是误检的次数占视频总帧数的百分比。检测到目标丢失的成功率当然是最重要的评估标准，但是如果单方面追求高成功率，而将检测条件设置过于苛刻，势必会导致误检率升高；相反，单方面追求低误检率，而将检测条件设置过于宽泛，就会导致成功率降低。因此性能好的检测方法既要求高成功率，又要确保低误检率。

表1 测试视频参数

4.2 目标丢失与峰值变化相关性验证实验

为了验证目标丢失与峰值变化的相关性具有普遍性，本文选取表1中的6段视频进行了实验，视频序列名称分别是Box、David3、Human4、Human6、Biker、Lemming。在KCF跟踪过程中，6段视频分别在第470帧、第133帧、第337帧、第360帧、第72帧、第970帧出现目标丢失。图3是6段视频响应峰值序列图，红色圆圈标记处为目标丢失处，从图中可以看出目标丢失处附近峰值都出现了急剧下降现象。实验进一步验证了目标丢失与峰值变化的相关性。

4.3 目标丢失检测算法性能测试

检测条件设置过于苛刻，会导致误检率升高，而设置过于宽泛，又会导致检测成功率下降。由式（12）可知：当λ取值越大，检测条件就越宽泛，反之则越苛刻，因此，分别对λ=3，λ=3.5，λ=4时进行实验。

将KCF跟踪算法程序在表1中20段视频序列上运行，得到20组响应峰值序列，再用Matlab分别对这20组峰值序列进行处理，得到如图4～图6所示的结果。图4～图6分别是λ=3，λ=3.5，λ=4时部分视频序列的检测结果。图中黑色曲线表示峰值，红色曲线表示峰值的平均值(u)，绿色曲线表示均值减去λ倍的标准差(u-λσ)，红色矩形标记处表示出现误检的帧，红色圆圈标记处表示实际目标丢失的处。从图中可以看出，总体上黑色曲线在绿色曲线之上，同时也出现了这两条曲线相交的情况，相交处的下一帧峰值即满足式（12），根据目标丢失检测方法原理，此时可以判定该帧目标丢失或即将丢失。

图3 6段视频集峰值序列图

图4 λ=3时部分视频序列目标丢失检测结果

根据实际的跟踪结果，20段测试视频共出现10次目标跟丢的情况，分别发生在视频Biker的第72帧、视频Box的第470帧、视频Coke的第40帧、视频David3的第133帧、视频Girl2的第898帧、视频Human4的第337帧、视频Human6的第360帧、视频Jogging的第72帧、视频Lemming的第970帧、视频Panda的第400帧。如果上述帧的峰值满足式（12），则表示目标丢失预警成功；反之则表示预警失败。如果除上述帧外其他帧的峰值满足式（12），则表示误检。

通过实验对比发现，λ取值越大，越容易发生预警失败，例如在视频Lemming的第970帧处，当λ取3和3.5时，目标丢失预警成功，取值4时，预警失败；λ取值越小，越容易发生误检，例如视频David3和Boy，λ=3时误检次数分别是3、3，λ=3.5时误检次数分别是2、2，λ=4时误检次数分别是0、1；目标出现部分遮挡、尺度变化等情况时，容易发生误检，例如视频FaceOcc1、Lemming和Suv，当λ=4时，仍出现了误检，误检次数分别是3、4、3。

图5 λ=3.5时部分视频序列目标丢失检测结果

图6 λ=4时部分视频序列目标丢失检测结果

表2是实验得出的评估结果，当λ=4时，目标丢失预警效果最好，成功率最高，达到100%，误检率比较低，仅为0.202%。

表2 评估结果

根据实验结果与分析情况，得出以下结论：

（1）在KCF目标跟踪效果不理想的情况下易发生误检。

（2）在遮挡物多、摄像机抖动频繁、尺度变化频繁且明显等情况下，可以适当地调高λ的取值，从而放宽检测条件，降低误检率。

5 结束语

针对目标丢失后KCF算法本身不能察觉，并且跟踪器会将背景信息作为目标继续进行跟踪的问题，本文在KCF的基础上，引入异常值检测方法作为目标丢失预警机制，检测方法时间空间复杂度低，不影响KCF目标跟踪的实时性。实验结果表明，本文方法在λ=3.5的情况下，能够正确预警目标丢失，成功率达到100%，误检率仅为0.202%，具有较高的可靠性和鲁棒性。实验中仅使用了网络上标准的测试视频，方法在实际场景中的应用效果还需要进一步验证。下一步需要结合目标丢失重检测定位机制，检验本文方法的应用效果。