Topological Potential Based Recommendation Trust Model for P2P Communities System

1.   引言

目标跟踪是计算机视觉领域中的基础研究课题，它是视频分析中的一项重要技术，其目标是利用视频数据估计目标的状态。目标跟踪在视频监控、车辆导航、人机交互、智能交通、运动分析和姿态估计等民用领域，以及视觉制导、目标定位和火力控制等军事领域均有重要的应用价值。近年来，虽然目标跟踪有了较大发展，但是其仍然面临复杂背景、目标变化和快速运动等诸多难题，目前仍然是计算机视觉领域中研究的热点问题。

受到结构化SVM在目标检测中应用的启发，Hare等人^[1]于2011年在ICCV上首次提出基于结构化SVM的目标跟踪方法Struck，2015年该文的扩展^[2]发表在顶级国际期刊IEEE Transactions on Pattern Analysis and Machine Intelligence上。Struck把目标跟踪看作结构化学习问题，避免了传统判别式跟踪的中间分类环节，显著提高了目标跟踪的性能。为了适应目标的变化同时又不丢失目标的时间上下文信息，Yao等人^[3]于2012年提出一种加权在线结构化SVM跟踪方法，进一步提升了结构化SVM跟踪的性能。为了提高遮挡与形变目标的跟踪性能，2013年，Yao等人^[4]又以在线算法Pegasos为基础，提出一种在线结构化SVM用于目标跟踪。为了解决目标跟踪中存在的模型漂移问题，2012年Bai等人^[5]提出一种在线拉普拉斯排序SVM跟踪。同样是为了应对模型漂移问题，Zhang等人^[6]于2014年提出了MEEM跟踪，该方法以在线SVM作为基础跟踪建立专家组跟踪目标，取得了较好的效果。2015年Hong等人^[7]利用在线SVM指导反向传播特定目标的CNN特征到输入层，进而建立特定目标的显著图跟踪目标，该方法建立的显著图保持了目标的空间结构，增强了目标跟踪的鲁棒性。2016年Ning等人^[8]基于对偶坐标下降原理提出一种对偶线性结构化SVM目标跟踪方法，该方法保证了目标跟踪的鲁棒性，同时又提高了目标跟踪的速度。2017年Wang等人^[9]提出LMCF跟踪，该方法利用相关滤波对基于结构化SVM的目标跟踪进行了加速。2018年Ji等人^[10]采用了与LMCF跟踪类似的思想来加速基于目标部件的结构化SVM跟踪。2019年Zuo等人^[11]提出一种基于离散傅里叶变换的交替优化方法求解相关滤波器，并设计了多通道支撑相关滤波器跟踪目标，进一步提升了基于SVM的目标跟踪的性能。

综上所述，基于结构化SVM的目标跟踪方法具有较优的跟踪性能，受到了广泛的关注，但是现有方法存在正样本和负样本不平衡的问题。针对基于结构化SVM的目标跟踪中存在的负样本和正样本不平衡的问题，本文提出一种代价敏感结构化SVM模型，基于对偶坐标优化原理设计了该模型的求解算法，并利用该算法实现了单尺度目标跟踪算法(Dual Liner Cost Sensitive Structured Support Machine, DLCS-SSVM)和多尺度目标跟踪方法(Scale Dual Liner Cost Sensitive Structured Support Machine, Scale-DLCS-SSVM)。利用OTB100数据集^[12]和VOT2019数据集^[13]对提出的目标跟踪方法进行了实验验证，并与现有的先进目标跟踪方法进行了比较。实验结果表明，本文提出的目标跟踪方法达到了预期的跟踪效果，与现有目标跟踪方法相比具有较好的性能。

2.   代价敏感和结构化支持向量机

2.1   代价敏感支持向量机

为了解决SVM中存在的正负样本不平衡的问题，文献^[14]提出一种代价敏感支持向量机。假设二分类训练数据集是$\{ ({\boldsymbol{x}_i},{y_i})\} _{i = 1}^N$，其中${\boldsymbol{x}_i} \in {{\boldsymbol{R}}^d}$是样本特征向量，${y}_{i}\in \rm{{+1},\rm{-1}}$是类别标签，则文献[14]提出的代价敏感支持向量机描述为

其中

w和b分别是SVM分类器的法向量和偏置，ξ_i是松弛变量，C, C₁, C_–1和κ是正则化参数。

2.2   结构化支持向量机

受到结构化SVM在目标检测中应用的启发，2011年Hare等人^[1]提出了基于结构化SVM的目标跟踪Struck。Struck把目标跟踪看作结构化学习问题，避免了传统判别式跟踪的中间分类环节，显著提高了目标跟踪的性能。在利用结构化学习器进行预测时，其目标是预测给定样本x∈R^d的结构化输出y∈Y，其中Y可以是任意结构输出空间。在基于结构化SVM的目标跟踪中，Y是矩形框空间，它的任一元素用(x,y,w,h)表示，其中(x,y)表示矩形框的中心位置，w和h分别表示矩形框的宽和高。假设训练数据为$\{ ({{\boldsymbol{x}}_i},{{\boldsymbol{y}}_i})\} _{i = 1}^N$, ${\boldsymbol{\varPhi }}({\boldsymbol{x}},{\boldsymbol{y}})$表示矩形框y在图像x上的特征向量，则可以通过式(3)学习一个参数为w的分类器。

其中，$f({\boldsymbol{x}},{\boldsymbol{y}},{\boldsymbol{w}}) = {{\boldsymbol{w}}^{\rm T}}{\boldsymbol{\varPhi }}({\boldsymbol{x}},{\boldsymbol{y}})$，分类器法向量w通过求解如下优化问题得到。

其中，${{\boldsymbol{\varPsi }}_i}({\boldsymbol{y}}) = {\boldsymbol{\varPhi }}({{\boldsymbol{x}}_i},{{\boldsymbol{y}}_i}) - {\boldsymbol{\varPhi }}({{\boldsymbol{x}}_i},{\boldsymbol{y}})$, C是正则化参数，${\xi _i}$是松弛变量。$L({{\boldsymbol{y}}_i},{\boldsymbol{y}})$是损失函数，表示预测输出矩形框y的结构误差损失。$L({{\boldsymbol{y}}_i},{\boldsymbol{y}})$由样本矩形y和目标矩形y_i的重合率定义，如式(5)所示。

其中

3.   代价敏感结构化SVM

3.1   代价敏感结构化SVM模型

现有基于结构化SVM的目标跟踪方法存在正样本和负样本不平衡的问题。如图1所示，与目标重叠区域较大的训练样本称为正样本，与目标重叠区域较小的训练样本称为负样本。目标跟踪需要在当前目标周围区域中进行采样更新表观模型。从图1可以看出，在采样得到的样本中，负样本的数量远大于正样本的数量，即负样本与正样本严重不平衡。其中，黑色实线是非代价敏感结构化SVM的超平面，红色虚线是代价敏感结构化SVM的超平面。当训练数据集不平衡时，SVM分类器对少数类的识别率较低，因此该问题制约了目标跟踪的性能。为了解决正样本和负样本不平衡对基于结构化SVM目标跟踪方法性能的影响，本文将文献[14]的思想引入到文献[1]提出的结构化SVM中，设计一种基于代价敏感的结构化SVM模型，描述为

图  1  结构化SVM目标跟踪中存在的正样本和负样本不平衡问题

下载: 全尺寸图片 幻灯片

其中，

${{\boldsymbol{\varPsi }}_i}\left( {\boldsymbol{y}} \right) = {\boldsymbol{\varPhi }}\left( {{{\boldsymbol{x}}_i},{{\boldsymbol{y}}_i}} \right) - {\boldsymbol{\varPhi }}\left( {{{\boldsymbol{x}}_i},{\boldsymbol{y}}} \right)$, $L({{\boldsymbol{y}}_i},{\boldsymbol{y}}) = 1 - s({{\boldsymbol{y}}_i},{\boldsymbol{y}})$，$s\left( {{{\boldsymbol{y}}_i},{\boldsymbol{y}}} \right) = \dfrac{{{{\boldsymbol{y}}_i} \cap {\boldsymbol{y}}}}{{{{\boldsymbol{y}}_i} \cup {\boldsymbol{y}}}}$。C⁺, C^–和C是正则化参数。m是阈值。当式(7)中损失函数$L({{\boldsymbol{y}}_i},{\boldsymbol{y}})$的值大于等于阈值m时，训练样本$({{\boldsymbol{x}}_i},{{\boldsymbol{y}}_i})$定义为负样本；否则当$L({{\boldsymbol{y}}_i},{\boldsymbol{y}})$值小于阈值m时，训练样本$({{\boldsymbol{x}}_i},{{\boldsymbol{y}}_i})$定义为正样本。

3.2   代价敏感结构化SVM算法

为了求解本文提出的代价敏感结构化支持向量机式(7)，使用拉格朗日乘子法可得到其对偶问题，为此引入拉格朗日乘子$\alpha _i^{\bf{y}}$和$\beta _i^{\bf{y}}$，满足条件

则式(7)的拉格朗日函数为

将拉格朗日函数$L({\boldsymbol{w}},\xi ,\alpha ,\beta )$分别对${\boldsymbol{w}}$和${\xi _i}$求偏导并令其为0可得

将式(11)—式(13)代入式(10)，可以将$L({\boldsymbol{w}},\xi ,$$\alpha ,\beta )$中的w、$\beta$和ξ消去，得到式(7)的对偶问题，如式14(a)—式14(c)所示。

本文模型采用线性核，并基于对偶坐标优化原理^[15]设计模型式(14)的求解算法。由文献[15]可知，对偶坐标优化(Dual Coordinate Descent，DCD)算法每次利用式(15)从训练集中选择一个训练样本k，然后利用式(16)更新其对偶标量$\alpha _k^y$。

解决问题的关键是如何求得式(16)中的$\Delta \alpha _k^{{{\bf{y}}^*}}$。为此，首先将式(16)代入式(14a)，然后将其转化为关于$\Delta \alpha _k^{{{\bf{y}}^*}}$的函数，得到式(17)。

其中，${\rm{c}}$是一个与增量$\Delta \alpha _k^{{{\bf{y}}^ * }}$无关的常量。将式(17)对$\Delta \alpha _k^{{{\bf{y}}^ * }}$求导并令其为0可得

根据约束条件式(14b)可得

当$L({{\boldsymbol{y}}_i},{\boldsymbol{y}}) < m$时，$\Delta \alpha _k^{{{\boldsymbol{y}}^ * }}$的取值范围为

根据约束条件式14(c)可得

当$L({{\boldsymbol{y}}_i},{\boldsymbol{y}}) \ge m$时，$\Delta \alpha _k^{{{\boldsymbol{y}}^ * }}$的取值范围为

利用式(18)—式(21)可以得到$\Delta \alpha _k^{{{\boldsymbol{y}}^*}}$，然后结合式(11)即可得到w的更新公式，如式(22)所示。

在基于结构化SVM的目标跟踪中，随着时间的推移，结构化SVM中的支持向量的数量不断增加。为了保证目标跟踪的效率，需要固定支持向量的数目。为此，当结构化SVM中模式数超出预算时，根据式(23)选择一个支持向量删除，本文提出的代价敏感结构化SVM采用这一策略。

综上所述，本文提出的代价敏感结构化SVM学习算法如算法1所示。

算法1　代价敏感结构化SVM学习算法

输入：t-1时刻代价敏感结构化SVM的参数${{\boldsymbol{w}}_{t - 1}}$和模式集${{\boldsymbol{P}}_{t - 1}}$，t时刻的训练样本$\{ {\boldsymbol{x}}_t^i,{\boldsymbol{y}}_t^i\} _{i = 1}^N$。

输出：t时刻代价敏感结构化SVM的参数${{\boldsymbol{w}}_t}$和模式集${{\boldsymbol{P}}_t}$。

步骤1　${{\boldsymbol{P}}_t} = {{\boldsymbol{P}}_{t - 1}} \cup \{ {\boldsymbol{x}}_t^i,{\boldsymbol{y}}_t^i\} _{i = 1}^N$；

For j=1：n₁

步骤2　计算模式集${{\boldsymbol{P}}_t}$中的模式数n；

步骤3　令$i = n - \left\lfloor {(j - 1) * n/{n_1})} \right\rfloor$；

步骤4　用式(15)，从模式${\boldsymbol{P}}_t^i$中选择样本；

步骤5　用式(16)，更新${\boldsymbol{y}}_i^*$的对偶变量$\alpha _i^{{{\boldsymbol{y}}^ * }}$；

步骤6　用式(22)，更新${{\boldsymbol{w}}_{t - 1}}$；

步骤7　如果模式集${{\boldsymbol{P}}_t}$中的支撑向量数目大于预算数目，则用式(23)更新模式集${{\boldsymbol{P}}_t}$；

步骤8　计算模式集${{\boldsymbol{P}}_t}$中的模式数n；

For p=1：n₂

令$i = n - \left\lfloor {(p - 1) \times n/{n_2})} \right\rfloor$；

步骤9　用式(15)，从模式${\boldsymbol{P}}_t^i$中选择样本${\boldsymbol{y}}_i^*$；

步骤10　用式(16)，更新${\boldsymbol{y}}_i^*$的对偶变量$\alpha _i^{{{\boldsymbol{y}}^ * }}$；

步骤11　用式(22)，更新${{\boldsymbol{w}}_{t - 1}}$；

End For

End For

步骤12　令${{\boldsymbol{w}}_t} = {{\boldsymbol{w}}_{t - 1}}$。

说明：算法1中n₁和n₂是外部循环和内循环的迭代次数，本文分别取5和10。

4.   目标跟踪方法

本文使用网格搜索生成候选样本，搜索区域的大小由跟踪目标的大小自适应确定。样本的大小设定为20×20。在得到代价敏感结构化SVM的超平面w后，利用内积运算计算候选样本的得分，根据最大得分准则式(24)估计目标的状态。

对于目标特征，本文选择目标的Lab颜色和局部秩变换(Local Rank Transformation, LRT)特征，LRT特征的计算方法同文献[16]，这里不再详述。基于上面的分析，本文提出的代价敏感结构化SVM目标跟踪方法描述如下。

方法1　代价敏感结构化SVM目标跟踪方法

输入：序列图像$I=\left\{{I}_{1}, {I}_{2}, \cdots, {I}_{T}\right\}$和目标状态${{\boldsymbol{s}}_1}$，尺度参数Sp={Sp[1], Sp[2], \cdots, Sp[n]}

输出：每一帧的跟踪结果${{\boldsymbol{s}}_i}\left( {i = 1,2, \cdots ,T} \right)$。

步骤1　根据当前目标状态${{\boldsymbol{s}}_1}$，采样N个训练样本${\rm{\{ (}}{\boldsymbol{x}}_1^i,{\boldsymbol{y}}_1^i{\rm{)\} }}_{i = 1}^{\rm{N}}$；

步骤2　初始${{\boldsymbol{w}}_0} = {{{\textit{0}}}}$和${{\boldsymbol{P}}_0} = {{{\textit{0}}}}$；

步骤3　调用算法1初始化t=1时刻DLCS_SSVM的参数${{\boldsymbol{w}}_1}$和模式${{\boldsymbol{P}}_1}$；

For (t=2：T)，

For (k=1: length(Sp))

I_t,k=Scale(I_t,Sp[k])；

步骤4　利用滑动窗口在I_t,k上的搜索区域中采样测试样本${\rm{\{ (}}{\boldsymbol{x}}_{t,k}^i,{\boldsymbol{y}}_{t,k}^i{\rm{)\} }}_{i = 1}^M$, ${{\boldsymbol{X}}_{{{t,k}}}}{\rm{ = }}[{\boldsymbol{x}}_{t{{,k}}}^i]_{i = 1}^M, {{\boldsymbol{Y}}_{{{t,k}}}}{\rm{ = }} [{\boldsymbol{y}}_{t{{,k}}}^i]_{i = 1}^M$；

步骤5　利用最大化得分准则估计目标当前状态：${\boldsymbol{s}}_{t,k}^{\rm{m}} = \mathop {\arg \max }\limits_{{\boldsymbol{y}} \in {{\boldsymbol{Y}}_{t,k}}} ({{\boldsymbol{w}}_t}^{\rm{T}} {{\boldsymbol{X}}_{t,k}})$；

End For

步骤6　根据当前目标状态${{\boldsymbol{s}}_t}$，采样N个训练样本${\rm{\{ (}}{\boldsymbol{x}}_t^i,{\boldsymbol{y}}_t^i{\rm{)\} }}_{i = 1}^{\rm{N}}$；

步骤7　调用算法1更新DLCS_SSVM的${{\boldsymbol{w}}_t}$；

End For

方法1中I_t,k=Scale(I_t, Sp[k])的功能是利用尺度参数Sp[k]对图像I_t进行缩放，结果赋予I_t,k。对于单尺度目标跟踪，尺度参数Sp设定为{1}，即可完成单尺度目标跟踪，称为单尺度代价敏感结构化SVM目标跟踪方法(简称DLCS_SSVM)。对于多尺度目标跟踪，尺度参数Sp={Sp[1], Sp[2], ···, Sp[n]}，本文Sp={1, 0.995, 1.005}，即在3种不同尺度图像上分别跟踪目标，以最大得分作为跟踪结果，即可完成多尺度目标跟踪，称为多尺度代价敏感结构化SVM目标跟踪(Scale-DLCS_SSVM)。

5.   实验

5.1   实验环境、数据集和参数设置

在SYS-7048GR-TR台式机(CPU型号为Intel Xeon(R) ES-2630v4@2.20 GHz×20，内存为64 GB，GPU为RTX2080Ti 11 GB)上使用Matlab和OpenCV实现了本文提出的跟踪方法，其中Matlab版本为R2017a, OpenCV版本为2.4.8。一方面利用OTB100数据集^[12]对提出的目标跟踪方法进行实验验证。评价指标为OPE, TRE和SRE^[12]。另一方面利用VOT2019数据集^[13]对提出的目标跟踪方法进行实验验证。评价指标为EAO, Accuracy, Robustness^[13]。本文提出的目标跟踪方法中有一些需要设置参数，实验中这些参数固定不变。惩罚系数C的值为100，支持向量的预算设为100，C⁺的值设为2，κ的值设为0.67，正样本与负样本的阈值m设为0.5。多尺度估计参数设置为Scale={1, 0.995, 1.005}。

5.2   实验结果及分析

5.2.1   与其它基于结构化SVM跟踪器在OTB100数据集上的比较

表1给出了本文方法DLCS_SSVM, Scale-DLCS_SSVM, DLSSVM^[8], Scale-DLSSVM^[8], Struck^[1]和LMCF^[9]等6种基于结构化SVM跟踪器在OTB100数据集上的OPE性能指标比较结果。从表1可以看出，在精度和成功率两项指标上，本文提出的方法Scale-DLCS_SSVM均明显优于其它跟踪器。在跟踪速度上，本文选择一个长视频liquor(1741帧)^[12]进行评估。由表1中的比较结果可以看出：本文方法与DLSSVM^[8]方法相比不仅在性能上有明显提升，而且对目标跟踪速度几乎没有影响。

表  1  6种基于结构化SVM的跟踪器在OTB100数据集上的OPE性能与速度指标

跟踪方法	精度(pixels)	成功率(AUC)	速度(fps)
Scale-DLCS_SSVM	0.837	0.648	12.18
DLCS_SSVM	0.805	0.603	25.32
Scale-DLSSVM[8]	0.803	0.561	11.47
DLSSVM[8]	0.765	0.540	23.16
Struck[1]	0.635	0.459	7.52
LMCF[9]	0.786	0.578	78.23

下载: 导出CSV 

| 显示表格

5.2.2   与其它高性能跟踪器跟踪速度比较

由表2与其他高性能跟踪器跟踪速度比较可知，相较于深度学习目标跟踪方法，如DeepLMCF^[9]和DeepSRDCF^[17]，本文方法速度明显更快。相较于相关滤波目标跟踪方法，如TADT^[18]，本文单尺度方法速度与其速度相当，能够达到实时的跟踪效果。

表  2  5种跟踪方法在OTB100数据集上的速度指标(fps)

跟踪方法	Scale-DLCS_SSVM	DLCS_SSVM	DeepLMCF[9]	DeepSRDCF[17]	TADT[18]
速度	12.18	25.32	7.45	1.56	27.89

下载: 导出CSV 

| 显示表格

5.2.3   与其它高性能跟踪器在OTB100数据集上的比较

在OTB100数据集上，将本文提出的目标跟踪方法与4种优秀的目标跟踪方法进行比较。4种方法分别是基于深度学习的DeepSRDCF^[17]、基于相关滤波的Staple^[19]、基于结构化SVM的多尺度跟踪Scale-DLSSVM^[8]及基于结构化SVM与相关滤波的LMCF^[9]。图2为6种跟踪器在OTB100数据集上取效果前5名的OPE, TRE和SRE性能指标曲线。从图2中的结果可以看出，本文提出的Scale-DLCS_SSVM与DLCS_SSVM跟踪器在准确度和成功率两个指标上相比Scale-DLSSVM跟踪方法都有明显的提高。且在OPE评价指标上Scale-DLCS_SSVM相比DeepSRDCF^[17]在成功率上高1.3%，在TRE评价指标上Scale-DLCS_SSVM相比DeepSRDCF^[17]在成功率上高1.5%，在SRE评价指标上Scale-DLCS_SSVM相比DeepSRDCF^[17]在成功率上高1.0%。

图  2  6种高性能跟踪器在OTB100数据集上取效果前5名的OPE, TRE和SRE性能指标曲线

下载: 全尺寸图片 幻灯片

5.2.4   与其它高性能跟踪器在VOT2019数据集上的比较

如表3所示，本文选取近两年高性能的深度学习与相关滤波跟踪方法在VOT2019数据集上进行比较。由表3可知，本文多尺度方法在单个指标上略低于SiamMask，但是相较于其他高性能方法来说在各个性能上有着优势。

表  3  本文多尺度方法与近年来4种高性能跟踪方法在VOT2019数据集上实验结果

	本文	SiamMask[20]	GradNet[21]	TADT[18]	DeepSRDCF[17]
EAO↑	0.217	0.289	0.213	0.207	0.198
Accuracy↑	0.538	0.596	0.531	0.516	0.512
Robustness↓	0.559	0.461	0.538	0.567	0.572

下载: 导出CSV 

| 显示表格

从上述所有实验结果可以看出：本文提出的目标跟踪方法达到了预期的跟踪效果，其跟踪性能优于现有基于结构化SVM的目标跟踪方法；与相关滤波目标跟踪方法相比，本文方法跟踪精度较高；与深度学习目标跟踪方法相比，本文方法具有速度优势。

6.   结束语

本文分析了基于结构化SVM的目标跟踪在进行训练时存在正样本和负样本不平衡的问题。针对该问题，基于代价敏感SVM和结构化SVM提出一种代价敏感结构化SVM模型，并利用对偶坐标下降优化设计了代价敏感结构化SVM算法。最后，利用提出的代价敏感结构化SVM实现了一种多尺度目标跟踪方法。利用OTB100数据集和VOT2019数据集分别对提出的目标跟踪方法进行了实验验证和分析。实验结果表明，与相关滤波目标跟踪中的一些优秀方法相比，本文方法跟踪精度较高，与深度目标跟踪中的一些优秀方法相比，本文方法具有速度优势。在目标跟踪中，由于跟踪误差会引起模型漂移，进而导致跟踪失败，如何利用结构化SVM解决这一问题是进一步研究的方向。