基于低秩约束的逆向联合稀疏跟踪算法

陈颖频，孔俊雅，余超群，林 晨，蒋旻佚，罗崇淼，虞虹玲

(1. 电子科技大学数学科学学院, 四川 成都 611731; 2. 闽南师范大学物理与信息工程学院，福建 漳州 363000)

0 引言

目标跟踪是计算机视觉领域重要的研究问题，具有广阔的应用前景。因跟踪过程中场景的多变性，使跟踪面临局部遮挡、光照强度变化、尺度变化、旋转和背景散乱等挑战[1]。

近年来，稀疏表示[2-3]被广泛应用于目标跟踪。稀疏表示最初应用于人脸识别[4]，能在部分遮挡场景下获得良好的鲁棒性。受此启发，有学者将稀疏表示引入目标跟踪，并提出基于l1范数的目标跟踪算法[5]，开创了将稀疏表示应用于跟踪领域的先河，许多基于稀疏表示的目标跟踪算法被相继提出。其中，基于正向稀疏表示的目标跟踪算法以目标模板为字典，选取少量字典原子表示候选模板，但这类方法忽略了目标模板之间的时空相似性，且候选模板数量较大，导致算法计算量巨大。2014年，文献[6]中提出逆向稀疏表示跟踪模型，该模型利用候选粒子逆向稀疏表示目标模板，因模板数远小于采样粒子数，跟踪器只需求解少量凸优化问题，运算量大幅下降。

逆向稀疏表示跟踪模型容易受到背景散乱的影响。考虑到目标在背景中运动存在一定的相似性，本文在目标模板中施加低秩约束[7]压制背景信息对目标跟踪的干扰，挖掘相邻帧之间目标的相似性。为进一步挖掘目标的纹理特征，降低运动模糊、形变等因素对跟踪性能的影响，本文在逆向稀疏表示跟踪模型中引入局部二值模式 (local binary pattern, LBP)[8-9]特征。为避免目标模板被局部“污染”并及时更新目标的局部有效信息，本文利用方向梯度直方图(histogram of oriented gradient, HOG)[10]区分目标表观模型中的有效信息(如目标形变、目标快速运动导致的表观变化)和无效信息(如目标局部遮挡、全局遮挡等)。

1 相关理论

1.1 粒子滤波框架

粒子滤波实质上是一种基于序贯蒙特卡罗滤波方法[11]，利用一系列随机抽取样本的重要性权重代替状态的后验概率分布。粒子滤波包括以下4个阶段：

1)撒粒子阶段：令x1=[dx,dy,s,θ,r,φ]表示第一帧目标的状态(dx,dy,s,θ,r,φ这6个仿射参数分别代表水平扰动量、垂直扰动量、缩放比例、旋转角度、高宽比和切边角度)。第f帧的运动状态转移概率p(xf|xf-1)定义为

p(xf|xf-1)=N(xf-1,Ψ)，

(1)

2)加权阶段：计算每个粒子的权重，即

(2)

将式归一化得

(3)

3)重采样阶段：对粒子按照权重进行筛选，即复制高权重粒子并去除低权重粒子。

4)输出阶段：对粒子加权求和，即

(4)

1.2 联合稀疏表示

如图1所示(颜色越深的块对应的值越大，最大为1)，左边矩阵通过行和稀疏收缩[12]可获得右边具有联合稀疏(即行和稀疏)特性的矩阵，这一过程称为联合稀疏表示。虚线框选中的块表示仅具有稀疏性而不具有行和稀疏的编码，通过联合稀疏约束能有效剔除这些编码。联合稀疏约束通常以l2,1范数[6]最小化加以刻画。

图1 联合稀疏表示示意图Fig.1 Schematic diagram of joint sparse representation

1.3 低秩约束

考虑到视频中相邻帧之间目标具有相似性，本文通过对目标矩阵施加低秩约束，降低背景散乱对目标的影响。

具体地，对目标模板采取如下约束：

(5)

对Y做SVD分解，即

Y=UΣVT。

(6)

可通过式(7)得到式(5)的最优解[13]：

(7)

式(7)中，Θτ0(Σ)=sign[vec(Σ)]·max(0,|vec(Σ)|-τ0)是软收缩算子，vec表示矩阵列向量化算子。

2 基于低秩约束的逆向联合稀疏跟踪方法

2.1 正负专家目标模板与候选模板的预处理

首先构建基于模板视觉特征的正负专家系统，如图2所示，使用大小为p×p的滑动窗口将正目标模板Pn∈Q×Q(n=1,2,…,N表示模板在模板集中的序号)划分为若干个图像块p×p，然后将其用拉列算子vec处理得到p2×1(k=1,2,…,K)，并构建目标正模板为了有效压制背景信息对跟踪性能的干扰，本文在当前帧的上一帧远离目标的区域随机选取N个负模板Nn∈Q×Q，然后用p×p的滑动窗口将负目标模板划分得到表示第n个负样本的第k个局部块)，由此构建包含背景信息的负专家系统。

图2 正负专家目标模板生成过程Fig.2 The process of generating the positive and negative expert object templates

利用当前帧的上一帧目标的状态，在新一帧视频图像中利用式(1)产生随机粒子，获取如图3所示的M个候选粒子，以得到M个候选模板C1,C2,…,CM，其中Cm∈Q×Q(m=1,2,…,M)。再用滑动窗口将其分割成K个局部图像块其中p×p。

图3 候选模板获取过程Fig.3 The sampling process of candidate templates

2.2 联合稀疏编码模型

图4 低秩逆向联合稀疏表示的稀疏编码稀疏建模Fig.4 Sparse coding modeling based on low-rank inverse joint sparse representation

(8)

式(8)中，Xk表示稀疏编码系数，‖Xk‖2,1为矩阵Xk的l2,1范数。矩阵X∈M×N的l2,1范数定义为

2.3 联合稀疏编码求解器

在迭代过程中，由于不同局部图像块的外观表示模型是独立的，可将稀疏编码稀疏的能量泛函定义为

(9)

(10)

式(10)中，〈X,Y〉表示计算两个矩阵X,Y的内积；λ为二次惩罚系数。

由于Xk，S和ΛS之间是相互去耦合的，可将式(10)转化为Xk、S和ΛS的子问题并分别进行计算。

2.3.1Xk子问题求解

Xk子问题对应的目标函数为

(11)

对式(11)关于Xk求偏导并置零得

(12)

式(12)中，E∈M×M表示单位矩阵。

2.3.2S子问题求解

S子问题对应的目标函数为

(13)

(14)

式(14)中，G(i,:)表示G矩阵的第i行向量。

2.3.3ΛS子问题求解

ΛS子问题对应的目标函数为

(15)

利用梯度上升法可计算ΛS，具体如下：

(16)

式(16)中，γ是学习率。

2.4 粒子评估机制

2.4.1联合稀疏评价机制

若第m个粒子的编码Xk的第m行系数都较大，则说明该粒子与目标模板较相似，可根据编码行和的大小初步优选粒子。初步优选粒子的判定条件为

‖Xk(m,:)‖2>τ1，

(17)

式(17)中，τ1∈[0，max(‖Xk(m,:)‖2)]是设置的阈值。

(18)

式(18)中，τ2是设置的阈值，取值范围为[0,1]；若式(17)、(18)两者同时成立，则该粒子打1分，否则打0分，从而得到K个大小为M×1的指示向量ik(k=1,2,…,K)，其过程如图5所示。

图5 指示向量生成过程Fig.5 The calculation of index vector

将图5获得的指示向量ik组成大小为M×K的矩阵I，再将I求行和得到一个列向量，如图6所示。在此基础上计算每个粒子的分数w1，再通过阈值控制，筛选出I个粒子s1,s2,…,sI，其中si(i=1,2,…,I)表示选择的粒子在原候选粒子集合中的编号。若粒子的分数低于设置的阈值，将其分数清零，则该粒子被淘汰，如式(19)所示：

(19)

式(19)中，τ3为设置的阈值，取值范围为[0,max (‖I(m,:)‖1)]，粒子的联合稀疏权值ω1(si)计算如下：

(20)

图6展示了联合稀疏粒子评价的过程。通过上述粒子评价选取得分靠前的I个候选粒子，再淘汰大部分稀疏编码较小且与正模板相似性较小的候选粒子，从而减小后续工作的计算量。

图6 联合稀疏粒子打分体系Fig.6 Joint sparse probability scoring system

2.4.2判别式打分机制

(21)

式(21)中，W∈N×I×K(i=1,2,…,I)表示相似性度量张量。

如图7所示，本文采用判别式非最大值抑制投票系统。打分体系通过式(21)计算正目标模板集中的每个局部模板与候选粒子的相似度，每个正目标模板区块都选取一个与该区块相似度最高的粒子，对该粒子加1分，再用直方图统计每个粒子的总得分情况。类似地，每个负目标模板区块也选出相似度最高的候选粒子，用直方图统计每个候选粒子与负模板的相似程度。然后将正模板相似性直方图减去负模板相似性直方图获得w2(si)∈I×1，再将得分归一化得到第二步打分的加权权重：

(22)

图7 判别式打分机制Fig.7 Discriminative scoring mechanism

2.4.3LBP纹理特征评价机制

首先将优选粒子对应的图像Csi∈Q×Q进行(local binary patterns, LBP)纹理特征提取，获得LBP(Csi)∈Q×Q，然后计算其与正目标模板集中随机抽取模板Pr(r为1到N之间的随机数)LBP特征的余弦距离，从而获得第三步的粒子打分w3(si)∈I×1，即

(23)

将式(23)归一化得

(24)

然后对粒子做一个筛选，即

(25)

式(25)中，τ4是人为设定的阈值，取值范围为[0,1]。

最后将上面三步求得的ω1,ω2和ω3计算ωf(i)，即

(26)

综上所述，三步评价法：通过联合稀疏评价机制可以选取最具联合稀疏性的粒子；通过判别式非最大值抑制投票评价机制可以选取与目标模板空间相似性最高的粒子；通过LBP纹理特征评价机制可选取与目标模板整体相似性最高的粒子，一定程度上减轻运动模糊、形变等因素带来的干扰。通过三步评分法筛选出的粒子可应对目标的多种外观变化，达到鲁棒跟踪的效果。

2.5 局部模板更新机制

在目标跟踪过程中，模板更新策略至关重要。若不更新模板则无法及时感知模板的表观变化，而无原则地整体更新模板则会引入无效的表观变化，如：局部遮挡、运动模糊等。

传统跟踪算法的模板更新机制常采用整体更新法。这种做法的弊端在于，一旦检测到目标被遮挡，未被遮挡区域的有效表观变化信息也将被忽略。为解决这一问题，本文提出了局部模板更新机制对最优候选目标进行分块相似性评价，若局部区域相似度过低，则该区域被判定为遮挡状态，不更新该区域模板，反之则更新局部模板。下面简要介绍局部相似性的评价方法。

(27)

(28)

接下来计算最优估计粒子图像与目标模板的相似性度量矩阵W(假定W(0)=1，为元素全为1的矩阵)，该矩阵元素计算如下：

(29)

以W(old)表示上一帧的相似性度量矩阵，根据式(30)可判断最优粒子的局部图像块是否被遮挡：

(30)

3 实验及结果分析

实验环境如下：笔记本配置为Inter(R) Core(TM) i5-5200U CPU @ 2.20 GHz 4 GB，测试序列选自OTB100数据集[14]，该数据集视频序列存在光照变化、旋转、遮挡、背景散乱和尺度变化等因素。为了评估本模型的性能，将所提低秩约束的逆向联合稀疏跟踪方法(low based reverse joint sparse tracking, LRRJST)与其他9个先进的跟踪方法进行定量和定性比较。这些方法包括背景感知相关滤波跟踪(learning background-aware correlation filters, BACF)[15]、学习用于视觉跟踪的空间正则化相关过滤(learning spatially regularized correlation filters, SRDCF)[16]、带检测跟踪学习算法(tracking learning detection, TLD)[17]、具有特征集成的比例自适应核相关滤波器跟踪器(scale adaptive kernel correlation filter, SAMF)[18]、核相关滤波算法(kernel correlation filter)[19]、判别式相关滤波快速尺度跟踪算法(discriminative scale space tracker, DSST)[20]、基于长时相关滤波的方法(long-time correlation filter, LCT)[21]、基于稀疏表示模型的局部加权逆向联合稀疏模型(locally weighted reverse joint sparse model, LWRJM)[21]、稀疏协作跟踪器 (sparse collaborative model, SCM)[22]和多目标跟踪(multiple target tracking，MTT)[23]。

表1给出本文展示跟踪序列存在的挑战因素。

表1 视频序列及其描述Tab.1 Video sequences and their description

3.1 关键模块验证

3.1.1低秩约束对比实验

为验证加入低秩约束对跟踪结果是否有影响，比对了有低秩约束的算法和无低秩约束的算法的跟踪结果，并根据跟踪结果进行分析说明。如图8所示，在第13帧时，目标背景未发生变化，绿色跟踪框(有低秩约束)和蓝色跟踪框(无低秩约束)都可以对目标实现较好的跟踪，而从第59帧到第112帧背景发生较为明显的变化，这时蓝色跟踪框跟踪失效，而绿色跟踪框依然能准确跟踪目标，说明本文提出的低秩约束可有效降低背景信息对目标跟踪的干扰。

图8 有无低秩约束对比实验Fig.8 Comparison experiment with or without low rank constraint

3.1.2判别式打分机制对比实验

为反映判别式打分机制的有效性，比对了采用判别式打分机制的算法与没有采用判别式打分机制的算法的跟踪结果，如图9所示。在第65帧时，目标尺寸变小，代表无判别式打分机制跟踪算法的蓝色跟踪框对目标的跟踪产生偏移，而代表采用判别式打分机制的LRRJST算法的绿色跟踪框可以较准确跟踪目标。在第190帧和303帧时，目标进行了平面内旋转和平面外旋转，其中头部、脸部和侧脸发生较大目标外观变化，蓝色跟踪框无法捕捉到目标，绿色跟踪框仍可准确跟踪目标。在第456帧，出现遮挡场景，蓝色跟踪框受干扰，而绿色跟踪框依然准确跟踪目标。因此，在尺度变化、旋转和遮挡等情况下，采用判别式打分机制均可应对目标外观变化。

图9 有无判别式打分机制对比实验Fig.9 Contrast experiment with or without discriminative scoring mechanism

3.1.3LBP纹理特征打分机制对比实验

为验证提取LBP纹理特征的有效性，比对了有LBP特征提取的算法和无LBP特征提取算法的跟踪结果，如图10所示。在第19帧时，目标进行尺度变化，代表无LBP特征提取算法的蓝色跟踪框产生偏移，而代表有LBP特征提取算法的绿色跟踪框可精准跟踪目标。在第27帧时，目标进行旋转，蓝色跟踪框仍没有准确跟踪目标，而绿色跟踪框未受影响。在第39帧时，目标模糊，蓝色跟踪框已无法跟踪目标，而绿色跟踪框仍可紧跟目标。在第51帧，目标形变，外观产生了较大变化，绿色跟踪框仍准确跟踪目标。可见，采用了LBP纹理特征提取的算法，在目标发生运动模糊、形变等场景下都可较好地进行跟踪。

图10 有无LBP特征提取对比实验Fig.10 Contrast experiment with or without LBP feature extraction

3.1.4有无局部模板更新机制对比实验

为验证本文采用的局部模板更新机制的有效性，对比没有采用局部模板更新机制的各种效果，如图11所示。在第84帧时，蓝色跟踪框(无局部模板更新)对目标的跟踪已经产生偏移，绿色跟踪(有局部模板更新)框准确跟踪目标。在123帧时，目标经过白车的后车窗，被大面积遮挡，由于车窗颜色和目标所穿裤子的颜色极其相似，蓝色跟踪框发生错误跟踪，而绿色跟踪框依然准确跟踪。在216帧时，目标的下半身被蓝黑色轿车再次遮挡，此时无局部模板更新机制的算法中，目标模板已经被“污染”，无法准确跟踪目标，而绿色跟踪框仍准确跟踪目标。在268帧时，目标经过蓝黑色轿车，绿色跟踪框仍未受遮挡影响。可见，在部分遮挡或全局遮挡影响目标外观时，采用局部模块更新机制可取得较好跟踪效果。

图11 有无局部模板更新对比实验Fig.11 Comparison experiment with or without partial template update

3.2 定量分析

成功率通过计算跟踪框的重叠率得到。重叠率的计算公式为

(31)

式(31)中，Spre表示预测跟踪框的面积，Str表示标注跟踪框的面积。

精确度根据中心点误差计算得出。中心点误差的计算公式为

(32)

式(32)中，(xd,yd)为预测跟踪框的中心点，(xt,yt)为真实的跟踪框的中心点。

图12是10个算法在OTB数据库不同视频序列场景下的综合比对的精确度和成功率图，图中右上角显示算法排名情况。如图12(a)所示，LRRJST算法的精确度排名第一，达到了0.850；如图12(b)所示，LRRJST的成功率排名第一，达到了0.780。对比说明提出方法跟踪性能较优。

图12 10种算法的精确度与成功率综合对比图Fig.12 A comprehensive comparison of the success rate and accuracy often algorithms

表2给出了各跟踪算法在不同视频序列中取得的平均跟踪重叠率，其中数值越大，表明跟踪性能越好，最优跟踪指标被加粗显示。从表中可看到，提出算法LRRJST在Football、Panda、Vase、Walking2视频序列中的平均跟踪重叠率分别为0.78、0.53、0.83、0.91，均高于其他9个主流算法，总平均值也达到了0.74，仅次于SRDCF。

表3给出了各跟踪算法在不同视频序列中取得的平均中心点误差，其中数值越小，表明跟踪框与目标真实位置的误差越小，最优跟踪指标被加粗显示。本文算法LRRST在Vase、Jumping 、Walking2视频序列的中心点误差分别为10.42、4.33、1.05像素，高于其他9个主流算法，总平均值像素误差为6.4像素，仅次于BACF。

表2 各跟踪算法在一些视频中的平均跟踪重叠率Tab.2 The average overlap rate of each algorithm in some video sequences

表3 各跟踪算法在一些视频中的平均中心点误差Tab.3 Average center error of each tracking algorithms in some video sequences

3.3 定性分析

图13表示LRRJST算法与所比对算法在OTB100数据集上的跟踪情况，本文只截取部分帧的跟踪结果并加以说明(不同颜色的跟踪框代表不同的跟踪算法)。

图13 OTB数据集不同序列的跟踪结果比较Fig.13 Comparison of tracking results on different sequences of OTB dataset

下面针对几种挑战因素进行定性分析：

1) 旋转。图13中的视频序列David3和Dragon Baby存在平面内旋转和平面外旋转的情况。从图13中可以看到，LRRJST算法能有效地在旋转场景下跟踪目标。

2) 快速运动。图13中Jumping存在快速运动和运动模糊的情况。在Jumping视频序列中，目标在跳绳，只有LRRJST算法始终准确且稳定地跟踪目标。

3) 背景散乱。视频序列Football存在背景散乱的情况，视频中有一群穿着相似衣服和头盔的足球队员快速运动，只有LRRJST、LCT和KCF算法对目标实现准确跟踪。可见在目标模板中引入的低秩约束能有效处理背景散乱的跟踪场景。

4) 遮挡。图13中的David3、Faceocc2和Football均存在部分遮挡或者完全遮挡的情况，部分跟踪算法失效，而本文提出的算法始终能很好地应对目标表观变化。说明本文提出的局部模板更新机制能有效检测目标遮挡场景并避免目标模板被污染。

5) 尺度变化。图13(b)中，DragonBaby视频序列中，目标在与龙布偶打斗，在第50帧时，目标尺寸缩小，只有LRRJST算法稳定地跟踪目标，说明提出方法对尺度变化也有较好地跟踪效果。

4 结论

本文提出基于低秩约束的逆向联合稀疏跟踪算法，该算法创新点：1) 对目标模板施加低秩约束，降低背景散乱对目标的影响；2) 引入含背景信息的负样本视觉字典进行判别式打分，进一步降低背景信息对跟踪的干扰；3) 引入LBP特征描述目标的纹理特性，进一步提高粒子评分的可靠性；4) 在局部模块更新机制中引入HOG特征，通过计算图像块与目标模板之间的相似度筛选出目标中的有效表观变化信息，降低模板被污染的可能。实验结果表明，提出算法在旋转、快速运动、遮挡、尺度变化和背景散乱等情况均取得较好地跟踪性能。