基于特征分组的在线目标跟踪算法

姜明新， 王洪玉

（1.大连理工大学信息与通信工程学院，辽宁大连 116024；2.大连民族学院信息与通信工程学院，辽宁大连 116602）

基于特征分组的在线目标跟踪算法

姜明新＊1，2， 王洪玉1

（1.大连理工大学信息与通信工程学院，辽宁大连 116024；2.大连民族学院信息与通信工程学院，辽宁大连 116602）

在线目标跟踪是计算机视觉领域的一个具有挑战性的问题.提出了一种基于特征分组的在线目标跟踪算法.首先，利用像素点在多帧的方差对模板库中的目标模板进行特征分组.然后，利用主要特征图像和次要特征图像学习投影矩阵P，对样本进行投影.最后，利用最小误差法得出当前帧的跟踪结果.与其他典型算法相比，该算法对目标的异常变化具有很强的鲁棒性.

在线目标跟踪；线性子空间学习；特征分组；模板更新

0 引 言

基于视频的在线目标跟踪技术是计算机视觉领域的关键问题之一，在人机交互、视频监控、智能交通、行为识别等领域都有着广泛的应用.很多学者做了这方面的研究［1－3］，并且取得了一些进展.然而，当发生遮挡、旋转、尺度变化、光照变化等异常变化时，目标的外观模型也会发生较大的变化，因此，如何建立一个鲁棒性强的目标跟踪器就成为了一个具有挑战性的问题.

想要建立一个鲁棒性强的目标跟踪器，就要采用一个能够在跟踪过程中反映目标变化的在线外观模型.线性子空间学习是一种典型的降维和特征提取技术，在模式识别领域已经得到了成功的应用.近年来，利用线性子空间学习的方法进行视频目标跟踪已经吸引了许多学者的注意［4－5］，其中文献［4］提出的IVT（incremental visual tracking）跟踪器比较有影响力，该算法对光照变化、尺度变化等的鲁棒性较强，但是当目标发生部分遮挡时，跟踪器的性能比较脆弱.文献［5］提出了一种基于半监督学习的在线跟踪器，仅对第一帧采集的样本赋予标签，其余帧的训练样本看作是无标签的，该方法同样在部分遮挡时会发生跟踪失败.

基于以上分析，本文提出一种基于特征分组的在线目标跟踪算法，对样本中的像素进行分组，利用分组后的结果计算映射矩阵.根据状态转移模型选取样本，对样本进行映射，选取与上一帧跟踪结果距离最短的作为本帧的跟踪结果.

1 特征分组

首先，分析一下IVT跟踪器［4］在目标发生部分遮挡时鲁棒性能差的原因.IVT跟踪器是利用增量PCA算法对低维子空间的目标模型进行学习和更新，PCA的基本原理为

其中y为观测向量，z为相应的编码向量，U为基向量，e为误差向量.在PCA算法中，假设误差向量e服从最小方差的高斯分布，因此，编码向量z可以表示为z＝UTy，重建误差则可以表示为.然而，当目标发生部分遮挡时，误差向量e并不服从高斯分布，所以IVT跟踪器在目标发生部分遮挡时变得非常脆弱.

1.1 对目标模板进行特征分组

假设目标模板库由n个目标模板tj组成，可以用矩阵T＝（tij）＝（t1t2…tn）∈Rd×n表示.其中tj∈Rd，dn.当前帧中跟踪结果图像块用y表示，y∈Rd.在实验过程中，取前n帧的跟踪结果作为目标模板库中的初始模板.本文取模板数目n＝10，目标模板的大小为32×32，则d＝1 024.

接下来，将每个目标模板图像tj（j＝1，2，…，n）分解为主要特征图像和次要特征图像.用表示目标模板库中像素tij在n帧内的均值表示第τ帧像素tij的值，则像素tij的方差为

设定阈值σ1，如果像素tij的方差σij＜σ1，则将该像素点放入主要特征图像.对目标模板进行特征分组后的结果如图1所示.

图1 特征分组的结果Fig.1 Results of feature grouping

1.2 计算投影矩阵

特征分组后，目标模板库中的每个目标模板tj可以表示为tj＝＋（j＝1，2，…，n），则目标模板库矩阵可以表示为T＝Ta＋Tb.现有的线性子空间学习算法都是只利用主要特征图像Ta来学习投影矩阵P，忽略了次要特征Tb对投影方向的影响.鉴于以上考虑，在特征分组后，利用Ta和Tb来学习投影矩阵P.这样得到的投影矩阵P能在很好地保留主特征图像能量的同时抑制次要特征图像的能量，进而减弱次要特征对跟踪结果的影响.计算投影矩阵P的具体过程如下：

显然，通过特征值分解可以得到投影矩阵P.

假如散布矩阵Sb不存在，Sa则成为全部训练样本的总体散布矩阵S，那么目标方程（6）则简化为

可以看出，方程（7）是PCA算法的目标方程.

2 状态转移模型

选取目标的运动仿射变换参数作为状态变量xt＝（xtytθtstαtt），其中xt、yt分别表示目标在第t帧x、y方向上的平移，θt表示目标在第t帧的旋转角度，st表示目标在第t帧变化的尺度，αt表示目标在第t帧变化的纵横比，t表示目标在第t帧的倾斜方向.

为不失一般性，假设状态转移模型服从高斯分布，即

3 算法的实现与模板库的更新

为了更直观地描述本文提出的基于特征分组的在线目标跟踪算法，如图2所示画出算法的流程图.

由于前n帧目标变化很小，可以利用最短距离法实现快速跟踪，取前n帧的跟踪结果作为目标模板库中的初始模板，利用初始模板库计算投影矩阵P.在n＋1帧到来时，根据状态转移模型，在上一帧目标跟踪结果的周围选取N个样本.对每个样本进行投影，计算投影后的结果与上一帧跟踪结果投影后的距离，取距离最小的样本作为本帧的跟踪结果.

图2 跟踪算法的流程图Fig.2 The flowchart of tracking algorithm

由于在目标跟踪的过程中会发生遮挡、旋转等异常变化，更新目标模板库具有十分重要的作用.从第n＋1帧开始，将本帧跟踪结果投影后的主特征图像与目标模板库中的后n－1个模板的主特征图像放在一起，计算这n帧主特征图像像素点的方差.如果方差小于阈值，则将该像素点分组到主要特征图像，然后把新得到的主特征图像更新到模板库中，舍弃原模板库中第1个主特征图像.次要特征图像也做相应的处理，这样就完成了一次模板库的更新，利用更新后的模板库重新计算映射矩阵，进而完成映射矩阵的更新.

4 实验结果及分析

为了说明基于特征分组的在线目标跟踪算法的鲁棒性，选取多组公共测试视频作为实验视频，鉴于篇幅限制，只列举其中5组视频的实验结果.选取的实验测试视频中的运动目标分别发生了遮挡、旋转、光线变化、尺度变化等异常变化.本文算法的实现基于Windows操作系统，采用MATLAB作为软件平台，计算机配置为AMD Athlon（tm）X2DualCore QL－62 2.00GHz，1.74 GB内存.

为了评估本算法的性能，选用6种目前最具有代表性的典型跟踪算法进行了实验结果的对比.6种典型算法分别为IVT Tracker［4］、L1 Tracker［6］、PN Tracker［7］、VTD Tracker［8］、MIL Tracker［9］和Frag Tracker［10］.

针对5组实验测试视频，本文提出的算法与6种典型算法的跟踪结果对比如图3～6所示，其中红色跟踪框为本文提出算法的跟踪结果，其余6种典型算法的跟踪结果分别用下列颜色的跟踪框进行表征：L1Tracker对应绿色跟踪框，IVT Tracker对应深蓝色跟踪框，PN Tracker对应黑色跟踪框，VTD Tracker对应黄色跟踪框，MIL Tracker对应粉色跟踪框，Frag Tracker对应浅蓝色跟踪框（由于印刷所限文中用深浅色区分）.

测试视频Car4和Singer1中影响目标跟踪的因素主要有光照变化和尺度变化；测试视频Lemming中影响目标跟踪的因素主要有平面外旋转、背景干扰和尺度变化；测试视频Car11的主要问题是光照变化、尺度变化和背景干扰.从图3～6的视频目标跟踪的实验结果可以看出，本文提出的基于特征分组的在线目标跟踪算法在目标发生遮挡、旋转、光线变化、尺度变化等异常变化时，能够稳定地跟踪目标，与其他几种典型算法相比，表现出更好的准确性和鲁棒性.

不同算法的跟踪误差曲线结果对比如图7所示.从图7可以看出，本文提出的基于特征分组的在线目标跟踪算法的跟踪误差低于其他6种典型算法，获得了较高的目标跟踪准确度.

图3 测试视频Car4的跟踪结果对比Fig.3 The comparison of tracking results for test video Car4

图4 测试视频Lemming的跟踪结果对比Fig.4 The comparison of tracking results for test video Lemming

图5 测试视频Singer1的跟踪结果对比Fig.5 The comparison of tracking results for test video Singer1

图6 测试视频Car11的跟踪结果对比Fig.6 The comparison of tracking results for test video Car11

图7 测试视频跟踪误差曲线结果对比Fig.7 The comparison of tracking error curves results for test videos

5 结 论

本文通过对传统的PCA算法的缺点进行分析，提出了基于特征分组的在线目标跟踪算法，对样本中的像素进行分组，利用分组后的结果计算映射矩阵.根据状态转移模型选取样本，对样本进行映射，选取与上一帧跟踪结果距离最短的作为本帧的跟踪结果.本文提出的跟踪算法，在很大程度上简化了计算的复杂度，提高了算法的准确性.从实验结果可以看出，本文的算法在目标发生遮挡、旋转等各种变化时，依然可以准确地跟踪目标，鲁棒性能非常好.

［1］ 刘晨光，程丹松，刘家锋，等.一种基于交互式粒子滤波器的视频中多目标跟踪算法［J］.电子学报，2011，39（2）：260－267.

LIU Chen－guang，CHENG Dan－song，LIU Jiafeng，etal.Interactive particle filter based algorithm for tracking multiple objects in videos［J］.Acta Electronica Sinica，2011，39（2）：260－267.（in Chinese）

［2］Kristan M，Kovacic S，Leonardis A，etal.A twostage dynamic model for visual tracking［J］.IEEE Transactions on Systems，Man，and Cybernetics，Part B：Cybernetics，2010，40（6）：1505－1520.

［3］ 冯 巍，胡 波，杨 成，等.基于贝叶斯理论的分布式多视角目标跟踪算法［J］.电子学报，2011，39（2）：315－321.

FENG Wei，HU Bo，YANG Cheng，etal.A distributed multi－view object tracking algorithm under the Bayesian framework［J］.Acta Electronica Sinica，2011，39（2）：315－321.（in Chinese）

［4］Ross D，Lim J，Lin R，etal.Incremental learning for robust visual tracking［J］.International Journal of Computer Vision，2008，77（1－3）：125－141.

［5］Grabner H，Leistner C，Bischof H.Semi－supervised on－line boosting for robust tracking［C］／／Computer Vision－ECCV 2008－10th European Conference on Computer Vision，ECCV 2008.Proceedings.Heidelberg：Springer Verlag，2008：234－247.

［6］MEI X，LING H B.Robust visual tracking and vehicle classification via sparse representation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，33（11）：2259－2272.

［7］Kalal Z，Matas J，Mikolajczyk K.P－N learning：Bootstrapping binary classifiers by structural constraints［C］／／Proceeding of the IEEE Conference on Computer Vision and Pattern Recognition，CVPR 2010.Piscataway：IEEE Computer Society，2010：49－56.

［8］Kwon J，Lee K M.Visual tracking decomposition［C］／／Proceeding of the IEEE Conference on Computer Vision and Pattern Recognition，CVPR 2010.Piscataway：IEEE Computer Society，2010：1269－1276.

［9］Babenko B，Belongie S，Yang M H.Visual tracking with online multiple instance learning［C］／／2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops，CVPR Workshops 2009.Piscataway：IEEE Computer Society，2009：983－990.

［10］Adam A，Rivlin E，Shimshoni I.Robust fragments based tracking using the integral histogram［C］／／Proceeding of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition，CVPR 2006.New York：IEEE Computer Society，2006：798－805.

Online object tracking algorithm based on feature grouping

JIANG Ming－xin＊1，2， WANG Hong－yu1

（1.School of Information and Communication Engineering，Dalian University of Technology，Dalian 116024，China；2.College of Information ＆Communication Engineering，Dalian Nationalities University，Dalian 116602，China）

Online object tracking is a challenging issue in computer vision.An online object tracking algorithm based on feature grouping is proposed.Firstly，the object templates in template base are grouped by computing the variance of the pixels in multiple frames.Then，the projection matrixPis learned based on the more discriminative image and the less discriminative image，and the samples are projected.Finally，tracking results of the current frame are performed by minimum error.Compared with other popular methods，the proposed method has strong robustness to abnormal changes.

online object tracking；linear subspace learning；feature grouping；template updating

TP391

A

1000－8608（2013）05－0755－05

2012－09－13；

2013－07－12.

国家自然科学基金资助项目（61172058）；中央高校基本科研业务费专项资金资助项目（DC10010103）；辽宁省教育厅资助项目（L2012476）.

姜明新＊（1979－），女，博士生，E－mail：jmx＠mail.dlut.edu.cn；王洪玉（1969－），男，教授，博士生导师.