0 引言

目标跟踪^[1-4]是计算机视觉领域一项重要的研究课题,广泛应用到视频监控、交通流量监测、人机接口等领域。近年来,国内外学者对目标跟踪算法进行了广泛的研究,但是由于跟踪视频中存在遮挡、尺度变化、角度变化、光照变化、运动模糊等影响跟踪性能的因素,使得设计一个鲁棒的跟踪算法仍然是一个具有挑战性的课题。目标跟踪算法可以分为基于模板匹配^[5]、在线分类^[6-9]、子空间学习^[10]以及稀疏表示^[11-13]等方法。其中,基于线性表示模型(子空间学习和稀疏表示)的目标跟踪算法得到学者们的广泛关注。2008年,文献^[14]提出一种在线子空间学习的目标跟踪算法,该算法通过被跟踪目标的表观变化在线更新对应的低维子空间,从而实现鲁棒的目标跟踪。受到稀疏表示在人脸识别领域巨大成功的启发,文献^[15]将稀疏表示模型首先引入到目标跟踪领域,提出基于L₁范数的目标跟踪算法。文献^[16]提出加速近似梯度算法,以解决L₁算法跟踪速度慢的问题,但是该算法在跟踪性能方面提高不是很明显。文献^[17]提出基于稀疏原型的在线目标跟踪算法(online object tracking with sparse prototypes,OSPT),该算法利用正交子空间建模跟踪目标的变化,同时提出考虑遮挡因素的观测模型更新机制,在一些跟踪视频上取得成功,但是该算法只对跟踪误差进行稀疏约束,没有对子空间对应的系数进行约束,从而导致对变化的跟踪目标的建模能力下降,部分视频出现跟踪失败。

基于上述讨论,提出一个基于L₁范数和最小软阈值的目标跟踪算法。首先,采用PCA子空间对跟踪目标进行建模,同时对对应的系数进行稀疏约束,即L₁范数;其次,对噪声项进行显性处理,并采用最小软阈值算法进行求解;在观测模型的更新过程中,考虑跟踪目标的遮挡因素,即噪声项的取值;最后,将所提算法运用到贝叶斯框架下进行目标跟踪。试验结果表明,本研究能够解决跟踪视频中存在的遮挡、尺度变化、角度变化、运动模糊等问题,实现鲁棒的目标跟踪。

1 L₁算法

文献^[15]将稀疏表示首先引入目标跟踪领域,并提出L₁算法,该算法假设候选样本能够由目标模板和琐碎模板组成的基向量线性表示,即

$y=Uz+e=\left[ U\text{ }I \right]\left[ \begin{matrix} z \\ e \\ \end{matrix} \right]=Ac,$

(1)

其中:y表示候选样本;U为目标模板;z为目标模板所对应的表示系数;I为单位矩阵,表示琐碎模板;e为琐碎模板所对应的表示系数,同时也是观测噪声;A为由目标模板和琐碎模板组成的基向量矩阵;c为对应的的稀疏表示系数。 L₁算法假设候选样本可以由A稀疏表示,因此式(1)可以通过L₁最小化方法求得,即

$min\frac{1}{2}\|y-Ac\|_{2}^{2}+\lambda \|c{{\|}_{1}},$

(2)

式中:λ表示常系数,‖·‖₁和‖·‖₂分别表示L₁和L₂范数。L₁算法在跟踪过程中对目标模板进行动态更新以应对跟踪目标的变化,并用琐碎模板来表征跟踪过程中可能出现的遮挡等异常噪声,在跟踪领域取得成功。但是该算法的计算量大,只能利用低像素的候选图像块,难以满足快速跟踪的需求。

2 基于L₁正则化和最小软阈值的目标跟踪算法 2.1 基于L₁正则化和PCA基向量矩阵的目标表示模型

受L₁算法和OPST算法启发,提出基于L₁范数和最小软阈值均方的目标跟踪算法,与式(1)相类似,待跟踪的目标观测向量可以近似表示为:

$y=\mu +Ux+e,\text{ }$

(3)

其中: y表示候选样本的观测向量,μ为均值向量,U表示PCA基向量矩阵,x表示PCA基向量矩阵对应的稀疏表示系数,e为小方差的高斯误差项。为了求解表示系数x和e,对x和e引入L₁范数约束,即通过下式的优化问题来求解x和e,

$\begin{matrix} \left[ x,e \right]=arg\underset{x,e}{\mathop{\min }}\,\frac{1}{2}\|y-\mu -Ux-e\|_{2}^{2}+ \\ \alpha \|x{{\|}_{1}}+\beta \|e{{\|}_{1}},\text{ } \\ \end{matrix}$

(4)

其中,α和β分别为常数。很明显,式(4)并没有闭合解。为了求解x和e,分别采用Lasso算法和最小软阈值方法进行求解。

首先,假定最优解${\hat{e}}$给定,则最优${\hat{x}}$ 的求解转化为$[\hat{x}]=arg\underset{x}{\mathop{\min }}\,\frac{1}{2}\|y-\mu -U\hat{x}-\hat{e}\|_{2}^{2}+\alpha \|\hat{x}{{\|}_{1}}=arg\underset{x}{\mathop{\min }}\,\frac{1}{2}\|y\prime -U\hat{x}\|_{2}^{2}+\alpha \|\hat{x}{{\|}_{1}},$因此可以通过Lasso算法对最优$\hat{x}$进行求解。其中,$y\prime =y-\mu -\hat{e}$。 假定最优解${\hat{x}}$给定,则最优${\hat{e}}$的求解转化为$[\hat{e}]=arg\underset{x}{\mathop{\min }}\,\frac{1}{2}\|y-\mu -U\hat{x}-\hat{e}\|_{2}^{2}+\beta \|\hat{e}{{\|}_{1}}$,则最优${\hat{e}}$可以通过最小软阈值均方方法求得,即$\hat{e}={{S}_{\beta }}\left( y-\mu -\text{ }U\hat{x} \right)$,其中S_β(x)=max(|x|-β,0)sgn(x),sgn(x)为符号函数。

最优${\hat{x}}$和${\hat{e}}$的迭代求解算法如下:

输入 观测向量y,PCA基向量矩阵,常系数α,β

(1) 初始化稀疏系数x₀=0,e₀=0,循环变量j=0;

(2) 开始循环计算;

(3) 计算x_j+1:

$\begin{matrix} [{{{\hat{x}}}_{j+1}}]=arg\underset{{{x}_{j}}}{\mathop{\min }}\,\frac{1}{2}\|y-\mu -U{{{\hat{x}}}_{j}}-\hat{x}\|_{2}^{2}+\alpha \|{{{\hat{x}}}_{j}}{{\|}_{1}}= \\ arg\underset{{{x}_{j}}}{\mathop{\min }}\,\frac{1}{2}\|y\prime -U\hat{x}j\|_{2}^{2}+\alpha \|{{{\hat{x}}}_{j}}{{\|}_{1}} \\ \end{matrix}$

(3) 通过Lasso算法求解;

(4) 计算e_j+1: e_j+1=S_β(y-μ-Ux_j+1);

(5) j=j+1;

(6) 满足循环终止条件时,跳出循环,否则,跳转至(2),继续进行循环计算。

输出 最优解 ${\hat{x}}$ 和 ${\hat{e}}$ 。

2.2 基于L₁

正则化和最小软阈值的目标跟踪框架 目标跟踪可以看成是贝叶斯框架下的推理问题,用z_t 表示跟踪目标在第t 帧的运动状态,y_1∶t-1 表示第1帧到第t-1 帧跟踪目标的观测向量,先验概率

$p({{z}_{t}}|{{y}_{1:t-1}})=\int p\left( {{z}_{t}}|{{z}_{t-1}} \right)p({{z}_{t-1}}|{{y}_{1\,\!:t-1}})d{{z}_{t-1,}}$

(5)

其中:p(z_t|z_t-1)表示两个连续状态的运动模型,即条件转移概率;p(zt-1|y_1∶t-1)为t-1时刻的后验概率。当前时刻最优状态_t可以通过对式(5)进行最大后验概率准则求得,即

$\hat{z}=arg\underset{z_{t}^{i}}{\mathop{max}}\,p\left( z_{t}^{i}|{{y}_{1:t}} \right),$

(6)

其中i表示第i个粒子。

2.2.1 运动模型

用仿射变换模型来建模帧与帧之间的运动模型p(z_t|z_t-1),并用6个参数来描述第t帧的运动状态z_t=(x_t,y_t,θ_t,s_t,a_t, φ_t),其中:x_t和y_t分别表示跟踪目标的坐标位置;θ_t表示跟踪目标整体的旋转角度,(°);s_t表示跟踪目标形变尺度;a_t表示跟踪目标的宽和高之比; φ_t表示切变系数。假设运动模型服从布朗运动,即独立的高斯分布,则运动模型可以表示为

$p({{z}_{t}}|{{z}_{t-1}})=N({{z}_{t}};{{z}_{t-1,}}\sum{{}}),$

(7)

其中∑为6个仿射不变参数的方差(σ_x²,σ_y²,σ²_θ,σ_s²,σ_a²,σ²_φ)组成的对角矩阵。

2.2.2 观测模型

观测模型的作用是评价每一个采样粒子跟踪目标的可能性,由于跟踪过程中,采样粒子可能会受到遮挡等异常噪声的影响,因此,需要对PCA基向量矩阵进行更新,以适应跟踪过程中目标的变化。因此,对每一个采样粒子采用式(8)进行优化计算求得其对应的观测向量yⁱ,

$\begin{matrix} \left[ {{{\hat{x}}}^{i}},{{{\hat{e}}}^{i}} \right]=arg\underset{{{x}^{i}},{{e}^{i}}}{\mathop{\min }}\,\frac{1}{2}\|{{{\bar{y}}}^{i}}-U{{x}^{i}}-{{e}^{i}}\|_{2}^{2}+ \\ \alpha \|{{x}^{i}}{{\|}_{1}}+\beta \|{{e}^{i}}{{\|}_{1}}, \\ \end{matrix}$

(8)

其中${{{\bar{y}}}^{i}}={{y}^{i}}-u$,u为PCA算法所生成的均值。每一个没有受到干扰的观测向量都可以由基向量矩阵U和均值u生成。 求得最优解${\hat{x}}$和${\hat{e}}$后,就可以利用重构误差来设计观测似然函数

$\begin{matrix} p({{y}^{i}}|{{x}^{i}})=\text{ }exp\{-\gamma (\frac{1}{2}\|{{{\bar{y}}}^{i}}-U{{x}^{i}}-{{e}^{i}}\|_{2}^{2}+ \\ \alpha \|{{x}^{i}}{{\|}_{1}}+\beta \|{{e}^{i}}{{\|}_{1}})\}, \\ \end{matrix}$

(9)

其中γ为常数。当观测向量与重构的观测向量越相似,则二者的差值越小,式(9)值越大,反之观测向量与重构的观测向量越不相似,式(9)值越小。同时采用式(10)对产生的最优观测向量进行更新,

$y_{i}^{r}=\left\{ \begin{align} & y_{i}^{0},{{{\hat{e}}}_{i}}=0, \\ & {{u}_{i}},{{{\hat{e}}}_{i}}\ne 0。 \\ \end{align} \right.$

(10)

当误差项等于0时,表示跟踪目标没有被遮挡,则直接用跟踪结果来更新观测模板矩阵;当误差项不等于0时,表示跟踪目标被遮挡,则用均值u来更新观测向量矩阵。

目标跟踪框架如下:

For t=1∶m

(1) 对跟踪参数进行手动初始化;

(2) 采用简单的跟踪算法对前m帧进行跟踪,同时对跟踪结果进行保留组成目标模板矩阵用以训练PCA子空间;

End。

(3) 对目标模板矩阵采用PCA方法进行计算,以获得均值向量μ和特征值矩阵U;

For t=m+1∶T(T表示跟踪视频数量)

(4) 在第t帧中以上一帧的跟踪结果为中心,随机选取n个候选样本y_t=[y_t¹,y_t²,…,y_tⁿ]以及n个候选样本的运动状态z_t=[z_t¹,z_t²,…,z_tⁿ];

(5) 对每一个候选样本计算

$\begin{matrix} \left[ {{{\hat{x}}}^{i}},{{{\hat{e}}}^{i}} \right]=arg\underset{{{x}^{i}},{{e}^{i}}}{\mathop{\min }}\,\frac{1}{2}\|{{{\bar{y}}}^{i}}-Uxi-{{e}^{i}}\|_{2}^{2}+ \\ \alpha \|{{x}^{i}}{{\|}_{1}}+\beta \|{{e}^{i}}{{\|}_{1}}; \\ \end{matrix}$

(6) 利用第5步得到的系数计算观测模型:

$\begin{matrix} p({{y}^{i}}|{{x}^{i}})=)exp\{-\gamma (\frac{1}{2}\|{{{\bar{y}}}^{i}}-U{{x}^{i}}-{{e}^{i}}\|_{2}^{2}+ \\ \alpha \|{{x}^{i}}{{\|}_{1}}+\beta \|{{e}^{i}}{{\|}_{1}})\}, \\ \end{matrix}$

同时在粒子滤波框架下计算最优运动状态;

(7) 利用得到跟踪结果及均值向量μ采用公式$y_{i}^{r}=\left\{ \begin{align} & y_{i}^{0},{{{\hat{e}}}_{i}}=0 \\ & u,\hat{e}\ne 0 \\ \end{align} \right.$对PCA子空间向量进行更新;

End。

3 试验结果

本研究在Inter(R) Core(TM)i7-5500 CPU(2.40GHz)、8G内存电脑平台上,采用MATLAB R2014a进行仿真。每一个跟踪结果图像归一化到32×32 像素,同时选取16个特征向量组成PCA特征向量矩阵,选取600个采样粒子,规则化系数α=0.01,β=0.05。为了验证本研究的有效性,选取14个具有挑战性的视频(Occlusion1、Occlusion2、 Caviar1、 Caviar2、 Caviar3、 Car4、 Car11、 DavidIn、 Singer1、 Face、 Jumping、 Owl、 Deer、 Football),与其他6种算法:Frag(fragments-based tracking)^[18]、IVT(incremental learning for robust visual track- ing)^[14]、VTD(visual tracking decomposition)^[19]、APGL1(real time robust L1 tracker using accel- erated proximal gradient approach)^[16]、 MTT (robust visual tracking via multi-task sparse learning)^[20]、OSPT^[17]进行试验对比。为了公平起见,其他算法采用作者提供的代码,并在跟踪时,对参数进行调试,以达到最佳效果。

3.1 定性对比

图 1~4给出不同视频的跟踪结果,用不同颜色的实线框代表不同算法的跟踪结果。红色(本研究),黑色(Frag),青色(IVT),黄色(VTD),蓝色(APGL1),紫色(MTT),绿色(OSPT)。

图 1给出Occlusion1、Occlusion2、Caviar1、Caviar2和Caviar3 5个视频的跟踪结果,这5个视频存在严重的遮挡、尺度变化、角度变化等影响跟踪性能的因素。从跟踪结果来看,相比其他6种算法,本研究在跟踪目标的位置以及尺度变化方面取得最好的跟踪性能,尤其是跟踪目标存在部分遮挡时,本研究也成功实现跟踪。从Occlusion2和Caviar3视频可以看出,由于IVT算法假设观测噪声服从小方差的高斯噪声,所以当跟踪目标存在部分遮挡时,IVT算法的跟踪结果不理想。APGL1由于对观测矩阵采用直接更新的方式,没有考虑遮挡因素,所以当跟踪目标存在部分遮挡,容易跟丢目标,导致跟踪失败。

图 2给出了Car4、Car11、DavidIn、Singer1视频采用不同算法的跟踪结果对比。4个视频中分别存在光照变化、角度变化以及尺度变化等影响跟踪性能的因素。本研究算法、OSPT算法及IVT算法都取得了成功。当跟踪目标存在尺度变化时,Frag算法和MTT算法不能随着跟踪目标的尺度变化而变化,所以跟踪性能下降。VTD算法则对光照变化比较敏感,当跟踪目标存在强烈的光照变化时,VTD算法则跟丢目标。

图 3为Face、Jumping、Owl视频的跟踪结果,3个视频存在相机快速抖动以及跟踪目标存在运动模糊等影响跟踪性能的因素。IVT、VTD、APGL1以及MTT算法在跟踪过程中都存在严重的漂移现象,甚至直接跟丢目标。只有本研究能够解决严重影响跟踪性能的因素,准确得实现目标跟踪。

图 4为Deer视频和Football视频,Deer视频中存在相似小鹿的遮挡以及小鹿的快速运动,Football视频中存在周围相似运动员的遮挡。从跟踪结果来看,本研究对Deer视频跟踪效果较好,但对Football视频最后几帧出现轻微漂移,表明本研究对出现相似物体的干扰时,跟踪会出现偏差。

3.2 定量对比

采用中心点位置误差(以像素为单位)和覆盖率来对本研究跟踪算法与其他跟踪算法进行定量评价。中心点位置误差的定义为CLE(t)=$\sqrt{{{\left( {{x}^{t}}_{T}-{{x}^{t}}_{G} \right)}^{2}}+{{\left( {{y}^{t}}_{T}-{{y}^{t}}_{G} \right)}^{2}}},\left( {{x}^{t}}_{T},{{y}^{t}}_{T} \right)$表示采用跟踪算法得到的跟踪结果中心点位置坐标,(x_G^t,y_G^t)表示跟踪目标真实位置的中心点坐标位置。如果采用跟踪算法得到的结果与跟踪目标的真实位置越接近,则第t帧的CLE(t)越小。覆盖率的定义为OR(t)=$\frac{area\left( {{R}_{T}}^{t}\cap {{R}_{G}}^{t} \right)}{area\left( {{R}_{T}}^{t}\cup {{R}_{G}}^{t} \right)}$,其中,R_T^t表示第t帧采用跟踪算法得到跟踪方框结果,R_G^t表示第t帧中被跟踪目标的真实方框结果,如果采用跟踪算法得到的结果与跟踪目标的真实位置越接近,则OR(t)越大,否则OR(t)越小。图 5和图 6给出了本研究与其他跟踪算法在所跟踪的视频上每帧的跟踪中心点位置误差对比与覆盖率对比。用不同颜色的线条给出不同算法的中心点误差和覆盖率,红色实线(本研究),蓝色虚线(Frag),黑色虚线(IVT),品红色虚线(VTD),青色虚线(APGL1),绿色虚线(MTT),黄色虚线(OSPT)。表 1和表 2给出中心点位置误差与覆盖率的每帧平均值以及14个视频的平均中心点位置误差和平均覆盖率。试验数据可以看出,在对比的14个视频中,本研究的平均中心点位置误差最小,平均覆盖率最大,表明相比其他算法,本研究的跟踪性能最稳定,跟踪性能最优。

表 3给出了不同算法的跟踪速度对比,本研究的跟踪速度虽不是最优,和OSPT算法的速度相当,但是跟踪性能是最优的。

4 结论

为了克服跟踪视频中存在的遮挡、背景杂乱、光照变化、尺度变化等影响跟踪性能的因素,提出一种基于L₁范数和最小软阈值均方的目标跟踪算法。在贝叶斯框架下对目标跟踪算法进行推理,采用PCA子空间建模跟踪目标的表观变化,同时对表示系数进行稀疏约束,对遮挡等因素引起的噪声项采用最小软阈值方法进行显性求解,观测模型的更新考虑遮挡机制。大量试验结果表明:相比其他算法,本研究能够适应目标尺度变化,能够解决光照变化和运动模糊等问题,跟踪精度和鲁棒性得到一定程度的提高。