基于超像素和判别稀疏的运动目标跟踪算法

邱晓荣，彭 力，刘全胜2，

1.马来西亚管理科学大学 信息科学与工程学院，雪兰莪 莎阿南 40100

2.无锡职业技术学院 物联网技术学院，江苏 无锡 214121

3.江南大学 物联网工程学院，江苏 无锡 214122

1 引言

运动目标跟踪是指在连续的视频或图像序列中运用在线跟踪算法对运动目标进行状态估计和跟踪的过程。作为机器视觉领域的重要研究方向，运动目标跟踪已被广泛应用于视频监控、事件检测、运动分析等领域。近年来，相关科研人员对常用的运动目标跟踪算法进行了广泛而有效的研究，Kristan等人[1]评估了70种有效算法在60个短视频序列上的跟踪效果，用以解决跟踪过程中遇到的目标遮挡、光照变换、运动变换、尺寸变换、摄像机运动等干扰问题。根据Wu等人[2]所做的研究，一个完整的运动目标跟踪算法通常由表观模型、跟踪策略以及更新策略3部分组成。其中如何构建表观模型是首要考虑的问题，表观模型必须能够精确地描述运动目标，可用于评价某一时刻候选目标与模板的相似程度。

根据表观模型的不同表示方式，一般可以分为生成式算法和判别式算法两大类。生成式算法一般基于全局特征模板匹配或基于子空间学习方法，前者可区分度较高，后者不变性较好。经典的生成式算法有VTD[3]、L1APG[4]等，但此类算法一般不会考虑运动目标周围的背景信息，以致在相似混杂背景干扰下运动目标跟踪效果较差。判别式算法一般基于局部特征把跟踪问题转换成前景和背景的二元分类问题，经典的算法有TLD[5]、ASLA[6]等，此类算法通过分类器分离出目标与背景，同时结合在线更新策略，取得了较好的跟踪效果。近年来，Wang等人[7]提出了SPT算法，该算法充分利用了中层视觉线索超像素的特点，能够较好地利用目标周围背景信息应对重度遮挡、非刚性变换等干扰因素的影响。Zhong等人[8]提出了生成式算法和判别式算法相结合的稀疏跟踪模型，目标的表观模型由稀疏的SGM和SDC两种模型混合而成。吉训生等人[9]提出了基于HOG特征对目标几何和光照的不变性，构建在线判别稀疏字典，可以精确地区分目标和背景，降低漂移概率。孙凯等人[10]提出基于空间金字塔、稀疏编码和多方位均值偏移的运动目标跟踪算法，通过空间金字塔模型、局部模型和全局模型相结合抑制噪声及光照的变化。Fan等人[11]提出基于传统SPT和BoW算法构建BoS表观模型，取得了较好的跟踪效果。

受上述相关研究的启发，本文提出了一种超像素与判别稀疏相结合的运动目标跟踪算法。该算法在传统SPT算法的基础上加入了一个判别稀疏函数，在由目标和背景信息构成的超像素字典上通过ℓ1范数最小化框架求解候选目标的稀疏系数，同时结合粒子滤波框架和在线字典更新策略完成目标跟踪。实验结果表明，本算法构建的运动目标表观模型具有较好的鲁棒性，更好地实现了目标和背景的区分，能够有效地应对目标遮挡、非刚性变换、光照变换等干扰因素的影响。

2 基于超像素构建初始表观模型

2.1 超像素分割

超像素是指由相邻像素构成的像素块，这些像素块具有相似的亮度、颜色、纹理等方面的特征。同传统的形状固定的像素网格相比，超像素将原始图像分割成了具有感知意义的中层视觉线索，可作为后续图像处理任务的预处理步骤，是当前视觉领域的一项关键技术。

Achanta等[12]对基于超像素的图像分割做了归纳和对比，其中最为快速高效的算法是SLIC算法，其基本原理如式（1）所示。其中[l,a,b,x,y]表示像素点的LAB颜色模型和二维坐标，[Nc,Ns]表示[dc,ds]的归一化参数。

SLIC算法的特点是在不损坏原有图像目标区域边界的前提下，根据超像素个数、颜色空间相似度进行图像分割。超像素个数越小，分割图像所得的超像素数量越少。颜色空间相似度越小，超像素内部亮度渐变平缓、突变梯度较小。

2.2 超像素字典的生成

为了能够在跟踪起始阶段快速有效的建立运动目标的表观模型，本文选取待测视频序列的前5帧图像构建初始超像素字典，相关步骤如下：

（1）在跟踪的初始阶段，运动目标前景和背景一般变化不大，因此可以基于MeanShift算法在前5帧求出最优目标区域，再用白色虚线框标出观测区域，用白色实线框标出目标区域。其中观测区域的边长是目标区域对角线长度的1.5倍，观测区域与目标区域非重叠部分可视为背景区域，如图1（a）所示。

（2）如图1（b）所示，基于SLIC算法对前5帧的观测区域分割超像素，设置每帧超像素个数为300、紧凑度为10，并用sprn表示第n帧的第r个超像素。

（3）如图1（c）所示，继续对所有超像素进行HIS特征提取，获得归一化后的颜色直方图，并用 frn表示第n帧第r个超像素的特征向量。

（4）如图1（d）所示，使用K-Means算法对所有超像素的特征向量进行聚类，用 fci表示第i个聚类中心的HIS归一化特征向量。同时，计算各聚类的目标背景权值Wi，如式（2）所示：

图1 超像素字典的生成过程

其中Wi的取值范围为[0，1]，R+(i)表示第i个聚类区域与目标区域的重合面积，R-(i)表示该聚类区域与背景区域的重合面积。Wi越大，该聚类属于目标区域的几率越大，反之Wi越小则属于背景区域的几率越大。然后设定一个用于区分前景背景的阈值W0，将各聚类权值Wi的大小降序排列，大于W0的聚类属于前景超像素字典，小于W0的聚类属于背景超像素字典，这样就构成了可用于判别稀疏的初始超像素字典Dsp=[,]，如式（3）所示。其中n表示聚类个数，k表示属于目标区域的聚类个数。

3 基于判别稀疏进行运动目标跟踪

3.1 粒子滤波框架

运动目标实时在线跟踪过程中，直接对场景中所有内容进行相似度匹配，需要处理大量冗余信息，运算量大且没有必要。因此利用跟踪策略搜索算法有选择地缩小搜索区域并进行最优匹配具有非常重要的意义。常见的跟踪策略主要有卡尔曼滤波和粒子滤波两种算法。卡尔曼滤波算法一般只适用于线性高斯系统，而粒子滤波算法是一种基于贝叶斯蒙特卡洛采样技术的最优估计算法，它无需存储和再处理先前的测量数据，可以直接以递归的方式对测量数据进行序贯处理，节省了大量计算和存储空间，特别适用于非线性非高斯的运动目标跟踪系统。

粒子滤波算法可以分为预测和更新两个阶段，分别如式（4）和式（5）所示。定义 xt=[ ]lx,ly,θ,s,α,ϕ 为仿射向量，各仿射参数相互独立且呈标准高斯分布，分别表示运动目标在第t帧的水平位移、垂直位移、水平方向尺度、旋转角、高宽比和扭角。zt表示第t帧的观测值，p(xt|xt-1)为状态转移概率，p(zt|xt)为xt的似然函数。

3.2 判别稀疏函数的表示

粒子滤波框架下，在当前帧t中一般基于上一帧的最优候选粒子，在运动目标中心位置附近基于一个非常小的仿射向量，随机创建n个候选粒子，然后基于表观模型字典判定最优粒子。传统ℓ1范数最小化的稀疏表示如式（6）所示，其中前一项是损失函数，用于保证训练误差最小，后一项是正则化函数，λ非常小，防止过度拟合。

但是传统的稀疏表示方法不具备判别性，并不适合信号分类问题的求解。为了更好地结合具有目标背景判别的超像素字典Dsp，本文在传统稀疏表示算法的基础上在‖Y - DspX中加入了判别函数的内容，如式（7）所示：

式（7）中除正则化函数λ‖X ‖1外，其余项均可微且严格收敛，可求出相关最优解。其中[||Y-Dsp+||Y-+]是具有判别功能的稀疏函数，表示候选粒子与整个超像素模板的全局相似度，表示与超像素字典中目标模板的局部相似度，表示与超像素字典中背景模板的局部相似度。从全局角度看，要求Y≈DX。从局部角度看，要求很小，表示目标应该能够被超像素目标模板较好地重构，而要求很小，表示目标不能被超像素背景模板较好地重构。这样就可以最大限度地保证跟踪结果保留跟踪目标信息，排斥背景信息。

3.3 最优跟踪目标的确定

为了能够从粒子滤波框架的众多候选粒子中选出最优粒子作为当前帧的跟踪结果，还需通过式（8）计算候选目标和超像素字典Dsp之间的相似性。

其中，ξ1=||Y-表示目标模板的相似度，ξ2=||Y-表示背景模板的相似度，η是一个很小的数。一般当H值最小时说明对应的候选粒子能够较好地跟踪运动目标。

3.4 遮挡检测处理

确定了当前帧的最优跟踪目标之后，还需进一步判定目标在运动过程中是否受到遮挡，以便后期有效地更新表观模型。如式（9）、式（10）所示，本文依据重构误差矩阵E计算当前帧最优候选目标的遮挡系数O。

其中，ρ0表示重构误差阈值，当重构误差小于ρ0，表明该部分区域未发生遮挡，对应的oi设为0；反之有遮挡时，对应的oi设为1。

4 运动目标表观模型的在线更新

在实际跟踪过程中，目标和背景将受到多种因素的影响发生相关的变化，特别是背景的变化更为频繁且无一定的相关性。为此，需要在线更新运动目标的表观模型，以便及时修正运动目标的前背景变化，整个更新过程可以参考2.2节的相关内容，包括样本选择和聚类更新两个步骤。

在样本选择阶段，需要判定当前帧的最优候选粒子是否存在严重遮挡。本文算法根据式（10）计算目标受到遮挡的比率。当实际遮挡系数O大于指定遮挡阈值O0时，表明存在严重遮挡。这时，为了保留未遮挡时运动目标的相关信息，提高了跟踪算法的有效性和鲁棒性，需要去除表观模型样本集中时间最早一帧的超像素信息，在样本集中保留最后5帧的位置不变，将当前帧的超像素信息存放到倒数第6帧的位置。而当不存在严重遮挡时，剔除最早一帧的超像素信息后，直接把当前帧的相关信息放在样本集的末尾即可。

聚类更新阶段，本文算法每隔15帧通过K-Means算法更新超像素聚类的相关信息。由于在实际跟踪过程中，当运动目标被严重遮挡时，聚类结果仍然保留了未遮挡时运动目标的相关信息，有效提高了跟踪算法的鲁棒性。

5 实验结果分析

为了验证算法能否在复杂环境下进行有效跟踪，本文按难易程度分别基于bird1、walking2、board、liquor等4个图像帧序列，将本文算法与SPT[7]、L1APG[4]、SCM[8]、ALSA[6]等4种经典算法做了定量和定性两方面的对比分析。相关标准图像帧序列和算法源码可访问文献[2]提供的网址：http：//cvlab.hanyang.ac.kr/tracker_benchmark/index.html。

算法相关实验都基于Matlab平台，本文设定阈值W0=0.15来划分超像素字典中的目标和背景，式（6）中防过度拟合参数 λ=0.01，式（8）中η=0.2，式（10）中重构误差阈值ρ0=0.05，遮挡阈值O0=0.2。

5.1 定量分析

本文算法使用以下两个标准来定量分析跟踪的精度：

（1）中心距离误差。如图2所示，各子图显示了5种算法在指定图像帧序列中实时跟踪到的目标中心点与初始标定的目标中心点之间的像素距离。

表1显示了5种算法分别对应4个标准图像帧序列的跟踪成功率，并用黑色粗体标识了各视频图像帧序列的最优算法。

图2 中心距离误差（像素）

图3 视频序列的跟踪结果比较

表1 跟踪成功率

5.2 定性分析

实验1 bird1图像帧序列较为复杂，其中的运动目标在做快速移动的同时，受到非刚性变换、移出视野等内外部因素的影响。例如，第25帧处目标处于快速飞行过程中，同时不停地在做非刚性变换，此时ALSA算法发生了较大的偏移，其余4种算法能够实现较好的跟踪效果，其中本文算法的跟踪精度最高。第185帧处目标刚刚从满屏遮蔽的云层中飞出，SPT算法、ALSA算法和本文算法能够迅速由一定的漂移状态重新精准定位目标。第309帧处目标呈现方式由尾部视图转到背部视图，本文算法的跟踪精度比SPT算法更高。

实验2 walking2图像序列中的目标在运动过程中主要受到尺度变化、遮挡等干扰因素的影响。例如，第228帧和第372帧处目标在行进过程中，两次受到了移动物体的部分遮挡，除本文算法外，相关算法都开始产生了一定的漂移。第450帧处目标的尺度较初始尺度大幅变小，同时还受到了前向静止物体的干扰，传统SPT算法发生了较大的漂移，本文算法结合了判别稀疏的相关信息后，较为精准地跟踪到了目标。

实验3 board图像帧序列中的运动目标受到了尺度变化、运动模糊、移出视野等干扰因素的影响。例如，第32帧处运动目标快速向右移动，本文算法能够较好地跟踪目标，其他算法都产生了一定程度的漂移。第120帧处运动目标部分移出了视野范围，第437帧处目标由于快速运动产生了运动模糊，本文算法都能够较为精准地跟踪到目标。

实验4 liquor图像帧序列中的运动目标受到了光照变换、尺度变化、遮挡、快速运动等干扰因素的影响。例如，第420帧处运动目标围绕左边的酒瓶做了一次逆时针旋转运动，本文算法能够较好地跟踪目标，其他算法都产生了一定程度的漂移。第503帧和第1 183帧处运动目标多次受到了较为严重的遮挡，本文算法都能够较为精准地跟踪到目标。

6 结束语

本文提出了一种基于超像素和判别稀疏的运动目标跟踪算法。该算法在传统SPT算法的基础上，构建了包含目标和背景信息的超像素字典，同时引入判别稀疏函数以及ℓ1范数最小化框架，实现了运动目标的在线跟踪。其优点在于当目标处于重度遮挡、非刚性变换、光照变换等严重干扰因素的影响下，算法能够准确地区分目标和背景，具有较好的稳定性和鲁棒性。

虽然本文算法能够在多种复杂场景的图像序列中取得较好的跟踪效果，但由于在初始构建和在线更新超像素聚类字典过程中用到了SLIC算法、K-Means算法、判别稀疏算法、粒子滤波算法，这些都提高了本文算法的运算复杂度。因此后期的研究工作可以着眼于对超像素聚类算法做相应的改进，以使现有K-Means算法更快更准地找到超像素聚类的中心，这样可以使本文算法具有更好的实时性和准确性。