网站排名方案,旺苍网站建设,上海哪家网站建设比较好,唐山自助网站建设系统目前在online visual tracking这个领域#xff0c;已经涌现出很多的跟踪算法#xff0c;比较知名如TLD#xff0c;Struck#xff0c;OAB#xff0c;CT等等。但是能做到非常快速而且效果还不错的相对就较少了#xff0c;好多算法都是刚刚能实时#xff0c;而且还是在图像…目前在online visual tracking这个领域已经涌现出很多的跟踪算法比较知名如TLDStruckOABCT等等。但是能做到非常快速而且效果还不错的相对就较少了好多算法都是刚刚能实时而且还是在图像分辨率不是很大的情况下。之前在博客里提到一篇该领域的测评综述1对该领域大部分算法进行了一个总结和评估作者在一个有50个视频的数据集上测试了29个算法其中速度和效果都还不错的算法有TLD2和Struck3。Struck的评价运行速度大概是20帧/sTLD相对快一点,大概28帧/s。但这个速度仍然不是很快而14年的一篇paper提出了一种叫做KCF(Kernerlized Correlation Filter)4的跟踪算法使得速度有了很大提升在同样的测试数据集上平均运行速度达到172帧/s(使用HOG特征的情况下)。而且据paper的实验结果显示准确率比Struck和TLD都高。之所以能有这么快的速度得益于作者巧妙地通过循环偏移构建出了分类器的训练样本从而使得数据矩阵变成了一个循环矩阵。然后基于循环矩阵的特性把问题的求解变换到了傅里叶变换域从而避免了矩阵求逆的过程大大降低了算法的复杂度。问题阐述目前跟踪算法主流的思想还是基于tracking by detection而训练样本的选择基本上就以目标中心为提取正样本然后基于周围的图像提取负样本。大部分算法都是采用非正即负的方法来标记训练样本即正样本标签为1负样本为0。这种标记样本的方法有一个问题就是不能很好的反应每个负样本的权重即对离中心目标远的样本和离中心目标的近的样本同等看待。所以就有算法提出使用连续的标签进行标记样本即根据样本中心里目标的远近分别赋值[0,1]范围的数。离目标越近值越趋向于1离目标越远值越趋向于0。事实也证明这种标记样本的方法能得到更好的效果比如Struck和KCF。Struck是通过一种loss函数隐式地采用了这种连续的样本标记方法而KCF则通过使用[0,1]范围的值作为样本的回归值从而给不同偏移下得到的样本不同的权重。首先我们先介绍一个简单的线性回归模型然后再讨论引入kernel之后的情况。样本训练过程实际上是一个岭回归问题或者叫做正则化最小二乘问题它有一个闭式的解。假设给定一些训练样本及其回归值 {(x1,y1),(x2,y2),...,(xi,yi),...}{(x1,y1),(x2,y2),...,(xi,yi),...} 其训练的最终目标是找到一个函数 f(z)wTzf(z)wTz 使得如下残差函数最小minw∑i(f(xi)?yi)2λ∥w∥2(1)(1)minw∑i(f(xi)?yi)2λ∥w∥2其中 λλ 是正则化参数防止过拟合的。上式的闭式解可以参考线性最小二乘的求解得出如下w(XTXλI)?1XTy(2)(2)w(XTXλI)?1XTy这里 XX 是由一个样本的特征向量占一行组成的样本矩阵。 yy 是对应每个样本的回归值 yiyi 组成的列向量。 II 是个单位矩阵。 因为考虑到后面要在傅里叶域进行计算这里给出一个复数情况下的求解结果其中 XHXH 是 XX 的共轭转置 w?w? 是 ww 的共轭。w?(XHXλI)?1XHy(3)(3)w?(XHXλI)?1XHy现在问题来了如果直接求解上述闭式解其中的求逆计算随着样本数的增大是非常耗时的。显然直接求解的方式是不靠谱的这里这篇paper的作者通过巧妙地把上述闭式解变换到傅里叶变换域的方式从而避开了矩阵求逆的运算大大节省了运行时间。而这也是这篇paper的主要贡献所在。DFT下的线性回归为了解释的简明性这里仅仅就一维的单通道信息做分析也就是说这里的 xx 都是一维向量当然推广到二维也是适用的而且实际上代码中也的确就是在二维上做的。我们看到式 (3)(3) 中的样本矩阵 XX 如果是一个循环矩阵的话该式子的计算就会变得容易很多。即XC(x)?????????x1xnxn?1?x2x2x1xn?x3x3x2x1?x4?????xnxn?1xn?2?x1?????????(4)(4)XC(x)[x1x2x3?xnxnx1x2?xn?1xn?1xnx1?xn?2?????x2x3x4?x1]其中 xx 是矩阵的第一行整个矩阵式由这一行的循环偏移得到的。那我们假设存在这么一个循环矩阵看看接下来式 (3)(3) 会变成怎样。首先列出一个循环矩阵拥有的一个性质5如下XFHdiag(x^)F(5)(5)XFHdiag(x^)F其中 xx 头上的那个小帽 x^x^ 代表 xx 的傅里叶变换 FF 是离散傅里叶变换矩阵即满足 x^Fxx^Fx 。这样把式 (5)(5) 代入式 (3)(3) 中得w?(FHdiag(x^?)FFHdiag(x^)FλI)?1FHdiag(x^?)FyF?1(diag(x^?⊙x^)λI)?1diag(x^?)FyF?1diag(x^?x^?⊙x^λ)Fy(6)(6)w?(FHdiag(x^?)FFHdiag(x^)FλI)?1FHdiag(x^?)FyF?1(diag(x^?⊙x^)λI)?1diag(x^?)FyF?1diag(x^?x^?⊙x^λ)Fy其中 ⊙⊙ 代表向量对应元素相乘然后两边同时左乘 FF 得w^?x^?⊙y^x^?⊙x^λ(7)(7)w^?x^?⊙y^x^?⊙x^λ至此我们可以看出通过上述变换后权重向量 ww 的求解变换到了傅里叶变换域而且计算量大大降低。构建循环样本矩阵不同的提取训练样本方法左图是以base图像为中心向周围偏移得到的样本作为负样本右图是基于base图像做循环偏移得到的样本作为负样本。通过上面的计算我们可以看出如果能构建一个循环矩阵那么就能极大的加速样本的训练过程。那到底能不能呢我们先来看一组基于目标中心周围偏移提取的正负训练样本。通过右图可以看出常规的方法是以目标图像为base图像基于该图像左右上下偏移得出一系列的图像块作为负样本进行训练(左图所示)。而通过对base图像进行循环偏移的方法可以得到一些近似的的负样本作为训练样本进行训练(右图所示)。这里我们发现通过循环偏移得到的图像在边界处并不是很平滑消除这种现象的方式就是通过对base图像乘以一个汉宁窗来降低边缘图像的权重。这样训练样本构成的样本矩阵就变成了一个循环矩阵(如式 (4)(4) 所示)。引入核函数以上介绍的都是线性回归的情况如果能引入核函数分类器的性能将会更好。核函数的引入是把特征空间映射到一个更高维的空间去这里我们假设这个映射函数为 φ(x)φ(x) 则分类器的权重向量变为w∑iαiφ(x)(8)(8)w∑iαiφ(x)这样我们最终要求解的参数就由 ww 变为 αα 这里 α{α1,α2,...,αi,...}Tα{α1,α2,...,αi,...}T 。因为其实我们并不知道核函数映射的高维空间是什么我们只是知道高维空间下的两个向量的乘积可以通过一个映射函数把其在低维空间下的乘积映射到高维空间也就是核函数。这里设不同样本之间的乘积的核函数结果组成的矩阵为Kijκ(xi,xj)(9)(9)Kijκ(xi,xj)这样最终的回归函数变为f(z)wTz∑i1nαiκ(z,xi))(10)(10)f(z)wTz∑i1nαiκ(z,xi))直接计算上述函数相对来说是很耗时的下面还是结合循环矩阵的特性实现一种快速的核函数计算方法。快速训练基于核函数下的岭回归的解为6α(KλI)?1y(11)(11)α(KλI)?1y其中 KK 核函数矩阵如式 (9)(9) 所示。如果我们能够证明 KK 是循环矩阵则上式的求解就可以转换到DFT域即α^?y^k^xxλ(12)(12)α^?y^k^xxλ这里 kxxkxx 是核函数矩阵 KK 的第一行元素组成的向量。如果两个向量的元素的次序发生变化不影响最终通过核函数计算的结果则该核函数构成的矩阵就是一个循环矩阵像高斯核函数多项式核函数都是满足上面条件的。快速检测上面已经提到直接计算式 (10)(10) 是非常耗时的快速的解法是像式 (9)(9) 那样通过构建测试样本和训练样本的核函数矩阵如下KzC(kxz)(13)(13)KzC(kxz)其中 kxzkxz 是这个循环矩阵的第一行组成的向量。这样就可以同时计算基于测试样本 zz 的循环偏移构成的所有测试样本的响应即f(z)(Kz)Tα(14)(14)f(z)(Kz)Tα注意这里 f(z)f(z) 不同于式 (10)(10) 它是一个向量由基于base样本 zz 不同循环偏移下的响应值组成。根据循环矩阵的性质(如式 (5)(5) 所示)上式变换到DFT域后f^(z)(k^xz)?⊙α^(15)(15)f^(z)(k^xz)?⊙α^快速计算核函数相关性到现在为止只剩下前面部分提到的 kxxkxx 和 kxzkxz 没有阐明如何计算了。首先列出 kxx^kxx^ 的计算公式如下kxx′g(C(x′)x)(16)(16)kxx′g(C(x′)x)其中 g(x)g(x) 是核函数 C(x′)C(x′) 是基于 x′x′ 为第一行的循环矩阵。参考式 (5)(5) 所示循环矩阵的特性代入上式得kxx′g(F?1(x^⊙x^?))(17)(17)kxx′g(F?1(x^⊙x^?))所以对于多项式核函数其计算公式如下kxx′(F?1(x^⊙x^?)a)b(18)(18)kxx′(F?1(x^⊙x^?)a)b对于高斯核函数其计算公式如下kxx′exp(?1σ2(∥x∥2∥x′∥2?2F?1(x^⊙x^?)))(19)(19)kxx′exp(?1σ2(∥x∥2∥x′∥2?2F?1(x^⊙x^?)))总结KCF的最大优势在于速度很快但是每帧训练的权重向量更新问题并没有很好的解决目前算法采用的是按照一定比例更新最新的训练的权重向量到现有的权重向量中去。此外作者在其主页上公布了Matlab源代码我根据其代码也写了一个C版的具体可以参考这里。ReferencesY. Wu, J. Lim, and M.-H. Yang, Online object tracking: A benchmark, in Computer vision and pattern recognition (CVPR), 2013 IEEE Conference on, 2013, pp. 2411-2418.Z. Kalal, K. Mikolajczyk, and J. Matas, Tracking-Learning-Detection, Pattern Analysis and Machine Intelligence, IEEE Transactions on,pp. 1-1, 2011.S. Hare, A. Saffari, and P. H. S. Torr, Struck: Structured Output Tracking with Kernels, 2011 IEEE International Conference on Computer Vision (ICCV),pp. 263-270, 2011.J. F. Henriques, R. Caseiro, P. Martins, and J. Batista, High-Speed Tracking with Kernelized Correlation Filters, IEEE Transactions on Pattern Analysis and Machine Intelligence,2014.R. M. Gray, Toeplitz and circulant matrices: A review: now publishers inc, 2006.R. Rifkin, G. Yeo, and T. Poggio, Regularized least-squares classification, Nato Science Series Sub Series III Computer and Systems Sciences,vol. 190, pp. 131-154, 2003.
