一种改进的长时间压缩感知跟踪算法

李宏波，郑世宝，周　芹

(上海交通大学 图像通信与网络工程研究所，上海 200240)

一种改进的长时间压缩感知跟踪算法

李宏波，郑世宝，周芹

(上海交通大学 图像通信与网络工程研究所，上海 200240)

摘要:压缩感知跟踪(CT)算法具有简单、高效、实时的优点，但是却存在着跟踪窗口尺寸不能自适应变化，无法有效处理遮挡以及跟踪失败后的目标再发现等问题。为了解决上述问题，提出了一种改进的长时间压缩感知跟踪算法。所提出的算法采用多尺度的目标外观再匹配方法，使得跟踪窗口大小能够适应目标尺寸变化。此外，通过分析滑动窗口内跟踪窗口图像的整体特征变化来判定目标是否发生遮挡。为了解决跟踪器漂移问题，采用Haar特征在线生成检测器，实现目标的再发现。实验结果表明提出的算法相比原CT算法具有更好的鲁棒性和准确性。

关键词:目标跟踪；压缩感知跟踪；尺寸自适应；长时间跟踪

1目标跟踪

目标跟踪一直是计算机视觉领域重要研究课题之一，广泛应用于智能视频监控、人机交互、增强现实等领域。尽管许多新颖的跟踪算法相继被提出，但是由于存在着光照变化、背景干扰、遮挡等问题，设计出高效鲁棒的跟踪算法依然是个难点。

一个良好的目标外观模型是跟踪算法成功的关键，近些年，以在线方式更新目标外观模型的在线视觉跟踪成为主流。在线视觉跟踪本质上可以看作是一个序列化的贝叶斯滤波过程，它主要包括3个部分：外观模型、状态转移模型和观测模型。

Zhang等提出的实时压缩感知跟踪(CT)算法[1]，由于其简单、高效，快速的特点，引起了很多学者的关注。CT算法是典型的遵循tracking-by-detection思路的跟踪算法，它采用在压缩子空间中得到的特征向量来描述目标，并利用朴素贝叶斯分类器进行判决。但是，CT算法本身存在着一些缺陷：第一，由于其所采集的样本大小相同，从而跟踪窗口不能够随目标尺寸变化自适应缩放；第二，CT算法采用固定学习速率在线更新分类器参数，在目标发生遮挡时，分类器参数被错误更新，导致跟踪漂移或失败。第三，CT算法无法在目标重现时将其识别出来，因此不能长时间锁定跟踪目标。

本文针对CT算法的上述缺陷做出相应的改进。第一，选取经过分类器判定后置信度最大的前10个样本作为候选样本，并在各个样本附近选取多种尺度的样本组成新一帧的候选样本集。然后将样本集中的所有样本分别与前一帧跟踪结果进行比较，选取置信度最高的样本作为跟踪结果。这种做法不仅减轻了跟踪器的漂移问题，而且使得跟踪窗口尺寸能够自适应变化。第二，通过滑窗的方式选取连续N帧目标图像，表示为X={xt+1,xt+2,…,xt+N}，采用归一化颜色直方图作为整体特征，分别计算xi(i=t+2,t+3,…,t+N)与xt+1相应颜色直方图的巴氏距离，通过分析巴氏距离的变化可以判定跟踪目标是否发生了遮挡。第三，利用遮挡前的目标图像以及背景图像，采用Hr特征训练分类器(即检测器)，在目标跟丢后启动检测器，实现对目标的再发现。

2压缩感知跟踪算法

压缩感知跟踪(CT)算法是由Zhang等人提出的简单高效的跟踪算法。它采用从压缩子空间提取的特征向量作为外观模型。在对CT算法的特征向量做降维时，采用具有严格正交变换性质的稀疏矩阵，将图像的特征空间降为低维的压缩子空间。在跟踪过程中，正负样本也是利用相同的稀疏投影矩阵进行压缩并由简单的朴素贝叶斯分类器进行区分。CT算法一定程度上可以减轻因姿态或者光照变化造成的跟踪漂移。

压缩感知理论是CT算法特征降维的基本原理。对于图像高维特征向量空间(x∈Rm)，利用满足有限等距(RIP)性质的随机矩阵R(R∈Rn×m)，其中n<

v=Rx

(1)

CT算法中采用的稀疏矩阵R，不仅满足RIP性质，而且便于计算。其定义如下

(2)

具体实现时，参数s定为m/4，即只需从m维的向量中随机选取2～3个值做加权求和得到新的特征值。

在目标跟踪过程中，分类器输入是降维后的低维特征向量，记作v=(v1,…,vn)T，向量v中各元素被认为是相互独立的，则朴素贝叶斯分类器的输出公式为

(3)

假定先验概率p(y=1)=p(y=0)，其中y=1表示正样本，y=0表示负样本，同时假定条件概率密度函数符合高斯分布

(4)

式(4)中的标量参数是被增量更新的，如式(5)所示(以y=1为例)

(5)

式中：参数λ是学习速率；μ1和σ1分别表示正样本第i个特征的均值和标准差。定义如式(6)(n是样本个数)

(6)

CT算法的基本算法流程如下，对于每一帧图像：

1)提取相应的正负样本用于更新分类器：在上一帧跟踪目标的位置附近选取若干个正样本图像块，在远离跟踪目标的位置选取若干个负样本图像块。根据选取的正负样本提取特征向量，并利用稀疏矩阵对特征作降维，输出低维特征以更新贝叶斯分类器参数。

2)利用更新后的分类器确定当前帧中目标的新位置：为了确定当前帧中目标的新位置坐标，在上一帧跟踪目标的位置附近选取若干个样本图像块，采用同样方法得到相应的低维向量特征，输入分类器后得到的概率最大的候选样本即为当前帧中目标位置。

3压缩感知跟踪算法的改进

本文针对压缩感知跟踪算法存在的缺陷提出相应的改进策略，使得改进后的算法能够有效处理遮挡和尺度变化问题，并能在目标消失后重现时再发现目标，从而实现对目标的长时间锁定跟踪。

3.1增加尺度变化

利用CT算法对场景内的目标进行跟踪时，由于当前帧的候选样本是在上一帧跟踪结果周围一定半径范围内选取的若干尺寸相同的矩形框中的图像，然后对所有的候选样本提取相应的特征向量并输入分类器，最终选取置信度最大的样本作为当前帧的跟踪结果。CT算法采集的样本的尺寸始终和初始目标框一致，不能够进行自适应的缩放。但是在实际视频中，目标尺寸可能会在运动过程中放大或者缩小，这就导致CT算法分类器参数被错误更新，最终导致跟踪失败。

CT算法从当前帧候选样本中选取置信度最大的样本作为跟踪结果，然而噪声和误差使得置信度最大的候选样本往往不能最接近目标的真实位置。因此，本文选取置信度最大的前10个样本作为初始的候选样本，并在每个样本附近一定半径范围内采用三种尺度的矩形框采样产生更多的候选样本。最后，采用归一化相关系数(NCC)算法计算每个候选样本与上一帧跟踪结果的相关系数，选取最大相关系数对应的候选样本作为跟踪结果。假设上一帧的目标尺度是s0=1，则当前帧的三种尺度分别是s1=1-σ，s2=1和s3=1+σ，分别对应于目标尺寸缩小，不变和放大三种情况。在文献[1]中，作者通过卷积的性质推导证明了利用尺度变化的特征模板可以对不同大小的目标进行特征提取，并使最终得到的样本特征值依然满足一定的统计规律，即具有尺度不变性。假定当前帧跟踪结果与目标真实位置吻合，则分类器参数的更新没有引入噪声和误差。与传统的在上一帧跟踪结果周围采用不同尺度的矩形框进行搜索的方法相比，该方法不仅减少了待匹配样本的数量，降低了计算量，而且减轻了累积误差带来的跟踪漂移问题。

3.2引入遮挡判定

由式(5)可知CT算法的分类器参数的更新是以恒定的学习速率逐帧进行的。它基于这样的假设：每一帧的跟踪结果都是和目标真实位置相吻合且没有被遮挡。但是当遇到目标被遮挡或者目标尺寸发生变化时，这样的假设就不成立了。当前跟踪结果的外观模型和目标的外观模型之间的误差会导致分类器参数被错误更新。同时，分类器参数将进一步影响下一帧的跟踪结果。这样，误差逐步积累，最终将导致跟踪漂移甚至跟踪失败。针对这一问题，本文提出了一种遮挡判定策略，在判定目标被遮挡时，分类器参数停止更新，并保存此时学到的外观模型，用于目标的再发现。

在目标由未被遮挡到完全被遮挡的过程中，跟踪窗口图像逐渐发生变化。跟踪窗口图像和真实目标图像的相似度越来越小，因此，通过观察相似度的变化可以判断目标是否发生遮挡。具体的实施方法如下：

本文采用滑动窗口的方式从第一帧开始选取连续N帧跟踪窗口图像，表示为X={xt+1,xt+2,…,xt+N}。其中，xt+1代表未发生遮挡的目标图像，N是一个根据实际情景设置的经验值。由于目标由未被遮挡到被完全遮挡的过程中，整体特征发生很大的变化，因此本文采用归一化的颜色直方图作为跟踪结果图像的外观表达，并通过计算颜色直方图之间的巴氏距离得到两幅图像之间的相似性。令Ht+i代表xt+i的归一化颜色直方图，xt+i与xt+j之间的相似度ρi,j表示为

(7)

式中：ρi,j越大表示两幅图像相似度越高。依次计算xt+i(i=2,…,N)与xt+1之间的相似度ρ1,i。通过分析ρ1,i的变化来判断目标是否发生遮挡。如果ρ1,i整体趋于减小，并且ρ1,N小于阈值Tmin，则跟踪结果图像发生了比较大的变化，可以认为存在目标被遮挡的情况，如图1所示。此时，停止CT跟踪器，并保存xt+1时学到的目标外观模型，由检测器开始检测目标；如果ρ1,N大于阈值Tmax，则判定不存在目标被遮挡的情况；如果ρ1,N介于Tmin与Tmax之间，则情况待定，下一滑动窗口的起始位置为max{i:ρ1,i>Tmax}(i=2,…,N)。该方法对遮挡的判定虽然存在一定的滞后，但是因为保存了遮挡发生前学到的目标外观模型，因此并没有因为遮挡而引入误差和噪声。

a　跟踪结果

b　相似度变化图1　进入遮挡过程跟踪结果图像及相似度变化

3.3目标的再发现

从目标被判定遮挡时起，CT算法停止跟踪，为了实现长时间的目标锁定跟踪，本文启动在线生成的检测器寻找再次出现的目标。

从保存的目标图像与背景图像中提取Hr特征，并利用该特征在线训练得到SVM分类器，并用它来实现目标的再发现。本文认为目标再次出现时，外观模型和遮挡前相比较并没有发生大的变化。该方法主要包括以下两个阶段。

1)训练阶段：假设在遮挡发生前跟踪结果是准确的，正样本就是每一帧的跟踪结果，负样本则是在遮挡前跟踪结果周围较远的位置随机选取的矩形图像片，如图2所示。

图2　正负样本的选取(黑线代表正样本，白线代表负样本)

2)搜索阶段：在判定目标被遮挡后，检测器开始检测被遮挡的目标。采用与目标初始尺寸大小一样的滑动矩形窗口全图搜索目标。由于检测窗口尺寸是固定的，所以在检测到目标后，为了获取更精确的目标位置，利用保存的目标外观模型(即分类器参数)，在目标周围选取多种尺寸的模板，提取特征向量，输入分类器，选取置信度最大的窗口作为目标的起始位置。

4实验结果与分析

为了验证本文提出的算法的有效性，选取一些存在尺度变化和遮挡情况的公共数据集和本实验室的数据集做了一系列测试，并与CT算法进行了比较。重要参数设置如下：尺度变化因子σ=0.05，遮挡判定的滑动窗口大小N=8～15，阈值Tmin=0.35，Tmax=0.65。

在图3a和图3b中，目标在运动过程中尺寸分别放大和缩小，由于原CT算法跟踪窗口尺寸固定不变，影响了正负样本的采集，目标外观模型更新错误，使得跟踪的准确性和覆盖率较低，更坏的情况会导致跟踪漂移甚至失败。本文提出的算法使得跟踪窗口大小自适应目标尺寸变化，无论在准确性还是覆盖率上都优于原CT算法，目标外观模型也得到更加准确的更新。

a　CarScale

b　Caviar图3　尺度变化对跟踪结果的影响(深色代表CT算法，浅色代表本文算法)

在图4a和图4b中，目标在运动过程中分别被不同物体遮挡，原CT算法以固定的学习速率在线逐帧更新目标外观模型，因此在发生遮挡时，背景信息被错误的引入，从而产生错误的外观模型，导致跟踪逐渐漂移并最终失败。本文提出的算法引入遮挡判定机制，在判定目标发生遮挡时，停止跟踪并保存遮挡前学到的目标外观模型，启动在线生成的目标检测器，在再次发现目标时利用保存的目标外观模型确定精确位置，继续跟踪目标。和原CT算法相比，改进后的算法可以更好地处理遮挡问题，能够实现长时间锁定跟踪。

a　David

b　Our Video Test图4　遮挡对跟踪结果的影响(深色代表CT算法，浅色代表本文算法)

5小结

本文针对原CT算法存在的跟踪窗口尺寸不自适应变化，无法有效处理遮挡和跟踪失败后目标再发现等情况的缺陷，提出了相应的改进策略。首先，选取置信度大小前十的候选样本，通过多尺度外观模型再匹配的方法，实现了跟踪窗口随着目标尺寸自适应变化，提高了跟踪的精度；此外，通过分析滑动窗口内跟踪窗口图像的归一化颜色直方图的变化，判定目标是否发生遮挡。在发生遮挡时停止跟踪并采用Haar特征在线训练得到SVM分类器，通过SVM分类器和保存的目标外观模型由粗到细搜索，再次发现目标并确定目标的精确位置，这样就解决了因目标遮挡导致的跟踪失败问题，实现了对目标的长时间锁定跟踪。本文提出的改进策略具有普适性，对不同的跟踪算法均适合。实验结果表明，本文提出的算法在目标尺寸发生变化和被遮挡的情况下能够做到长时间锁定跟踪。

参考文献：

[1]ZHANG K H，ZHANG L，YANG M H. Real-time compressive tracking[C]//Proc. 12th European Conference on Computer Vision. Florence， Italy：IEEE， 2012：864-877.

[2]BABENKO B， YANG M H， BELONGIE S. Visual tracking with online multiple instance learning[C]//Proc.IEEE Conference on Computer Vision and Pattern Recognition. Miami， FL：IEEE， 2006：983-990.

[3]LI H X， SHEN C H， SHI Q F. Real-time visual tracking using compressive sensing[C]//Proc. IEEE Conference on Computer Vision and Pattern Recognition. Providence， RI：IEEE， 2011：1305-1312.

[4]COLLINS R T， LIU Y X， LEORDEANU M. Online selection of discriminative tracking features[J]. IEEE transations on pattern analysis and machine intelligence， 2005， 27(10)：1631-1643.

[5]KALAL Z， MIKOLAJCZYK K， MATAS J. Tracking learning detection[J]. IEEE transactions on pattern analysis and machine intelligence(S0162-8828)， 2011， 6(1)：1-14.

[6]DONOHO D. Compressed sensing[J]. IEEE transactions on information theory(S0018-9448)， 2005， 52(4)：1289-1306.

李宏波，硕士生，主要研究行人跟踪；

郑世宝，教授，主要研究网络多媒体通信、智能视频监控以及老人健康信息技术；

周芹，博士生，主要研究行人重识别。

责任编辑：时雯

Improved long-time compressive tracker

LI Hongbo，ZHENG Shibao，ZHOU Qin

(InstituteofImageCommunicationandNetworkEngineering，ShanghaiJiaotongUniversity，Shanghai200240，China)

Abstract:Compressive tracker is famous for its simplification and efficiency. However，there still exists a few problems to be solved. For example， only fixed-size tracking windows can be generated，besides，the problem of occlusion as well as re-identification of the target after a track failure is not well handled. To address the issues mentioned above， an improved long-time compressive tracker is proposed. Through multi-scale appearance matching of the target，tracking windows adaptive to the object size are generated. Besides，the change of the global feature of consecutive frames in a sliding window is analyzed to see if an occlusion occurs. Finally，to solve the problem of drift，an online detector using Haar features is learned to re-identify the lost object. The experimental results demonstrate that our algorithm performs better than the CT algorithm in robustness and precision.

Key words:object tracking； compressive tracking； adaptive size； long-time tracking

中图分类号：TN919.8

文献标志码:A

DOI：10.16280/j.videoe.2016.04.005

作者简介：

收稿日期：2015-11-04

文献引用格式：李宏波，郑世宝，周芹. 一种改进的长时间压缩感知跟踪算法[J].电视技术，2016，40(4)：22-26.

LI H B，ZHENG S B，ZHOU Q. Improved long-time compressive tracker [J].Video engineering，2016，40(4)：22-26.