基于多示例学习的目标跟踪算法

李 娜， 李大湘， 刘卫华， 刘 颖

(1. 西安邮电大学 通信与信息工程学院， 陕西 西安 710121；2. 长安大学 信息工程学院, 陕西 西安 710064；3. 陕西省法庭科学电子信息实验研究中心 图像处理实验室， 陕西 西安 710121)

基于多示例学习的目标跟踪算法

李 娜1,2,3， 李大湘1,3， 刘卫华1,3， 刘 颖1,3

(1. 西安邮电大学 通信与信息工程学院， 陕西 西安 710121；2. 长安大学 信息工程学院, 陕西 西安 710064；3. 陕西省法庭科学电子信息实验研究中心 图像处理实验室， 陕西 西安 710121)

为提高运动目标跟踪算法的鲁棒性，提出一种基于多示例学习(MIL)框架的跟踪算法。该算法利用类Haar特征构建若干弱分类器，然后级联为多示例学习强分类器，根据目标在视频前一帧中的位置，依据最大熵原理，在当前帧中找出目标可能出现的范围，并利用该强分类器确定其最有可能出现的位置，作为跟踪结果，并且将该位置不同邻域内的图像分别作为正包和负包去更新多示例学习强分类器。实验结果表明，该算法对于运动目标外观有显著变化的情况具有较好的鲁棒性和实时性。

目标跟踪；多示例学习；弱分类器

目标跟踪是计算机视觉研究的热点，在视频监控、视频检索、交通监控等领域都有广泛应用，但现有的部分算法往往不能有效解决照明变化、外观变化、形状变化和遮挡对目标跟踪的影响[1-3]，因此，目标跟踪领域的新思想新算法仍然层出不穷。

文[4]提出了多示例学习(Multiple instance Learning, MIL)的概念。在MIL问题中，训练样本以包作为单位，包有确定标记，而包内示例标记则不确定。如果包被标记为负，则表明包中所有示例都为负示例，如果包被标记为正，则表明包中至少有一个正示例。

针对目标跟踪问题，将视频当前帧中的图像块与图像块的集合分别看作示例和包。将包含目标的图像集合标记为正包，否则标记为负包。利用正包和负包来训练分类器，并以此对下一帧图像中的目标位置进行预测和判断。文[5]将多示例学习用于目标检测中，提高了检测精度。文[6-8]研究了基于检测的跟踪方法，将多示例学习算法用于目标跟踪中，建立了鲁棒的目标外观模型。多示例学习问题中，示例选择的好坏直接影响到分类的结果，文[9]对多示例学习问题中如何选择示例进行了探讨。

本文拟在MIL框架下，提出一种基于多示例学习框架的跟踪算法。该算法利用类Haar特征构建若干弱分类器，然后级联为多示例学习强分类器。根据目标在视频前一帧中的位置，依据最大熵原理，在当前帧中找出目标可能出现的范围，由此确定其最有可能出现的位置，作为跟踪结果，并且将该位置不同邻域内的图像集合分别作为正包和负包去更新强分类器。

1 算法描述

1.1 基于多示例学习的目标跟踪

算法1(基于多示例学习的跟踪)

输入第t-1帧中目标所在位置坐标、视频第t帧;输出第t帧中目标所在位置坐标，更新后的MIL分类器。

步骤1 从第t帧中找到图像集合

其中，s为搜索半径，l(x)为图像块x的位置，用目标中心点坐标(x,y)表示,Xs中的任意图像块与t-1帧中目标位置的距离小于s。计算该图像集合中每个图像块x的特征向量。

步骤2 使用最新的MIL分类器，计算

即找出Xs中出现目标概率最大的图像块，并将它作为第t帧中目标所在位置。

将Xγ作为正包，Xγ,β作为负包，对MIL分类器进行更新。其中γ和β分别是正包、负包的选择半径。

在该跟踪算法中，最重要的就是如何得到MIL分类器以及如何对其进行更新。

1.2 在线MIL分类器

在线MIL分类器是由K个弱分类器级联而成的。目的是要从M个弱分类器

Φ={h1,h2,…,hM}

中依次选出K个弱分类器，使其满足

其中

(1-pi)(1-yi) log (1-pi)],

分别是包的信息熵函数和从Φ中选出的k-1个弱分类器构成的强分类器。

文[7]中L取值为包的对数似然函数

(1-yi) log (1-pi)]。

考虑到最大熵原理是从符合条件的分布中选择熵最大的分布作为最优秀的分布，符合应用背景，故可选择信息熵作为目标函数，通过求它的最大值，从而确定出最合适的弱分类器,因此，求在线MIL分类器的问题就转化为如何求包的概率pi以及如何得到弱分类器hj(j=1,2,…,M)。

在MIL中，记训练集为

{(X1,y1),(X2,y2),…,(Xn,yn)},

其中

Xi={Xi1,Xi2,…,xim}

代表第i个包，xij代表第i个包中的第j个示例，yi代表第i个包的标记(0代表负包，1代表正包)。包标记定义为

其中yij代表第i个包中的第j个示例的标记，在训练阶段示例标记是未知的。

根据文[5]，采用Noisy-OR(NOR)模型对包概率建模，即

但在求包标记时会用到示例标记P{yi|xij}，因此需要对示例标记建模，即

其中H(xij)是上文提到的由K个弱分类器级联的强分类器，其生成方法描述如下。

算法2(在线MIL分类器)

Xi={xi1,xi2,…,xim},yi∈{0,1};

输出分类器

步骤2 依次遍历M个弱分类器，用它和强分类器的组合，估计每个示例xij为正示例的概率

估计每个包Xi为正包的概率

计算每个包的信息熵

步骤3 从M个信息熵Lm中，选出使得Lm取得最大值的弱分类器，即

hk(xij)=hm*(xij)。

把该弱分类器添加到强分类器中，即

H(xij)=H(xij)+hk(xij)。若k=K，停止计算；否则令k=k+1，跳至步骤2。

1.3 弱分类器

求在线MIL分类器的问题可转换为求弱分类器的问题。更新MIL分类器时，弱分类器也在更新。假设正包中的类Haar特征服从正态分布，即

负包中的类Haar特征服从正态分布，即

假设P{y=1}=P{y=0}，利用Bayes公式可计算求得弱分类器hk(x)，即

2 实验结果与分析

实验在Visual Studio 2008环境下，结合OpenCV 2.2和Intel IPP 6.1，在Pentium Dual-Core 2.93GHz CPU和2G内存的电脑上进行。为了验证新算法的有效性，将其与Online AdaBoost[10]和MIL跟踪方法[7]，在两个公开数据集David Indoor和Girl[11]上进行了测试对比。Online AdaBoost方法中比较了正包搜索半径γ=1(记为OAB1)和γ=4(记为OAB4)两种情况。MIL和新方法中，设置正包搜索半径γ=4，负包中包含65个图像块，特征池中总的特征总数M=250，待选取的特征数为K=50构成强分类器，弱分类器的更新速率α=0.85。

2.1 跟踪结果对比

David Indoor数据集的跟踪效果如图1所示，当光照条件和目标外观发生变化(眼镜摘掉、面部旋转)时，OAB1和OAB4方法随着时间的推移，跟踪效果越来越差，最后严重偏离了运动目标。MIL方法具有较好的跟踪效果，但从总体上看，新算法的跟踪结果最接近目标真实位置。

图1 David Indoor跟踪效果

通过计算不同方法的跟踪结果与目标真实位置的距离，得到了不同跟踪方法的误差曲线，如图2所示。在刚开始的10帧内，四种方法的跟踪效果差别不大，但是随着时间的推移，在第150帧至224帧之间以及第370帧至最后一帧，OAB1和OAB4的误差急剧增大，跟踪结果偏离真实目标较远，跟踪失败。而MIL和新算法的误差曲线较平稳，但从总体上看，新算法的平均误差更小。

图2 David Indoor误差曲线

四种方法跟踪结果的误差最大值、误差均值以及误差标准差如表1所示，新算法产生的误差的最大值、均值和标准差在四种方法中均为最小，表现出较好的稳定性和鲁棒性，对于光照条件和目标外观发生变化的情况，仍能得到较好的跟踪效果。

表1 David Indoor误差比较

Girl数据集的跟踪效果如图3所示。目标的外观发生了显著变化，有正面脸、侧面脸、背面以及其他目标的干扰，跟踪难度比David Indoor数据集增大。从跟踪效果来看，MIL和新算法的跟踪效果要优于OAB1和OAB4。

图4为采用不同跟踪方法得到的误差曲线，可以看出，四种方法的跟踪效果都比David Indoor数据集的跟踪效果差，这是由于Girl数据集中运动场景更为复杂所致。OAB1和OAB4的跟踪误差随着时间在逐步增加，在450帧之前，MIL和新算法的误差曲线较为平稳，性能相差不大。但在450帧至最后一帧之间，MIL的误差急剧增大，这是由于运动目标被部分遮挡所致，而新算法误差呈现出平稳变化的趋势。

图3 Girl跟踪效果

图4 Girl误差曲线

四种方法跟踪结果的误差最大值、误差均值以及误差标准差如表2所示。新算法产生的误差的最大值和标准差在四种方法中最小，而误差均值略高于MIL。总体来看，新算法表现出较好的稳定性和鲁棒性，对于目标外观发生显著变化的情况，仍能得到较好的跟踪效果。

表2 Girl误差比较

2.2 处理时间对比

在David Indoor和Girl数据集上，对比OAB1、OAB4、MIL和新算法的平均处理时间，如表3所示。两个数据集中每帧图像大小均为320 pixel×240 pixel，OAB1算法在David Indoor和Girl数据集上的平均处理时间为161 ms/帧和153 ms/帧。OAB4的算法复杂度较OAB1稍高，平均处理时间分别为175 ms/帧和166 ms/帧。MIL和新算法的时间复杂度相同，平均处理时间分别为238 ms/帧和222 ms/帧。可见，新算法取得较好的跟踪效果是以牺牲时间为代价的。

表3 各算法在相应数据集上的平均处理时间/ms

3 结 语

提出一种基于多示例学习框架的跟踪算法。该算法利用类Haar特征构建若干弱分类器，然后级联为多示例学习强分类器，进行基于检测的跟踪，并在跟踪的过程中，实时更新多示例学习强分类器，以适应运动目标外观变化。实验表明，该算法具有较好的鲁棒性和实时性，对于运动目标外观有显著变化的情况具有较好的跟踪效果。

[1] Yilmaz A, Javed O, Shah M. Object Tracking: A Survey[J]. ACM Computing Surveys, 2006, 38(4): 1-45.

[2] 靳鹏飞. 基于自适应模板相关跟踪算法的研究[J]. 西安邮电学院学报, 2007, 12(1): 44-47.

[3] 李晶, 范九伦, 张雁冰. 基于卡尔曼滤波的人脸跟踪算法[J]. 西安邮电学院学报, 2010, 15(3): 101-104.

[4] Dietterich T G, Lathrop R H, Lozano-Perez T. Solving the multiple-instance problem with axis-parallel rectangles[J]. Artificial Intelligence, 1997, 39(1/2): 31-71.

[5] Viola P, Platt J, Zhang Cha. Multiple instance boosting for object detection[J]. Neural Information Processing Systems, 2007,18(1): 1417-1426.

[6] Babenko B, Dolla P, Tu Zhuowen, et al. Simultaneous Learning and Alignment: Multi-Instance and Multi-Pose Learning[C]//Workshop on Faces in Real-Life Images: Detection, Alignment, and Recognition. France Marseille: IEEE ECCV, 2008: 1-14.

[7] Babenko B, Yang M, 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] Zhang Kaihua, Song Huihui. Real-time visual tracking via online weighted multiple instance learning[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 46(1): 397-411.

[9] Fu Zhouyu, Robles-Kelly A. MILIS: Multiple Instance Learning with Instance Selection[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(5): 958-977.

[10] Grabner H, Grabner M, Bischof H. Real-Time Tracking via On-line Boosting[C]//Proceedings of the British Machine Vision Conference. UK Edinburgh: BMVC,2006: 47-56.

[11] Babenko B. Tracking with online multiple instance learning[EB/OL].(2011-02-03)[2013-11-20].http://vision.ucsd.edu/～bbabenko/project_miltrack.shtml.

[责任编辑:王辉]

Object tracking algorithms with multiple instance learning

LI Na1,2,3， LI Daxiang1,3， LIU Weihua1,3， LIU Ying1,3

(1.School of Communication and Information Engineering, Xi’an University of Posts and Telecommunications, Xi’an 710121, China;2.School of Information Engineering, Chang’an University, Xi’an 710064, China；3.Lab of Image Processing, Shaanxi Crime Scene Investigation Unit, Xi’an 710121, China)

In this paper, an object tracking algorithm with multiple instance learning is proposed. This algorithm uses Haar-like features to build many weak classifiers, and combines some of them into an additive strong classifier. According to the position of the object in the former frame, the position of the object in the current frame is ascertained with the strong classifier. Different image patches are cropped as positive and negative bags to update the online strong classifier in its neighborhood. The experimental results show that this algorithm has good robustness and real-time performance when the appearance of object undergoes some significant changes.

object tracking, multiple instance learning, weak classifier

2013-12-03

陕西省自然科学基金资助项目(2013JM8031)；西安邮电大学中青年教师基金资助项目(ZL2013-04，ZL2012-01)

李娜(1981-)，女，讲师，从事目标跟踪和行为分析研究。E-mail：lina114@xupt.edu.cn 李大湘(1974-)，男，副教授，从事多示例学习和图像检索研究。E-mail: 35108809@qq.com

10.13682/j.issn.2095-6533.2014.02.007

TP391

A

2095-6533(2014)02-0043-05