1 引言

视频目标跟踪是指对图像序列中机动目标进行检测、提取、识别和跟踪, 以获得机动目标位置、速度、加速度、运动轨迹等运动参数, 从而对机动目标进行进一步处理与分析的过程^[1]. 随着计算机运算能力和存储能力的迅速发展及大数据分析需求的逐渐增大, 视频跟踪技术在交通控制^[2]、视频检索^[3]、人机交互^[4]等方面有了广泛应用. 早期的目标跟踪算法主要根据目标建模或对目标特征进行跟踪, 主要的方法有基于目标模型建模方法与基于搜索的方法^[1]. 特征匹配法是常用的基于目标模型建模方法, 首先提取目标特征, 然后在后续帧中找到最相似的特征进行目标定位; 均值漂移(mean-shift)算法^[5]是常用的基于搜索的方法, 该方法利用图像特征构造概率密度函数, 由梯度方向搜索局部最大值作为目标位置. 由于在新近的较有挑战的数据集例如VOT2018或者大规模数据集TrackingNet上, 传统跟踪算法达不到实际要求, 而深度学习因为其强大的特征提取能力以及端对端的训练模式慢慢受到了广泛关注. 近年来越来越多基于深度学习的跟踪方法被相关学者提出, Chao等^[6]将深度学习网络及自适用相关滤波器结合, 提出了ECO (efficient convolution operators for tracking)算法, 该算法在速度和精度上都有较好的表现. Wang等^[7]使用Transformer^[8]深度学习跟踪器将不同时刻视频帧桥连起来, 传递了丰富的时序信息, 该算法在最新数据集上有很高的速度与精度.

在对视频中目标跟踪过程中不可避免会存在目标快速移动问题, 即对视频序列中机动目标进行跟踪时, 如果跟踪目标在前后两视频帧间位移超过20个像素点, 则被认为是快速移动^[9]. 此时目标可能超出了搜索范围或移动到了搜索范围边界, 导致丢失目标的情况, 进而跟踪失败. 目标位置预测是解决机动目标快速移动问题的首要难点, 虽然卡尔曼滤波算法可以快速预测目标位置, 但是不能很好地解决机动目标运动过程中存在的非线性情况, 而粒子滤波算法具有解决非线性问题的特性, 对非线性运动过程有较好的预测效果. Nummiaro等^[10]提出了基于颜色特征的粒子滤波跟踪(particle filter, PF)算法. PF首先在目标区域提取颜色特征, 然后散播粒子, 计算每个粒子的权重, 最后根据粒子位置及权重预测目标位置. PF提取目标区域颜色特征, 得到丰富的特征信息, 可以有效地对非刚性和快速移动目标进行跟踪, 而且在遮挡以及复杂环境情况下也有较好的鲁棒性. 然后对目标位置进行修正, 为了正确跟踪目标, 修正算法需要有较高的速率及准确率, 深度学习方法准确率高但运行时间过长. Bolme等^[11]设计了MOSSE (minimum output of squared error )滤波器, 将计算由时域转换到频域, 提供了运算速度, 对信号相关性的求解保证了算法精度. MOSSE虽然运算速度快, 但不能直接对快速移动的机动目标进行跟踪. Henriques等^[12]在MOSSE基础上引入循环矩阵及核函数, 提出CSK (circulant structure of tracking-by-detection with kernels)算法. 精度上相对于MOSSE有了很大提升, 但CSK特征选取比较单一, 而且对快速移动情况没有处理, 很难直接跟踪快速移动的机动目标. Henriques等^[13]在CSK的基础上改变灰度特征提取为FHOG特征提取, 同时加入核方法, 提出了KCF (kernel correlation filter)及DCF (dual correlation filter)算法, KCF对应非线性核, DCF对应线性核. Li等^[14]在KCF的基础上将单一特征选择扩展为多个特征选择, 并添加了尺度池, 提出了SAMF (scale adaptive with multiple features tracker)算法. SAMF算法虽然精度相对于KCF有些许提升但是速度比较慢, 所以这里选择KCF作为修正算法. 最后针对机动目标在视频中由于快速移动问题导致的形变、模糊问题, 融入零截距以及平均峰值相关能量. 实验结果表明, 新方法在公开数据集OTB100与UA-DETRAC上都有较高的识别率.

2 核相关滤波

Danelljan等^[15]将相关滤波器的求解转换为岭回归问题进行推导运算, 利用循环矩阵的特性将问题从时域变换到频域进行快速计算, 为了解决高维运算问题引入了核方法. KCF可以分为滤波器模型建立、目标搜索、模板更新3部分.

(1) 滤波器模型建立. 岭回归问题的目标函数为:

$ f({\mathbf{z}}) = {{\mathbf{w}}^{\text{T}}}{\mathbf{z}} $

(1)

需要合适的目标函数使如下残差函数最小:

$ \mathop {\min }\limits_{\mathbf{w}} \sum\limits_i {\left( {f\left( {{{\mathbf{a}}_i}} \right) - {b_i}} \right)} + \lambda {\left\| {\mathbf{w}} \right\|^2} $

(2)

其中, $ {{\mathbf{a}}_i} $ 表示样本向量, $ {b_i} $ 为其对应样本标签, $ \lambda $ 为防止过拟合归一化参数, $\left\| {\mathbf{w}} \right\|$ 表示 ${\mathbf{w}}$ 的范数. 对式(2)求闭式解得:

$ {\mathbf{w}} = {({{\mathbf{A}}^{\text{H}}}{\mathbf{A}} + \lambda {\mathbf{I}})^{ - 1}}{{\mathbf{A}}^{\text{H}}}{\mathbf{b}} $

(3)

其中, A表示样本向量 $ {{\mathbf{a}}_i} $ 循环移位得到的循环矩阵, A^H为A的共轭转置, I表示单位矩阵, b中每一个元素为一个样本标签 ${b_i}$ .

由于循环矩阵可以通过对角矩阵( ${\text{diag}}$ )进行离散傅里叶变换(DFT)得到, 并且与基础向量 ${\mathbf{a}}$ 无关. 通过式(4)表达此性质:

$ {\mathbf{A}} = {\mathbf{F}}\;{\text{diag}}({\mathbf{\hat a}})\;{{\mathbf{F}}^{\text{H}}} $

(4)

式中, F表示与基础向量a无关的常数矩阵, ${\mathbf{\hat a}}$ 表示a的傅里叶变换, 通过式(4)将式(3)转换到傅里叶域:

$ {\mathbf{\hat w}} = {{{{{\mathbf{\hat a}}}^ * } \otimes {\mathbf{\hat b}}} \mathord{\left/ {\vphantom {{{{{\mathbf{\hat a}}}^ * } \otimes {\mathbf{\hat b}}} {{{{\mathbf{\hat a}}}^ * } \otimes {\mathbf{\hat a}} + \lambda {\mathbf{I}}}}} \right. } {{{{\mathbf{\hat a}}}^ * } \otimes {\mathbf{\hat a}} + \lambda {\mathbf{I}}}} $

(5)

其中, $ \otimes $ 表示Hadamard乘积符号.

考虑实际中存在非线性问题, 使用核技巧可以将非线性回归问题映射到对偶空间, 使最优化问题依旧是线性的. 假设映射函数为 $ \varphi \left( {\mathbf{a}} \right) $ , 对应核函数为 ${\mathbf{\kappa }}\left( {{\mathbf{a}}, {\mathbf{a'}}} \right) = $ $ \left\langle {\varphi \left( {\mathbf{a}} \right), \varphi \left( {{\mathbf{a'}}} \right)} \right\rangle $ (点积: ${\mathbf{\kappa }}\left( {{\mathbf{a}}, {\mathbf{a'}}} \right) = {\varphi ^{\text{T}}}\left( {\mathbf{a}} \right)\varphi \left( {{\mathbf{a'}}} \right)$ ). 通过式(6)将待优化参数由线性空间 ${\mathbf{w}}$ 转变到对偶空间 ${\bf{\alpha }}$ ( ${\bf{\alpha }} = $ $ {\{ {{\alpha _1}, {\alpha _2}, \cdots, {\alpha _i}} \}^{\text{T}}}$ )

$ {\mathbf{w}} = \sum\limits_i {{\alpha _i}} \varphi ({{\mathbf{a}}_i}) $

(6)

原本对 ${\mathbf{w}}$ 的求解^[16]可以变换为:

$ {\mathbf{\hat \alpha }} = {{{\mathbf{\hat b}}} \mathord{\left/ {\vphantom {{{\mathbf{\hat b}}} {{{{\mathbf{\hat k}}}^{aa}} + \lambda {\mathbf{I}}}}} \right. } {{{{\mathbf{\hat k}}}^{aa}} + \lambda {\mathbf{I}}}} $

(7)

式中, k^az表示核矩阵 ${\mathbf{K}} = C\left( {{{\mathbf{k}}^{aa}}} \right)$ 的第一行.

(2) 目标搜索. 对响应函数求解得目标位置

$ {\mathbf{\hat f}}({\mathbf{z}}) = {{\mathbf{\hat k}}^{{{az}}}} \otimes {\mathbf{\hat \alpha }} $

(8)

其中, k^az表示基础样本a以及循环移位后训练样本z的核相关运算^[17,18].

(3) 模板更新. 更新策略如下:

$ {\bf{\beta }} = \left( {1 - \mu } \right){{\mathbf{\beta }}_{i - 1}} + \mu {{\mathbf{\beta }}_i} $

(9)

式中, $\;{{\mathbf{\beta }}_i}$ 表示当前帧的目标模板, $\;{{\mathbf{\beta }}_{i - 1}}$ 表示前一帧目标模板, $\;\mu $ 是常数.

3 粒子滤波

PF可分为模型建立、粒子散播、位置估计3部分.

(1) 模型建立. 首先提取颜色特征来计算颜色直方图^[19] ${{\mathbf{p}}_{{y_i}}} = \left\{ {p_{{y_i}}^{\left( u \right)}} \right\}\left( {u = 1, 2, \cdots, m} \right)$ , $p_{{y_i}}^{\left( u \right)}$ 可表示为:

$ p_{{y_i}}^{({\rm{u}})} = f\sum\limits_{i = 1}^L {k\left( {{{\left\| {{y_i} - {x_0}} \right\|} \mathord{\left/ {\vphantom {{\left\| {{y_i} - {x_0}} \right\|} a}} \right. } a}} \right)} \delta [h({y_i}) - u] $

(10)

式中, $u = 1, 2, \cdots, m$ 表示 $1 \times m$ 颜色直方图的第u单元, f表示归一化因子, L表示像素数, $a = \sqrt {H_{la}^2 + H_{sa}^2} $ ( ${H_{la}}$ 与 ${H_{sa}}$ 表示跟踪椭圆框长短轴的大小)表示尺度因子, $ \left\| {{y_i} - {x_0}} \right\| $ 表示像素点 ${y_i}$ 与目标区域中心 ${x_0}$ 的欧氏距离, $h\left( {{y_i}} \right)$ 为计算像素点 ${y_i}$ 位于直方图哪个单元的函数, $\delta $ 表示狄拉克函数. $k\left( r \right)$ 对应公式如下:

$ k\left( r \right) = \left\{ \begin{array}{l} 1 - {r^2},\;\;\;r < 1 \\ 0,\;\;\;\;\;\;\;\;\;\;\;\;{\text{otherwise}} \\ \end{array} \right. $

(11)

其中, r表示像素点与中心的距离. 然后利用颜色直方图计算巴氏系数^[20,21]以及巴氏距离:

$ \rho \left[ {{\mathbf{p}}, {\mathbf{q}}} \right] = \sqrt {{{\mathbf{p}}^{\rm{T}}}{\mathbf{q}}} $

(12)

$ d = \sqrt {1 - \rho \left[ {{\mathbf{p}}, {\mathbf{q}}} \right]} $

(13)

(2) 粒子散播. 粒子散播动态模型如下:

$ {{\mathbf{s}}_t} = {\mathbf{J}}{{\mathbf{s}}_{t - 1}} + {{\mathbf{w}}_{t - 1}} $

(14)

式中, ${\mathbf{J}}$ 表示状态转移矩阵, ${{\mathbf{s}}_{t - 1}}$ 为上一帧粒子坐标集合, ${{\mathbf{w}}_{t - 1}}$ 表示服从 ${N}\left({0}, {0.04}\right)$ 的一组高斯随机数集合.

(3) 位置估计. 根据粒子权重及粒子位置集合 ${{\mathbf{s}}_t}$ 获取目标位置:

$ E\left[ {{{\mathbf{s}}_t}} \right] = \sum\limits_{n = 1}^N {\pi _t^{\left( n \right)}} s_t^{\left( n \right)} $

(15)

其中, $N$ 表示粒子个数, ${\pi ^{\left( n \right)}}$ 表示每个粒子权重系数:

$ {\pi ^{\left( n \right)}} = {1 \mathord{\left/ {\vphantom {1 {\sqrt {2\pi \sigma } }}} \right. } {\sqrt {2\pi \sigma } }}{{\rm{e}}^{ - {{{d^2}} \mathord{\left/ {\vphantom {{{d^2}} {2{\sigma ^2}}}} \right. } {2{\sigma ^2}}}}} $

(16)

4 基于位置一步预测的核相关目标跟踪算法

结合KCF精度高及PF对快速移动目标跟踪有较好的鲁棒性的优点, 并针对机动目标移动过程中产生的形变、模糊问题, 有机融合PF与KCF, 提出了基于位置一步预测的核相关目标跟踪算法(KCF-PF). KCF-PF在KCF与PF的基础上融入了零截距^[22]以及平均峰值相关能量( $APCE$ )^[23], 分别用来解决形变、模糊问题. KCF-PF流程图如图1.

为解决形变问题, 首先根据目标区域的色调(H)矩阵求得色调直方图, 然后对其反向投影^[24]得到概率( ${\mathbf{prob}}$ )矩阵:

$ {\mathbf{prob}}(x, y) = {{his}}({\mathbf{H}}(x, y)) $

(17)

其中, $ x, y $ 表示横纵坐标, ${{his}}$ 表示反向投影运算. 进而根据 ${\mathbf{prob}}$ 矩阵求得零阶矩 ${M_{{\text{00}}}}$ 以及目标框宽 $s$ :

$ {M_{{\text{00}}}}{\text{ = }}\sum\nolimits_x {\sum\nolimits_y {{\mathbf{prob}}(x, y)} } $

(18)

$ s = k\sqrt {{{{M_{{\text{00}}}}} \mathord{\left/ {\vphantom {{{M_{{\text{00}}}}} {{\text{256}}}}} \right. } {{\text{256}}}}} $

(19)

式中, k表示一个大于1的常数, $ {{{M_{00}}} \mathord{\left/ {\vphantom {{{M_{00}}} {256}}} \right. } {256}} $ 表示搜索框中属于目标的像素点个数^[25], 目标框的长度为 $\eta s$ ( $\eta $ 为目标框长宽比例系数).

由于机动目标在快速运动过程中很容易出现模糊情况, 如果对此不进行处理, 会在每一帧更新的模板中加入背景扰动, 最终影响跟踪精度. 针对该问题, 首先利用 $APCE$ 对目标状态估计:

$ APCE = {{\left| {{F_{\max }} - {F_{\min }}} \right|} \mathord{\left/ {\vphantom {{\left| {{F_{\max }} - {F_{\min }}} \right|} {mean\left( {\sum\nolimits_{w, h} {{{\left( {{F_{w, h}} - {F_{\min }}} \right)}^2}} } \right)}}} \right. } {mean\left( {\sum\nolimits_{w, h} {{{\left( {{F_{w, h}} - {F_{\min }}} \right)}^2}} } \right)}} $

(20)

其中, ${F_{\max }}$ 与 ${F_{\min }}$ 表示响应矩阵中最大、最小值.

然后 $APCE$ 与预先设定阈值 $ Thr1 $ 比较, 当 $APCE$ 大于 $ Thr1 $ 时正常跟踪, 小于 $ Thr1 $ 时停止更新模板, 直至当前帧 $APCE$ 大于 $ Thr1 $ 后对目标重跟踪.

考虑到跟踪过程中时间与空间的连续性, 如果仅丢失一帧, 目标不会移动很远, 可以在上帧目标位置周围搜索, 但当连续帧丢失目标时, 目标可能位移到任何位置, 此时需要扩大搜索范围. 传统的遍历搜索方法花费时间长, 为减少重跟踪时长, 将视频帧划分成n个不重叠区域, 用倒金字塔搜索方式进行重跟踪. 倒金字塔搜索方式的迭代公式及步长计算公式如下:

$ \left\{ \begin{gathered} Pos(x_k^{(i)}, {y^{(i)}}) = Pos(x_{k - 1}^{(i)}, {y^{(i)}}) + \textit{Step}{_i}(x_{\rm step}^{(i)}, 0){\text{ }} \hfill \\ Pos({x^{(i)}}, y_k^{(i)}) = Pos({x^{(i)}}, y_{k - 1}^{(i)}) + \textit{Step}{_i}(0, y_{\rm step}^{(i)}){\text{ }} \hfill \\ \end{gathered} \right. $

(21)

$ \textit{Step}{_n}(x_{\rm step}^{(n)}, y_{\rm step}^{(n)}) = \tau \textit{Step}{_1}(x_{\rm step}^{(1)}, y_{\rm step}^{(1)}) $

(22)

其中, x、y表示横纵坐标, 式(21)中的上下两式分别表示沿着x、y方向的搜索迭代公式, $Pos\left( { \cdot , \cdot } \right)$ 表示搜索位置坐标, $\textit{Step}\left( { \cdot , \cdot } \right)$ 表示搜索步长, i表示区域编号, $\tau $ 表示常数.

为了更好地解释倒金字塔跟踪方式, 假设只有3个分区, 分区图如图2所示.

根据上次正确跟踪地目标位置为中心划分区域, 距离中心越远搜索步长越大, 第一分区是距离目标最近的搜索区域, 在第一分区进行搜索时步长最短. 第二分区步长是第一分区的二倍, 第三分区步长是第二分区的二倍, 公式如下所示:

$ \left\{ {\begin{array}{*{20}{c}} {\textit{Step}{_2}(x_{\rm step}^{(2)}, y_{\rm step}^{(2)}) = 2\textit{Step}{_1}(x_{\rm step}^{(1)}, y_{\rm step}^{(1)})} \\ {\textit{Step}{_3}(x_{\rm step}^{(3)}, y_{\rm step}^{(3)}) = 4\textit{Step}{_1}(x_{\rm step}^{(1)}, y_{\rm step}^{(1)})} \end{array}} \right. $

(23)

5 评价标准

为了对KCF-PF算法量化评价, 引入OTB数据集两个评价标准: 精确度(precision plot)以及成功率(success plot), 下面分别对两个评价标准进行简介.

(1) Precision plot: 跟踪过程中, 算法估计出的目标位置称为预测值, 人工标注目标位置为真实值, 两者的差值小于阈值的帧数占总帧数的百分比就是精确度. 一般选择20个像素点作为阈值, 给定的阈值不同, 求出的precision plot也不同.

(2) Success plot: 成功率的计算用到了覆盖率公式:

$ Cov = {{Area\left( {{B_T} \cap {B_G}} \right)} \mathord{\left/ {\vphantom {{Area\left( {{B_T} \cap {B_G}} \right)} {Area\left( {{B_T} \cup {B_G}} \right)}}} \right. } {Area\left( {{B_T} \cup {B_G}} \right)}} $

(24)

其中, ${B_T}$ 表示运行算法得到的目标框, ${B_G}$ 表示真实目标框, $Area$ 表示面积统计函数. 如果覆盖率大于给定阈值, 表明此帧成功跟踪, 成功跟踪的帧数占总帧数的百分比, 即成功率. 一般阈值设定为0.5, 给定阈值不同, success plot也不同.

6 仿真结果及分析 6.1 参数设定

为了更好地验证新方法的准确性, 设置了两组参数在不同的数据集上进行实验, 实验参数如表1所示.

6.2 模板更新策略的阈值选定实验

Jogging中部分视频帧与 $APCE$ 关系如图3所示.

对图3左边跑步女人分析, 第3帧没有遮挡及模糊情况, 此时 $APCE$ 大于30. 第74帧目标被遮挡, 此时 $APCE$ 小于10. 接着对OTB100中多个存在模糊、遮挡的视频分析后得到表2.

根据以上分析, 为了更好地运用历史信息并减少模糊、遮挡的影响, 得到新的模板更新策略如下:

$ \left\{ {\begin{array}{*{20}{l}} {{\mathbf{mel}} = \left( {1 - \mu } \right){\mathbf{me}}{{\mathbf{l}}_{T - 1}} + \mu {\mathbf{me}}{{\mathbf{l}}_T}},&{APCE \geqslant {\text{30}}} \\ {{\mathbf{mel}} = \left( {1 - 2\mu } \right){\mathbf{me}}{{\mathbf{l}}_{T - 1}} + \mu {\mathbf{me}}{{\mathbf{l}}_T} + \mu {\mathbf{me}}{{\mathbf{l}}_{T - 2}}}, &{{\text{30}} > APCE \geqslant {\text{20}}} \\ {{\mathbf{mel}} = {\mathbf{me}}{{\mathbf{l}}_{T - 1}}},&{APCE < {\text{20}}} \end{array}} \right. $

(25)

其中, $ \mu $ 表示常量, $ {\mathbf{mel}} $ 表示模板矩阵. 更改模板更新策略后的KCF-PF与其他算法性能比较如图4所示.

6.3 性能分析

与Meanshift、PF、KCF、SAMF相比, KCF-PF在UA-DETRAC及OTB100数据集上有更高的识别率, 具体提升如表3和表4所示.

6.3.1 定性分析

本节选取UA-DETRAC视频数据集中两个视频片段进行定性分析. 图5与图6为跟踪效果图, 其中红色框是KCF-PF, 黄色框是SAMF, 绿色框是KCF, 黑色框是PF, 蓝色框是Meanshift. 由图5与图6可以看出随着目标车辆的快速移动SAMF、KCF、PF、Meanshift都丢失了目标, 而KCF-PF可以对目标准确跟踪.

6.3.2 定量分析

本节对UA-DETRAC以及OTB100数据集进行定量分析, 结果如图7所示. 其中图7(a)与图7(b) 是在10个有快速移动情况车辆行驶序列中进行算法对比的结果; 图7(c)与图7(d) 是在25个车辆行驶视频序列中进行算法对比的结果; 图7(e)与图7(f)是在OTB100数据集中算法对比的结果; 图7(g)与图7(h)是在混合了OTB100与UA-DETRAC数据集中算法比较的结果.

7 结语

视频机动目标快速移动问题一直是目标跟踪问题中的难点, 结合粒子滤波以及核相关滤波算法的优点, 提出首先由粒子滤波算法预测目标位置, 然后核相关滤波算法修正目标位置的新方法, 在一定程度上解决了快速移动问题. 针对形变问题加入了零截距, 实现了对快速移动形变机动目标的跟踪, 在原模板更新策略的基础上融入平均峰值相关能量, 更好的利用了历史信息. 实验结果表明, 新方法可以有效地跟踪快速移动的机动目标.