目前，粒子滤波方法已被成功应用到目标追踪中：若追踪过程中第(t-1) 帧的追踪目标状态为粒子${q_{t - 1}}$，则第t帧的追踪目标可能的状态记为$p({q_t}|{q_{t - 1}})$，且第t帧的观测为$p({y_t}|{q_t})$，其中${y_t}$为第t帧的观测值。稀疏表示追踪给出了$p({y_t}|{q_t})$的具体形式，并根据最小重构误差得到目标的追踪结果${y_t}$。

对于一个给定目标模板的图像集合${\mathit{\boldsymbol{T}}} = [{{\mathit{\boldsymbol{T}}}_1},{{\mathit{\boldsymbol{T}}}_2}, \cdots ,{{\mathit{\boldsymbol{T}}}_n}] \in {{\mathit{\boldsymbol{R}}}^{d \times n}}(d > > n)$($d$表示图像的维数，$n$表示模板基向量的个数)，T的每一列都是通过零均值化后得到的向量，因此对于一个候选目标${\mathit{\boldsymbol{y}}}$可以近似通过模板的线性组合表示为：

式中，e表示高斯噪声；I表示琐碎模板。文献[15, 22]提出的稀疏表示追踪模型为：

式中，${\mathit{\boldsymbol{D}}} = [{\mathit{\boldsymbol{T}}},{\mathit{\boldsymbol{I}}}]$表示追踪模板；${\mathit{\boldsymbol{x}}} = {[{\mathit{\boldsymbol{z}}},{\mathit{\boldsymbol{e}}}]^{\rm{T}}}$；$\lambda $表示正则参数，用来平衡保真项和正则项。若考虑粒子之间的关系，则可给出稀疏追踪模型^[17]：

式中，${\mathit{\boldsymbol{Y}}} = [{{\mathit{\boldsymbol{y}}}_1},{{\mathit{\boldsymbol{y}}}_2}, \cdots ,{{\mathit{\boldsymbol{y}}}_m}]$表示所有侯选目标；$\left\| {\mathit{\boldsymbol{X}}} \right\|_{p,q}^q = \sum\nolimits_{i = 1}^{n + d} {{{({{\left\| {{{\mathit{\boldsymbol{X}}}_i}} \right\|}_p})}^q}} (p \ge 1,q \le 1)$；${\left\| \cdot \right\|_p}$是L_P范数；正则项${\left\| {\mathit{\boldsymbol{X}}} \right\|_{p,q}}$能更好地提取粒子之间的相似性并能有效去除模板的冗余信息。

尽管上述模型在一定程度上解决了部分遮挡、光照变化、姿势改变和背景混杂等影响，但太过简单地考虑噪声的分布情况，因此面对一些复杂的噪声分布情况可能会出现跟踪失败。为此下面假设噪声服从高斯拉普拉斯分布，即：

式中，S表示拉普拉斯噪声；E表示高斯噪声。给出同时稀疏追踪模型：

式中，${\mathit{\boldsymbol{X}}} = {\left[ {{\mathit{\boldsymbol{Z}}},{\mathit{\boldsymbol{E}}}} \right]^{\rm{T}}}$。但对于一个给定的视频序列，目标并不总处于被污染状态，设已追踪到目标对应的拉普拉斯噪声为${{\mathit{\boldsymbol{S}}}_t}$(表示S的第$t$列)，因此可给出自适应的同时稀疏追踪模型为：

1) 噪声${\left\| {{{\mathit{\boldsymbol{S}}}_t}} \right\|_2} \le \tau $时，模型变为：

2) 噪声${\left\| {{{\mathit{\boldsymbol{S}}}_t}} \right\|_2} > \tau $则模型变为：

式中，$\tau $为给定噪声能量的阈值；${\lambda _1}$和${\lambda _2}$为模型的正则参数，分别用来控制表示系数X的稀疏程度以及噪声S的能量大小。

模型求解：式(6) 和式(7) 的目标函数是一个凸优化。使用交替方向乘子方法(alternating direction method multipliers, ADMM)求解优化问题(7) 如下：

首先，将约束问题变为无约束问题：

式中，${\tau _ + }({\mathit{\boldsymbol{X}}}) = \sum\limits_{i = 1}^d {{\tau _ + }({{\mathit{\boldsymbol{x}}}_i})} $是一个指示函数。因此优化问题(7) 有如下的等价形式：

式中，${{\mathit{\boldsymbol{V}}}_1},{{\mathit{\boldsymbol{V}}}_2},{{\mathit{\boldsymbol{V}}}_3}$为对偶变量，式(9) 进一步优化为：

式中，

式(10) 的增广拉格朗日函数为：

式中，$\beta $表示拉格朗日乘子；${\mathit{\boldsymbol{U}}} = {[{{\mathit{\boldsymbol{U}}}_1},{{\mathit{\boldsymbol{U}}}_2},{{\mathit{\boldsymbol{U}}}_3}]^{\rm{T}}}$。式(11) 可分解为3个子优化问题：

因此根据极值原理，只需要对上述子问题求一阶导数，可获得式(11) 的最优解：

同理，对于式(6) 得到以下解：

这样通过对子问题的分析与求解，获得了式(6) 和式(7) 解的一般形式，数值求解见算法1和2。

算法1：问题(6) 的ADMM求解算法

初始化：$k=0$，${{\mathit{\boldsymbol{X}}}^{(0)}}$，Y，正则参数${\lambda _1}$，${\lambda _2}$，对偶变量${{\mathit{\boldsymbol{V}}}_1}^{(0)}$，${{\mathit{\boldsymbol{V}}}_2}^{(0)}$，${{\mathit{\boldsymbol{V}}}_3}^{(0)}$，拉格朗日乘子${{\mathit{\boldsymbol{U}}}_1}^{(0)}$，${{\mathit{\boldsymbol{U}}}_2}^{(0)}$，${{\mathit{\boldsymbol{U}}}_3}^{(0)}$，收敛误差$\varepsilon $，惩罚因子$\beta $。

1) 迭代

2) ${{\mathit{\boldsymbol{V}}}_{1}}^{(k+1)}\leftarrow {[\beta (\mathit{\boldsymbol{D}}{{\mathit{\boldsymbol{X}}}^{(k)}}-\mathit{\boldsymbol{U}}_{1}^{(k)})+\mathit{\boldsymbol{Y}}]}/{(1+\beta )}\;$

3) ${{\mathit{\boldsymbol{V}}}_{2}}^{(k+1)}\leftarrow \rm{shrink}({{\mathit{\boldsymbol{X}}}^{(k)}}-\mathit{\boldsymbol{U}}_{2}^{(k)},{{{\lambda }_{1}}}/{\beta }\;)$

4) ${{\mathit{\boldsymbol{V}}}_{3}}^{(k+1)}\leftarrow \max (0,{{\mathit{\boldsymbol{X}}}^{(k)}}-\mathit{\boldsymbol{U}}_{3}^{(k)})$

5) ${{\mathit{\boldsymbol{U}}}_{1}}^{(k+1)}\leftarrow {{\mathit{\boldsymbol{U}}}_{1}}^{(k)}-(\mathit{\boldsymbol{D}}{{\mathit{\boldsymbol{X}}}^{(k+1)}}-\mathit{\boldsymbol{V}}_{1}^{(k+1)})$

6) ${{\mathit{\boldsymbol{U}}}_{2}}^{(k+1)}\leftarrow {{\mathit{\boldsymbol{U}}}_{2}}^{(k)}-({{\mathit{\boldsymbol{X}}}^{(k+1)}}-\mathit{\boldsymbol{V}}_{2}^{(k+1)})$

7) ${{\mathit{\boldsymbol{U}}}_{3}}^{(k+1)}\leftarrow {{\mathit{\boldsymbol{U}}}_{3}}^{(k)}-({{\mathit{\boldsymbol{X}}}^{(k+1)}}-\mathit{\boldsymbol{V}}_{3}^{(k+1)})$

8) ${{\mathit{\boldsymbol{X}}}^{(k+1)}}\leftarrow {{({{\mathit{\boldsymbol{D}}}^{\rm{T}}}\mathit{\boldsymbol{D}}+2\mathit{\boldsymbol{I}})}^{-1}}[{{\mathit{\boldsymbol{D}}}^{\rm{T}}}(\mathit{\boldsymbol{V}}_{1}^{(k+1)}+\mathit{\boldsymbol{U}}_{1}^{(k+1)}\rm{+}\mathit{\boldsymbol{V}}_{2}^{(k+1)}+\mathit{\boldsymbol{U}}_{2}^{(k+1)}+\mathit{\boldsymbol{V}}_{3}^{(k+1)}+\mathit{\boldsymbol{U}}_{3}^{(k+1)}]$

9) 直到$\left\| \mathit{\boldsymbol{G}}{{\mathit{\boldsymbol{X}}}^{(k+1)}}+\mathit{\boldsymbol{B}}{{\mathit{\boldsymbol{V}}}^{(k+1)}} \right\|\le \varepsilon $

输出：最优解${{\mathit{\boldsymbol{X}}}^{(k+1)}}$

算法2：问题(7) 的ADMM求解算法

初始化：$k=0$，${{\mathit{\boldsymbol{X}}}^{(0)}}$，${{\mathit{\boldsymbol{S}}}^{(0)}}$，Y，正则参数${{\lambda }_{1}}$，${{\lambda }_{2}}$，对偶变量${{\mathit{\boldsymbol{V}}}_{1}}^{(0)}$，${{\mathit{\boldsymbol{V}}}_{2}}^{(0)}$，${{\mathit{\boldsymbol{V}}}_{3}}^{(0)}$、拉格朗日乘子${{\mathit{\boldsymbol{U}}}_{1}}^{(0)}$，${{\mathit{\boldsymbol{U}}}_{2}}^{(0)}$，${{\mathit{\boldsymbol{U}}}_{3}}^{(0)}$，收敛误差$\varepsilon $，惩罚因子$\beta $。

1) 迭代

2) ${{\mathit{\boldsymbol{V}}}_{1}}^{(k+1)}\leftarrow {[\beta (\mathit{\boldsymbol{D}}{{\mathit{\boldsymbol{X}}}^{(k)}}-\mathit{\boldsymbol{U}}_{1}^{(k)})+\mathit{\boldsymbol{Y}}-{{\mathit{\boldsymbol{S}}}^{(k)}}]}/{(1+\beta )}\;$

3) ${{\mathit{\boldsymbol{V}}}_{2}}^{(k+1)}\leftarrow \rm{shrink}({{\mathit{\boldsymbol{X}}}^{(k)}}-\mathit{\boldsymbol{U}}_{2}^{(k)},{{{\lambda }_{1}}}/{\beta }\;)$

4) ${{\mathit{\boldsymbol{V}}}_{3}}^{(k+1)}\leftarrow \max (0,{{\mathit{\boldsymbol{X}}}^{(k)}}-\mathit{\boldsymbol{U}}_{3}^{(k)})$

5) ${{\mathit{\boldsymbol{S}}}^{(k+1)}}\leftarrow \rm{shrink}(\mathit{\boldsymbol{Y}}-\mathit{\boldsymbol{V}}_{1}^{(k)},{{\lambda }_{2}})$

6) ${{\mathit{\boldsymbol{U}}}_{1}}^{(k+1)}\leftarrow {{\mathit{\boldsymbol{U}}}_{1}}^{(k)}-(\mathit{\boldsymbol{D}}{{\mathit{\boldsymbol{X}}}^{(k+1)}}-\mathit{\boldsymbol{V}}_{1}^{(k+1)})$

7) ${{\mathit{\boldsymbol{U}}}_{2}}^{(k+1)}\leftarrow {{\mathit{\boldsymbol{U}}}_{2}}^{(k)}-({{\mathit{\boldsymbol{X}}}^{(k+1)}}-\mathit{\boldsymbol{V}}_{2}^{(k+1)})$

8) ${{\mathit{\boldsymbol{U}}}_{3}}^{(k+1)}\leftarrow {{\mathit{\boldsymbol{U}}}_{3}}^{(k)}-({{\mathit{\boldsymbol{X}}}^{(k+1)}}-\mathit{\boldsymbol{V}}_{3}^{(k+1)})$

9) ${{\mathit{\boldsymbol{X}}}^{(k+1)}}\leftarrow {{({{\mathit{\boldsymbol{D}}}^{\rm{T}}}\mathit{\boldsymbol{D}}+2\mathit{\boldsymbol{I}})}^{-1}}[{{\mathit{\boldsymbol{D}}}^{\rm{T}}}(\mathit{\boldsymbol{V}}_{1}^{(k+1)}+\mathit{\boldsymbol{U}}_{1}^{(k+1)}+\mathit{\boldsymbol{V}}_{2}^{(k+1)}+\mathit{\boldsymbol{U}}_{2}^{(k+1)}+\mathit{\boldsymbol{V}}_{3}^{(k+1)}+\mathit{\boldsymbol{U}}_{3}^{(k+1)}]$

10) 直到$\left\| \mathit{\boldsymbol{G}}{{\mathit{\boldsymbol{X}}}^{(k+1)}}+\mathit{\boldsymbol{B}}{{\mathit{\boldsymbol{V}}}^{(k+1)}} \right\|\le \varepsilon $

输出：最优解${{\mathit{\boldsymbol{X}}}^{(k+1)}}$, ${{\mathit{\boldsymbol{S}}}^{(k+1)}}$

模板更新的好坏直接影响追踪的性能。在稀疏追踪模型中提出了用目标模板和琐碎模板相结合的模板更新方法，对于每一个追踪的目标y，如果y与模板的相似性很高，则不更新，否则将y引入模板中并剔除模板中权重较小的向量。引入琐碎模板是为了更好地解决目标遮挡问题，这种模板更新方法虽然在一定程度上可以减弱跟踪漂移现象，但是模板维数较高，提高了模型的计算代价，从而降低了追踪系统的实时性。下面用子空间学习和无监督学习相结合的模板更新方法来降低模板的维数，并且能避免模板更新过快而引入较大的误差。

若给定当前模板T，已追踪到的目标y以及噪声能量相似度$\tau $，则拉普拉斯噪声$\mathit{\boldsymbol{S}}=\mathit{\boldsymbol{Y}}-\mathit{\boldsymbol{TZ}}-\mathit{\boldsymbol{E}}$。如果${{\left\| \mathit{\boldsymbol{s}} \right\|}_{2}}\le \tau $，则对模板T进行更新：首先分别对T和y进行奇异值分解：

进一步给出$\tau $的等价定义, 令$c=\rm{mean}(\mathit{\boldsymbol{T}})$，则：

式中，$\tau $等价为目标与模板均值的反余弦，即余弦夹角。文献[4]提出增量子空间学习追踪算法，同理可使用奇异向量$\mathit{\boldsymbol{u}},\mathit{\boldsymbol{s}},\mathit{\boldsymbol{v}}$去增量更新$\mathit{\boldsymbol{U}},\mathit{\boldsymbol{S}},\mathit{\boldsymbol{V}}$，从而得到新的奇异向量${{\mathit{\boldsymbol{U}}}_{*}},{{\mathit{\boldsymbol{S}}}_{*}},{{\mathit{\boldsymbol{V}}}_{*}}$。新的模板可表示为：

考虑模板的维数较大，给定初始类个数为k，使用无监督学习K-means方法训练模板：

式中，$i$表示第$i$个样本；当${{\mathit{\boldsymbol{T}}}_{i*}}$属于类$k$时，${{r}_{ik}}=1$，否则${{r}_{ik}}=0$；${{\mathit{\boldsymbol{u}}}_{k}}$为所有属于类$k$的样本的平均值。因此新的模板变为${{\mathit{\boldsymbol{T}}}_{\rm{new}}}=[{{\mathit{\boldsymbol{u}}}_{1}},{{\mathit{\boldsymbol{u}}}_{2}},\cdots ,{{\mathit{\boldsymbol{u}}}_{k}}]$。

本文提出的模板更新不同于传统的模板更新，它强调选择对目标追踪具有重要贡献的模板，而避免使用琐碎模板，并通过K-means算法对模板进行无监督训练，大大剔除了模板的冗余信息，从而提高了追踪的实时性。

在目标追踪过程中，假设第(t-1) 帧的目标状态为${{q}_{t-1}}$，第t帧的所有观测为${{\mathit{\boldsymbol{Y}}}_{t}}$。目标状态更新和观测更新可以表示为：

式中，状态${{q}_{t}}$由6个仿射参数决定且彼此之间相互独立，即${{q}_{t}}=[{{t}_{x}},{{t}_{y}},\theta ,\varepsilon ,\mu ,\rho ]$，$\theta $、$\varepsilon $、$\mu $、$\rho $分别表示旋转角度、规模大小、长宽比和倾斜度；$[{{t}_{x}},{{t}_{y}}]$表示二维旋转参数；${{w}_{t}}$表示第t帧的粒子权重；$G({{q}_{t-1}},{{\delta }^{2}})$表示第t帧的目标状态，可以由服从均值为${{q}_{t-1}}$、方差为${{\delta }^{2}}$的高斯分布函数决定；而$p({{Y}_{t}}|{{q}_{t}})$可由同时稀疏L_{(p, q)}的最小重构误差得到：

在实际中${{w}_{t}}$通过粒子滤波算法自适应更新得到，细节见文献[15]；方差$\delta $=0.05，仿射参数由仿射矩阵逆变换得到。对应的自适应同时追踪算法，见算法3。

算法3：自适应同时稀疏追踪算法

输入：第t帧所有侯选粒子${{\mathit{\boldsymbol{Y}}}_{t}}=[\mathit{\boldsymbol{y}}_{t}^{1},\mathit{\boldsymbol{y}}_{t}^{2},\cdots ,\mathit{\boldsymbol{y}}_{t}^{m}]$、初始追踪目标$\mathit{\boldsymbol{y}}_{t}^{(0)}$、模板${{\mathit{\boldsymbol{D}}}_{t}}$、最大迭代次数Loop、收敛误差tol、余弦夹角阈值$\alpha $、正则参数${{\lambda }_{1}}$, ${{\lambda }_{2}}$。

1) 根据式(13) 计算追踪目标${{y}_{t}}$与模板均值的相似性，记为sim

2) 判断sim与$\alpha $的大小，并自适应地选择模型进行追踪

3) IF $\text{sim}<\alpha $

4) 选择算法1进行求解并获得稀疏系数矩阵X

5) ELSE $\text{sim}\ge \alpha $

6) 选择算法2求解得到稀疏系数X和噪声S

7) 根据式(12)，式(14) ~式(15) 自适应更新模板

8) 追踪目标$\mathit{\boldsymbol{y}}_{t}^{j}=\underset{1\le j\le m}{\mathop{\arg \max }}\,p(y_{t}^{j}|{{q}_{t}})$

输出:追踪目标$\mathit{\boldsymbol{y}}_{t}^{j}$和新的模板${{\mathit{\boldsymbol{D}}}_{\rm{new}}}$。

下面通过数值试验把本文提出的算法与其他5种具有很好追踪性能的算法进行比较，这5种追踪算法分别为核技巧的循环矩阵追踪(circulant structure of kernels, CSK)^[8]、加速梯度追踪(accelerated proximal gradient, L1APG)^[14]、多任务追踪(multi-task tracking, MTT)^[17]、稀疏原型追踪(sparse prototype tracking, SPT)^[23]以及稀疏联合追踪(sparse collaborative method, SCM)^[21]。所有的实验均基于Matlab 2012a，计算机内存为2 GB，CPU为Intel(R) Core(TM)i3。实验数据来源于文献[20]。

本次实验选择了14种不同的具有追踪挑战性的视频，其中包括遮挡、光照变化、背景混杂、姿势改变、低分辨率和快速运动等影响追踪结果的因素，如表 1所示。其中OV表示目标丢失，BC表示背景混杂，OCC表示完全遮挡，OCP表示部分遮挡，OPR表示旋转出平面，LR表示低分辨率，FM表示快速运动，SV表示大小变化。

在实验中参数设置如下:正则参数${{\lambda }_{1}}=0.1$，${{\lambda }_{2}}=0.1$，惩罚因子$\beta =0.1$，余弦角度阈值${{\alpha }_{\min }}=20$，${{\alpha }_{\max }}=35$，模板最大基向量个数为15，粒子采样数为600，图像块的大小为$25\times 25$，实验最大迭代次数Loop=20。参数${{\lambda }_{1}}$, ${{\lambda }_{2}}$均通过交叉验证方法得到，且${{\lambda }_{2}}$参数的调节满足如下规则，若噪声S的能量较大(即目标遭受较大的遮挡、外形变化或光照变化)，此时${{\lambda }_{2}}$的值应该较小，反之则较大。

本文实验采用的评价方法有3种，且每种评价方法都能在一定程度上解释追踪性能的好坏，分别为局部中心误差(center local error)、重叠率(overlap ratio)、曲线下的面积(area under curve, AUC)。

给定帧的真实目标框${{R}_{g}}$(ground truth)和追踪目标框${{R}_{t}}$(tracked target bounding)，设它们的中心位置分别为：${{p}_{g}}=({{x}_{g}},{{y}_{g}})$和${{p}_{t}}=({{x}_{t}},{{y}_{t}})$，则局部中心误差为$\text{CLE}={{\left\| {{p}_{g}}-{{p}_{t}} \right\|}_{2}}$，重叠率为：

式中，$\text{area}(\cdot )$表示在该区域的所有像素；AUC每一点的值表示重叠率大于给定阈值$\eta $时该视频追踪的成功率。特别地设定$\eta =0.5$，当重叠率$\text{OR}>0.5$时则认为该帧追踪成功。相关追踪结果如表 2~4所示，表 2中AOR表示总的平均重叠率，表 3中ACLE表示总的平均中心误差，表 4中ASR表示总的平均成功率，表中最好的两个结果分别用红色和蓝色表示。各算法追踪性能如图 1~3所示，图 1中平均重叠率越大表示追踪性能越好，图 2中平均中心误差越小表示追踪性能越好，图 3中曲线与x轴围成的面积越大表示追踪性能越好。

图  1  各种不同追踪算法的平均重叠率

图  2  各种不同追踪算法的平均中心误差

图  3  各种不同追踪算法的AUC曲线

为了方便描述，将本文提出的追踪算法简记为ASSAT算法(adaptive simultaneous sparse representation appearance tracking algorithm)。

1) 背景混杂和快速运动情形：图 4分别给出了快速运动和背景混杂的追踪效果，视频Deer包含快速运动因素。从Singer2可看到大部分算法都无法有效追踪到结果，在帧240时，有很多算法的追踪框偏离目标，漂移现象很严重，如SCM，CSK，MTT，L1APG，SPT等，只有ASSAT算法可以有效追踪到目标。在帧366时(视频结束)本文提出的依然可以有效追踪到目标，大大减弱了追踪漂移现象。在视频SUV中，开始时所有追踪算法均能有效追踪到目标，在帧560时，只有SCM, CSK和ASSAT算法可以追踪到目标，在第945帧时只有ASSAT可以有效追踪到目标。对于视频Deer而言，可以看到除了MTT算法大部分算法均能有效追踪到目标，另外可以看到SCM算法不太稳定，因在帧40时SCM算法偏离了追踪目标，出现跟踪漂移现象。ASSAT算法可以有效追踪背景混杂的视频序列是因为其采用了同时稀疏表示方法，该方法通过模板基的选择来刻画粒子之间的关系，对噪声污染较大的粒子给与了较低的稀疏权重，因此具有很强的噪声抗干扰性。

图  4  基于快速运动和背景混杂视频下的追踪效果

2) 姿势改变和光照变化情形：图 5和图 6分别给出了姿势改变和光照变化的追踪效果。从图 5中的Deduk视频可以看出所有的追踪算法都能有效追踪到目标(人脸)，但是ASSAT可以更加准确地追踪到人脸目标，而对于Skater2视频，大部分算法都无法准确跟踪到目标，因为目标姿势改变的太过频繁且改变的幅度较大，在第90帧时只有LIAPG, CSK和ASSAT算法可较为准确的追踪的目标，但在帧435时只有ASSAT和CSK能够追踪到目标，尽管追踪的不太精确。图 6可以看到几乎所有算法都可以对光照变化产生一定的抗干扰性，除了LIAPG和CSK算法有一些不太稳定。因此对于姿势改变不大的情况ASSAT算法还是可以有效的追踪到目标。

图  5  基于姿势改变和旋转视频下的追踪效果

图  6  基于光照变化视频下的追踪效果

3) 目标遮挡情形：图 7展示了目标遮挡对跟踪性能的影响，在Girl视频序列中可看到在帧458和帧500时，大部分算法都出现了跟踪漂移现象，不能有效追踪到目标，除了ASSAT，LIAPG和MTT算法，从Subway也可看到在帧41时，只有SCM, L1APG和ASSAT算法可有效追踪到目标，而在帧175时，除了SCM和ASSAT算法其他算法都出现了很大的跟踪漂移。通过比较可看出ASSAT算法能更好的解决目标遮挡问题，这是因为该算法考虑了遮挡对追踪的影响，它就像一个滤波器在追踪之前对噪声进行了有效剔除，去除了可能对追踪效果产生影响的不稳定的因素(遮挡、光照变化、背景混杂和姿势改变等)。

图  7  基于目标遮挡视频下的追踪效果

下面详细介绍模型中提到的拉普拉斯噪声和模板更新准则对追踪效果的具体影响。

传统的模板更新方法是直接通过追踪目标与模板的相似度进行更新，若相似度大于给定的阈值，则认为目标遭遇了较大的噪声污染，因此需要将追踪目标替代原始权值较小的模板向量，这样替换其实是比较粗糙的，因为引入了较大的噪声误差，这样就给下一帧目标的追踪造成了很多不确定性，而本文提出的新的模板更新方法则削弱了噪声影响。具体表现如下：

1) 新的模板更新方法有效权衡原始模板向量和新的追踪目标之间的权重，通过遗忘因子实现模板更新(具体见文献[4]);

2) 新的模板更新方法引入了K-means方法，可以有效地降低冗余模板向量，提高追踪的实时性，通过式(18) 可看到类中心的计算是通过加权平均得到的，因此也可有效地减弱噪声。

下面给出具体实验分别比较模板更新和拉普拉斯对实验效果的影响。实验数据选择序列Skater2，Dudek, SUV，Walking2，Subway，Deer等。

从表 5可以看出除了Walking2序列，加入拉普拉斯噪声后其追踪效果要优于MTT算法。但是原始模板更新的方法限制了它的追踪性能，而提出的新模板更新方法促进了ASSAT算法的追踪性能。

从表 6中可以看出仅使用模板更新的ASSAT方法和IVT方法的追踪效果差不多，对于Skater2，Subway序列两种方法效果都不好，原因是这两种序列含有较大的遮挡，对于仅考虑模板更新而没有考虑拉普拉斯噪声的ASSAT算法是无法有效追踪到目标的，IVT也是一样。但两者结合会取得更好的追踪效果。事实上，对于这种含有较大遮挡的情况，若不考虑拉普拉斯噪声，可归结到噪声因素影响了式(5) 中解X的稀疏结构，如图 8所示。

图  8  拉普拉斯噪声对解X的影响

图 8表示目标在遮挡情况不同的情况下噪声选择对解的影响。图 8的第一行表示考虑拉普拉斯噪声时所得到的解，可以看到解是稀疏的，此时解是最优的；图 8的第二行表示未考虑拉普拉斯噪声时所得到解，此时解是稠密的，非最优解，因此保持解的稀疏结构直接影响算法的追踪性能。

为了提高追踪系统的实时性，下面考虑自适应${{\text{L}}_{p}}$稀疏表示目标追踪算法，该算法与前面提出的算法一样，也考虑了噪声分布的影响，且模板更新采用在线增量学习与K-means相结合的模板更新方法，唯一不同的是，模型中认为粒子之间的影响是相互独立的，可以分别通过稀疏模型进行求解，且使用了LASSO求解算法，根据粒子滤波框架理论和最大后验概率求出最优追踪结果。数值试验结果表明该算法相对于目前存在的较好的追踪算法取得了更好的追踪效果，表现为精确性更高、实时性更好。

假设噪声分布服从高斯拉普拉斯分布：噪声$n$服从高斯分布($n\tilde{\ }N(0,\sigma _{N}^{2})$)，噪声$s$服从拉普拉斯分布($s\tilde{\ }N(0,{{\sigma }_{L}})$)，侯选目标$y$可以写成：

通常在噪声污染较小的情况下，认为侯选目标$y$可由模板$T$的少量基的线性组合来表示，这就意味着求解系数$x$是稀疏的，因此稀疏表示模型变为：

同前面分析一样，令：

式中，$\tau $是一个阈值，当噪声能量大于$\tau $时，此时需要考虑拉普拉斯噪声的影响，反之则忽略拉普拉斯噪声的影响。因此最终模型如下：

式(21) 的求解可以采用交替迭代的方法，每一次迭代都使用一次LASSO算法，令：

即：

式中，shrink是一个紧缩算子。

目标状态的更新和预测是目标追踪算法的核心问题。前面介绍了增量学习与K-means相结合的模板更新方法，本节提出的算法依然采用这种模板更新机制。类似的给出了自适应L_p模型的追踪算法4。

算法4：自适应L_p模型追踪算法

输入：第t帧侯选粒子${{\mathit{\boldsymbol{Y}}}_{t}}=[\mathit{\boldsymbol{y}}_{t}^{1},\mathit{\boldsymbol{y}}_{t}^{2},\cdots ,\mathit{\boldsymbol{y}}_{t}^{m}]$、最大迭代次数Loop、收敛误差tol、阈值区间$[\alpha ,\beta ]$、正则参数${{\lambda }_{1}}$、${{\lambda }_{2}}$。

1) 初始化$i=0$，$j\in [1,m]$，拉普拉斯噪声$s_{t}^{i}=0$

2) 根据式(13) 计算追踪目标${{y}_{t}}$与模板均值的相似性，记为sim

3) 迭代

4) 迭代直到$i>\text{Loop}$或者

5) 获得最好追踪目标${{y}_{\text{opt}}}=\underset{1\le j\le m}{\mathop{\arg \max }}\,p(y_{t}^{j}|{{q}_{t}})$

6) 通过式(12) ~式(15) 更新目标模板T，并得到新模板${{T}^{*}}$

输出：追踪目标${{y}_{\text{opt}}}$和新的模板${{T}^{*}}$

选取20种不同的视频序列(http://cvlab.hanyang.ac.kr/trackerbenchmark/datasets.html)，实验中模板基的个数设定为15，最大迭代次数和收敛误差分别为$\text{Loop}=5$，$\text{tol}=0.001$，阈值区间$\alpha =20$, $\beta =28$。使用LASSO算法^[24]求解${{L}_{1}}$模型，在默认的情况下正则参数${{\lambda }_{1}}=0.2$，${{\lambda }_{2}}=0.1$，实际中通过交叉验证的方法可以设置参数${{\lambda }_{2}}\in (0.000\text{ }5,0.5)$。

将算法4和目前9种比较好的算法进行比较，除了前面的CSK算法^[8]、L1APG算法^[14]、MTT算法^[17]、SPT算法^[23]和SCM算法^[21]、再增加DFT算法^[25]、ORIA算法^[26]、IVT算法^[4]、ASLSA算法^[7]。

表 7和表 8给出了在20种不同情境下的定量数据展示。表 7中AOR表示平均重叠得分，Fps表示每秒追踪的帧数，Fps越大表示追踪的越快即说明该算法的实时性越好。本文提出的算法AOR=0.74和ACLE=6.5是最好的，而Fps=9.53排名第三，这表明算法4在保证追踪精度的同时实时性也较好。

图 9展示了目标遭受快速运动、尺度变化和姿势旋转等噪声影响的追踪实验结果。对于视频Football，很明显本文算法可成功追踪到目标，其他算法都丢失了目标(见帧318和帧362)；对于视频Skater2，大部分算法都不能准确追踪到目标，在帧10时，每一种追踪算法都可以捕捉到目标，但在帧200时，因为目标形态改变太多，此时已经没有算法可以准确捕捉到目标了，在帧435时，只有本文的算法、CSK和ASLSA算法可以捕捉到目标的一部分；对于视频Deer和Surfer，可很清楚地看到本文的算法，SCM, SPT, ASLSA和L1APG算法可有效捕捉到目标。其原因归结于本文的算法综合考虑了噪声的影响，且将噪声部分进行很好地剔除，使得目标可以被模板稀疏表示，因而追踪成功。

图  9  几种追踪算法在快速运动和姿势旋转视频中的追踪效果

在实验中所有的参数都通过交叉验证的方法得到，在追踪过程中参数${{\lambda }_{1}}$不灵敏，一般可据经验设置在区间0.05~0.5，本文设置为0.1。难点是参数${{\lambda }_{2}}$的调整，因参数${{\lambda }_{2}}$直接影响拉普拉斯噪声能量的大小，一般相对来说，${{\lambda }_{2}}$越大拉普拉斯噪声能量越小。本文只给出了参数${{\lambda }_{2}}$的经验调整范围，当目标遭受较大的噪声污染时，如完全遮挡，此时${{\lambda }_{2}}$通常取较小的值一般在0.000 5~0.01之间，反之参数${{\lambda }_{2}}$取值在0.01~0.5之间。

本文提出了同时稀疏表示的自适应追踪算法，该方法考虑了拉普拉斯噪声的影响，并根据噪声的能量大小自适应的选择稀疏模型。另外，模型使用了2种稀疏表示：同时稀疏(L_{p, q})法，综合考虑了粒子之间的关系，使用ADMM方法对模型进行求解；对${{L}_{p}}$模型，认为粒子之间的影响是相互独立的，可以分别通过LASSO算法分别求解；不同情境下的大量实验表明，这两种方法均得到了稳定的结果。