基于排序支持向量机的多特征融合目标跟踪算法

刘 锴,戴平阳,江晓莲,李翠华

(厦门大学信息科学与技术学院,福建厦门361005)

基于排序支持向量机的多特征融合目标跟踪算法

刘 锴,戴平阳,江晓莲,李翠华

(厦门大学信息科学与技术学院,福建厦门361005)

针对计算机视觉领域的目标跟踪问题,提出一种基于排序支持向量机的多特征融合目标跟踪算法。利用排序支持向量机学习得到排序函数,提取2种不同的图像特征分别构造分类器,使2个排序支持向量机并行预测,分别计算2个分类器的错误率,从而得到分类器权重完成融合。实验结果表明,与目前主流的跟踪算法相比,该算法的跟踪结果更准确,在复杂视频环境下也能对目标进行稳定跟踪,具有较强的鲁棒性。

目标跟踪;多特征融合;排序学习;分类器;排序支持向量机;鲁棒性

1 概述

视觉目标跟踪是计算机视觉领域内一个重要组成部分,随着研究的不断深入,人们提出了许多跟踪算法［1］,但要实现不同场景下的目标鲁棒跟踪,仍然需要克服许多难点,如场景光照变化、背景混淆、目标自身形变、目标快速运动、部分遮挡、完全遮挡等［2］。

近年来,基于学习的视觉跟踪方法越来越受到人们的关注,文献［3］提出了一种结合光流法的支持向量机跟踪算法,该算法使用离线数据训练支持向量机来进行目标跟踪。文献［4］引入结构化输出的支持向量机(Support Vector Machine,SVM)来进行目标跟踪,该方法通过使用结构化输出的支持向量机直接给出了目标跟踪结果,而不是采用传统的基于检测的先采用后分类的跟踪方法来进行跟踪。文献［5］则将排序支持向量机引入跟踪领域,提出了使用排序支持向量机来进行视觉目标跟踪,并进一步改进为带有弱监督样本的排序支持向量机跟踪算法［6］。

本文提出一种多特征融合的排序支持向量机跟踪算法。首先通过排序支持向量机得到一个排序函数,然后将多特征融合的思想与排序支持向量机相结合,使用不同的特征并行训练支持向量机,并将它们用相应的权重值结合起来,最终形成一个自适应的在线学习多特征融合算法。

2 排序学习

排序学习是一种监督或半监督学习问题,其目的是利用训练数据自动构建排序模型。训练数据由数据列表组成,这些数据两两之间存在偏序关系。其中的排序是通过给出每项数据的分值来实现。排序学习与分类或回归等传统的机器学习任务有所不同。与分类学习相比,排序学习定义了序的关系,而与回归学习不同,排序学习元素之间有序但没有度量关系。

排序学习定义为:给定输入向量集合X={x1, x2,…,xl}及对应标签集合Y={y1,y2,…,yl}。排序学习就是从决策函数集合F={f:X→Y}中寻找最优决策函数f*,使得其能精确预测未标记数据x的标签y。即给定损失函数g,在最优决策函数f*,有风险函数R(f)最小。

3 排序支持向量机

排序支持向量机 (Ranking Support Vector Machine,RSVM)是解决排序学习问题的一类典型算法［7］。排序支持向量机的核心思想是把对目标数据样本的排序问题,转换为基于有序对数据样本的二值分类问题,并利用支持向量机求解。

假设f是如下线性函数满足:

其中,w表示权重向量;＜·,· ＞表示内积。将式(3)代入式(2)得:

由式(4)可得,xi和xj之间的优先关系xi≻xj转换为xi-xj表示。对于任意给定样本对,都可以将它们之间的有序关系转换为新的向量和新的标签,从而由已知训练集S,可以构成包含已标记样本的新数据集S′,由式(5)给出:

从而将排序学习问题转化为标准的二分类问题。构造RSVM可得:

令w*为式(6)的最优权重向量,则RSVM排序函数为:

4 多特征融合

4.1 特征表示

图像的信息提取及表示,是影响跟踪算法性能的关键因素。其中,图像特征的选择尤为关键。图像特征大致分为颜色和灰度统计特征、纹理和边缘特征、代数特征、变换系数特征或滤波器系数特征。在跟踪过程中,每个实例根据其特征表示成为一个特征向量。本文用到的描述图像区域实例的特征包括Haar类特征和HOG特征2类。其中Haar类特征由2个～6个随机生成的矩形框和对应权重决定,每个图像区域随机采样200个Haar类特征来表示,而HOG特征则将每个图像区域表示成为一个3 780维特征向量。

4.2 融合过程

单独使用某个特征往往难以全面描述各种场景中的目标信息。过去的研究常常将不同的特征简单地结合成为一个新的特征,然而由于各个特征对图像的描述准确度不同,简单结合的特征将不能灵活地根据实际情况调整不同特征之间的权重关系,从而影响到训练的分类器性能。

分别训练基于HOG和Haar 2个不同特征表示的分类器,然后根据其对应错误率分别计算相应的权重,从而有效地调整2种特征的影响因子。在t时刻某个特征无法很好描述目标,从而导致跟踪性能下降时,该特征对应分类器的权重值会因其错误率的升高而降低,这将使得能有效描述目标特征的跟踪器在跟踪过程中起主导作用,从而实现基于多特征融合的鲁棒目标跟踪。

在训练过程中,给定训练集合C,其中有已标记样本数N,分别训练基于HOG及Haar特征的分类器。由每个分类器的分类结果可以得到M个分类错误样本,从而计算得到该分类器错误率:

那么该分类器权重可以表示为:

5 训练集的构成

从连续k帧图像中采集训练样本并学习得到排序支持向量机。假定目标周围的图像块分值要高于远离目标区域的图像块分值。若在t帧目标的位置为,那么,可以分别构建和2个训练样本集,如式(10)和式(11)所示:

6 多特征融合的排序SVM跟踪算法

根据Ranking SVM构造排序函数:

那么,图像对的排序问题就转换为二值分类问题,其RSVM定义如下:

式(14)的对偶问题由式(15)给出:

那么,图像排序问题就等价于一个二次优化问题。求解式(15)得到最优解α*,由式(16)可以计算得到最优权重向量w*:

那么,排序函数F由式(17)给出:

式(17)表明,F(xi)越大,对应的xi排名越高。因此,最终融合的分类器C的分值由式(18)计算得到:

苏轼“以诗为词”的词学理论是建立在“诗词同源”基础之上的，“清诗绝俗，甚典而丽。搜研物情，刮发幽翳，微词宛转，盖诗之裔”［3］。词为诗之苗裔，苏轼重点强调的是词如诗的主观抒情性、个性化的色彩，用以淡化词之媚俗，展现文人士大夫刚健清雅的精神境界，这就打破了词为艳科的藩篱，摆脱了音律对词的束缚，从而改革词风，扩大词境，促进词之雅化，提高词之品格。古往今来的论者，对“以诗为词”的褒扬者，其在自己所处时代的历史境遇内，皆是以诗词的相通之处——诗词均出自于《诗》、《骚》、古乐府，都能吟咏性情，皆可作为察政观俗的工具，词可寓诗人的句法［4］50为基点，进而对苏轼“以诗为词”理论的进行发扬。

其中,wHaar和wHOG由式(8)和式(9)计算得到。

在t时刻,给定搜索区域和分类器C,由式(18)计算搜索区域内候选图像块的最终分值Ft(x),从而得到目标位置。

多特征融合的排序支持向量机目标跟踪算法的具体描述如下:

算法 多特征融合的排序支持向量机目标跟踪算法

输入 图像序列{I1,I2,…,IT},原始帧目标位置

7 实验结果与分析

本文算法在vs2010上由c++编写实现。测试用的视频序列为经典公开测试序列。在所有测试序列实验中,参数设置对所有视频序列都是固定的。实验参数具体为 r=2,α=5,β=30,s=30,其中式(10)采样得到45个样本构成,式(11)采样后随机选取100个样本构成。

在Davidindoor序列中,目标在室内走动过程中有光照变化、尺度变化、自身形变等干扰。

在Davidoutdoor序列中,目标从左往右运动再返回,期间目标外观因变向而改变,且发生多次严重遮挡。

在Girl视频序列中,跟踪难点主要是目标在跟踪过程中会出现较明显的尺度变化、旋转、遮挡、自身形变、相似物体干扰,是较难的测试序列。

在Jumping序列中,跟踪难点则是目标快速运动及因此而造成的目标模糊。

本文算法在经典测试序列上跟踪结果如图1所示,表 1 是本文算法与 Frag［8］,L1［9］,MIL［10］, PCA［11］,PN［12］,VTD［13］等主流跟踪算法在测试序列上相应的中心误差对比。实验结果表明,本文算法在经典的测试序列上明显优于上述对比算法,能够实现准确鲁棒的目标跟踪。

图1 经典序列跟踪结果

表1 经典序列中心误差对比像素

8 结束语

本文在跟踪领域引入排序支持向量机,将样本间的排序问题转化成有序对的分类问题,提高了分类的准确度。通过构造2个不同图像特征的分类器,克服了单特征难于全面描述目标外观的缺点,并且由它们各自的分类错误率来调整其相应权重,可以使融合后的分类器自适应地描述目标外观的变化,达到稳定鲁棒的跟踪效果。下一步工作是将本文算法与CUDA编程相结合,提高特征提取和训练排序支持向量机的速度。

［1］ 侯志强,韩崇昭.视觉跟踪技术综述［J］.自动化学报, 2006,32(4):603-617.

［2］ 卢晓鹏.视频序列中目标跟踪技术研究［D］.北京:中国科学院研究生院,2007.

［3］ Avidan S.Support Vector Tracking［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence,2004,26(8): 1064-1072.

［4］ Hare S,Saffari A,Torr P H S.Struck:Structured Output Tracking with Kernels［C］//Proceedings of CVPR'11.Barcelona,Spain:IEEE Press,2011:263-270.

［5］ Bai Yancheng,Tang Ming.Robust Visual Tracking via Ranking SVM［C］//Proceedings of ICIP'11.Brussels, Belgium:IEEE Press,2011:517-520.

［6］ Bai Yancheng,Tang Ming.Robust Tracking via Weakly Supervised Ranking SVM［C］//Proceedings of CVPR'12.Rhode Island,USA:IEEE Press,2012:1854-1861.

［7］ Yu H,Kim Y,Hwang S.RV-SVM:An Efficient Method for Learning Ranking SVM［C］//Proceedings of PAKDD'09.Berlin,Germany:Springer-Verlag,2009:426-438.

［8］ Adam A,Rivlin E,Shimshoni I.Robust Fragments-based Tracking Using the Integral Histogram ［C］// Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition.New York, USA:IEEE Computer Society,2006:798-805.

［9］ Mei X,Ling H.Robust Visual Tracking and Vehicle Classification via Sparse Representation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011,33(11):2259-2272.

［10］ Babenko B,Yang M H,Belongie S.Robust Object Tracking with Online Multiple Instance Learning［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,33(8):1619-1632.

［11］ Ross D A,Lim J,Lin R S,et al.Incremental Learning for Robust Visual Tracking［J］.International Journal of Computer Vision,2008,77(1-3):125-141.

［12］ Kalal Z,Mikolajczyk K,Matas J.Tracking-learningdetection［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence,2012,34(7):1409-1422.

［13］ Kwon J,Lee K M.Visual Tracking Decomposition［C］// Proceedings of CVPR'10.San Francisco,USA:IEEE Press,2010:1269-1276.

编辑 金胡考

Object Tracking Algorithm Based on Ranking Support Vector Machine Fused with Multiple Features

LIU Kai,DAI Pingyang,JIANG Xiaolian,LI Cuihua
(School of Information Science and Technology,Xiamen University,Xiamen 361005,China)

For the object tracking problems in computer vision,this paper proposes a tracking algorithm based on Ranking Support Vector Machine(RSVM)fused with multiple features.Firstly,RSVM is used to get rank function.Secondly,the RSVMs combined with the two different image features are learnt respectively,then the two RSVMs predict parallel.Finally,the two RSVMs are fused with the weights which are calculated by the error rates of two classifiers,then it constructs a more adaptive RSVM framework fused with multiple features.This algorithm fuses image features effectively,and gets accurate predictions using RSVM.Experimental results demonstrate that it outperforms several stateof-the-arts algorithms.

object tracking;multiple features fusion;rank learning;classifier;Ranking Support Vector Machine (RSVM);robustness

1000-3428(2014)11-0042-04

A

TP18

10.3969/j.issn.1000-3428.2014.11.008

国家部委基金资助项目;高等学校博士学科点专项科研基金资助项目(20110121110020)。

刘 锴(1989-),男,硕士研究生,主研方向:计算机视觉;戴平阳,博士研究生;江晓莲,硕士研究生;李翠华,教授、博士。

2013-11-13

2014-01-10E-mail:LKnight.xmu@gmail.com

中文引用格式:刘 锴,戴平阳,江晓莲,等.基于排序支持向量机的多特征融合目标跟踪算法［J］.计算机工程, 2014,40(11):42-45.

英文引用格式:Liu Kai,Dai Pingyang,Jiang Xiaolian,et al.Object Tracking Algorithm Based on Ranking Support Vector Machine Fused with Multiple Features［J］.Computer Engineering,2014,40(11):42-45.