Optimization Algorithm of Dual-port Memory Mapping on FPGA

Yu XU; Yu LIN; Haigang YANG

doi:10.11999/JEIT190077

Volume 42 Issue 10

Oct. 2020

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2020 > 42(10): 2549-2556

Guanglin YUAN, Ziwen SUN, Xiaoyan QIN, Liang XIA, Hong ZHU. Object Tracking Based on Cost Sensitive Structured SVM[J]. Journal of Electronics & Information Technology, 2021, 43(11): 3335-3341. doi: 10.11999/JEIT200708

Citation:

Yu XU, Yu LIN, Haigang YANG. Optimization Algorithm of Dual-port Memory Mapping on FPGA[J]. Journal of Electronics & Information Technology, 2020, 42(10): 2549-2556. doi: 10.11999/JEIT190077

Citation:

Yu XU, Yu LIN, Haigang YANG. Optimization Algorithm of Dual-port Memory Mapping on FPGA[J]. Journal of Electronics & Information Technology, 2020, 42(10): 2549-2556. doi: 10.11999/JEIT190077

PDF( 1439 KB)

Optimization Algorithm of Dual-port Memory Mapping on FPGA

doi: 10.11999/JEIT190077

Yu XU^{1, 2},
Yu LIN³,
Haigang YANG^{1, 2
,
,}

1.
Institute of Electrics, Chinese Academy of Sciences, Beijing 100190, China
2.
University of Chinese Academy of Sciences, Beijing 100049, China
3.
Xilinx Incorporated, Beijing 100101, China

Funds: The National Natural Science Foundation of China (61474120, 61404140, 61704173)

Received Date: 2019-01-28
Rev Recd Date: 2020-01-20

Available Online: 2020-07-20

Publish Date: 2020-10-13

Abstract

Abstract

FPGA memory mapping algorithm utilizes distributed storage resources on chip and cooperates with some auxiliary circuits to realize the different needs of users in designing logical storage functions. Previous studies on dual-port memory mapping algorithm are relatively few. There is still much space for improvement in the mapping results by mature commercial EDA tools. An optimization algorithm of dual-port memory mapping is proposed for area, delay and power consumption, and a specific configuration scheme is given. Experiments show that when facing simple storage requirements, the mapping results are consistent with those of commercial tools; when facing complex storage requirements, the mapping results of area optimization and power optimization are improved by at least 50% compared with commercial tools Vivado.
- FPGA,
- Dual-port memory mapping,
- Delay optimization,
- Area optimization,
- Power optimization

FullText(HTML)

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]提出的代价敏感支持向量机描述为

$\begin{split} & {\mathop {{\rm{argmin}}}\limits_{\boldsymbol{w},b,{\xi _i}} \frac{1}{2}{{\left\| \boldsymbol{w} \right\|}^2} + C\left( {{C_1}\sum\limits_{\left\{ {i|{y_i} = 1} \right\}}^{} {{\xi _i}} + \frac{1}{\kappa }\sum\limits_{\left\{ {i|{y_i} = - 1} \right\}}^{} {{\xi _i}} } \right)}\\ & {\;\;\;\;\;\;\forall {\xi _i} \ge 0}\\ & {{\rm{s}}.{\rm{t}}.\;\;\;({\boldsymbol{w}^{\rm{T}}}{\boldsymbol{x}_i}{\rm{ + }}b) \ge {\rm{1 - }}{\xi _i}{\rm{;}}{y_i}{\rm{ = + 1}}}\\ & {\;\;\;\;\;\;({\boldsymbol{w}^{\rm{T}}}{\boldsymbol{x}_i} + b) \le - \kappa + {\xi _i}{\rm{;}}{y_i} = - 1}\\[-10pt] \end{split}$

(1)

其中

$\kappa = \frac{1}{{2{C_{ - 1}} - 1}},\;0 < \kappa \le 1 \le \frac{1}{\kappa } \le {C_1}$

(2)

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的分类器。

${{\boldsymbol{y}}^ * } = \mathop {\arg \max }\limits_{{\boldsymbol{y}} \in {\boldsymbol{Y}}} f\left( {{\boldsymbol{x}},{\boldsymbol{y}},{\boldsymbol{w}}} \right)$

(3)

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

$\begin{split} & \mathop {\min }\limits_{\boldsymbol{w}} \frac{1}{2}{\left\| {\boldsymbol{w}} \right\|^2} + C\sum\limits_{i = 1} {{\xi _i}} \\ & {{\rm{s}}{\rm{.t}}{\rm{.}}} \ \ \;\;\forall i,{\xi _i} \ge 0 \\ & \;\; \quad\quad \forall i,\forall {\boldsymbol{y}} \ne {{\boldsymbol{y}}_i}:\left\langle {{\boldsymbol{w}},{{\boldsymbol{\varPsi }}_i}({\boldsymbol{y}})} \right\rangle \ge L({{\boldsymbol{y}}_i},{\boldsymbol{y}}) - {\xi _i} \end{split}$

(4)

其中， ${{\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)所示。

$L({{\boldsymbol{y}}_i},{\boldsymbol{y}}) = 1 - s({{\boldsymbol{y}}_i},{\boldsymbol{y}})$

(5)

其中

$s\left( {{{\boldsymbol{y}}_i},{\boldsymbol{y}}} \right) = \frac{{{{\boldsymbol{y}}_i} \cap {\boldsymbol{y}}}}{{{{\boldsymbol{y}}_i} \cup {\boldsymbol{y}}}}$

(6)

3. 代价敏感结构化SVM

3.1 代价敏感结构化SVM模型

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

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

下载: 全尺寸图片幻灯片

$\begin{split} &\mathop {\min }\limits_{\boldsymbol{w}} \frac{1}{2}{\left\| {\boldsymbol{w}} \right\|^2} + C\left( {{C^ + }\sum\limits_{{\boldsymbol{y}} \ne {{\boldsymbol{y}}_i},\atop L({{\boldsymbol{y}}_i},{\boldsymbol{y}}) < m} {{\xi _i}} + \frac{1}{\kappa }\sum\limits_{{\boldsymbol{y}} \ne {{\boldsymbol{y}}_i},\atop L({{\boldsymbol{y}}_i},{\boldsymbol{y}}) \ge m} {{\xi _i}} } \right)\\ &\quad\;\;\;\; \forall i,\;{\xi _i} \ge 0\\ &{{\rm{s}}{\rm{.t}}{\rm{.}}}\;\;\;\forall i,\forall {\boldsymbol{y}} \ne {{\boldsymbol{y}}_i},\;L({{\boldsymbol{y}}_i},{\boldsymbol{y}}) < m\\ &\;\;\;\; \quad\left\langle {{\boldsymbol{w}},{{\boldsymbol{\varPsi }}_i}({\boldsymbol{y}})} \right\rangle \ge L({{\boldsymbol{y}}_i},{\boldsymbol{y}}) - {\xi _i}\\ &\;\;\;\; \quad \forall i,\forall {\boldsymbol{y}} \ne {{\boldsymbol{y}}_i},\;L({{\boldsymbol{y}}_i},{\boldsymbol{y}}) \ge m\\ &\;\;\;\; \quad\left\langle {{\boldsymbol{w}},{{\boldsymbol{\varPsi }}_i}({\boldsymbol{y}})} \right\rangle \ge \kappa L({{\boldsymbol{y}}_i},{\boldsymbol{y}}) - {\xi _i}\\[-10pt] \end{split}$

(7)

其中，

$\kappa = \frac{1}{{2{C^ - } - 1}},\;0 < \kappa \le 1 \le \frac{1}{\kappa } \le {C^ + }$

(8)

${{\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}}$ ，满足条件

$\forall i,\forall {\bf{y}} \ne {{\bf{y}}_i}:\alpha _i^{\bf{y}} \ge 0,\;\beta _i^{\bf{y}} \ge 0$

(9)

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

$\begin{split} & L({\boldsymbol{w}},\xi ,\alpha ,\beta ) = \frac{1}{2}{\left\| {\boldsymbol{w}} \right\|^2} \\ & \quad + {\rm{ }}C\left( {{C^ + }\sum\limits_{i,{\boldsymbol{y}} \ne {{\boldsymbol{y}}_i}\atop L({{\boldsymbol{y}}_i},{\boldsymbol{y}}) < m}^{} {{\xi _i}} + \frac{1}{\kappa }\sum\limits_{i,{\boldsymbol{y}} \ne {{\boldsymbol{y}}_i}\atop L({{\boldsymbol{y}}_i},{\boldsymbol{y}}) \ge m}^{} {{\xi _i}} } \right) \\ & \quad - \sum\limits_{i,{\boldsymbol{y}} \ne {{\boldsymbol{y}}_i}\atop L({{\boldsymbol{y}}_i},{\boldsymbol{y}}) < m}^{} {\alpha _i^{\boldsymbol{y}}\left( {\left\langle {{\boldsymbol{w}},{{\boldsymbol{\varPsi }}_i}({\boldsymbol{y}})} \right\rangle + \xi _i^{} - L({{\boldsymbol{y}}_i},{\boldsymbol{y}})} \right)} \\ & \quad-\sum\limits_{i,{\boldsymbol{y}} \ne {{\boldsymbol{y}}_i}\atop L({{\boldsymbol{y}}_i},{\boldsymbol{y}}) \ge m}^{} {\alpha _i^{\boldsymbol{y}}\left( {\left\langle {{\boldsymbol{w}},{{\boldsymbol{\varPsi }}_i}({\boldsymbol{y}})} \right\rangle + {\xi _i} - \kappa L({{\boldsymbol{y}}_i},{\boldsymbol{y}})} \right)} \\ & \quad - {\rm{ }}\sum\limits_{i,{\boldsymbol{y}} \ne {{\boldsymbol{y}}_i}}^{} {\beta _i^{\boldsymbol{y}}{\xi _i}} \end{split}$

(10)

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

${\boldsymbol{w}} = \sum\limits_{i,{\boldsymbol{y}} \ne {{\boldsymbol{y}}_i}}^{} {\alpha _i^{\boldsymbol{y}}{{\boldsymbol{\varPsi }}_i}({\boldsymbol{y}})}$

(11)

$\forall i,{\boldsymbol{y}} \ne {{\boldsymbol{y}}_i},\;L({{\boldsymbol{y}}_i},{\boldsymbol{y}}) < m,\;C{C^ + } - \alpha _i^{\boldsymbol{y}} - \beta _i^{\boldsymbol{y}}{\rm{ = }}0$

(12)

$\forall i,{\boldsymbol{y}} \ne {{\boldsymbol{y}}_i},\;L({{\boldsymbol{y}}_i},{\boldsymbol{y}}) \ge m,\;\frac{C}{\kappa } - \alpha _i^{\boldsymbol{y}} - \beta _i^{\boldsymbol{y}}{\rm{ = }}0$

(13)

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

$\begin{split} \mathop {{\rm{min}}}\limits_{\alpha \ge 0} L(\alpha ) =\,& \frac{1}{2}{\left\| {\sum\limits_{i,{\boldsymbol{y}} \ne {{\boldsymbol{y}}_i}}^{} {\alpha _i^{\boldsymbol{y}}{{\boldsymbol{\varPsi }}_i}({\boldsymbol{y}})} } \right\|^2} - \sum\limits_{i,{\boldsymbol{y}} \ne {{\boldsymbol{y}}_i},\atop L({{\boldsymbol{y}}_i},{\boldsymbol{y}}) < m}^{} {\alpha _i^{\boldsymbol{y}}L({{\boldsymbol{y}}_i},{\boldsymbol{y}})} \\ & - \kappa \sum\limits_{i,{\boldsymbol{y}} \ne {{\boldsymbol{y}}_i},\atop L({{\boldsymbol{y}}_i},{\boldsymbol{y}}) \ge m}^{} {\alpha _i^{\boldsymbol{y}}L({{\boldsymbol{y}}_i},{\boldsymbol{y}})} \end{split} \tag{14a}$

${\rm{s}}{\rm{.t}}{\rm{.}}\;\forall i,{\boldsymbol{y}} \ne {{\boldsymbol{y}}_i},\;L({{\boldsymbol{y}}_i},{\boldsymbol{y}}) < m,\;\alpha _i^{\boldsymbol{y}} \ge 0,\sum\limits_{\boldsymbol{y}} {\alpha _i^{\boldsymbol{y}}} \le C{C^ + } \tag{14b}$

$\forall i,{\boldsymbol{y}} \ne {{\boldsymbol{y}}_i},\;L({{\boldsymbol{y}}_i},{\boldsymbol{y}}) \ge m,\;\alpha _i^{\boldsymbol{y}} \ge 0,\;\sum\limits_{\boldsymbol{y}} {\alpha _i^{\boldsymbol{y}}} \le \frac{C}{\kappa } \tag{14c}$

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

${\boldsymbol{y}}_k^ * = \mathop {\arg \max }\limits_{{\boldsymbol{y}} \in {{\boldsymbol{Y}}_k}} L({\boldsymbol{y}},{{\boldsymbol{y}}_k}) - {{\boldsymbol{w}}^{\rm T}}{{\boldsymbol{\varPsi }}_k}\left( {\boldsymbol{y}} \right)$

(15)

$\qquad \alpha _k^{{{\boldsymbol{y}}^ * }({\rm{new}})} = \alpha _k^{{{\boldsymbol{y}}^ * }({\rm{old}})} + \Delta \alpha _k^{{{\boldsymbol{y}}^ * }}$

(16)

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

$\begin{split} L(\Delta \alpha _k^{{{\boldsymbol{y}}^ * }}) = \,& \frac{1}{2}{\left( {\alpha _k^{{{\boldsymbol{y}}^ * }({\rm{old}})} + \Delta \alpha _k^{{{\boldsymbol{y}}^ * }}} \right)^2}{\left\| {{{\boldsymbol{\varPsi }}_k}({{\boldsymbol{y}}^ * })} \right\|^2} \\ & + \Delta \alpha _k^{{{\boldsymbol{y}}^ * }}\sum\limits_{i \ne k\atop {{\boldsymbol{y}} \ne {{\boldsymbol{y}}_i}\atop {\boldsymbol{y}} \ne {{\boldsymbol{y}}^ * }}} {\alpha _i^{\boldsymbol{y}}{{\boldsymbol{\varPsi }}_i}({\boldsymbol{y}}){{\boldsymbol{\varPsi }}_k}({\boldsymbol{y}})} \\ &- \Delta \alpha _k^{{{\boldsymbol{y}}^ * }}L({{\boldsymbol{y}}_k},{{\boldsymbol{y}}^ * })\left| {_{L({{\boldsymbol{y}}_k},{{\boldsymbol{y}}_i}) < m}} \right. \\ & - \kappa \Delta \alpha _k^{{{\boldsymbol{y}}^ * }}L({{\boldsymbol{y}}_k},{{\boldsymbol{y}}^ * })\left| {_{L({{\boldsymbol{y}}_k},{{\boldsymbol{y}}_i}) \ge m}} \right. + {\rm{c}} \end{split}$

(17)

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

$\begin{split} & \forall i,{\boldsymbol{y}} \ne {{\boldsymbol{y}}_i},\;L({{\boldsymbol{y}}_i},{\boldsymbol{y}}) < m,\\ & \Delta \alpha _k^{{{\boldsymbol{y}}^ * }} = \frac{{L({{\boldsymbol{y}}_k},{{\boldsymbol{y}}^ * }) - {{\boldsymbol{w}}^{\rm{T}}}{{\boldsymbol{\varPsi }}_k}({{\boldsymbol{y}}^ * })}}{{{{\left\| {{{\boldsymbol{\varPsi }}_k}({{\boldsymbol{y}}^ * })} \right\|}^2}}} \end{split}$

(18)

$\begin{split} & \forall i,{\boldsymbol{y}} \ne {{\boldsymbol{y}}_i},\;L({{\boldsymbol{y}}_i},{\boldsymbol{y}}) \ge m,\\ & \Delta \alpha _k^{{{\boldsymbol{y}}^ * }} = \frac{{\kappa L({{\boldsymbol{y}}_k},{{\boldsymbol{y}}^ * }) - {{\boldsymbol{w}}^{\rm{T}}}{{\boldsymbol{\varPsi }}_k}({{\boldsymbol{y}}^ * })}}{{{{\left\| {{{\boldsymbol{\varPsi }}_k}({{\boldsymbol{y}}^ * })} \right\|}^2}}} \end{split}$

(19)

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

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

$\left[ - \alpha _k^{{{\boldsymbol{y}}^ * }({\rm{old}})},C{C^ + } - \sum\limits_{\boldsymbol{y}} {\alpha _k^{\boldsymbol{y}}} \right]$

(20)

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

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

$\left[ - \alpha _k^{{{\boldsymbol{y}}^ * }({\rm{old}})},\frac{C}{\kappa } - \sum\limits_{\boldsymbol{y}} {\alpha _k^{\boldsymbol{y}}} \right]$

(21)

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

${{\boldsymbol{w}}^{({\rm{new}})}} = {{\boldsymbol{w}}^{({\rm{old}})}} + \Delta \alpha _k^{{{\boldsymbol{y}}^ * }}{{\boldsymbol{\varPsi }}_k}\left( {{{\boldsymbol{y}}^ * }} \right)$

(22)

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

${\alpha ^ * } = \mathop {\arg \min }\limits_{\alpha _i^{\boldsymbol{y}} \in \alpha } {\left\| {\alpha _i^{\boldsymbol{y}}{{\boldsymbol{\varPsi }}_i}\left( {{{\boldsymbol{x}}_i},{\boldsymbol{y}}} \right)} \right\|^2}$

(23)

综上所述，本文提出的代价敏感结构化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

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

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

4. 目标跟踪方法

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

${{\boldsymbol{y}}^ * } = \mathop {\arg \max }\limits_{{\boldsymbol{y}} \in {\boldsymbol{Y}}} {{\boldsymbol{w}}^{\rm{T}}}{{\boldsymbol{\varPsi }}_t}\left( {\boldsymbol{y}} \right)$

(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

${{\boldsymbol{s}}_{\rm{t}}} = \max ({\boldsymbol{s}}_{t,k}^{\rm{m}} ),\;m \in {\rm{S}}p$

步骤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解决这一问题是进一步研究的方向。

References(15)

References

TRIMBERGER S M. Three ages of FPGAs: A retrospective on the first thirty years of FPGA technology[J]. Proceedings of the IEEE, 2015, 103(3): 318–331. doi: 10.1109/JPROC.2015.2392104

KUON I and ROSE J. Measuring the gap between FPGAs and ASICs[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2007, 26(2): 203–215. doi: 10.1109/TCAD.2006.884574

WILTON S J E. Architectures and algorithms for Field-Programmable Gate Arrays with embedded memory[D]. [Ph. D. dissertation], University of Toronto, 1997.

TESSIER R, BETZ V, NETO D, et al. Power-efficient RAM mapping algorithms for FPGA embedded memory blocks[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2007, 26(2): 278–290. doi: 10.1109/TCAD.2006.887924

HSU T Y and WANG Tingchi. A generalized network flow based algorithm for power-aware FPGA memory mapping[C]. The 45th ACM/IEEE Design Automation Conference, Anaheim, USA, 2008: 30–33.

DU Fangqing, LIN C Y, CUI Xiuhai, et al. Timing-constrained minimum area/power FPGA memory mapping[C]. The 23rd International Conference on Field programmable Logic and Applications, Porto, Portugal, 2013: 1–4.

HO W K C and WILTON S J E. Logical-to-physical memory mapping for FPGAs with dual-port embedded arrays[C]. The 9th International Workshop on Field Programmable Logic and Applications, Glasgow, UK, 1999: 111–123.

CONG J and YAN K. Synthesis for FPGAs with embedded memory blocks[C]. 2000 ACM/SIGDA Eighth International Symposium on Field Programmable Gate Arrays, Monterey, USA, 2000: 75–82.

MA Yufei, CAO Yu, VRUDHULA S, et al. An automatic RTL compiler for high-throughput FPGA implementation of diverse deep convolutional neural networks[C]. The 27th International Conference on Field Programmable Logic and Applications (FPL), Ghent, Belgium, 2017: 1–8.

GUAN Yijin, LIANG Hao, XU Ningyi, et al. FP-DNN: An automated framework for mapping deep neural networks onto FPGAs with RTL-HLS hybrid templates[C]. The 25th IEEE Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), Napa, USA, 2017: 152–159.

LIANG Shuang, YIN Shouyi, LIU Leibo, et al. FP-BNN: Binarized neural network on FPGA[J]. Neurocomputing, 2018, 275: 1072–1086. doi: 10.1016/j.neucom.2017.09.046

GUO Kaiyuan, SUI Lingzhi, QIU Jiantao, et al. Angel-eye: A complete design flow for mapping CNN onto embedded FPGA[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018, 37(1): 35–47. doi: 10.1109/TCAD.2017.2705069

MA Yufei, SUDA N, CAO Yu, et al. ALAMO: FPGA acceleration of deep learning algorithms with a modularized RTL compiler[J]. Integration, 2018, 62: 14–23. doi: 10.1016/j.vlsi.2017.12.009

Xilinx. Virtex-4 FPGA user guide[EB/OL]. https://china.xilinx.com/support/documentation/user_guides/ug070.pdf, 2008.

Xilinx. LogiCORE IP product guide block memory generator v8.4[EB/OL]. https://china.xilinx.com/support/documentation/ip_documentation/blk_mem_gen/v8_4/pg058-blk-mem-gen.pdf, 2019.

Relative Articles

Supplements(0)

Cited By

Cited by

Periodical cited type(4)

1.	林自强，李明，刘张榕. 基于改进的SECOND网络与MobileNet V2网络的视频监控与追踪技术实现. 测控技术. 2024(05): 78-84 .
2.	李豪. Deep Snake协助相关滤波目标跟踪. 信息工程大学学报. 2024(05): 538-544 .
3.	张鑫，周伟，徐志宇. 基于代价敏感学习的配电网故障线路分类算法. 实验室研究与探索. 2024(11): 46-51+81 .
4.	吴崇明，王晓丹，赵振冲. 一种新的代价敏感SVDD二类分类方法. 计算机科学. 2023(S1): 147-151 .

Other cited types(7)

Proportional views

Proportional views

通讯作者: 陈斌, bchen63@163.com

1.
沈阳化工大学材料科学与工程学院沈阳 110142

Figures(4) / Tables(6)

Get Citation

PDF

XML

Article Metrics

Article views (1959) PDF downloads(115)

Optimization Algorithm of Dual-port Memory Mapping on FPGA

doi: 10.11999/JEIT190077

Abstract

1. 引言

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

2.1 代价敏感支持向量机

2.2 结构化支持向量机

3. 代价敏感结构化SVM

3.1 代价敏感结构化SVM模型

3.2 代价敏感结构化SVM算法

4. 目标跟踪方法

5. 实验

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

5.2 实验结果及分析

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

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

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

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

6. 结束语

References

Cited by

Periodical cited type(4)

Other cited types(7)

Proportional views

Catalog

通讯作者: 陈斌, bchen63@163.com

Article Metrics

Proportional views

Related

Optimization Algorithm of Dual-port Memory Mapping on FPGA

doi: 10.11999/JEIT190077

Abstract

1. 引言

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

2.1 代价敏感支持向量机

2.2 结构化支持向量机

3. 代价敏感结构化SVM

3.1 代价敏感结构化SVM模型

3.2 代价敏感结构化SVM算法

4. 目标跟踪方法

5. 实验

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

5.2 实验结果及分析

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

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

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

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

6. 结束语

References

Cited by

Periodical cited type(4)

Other cited types(7)

Proportional views

Catalog

通讯作者: 陈斌, bchen63@163.com

Article Metrics

Proportional views

Related

Export File

Citation

Format

Content