0 引言

目标跟踪是计算机视觉领域研究中的一个核心问题。在过去的十多年中它已经迅速成为学者们研究的热点, 不断地被应用于国防军事和生产生活的各个领域, 比如轨道预测、精确制导系统、视频监控^[1]、目标识别^[2]、行为分析^[3]、机器人视觉导航^[4]、视频检索^[5]、三维重建^[6]等。

目标的有效表征是跟踪算法实现的首要条件，影响表征的因素很多，主要可分为以下两类：可逆因素和不可逆因素。可逆因素有对比度、视觉变化等；不可逆因数有遮挡、传感器量化和光照变化等。近些年，为了消除不利因素对跟踪效果的影响，许多具有代表性的算法被提出。下面将具体介绍这些算法。

在L1算法^[7]中，作者采用像素的稀疏子空间表示，并且将模板和像素值结合提升跟踪性能，这些模板主要判断在候选区域是否有目标。虽然模板考虑了遮挡，但是这些基于像素的启发式表示对局部遮挡和运动模糊比较敏感。Predator-TLD(Predator Tracking learning Detection)算法^[8]和ConTra(Context Tracker)算法^[9]采用了LBP(Local Binary Pattern)特征表征目标。MIL(Multiple Instance Learning)算法^[10]和PROST(Parallel Robust Online Simple Tracking)算法^[11]采用Haarlike特征表征目标。虽然这些都是局部特征，但是都是对目标模板作全局估计, 也都是对局部遮挡比较敏感。

在CoGD(Cotrained Generative and Discriminative trackers)算法^[12]、ET(Ensemble Tracking)算法^[13]以及其他部分跟踪算法都采用纹理特征来提高目标和背景的区分度。这就把问题变成了怎么提高从背景区域分离出前景图像区域的准确率。这些算法使用轴对齐矩形边界框分离目标图像区域，但是这种方法可能将背景区域划分到目标区域，使目标逐渐退化，造成跟踪漂移。在文献[8]中使用目标分割解决了跟踪漂移问题，但是鲁棒的目标分割就成为能否有效跟踪的瓶颈。

模板更新也是目标跟踪的一个重要部分。优秀的模板跟踪算法能够增强算法的抗干扰能力，保持长时间跟踪而不会产生跟踪误差漂移。在MIL算法^[10]和其他跟踪算法中，模板更新是通过使用增强的级联分类器跟踪图像块和学习目标实现的。在线增强算法要求数据是独立的，并且服从一致性分布。在PROST算法^[11]中，作者将光流跟踪算法和在线随机森林结合，以提高跟踪的性能；但是级联分类器和在线随机森林中参数众多，各参数的选取也是一个难题，针对不同的应用场景，需要调整各个参数，这些都严重影响算法的鲁棒性。

本文针对目标跟踪过程中的长视频序列跟踪漂移问题、部分遮挡问题提出了一种基于随机一致性采样(RANdom SAmple Consensus, RANSAC)估计的目标跟踪算法。算法首先在从估计的目标搜索区域提取局部不变特征集，然后利用特征匹配传递性和非参数学习方法从特征集中分离出目标特征，再对目标特征进行随机一致性采样估计跟踪目标位置，并且判断目标是否存在遮挡以及更新目标模板和背景模板。

1 随机一致性采样估计目标跟踪算法

这一章，将对跟踪算法作总体概述以及介绍算法模块之间的关系，算法流程如图 1。

1.1 算法概述

设S(x, y, r)表示以(x, y)为中心，r为半径的目标搜索区域，然后采用两个不同的无参最近邻分类器分别判别跟踪目标和背景。目标模板T_t表示t时刻目标的形状和外观：

${T_t} = \left\{ {\left( {{\boldsymbol{p}_i},{\boldsymbol{d}_i}} \right)} \right\}_{i = 1}^{{N_t}}$

(1)

其中: p∈R²是关键点在目标模板坐标系统中的位置，d∈Rⁿ是特征描述子向量，N_t是目标特征的个数。背景模板C_t表示目标周围的背景：

${C_t} = \left\{ {{\boldsymbol{d}_i}} \right\}_{i = 1}^{{N_c}}$

(2)

其中：d∈R^d是背景区域关键点的特征描述子向量，N_c是特征个数。这里采用具有尺度不变性特征变换(Scale-Invariant Feature Transform, SIFT)的特征描述子^[14]。

目标跟踪是通过两个模板T_t、C_t相互配合和跟踪目标的状态变量X_t实现的。在时刻t的状态变量X_t包括目标的中心位置(x_t, y_t)和相对于t=0时刻边界框的尺度s_t，相当于间接定义一个目标方向矩形框OBB(X_t)。因此，这里定义了一个二维相似变换:

$\boldsymbol{M}\left( {\boldsymbol{p},{\boldsymbol{X}_t}} \right) \Leftrightarrow {\boldsymbol{X}_t} = \left( {{x_t},{y_t},{s_t}} \right)$

(3)

p∈R²是关键点的坐标，M : R²｜ → R²是将图像中检测到目标的位置映射到目标模板的坐标系统，X_t=(x_t, y_t, s_t)是需要预测的目标状态变量。

对于搜索区域的估计，假定：在时刻t，跟踪目标出现在时刻t-1估计的跟踪状态的半径r内。即：

$P\left( {{{\boldsymbol{\hat X}}_t}\left| {{{\boldsymbol{\hat X}}_{t - 1}}} \right.} \right) = \left\{ \begin{array}{l} \begin{array}{*{20}{c}} {1,}&{{{\left\| {{{\boldsymbol{\hat X}}_t} - {{\boldsymbol{\hat X}}_{t - 1}}} \right\|}_\infty }M < r} \end{array}\\ \begin{array}{*{20}{c}} {0,}&{其他} \end{array} \end{array} \right.$

(4)

目标检测返回跟踪的状态和概率P(y=1|S_t)：

${S_t} = \left\{ {\left( {{p_i},{d_i}} \right)} \right\}_{i = 1}^{{N_s}}$

(5)

是从图像搜索区域S(x, y, r)提取的特征集。y是二值变量，表示在图像中是否存在跟踪目标。如果在某一帧图像没有检测到跟踪目标，算法将使用随机搜索确定搜索区域，再检测目标。

在检测到目标之后，算法将判断目标是否存在遮挡。如果没有遮挡，将分别更新目标模板和背景模板。所有在OBB(X_t)区域内的局部特征都将被标记为目标特征，目标区域之外的局部特征和前l-1帧图像的背景特征累积作为背景特征C_t:

${C_t} = \bigcup\limits_{\tau = t - l}^t {\left\{ {\left( {\boldsymbol{p,d}} \right)\left| {p \in {A_\tau }} \right.} \right\}} $

(6)

其中${A_\tau } = {S_t}/OBB\left( {{{\boldsymbol{\hat X}}_t}} \right)$。

1.2 目标特征选择

为了区分目标特征和背景特征，这里利用搜索区域特征集S_t、背景区域特征集C_t和目标特征集T_t之间匹配关系的传递性：

$\left( {{T_t} \sim {S_t}} \right) \cap \left( {{C_t} \sim {S_t}} \right) \Rightarrow {T_t} \sim {C_t}$

(7)

式(7)表示如果在特征集S_t中的特征既与C_t中的特征匹配又与T_t中的特征匹配，那么该特征对目标和背景没有足够的区分度。根据以上原理，所有满足式(7)的特征将被剔除：

${F_t} = T_t^*/C_t^*$

(8)

其中:T_t^*是特征集S_t中与T_t中特征匹配的特征集，C_t^*是特征集S_t中与C_t中特征匹配的特征集，这两个特征集是通过两个最近邻分类器^[14]分类得到的。这种方法同时也会剔除目标矩形框里背景区域特征。图 2(a)表示了在搜索区域提取的SIFT特征点，图 2(b)表示从搜索区域分离出的目标特征点。

1.3 目标状态估计

采用式(8)获得的特征集F_t估计相似转换模型M和目标状态X_t。这里采用随机一致性采样估计相似转换模板。它可以从一组包含“局外点”的观测数据集中，通过迭代方式估计数学模型的参数。它是一种不确定的算法——有一定的概率得出一个合理的结果，为了提高概率必须增加迭代次数。

在对模型M进行估计的过程中，用p表示迭代过程中从特征集内随机选取出的特征均为目标特征的概率；此时，结果模型很可能有用，因此p也表征了算法产生有用结果的概率。用w表示每次从特征集中选取一个目标特征的概率：

w=目标特征的数目/特征集中特征的数目

通常情况下，w的值未知，但是可以给出一些鲁棒的值。假设估计模型需要选定n个特征，wⁿ是所有n个特征均为目标特征的概率；(1-wⁿ)是n个特征中至少有一个特征不是目标特征的概率，此时表明从特征集中估计出了一个不好的模型。(1-wⁿ)^k表示算法k次采样都不会选择到n个特征均为目标特征的概率，它和1-P相同。因此:

$1 - P = {\left( {1 - {w^n}} \right)^k}$

(9)

对式(9)的两边取对数，得出：

$k = \frac{{\log \left( {1 - P} \right)}}{{\log \left( {1 - {w^n}} \right)}}$

(10)

值得注意的是，这个结果假设n个特征都是独立选择的；也就是说，某个特征被选定之后，它可能会被后续的迭代过程重复选定到。这种方法通常都不合理，由此推导出的k值被看作是选取不重复点的上限。为了得到更可信的参数，标准偏差或它的乘积可以被加到k上。k的标准偏差定义为：

$SD\left( k \right) = \sqrt {1 - {w^n}} /{w^n}$

(11)

根据上面的算法可以估计出相似转换矩阵M，进而根据相似变换矩阵M，得到目标的位置。

$\left( {{x_t},{y_t}} \right) = \boldsymbol{M}\left( {{x_o},{y_o}} \right)$

(12)

其中：(x_o, y_o)是目标在对应的目标模板坐标系统中的位置，(x_t, y_t)是目标在图像中的位置。再根据比例关系计算出目标矩形框的尺度s_t。

为了防止目标模板过拟合，设定固定的迭代次数。这里通过式(13)判断估计的结果是不是目标:

$P\left( {y = 1\left| {{S_t}} \right.} \right) = \left\{ \begin{array}{l} \begin{array}{*{20}{c}} {1,}&{{{\left\| {{{\hat s}_t} - {{\hat s}_{t - 1}}} \right\|}_\infty } < {k_s}} \end{array}\\ \begin{array}{*{20}{c}} {0,}&{其他} \end{array} \end{array} \right.$

(13)

k_s是预定义的常量，控制尺度变化的最大速度，这可以避免在相似变换过程中由坐标和非中心对称建模引起的误报。因为跟踪是在尺度空间上执行的，从检测的目标上提取的特征要好于目标模板上的特征，因此，使分类器学习正确目标的外观和形状更容易。

1.4 遮挡检测

当视频中出现连续遮挡时，引进另一个分类器阻止模板更新。在OBB(X_t)区域里也可能包含特征集C_t^*中的特征。

${O_t} = \left\{ {\left( {\boldsymbol{p,d}} \right) \in \left| {p \in OBB\left( {{{\boldsymbol{\hat X}}_t}} \right)} \right.} \right\}$

(14)

在特征集O_t中的特征可能是：目标和背景模棱两可的特征、目标和背景边界特征、有遮挡目标的特征。对于前两类特征，不予考虑；而第三类特征的数目往往很多，因为遮挡通常由大量的联通区域构成。因此，遮挡的检测可以通过计算式(14)中O_t的模值|O_t|然后和阈值比较判断。如果目标有遮挡，目标模板不更新。跟踪效果如图 3。

1.5 目标和背景模板更新

所有在搜索区域特征集S_t里同时又包含在OBB(X_t)里的特征被标记为目标特征(集合ε_t表示当前新的目标特征集合)。新特征在模板中的位置由式(15)计算：

$\boldsymbol{p'} = \boldsymbol{M}\left( {\boldsymbol{p};{{\boldsymbol{\hat X}}_t}} \right)$

(15)

然后计算当前特征ε_t在模板中的位置，再和前一时刻的目标特征集T_t-1求并集得到当前的目标特征模板T_t：

${{\varepsilon '}_t} = \left\{ {\left( {\boldsymbol{p',d}} \right)\left| {\left( {\boldsymbol{p,d}} \right) \in {\varepsilon _t},\boldsymbol{p'} = M\left( {\boldsymbol{p};{{\boldsymbol{\hat X}}_t}} \right)} \right.} \right\}$

(16)

${T_t} = {\varepsilon _t} \cup {T_{t - 1}}$

(17)

这里，当目标特征集里特征数目大于N_T时，通过随机采样移除多余的特征。这种重采样策略为模板中匹配和不匹配的特征提供了目标的重新表示，模板中非匹配特征在跟踪算法中扮演一个重要角色。实际上，这些特征可能表示目标旋转之后的模板样本，这可以增加目标外观和外形的普适性。

同时，背景也必须被更新, 对于遮挡特征集D_t，将所有的遮挡特征累积：

${D_t} = {D_{t - 1}} \cup {O_t}$

(18)

当特征集的数目大于N_D时，也采用随机采样移除多余的特征。在当前帧中，所有搜索区域特征集S_t中同时又不包含在OBB(X_t)里的特征被标记为背景特征。这里累加最近的1帧图像的背景特征和遮挡特征D_t作为背景模板特征C_t：

${C_t} = \bigcup\limits_{\tau - 1}^t {\left( {{S_\tau }/{\varepsilon _\tau }} \right) \cup {D_t}} $

(19)

2 实验结果分析 2.1 实验环境设置

为了验证本文算法的性能，本文选择了3个不同的视频序列(Pedestrian1、Jumping、Motocross)共3 118帧与其他算法进行实验对比，实验的3个视频序列包括了遮挡(Pedestrian1)、运动方向和速度的突然变化(Jumping)以及长时间的视频序列(Motocross)等情况，可以很好地测试目标跟踪算法的效果。参与对比的跟踪算法有：OB(On-line Boosting)跟踪算法^[15]，半监督在线Boosting(SB)跟踪算法^[16]和TLD(Tracking-Learning-Detection)跟踪算法^[17]。

2.2 实验评价指标

3个评价指标分别是：准确率、召回率和综合评价指标(F1-Measure)：

$F1 = \left( {2 \times P \times R} \right)/\left( {P + R} \right)$

(20)

其中：P是准确率，R是召回率。

准确率：视频中跟踪到目标的总帧数与视频总帧数之比。

召回率：视频中跟踪到目标的总帧数与视频含有目标的总帧数之比。

F1综合评价指标是准确率和召回率的调和平均数。

2.3 实验结果分析

文中实验的参数设置分别是：N_T=1 000, N_c=1 500，遮挡检测阈值N_o=5，l=8, k_s=0.8。从表 1的实验结果(下划线数据表示此算法性能最好)可以得出：对于含有遮挡的Pedestrian1视频序列，本文算法和TLD跟踪算法^[17]在准确率

和召回率上都优于另外两种算法，说明本文算法对含有遮挡的目标跟踪更加鲁棒；在Jumpimg视频序列中，本文算法的准确率和召回率优于OB算法^[15]和SB算法^[16]但是略逊色于TLD跟踪算法^[17]；在Motocross长视频序列中，本文算法的准确率和召回率都明显优于其他3种算法，故而也说明本文算法对跟踪漂移有一定的抑制。跟踪部分效果如图 5、图 6和图 7。

3 结语

针对跟踪过程中，经常会出现目标遮挡、外观变化和时间过长导致跟踪失败的问题，本文将特征匹配关系传递性用于目标跟踪，并结合随机一致性采样算法估计目标位置，用以提高跟踪的准确性。实验结果表明，采用本文算法后，准确性有了一定的提高，跟踪漂移也得到一定的抑制，从而验证了本文算法的有效性。