基于在线支持向量机的Mean Shift彩色图像跟踪

郭敬明，何 昕，魏仲慧

（1.中国科学院 长春光学精密机械与物理研究所，吉林 长春，130033；2.中国科学院大学，北京100049）

1 引 言

目标跟踪广泛应用于智能视频监控、智能机器人及国防安全方面等领域。如何在视频序列中对目标进行稳健、实时跟踪，是计算机视觉领域的热点问题。稳健性要求算法能够克服光照、姿态变化，目标快速运动，部分遮挡等干扰因素的影响；实时性要求算法必须有较高的搜索效率，计算耗时少，其实质是如何在当前帧内快速运算锁定目标。

文献［1］将目标跟踪算法分为两类：一类是基于“滤波、数据关联”的跟踪方法，代表为粒子滤波［2］（particle filter）及其改进算法［3－5］；一类是基于“目标建模、定位”的跟踪方法，代表为Mean Shift［6］及其改进算法［7－8］。由于粒子滤波收敛速度慢，算法复杂度与粒子数成正比，且过多依赖参数，而Mean Shift是一种基于核密度估计的无参数的、基于微分方法的模式匹配搜索算法，计算复杂度低，具有很好的实时性，因此在目标实时跟踪系统中应用越来越广泛［9－15］。

尽管Mean Shift应用十分广泛，但有两个基本的缺陷：（1）目标模板只能从单一图像建立；（2）模板很难自适应更新。针对以上问题，相关学者提出了多种改进方案。文献［5］提出用Mean Shift与粒子滤波相结合的多模式融合跟踪算法，分别跟踪后，采用加权参考函数定位目标，但粒子滤波器的复杂计算降低了系统的实时性。文献［12］提出在线特征选择机制来对特征进行排序，选择区分能力最强的特征来建立模板，将颜色R、G、B特征以不同权值组合找到具有更具判决能力的特征，这样也将大大增加算法的复杂度。文献［11］研究了跟踪过程中在线学习的重要性，模型的更新能够捕获目标或背景的变化。文献［10］提出了模板在线更新的Mean Shift算法，通过将跟踪问题看作目标和背景的分类问题，引入支持向量机（Support Vector Machine）分类函数置信度，将最小化距离函数转换为最大化分类函数置信度，但其没有给出在线支持向量机的实现方法，且针对彩色RGB空间加权求得灰度建立目标及背景模型，在光照发生变化或有阴影时有明显缺陷［15］。

针对上述算法的优缺点，本文提出了基于HSV 彩色空间的在线SVM 的Mean Shift跟踪算法。为克服RGB 颜色空间在光照变化及阴影效应下的缺陷，将RGB 空间变换到HSV 空间，首先分别建立H、S、V 核直方图，然后建立统一的HSV 核直方图，并赋予各分量不同权重，最后将HSV 核直方图融合到基于在线SVM［13］的Mean Shift跟踪算法框架中，在计算复杂度不变的情况下，提高了跟踪定位精度。实验表明，本文算法优于传统Mean Shift算法、Particle Filter及文献［10］算法，稳健性、实时性均有较大提高。

2 Mean Shift跟踪与支持向量机

2.1 Mean Shift跟踪

文献［1］提出了基于核估计的目标跟踪方法，文中核基的跟踪方法即为Mean Shift跟踪方法。目标和候选目标的模型是对图像目标区域的归一化核基直方图向量：

假定目标区域由n个像素点构成｛Xi｝，i＝1，…n构成，其中Xi＝（xi，yi）为图像像素坐标，直方图bin量化个数为m，则目标的核直方图模型为：

式中，δ为Kronecker delta函数。窗口的带宽矩阵为h，用来限定目标的像素个数。b（Xi）为映射函数，将Xi对应的特征映射到bin值。c为窗口中心位置坐标。k（x）为轮廓函数，为每个像素赋予不同的权值，权值大小与距离目标中心的距离成反比，一定程度上增加了模型的可靠性，因为靠近外侧的像素易被遮挡或受背景干扰；同时，使目标函数成为光滑函数，可以由微分法计算。常用的核函数包括高斯核函数和Epanechnikov函数。C 为归一化系数。

相应地，中心位置位于y 的候选目标模型定义为：

相似性度量函数用来计算在特征空间中目标与候选目标之间的距离。Mean Shift常用的是Bhattacharyya距离：

Mean Shift跟踪原理是找到位置y，使其在所属特征空间中与目标距离最小，即Bhattacharyya系数ρ［p（y），q］最大。上述优化问题，可以通过以下迭代过程求解：

式中，g（x）＝－k′（x），当｜＾y－y｜＜ε时本帧迭代终止，ε为设定的阈值。

2.2 支持向量机

支持向量机（SVM）是基于VC 维理论和结构风险最小化原理，克服了传统机器学习中的维数灾难问题。SVM 在处理线性不可分问题中应用十分广泛，通过将训练数据从输入空间映射到高维，甚至无限维空间，SVM 求解最优超平面等价于求解如下方程：

求解上式，可以得到SVM 的判别函数：

其中：K（xi，x）＝〈Φ（xi），Φ（x）〉，满足Mercer条件的核函数，常用的核函数有RBF 核函数，多项式核函数等。xi为支持向量，Ns为支持向量个数，αi为 不 同 支 持 向 量 的 权 值，b 为 偏 置 系 数，yi为＋1或－1。

2.3 基于SVM 的Mean Shift跟踪算法

支持向量机中核函数通常采用RBF核函数、多项式核函数等，但这些函数不是根据概率密度分布来定义的。而Mean Shift是根据颜色直方图的密度函数进行估计。通过p（xi）建立训练样本xi概率密度模型，将核函数作为不同概率分布之间的相似性度量函数，从而建立基于SVM 的Mean Shift跟踪方法。

式（10）为PPK（probability product kernel）核函数，而传统Mean Shift 中采用的Bhattacharyya度量函数为ρ＝1／2时的特殊情况。

f（x）＞0，代表目标；f（x）＜0，代表背景。q（xi）为第i个支持向量，｜f（x）｜代表置信度，当｜f（x）｜递增时，表示迭代由初始值向跟踪目标优化。为了后续与传统Mean Shift进行对比，这里核函数选择Bhattacharyya系数，即ρ＝1／2。

将式（11）代入到式（12）中，得到基于图像窗口的直方图估计，即候选目标位置的判别函数：

我们对式（13）进行泰勒展开，保留一阶量，忽略了二阶及高阶展开量，得到式（14）：

其中：

上述优化问题转换为使f（＾y）最大，得到迭代求解过程：

3 基于HSV 空间的在线SVM 的Mean Shift跟踪算法

传统Mean Shift方法目标模型由单一图像建立，且很难更新，当光照、姿态变化，目标快速运动等因素造成模型变化时，极易造成目标跟踪失败。为了更新模型，模型必须尽可能多地选择样本进行训练学习。我们把目标跟踪问题视为目标和背景的分类问题，可以将在线SVM 分类器融合到传统Mean Shift框架中，使得跟踪器更加鲁棒。当光照条件发生剧烈变化或存在阴影时，R、G、B颜色空间有明显的缺陷。基于以上分析，提出了基于HSV空间的在线SVM 的Mean Shift彩色图像跟踪方法。

3.1 HSV 空间核直方图

HSV 是人们用来从调色板或颜色轮中挑选颜色所用的彩色系统之一，代表色调、饱和度和亮度值，它比RGB 空间更接近于人们对彩色的感知，在表征阴影及剧烈光照变化方面有更好的效果，可以由RGB转换得到。

因此，我们将RGB 空间直方图转换为HSV空间直方图作为相似性度量的特征。色调H 取值范围为0°～360°，红色为0°，绿色为120°，蓝色为240°；饱和度S 取值范围为0～100%；亮度值V 取值范围为0～100%。

首先，获取彩色图像RGB 值，将RGB 值从0～255归一化到0～1之间，然后按如下公式将RGB值转换为HSV 值，为了便于计算，将HSV值转换到0～255之间：

这样，获取目标图像RGB 值后，将RGB 值转换到HSV 值，得到目标模型HSV 核直方图分量｛qH，qS，qV｝：

式（20）中，H，S，V 分别为色调、饱和度、亮度直方图对应的bin值个数；h，s，v 分别为色调、饱和度、亮度对应的bin值。同理，获取候选目标模型HSV 核直方图分量｛pH，pS，pV｝。

然后，根据式（5）计算HSV 各分量Bhattacharyya系数：

从而，建立加权合成的统一相似性度量函数。

式（22）中，0≤γ，λ≤1，为预先设定的HSV各分量的权重。依式（22）构造新的满足核函数性质［14］的核函数为：

3.2 目标位置确定

根据式（13）及式（23），得到基于SVM 的Mean Shift彩色图像跟踪算法判别函数：

依照（14），通过泰勒展开得到其求解过程：

其中：b1（x），b2（x），b3（x）分别为色调、饱和度及亮度的映射函数。式（26）中，分子部分可以离线计算，因此，其算法复杂度与传统Mean Shift相同，没有增加额外的时间消耗。迭代求解式同式（16）。

3.3 模板在线学习

（1）创建初始样本空间。初始时，在第1 帧图像中手动选取待跟踪目标，窗口大小为m×n。按传统Mean Shift跟踪式（6）跟踪N 帧图像，并依次记录下每次迭代的中心位置xi（i＝1…N）。将以xi为中心m×n大小的区域图像按式（17～19）转换到HSV 空间，依（20）分别计算，得到N个正样本，即（Xi＝qH（xi）∪qs（xi）∪qV（xi），Yi＝＋1）；同理，可以从这N 帧图像中任意选取2×N 个m×n大小的不含目标的区域，按上述步骤得到2×N 个负样本为（Xi′＝qH（xi′）∪qs（xi）∪qV（xi′），Yi′＝－1）。

（2）训练生成初始支持向量。选取阈值ε及惩罚因子C，核函数为式（23），依据上述N 个正样本和2×N 个负样本，训练计算出（ω0，b0）、分类函数f0及支持向量SV0＝qH（xi）∪qS（xi）∪qV（xi），yi）i＝1…Ns）。

（3）在线支持向量机学习。当跟踪第N ＋t（t＝1）帧图像时，依据式（16），（26）迭代求解目标位置，迭代时初始位置选为上一帧目标位置xN＋1。以xN＋1为中心m×n大小区域图像产生1个新的正样本，同时，任意选取2 个不含目标的区域产生负样本，构成新增样本集It。根据决策函数f0寻找It中 违 反KKT 条 件［13］的 样 本，记为，违反KKT 判决条件如式（27）所示：

若Ivt为空集，则令SVt＋1＝SVt，ft＋1＝ft，t＝t＋1，转（3）。否则得到新样本集T＝SVt∪Ivt，进行重新学习得到SVt＋1，ft＋1，t＝t＋1，转（3）。

4 算法流程

整个算法的实现过程简单描述如下：首先手动选取第1帧待跟踪目标，采用Mean Shift跟踪第2～N 帧目标，得到当前目标位置的候选值，从每帧生成HSV 空间1 个正样本和2 个负样本；然后选择阈值及惩罚因子等参数，生成初始支持向量和分类函数；最后，跟踪后续帧时提取新增样本，根据KKT 条件，判断是否更新参考模板。算法流程如图1所示。

图1 算法流程图Fig.1 Flow chart of algorithm

5 实验结果与分析

本文提出的跟踪算法采用VC＋＋6.0实现，结果仿真采用Matlab7.1 平台实现。实验均在Pentium Dual E2180 2.0Hz的PC 平台上进行。为了验证本文算法的有效性，对国际通用的两组CAVIAR 彩色图像序列［16］进行跟踪测试，给出了试验结果。

5.1 HSV 与RGB 直方图彩色图像跟踪对比试验

第一组为oneleaveshop序列，图像分辨率为384×288，标 准PAL 制，帧 频25 f／s，采 用MPEG2压缩格式。部分跟踪结果如图1所示。

图2中，绿色矩形是传统Mean Shift跟踪结果图，矩形中十字为目标中心；红色矩形为本文算法跟踪结果图。第1帧由手动方式确定待跟踪的目标，红、绿两矩形重合。第28 帧时，传统Mean Shift算法还能定位准确。但当目标尺寸及姿态发生一定变化时，由于模板的单一性及无法更新，导致目标跟踪失败，如第94帧，第175帧。

图2 oneleaveshop序列跟踪结果Fig.2 Tracking result on oneleaveshop sequence

图3给出了初始帧手动选取的目标模板的R、G、B直方图和H、S、V 直方图，图4给出了第175帧中两种算法跟踪结果窗口的R、G、B 直方图和H、S、V 直方图。可以看出，当目标姿态发生变化时，基于RGB颜色空间的传统Mean Shift跟踪器有明显的缺陷，虽然第1帧与第175帧跟踪窗RGB 颜色直方图分布Bhattacharyya系数较大，而目标几乎完全丢失，导致跟踪失败。而HSV 颜色空间在整个彩色序列跟踪过程中具有良好的抗干扰能力。

图3 初始帧目标模板直方图Fig.3 RGB and HSV histogram of target model in frame No.1

图4 第175帧两种算法跟踪窗口直方图Fig.4 Histogram of track window by two trackers in frame No.175

5.2 4种跟踪算法跟踪性能对比试验

图5为Enter Exit序列跟踪效果图，图像分辨率及帧频同oneleaveshop 序列，与其相比，整个序列中目标姿态及光照都发生了更加剧烈的变化，除了传统Mean Shift，还增加了粒子滤波和文献［10］算法进行对比跟踪实验，主要考察算法的跟踪精度及耗时两个方面。

图中红色矩形代表本文算法，蓝色矩形代表文献［10］算法，绿色矩形代表粒子滤波算法（“＋”字代表跟踪的粒子），青色代表传统Mean Shift算法。同样，第1 帧由手动方式确定，4 个跟踪窗重合。第40 帧时，光照及目标姿态发生微小变化，Mean Shift跟踪定位误差最大，导致后续跟踪失败。第40帧，第89帧时，粒子滤波还能表现出良好的跟踪能力，定位误差较Mean Shift小。但当第157帧时，目标姿态由正面转为侧面，背景及光照也发生较大变化，粒子滤波跟踪失败。可以看出，由于背景的变化及目标姿态变化，待跟踪目标模型发生巨大变化，因此，模型更新是有效跟踪的必要手段。文献［10］及本文算法均采用从多帧图像建立模型及模型自适应更新算法，因此，在整个图像跟踪序列中都能够精确跟踪目标，尤其在第232帧以后。

图5 4种跟踪算法对EnterExit序列跟踪结果Fig.5 Tracking result on EnterExit sequence by four trackers

图6，图7 分别给出了x，y 方向定位偏差。Proposed Tracker代表本文算法；Tracker in［10］代表文献［10］算法；Standard Mean Shift代表传统Mean Shift算法；Particle Filter代表粒子滤波算法。

图6 x 方向偏差Fig.6 Deviation of axis

定位偏差计算公式［7］如式（28）所示：

式中：（xi，yi）为各种算法计算所得目标矩形中心位置，（xc，yc）为通过人工逐帧获取的目标中心位置。Errori的平方即为图6、图7 对应曲线各点的平方和。

表1给出了4种跟踪算法根据式（28）计算的整个图像序列定位误差的均值和方差，单位为像素。FR0.5［10］代表跟踪窗中心偏离实际目标中心大于0.5像素的帧数占序列总帧数的比例，FR1代表阈值为1 像素时的跟踪失败比例。粒子滤波跟踪器采用100个粒子，调整参数，取10次跟踪的平均值。可以看出，本文算法跟踪精度最高，跟踪失败率最低。

表1 4种跟踪算法对EnterExit序列跟踪误差结果Tab.1 Tracking error of four trackers against the ground truth on EnterExit sequence

表2给出了各自的平均处理时间。粒子滤波收敛速度最慢，消耗时间最长。而本文算法和文献［10］虽然增加了在线学习，但部分计算因子可以离线进行，其计算复杂度与Mean Shift相当，与支持向量数无关。本文算法对分辨率为384×288的视频序列，最快处理速度能达到40 f／s。

表2 4种跟踪算法对EnterExit序列平均处理时间Tab.2 Average computing time of four trackers on EnterExit sequence

6 结 论

针对传统Mean Shift算法模板从单一图像建立，且很难更新问题，提出了基于HSV 空间的在线SVM 的Mean Shift跟踪算法，将RGB颜色空间转换到HSV 空间，建立新的统一核函数模型，引入增量学习支持向量机算法，对违反KKT条件的样本进行学习，减少计算量，实现目标模型的在线更新。实验表明：本文算法对目标姿态、光照及背景发生较大变化时，跟踪有效且耗时少。当像素大小为384pixel×288pixel（目标尺寸为20pixel×80pixel）时，最快处理速度达40f／s，且跟踪精度（FR0.5）比传统Mean Shift提高了32.1%，平均定位误差为4.1pixel，基本满足了某些稳健实时跟踪系统的要求。

［1］ Comaniciu D，Ramesh V.Kernel－based object tracking［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2003，24（5）：564－577.

［2］ ISARD M，BLAKE A.Condensation－conditional density propagation for visual tracking［J］.International Journal of Computer Vision，1998，29（1）：5－28.

［3］ 杜超，刘伟宁，刘恋.一种基于卡尔曼滤波及粒子滤波的目标跟踪算法［J］.液晶与显示，2011，26（3）：384－389.Du C，Liu W N，Liu L.Target tracking algorithm based on Kalman filter and particle filter［J］.Chinese Journal of Liquid Crystals and Displays，2011，26（3）：384－389.（in Chinese）

［4］ 王国良，刘金国.基于粒子滤波的多自由度运动目标跟踪［J］.光学 精密工程，2011，19（4）：864－869.Wang G L，Liu J G.Moving object tracking with multi－degree－of－freedom based on particle filters［J］.Optics and Precision Engineering，2011，19（4）：864－869.（in Chinese）

［5］ 陈爱华，孟勃，朱明，等.多模式融合的目标跟踪算法［J］.光学 精密工程，2009，17（1）：185－190.Chen A H，Meng B，Zhu M，et al.Multi－pattern fusion algorithm for target tracking［J］.Optics and Precision Engineering，2009，17（1）：185－190.（in Chinese）

［6］ Comaniciu D，Meer P.Mean shift：A Robust application toward feature space analysis［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2002，24（5）：603－619.

［7］ 王田，刘伟宁，韩广良，等.基于改进Mean Shift的目标跟踪算法［J］.液晶与显示，2012，27（3）：396－400.Wang T，Liu W N，Han G L，et al.Target tracking algorithm based on improved Meanshift［J］.Chinese Journal of Liquid Crystals and Displays，2012，27（3）：396－400.（in Chinese）

［8］ 刘扬，张云峰，董月芳.复杂背景下抗遮挡的运动目标跟踪算法［J］.液晶与显示，2010，25（6）：890－895.Liu Y，Zhang Y F，Dong Y F.Anti－occlusion algorithm of tracking moving object in clutter background［J］.Chinese Journal of Liquid Crystals and Displays，2010，25（6）：890－895.（in Chinese）

［9］ Jung U C，SEUNG H J，XU.FPGA－based real－time visual tracking system using adaptive color histograms［C］／／Proceedings of the 2007th International Conference on Robotics and Biomimetics，Sanya，P.R.China：ICRB，2007：172－177.

［10］ Sheng S H，Kim J，Wang H Z.Generalized kernel－based visual tracking［J］.IEEE Transactions on Circuits and Systems for Video Thechnology，2010，20（1）：119－130.

［11］ AVIDAN S.Ensemble tracking［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2007，29（2）：261－271.

［12］ Collins R T，Liu Y X，Leordeanu M.Online selection of discriminative tracking features［C］／／IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（10）：1631－1643.

［13］ Syend N A，Liu H，Sung K.Incremental learning with support vector machines［C］／／Proceedings of the Workshop on Support Vector Machines at the International Joint Conference on Artificial Intelligence，Stockholm，Sweden：IJCAI，1999：2165－2176.

［14］ 李国正，王猛，曾华军.支持向量机导论［M］.北京：电子工业出版社，2004.Li G Z，Wang M，Zeng H J.An Introduction to Support Vector Machines and Other Kernel－based Learning Methods［M］.Beijing：Publishing House of Electronics Industry，2004.（in Chinese）

［15］ Perez P，Hue C，Vermaak J，et al.Color－Based Probabilistic tracking.［C］∥Lecture Notes in Computer Science，Copenhagan，Denmark：Eccv，2002：661－675.

［16］ The school of Information，University of Edinburgh.CAVIAR Test case Scenarios［DB／OL］.［2011－05－12］／／http：groups.inf.ed.ac.uk／vision／CAVIAR／CAVIARDATA1／.