基于局部分块和模型更新的视觉跟踪算法

侯志强 黄安奇余旺盛 刘 翔

(空军工程大学信息与导航学院 西安 710077)

基于局部分块和模型更新的视觉跟踪算法

侯志强 黄安奇*余旺盛 刘 翔

(空军工程大学信息与导航学院 西安 710077)

针对目标跟踪过程中的目标表观变化、背景干扰及发生遮挡等问题，该文提出一种基于局部分块和模型更新的视觉跟踪算法。该文采用粗搜索与精搜索相结合的双层搜索方法来提高目标的定位精度。首先，在包含部分背景区域的初始跟踪区域内构建目标模型。然后，利用基于积分直方图的局部穷搜索算法初步确定目标的位置，接着在当前跟踪区域内通过分块学习来精确搜索目标的最终位置。最后，利用创建的模型更新域对目标模型进行更新。该文主要针对分块跟踪中的背景抑制、模型更新等方面进行了研究，实验结果表明该算法对目标表观变化、背景干扰及遮挡情况的处理能力都有所增强。

视觉跟踪；局部分块模型；穷搜索；局部分块学习；模型更新

1 引言

视觉跟踪作为计算机视觉领域中最困难和最为核心的问题之一，近年来一直是国内外研究的热点[1−4]。目标在运动过程中外观的不断变化、背景元素的干扰以及遮挡情况的处理等问题是视觉跟踪的研究难点。如何构建能够适应外观变化和复杂环境的目标模型并进行及时有效的更新是解决问题的关键。经典的均值迁移(mean shift)算法[5,6]利用区域颜色直方图表示目标模型，对简单场景下的运动目标可以实现准确有效的跟踪，但是对光照变化和遮挡情况都比较敏感。文献[7]使用多示例学习(Multiple Instance Learning, MIL)来训练分类器，构造了一个更加鲁棒的判别式外观模型。近几年来，图像的稀疏表示使其能够用很少的数据捕获感兴趣目标的重要信息，其被引入到视觉跟踪中后，提高了算法对光照、姿态变化及遮挡情况的适应性[8]。基于局部分块模型的跟踪算法由于能检测出目标区域中发生遮挡或外观变化的相应分块而引起许多学者的关注。根据产生方式的不同，分块方法可以分为规则分块和不规则分块两大类。其中，规则分块以文献[9]提出的基于分块的跟踪(Fragments-based Tracking, Frag)最具代表性。另外，文献[10]提出一种基于直方图和关节式分块的跟踪算法(Tracking with Histograms and articulating Blocks, BHT)，该算法针对非刚体目标提出一种基于动态分块的目标模型，增强了算法对非刚性形变的适应性。文献[11]提出一种自适应的分块方法，并利用尺度不变特征变换(Scale Invariant Feature Transform, SIFT)解决目标的尺度变化问题。不规则分块以文献[12]和文献[13]提出的超像素跟踪(SuperPixel Tracking, SPT)最具代表性，超像素具有较为明确的语义信息，因此能较好地建立具有结构信息的目标模型，提高了跟踪算法的鲁棒性。

本文使用的分块方法为规则分块，而当前基于规则分块模型的跟踪算法主要存在以下几个问题：(1)分块方式。不考虑子块之间差异的简单均匀分块，容易造成跟踪漂移。(2)背景抑制。现有的规则分块跟踪算法对复杂背景变化的适应性较差。(3)模型更新。在长时间的跟踪过程中，目标和背景都会发生较大的变化。如果不考虑模型更新，跟踪结果会逐渐偏离正确位置，因此，更新目标模型以适应目标和背景的变化，是提高视觉跟踪算法鲁棒性必须要考虑的问题[14]。针对以上规则分块模型存在的问题，本文受超像素跟踪[12]的启发，采用聚类分析的方法来抑制背景干扰，并通过创建模型更新域，将跟踪结果合理地组织起来，从而实现对目标模型的有效更新。需要说明的是，本文虽然同样涉及聚类分析，但是在分块方法、模型构建、模型更新以及跟踪框架上都与超像素跟踪方法有很大不同。本文主要针对分块跟踪中的模型构建、模型更新和背景抑制等问题进行了研究，提出了一种基于局部分块和模型更新的视觉跟踪算法。实验结果表明，本文算法与同类算法相比具有较强的鲁棒性。

2 分块模型的构建

本文在描述目标时，采用了两种方式：一种为生成式模型，用于目标的初步搜索；另一种为判别式模型，用于目标的精确定位。本文采用HSI颜色空间的10×10×5归一化直方图对目标的颜色特征进行描述。

2.1 生成式模型的构建

用来构建目标生成式模型的目标区域，即目标模板，通过在第1帧图像中手动标定得到，如图1红框内的图像区域。目标模板用于对目标的初步搜索，并根据搜索结果来确定当前跟踪区域。目标模板的颜色直方图可以表示为

式中，r为颜色直方图的维数。

2.2 判别式模型的构建

文献[9]提出的分块跟踪在进行分块建模时，沿水平和垂直方向将目标区域分成9×2和2×9的分块集合，如图2所示。分块模型由于在一定程度上考虑了目标的空间结构信息，因此具有较为突出的抗遮挡能力。在初始帧选定目标区域时，往往会包含部分背景信息，这些信息会对目标定位的精度造成不利影响。本文对目标区域及周围的背景区域共同分块，通过聚类算法将特征相似的子块聚到同一类中，从而有效地突出目标特征并抑制背景特征。本文构建目标判别式模型的思路为：

(1)将整个初始跟踪区域分为n2个子块。设定其中的背景区域大小为目标区域的3倍，如图1所示。将目标区域内像素的置信值(属于目标前景的概率)赋为1，背景区域内像素的置信值赋为-1，像素的置信值记为p(i,j)。每个分块的初始置信值(k=1,2,…,n2)为分块内所有像素置信值的平均值。

(2)提取各个分块的颜色特征，并用颜色直方图对其进行描述，构建特征空间：

式中，fk为第k个子块的特征向量，2n为子块的个数。

(3)在特征空间内对分块进行聚类，并根据聚类结果计算出聚类成员属于目标前景的概率。由于均值迁移聚类方法更加注重数据对象间的类似度和分布情况，因此选择均值迁移聚类方法对分块特征进行聚类，得到N个不同的聚类clu(m)(m=1,2,…,N)，并且每个聚类包含Nf个特征向量{fk|fk∈clu(m)}。聚类完成后，特征相似的分块被聚到同一类内，类的置信值为类内所属分块初始置信值的均值

图1 本文算法目标分块示意图

图2 文献[9]分块方法

式中，clum为包含分块特征的聚类结果。图3所示为目标模型构建的示意图。

3 本文跟踪算法

为了提高算法的跟踪精度，本文采用粗搜索与精搜索相结合的双层搜索方法来实现目标的定位。当输入新的一帧图像时，首先利用基于积分直方图的穷搜索算法对目标进行快速定位并确定当前跟踪区域；然后对当前跟踪区域进行局部分块，分别计算每个分块到模型中各类的特征距离，并依据最近邻准则将模型中聚类的置信值赋给各个分块；最后根据分块置信值总和最大准则确定目标的最终位置。

3.1 基于积分直方图的目标穷搜索

本文在目标初步定位时采用局部穷搜索算法来获取最优结果。穷搜索算法需要搜索区域内反复计算矩形区域的直方图，实时性较差。而文献[15]提出的积分直方图方法实现了快速穷搜索，能保证在获得全局最优解的前提下实现快速甚至是实时的跟踪。本文在进行局部穷搜索时，首先确定目标在当前帧的搜索区域，将搜索范围设定为以上一帧跟踪结果为中心的4倍于目标尺寸的范围。然后利用目标生成式模型在搜索区域内进行快速穷搜索，得到目标的初始位置(x',y')。

3.2 基于分块学习的目标穷搜索

在传统的分块跟踪算法中，首先利用快速穷搜索方法得到各个分块的位置，然后对分块的位置进行加权融合得到目标的最终位置。虽然在对各个分块进行加权时，考虑了分块与中心位置的空间距离，但是仍然不能很好地抑制背景元素的干扰。因此，本文根据在第1帧建立的判别式分块模型，采用局部分块学习的方法来有效地抑制背景干扰。

以目标的初始位置为中心确定目标在当前帧的跟踪区域，由于穷搜索得到的初始位置已经较为准确，因此适当缩小当前跟踪区域的范围以减少计算量，此处设定为以初始位置为中心的2倍于目标尺寸的范围。基于分块学习的跟踪可以分为以下几个步骤：

步骤1 局部分块。输入新的一帧图像后，在当前跟踪区域内进行局部分块，并进行特征描述。

步骤2 计算置信图。首先计算当前帧每个分块到目标模型中各类的特征距离，使用巴氏系数进行相似度度量，相似度最大则距离最小。然后将距离最小类的置信值赋给该分块，分块内像素的置信值与分块相同。

步骤3 目标搜索。根据得到的目标置信图，在当前跟踪区域内，针对任意一个目标候选区域，都可以计算得到对应的目标置信值。

式中，(x,y)为目标候选区域的中心坐标，λ为归一化系数，p(i,j)为候选区域内任意一点的置信值。由于目标前景像素的置信值范围为(0,1]，而背景像素的置信值范围为[−1,0)，因此跟踪框所覆盖像素置信值的总和越大，所覆盖区域属于目标的概率就越大。

图3 目标模型构建示意图

然而式(5)中计算得到的目标置信值并没有考虑目标的尺度变化，为了增强算法对目标尺度变化的鲁棒性，在式(5)中加入尺度调节系数为

当目标置信值达到最大时，所对应的坐标就是目标最终的中心位置

本文在基于分块学习的目标搜索过程中，同样利用了积分图技术，首先在整张置信图中根据式(6)构建积分数据结构，然后通过快速穷搜索来实现目标的最终定位。

3.3 基于遮挡判断的模型更新

模型更新需要解决两个问题：一个是模型更新时机，即什么时候更新模型；另一个是新模型的选择，即用什么模型更换旧模型。针对模型更新时机问题，需要重点解决的是遮挡判断问题，目标被遮挡时不能将遮挡物的信息更新到目标模型内。针对模型选择问题，本文通过建立一个模型更新域，将L帧图像的跟踪结果合理地组织起来，发掘出被跟踪目标的本质信息，从而更好地解决模型更新问题。

首先根据提出的局部分块模型，计算得到遮挡判断因子θt并设定遮挡判断阈值θ0。当θt＜θ0时，每隔U帧对模型更新域进行更新，每隔W帧对目标模型进行更新；当θt＞θ0时，对模型更新域和目标模型都停止更新，从而防止引入遮挡物的信息，避免发生跟踪漂移。同时为了减少由于遮挡造成的跟踪偏差，在判断遮挡发生后用上一帧的跟踪结果来代替当前帧的跟踪结果。遮挡因子定义为

式中，uV为模型更新域内所有目标归一化置信值的平均值，根据式(5)计算得到。

模型更新域的建立与更新：将跟踪过程中得到的L帧跟踪结果，包括当前帧跟踪区域的分块结果及目标的最大置信值Vk，存入更新域中并按照置信值大小进行排序。在未发生遮挡的情况下，每隔U帧将当前帧的跟踪结果存入更新域，并删除置信值最小的一帧跟踪结果，从而保证更新域既是最新的又是最优的。

目标模型的更新：由于本文算法在对目标进行定位时，采用了分步跟踪的方法，对目标的描述也采取了两种方式。因此，在未发生遮挡的情况下，每隔W帧对两种形式的目标模型都要进行更新。

(1)生成式模型的更新。对更新域中目标置信值最大的跟踪结果和初始跟踪区域中的目标模板进行线性加权来更新目标生成式模型。

(2)判别式分块模型的更新。首先选择更新域中前L/2帧目标置信值较大的跟踪结果，对选择的所有分块进行聚类分析，重新对类和分块进行标记，从而实现模型的更新。

本文跟踪算法的流程图如图4所示，灰色区域为算法的模型更新过程。

4 实验结果与分析

图4 本文跟踪算法流程图

实验中，本文算法的参数设置为：分块数目n2=144，均值迁移聚类的带宽B=0.2，遮挡判断阈值θ0=0.48，模型更新参数L=6, U=1, W=6。上述参数在所有实验中的设置是一样的。本文算法的仿真环境为：Intel G1610 CPU, 2G内存，Windows XP系统，MATLAB 7.12.0。

为了验证本文算法在处理遮挡、背景干扰及光照变化等情况的有效性，在6组具有挑战性的视频序列上进行了对比测试，各组序列的跟踪难点如表1所示，视频序列及目标真实位置全部来自文献[2]。本文算法采用分块模型并且涉及模型的在线更新，因此有针对性地选择以下4种参考算法：Frag[9], BHT[10], MIL[7]和SPT[12]。Frag算法和MIL算法的代码来自文献[2]，BHT算法的代码来自文献[10], SPT算法的代码来自文献[13]发布的最新版本。为了保证实验对比的公平性，本文对每个算法的参数都进行了仔细调整，或是直接采用算法设定好的参数，比如SPT算法在测试序列Lemming, Bolt和Basketball时的参数，并从5组测试结果中选择最优的一组用来实验对比。

4.1 定性对比

(1)Faceocc1序列 如图5(a)所示，Frag算法、BHT算法、SPT算法和本文算法都采用了分块模型，因此能够有效地处理遮挡情况。MIL算法不能适应遮挡情况，跟踪误差较大。

图5 跟踪算法性能的定性比较

表1 测试视频序列说明

(2) Lemming序列 如图5(b)所示：Frag算法和BHT算法由于不能有效地抑制背景干扰，跟踪误差较大，最终丢失了目标。SPT算法刚开始可以较好地跟踪目标，但是随着跟踪的进行，在模型更新过程中引入了过多的误差，最终导致目标丢失(从第902帧开始)。MIL算法和本文算法都可以较好地跟踪上目标，但本文算法在处理目标旋转上更有优势，如第998帧。

(3)Bolt序列 如图5(c)所示：Frag算法和MIL算法跟踪误差较大，最终都丢失了目标。BHT算法由于其在处理非刚性形变上的优势，跟踪误差较小。SPT算法和本文算法通过聚类分析能够很好地突出前景目标，抑制背景干扰，从而增强了对非刚性形变的适应性。

(4)Basketball序列 如图5(d)所示：Frag算法虽然成功完成了跟踪，但是跟踪误差较大。BHT算法和MIL算法开始时可以较为准确地跟踪目标，但是后面都出现了丢失目标的情况。SPT算法的跟踪误差最小。本文算法对遮挡和背景干扰都有一定的鲁棒性，跟踪误差也比较小。

(5)David序列 如图5(e)所示：Frag算法和BHT算法由于都不具有有效的模型更新机制，跟踪误差较大。SPT算法在更新模型的过程中引入了一定的背景元素，跟踪误差较大。MIL算法能够对构建的判别式外观模型进行有效地在线更新，跟踪误差较小。本文算法在更新模型的过程中，通过合理地选择特征信息，有效地抑制了背景干扰，取得了较好的跟踪结果。

(6)Trellis序列 如图5(f)所示：Frag算法和BHT算法显然不能适应这种复杂场景，跟踪误差较大。MIL虽然对光照变化具有一定的鲁棒性，但是不能够有效地抑制背景干扰，导致跟踪算法失效。SPT算法和本文算法能够在更新模型的同时有效地抑制背景元素的干扰，取得了较为准确的跟踪结果。

4.2 定量分析

为了定量地评价跟踪算法的性能，本文采用中心位置误差(Center Location Error, CLE)来对以上4种算法的跟踪结果进行比较。CLE用来衡量算法的跟踪精度，第k帧CLE的计算公式为

式中，(xk,yk)为第k帧跟踪结果中目标中心位置的坐标，(,)为对应帧目标真实位置的中心坐标。CLE的单位为像素，数值越小，表明算法的跟踪精度越高。

图6所示为各个算法在跟踪视频序列时的中心位置误差，由CLE曲线可见：Frag算法在Faceocc1序列和Basketball序列上的跟踪误差较小，而在其他几段序列上的跟踪误差都比较大。BHT算法在Bolt序列上的跟踪结果较为准确，而在其他序列上的跟踪误差都比较大。MIL算法在Lemming序列和David序列中具有较小的跟踪误差。除了Lemming序列，SPT算法在其余几段序列上都取得了较为理想的跟踪结果。本文算法在构建目标模型时采取分块的方式，有效地利用了目标的空间信息，增强了对遮挡情况的适应性；在构建目标的判别式外观模型时，通过聚类的方法有效地突出了前景目标，增强了算法抑制背景干扰的能力；在进行模型更新时，通过构建模型更新域，既保留了目标可靠的历史信息，又不断学习目标新的特征，利用聚类算法使得在更新模型的同时有效地抑制了背景干扰。相对而言，本文算法在所有测试序列上得到的CLE都比较小，验证了本文算法的优势。

表2给出了各个算法的平均中心误差。由表中数据可知：本文算法在Lemming序列、Bolt序列和David序列上取得了最优结果，在其余序列上取得了次优结果。SPT算法也取得了较好的跟踪结果，在Basketball序列和Trellis序列上取得了最优结果。

4.3 与SPT算法的对比分析

SPT算法有效地利用了目标的中层视觉特征，增强了算法对遮挡及表观变化的适应性。但是SPT算法依然存在一些问题，首先SPT算法需要建立在上一帧具有一定的跟踪精度且目标运动在空间上连续的基础上，否则容易引入跟踪误差。虽然SPT算法具有一定的从跟踪漂移中恢复的能力，但是需要被引入的特征在背景中大量存在，才能通过聚类分析将跟踪框中引入的错误信息聚类到背景中。其次，SPT算法通过一个简单的滑动窗口来利用存储的所有特征信息对模型进行更新，同样容易带来跟踪偏差，如图5(b)所示。

图6 中心位置误差比较

表2 目标中心位置平均误差比较

本文算法通过局部穷搜索来确定目标的初始位置，保证了用于分块提取的当前跟踪区域的正确性。并且本文算法通过构建模型更新域，选择其中可靠的特征信息用于更新，从而防止在更新过程中引入跟踪误差。实验证明，本文算法取得了与SPT算法相近或是更好的跟踪结果。本文算法在分块提取和置信图计算上的复杂度也比较低，并在快速穷搜索的框架下进行实现，实时性较好。

5 结束语

针对现有分块跟踪算法存在的问题，本文提出了一种基于局部分块和模型更新的视觉跟踪算法。算法通过聚类分析，构建了一种能够有效突出前景特征并抑制模型漂移的判别式分块模型。在所构建的模型基础上，首先利用基于积分直方图的快速穷搜索算法初步确定目标的位置，然后通过分块学习，得到的目标最大置信值对应的位置即为目标的最终位置。算法在构建模型更新域的基础上还提出了一种基于遮挡判断的模型更新方法，能够在对模型进行更新的同时有效地抑制背景元素。实验结果表明，本文算法能够较好地处理遮挡、背景干扰和目标表观变化等情况，得到了更为准确的跟踪结果。本文算法只采用了简单的HSI颜色特征，下一步工作将考虑融合多种特征对目标进行描述，进一步提高算法的有效性和鲁棒性。

[1] Yang Han-xuan, Shao Ling, Zheng Feng, et al.. Recent advances and trends in visual tracking: a review[J]. Neurocomputing, 2011, 74(18): 3823-3831.

[2] Wu Yi, Lim J, and Yang M H. Online object tracking: a benchmark[C]. Proceedings of the Computer Vision and Pattern Recognition, Portland, United States, 2013: 2411-2418.

[3] Smeulders A W M, Chu D M, Cucchiara R, et al.. Visual tracking: an experimental survey[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013: DOI: 10. 1109/TPAMI. 2013. 230.

[4] Lu Zhang and Laurens V D M. Structure preserving object tracking[C]. Proceedings of the Computer Vision and Pattern Recognition, Portland, United States, 2013: 1838-1845.

[5] Comaniciu D, Ramesh V, and Meer P. Real-time tracking of non-rigid objects using mean shift[C]. Proceedings of the Computer Vision and Pattern Recognition, Hilton Head Island, United States, 2000: 142-149.

[6] Comaniciu D, Ramesh V, and Meer P. Kernel-based objecttracking[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, 25(5): 564-577.

[7] Babenko B, Yang M H, and Belongie S. Robust object tracking with online multiple instance learning[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(8): 1619-1632.

[8] Wang Dong, Lu Hu-chuan, and Yang M H. Online object tracking with sparse prototypes[J]. IEEE Transactions on Image Processing, 2013, 22(1): 314-315.

[9] Adam A, Rivlin E, and Shimshoni I. Robust fragments-based tracking using the integral histogram[C]. Proceedings of the Computer Vision and Pattern Recognition, New York, United States, 2006: 798-805.

[10] Nejhum S, Ho J, and Yang M H. Online visual tracking with histograms and articulating blocks[J]. Computer Vision and Image Understanding, 2010, 114(8): 901-914.

[11] 董文会, 常发亮, 李天平. 融合颜色直方图及SIFT特征的自适应分块目标跟踪方法[J]. 电子与信息学报, 2013, 35(4): 770-776. Dong Wen-hui, Chang Fa-liang, and Li Tian-ping. Adaptive fragments-based target tracking method fusing color histogram and SIFT features[J]. Journal of Electronics & Information Technology, 2013, 35(4): 770-776.

[12] Wang Shu, Lu Hu-chuan, Yang Fan, et al.. Superpixel tracking[C]. Proceedings of the IEEE International Conference on Computer Vision, Barcelona, Spain, 2011: 1323-1330.

[13] Yang Fan, Lu Hu-chuan, and Yang M H. Robust superpixel tracking[J]. IEEE Transactions on Image Processing, 2014, 23(4): 1639-1651.

[14] Matthews I, Ishikawa T, and Baker S. The template update problem[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(6): 810-815.

[15] Porkili F. Integral histogram: a fast way to extract histograms in cartesian spaces[C]. Proceedings of the Computer Vision and Pattern Recognition, San Diego, United States, 2005: 829-836.

侯志强： 男，1973年生，博士，教授，研究方向为图像处理、计算机视觉和信息融合.

黄安奇： 男，1988年生，硕士生，研究方向为视觉跟踪.

余旺盛： 男，1985年生，博士生，研究方向为图像分割、视觉跟踪.

Visual Object Tracking Method Based on Local Patch Model and Model Update

Hou Zhi-qiang Huang An-qi Yu Wang-sheng Liu Xiang
(The Information and Navigation Institute, Air Force Engineering University, Xi'an 710077, China)

In order to solve the problems of appearance change, background distraction and occlusion in the object tracking, an efficient algorithm for visual tracking based on the local patch model and model update is proposed. This paper combines rough-search and precise-search to enhance the tracking precision. Firstly, it constructs the local patch model according to the initialized tracking area which includes some background areas. Secondly, the target is preliminarily located through the local exhaustive search algorithm based on the integral histogram, then the final position of the target is calculated through the local patches learning. Finally, the local patch model is updated with the retained sequence during the tracking process. This paper mainly studies the search strategy, background restraining and model update, and the experimental results show that the proposed method obtains a distinct improvement in coping with appearance change, background distraction and occlusion.

Visual tracking; Local patch model; Exhaustive search; Local patches learning; Model update

TP391.4

： A

：1009-5896(2015)06-1357-08

10.11999/JEIT141134

2014-09-01收到，2014-11-02改回

国家自然科学基金(61175029, 61473309)和陕西省自然科学基金(2011JM8015)资助课题

*通信作者：黄安奇 13319270512@163.com