目标跟踪是指对连续的视频序列中的运动目标进行跟踪，是计算机视觉的重要研究内容。通过视频目标的跟踪可以跟踪到目标的运动状态和相关参数，进而为智能视频监控、运动目标分析、目标行为识别方面提供重要基础^[1]。

目前跟踪的热点模型是将视频目标跟踪的问题看做二元分类问题，其主要任务就是将视频内容分类背景元素和目标元素两类，一类属于背景，一类属于目标。这样目标跟踪问题就转化为二元分类问题，很多原本用来做分类的算法将可以被用来实现目标跟踪算法，例如应用广泛的在线学习跟踪^[2]，基于在线Boosting的视频目标跟踪^[3]，结合了先验知识的在线Boosting算法的目标跟踪^[4]。

2006年Candes和Donoho^[5]正式提出压缩感知的理论，基本原理是先采用投影矩阵得到压缩后的数据，然后根据相应的重构算法重构原始信号。直接采集压缩后的数据相比采集全部数据耗费的时间要少很多，因此得到广泛的应用。应用之一就是分类，同时在目标跟踪中得到广泛的应用，文献[6]根据数据在投影矩阵中不同类别轴上的测量值来进行分类的分类方法运用到跟踪中，将目标的正负样本模版库构造成一个投影矩阵，在投影矩阵中寻找到正样本所对应的投影系数最大的候选位置，将其作为新的目标位置。文献[7]通过一定的宽松规则，生成一个系数的投影矩阵，然后直接将压缩后的数据作为特征来使用。该算法的优点在于快速的提取特征，提高了跟踪算法的效率，但由于该算法在搜索候选目标时采用每隔一个像素的办法，使得其搜索目标的过程耗时仍然相当大，并且抗目标遮挡的能力较差。最终阻碍该算法的进一步的发展和应用。文献[8]提出了粗精搜索的策略实现了快速的压缩跟踪算法，但是减少的跟踪时间有限，且没有提升抗目标遮挡的能力。

鉴于压缩跟踪算法耗时较大的缺陷，对压缩跟踪算法做进一步的改进，通过综合分析压缩跟踪算法，得出压缩跟踪算法跟踪耗时大的主要原因是由于搜索候选目标的策略问题。为解决此问题，提出了基于粒子群优化的压缩跟踪算法。采用粒子群优化的办法代替每隔一个像素的搜索策略，使得算法可以更加快速地寻找到真实目标，在目标发生遮挡时，采用粒子群优化的办法进行全局的搜索，当目标复现时，快速重新跟踪上目标。

压缩感知理论通过将信号投影到某个合适的变换域得到稀疏的变换系数，通过设计一个高效的观测矩阵获得隐藏在稀疏信号中的有用观测值，通过少量的有用的观测值就可以与信号相关联，最后通过设计有效的重构算法，根据观测值求解信号的最优逼近。

基本原理是用测量矩阵A对信号x进行测量运算，得到测量向量y。具体指的是：设一个离散信号为x，m×n的测量矩阵为A。y=Ax，称y为测量信号。

如果一个信号是可以压缩的，那么当测量矩阵A满足Johnson-Lindenstrauss准则时，那么经压缩后，y保留了x的大部分信息，并且y能以最小误差重构x。

从文献[9]中可以得出，直接提取样本的特征将耗费更多的时间，采用在现有的特征提取办法的基础上，提取满足压缩感知理论条件的新特征。具体提取特征为

$v=Rx$

(1)

式中，x为原始的样本特征，矩阵R_n×m(n<<m)为测量矩阵，v为满足压缩感知理论条件的特征。在该压缩感知算法中，测量矩阵R是压缩感知理论中非常重要的部分，假如R是稠密矩阵，即使满足约束等距性条件，但是这样做并没有取到真正的压缩信号的效果，因此通常采用稀疏的随机的测量矩阵^[8]。R的定义为

${{r}^{ij}}=\sqrt{s}\times \left\{ \begin{matrix} 1 & p=1/2s \\ 0 & p=1-1/s \\ -1 & p=1/2s \\ \end{matrix} \right.$

(2)

式中，p为产生概率，s通过随机概率得出，一般为34。由式(2)可知直接采集的新特征v是由原始的特征以r^ij为权值的加权和得到。

分类器采用基于贝叶斯的分类器。具体过程是在目标确定之后，通过式(3)贝叶斯准则构造分类器^[9]，把确定的目标区域的临近区域作为搜索区域，每隔一个像素选取一个候选目标，最终经过分类器分类得出真实目标。式(3)中假设所有的特征是相互独立的。

$\begin{align} & H\left( v \right)=\log \left( \frac{\prod\nolimits_{i=1}^{n}{p\left( {{v}_{i}}|y=1 \right)p\left( y=1 \right)}}{\prod\nolimits_{i=1}^{n}{p\left( {{v}_{i}}|y=0 \right)p\left( y=0 \right)}} \right)= \\ & \sum\limits_{i=1}^{n}{\log }\left( \frac{p\left( {{v}_{i}}|y=1 \right)}{p\left( {{v}_{i}}|y=0 \right)} \right) \\ \end{align}$

(3)

通常情况下认为^[7]，条件分布p(v_i|y=1)、p(v_i|y=0)大多情况下符合高斯分布，即

$\begin{align} & p\left( {{v}_{i}}|y=1 \right)\tilde{\ }N\left( \mu _{i}^{1},\sigma _{i}^{1} \right) \\ & p\left( {{v}_{i}}|y=0 \right)\tilde{\ }N\left( \mu _{i}^{0},\sigma _{i}^{0} \right) \\ \end{align}$

(4)

式中，μ₁、σ₁和μ₀、σ₀分别为真实目标和候选背景样本的均值与标准差。

通过选取最大的H(v)所在的候选区域作为新的目标区域，即

$Conf\left( {{H}_{i+}} \right)=\arg \max \left( {{H}_{i}} \right)$

(5)

式中,Conf(H_i+)为所有H(v)为最大值的所在区域，H_i+为所有H(v)的最大值，H_i为第i个H(v)值。之后选取正负样本用来更新分类器，即

$\begin{align} & {{D}^{\alpha }}=\left\{ z|l\left( z \right)-{{l}_{t}}|<a \right\} \\ & {{D}^{\xi ,\beta }}=\left\{ z|\xi <|l\left( z \right)-{{l}_{t}}|<\beta \right\} \\ \end{align}$

(6)

式中，z为样本，D^a为正样本，以区域中心为圆心，a为半径的区域内选取正样本；D^ξ,β 为负样本，a<ξ<β，以区域中心为圆心，分别以ξ和β为半径得到的圆环的区域中选取负样本；l(z)，l_t分别为样本位置和目标区域位置。

最后通过选好的正样本和负样本更新分类器，即

$\begin{align} & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ u_{i}^{1}\leftarrow \lambda u_{i}^{1}+\left( 1-\lambda \right){{u}^{1}} \\ & \sigma _{i}^{1}\leftarrow \sqrt{\lambda {{\left( \sigma _{i}^{1} \right)}^{2}}+\left( 1-\lambda \right){{\left( {{\sigma }^{1}} \right)}^{2}}+\lambda \left( 1-\lambda \right){{\left( {{\sigma }^{1}} \right)}^{2}}\left( u_{i}^{1}-{{u}^{1}} \right)} \\ \end{align}$

(7)

式中，u¹为样本灰度均值，σ_i¹ 为样本灰度方差，λ>0，λ为更新速率，λ越小目标模型更新的速度就越快，本文定λ为0.85。u_i⁰与σ_i⁰采用类似规则更新。

压缩跟踪算法具有快速提取特征等优点，能适应各种复杂场景下的目标检测和目标跟踪，具有较强的抗干扰能力。但是该算法计算量仍然较大，仅能在高性能计算机上达到实时跟踪的目的，从而影响该算法进一步的推广应用，如果压缩跟踪算法的计算量能够大大减少，但又不影响该算法的跟踪准确率，那么该目标跟踪算法将大大提高适应性，满足实际的工程应用的需要。

将压缩感知理论应用于视频跟踪问题，是通过压缩感知理论对目标特征进行表述，在此基础上对目标进行分类判别。因此直观的思路是通过借助观测矩阵将目标特征变换为有效的观测值以进行降维，再采用稀疏分解将观测值变换为稀疏向量，通过稀疏向量来表征目标特征并对其进行分类判别。另一思路是通过观测矩阵将目标特征变换为有效的观测值，即压缩向量，直接对降维后的压缩向量进行分析，从而对目标进行分类判别(如压缩跟踪算法(CT)^[7]，快速压缩跟踪算法(FCT)^[8] 算法)，本文算法也采用这一思路。

在视频跟踪过程中，压缩感知理论提供了对目标进行表述的一种方法，跟踪算法关心的是表征目标的特征向量对目标跟踪判别的有效性，而并不关心这些特征向量是否为稀疏向量。而要获得描述目标的稀疏向量，还需要进行复杂的稀疏分解，因此直接利用压缩向量作为跟踪目标的判据可减少跟踪算法的计算复杂度(如CT^[7]，FCT^[8])。

在压缩跟踪算法的基础上，本文采用了粒子群优化的方法通过优化压缩跟踪算法中候选模版的搜索策略来达到减少计算量的目的，在目标被遮挡时，采取粒子群优化的方法进行全局搜索目标，从而提高了本文所提跟踪算法的抗遮挡的能力。

Kennedy和Eberhart^[10]在受到鸟群研究理论的影响之后，模拟鸟群觅食的过程中的相聚以及分散行为，得出一种基于大群体智能的全局的随机搜索目标的算法，称为粒子群优化算法(PSO)。粒子群优化算法是一种容易理解，并且参数比较少又容易实现的一种优化算法，而且具有非常强的全局搜索目标的能力，特别是在处理多峰的问题上效果很好，广泛应用于各类的学术研究和工程项目。

假设在N维搜索区域中，存在某个粒子群X={x₁,x₂,…,x_m}由m个粒子(候选目标)构成，第t步时，x_i(t)=[x_i1,x_i2,…,x_in]^T是指粒子(候选目标)i的位置，粒子(候选目标)i的移动速度为v_i=(v_i1,v_i2,…,v_in)^T，当前搜索的过程中粒子(候选目标)的个体最优值为p_i=[p_i1,p_i2,…,p_in]^T，当前在全部粒子群中的全局最优值为p_g=[p_g1,p_g2,…,p_gn]^T。粒子(候选目标)的速度和位置^[11]迭代更新公式为

$\begin{align} & {{v}_{id}}\left( t+1 \right)=w\times {{v}_{id}}\left( t \right)+{{c}_{1}}{{r}_{1}}\left( {{p}_{id}}\left( t \right)-{{x}_{id}}\left( t \right) \right)+ \\ & {{c}_{2}}{{r}_{2}}\left( {{p}_{gd}}\left( t \right)-{{x}_{td}}\left( t \right) \right) \\ \end{align}$

(8)

${{x}_{id}}\left( t+1 \right)={{x}_{id}}\left( t \right)+{{v}_{id}}\left( t+1 \right)$

(9)

式中，d=1,2,…,n，i=1,2,…,m，t为时间，表示迭代次数，惯性权值^[12]w表示上一次迭代粒子的速度对本次的粒子的速度的影响；在[0,1]范围内的均匀随机数r₁和r₂，指的是上一次的个体最优候选目标和全局最优候选目标对本次的粒子速度的随机性影响。c₁和c₂为学习因子，表示上一次迭代的个体最优候选目标和全局最优候选目标对当前的粒子速度的影响权重，由于候选目标在每次迭代之后都会更加接近个体最优候选目标和全局最优候选目标，所以粒子的速度就会越来越小，所以在本算法中采用随着迭代次数的增加而减小的办法给出学习因子和惯性权值的值。

此外，为避免粒子速度由于过大而可能超出了搜索的范围。设置了粒子速度的上限v_max，当v_id(t+1)>v_max时则v_id(t+1)=v_max，以及粒子速度的下限，当v_id(t+1)<-v_max时则v_id(t+1)=-v_max，这里粒子的速度上限的选取需要随跟踪框的大小变化而变化。

在通过压缩感知理论获得目标的压缩向量，建立目标模型之后，跟踪算法通过朴素贝叶斯算法在表征目标位置以及范围的状态空间中搜寻目标的最大似然以获得跟踪结果。CT^[7]以及FCT^[8]算法采用了遍历或由粗及精的方法在状态空间中寻找最大似然以得到跟踪结果。将目标的位置(x,y)或范围(hx,hy)，作为粒子群优化搜索的状态空间，采用粒子群优化策略在状态空间中寻找目标的最大似然以得到跟踪结果，算法根据上一帧的目标状态随机初始化粒子群，朴素贝叶斯算法得到的似然值作为各粒子优劣的判据，各粒子的运动取决于其惯性、个体经验以及群体经验，经过多次迭代满足收敛条件后，粒子群算法搜索全局最优粒子所代表的状态即为当前目标跟踪的结果。

1)在首帧图像中确定跟踪目标T(s,t),在跟踪目标周围选取100个正样本，在正样本外选取100个负样本，训练分类器。

2)在第2帧中，搜索区域S内随机的采集20个候选目标(粒子)G(s+x,t+y)，根据分类器计算每个候选目标G(s+x,t+y)似然值，并找出似然值最大的样本作为首次全局最优候选目标P_g，其余19个候选目标作为各自的首次个体最优候选目标P_b。

3)开始迭代，根据式(8)(9)更新每个个体最优候选目标的速度和位置，得到新的19个候选目标，全局最优在其周围随机游动6次，获得7个候选目标。再通过分类器求出这26个候选目标的似然值，并找出似然值最大的候选目标作为新的全局最优候选目标P_g。并通过比较这次计算的似然值与上一次计算的似然值，得到本次迭代的每个个体最优候选目标P_b。

4)当满足相邻两次全局最优候选目标对应的似然值之差小于0.1，并且距离相差小于1个像素时，迭代结束。最后一次迭代的全局最优候选目标即为当前帧中的目标。

5)当分类器得出的最大值小于给定阈值时，返回步骤1)进行整幅图全局搜索，直到满足条件。

6)更新分类器。

7)重复步骤1)—6)进行视频的实时跟踪。

为了验证提出的基于粒子群优化的压缩跟踪算法(CTP)的实时性，选择了与 CT^[7]、FCT ^[8]、tracking learning detection (TLD) ^[13]、l1-tracker (L1T)^[14]、CT using cosine similarity metric (CS_CT)^[15]、multitask tracker (MTT)^[16]以及real-time object tracking via the online discriminative feature selection (ODFS)^[17]进行比较，所有算法都使用统一的视频序列和初始跟踪位置。采用了20种常用的视频序列。这些视频序列的目标准确位置都采用人工画出。用于比较的所有跟踪算法都是按照原作者的参数设置方法设置参数，所有实验结果数据都采用运行10次取平均值的结果。实验环境为MATLAB R2010a 酷睿i7-4510U 3.0 GHz CPU和8 GB RAM。

为了有效地比较本文算法与其他跟踪算法的跟踪效果，选择20个经典常用的视频序列进行测试，如表 1。这20个视频序列都来自于各大经典的算法提供的视频序列。这些视频序列各有跟踪特点，例如animal、cliffbar及David视频序列有目标尺度、姿态变化及背景干扰的情况；faceocc、football及shaking视频序列目标有遮挡、相似目标干扰及复杂背景干扰；singer1、tiger2及twinnings视频序列有旋转、遮挡及缩放的情况。

用来做比较的7种跟踪算法都是按照原作者的参数设置方法设置参数。本文算法中，由于目标帧间移动距离不大，候选目标的选取区域设定为以r=(1.5w+1.5h)/4为半径(w，h分别为图像宽度和高度)，以上一帧目标的中心坐标为圆心的圆中。定义粒子群优化中，经过多次实验得出，随机采集的候选目标20个，全局最优候选目标随机游动6次，可以产生最佳的跟踪效果。惯性权值w为1/(2n)，候选目标朝向个体最优候选目标的加速常数c₁为1.5/(1.5×n)，粒子朝向全局最优候选目标的加速常数c₂为2.5/(0.5×n)，式中n为迭代次数。为了使候选目标更快地移向全局最优候选目标，所以c₂取值较大，为了提高跟踪的精度，两种加速常数以及惯性权值都随迭代的增加而减小。为使所有移动的粒子都在搜索区域中移动，x速度上限v_max^x为0.3×h，y速度上限v_max^y为0.3×w。

为了评价跟踪算法的各种跟踪性能，采用跟踪成功率^[18] (SR)来评价目标跟踪的准确程度。首先，计算每一帧跟踪目标位置与真实目标位置的重合率

$score=\frac{area\left( RO{{I}_{\text{T}}}\cap RO{{I}_{\text{G}}} \right)}{area\left( RO{{I}_{\text{T}}}\cup RO{{I}_{\text{G}}} \right)}$

(10)

式中，ROI_T表示跟踪算法得出的目标位置的矩形框；ROI_G表示真实的目标所在位置的矩形框；area表示求面积运算。式(10)表示ROI_T与ROI_G相交部分的面积除以相并部分的面积即为当前帧的重合率score，其值表示跟踪目标位置的准确度的高低。规定重合率score≥0.5则当前帧跟踪成功，否则跟踪失败。最后将跟踪成功的帧数除以总的帧数得出各算法的跟踪某一视频序列的成功率。

采用中心位置偏差 (CLE)来评价跟踪的偏移情况，计算真实目标的中心坐标和算法跟踪目标的中心坐标的欧氏距离，求取所有帧的欧氏距离的平均值即为该视频序列的中心位置偏差。

采用每秒运行的帧数(AFPS)来评价算法的跟踪耗时情况，每次结果都采取运行10次取平均值得出。

将所有跟踪算法在20个视频序列上跟踪成功率(CLE)绘制成表 2。从表 2中的实验结果数据可以看出，本文算法在20个序列上跟踪成功率最高的有8个，跟踪成功率其次的有6个，共14个，跟踪效果较好的视频序列比例达到70%。另外，在singer1视频序列和Twinnings视频序列中，本文算法的成功率分别达到85.2%和89.6%。实验结果表明，结合了粒子群优化的压缩跟踪算法很好地改进了压缩跟踪算法的跟踪效果。

表 3为中心位置偏差及平均每秒运行帧数，表 3中，加组字体数据代表中心位置偏差最小的算法数据，斜体为中心位置偏差次小的算法数据。从表 3中给出了每个视频序列下跟踪实验的中心位置偏差(CLE)，以及20个视频序列的平均中心位置偏差(ACLE)和平均每秒运行帧数(AFPS)，本文提出的算法跟踪中心位置偏差(CLE)最小的视频序列有6个，跟踪效果偏差次小的有8个，合计占总的视频序列的70%。其中cliffbar视频序列和shaking视频序列平均中心位置偏差为6.78和8.96。最后，为了分析各种目标跟踪算法跟踪耗时的情况，采用的每一秒运行的帧数(AFPS)作为对比的依据，各种算法在20种不同视频序列上跟踪耗时情况如表 3。

以animal视频序列为例，animal视频序列目标大小为100×70，设定算法在搜索候选目标的范围都采用宽1.5×100和高1.5×70的区域，即150×105的区域。压缩跟踪算法的搜索策略是，在150×105的区域内，每隔一个像素采集一个候选目标进行分类器分类，最终在这150×105的区域中将要采集1 750个样本，进行1 750次分类器分类。而基于粒子群优化的压缩跟踪算法的搜索策略采用的是粒子群优化算法的方法，首选在150×105的搜索区域中随机的采集30个候选目标进行分类器分类，找出全局最优候选目标和个体最优候选目标，之后进行粒子群的迭代运算，其中全局最优随机游动6次，根据实验可以得出，平均每次迭代2.5次可以找到目标。即每帧需要运行(30+36×2.5)次，即仅120次分类器分类运算。分类器分类运算的运算量仅为其他跟踪算法的0.07。加上粒子群优化算法本身所需要的运算量，所以本文算法比其他跟踪算法在跟踪animal视频序列上显著减少跟踪所费时间。

为了更加直观地分析本文算法的实验效果，从20个视频序列中，列出了9个不同场景不同干扰情况下的跟踪实验实图。

图 1中3个视频序列包括尺度、姿态变化及背景干扰的影响。在经常发生姿态变化的animal视频序列中，L1T和CS_CT从一开始就没能跟踪上目标，之后也没能找回目标。而TLD算法在第55帧之后开始丢失目标，之后也没能找回目标。其余算法跟踪效果都很好，本文算法从始至终都能稳定地跟踪上目标。在cliffbar视频序列中，主要是尺度发生变化并伴有旋转，MTT算法容易受背景的干扰，在第55帧时就已经丢失目标，并在之后没能找回目标。L1T算法也受背景的干扰没能跟踪到目标的精确位置。而CTP能够一直跟踪上目标。但是本文算法仍然能够稳定地跟踪目标。David视频序列在开始时有光线偏暗的影响，其中MTT算法和CS_CT算法受此影响比较大而发生跟踪偏移的现象，随着偏移逐帧的累积最后丢失目标。CTP算法不受这些干扰的影响，一直能良好地跟踪目标。

图 2中3个视频序列主要有遮挡及复杂背景干扰的影响。其中faceocc视频序列有较多的半遮挡的情况，ODFS算法、MTT算法和L1T算法受次影响比较大而发生偏移，其余算法跟踪情况比较好，CTP和FCT跟踪效果最好。football视频序列中，TLD从第56帧开始就丢失了目标，之后一直跟踪错误的目标，L1T算法在第153帧开始产生跟踪偏差，累积到第336帧发生了目标遮挡后丢失了目标。CTP算法开始跟踪较好，并在第153帧中有目标发生部分遮挡的情况下仍然能够稳定的跟踪上目标。

shaking视频序列背景比较复杂，多数跟踪算法都没能跟踪上目标，第11帧中，MTT算法偏移情况最大，也最早的丢失目标，第78帧中，TLD算法、CT算法、L1T算法和MTT算法都丢失了目标，到第237帧中CS_CT也丢失了目标，最后到345帧FCT也发生了跟踪偏移，相较下CTP算法偏移最小。

图 3中主要是旋转、遮挡的影响，singer1视频序列中，拍摄角度经常发生变化造成目标发生旋转形变，其中FCT算法跟踪效果最差，从第16帧开始发生偏移最后逐渐丢失目标。TLD算法跟踪框缩放的精度不高，最后完全丢失目标。MTT算法在第332帧开始丢失目标。其余算法跟踪效果都很好。tiger2视频序列经常发生旋转并有部分遮挡的情况，属于比较难跟踪的视频序列，在第101帧时ODFS和L1T都向目标的左上角发生偏移，CT和MTT都向目标的下方发生偏移，TLD向目标的上方偏移，到第261帧时L1T和TLD彻底的丢失了目标。Twinnings视频序列主要旋转和缩放的影响，在前91帧以内所有算法都跟踪较好，到131帧后,ODFS发生了明显的偏移，在到221帧后MTT算法和CS_CT算法也发生了明显的偏移。最后到356帧，CT算法跟踪丢失目标。只有CTP和FCT能一直跟踪上目标。

本文将粒子群优化算法与压缩跟踪算法相结合，提出一种更加快速准确的压缩跟踪算法，并通过对结合了粒子群优化的压缩跟踪算法的跟踪效果进行分析，得到了若干有指导意义的结论。与常见的7种跟踪算法相比，本文提出在搜索区域进行搜索候选目标时，采用粒子群优化算法代替每隔一个像素采集一个候选目标的方式，达到减少分类器分类运算次数的目的，从而提高了算法的效率。在跟踪发生遮挡时，采取粒子群优化算法进行全局搜索，这样可以更加的发挥粒子群优化算法的全局搜索的能力，从而提高了算法的抗遮挡能力和准确性。本文算法能用于智能视频监控系统中提高监控系统的智能化性能，今后将重点研究分类方法，用于改善贝叶斯分类方法的性能，提高分类的精度和效率，从而提高跟踪算法的性能。