0 引言

视频目标跟踪^[1]是计算机视觉领域研究的核心内容之一，同时也是图像处理的主要分支之一。在对运动目标进行检测和跟踪过程中，应用了多个研究领域的内容，比如图像处理、模式识别、人工智能和机器学习等。视频目标跟踪在智能视频监控、人机交互、机器人视觉导航、虚拟现实、医学图像分析和视频压缩等领域中有很大的理论意义和应用价值^[2]。

简而言之，视频目标跟踪是一个只知道目标的初始位置去估计它在一个图像序列中轨迹的问题。对目标的跟踪方法则成为各种跟踪算法中的重要组成部分。由于有限的目标先验知识，解决这个问题是特别具有挑战性的；而且，跟踪算法必须是灵活的，以应对快速的目标外观的变化，同时对发生遮挡和背景干扰应该是鲁棒的。

在最近几年，学者们运用tracking-by-detection的方法^[3-6]，使上述问题得到了一定的解决。在这类算法中，跟踪方法采用机器学习技术来训练目标样本的外观模型和背景模型。比如，监督学习方法中的支持向量机(Support Vector Machine, SVM)^[7]和岭回归^[8]方法通常构建一个有区分能力的分类器或回归量。在常用的目标跟踪算法中，基于均值漂移的MeanShift目标跟踪算法^[9-10]通过颜色直方图分别描述目标模型和候选模型，然后利用Bhattacharyya相似函数度量候选模板的相似性，选择使相似函数最大的候选模型并通过不断迭代计算MeanShift向量，实现对目标的跟踪。该算法实时性较好，并在目标发生形变、旋转时仍能有效跟踪目标，受到广泛的应用^[11]。

同时，此类跟踪模型的质量很大程度上依赖于它的训练集^[12]。当训练集不能正确表达目标时，标准的tracking-by-detection跟踪算法的结果会受到很大的影响。这些不正确的训练样本通常是因为目标发生了形变、旋转、遮挡和尺度变换，跟踪的不准确也会带来不正确的训练样本，从而导致分类器的退化。当训练集出错时，跟踪模型会出现目标漂移，最终导致目标跟踪失败。

因此，一个正确的训练集对此类算法至关重要，可避免发生目标漂移和跟踪失败。为了避免此类瓶颈的出现，本文算法在tracking-by-detection的基础上，采用了匹配跟踪和搜索跟踪，通过两种跟踪策略的结合，一定程度上防止了在跟踪过程中训练集出错，从而防止了在跟踪过程中出现目标漂移，提高了算法的准确性和鲁棒性。

本文提出了一种融合前景判别和圆形搜索(Foreground Discrimination and Circle Search, FDCS)的目标跟踪算法，该算法利用本文提出的圆形搜索(Circle Search, CS)算法对目标进行搜索跟踪，同时结合PBAS(Pixel-Based Adaptive Segmenter)前景判别算法进行匹配跟踪。其中，CS算法在应对目标移动时具有良好的跟踪效率；PBAS在跟踪过程中应对目标发生形变、部分遮挡、尺度变化和外部光照变化有较好的鲁棒性。

1 系统概述

本文在融合前景判别和CS的跟踪算法框架下，使用了图像感知哈希特征描述子，所提出的FDCS跟踪算法框架如图 1所示。其中，为了能够准确提取目标图像摘要，所采取的图像感知哈希算法使用了离散余弦变换(Discrete Cosine Transform, DCT)^[13]提取图像的低频信息来近似表示图像。DCT对图像的处理效果如图 2所示，DCT会将图片的低频信息集中在左上角，低频信息所对应的DCT系数会相对较大，而靠近右下角的高频信息对应的DCT系数较小。同时，FDCS采用搜索跟踪策略和匹配跟踪策略对视频运动目标进行跟踪，两种跟踪策略如下所述。

搜索跟踪策略 采用本文提出的CS算法，其思想是根据目标运动方向的不确定性和帧间目标运动的缓慢性，对跟踪目标周边区域(以目标为中心、半径为2的圆)的13个跟踪点进行判断搜索。

匹配跟踪策略 使用的是PBAS前景检测算法，它引入了控制论的思想和背景复杂程度的度量方法，使得前景判断阈值和背景模型更新率可以根据背景复杂程度自适应调整，保证了前景提取的正确率和鲁棒性。

2 图像感知哈希技术

本文算法使用了图像感知哈希(Image Perceptual Hashing)技术来描述图像特征，由于哈希的二值特性使得算法在特征描述与匹配的效率上得到了提高。

2.1 图像感知哈希性质

图像感知哈希又称为图像指纹(Image Fingerprinting)，是近几年新发展的一个图像特征描述算子^[14]。它用一个二进制比特串来近似表示图像，通过对图像数据的二值化提高了匹配算法的效率，增强了实用性。图像感知哈希技术的总体框架如图 3所示。

图像感知哈希技术要求所使用的哈希算法应当满足以下4个性质：

1) 摘要性(Compactness)。经过哈希算法生成的Hash值应远小于原图像的大小。

2) 唯一性(Uniqueness)。一幅图像经过同一哈希算法生成的Hash值是相同的。

3) 差异性(Otherness)。差异明显的图像经过同一哈希算法生成的Hash值是不相近的。

4) 鲁棒性(Robustness)。相似的图像经过同一哈希算法生成的Hash值是相同或相近的。

2.2 哈希特征值的生成

目前，比较流行的对图像构造Hash值的算法有均值哈希算法、感知哈希算法和差异哈希算法。由于均值哈希不能很好地以人类的视觉角度表达图像信息，更适合搜索缩略图；差异哈希侧重于局部差异，忽略了图像总体信息；为了模拟人类视觉对低频信息比较敏感的特点，并获得更精确的结果，本文选择感知哈希算法，它采用DCT算法，通过提取的DCT低频系数近似表示图像信息的方法，量化此低频信息生成图像感知Hash值。本文构造图像感知Hash值的流程如图 4所示。

本文图像感知Hash值生成定义为如下单向函数^[15]：

$ h = {\rm{PHGen}}\left( \mathit{\boldsymbol{I}} \right) $

(1)

其中：h表示由图像I生成的感知摘要，PHGen代表感知哈希的生成算法，PHGen的主要步骤如下：

1) 去噪。将图像进行灰度处理，转化为256阶的灰度图，并采用中值滤波法去除图像噪声。

2) 采样。通过采样处理，将图像分辨率置为32×32，有利于DCT的计算。

3) 分块。将得到的32×32图片分成4个16×16小块。

4) 提取DCT系数。计算4个小块经过DCT得到的DCT系数，分别选择各个系数矩阵的左上角4×4的低频系数，组成8×8的矩阵。

5) 量化。计算8×8系数矩阵的均值，将大于或等于均值的矩阵元素置为1，否则置为0，得到量化后的8×8二维二进制矩阵。

6) 生成Hash值。逐行读取8×8二维矩阵，得到长度为64的哈希二进制比特串。

2.3 哈希特征值的匹配

基于图像感知哈希算法的匹配，是通过其感知摘要的距离大小来表达两幅图像的相似程度。图像间的感知距离是通过Hash值的匹配算法完成的，用式(2)^[15]来表示：

$ pd = {\rm{PHMatch}}({h_i}, {h_j}) $

(2)

在本文中，PHMatch表示所使用的感知哈希匹配算法，输入参数h_i和h_j是两幅图像通过PHGen(感知哈希生成算法)生成的二进制感知摘要，输出参数pd表示两幅图像的感知距离，pd越大表示两幅图像越不相似，pd越小表示其相似度越高。因输入的Hash值为二进制数，所以本文使用汉明距离(Hamming Distance)^[16]计算Hash值的差异性，即两个二进制数对应位置的不同字符的个数，如式(3)所示，dis表示两个哈希字符串h_i和h_j的汉明距离。dis越小，h_i和h_j的差异性越小，即相似度越高。

$ dis = {\rm{HamDis}}({h_i}, {h_j}) $

(3)

3 FDCS跟踪算法

为了清晰描述FDCS算法及其跟踪步骤，将其中涉及到的一些新概念和相关定义给出如下。

3.1 CS算法

在实际生活中，运动目标在视频相邻两帧中的移动是缓慢的，根据FS(Full Search)算法(全局搜索算法)实验数据表明，50%~90%的运动目标在原目标中心旁的2个像素点移动。由于拍摄角度的不确定性和运动目标方向的不规则性，运动目标可能在原中心位置360°范围进行移动。所以，如图 5所示，在以原目标中心为圆心、半径为2的圆中的13个像素点，认为是具有最高匹配概率的搜索点。基于上述理论，本文提出了一种新的运动估计方法——圆形搜索(CS)算法。以下将先介绍算法中搜索点的分类，并描述算法的基本思想，再通过算法步骤具体介绍所提出的圆形搜索算法。

3.1.1 搜索点分类

CS算法对13个搜索点进行归类：圆环搜索点(Circle Ring Search Point, CRSP)和内圆搜索点(Inner Circle Search Point, ICSP)，如图 6所示。在目标跟踪算法中，搜索点表示与当前目标模板同大的矩形框的中心；同时，它们具备以下两个性质：

性质1  CRSP的四连通区域上的搜索点不全在大圆内。

性质2  ICSP的四连通区域上的搜索点全在大圆内。

3.1.2 算法基本思想

根据目标运动的缓慢性，CS算法先以上次目标中心为圆心、两个像素点为半径作圆，计算以圆内13个搜索点为中心的目标矩形框与目标模板的相似度，得到最大相似度搜索点(Max Similar Point, MSP)。若得到的MSP属于ICSP，则停止搜索，因为ICSP的四连通区域全部在圆内，则认为此时得到的MSP可靠性较强，达到局部最优，可作为此次的搜索结果；若得到的MSP属于CRSP，则将此MSP作为新的圆心，循环CS，直到得到的MSP属于ICSP为止。

3.1.3 算法步骤

步骤1  以上一次目标中心为圆心、半径为2作圆，分别计算圆内13个搜索点代表的矩形框与目标模板的相似度，若MSP属于ICSP，则进行步骤3；若MSP属于CRSP，进行步骤2。

步骤2  以当前找到的MSP所在位置作为新的圆心，得到新的搜索区域的13个搜索点，分别计算它们与目标模板的相似度，若MSP属于ICSP，则进行步骤3；若MSP属于CRSP，重复步骤2。

步骤3  以找到的MSP所在位置作为此次跟踪结果，即MSP所在位置为当前目标中心。

3.2 PBAS前景判别算法

PBAS前景检测算法是基于像素的无参数模型^[17]，该算法结合了经典的SACON(SAmple CONsensus)^[18]和ViBE(Visual Background Extractor)^[19]两个算法在计算速度和判断结果上的优势，并在这两个算法的基础上改进而来。其基本框架如图 7所示。

图 7中，R(x_i)为自适应的阈值，T(x_i)为自适应的更新率，d_min(x_i)为背景复杂度的度量。

主要步骤如下：

1) 建立背景模型。

PBAS算法采用类似SACON算法背景建模方法，收集前N帧像素以及梯度幅值作为背景模型, 构建方法如下：

$ \mathit{\boldsymbol{B}}{\rm{ }}({x_i}) = \{ {B_1}({x_i}), {B_2}({x_i}), \cdots, {B_k}({x_i}), \cdots, {B_N}({x_i})\} $

(4)

其中: B(x_i)表示像素点x_i的背景模型，是由像素点x_i的一系列过去被观察的背景像素值所构成; B_k(x_i)表示像素点x_i的背景模型中的第k个像素值。

2) 前景检测。

PBAS前景检测过程与ViBE算法类似，计算样本集合中满足匹配条件的样本个数，若小于阈值T_min，则认为是前景，不同之处在于不同像素的判断阈值R(x_i)不同；

$ F{\rm{ }}({x_i}) = \left\{ \begin{array}{l} 1, \;\{ dist{\rm{ }}(I{\rm{ }}({x_i}), {B_k}({x_i})) < R({x_i})\} < {T_{\min }}\\ 0, 其他 \end{array} \right. $

(5)

式(5)中：F(x_i)存储像素点x_i的判断结果，1表示为前景，0表示为背景；R(x_i)为距离阈值，该参数取决于像素位置并可以动态变化；阈值T_min是一个固定的全局参数。

3) 背景模型的更新。

由于被判定为前景的区域是不会被用来进行更新的，因此，只有像素被判为背景点F(x_i)=0，才能进行背景模板更新。其更新过程与ViBE算法类似，被判断为背景的像素只有p=1/T(x_i)的概率来进行更新，同样，也有p=1/T(x_i)的概率去随机选择目标像素的相邻像素y_i∈N(x_i)来进行更新。不同之处在于更新率不同，ViBE是固定的更新率，而PBAS的更新率是自适应的，并且更新使用的像素值是邻域样本集合中y_i的新像素值，而不是用x_i本身的新像素值。

4) 判决阈值R(x_i)的更新。

首先，除了将过去观察到的像素值储存在背景模板B(x_i)中，还要建立一个最小决策距离数组D(x_i)={D₁(x_i), D₂(x_i), …, D_N(x_i)}。只要背景模板B(x_i)进行更新，当前观测的最小距离$ {d_{\min }}\left( {{x_i}} \right) = \mathop {\min }\limits_k dist\left( {I\left( {{x_i}} \right), B\left( {{x_i}} \right)} \right) $被放入了该数组：D_k(x_i)←d_min(x_i)。结果，建立了一个最小决策距离的寄存器。这些数的平均值$ {\bar d_{\min }}\left( {{x_i}} \right) = 1/\sum\limits_k {{D_k}} \left( {{x_i}} \right) $就是对背景变化的估算，作为背景复杂度的度量。背景越复杂，其判断阈值应该越大，保证背景像素不被误判为前景；背景越简单，微小的变化都是由前景引起，判断阈值应该越小。调整策略如下：

$ \begin{array}{l} R{\rm{ }}({x_i}) = \\ \left\{ \begin{array}{l} R({x_i})\cdot(1-{R_{{\rm{inc/dec}}}}), \;\;R({x_i}) > {{\bar d}_{{\rm{min}}}}({x_i})\cdot{R_{{\rm{scale}}}}\\ R({x_i})\cdot(1 + {R_{{\rm{inc/dec}}}}), \;\; 其他 \end{array} \right. \end{array} $

(6)

式(6)中：R_inc/dec是阈值的变化量，R_scale用于控制背景复杂度对判断阈值的调整。

5) 学习参数T(x_i)的更新。

当视频帧中的背景越复杂，其出现判断错误的概率越大，对应的背景更新的频率应该越低，为了减少判断错误对背景模型的影响，学习参数T(x_i)的更新策略如下：

$ T({x_i}) = \left\{ \begin{array}{l} T({x_i}) + {T_{{\rm{inc}}}}/{{\bar d}_{{\rm{min}}}}({x_i}), F{\rm{ }}({x_i}) = 1\\ T({x_i}) + {T_{{\rm{dec}}}}/{{\bar d}_{{\rm{min}}}}({x_i}), F{\rm{ }}({x_i}) = 0 \end{array} \right. $

(7)

式(7)中：F(x_i)表示前景检测结果，T_inc和T_dec分别表示更新率增加、减小的幅度。此外，本文还为学习参数T(x_i)定义了上限和下限T_lower < T < T_upper，因此该数值不会出现很大的偏差。

3.3 算法实现

根据以上叙述，下面给出FDCS跟踪算法的流程思想：首先，本文算法根据用户手动划定的跟踪目标区域建立目标模板的哈希特征描述算子；其次，使用CS算法作为搜索跟踪算法，得到当前帧目标的搜索跟踪结果，并计算跟踪得到的目标Hash值与目标模板Hash值的相似度；再次，使用前景判别PBAS算法作为匹配跟踪算法，获取当前帧目标的匹配跟踪结果，并计算跟踪得到的目标Hash值与目标模板Hash值的相似度；然后，将匹配跟踪结果和搜索跟踪结果进行比较，取其与目标模板相似度更高者为当前帧目标位置；最后，计算包含匹配跟踪与搜索跟踪结果最小矩形框的重叠率，并结合跟踪得到的目标与目标模板的相似度，根据阈值判断条件更新目标模板。下面给出在线目标跟踪算法:

1) 读入视频帧序列，在初始帧手动选择目标跟踪区域r_obj(x₀, y₀, w₀, h₀)，令frame=1。

2) 在新的一帧中，以上次目标中心(x_i, y_i)为起点，进行如下循环：

① 以(x_i, y_i)为圆心、半径为2作圆，分别计算以圆内13个搜索点为中心的目标的Hash值，并使用汉明距离计算其与目标模板的哈希距离search₁, search₂, …, search₁₃；

② 若min(search₁, search₂, …, search₁₃)对应的搜索点属于ICSP，则将此搜索点作为当前帧搜索跟踪得到的目标的中心，break；

③ 若min(search₁, search₂, …, search₁₃)对应的搜索点属于CRSP，则将此搜索点作为新圆形搜索的圆心，返回①。

3) 对当前帧使用PBAS前景提取算法，得到包含前景的最小矩形框的集合fg₁, fg₂, …, fg_k，计算这k个前景的Hash值，并使用汉明距离计算其与目标模板的哈希距离match₁, match₂, …, match_k，取min(match₁, match₂, …, match_k)对应的前景为当前帧匹配跟踪得到的结果。

4) 若min(search₁, search₂, …, search₁₃) ≤min(match₁, match₂, …, match_k)，则将搜索跟踪得到的结果作为当前帧的跟踪结果; 否则将匹配跟踪得到的结果作为当前帧的跟踪结果。

5) 计算跟踪结果与目标模板的匹配相似度σ_frame，这里使用汉明距离表示相似度，汉明距离越小，即图像的相似度越高。

6) 根据式(8)计算当前帧搜索跟踪结果R_search与匹配跟踪结果R_match的重叠率：

$ \delta = \frac{{{S_{{R_{{\rm{search}}}}}} \cap {S_{{R_{{\rm{match}}}}}}}}{{{S_{{R_{{\rm{search}}}}}} \cup {S_{{R_{{\rm{match}}}}}}}} $

(8)

7) 若(δ > T_δ)∩(σ_frame < T_σ)，则以当前帧跟踪结果更新目标模板，其中，T_δ=0.7, T_σ=10。

8) frame++，若frame ≤ N(N为总帧数)，返回2)；否则跟踪结束。

4 实验结果与分析

为了验证新算法的效果，本文使用了标准摄像机拍摄的Walker视频和目标跟踪视频库Visual Tracker Benchmark^[20]中的4个具有代表性的测试视频序列进行实验，并与MeanShift算法在运行精度、准确率和实时性等3个方面进行了比较。同时，由于两个算法对目标跟踪过程中都存在随机的因素，为了提高实验数据的准确性，在提取每组实验数据时分别对两个算法进行了5次实验，取5次实验结果的平均值作为该组最终的实验数据结果。本实验的计算机配置为: Intel Core i5-4590 3.30 GHz处理器，8 GB内存，实验平台为Visual Studio 2012。

表 1分别列出了两个算法在精度、准确率和实时性的对比结果。两个算法精度的对比，即对比两个算法实验结果中跟踪得到的目标位置与实际目标位置的误差，误差单位为像素点(pixel)，计算所有帧的跟踪误差，取其平均值作为最终的精度对比结果；当该帧目标的跟踪位置与实际位置的跟踪误差超过20像素，则认为该帧跟踪错误，计算每个视频帧序列中非跟踪错误的帧数占总帧数的比例，作为两个算法准确率的对比结果；两个算法的实时性对比用每帧所需的处理时间(单位s·frame^-1)来表示。

David视频(320×240)目标在移动的过程中，发生了明显的形变和光照变化。从图 8(a)中可以看出本文跟踪算法表现出色，跟踪误差较小，在目标受到干扰(如178帧左右目标戴眼镜动作)时能够保持持续跟踪，在目标光照强度变化之下(188帧左右)也能保持稳定的跟踪; 而MeanShift跟踪算法在跟踪过程中发生了明显的偏移，跟踪效果较差，如图 8(b)所示。

在BlurCar2视频(640×480)中，由于是在行车过程中拍摄，视频中的目标不间断地发生剧烈抖动(如142帧所示)，抖动造成了视频帧模糊，使得算法容易跟丢目标。如图 9(a)所示，可见本文算法在目标发生抖动的过程中仍能跟踪目标；而MeanShift跟踪结果发生严重偏移，导致跟踪失败，如图 9(b)所示。

在Couple视频(320×240中，目标的背景比较复杂，移动的过程中有车辆驶过目标，同时目标在移动的过程中发生了形变和尺度变化，两个跟踪算法均能跟踪到目标，但本文算法跟踪结果偏移量更小，如图 10所示。

Girl视频(128 Pixel×96 Pixel)中，视频的分辨率较低，且目标在移动的过程中发生了旋转、遮挡和尺度变化等，对目标的跟踪产生较大的影响。如图 11(a)所示，本文跟踪结果较为稳定，只发生轻微偏移；但MeanShift算法在跟踪过程中发生了较明显的偏移，如图 11(b)所示。

为了对比两种算法的实际跟踪效果，不仅使用了上述4个目标跟踪视频库中的测试视频，还使用了标准摄像机拍摄的视频进行实验。如图 12中的Walker(320×240)视频中，目标与背景较为相近，且目标的尺度较小，不利于对目标进行特征描述，并在行走的过程中目标发生了形变，在视频后半部分出现了类似的行人，容易导致目标跟踪错误。通过实验表明，本文算法仍能准确跟踪目标，而MeanShift算法发生了轻微偏移，跟踪结果如图 12所示。

5 结语

为了能在目标在发生遮挡、形变、旋转和光照等变化时仍能保持准确的跟踪，本文提出了一种融合前景判别和CS的目标跟踪算法。该算法通过搜索策略与跟踪策略的结合，并利用图像感知哈希技术表达目标，使其能够有效解决以上问题。其中，图像感知哈希技术的引入使算法具有了较好的实时性，前景判别PBAS算法通过全局搜索提高了跟踪的鲁棒性，CS算法能够快速地定位到局部最优，并有效进行实时跟踪。实验结果表明，本文算法在应对目标发生遮挡、形变、旋转和光照等变化下仍能保持准确跟踪，且在精度、准确率和实时性上都优于MeanShift算法。但当目标在动态的背景下发生快速移动时，会丢失目标。在未来的工作中，将针对快速移动的目标跟踪作进一步的研究。