CT文章翻译

实时的压缩跟踪

张开华

摘要

由于受姿态变化、关照变化、遮挡以及运动模糊等因素的影响，导致开发一个有效的且高效的外表模型用于目标跟踪是一项具有挑战性的任务。现有的跟踪算法通常采用从最近帧中观察到的样本更新模型。虽然有很多成功的例子，但是，仍然有很多问题需要解决。第一，尽管这些自适应的模型是数据独立的，但是在开始使，算法没有充分的学习数据。第二，联机学习算法通常会遇见跟踪漂移（drift）问题，由于自身学习的问题，一些没有对齐的样本可能被添加到模型中，从而导致模型的性能退化。在这篇文章中，我们提出一个简单但有效且高效的跟踪算法，此算法采用了基于特征的外表模型，这些特征从数据独立的多尺度图像特征空间中选取获得。我们的外表模型采用非自适应的随机投影技术，此技术保持了目标图形特征空间的结构性。采用一个非常稀疏的矩阵有效的为外表模型提取特征。我们采用同样的稀疏矩阵压缩前景和背景的样本。跟踪的任务可以被构造成一个通过朴素贝叶斯分类器进行二分类的问题，此分类器在压缩域内被联机更新。提出的压缩跟踪算法能够实时运行且在一些具有挑战性的序列中进行测试，根据效率、精确性和健壮性评价，结果优越于其他经典的跟踪算法。

1 引言

尽管在一些文献中提出了大量的跟踪算法，由于姿态、光照、遮挡、运动等因素导致目标外形的变化，因此，目标跟踪仍然是一个具有挑战性的问题。一个有效的外表模型是跟踪算法成功的重要基础，在最近几年已经引起人们的广泛注意[1-10]。基于外表模型可以将跟踪算法可以被概括为通用的算法[1,2,6,9,10]和区分的算法[3-5,7,8]两种类型。

通用的跟踪算法学习一个模型来表示目标对象且使用此目标对象在图像区域内进行搜索。Black等[1]学习一个脱机的子空间模型来表示感兴趣对象，实现目标跟踪。IVT[6]算法采用增量的子空间模型来适应目标外形的变化。最近，稀疏表示被用在L1跟踪算法中，其中一个对象由目标和一些模板的稀疏线性融合所构成[10]。然而，这个跟踪器(tracker)的计算复杂性很高，因此，限制了它在实时场景中的应用。Li等[9]进一步拓展了L1算法，他们采用正交匹配追踪算法(orthogonal matching pursuit algorithm)有效的解决了优化问题。尽管有很多成功的在线通用跟踪算法，但是仍然有一些问题需要解决。第一，为了在线学习一个外表模型，需要从连续帧中采集大量的训练样本。因此，开始只有少量的样本，很多跟踪算法常常假设在训练期间目标的外形不会发生改变。然而，如果在开始时，目标的外形发生较大的变化，那么很有可能会发生飘移(drift)问题。第二，当从当前目标位置多重采样时，由于需要适应这些潜在的不匹配样本，通常会导致飘移问题[8]。第三，这些通用的跟踪算法没有采用背景信息，这些背景信息可以提高跟踪的稳定性(stability)和精确性(accuracy)。

为了寻找一个决策边界将目标对象从背景中分离，区分的跟踪算法提出将跟踪问题作为二分类问题。Avidan[3]采用支持向量机分类器拓展了基于光流的目标跟踪算法。Collins等[4]证明了，大部分的在线学习特征都能够从背景中区分目标对象。Grabner等[5]提出一种在线增强算法来选择特征用于跟踪。然而，这些跟踪器(trackers)[3-5]仅仅使用一个正样本(例如，当前的跟踪位置)和少量的负样本来更新分类器。由于采用噪声和潜在的不匹配样本来更新背景模型，常常会导致跟踪飘移问题。Grabner等[7]提出一种在线半监督学习算法来解决飘移问题，他们仅仅在第一帧中标记样本，所有的其他样本都是未标记的。Babenko[8]将多实例学习(multiple instance learning)引入到在线学习跟踪中，在算法中只考虑集合(bags or sets)中的正样本和负样本。最近，文献[11]开发一种半监督学习算法，算法采用带结构化约束的在线分类器来选取正样本和负样

本。

在这篇文章中，我们提出一种有效的和高效的跟踪算法，算法使用基于压缩域特征的外表模型。我们压缩跟踪算法的主要组成部分如图1所示。我们的外表模型生成的对象可以采用基于压缩域的特征获得很好的表达。同时，我们的算法也是区分性的算法，我们使用这些特征通过朴素贝叶斯分类器从背景中区分目标对象。在我们的外表模型中，被选取的特征是信息保持的且从基于压缩感知理论[12,13]的多尺度图像特征空间中实现非自适应降维。结果证明，少量的随机产生的线性矩阵能够保持大量的显著信息，且如果信号是像自然图像和声音这样可压缩的信号，那么几乎完全可以重建此信号[12-14]。我们采用一个非常系数的矩阵，此矩阵满足受限等距特性(restricted isometry property, RIP[15])，因此，便于从图像特征空间投影到低维的压缩子空间。为了跟踪，正样本和负样本是采用同样尺度的举证被投影过后的(例如，被压缩的)且通过一个简单的朴素贝叶斯在线学习分类器即可实现区分。根据效率、精确性和健壮性，在一些具有挑战性的序列中测试，提出的压缩跟踪算法能够实时运行且优越于其他的经典算法(state-of-the-art)。

图1压缩跟踪算法的主要组成部分

2 基础知识

我们给出在跟踪算法中使用的压缩感知理论的基础知识。 2.1 随机投影

一个随机矩阵R??n?m它的行具有相同的长度，将数据从高维图像空间x??m投影到低维数据空间

v??n，如式(1)所示：

v?Rx(1)

此处，n的值远小于m的值。确实，我们期望R提供一个稳定的嵌入，从而近似的保持所有成对原始信号之间的距离。Johnson Lindenstrauss lemma[16]认为，如果向量空间中的点被投影到一个随机选择的具有稳定维度的高维子空间中，那么向量空间中的点之间的距离被保持的概率较高。Baraniuk等[17]证明了在压缩感知邻域，随机矩阵不但满足JphnsonLindenstrauss lemma的观点，而且还满足受限等距特性(retrictedisometry property)。因此，如果式(1)中的随机矩阵R满足Johnson-Lindenstrauss引理且x是像声音或图像这样的压缩信号，那么我们能够从高维的v中重建出具有较小误差的x。我们可以确保v保持在x中的所有信息。这强

有力的理论激励我们采用低维随机投影矩阵来分析高维信号。在提出的跟踪算法中，我们使用一个非常稀疏的矩阵，不但能够满足Johnson-Lindenstrauss引理，而且还能够被有效的计算。 2.2随机维度矩阵

通常，满足受限等距属性(restricted isometry property, RIP)的矩阵是随机高斯矩阵(random Gaussian matrix)，R??n?m，其中，ri,j?N?0,1?，随机高斯矩阵在最近的一些工作中被使用到[9,14,18]。然而，由

于随机高斯矩阵是稠密矩阵，当m的取值较大时，内存和计算量仍然很大。在这篇文章中，我们采用一个非常稀疏的随机投影矩阵，定义如下式(2)所示：

1?1withprobability?2s?1(2) ?ri,j?s??0withprobablity1?2s?1??1widthprobability?2s?Achlioptas[16]证明了，当s的取值为2或3时，此矩阵满足Johnson-Lindenstrauss引理。这个矩阵是非常容

易计算的，且只需要一个均匀分布的随机数产生器。更重要的是，当s的取值为3时，此矩阵是非常稀疏的，可以节省三分之二的计算量。此外，Li等[19]证明，当s?O?m?x???m?时，此矩阵是接近正态分布。甚

至，当s?m/log?m?时，随机投影矩阵的精确性几乎接近于传统矩阵(ri,j?N?0,1?)。在这篇文章中，我们设置s?m/4计算一个非常稀疏的随机矩阵。对于矩阵R的每一行只有4个实体需要计算。因此，计算复杂度仅为O?cn?，它是非常低的。此外，我们只要存储矩阵R的非零元素，从而只需要少量的内存空间。

3 提出的算法

在这部分，我们将详细的介绍提出的跟踪算法。跟踪问题被转化为检测任务，我的算法如图1所示。我们假设跟踪窗口在第一帧中就被确定。在每一帧中，我们从接近当前目标位置采集一些正样本和原理目标位置采集一些负样本用于更新分类器。为了预测目标在下一帧中的位置，我们从当前目标位置采集一些样本，确定其中一个具有最大化分类结果。(To predict the object location in the next frame, we draw some samples around the current location and determine the one with the maximal classification score.)

图2压缩高维向量x到低维向量v的图形表示。在矩阵R中，黑色、灰色和白色矩形分别

代表负样本、正样本和零元素。蓝色箭头表示，矩阵R中某一行中的一个非零元素对x进行采样等于一个矩形滤波对输入图像的固定位置进行卷积。

3.1 有效的降维

对于每一个样本z??w?h，为了处理尺度问题，我们采用如下方式重新表示：在多尺度空间

?h1,1,?,hw,h?内采用一个矩形滤波器集合对z进行卷积操作，具体定义如式(3)所示：

?1,1?x?i,1?y?j (3) hi,j?x,y????0,otherwise其中，i，j分别表示矩形滤波器的宽度和高度。我们采用每一个滤波后的图像表示?wh中的一个列向量，

Tm且将这些向量串联在一个形成了一个维度较高的多尺度图像特征向量，即x??x1,?,xm???2，其中

610m?m??wh?，m的维度在?10,10??范围内。我们采用一个稀疏的矩阵R(在式(2)中所示，其中s?4)

将x投影到一个低维的向量空间v??。随机矩阵R只需要一次脱机(off-line)计算，在整个跟踪过程中都是固定不变的。对于式(2)中的稀疏矩阵R，计算量是很低的。如图2所示，我们只需要存储矩阵R中的非

零元素，输入图像中矩形滤波的位置与矩阵R中每一行的非零元素相对应。因此，使用矩阵R可以有效的计算出v，采用积分图像可以有效的计算出稀疏的矩形特征[20]。

n3.2 分析低维压缩特征

如图2所示，低维特征v??中的每一个元素vi是在不同尺度的空间分布特征的线性融合。由于在尺度矩阵(measurement matrix)中的系数(coefficients)可能是正值或负值(如式(2)所示)，压缩特征计算相对亮度的差，采用的方式与通用的haar-like特征类似(如图2所示)。Haar-like特征被广泛的用于对象检测，在文献[8,20,21]中获得了成功验证。通常这些基本类型的Haar-like特征被设计用于不同的任务[20,21]。大量的Haar-like特征使得计算负载较高。这个问题可以通过boosting算法选取一些重要的特征实现缓解[20,21]。最近，Babenko等[8]采用通用的Haar-like特征，其中每一个特征都是随机产生的矩形特征的线性组合，且采用在线boosting算法选择少量的特征用于实现目标跟踪。在我们的工作中，采用一个非常系数的尺度矩阵对大量的Haar-like特征进行压缩采样。压缩感知理论确保我们算法提取的特征能够保持原始图像的所有信息。因此，我们可以在压缩域内有效的分类被投影的特征，且没有维数灾难问题。

n