基于三次样条插值和马尔科夫链的KCF目标跟踪方法

技术领域

本发明涉及遮挡目标检测和定位跟踪领域，具体是一种基于三次样条插值和马尔科夫链的KCF目标跟踪方法。

背景技术

目标跟踪是指对视频中的运动目标进行识别，并且在下一帧图像中找到该目标，依次类推完成跟踪。目标跟踪算法根据不同的方法和思想，可以分为生成式(generativemodel)方法和判别式(discriminative model)方法。生成式方法采用特征模型描述目标的外观特征，再最小化跟踪目标与候选目标之间的重构误差来确认目标，生成式方法着重于目标本身的特征提取，忽略目标的背景信息，在目标外观发生剧烈变化或者遮挡时候容易出现目标漂移或者目标丢失；判别式方法将目标跟踪看作是一个二元分类问题，通过训练关于目标和背景的分类器来从候选目标中确定目标，该方法可以显著的区分背景和目标，性能鲁棒，渐渐成为目标跟踪领域主流方法。

KCF(Kernelized Correlation Filters)是一种判别式目标跟踪方法，该方法一般是在跟踪过程中训练一个目标检测器(也叫滤波模板)，使用目标检测器去检测下一帧预测位置是否是目标，然后再使用新检测结果去更新训练集进而更新目标检测器(滤波模板)。其目的是寻找到一个滤波模板，对图像进行相关性计算，常用的方法是用滤波模板对输入图像做滑动卷积操作，得到一个响应图，响应值最大的像素点即为目标的中心点位置。

但是KCF目标跟踪方法本身存在着问题，它无法解决目标跟踪过程中的遮挡问题。当目标遇到遮挡时，当前的滤波模板仍然返回响应图，并且继续按照响应值最大的位置跟踪目标，但是当目标遭遇遮挡后，以上一帧图像中目标框的位置为中心，无法得到准确的响应图，因为在目标被遮挡后其特征就会出现很大的改变，这就会造成目标框的位置出现飘移，而此时KCF依然会按照错误的目标位置继续更新滤波模板，这就很容易造成目标框的持续飘移，再也无法找到正确的目标位置。

以往解决目标遮挡问题，大多从图像本身出发，例如有学者提出对目标框进行分块处理，将大的目标框分解为小的区域，再利用未遮挡的小区域进行相应位置的匹配。虽然取得了一定的效果，但是对于完全遮挡的目标却是无能为力。

因此，本发明给出了一种基于物体运动轨迹和图像本身结合进行预测的方法，利用样条插值对目标轨迹进行模拟，从而对目标的位置进行预测。当遇到遮挡问题时，停止更新KCF滤波模板，而根据遮挡前目标的运动特征，用离线训练的轨迹曲线模拟遮挡后的目标轨迹，并且基于马尔科夫链中当前目标状态只与上一时刻状态有关的假设，认为跟踪过程中当前图像的权重只与上一帧图像的权重有关，提出一种基于三次样条插值和马尔科夫链的KCF目标跟踪方法，从而解决目标跟踪过程中的遮挡问题。

发明内容

本发明就目标跟踪过程中的遮挡问题，提出一种基于三次样条插值和马尔科夫链的KCF目标跟踪方法。该方法的主要思想是，在跟踪目标被遮挡过程中，利用样条插值的方法，对目标轨迹进行模拟，从而对目标的运动位置进行预测。具体思路为，在目标跟踪过程中遇到遮挡问题时，停止更新KCF滤波模板，而根据遮挡前目标的运动特征，用离线训练的轨迹曲线模拟遮挡后的目标运动轨迹。同时为了增加模型的鲁棒性，使用四个不同权重的三次多项式来模拟，并且基于马尔科夫链中当前目标状态只与上一时刻状态有关的假设，认为跟踪过程中当前图像的权重只与上一帧图像的权重有关，从而实现对遮挡目标运动位置的预测跟踪。本发明不局限于图像中的特征，而是着眼于目标的运动轨迹，通过对物体运动轨迹的分析模拟，解决目标跟踪过程中的遮挡问题，具有跟踪准确率高，计算速度快的特点。

KCF算法由最小输出均方误差算法(Minimum Output Sum of Squared Error，MOSSE)发展而来，MOSSE算法是最早提出将相关滤波运用到目标跟踪领域的模型。MOSSE算法与KCF算法相同，都是判别式跟踪算法，即通过判断目标区域与背景区域来判断目标的位置。其目的是寻找到一个滤波模板，对图像进行相关性计算，常用的方法是用滤波模板对输入图像做滑动卷积操作，得到一个响应图，响应值最大的像素点即为目标的中心点位置。

MOSSE的算法流程为，输入一张图像F，F可以是原始图像，也可以是提取的特征图；寻找滤波模板H，通过滤波模板对输入图像进行滑动卷积，然后对卷积后的特征图中元素进行求和，得到输入图像F中对应区域中心位置的响应值，响应值最大的像素点即为目标的中心点位置。在进行滑动卷积操作前，对F与H的卷积进行傅里叶变换，利用卷积定理将时域信号转化到频域，公式如下：

简写为：

G＝F⊙H

其中

滤波模板的计算可由上式看出：

MOSSE算法是一个在线训练的跟踪算法，由第一帧图像训练出滤波模板，然后由这个滤波模板在第二帧图像相同的位置做响应，得到响应图，再根据第二帧图像得到的结果更新滤波模板，依次类推，对一系列视频做预测。第一帧图像训练的方法是根据第一帧图像给出的目标区域，对目标区域进行随机仿射变换，可以理解为作线性变换，y＝ax+b，其中a控制缩放和旋转，而b控制平移，由此可以获取一系列的训练样本F

由一系列推导可得滤波器的解为：

滤波模板的更新策略为：

A

B

在KCF算法中，不再使用仿射变换生成训练样本，而是通过循环矩阵生成训练样本，即在目标周围按照x，y方向分别位移，得到不同的循环矩阵，从而生成第一帧图像训练所需要的正负样本。在KCF算法中，训练样本的生成都是基于循环矩阵形式来构建的，其中基样本为正样本，其他都是虚构出的负样本，这样的样本集具有很好的特性，可以很方便的利用快速傅里叶变换和傅里叶对角化的性质来进行计算，而不需要得知负样本的具体形式，KCF算法还将有关负样本的计算都转换到了频域进行求解。这样，采用了循环矩阵的性质对输入图像的搜索区域进行密集采样之后，使得进行跟踪器训练时缺少样本的问题迎刃而解。因此，整个KCF算法对跟踪器进行训练的目的就是利用生成的这些样本，生成一个滤波器，使得其作用于这些样本时会生成我们期望的分布形式。KCF训练的损失函数通过岭回归给出，对于训练样本(x

f(x

岭回归求解公式为：

其中后半部分可以理解为正则化项，其中λ是正则化参数，ω是权重矩阵。将其转化成矩阵形式：

其中X＝[x

ω＝(X

其中，I是单位矩阵。由于在傅里叶空间中，对所有的循环矩阵X使用傅里叶变换，都可以使循环矩阵对角化，即：

其中F是不依赖x的常数矩阵，

根据上述性质，将公式(1)转化到傅里叶空间中计算，结果形式写为：

ω＝(X

其中X

由于对角矩阵是对称的，因此仅采用Hermitian转置即可，

将公式(5)代入岭回归求解公式(3)中，则：

将上式两边同时进行傅里叶变换，得

此外，KCF算法还引入了核空间的概念，将低维空间中的问题映射到高维空间中，将线性问题转化为高维非线性问题，将低维中的不可分线性问题转化为了高维线性可分问题。

虽然KCF算法在目标跟踪领域取得了不错的效果，但是其本身也存在着问题。该方法无法解决目标跟踪过程中的遮挡问题。当目标遇到遮挡时，当前的滤波模板仍然返回响应图，并且继续按照响应值最大的位置跟踪目标。但是当目标遭遇遮挡后，以上一帧图像中目标框的位置为中心，无法得到准确的响应图，因为在目标被遮挡后其特征就会出现很大的改变，这就会造成目标框的位置出现飘移。而此时KCF依然会按照错误的目标位置继续更新滤波模板，这就很容易造成目标框的持续飘移，再也无法找到正确的目标位置。

因此，本发明提出一种利用样条插值的方法，对目标轨迹进行模拟。当遇到遮挡问题时，停止更新KCF滤波模板，根据遮挡前目标的运动特征，用离线训练的轨迹曲线模拟遮挡后的目标轨迹。

优选的，本发明选取三次样条插值进行轨迹模拟，因为如果选用二次样条插值，很有可能误差较大，达不到拟合的要求，而如果选择较高次数的插值，计算比较复杂，不符合视频序列中实时跟踪的需求。并且三次样条插值在一些轨迹拟合方面表现较为良好，比如在飞行器轨迹的导航等方面，三次样条插值就有着不错的表现。

三次样条插值的具体原理是，两端相邻的三次函数，由于曲线光滑，那么其样本点的值显然相同，若其一阶导数与二阶导数连续，则其一阶导数与二阶导数的值也相同。其具体定义是，假设在[a，b]区间内，有一组互不相同的节点：a≤x

(1)S(x)∈C

(2)S(x)在每个相邻节点之间的小区间[x

(3)插值函数S(x)经过所有的样本点，也就是说：

S(x

其中f(x

由以上定义可知，插值函数S(x)经过所有的样本点，那么可以得到第一个条件：

S(x

又由于插值函数S(x)在区间[a，b]内具有连续的一阶导数和二阶导数，则可以得到以下两个条件：

则：

由于共有n+1个点，可以得到3(n-1)个求解方程，又因为插值函数S(x)经过所有的样本点，所以有(n+1)个方程，此时总共是(4n-2)个方程。但是由于每个相邻样本点之间的插值函数是一段三次多项式，假设第i个区间中的插值函数为：

S

则：

可以看到，待求解的未知数为4n个。所以，为了求解方程，还需要两个不同于区间[a，b]中内点的条件，也就是边界条件：

第一边界条件：

S′(x

第二边界条件：

S″(x

则可以根据以上4n个方程求解所需要的4n个参数，即求解三次样条插值函数。

在目标跟踪过程中目标在图像中的位置即为样本点的值。在目标运动过程中，其运动轨迹是连续的(在视频中的每帧图像上是离散的)，并且一般来说，跟踪目标以人和人类社会中的工具或物品为主，那么目标的运动轨迹必然是有规律的，所以可以对固定帧数的训练样本视频，先做三次样条插值，得到该段样本视频中目标运动的线性轨迹。对不同视频插值出一系列参数：

其中m为训练样本视频数量，每行代表每段训练视频中插值出的三次样条函数的参数值。根据这一系列参数训练出一组参数(即后面提到的权重变化矩阵P和多项式系数矩阵Q)，训练方法为神经网络中的反向传播训练，通过最小二乘法构造损失函数，再通过随机梯度下降法，设定学习率，即可训练得到该参数。

由三次样条插值函数的定义可知，两个相邻样本点内的区间，可以插值出一个三次多项式，那么可以假设一个三次多项式，认为它是该区间内的曲线。由上所述，目标的运动轨迹是可循的，那么在相邻的两个区间内，可以认为目标的运动曲线轨迹是相关的。假设每个区间内的插值曲线只与上一个区间中的曲线有关，又假设上一个区间中的曲线已知，那么就可以利用随机过程中的马尔科夫链模型来求解。

所谓马尔科夫(Markov)链，是指认为当前状态只与前一时刻状态相关，与其它任何状态无关的一类随机过程。其定义为，假设一系列随机过程{X

P(X

上式即表明，如果该随机过程n+1时刻的状态只与n时刻的状态有关，与其它之前任何时刻状态无关，那么称之为Markov链。

通过假设某个区间段内的插值函数只与上一区间段内的插值函数有关，从而可以通过上一区间段内的三次多项式来给出下一阶段的三次多项式。但是在实际的问题中，由于目标运动的多样性，很难使用一个三次样条函数来准确的模拟某个区间段内目标的运动轨迹，那么为了提高模型的鲁棒性，本发明使用四个三次多项式来模拟目标的运动轨迹。其可以理解为在k维空间中，利用k个基向量赋予相应的权重来给出某个向量的值。可以认为所设的四个多项式，即为四个基向量，通过基向量求出所要的向量值。

假设四个三次多项式为：

既然涉及到四个三次多项式，那么必然要考虑到权重的问题，如果将权重带入到Markov链中，四个三次多项式的权重即为Markov链中的状态。由于Markov链中的状态只依赖于前一时刻状态，因而从某时刻到下一时刻的状态变化会有一个转移概率：

p

这个概率只与i，j有关，表示目标从上一时刻的状态i转移到当前时刻的状态j的概率，可以将转移概率写成矩阵形式：

在本发明里，将转移概率矩阵P称为权重变化矩阵，并且不再受限于转移概率中的p

令：

矩阵P称为权重变化矩阵，指示了从上一帧图像的四个三次样条多项式的权重转移到当前帧的四个三次样条多项式的权重的概率，Q是多项式的系数矩阵，w

其中W

其中z表示目标在第z帧遭遇遮挡。在对第i帧的计算过程中，用第i-2帧与第i-1帧，得到W

其中，W

w

最小二乘法定义的损失函数为：

利用随机梯度下降算法，对损失函数进行训练，可以得出权重变化矩阵P与多项式系数矩阵Q。

在目标跟踪的过程中，通过计算被遮挡前两帧的目标中心点位置，按照上述的权重计算方法，计算出初始的权重。假设在目标被遮挡后，目标x的位移速度与被遮挡前的位移速度相同，且匀速变化，则可以持续的给出遮挡后x的值，再由三次样条函数组以及权重转移矩阵，给出第i帧中目标在图像中纵坐标的值：

在跟踪过程中必须首先进行遮挡检测。在跟踪的过程中，如果目标遭遇遮挡，其KCF响应值最大的点会产生较大的偏差，由于目标的位移是连续的，不太可能突然产生较大的变化。那么当响应值最大的位置与上一帧中的位置差异较大时，即可认为目标被遮挡。传统的KCF算法在跟踪过程中以上一帧目标框的中心点位置扩大2.5倍目标框去搜索响应值最大的位置来判断目标重新出现，本发明中将搜索框扩大到原目标框的5倍，基本能够再次捕捉到目标出现的位置。

与现有技术相比，本发明具有如下创新点：

(1)本发明给出了一种基于物体运动轨迹和图像本身结合进行目标位置预测的方法，利用样条插值对目标轨迹进行模拟，对遮挡目标运动位置进行预测。当遇到遮挡问题时，停止更新KCF滤波模板，而根据遮挡前目标的运动特征，用离线训练的轨迹曲线模拟遮挡后的目标轨迹，基于马尔科夫链中当前目标状态只与上一时刻状态有关的假设，认为跟踪过程中当前图像的权重只与上一帧图像的权重有关，提出一种基于三次样条插值和马尔科夫链的KCF目标跟踪方法，从而解决目标跟踪过程中的遮挡问题。

(2)本发明在解决跟踪过程中遇到的遮挡问题时，不再局限于图像中的特征，而是着眼于目标的运动轨迹。通过对物体运动轨迹的分析对目标位置进行预测，采取按照不同运动方向进行样条插值的方法来拟合目标的运动轨迹。

(3)由于简单的样条插值参数量非常少以及目标运动轨迹的多样性，会出现非常严重的欠拟合现象，无法对目标轨迹进行准确的预测。在此基础上，基于马尔科夫链，不再简单的用一条轨迹来预测目标的位置，而是通过多条轨迹来预测。通过对多条轨迹附加相应权重，融合成一条轨迹，每条轨迹仍然使用样条插值来拟合，而每条轨迹对应的权重值由初始的权重值以及马尔科夫链中的转移矩阵计算，这样使得预测方法更为合理，一定程度上增加了模型预测的鲁棒性。

根据本申请的第一方面，提供了第一基于三次样条插值和马尔科夫链的KCF目标跟踪方法，包括：获取要从中进行目标跟踪的视频序列，转向执行步骤235；步骤235，从所述视频中获取按时间顺序的下一帧图像作为当前帧图像，转向执行步骤240；步骤240，从当前帧图像中提取FHOG(方向梯度直方图)特征，转向执行步骤255；步骤255，用训练得到的KCF滤波模板H处理当前帧图像的FHOG(方向梯度直方图)特征得到响应值图，并根据响应值图中响应值最大的点所在位置识别所述跟踪目标在当前帧图像中的位置，转向执行步骤260；步骤260，若识别出所述目标在当前帧图像中被遮挡，则转向步骤270；步骤270，根据训练得到的权重变化矩阵P、多项式系数矩阵Q以及相对于当前帧图像的前一帧图像的权重W

根据本申请的第一基于三次样条插值和马尔科夫链的KCF目标跟踪方法，提供了第二基于三次样条插值和马尔科夫链的KCF目标跟踪方法，其中步骤260，若识别出所述目标在当前帧图像未被遮挡，则实现了在当前帧图像中对所述目标的跟踪，以及转向步骤235，以继续在下一帧图像中跟踪所述目标。

根据本申请的第一或第二基于三次样条插值和马尔科夫链的KCF目标跟踪方法，提供了第三基于三次样条插值和马尔科夫链的KCF目标跟踪方法，其中步骤280，其中若在当前帧图像中的所述预测位置周围所述目标框大小的N倍范围内存在响应值图的响应值最大的点，则确定搜索到所述目标；其中若在当前帧图像中的所述预测位置周围所述目标框大小的N倍范围内不存在响应值图的响应值最大的点，则确定未搜索到所述目标；其中N为3～5的整数。

根据本申请的第三基于三次样条插值和马尔科夫链的KCF目标跟踪方法，提供了第四基于三次样条插值和马尔科夫链的KCF目标跟踪方法，其中步骤290，若步骤280在当前帧图像中搜索到所述目标，则实现了对所述目标的跟踪，以及转向步骤235以继续在下一帧图像中跟踪所述目标。

根据本申请的第四基于三次样条插值和马尔科夫链的KCF目标跟踪方法，提供了第五基于三次样条插值和马尔科夫链的KCF目标跟踪方法，其中步骤290，若通过步骤237、步骤247与步骤280在连续M帧图像中未搜索到所述目标，则转向步骤298，指示对所述目标的跟踪失败，其中M正整数，并且为指定的阈值。

根据本申请的第五基于三次样条插值和马尔科夫链的KCF目标跟踪方法，提供了第六基于三次样条插值和马尔科夫链的KCF目标跟踪方法，还包括：从所述视频中获取一帧图像F作为训练图像；在所述训练图像中标注所述目标的位置并指定目标框大小；从所述训练图像、标注的所述目标的位置与指定的目标框生成正样本与多个负样本，用所述正样本与多个负样本训练得到所述KCF滤波模板H。

根据本申请的第六基于三次样条插值和马尔科夫链的KCF目标跟踪方法，提供了第七基于三次样条插值和马尔科夫链的KCF目标跟踪方法，其中所述KCF滤波模板H的生成过程为：通过循环矩阵生成一帧图像训练所需要的正样本与多个负样本；由高斯函数按照以F

则滤波器模板为：

其中⊙表示点乘，H

根据本申请的第七基于三次样条插值和马尔科夫链的KCF目标跟踪方法，提供了第八基于三次样条插值和马尔科夫链的KCF目标跟踪方法，其中步骤240，从当前帧图像中提取FHOG(Felzenszwalb′s HOG(FHOG)，方向梯度直方图)特征，包括：

1)对当前帧图像进行Gamma压缩和颜色空间归一化；

2)计算当前帧图像的梯度，其中根据公式

计算当前帧图像的各像素点(x，y)梯度的幅值G(x，y)；

根据公式

计算当前帧图像的各像素点(x，y)梯度的方向α(x，y)；其中

G

3)计算当前帧图像的各个细胞单元(cell)的梯度直方图，其中细胞单元是当前帧图像中互不重叠且大小相同的区域，每个区域包括n*n像素，其中n为正整数；

4)通过4种归一化因子对每个细胞单元进行对角线邻域归一化及截断，提取每个细胞单元内的31维FHOG特征；其中，18维FHOG特征来自于细胞单元的有符号的梯度方向直方图；9维FHOG特征来自于细胞单元的无符号的梯度方向直方图；4维FHOG特征来自于对18维有符号的FHOG特征和9维无符号的FHOG特征按行累加。

根据本申请的第八基于三次样条插值和马尔科夫链的KCF目标跟踪方法，提供了第九基于三次样条插值和马尔科夫链的KCF目标跟踪方法，其中步骤260，还包括：若识别出所述目标在当前帧图像未被遮挡，则更新所述KCF滤波模板H；若识别出所述目标在当前帧图像被遮挡，则不更新所述KCF滤波模板H。

根据本申请的第九基于三次样条插值和马尔科夫链的KCF目标跟踪方法，提供了第十基于三次样条插值和马尔科夫链的KCF目标跟踪方法，其中根据公式

A

B

其中，⊙表示点乘，F

根据本申请的第九基于三次样条插值和马尔科夫链的KCF目标跟踪方法，提供了第十一基于三次样条插值和马尔科夫链的KCF目标跟踪方法，其中识别所述目标在当前帧图像中被遮挡，包括：若所述当前帧图像中所述目标的位置相对于所述当前图像的上一帧图像中所述目标的位置的变化大于指定阈值，则识别所述目标在当前帧图像中被遮挡。

根据本申请的第十一基于三次样条插值和马尔科夫链的KCF目标跟踪方法，提供了第十二基于三次样条插值和马尔科夫链的KCF目标跟踪方法，其中在当前帧图像中的所述预测位置周围的指定目标框大小的N倍范围内搜索所述目标，包括：获取当前帧图像的响应值图的最大值在响应值图中的第一位置；若所述第一位置在所述预测位置周围的指定目标框大小的N倍范围内，则确定搜索到所述目标；若所述第一位置不在所述预测位置周围的指定目标框大小的N倍范围内，则确定未搜索到所述目标。

根据本申请的第十二基于三次样条插值和马尔科夫链的KCF目标跟踪方法，提供了第十三基于三次样条插值和马尔科夫链的KCF目标跟踪方法，其中步骤270，根据训练得到的权重变化矩阵P、多项式系数矩阵Q以及相对于当前帧图像的前一帧图像的权重W

其中根据第j-1帧图像中所述目标在X轴的坐标x

根据本申请的第十三基于三次样条插值和马尔科夫链的KCF目标跟踪方法，提供了第十四基于三次样条插值和马尔科夫链的KCF目标跟踪方法，其中权重变化矩阵P指示所述目标从第j-1帧图像中的多个多项式的权重转移到当前帧的多个多项式的权重的概率，其中当前帧图像是第j帧图像。

根据本申请的第十四基于三次样条插值和马尔科夫链的KCF目标跟踪方法，提供了第十五基于三次样条插值和马尔科夫链的KCF目标跟踪方法，其中多项式系数矩阵Q指示多个多项式的系数，其中所述多个多项式的每个代表用于预测所述跟踪对象的运动轨迹的三次样条插值函数。

根据本申请的第十五基于三次样条插值和马尔科夫链的KCF目标跟踪方法，提供了第十六基于三次样条插值和马尔科夫链的KCF目标跟踪方法，其中第j帧图像的权重W

其中，x

根据本申请的第十六基于三次样条插值和马尔科夫链的KCF目标跟踪方法，提供了第十七基于三次样条插值和马尔科夫链的KCF目标跟踪方法，其中w

根据本申请的第十七基于三次样条插值和马尔科夫链的KCF目标跟踪方法，提供了第十八基于三次样条插值和马尔科夫链的KCF目标跟踪方法，其中获取权重变化矩阵P，以及多项式的系数矩阵Q的过程包括：使用

由此训练出模型所需要的权重变化矩阵P，以及多项式的系数矩阵Q；其中x

附图说明

图1为本发明的MOSSE/KCF目标跟踪预测流程图。

图2为本发明的基于三次样条插值和马尔科夫链的KCF目标跟踪算法流程。

图3为本发明的实施例的FHOG特征提取流程图。

图4为本发明的实施例的不同iou阈值下三种算法的预测准确率。

图5为本发明的实施例的三种跟踪算法的性能数值对比。

图6为本发明的实施例的K-KCF和KS-KCF跟踪算法的跟踪实例。

具体实施方式

下面结合附图和实施例对本发明进行详细说明。

图1为本发明的MOSSE/KCF目标跟踪预测流程图

参看图1，其中F是输入图像，F可以是原始图像，也可以是提取的特征图；H是滤波模板，通过滤波模板对输入图像进行滑动卷积，然后对卷积后的特征图中元素进行求和，得到输入图像F中对应区域中心位置的响应值。注意到，图中的卷积操作，是用所选区域与滤波模板进行对应位置的点乘操作，并不是如卷积神经网络中的卷积，将两个矩阵进行求积。原因是在进行滑动卷积操作前对F与H的卷积进行了傅里叶变换，利用卷积定理将时域信号转化到频域，公式如下：

简写为：

G＝F⊙H

其中F是输入图像，H是滤波模板，f和h分别是F和H的时域表示，

滤波模板的计算可由上式看出：

MOSSE算法是一个在线训练的跟踪算法，由第一帧图像训练出滤波模板，然后由这个滤波模板在第二帧图像相同的位置做响应，得到响应图，再根据第二帧图像得到的结果更新滤波模板，依次类推，对一系列视频做预测。第一帧图像训练的方法是根据第一帧图像给出的目标区域，对目标区域进行随机仿射变换，可以理解为作线性变换，y＝ax+b，其中a控制缩放和旋转，而b控制平移，由此可以获取一系列的训练样本f

由一系列推导可得滤波器的解为：

滤波模板的更新策略为：

A

B

KCF算法做了一些改进，不再使用仿射变换生成训练样本，而是通过循环矩阵，在目标周围按照x，y方向分别位移，得到不同的循环矩阵，从而生成第一帧图像训练所需要的正负样本，在KCF算法中，训练样本的生成都是基于循环矩阵形式来构建的，其中基样本为正样本，其他都是虚构出的负样本，这样的样本集具有很好的特性，可以很方便的利用快速傅里叶变换和傅里叶对角化的性质来进行计算，而不需要得知负样本的具体形式，KCF算法还将有关负样本的计算都转换到了频域进行求解。这样，采用了循环矩阵的性质对输入图像的搜索区域进行密集采样之后，使得进行跟踪器训练时缺少样本的问题迎刃而解。因此，整个KCF算法对跟踪器进行训练的目的就是利用生成的这些样本，生成一个滤波器，使得其作用于这些样本时会生成我们期望的分布形式。从而实现目标的检测跟踪。

图2为本发明的基于三次样条插值和马尔科夫链的KCF目标跟踪算法流程。

基于三次样条插值和马尔科夫链的KCF目标跟踪算法流程如下：

(1)获取视频的一帧图像(例如第一帧图像)中的目标的位置以及目标框大小(x，y，d，h)(210)；x，y指目标的中心位置，d，h指目标框的宽度和高度。

(2)通过第一帧图像给出的(x，y，d，h)对目标框周围进行位移，得到不同的循环矩阵，生成正负样本(220)；

(3)对于第一帧图像进行训练，得到KCF滤波模板H(230)；

(4)从视频中获取下一帧图像作为当前帧图像(235)；

(5)对于当前帧图像，提取图像的FHOG(Felzenszwalb′s HOG(FHOG)，HOG(histogram of oriented gradients)，方向梯度直方图)特征(240)；

HOG(histogram of oriented gradients)特征的提取过程如下：

1)颜色空间归一化

在现实的情况，图像目标会出现在不同的环境中，光照也会有所不一样，颜色空间归一化就是对整幅图像的颜色信息作归一化处理从而减少不同光照及背景的影响，也为了提高检测的鲁棒性，引入图像Gamma压缩和颜色空间归一化来作为特征提取的预处理手段。

2)梯度计算

边缘是由图像局部特征包括灰度、颜色和纹理的突变导致的。一幅图像中相邻的像素点之间变化比较少，区域变化比较平坦，则梯度幅值就会比较小，反之，则梯度幅值就会比较大。梯度在图像中对应的就是其一阶导数。模拟图像f(x，y)中任一像素点(x，y)的梯度是一个矢量：

其中，G

数字图像中像素点的梯度是用差分来计算的：

一维离散微分模板将图像的梯度信息简单、快速且有效地计算出来，其公式如下：

式中，G

3)计算细胞单元的梯度直方图

对于整个目标窗口，需要将其分成互不重叠大小相同的细胞单元(cell)，每个cell大小为3*3像素，然后分别计算出每个cell的梯度信息，包括梯度大小和梯度方向。有实验指出，将像素的梯度方向在0-180°区间内平均划分为9个bins，超过9个时不仅检测性能没有明显的提高反而增加了检测运算量，每个cell内的像素为其所在的梯度方向直方图进行加权投票，加权的权值可以是像素本身的梯度幅值，也可以是幅值的平方或平方根等，而若使用平方或平方根，实验的检测性能会有所降低。对cell内每个像素用梯度方向在直方图中进行加权投影，就可以得到这个cell的梯度方向直方图，该直方图即为该cell对应的9维特征向量(即9个bin直方图)。

4)对组合成块的梯度直方图作归一化

从梯度计算公式中可以看出，梯度幅值绝对值的大小容易受到前景与背景对比度及局部光照的影响，要减少这种影响得到较准确的检测效果就必须对局部细胞单元进行归一化处理。归一化方法多种多样，但整体思想基本上是一致的：将几个细胞单元(cell)组合成更大的块(block)，每个block包含2*2个cell，则block大小为6*6像素。这时整幅图像就可看成是待检测窗口，将更大的块看成是滑动窗口，依次从左到右从上到下进行滑动，得到一些有重复细胞单元的块及一些相同细胞单元(cell)在不同块(block)中的梯度信息，再对这些块(block)信息分别作归一化处理。每个block会得到一个4*9＝36维的特征向量，这些特征是按照顺序串联起来的(保证空间特征)。通过将原始图像划分为block，计算每个block的特征向量，再将每个block的特征向量按照顺序串联，便得到图像的HOG特征。

在HOG特征提取中，颜色空间的归一化是为了减少光照以及背景等因素的影响；划分检测窗口成大小相同的细胞单元(cell)，并分别提取相应的梯度信息，组合相邻的细胞单元成大的相互有重叠的块(block)，这样能有效的利用重叠的边缘信息，以统计整个块(block)的直方图；对每个块内的梯度直方图进行归一化，从而进一步减少背景颜色及噪声的影响；最后将整个窗口中所有块的HOG特征收集起来按照顺序串联构成特征向量，便可以表示图像的HOG特征。

FHOG特征在传统的HOG特征上进行了一些改进。参看图3，图3为本发明的实施例的FHOG特征提取流程图。将整幅图像划分为若干个8*8的cell，通过定义4种不同的归一化因子进行对角线邻域归一化及截断，提取每个cell内的31维特征，其中18维特征来自于对cell做18个bin的有符号的梯度方向直方图，即将360°划分为18个bin，然后令cell中的每个像素根据其梯度方向加权投影到直方图相应的bin中，这样就得到了18维有符号的FHOG特征；9维特征来自于对cell做9个bin的无符号的梯度方向直方图，此时是将180°划分为9个bin，则得到9维无符号的FHOG特征；最后的4维特征来自于对18维有符号的FHOG特征和9维无符号的FHOG特征按行累加。每个cell的31维特征中，27维包含了27个bin通道，其中18个对方向敏感，9个对方向不敏感，4维分别捕获了当前cell周围4个cell组成的梯度能量。

返回参看图2，

(6)通过KCF滤波模板H依次对当前帧进行目标位置检测，同时进行模板的更新(255)；

(7)在跟踪过程中检测响应值位置的变化，当当前响应值最大的位置与上一帧中的响应位置变化达到阈值时，判定目标被遮挡(260)；若判定目标未被遮挡，返回步骤(4)(235)继续从视频中获取下一帧图像作为当前帧并继续后续处理。

(8)当目标被遮挡后，由离线训练的P，Q矩阵，给出当前帧图像中目标预测位置y

其中i代表当前帧图像为第i帧图像，P为权重变化矩阵，Q为多项式系数矩阵，利用神经网络中的反向传播训练，通过最小二乘法构造损失函数，再通过随机梯度下降法，设定学习率，使用一系列样本视频里插值出的三次样条函数的参数值进行训练，即可得到P、Q。

(9)在当前帧图像中目标预测位置(x

(10)若在目标预测位置(例如目标框大小5倍范围内)搜索到目标，转向步骤(4)(235)继续从视频中获取下一帧图像作为当前帧并继续后续处理；若在目标预测位置搜索不到目标，还进一步判断搜索失败次数是否已达到阈值(295)。

(11)若搜索失败次数尚未达到阈值(295)，继续从视频中获取下一帧图像作为当前帧图像(237)，并提取图像的FHOG特征(247)；以及在目标预测位置(x

在步骤247，提取了当前图像的FHOG特征后，直接转向步骤280，并用对前一帧(在步骤270)所作的目标预测位置，在当前帧图像的该目标预测位置附近的目标框大小5倍范围内搜索目标。

在步骤298，若搜索失败次数达到或超过阈值，则认为目标丢失，对目标的跟踪失败。

实施例1：

本实施例选用了LaSot数据集(参见https：//arxiv.org/abs/1809.07845)中的部分视频序列，并选取每个视频序列的前500帧图像进形跟踪性能测试。

在本发明中，采用三次样条插值，结合马尔科夫链来解决遮挡后的目标预测问题，同时扩大搜索范围，以便能够在目标重新出现时找到目标。为了方便后续说明，将该算法记为MS-KCF算法。

为了说明本发明的目标跟踪算法的有益性，将传统的KCF算法作为第一种比较算法，并且将经典的基于卡尔曼滤波的KCF算法作为第二种比较算法，记为K-KCF算法。在K-KCF算法中，在目标跟踪过程中，加入二维卡尔曼滤波进行预测结果的修正，并且当目标遭遇遮挡时，停止更新KCF滤波模板，使用卡尔曼滤波，根据遮挡前的目标状态，进行遮挡后目标位置的预测。

在本实施例中，通过预测目标框与标签中真实目标框的重合面积(称为iou指数)，设置不同的阈值，指定当iou指数大于阈值时认为预测的结果是正确的，根据准确预测的数量计算出预测准确率。

接下来在相同的硬件配置下运行KCF、K-KCF、MS-KCF算法，使用平均FPS(每秒传输帧数(Frames Per Second))，平均iou指数以及不同iou指数阈值下的预测准确率来分析三种算法的性能和优劣势。

图4为本发明的实施例的不同iou阈值下三种算法的预测准确率。由图4可见，当iou阈值接近0时，三种算法的预测准确率都接近100％，当iou阈值接近1时，三种算法的预测准确率都趋近于0，但是iou阈值靠近1和0时的准确率参考意义不大，因此本实施例中只考虑中间部分的数值。可以看到，引入卡尔曼滤波算法的K-KCF算法在中间区域完全落后于另外两种算法。而KS-KCF算法与KCF算法互有交织，但大部分情况下KS-KCF算法还是要优于KCF算法。

图5为本发明的实施例的三种跟踪算法的性能数值对比。可以看到图5中KCF与K-KCF算法的平均FPS较高，达到了70以上，而KS-KCF也较高，接近40，基本能实现实时跟踪。同时由图5可得，KS-KCF的平均iou指数最高，基本接近0.4。因而，在基本满足实时跟踪的情况下，KS-KCF算法的鲁棒性最好。所以本发明提出的在KCF算法中引入三次多项式和马尔科夫链并扩大搜索范围的思想是有益的。

图6为本发明的实施例的K-KCF和KS-KCF跟踪算法的跟踪实例，跟踪目标为运动中的篮球。由图6可以看出，在遮挡后的较短时间里，K-KCF算法比较准确的预测出了目标的位置，但当目标改变方向并且重新出现后，K-KCF算法并不能够及时的改变跟踪方向。因为前几帧图像中，整个目标确实是在横轴方向匀速运动，这就给卡尔曼滤波造成了错觉，训练出的转移矩阵不再具有鲁棒性，所以从这一帧开始，目标框开始匀速向左飘移，直至离开整个图像。而相对的，KS-KCF算法在同一帧图像上预测结果却不同。可以看到，当目标改变方向并且重新出现后，预测的结果虽然有偏差，但目标框的变化方向却是正确的。所以在接下来的短暂的几帧之后，KS-KCF模型重新找到目标，并给出完整的目标框。这说明了KS-KCF算法跟踪的鲁棒性要高于K-KCF算法。

根据本申请实施例提供的一种或多种算法与处理流程，运行在例如个人计算机、服务器、嵌入式计算设备、云计算平台等设备中。