懒交互模式下散乱不规则分块引导的目标跟踪*

刘财兴，李亚桢，陈铭钦，梁云，甘乙波

(华南农业大学数学与信息学院，广东 广州 510642)

目标跟踪是计算机视觉领域研究热点之一，通过对视频序列中的目标提取特征，然后根据特征匹配视频流中每帧的位置和目标大小，从而实现目标跟踪。目标跟踪具有广泛的应用前景，如视频监控(实现对目标自动监控)、无人机(实现对目标的自动跟踪拍摄)等。本文采用懒交互将跟踪目标分成多个散乱不规则分块，基于核相关滤波算法实现对各个分块进行建模和跟踪。根据每个分块的置信度值等进行异常判定，采用懒交互方式对异常判定进行重采样。最后运用霍夫投票算法确定跟踪目标在新一帧中的位置。其中,懒交互处理将目标分成多个散乱不规则分块，保证分块对目标特征描述的有效性以及通过对目标典型特征进行多次不规则的采样，能够更好的适应目标状态的变化。与现有跟踪方法相比，本文跟踪算法在旋转、复杂背景、光照变化等挑战的跟踪准确度和成功率具有显著提高。

1 相关工作

目标跟踪是计算机视觉领域研究热点之一。近年来多种目标跟踪方法被提出，如基于相关滤波方法和基于卷积神经网络方法等[1-11]。但是由于现实情况复杂多变，如目标在跟踪过程中出现遮挡、光照变化、旋转等情况，容易导致跟踪目标丢失。故此，设计出一种鲁棒性很好的跟踪算法是一大挑战。

目标跟踪过程中关键步骤之一是建立符合跟踪目标特征的表观模型。主流的跟踪方法对于跟踪目标的表观模型有两种，一种是用跟踪目标的全局特征描述和表达目标物体[2,12-15]；一种是将跟踪目标分块多个分块，通过对每个分块进行局部特征来表示跟踪目标[16-19]。

基于局部特征的目标跟踪，即通过对目标的局部信息进行跟踪来达到对目标整体跟踪的效果。如：Cai等[24]提出采用超像素分解目标，通过对计算相邻超像素点像素差值进行连接从而区分背景与目标，增加目标跟踪的准确性。Guo等[25]通过学习和训练目标局部特征构建和更新目标表观模型，以解决遮挡或光照等跟踪挑战。Li等[16]基于核相关滤波方法提出基于可靠分块的目标跟踪方法，通过将跟踪目标分成N个分块，然后对每个分块进行跟踪，来提高算法的鲁棒性。以上方法都是通过规则、随机局部分块对跟踪目标进行描述，在跟踪过程中随着跟踪目标的运动和背景的变化，容易出现分块偏移，导致跟踪目标丢失。

本文在继承基于局部跟踪方法的基础，采用懒交互对目标进行分块建模和更新，进一步保证目标外观的准确性。采用交互方式确定初始化目标，能够很好的确定跟踪目标区域，避免出现冗余区域，但大部分交互方式比较复杂难操作[26-27]。本文交互方式在目标区域内随意划分分块，简单易操作，故称为“懒交互”。首先在初始化建模阶段，采用懒交互方式将目标分成多个散乱不规则分块。然后运用核相关滤波方法对每个分块进行初始化建模，以此能够有效地控制欠拟合或者过拟合现象。其次对每个分块跟踪过程中进行异常判定，并对异常分块采用懒交互方式进行重采样，从而可以在最大程度上保证分块的有效性。本算法的优点在于：

(i) 采用懒交互方式将目标划分为N个散乱不规则分块，简单易操作。

(ii) 对每个分块分别建模，当个别分块出现跟踪异常时，并不会影响整体的跟踪效果，有效地提高了算法的鲁棒性。

(iii) 提出基于懒交互方式目标跟踪方法。在跟踪过程中目标框发生漂移现象时，能及时处理掉异常的块并进行重采，使目标框能够重新正确的对目标进行跟踪，以保证跟踪的延续性，从而保证跟踪算法的准确性。

2 本文系统框架

本文通过懒交互的方式将跟踪目标分成多个散乱不规则分块，提出了一种基于懒交互模式下散乱不规则分块引导的目标跟踪方法。根据实现过程本文算法主要流程是：首先采用懒交互方式将跟踪目标分成N个散乱不规则分块并对每个分块建立初始化表观模型；然后根据表观模型和核相关滤波方法对每个分块进行跟踪,并根据跟踪结果确定每个分块在新一帧上的位置；接着对每个分块进行异常判断并对异常分块采用懒交互方式重采样，并对非异常分块更新。最后采用霍夫投票算法[28]确定跟踪目标在新一帧上的位置，并更新目标模板进行后续的跟踪。本文算法流程如图1所示，包含目标建模阶段、目标跟踪阶段和目标模板更新阶段。

目标建模阶段：在第一帧图像上以标准目标区域为基础，向四周扩展得到一个扩展区域。在扩展区域内采用交互方式随机选取N个散乱不规则分块(例如N=25)，并提取各个分块中心位置，同时计算分块中心与跟踪目标位置的偏移值，以此判定分块正负样本属性，若分块在标准目标区域内则为正样本，否则为负样本。最后，运用核相关滤波方法，构建出每个分块的表观模型。

图1 本文算法总体流程图Fig.1 Algorithm flow chart

目标跟踪阶段：输入新一帧图像，对每一个局部分块进行核相关滤波操作，得到每个分块在当前帧出现在每个位置上的概率值和每个分块在目标对象上概率值，从而确定每个分块的作为目标中心位置的概率值。由此，得到每个分块在当前帧的跟踪位置，再根据所有分块的跟踪位置，并结合霍夫投票算法初步得到跟踪目标位置。其次对每个分块进行异常判定，依据是：分块与跟踪目标中心距离值、分块跟踪中心的置信度值、所有分块的正负样本比例值。然后比较异常块数量与预先设定阈值大小，当异常块数量大于阈值时采用交互方式重采相对应的异常分块数量。最后根据每个分块在新一帧上的中心位置值和每个分块的作为目标中心位置的概率值运用霍夫投票算法确定目标位置。

目标模板更新：主要为对异常分块重采样的重新建模和对非异常分块的模型更新。重采样分块的建模过程即分块初始化过程。非异常分块的更新为：更新其在新一帧中的参数，建立新的表观模型，再与旧表观模型线性组合。

3 懒交互模式下散乱不规则分块引导的目标跟踪

本章首先介绍如何根据懒交互和散乱不规则分块建立跟踪目标的表观模型，然后结合核相关滤波方法，对每个分块进行跟踪。最后根据所有分块的中心位置，运用霍夫投票计算跟踪目标的跟踪结果, 并更新分块的表观模型以精确指导后续帧的跟踪处理。

3.1 建立目标分块的表观模型

建立目标分块表观模型，首先根据懒交互方式选择目标的散乱不规则分块，然后运用核相关滤波建立分块表观模型。

(i) 基于懒交互的目标散乱不规则分块选择。首先，在视频第一帧的目标区域周围，采用懒交互方式选择N个散乱布局的分块(如：N=25)，要求这些分块能够覆盖目标具有典型特征的主要区域，因此分块常是无规则散乱分布且具有不同的尺寸。其次，计算每个分块中心与目标中心的中心偏移值，并据此对每个分块进行正负样本的判定。如图2所示，黄色矩形区域为目标区域，橙色区域为基于目标区域的扩展区域，当所取分块的中心位置处于黄色框架内时为正样本，处于橙色框架与黄色框架之间时为负样本。

图2 散乱不规则目标分块的采集和划分Fig.2 Collection and division of scattered and irregular targets

(ii) 基于核相关滤波的分块表观模型。采集目标分块后，运用核相关滤波初始化每个分块。其中，核相关滤波根据分块的表观信息如颜色、梯度等，通过求解岭回归训练目标检测器，它成功地利用了循环矩阵在傅里叶空间可对角化的特性，将矩阵的运算转化为向量的点乘，从而提高了计算效率。本文运用核相关滤波得到每个分块的特征矩阵X和用于区分目标与背景的分类器矩阵α。

结合上述内容，即可得到每个分块的表观模型。该分块表观模型共包括分块的4部分即：特征矩阵X，分类器矩阵α、中心偏移、正负样本标记。

3.2 基于核相关滤波的分块跟踪

(1)

该矩阵中，响应值越大说明分块中心位于此点的概率越大。核相关滤波最大的特点是跟踪速度快，因此虽然本算法需要对每帧图像中的多个分块进行跟踪，故此能够在最大程度上保证算法的跟踪速度。其中，目标预测区域是根据前一帧目标中心和尺寸得到的。

3.3 基于最优分块的目标跟踪

因本文根据所有散乱不规则分块实现目标跟踪，故需对每个分块进行有效性判定。首先根据分块目标概率值对每个分块进行最优判定(概率值越大，说明离目标中心位置越近)；然后对分块进行异常判定并对异常分块采用懒交互方式进行重采样；最后根据每个分块的位置和其作为目标中心的概率值，采用霍夫投票算法计算跟踪目标在新一帧的位置。通过将每个分块作为目标中心概率值作为权值，并对异常分块进行及时的重采样操作，保证每个分块的有效性来确保整体跟踪效果的准确性。

3.3.1 最优分块的判定 判定一个分块是否为最优分块的依据是分块在当前帧置信度值和分块在当前帧目标区域上的概率值。结合二者，计算每个分块在当前帧上作为最优分块的概率值。如下式所示：

pzt|xt=ptzt|xtp0zt|xt

(2)

其中，zt表示当前帧(第t帧)，xt表示第t个分块。所以，p(zt|xt)表示第t个分块在当前帧的作为最优分块的概率值，pt(zt|xt)表示第t个分块在当前帧可跟踪的置信度值，它将根据公式(3)计算。po(zt|xt)表示第t个分块在当前帧跟踪目标上的概率值，它将根据公式(5)计算。具体而言，最优分块的确定根据如下3步实现：

(i) 计算分块的置信度值。置信度值是基于核相关滤波所得的响应值来计算的。再引入了峰值-旁瓣比来作为衡量分块的置信度值标准。峰值-旁瓣比计算公式：

(3)

其中，R(X)是搜索区域上的响应值矩阵，Φ是在响应峰值的周围区域。μΦ和σΦ分别是响应值矩阵中除了Φ区域的平均值和标准差值。基于con(Xi)的结果，分块的置信度值设置为pt(zt|xt)=con(Xt)2。

(ii) 计算每个分块在目标区域内的概率值。由于在分块跟踪的过程中，搜索范围包含了背景信息，因此计算过程中需要参考背景的因素，通过对前、背景进行区分可提高整体算法的鲁棒性。本文通过当前分块与分块在上一帧的距离，并借助正样本和负样本的分布信息来来计算新块在目标对象上的概率值。计算公式：

(4)

其中，yt∈{+1,-1}表示当前块是正样本还是负样本。Ω+，Ω-分别表示正负样本的集合，N+表示正样本数量，N-表示负样本数量。基于l(X)，可以计算出这个分块在目标对象上的概率值，计算公式为：

po(zt|xt)=el(Xt)

(5)

(iii) 根据公式(2)，则可得每个分块作为最优分块中心的概率值。概率值越大，离目标中心位置的概率越大。

3.3.2 异常分块的判定及处理 在跟踪过程中随着跟踪目标及背景的变化，不可避免出现分块跟踪异常的现象，故需对每个分块进行异常判定并对异常分块进行重采。分块异常判断依据具体如下：

(i) 判断分块是否远离目标。当分块已经超出了目标以及背景的范围，则需要删除这个分块，因为这个分块已经不能代表目标或者周围背景的局部区域。

(ii) 判断正负样本比例是否失衡：在初始化分块时是在扩展区域内随机选择分块的，正负样本的数量也为随机产生。当正样本数量过多时，容易出现过拟合现象；当负样本过多时，则容易跟踪目标丢失。因此，维持正负样本的比例可保持跟踪算法的稳定性。所以，当分块的正样本(目标)数或者负样本(背景)数大于某一阈值之后(如：阈值为5)，则需要删除掉正样本或者负样本中置信度较小的一些块。

(iii) 所跟踪分块的置信度值是否太低。根据式(1)我们得到每个分块的响应值矩阵，并运用式(3)和公式pi(zt|xt)=con(Xt)2，得到每个分块的置信度值。当这个分块的置信度值过小，则说明与原分块的相似度较低，应该视为异常分块，应删掉此分块。

通过删除异常分块，可防止跟踪漂移现象出现；并通过对异常分块的及时重采样，提高整体算法的鲁棒性。而未被删除的分块，在新一帧图像上建立新表观模型并与旧表观模型进行线性组合，得到最后在新一帧上的表观模型。

3.3.3 异常分块的重采样 由于本文采用懒交互方式对异常分块进行重采样，需在保证跟踪准确性的同时最大程度上不影响跟踪速度，故此对异常分块设定一个重采样判定阈值m。当异常分块的数量大于等于m时，则对异常分块进行重采。当阈值设定过高时，不能对异常分块进行及时的重采样操作，容易出现跟踪漂移现象；当阈值设定过低时，容易导致重采样次数增加，从而影响跟踪的实时性。在本文设置m=5，在保证跟踪准确性的同时，保证其实时性。其过程如图3所示，其中(a)为在进行懒交互式散乱不规则块采集之后目标的跟踪效果；(b)出现分块漂移现象(左上角红色框)；(c)为进行懒交互式重采样过程；(d)为进行懒交互式重采样之后目标分跟踪效果。

图3 懒交互式重采样过程(黄色框为目标区域)Fig.3 The process of lazy interaction resampling (yellow box for object area)

3.3.4 基于霍夫投票投票的目标跟踪结果计算 在异常分块处理之后，我们得到了所有的散乱不规则分块，并依据所以分块采用霍夫投票算法计算跟踪目标在新一帧上的最终位置。将最优分块中心的概率值作为每一个分块的权重，并与对应的分块位置进行加权求和，得到跟踪目标在新一帧上的最终位置，具体计算如式(5)所示。图4为霍夫投票示意图。

图4 霍夫投票Fig.4 Hough-voting

将最优分块中心的概率值pi(zt|xt)作为每一个分块的权重，并根据式(6)加权计算出跟踪目标中心位置结果。

(6)

其中postar表示跟踪目标在新一帧上的最终位置，posi表示第i分块的位置，pi(zt|xt)表示第i个分块作为跟踪目标中心位置的概率值。

3.4 表观模型的更新

表观模型的更新分为2种情况：对异常块的更新和对非异常块的更新。

(i) 异常分块表观模型的更新。异常分块都是先删除，然后再对其进行重采样操作。需要对每个新采样的分块利用核相关滤波进行初始化，即对新采样分块建立初始表观模型。

(ii) 非异常分块表观模型的更新。线性组合每个分块的新表观模型和旧表观模型，实现目标分块表观模型的更新。首先，利用核相关滤波和分块的新跟踪结果，计算其新表观模型；然后将该模型与其旧表观模型进行线性组合，具体而言是将描述表观模型的特征矩阵进行组合，最终得到每个分块更新后的表观模型。同时，更新分块与目标中心的偏移值以更新目标的结构信息。

4 实验结果及分析

本文在普通PC机(Windows 7系统，Intel i5-4460CPU,3.20 GHz，4 G内存)上基于MATLAB 2012A实现本文算法。采用Visual tracking benchmark平台的27组视频序列进行实验，它们包含多种挑战如旋转、快速移动、背景复杂、光照变化等。为验证本算法的优越性，将其与当前主流的5种方法(含KCF[2]、RPT[16]、SCM[29]、Struck[30]、VTD[31])进行对比。结果表明本文方法对平面旋转、外平面旋转、背景复杂、光照变化比较有效。

4.1 跟踪结果定量分析

本文依据中心位置误差精度图和每一帧跟踪区域与目标标准区域的覆盖成功率图对目标跟踪进行定量分析。其中精准度通过跟踪结果区域和理想目标区域的中心距离计算，而成功率则根据两者的重叠率计算[32]。如图5所示，与其它5种目标跟踪方法相比，本文方法在中心距离误差精度图和覆盖成功率分别以0.785和0.658排在第1。而在光照变化、内平面旋转、复杂背景和外平面旋转(表1和表2)这4种情况下，分别以0.783和0.618、0.779和0.628、0.759和0.624、0.774和0.615排在首位。

图5 综合情况Fig.5 The total situation

表1 跟踪精确度(红色为第1，绿色为第2、蓝色为第3)Tabel 1 Precision plots of OPE(Red is the first, green is second and blue is third)

表2 平均成功率Tabel 2 Success plots of OPE

4.2 目标跟踪结果定性分析

本节主要针对内平面旋转、外平面旋转、背景复杂、光照变化挑战来分析本文方法的有效性，并与现有方法进行对比分析。

4.2.1 内平面旋转 图5展示了内平面旋转挑战中两个例子(football1，dudek)跟踪效果。由于本文方法通过多个分块表示跟踪目标且在重采样时采用懒交互方式，故当目标在旋转过程中，通过对每个分块进行跟踪以达到对目标的跟踪效果。当出现异常分块时，通过懒交互方式可以保证重采样分块的有效性，从而确定跟踪的有效性。如在football1视频(第55帧，第67帧)或者dudek视频(第761帧)中，目标在剧烈运动且背景复杂中出现旋转现象，本算法依然能够正确跟踪目标，而其它算法如RPT算法，在重采样分块过程中在置信度值最高分块附近进行异常分块重采样，当置信度值最高的分块已发生漂移现象时，则重采样分块也容易出现漂移现象，故容易导致跟踪失败。

图6 内平面旋转跟踪结果(第一行为：football1序列；第二行为dudek序列)Fig.6 The result of in-plane rotation (First line: football; Second line: dudek)

4.2.2 外平面旋转 图7展示了外平面旋转挑战中两个例子(basketball，david3)跟踪效果。对比分析可知，本文算法通过对每个分块进行建模跟踪，通过每个分块的局部信息来表达整体，当部分分块丢失时可通过其它分块来达到跟踪目标的目的，从而提高整体算法的鲁棒性。在basketball视频(109帧)中，SCM、TLD和KCF算法都是通过整体跟踪，故在目标旋转且剧烈运动情况下跟踪失败。在david3视频(54帧，118帧)中，目标在运动中经过电线杆或者树时被完全遮挡，KCF、Struck和SCM算法采用整体跟踪，故而导致失败。

4.2.3 背景复杂 图8展示了背景复杂挑战中两个例子(carDark, singer2)跟踪效果。carDark视频中，在目标运动路线上背景复杂且出现光照变化情况。第222帧左右，目标运动路线出现变化。第263帧，如RPT算法虽然基于局部分块进行跟踪，但由于分块比较规则，容易融入背景信息，导致出现跟踪漂移现象；而TLD算法等背景环境复杂，且采用整体跟踪导致跟踪失败。本文算法在跟踪过程中，出现跟踪分块丢失情况，但通过其余分块调整且通过懒交互方式及时重采样，从而保证后续跟踪的准确性。

4.2.4 光照变化 图9展示了光照变化挑战中两个例子(david，singer1)跟踪效果。在david视频中，目标由光照比较暗的地方走到光照比较亮的地方(第387-444帧)，本文算法跟踪效果很稳定。在singer1视频中(第195帧、第286帧)，光照变化很频繁，本文通过对散乱不规则分块跟踪性且通过懒交互重采样方式，最大程度保证分块有效性，在后续模版更新及跟踪时，可维持算法的鲁棒性。

图7 外平面旋转跟踪结果(第一行为：basketball序列；第二行为david3序列)Fig.7 The result of out-of-plane rotation (First line: basketball; Second line: david3)

图8 背景复杂跟踪结果第一行为：carDark序列；第二行为singer2序列)Fig.8 The result of background clutters (First line: carDark; Second line: singer2)

图9 光照变化跟踪结果(第一行为：david序列；第二行为singer1序列)Fig.9 The result of illumination variation (First line: david; Second line:singer1)

4.3 实时性分析

如表3所示，列举了本文算法与其它四种算法的平均速度对比数据。由表中可知，本文算法的运行速度为7.8 Fps，远小于KCF算法(195.1 Fps)，但大于同样通过对目标分块跟踪以达到对目标整体跟踪的RPT算法(3.59 Fps)。

表3 运行平均速度对比Tabel 3 Running average speed contrast

5 结 语

本文针对在视频跟踪过程中出现背景复杂、光照变化等挑战展开研究，提出了一种懒交互模式下散乱不规则分块引导的目标跟踪方法。该方法首先将跟踪目标区域通过懒交互方式划分为N个散乱不规则分块，然后分别对N个分块进行初始化建模，并引入核相关滤波算法提高跟踪效率。针对异常分块，本文提出一种懒交互方式方法对异常分块进行重采。最后采用霍夫投票算法确定跟踪目标在新一帧上的最终位置。通过在benchmark上对大量视频序列进行跟踪的结果表明：与现有主流跟踪算法相比，本算法对多种挑战(如背景复杂、光照变化、旋转等)情况下，本方法的跟踪结果具有更高的精度。