一种分层Mean Shift目标跟踪算法
第35卷第4期2009年4月
自动化学报ACTAAUTOMATICASINICA
Vol.35,No.4April,2009
一种分层MeanShift目标跟踪算法
许海霞1,2
王耀南1
袁小芳1
周维2
朱江1
摘要针对经典Meanshift(MS)目标跟踪算法的颜色特征鲁棒差、匹配迭代复杂的缺点,提出一种分层Meanshift(Hierarchicalmeanshift,HMS)目标跟踪算法.首先通过MS迭代将目标区域特征空间的数据点聚类于模式点,使得以简洁的方式描述前景跟踪目标,建立目标模型与目标候选模型的聚类模式点描述,进行聚类块匹配.然后,导出聚类块模式点匹配下的相似度量函数,进行像素点匹配,结合邻域一致性,计算像素平移量,分层估计序列帧中跟踪目标质心模式点的位置,并给出HMS匹配迭代跟踪算法.实验结果表明,与其他两种MS跟踪算法相比,HMS既能提高序列帧跟踪目标表达与匹配的鲁棒性,又无需匹配所有数据点,算法简洁且有效可行.关键词目标跟踪,分层Meanshift,聚类模式点,匹配中图分类号TP391
AHierarchicalMeanShiftAlgorithmforObjectTracking
XUHai-Xia1,2
WANGYao-Nan1
YUANXiao-Fang1
ZHOUWei2
ZHUJiang1
AbstractWeproposeahierarchicalmeanshift(HMS)algorithmforobjecttracking.Firstly,clustermodalpointsareobtainedbymean-shiftiterativelyprocessingallthedatapointsintheregionsothattheycanrepresentforegroundobjectinasuccinctmanner.Thetargetmodelandthetargetcandidatemodelaredescribedbytheclustermodalpoints,andmatchprocessesofclusteredblocksareperformed.Then,onthebasisofclusterblocksmatch,similaritymeasurefunctionissetuptomatchbetweentargetmodelandtargetcandidateatpixellevel.Andthepixelshiftvectoroftargetiscalculatedwiththeintroductionoftheneighborhoodconsistencyconcept.So,thecentroidoftrackingobjectisgotlayerbylayerintheconsecutiveframes,andtheHMSmatchiterationforobjecttrackingispresented.ExperimentalcomparisonswithothertwoMSalgorithmsdemonstratethevalidityandperformanceoftheproposedalgorithm.Keywords
Objecttracking,hierarchicalmeanshift(HMS),clustermodalpoint,match
运动目标跟踪是计算机视觉、人机交互等的研究热点之一.常用的跟踪算法有Kalman、Particle、Meanshift(MS)及其各种变形、改进算法.MStrack最初是Comaniciu[1]于2000年将核密度估计[2]用于跟踪而提出的一种高效的实时跟踪算法,得到了广泛的研究与应用.它是基于目标颜色特征的区域匹配跟踪,通过对目标模型区与后续帧中候选区的颜色直方图进行比较,用Bhattacharyya系数、KullbackLeibler距离等方式度量其相似度,为以后的MS跟踪算法奠定了基础.进一步的改进算法从驱动MS迭代方式来看可以归为以下几类:1)
收稿日期2007-11-06收修改稿日期2008-06-26
ReceivedNovember6,2007;inrevisedformJune26,2008国家自然科学基金重点项目(60835004),国家高技术研究发展计划(863计划)(2007AA04Z244,2008AA04Z214),湖南省教育厅项目(07C073)资助
SupportedbyNationalNaturalScienceFoundationofKeyProgramofChina(60835004),NationalHighTechnologyRe-searchandDevelopmentProgramofChina(863Program)(2007AA04Z244,2008AA04Z214),andFoundationofHunanEducationalCommittee(07C073)
1.湖南大学电气与信息工程学院长沙4100822.湘潭大学信息工程学院湘潭411105
1.SchoolofElectricalandInformationEngineering,HunanUniversity,Changsha4100822.SchoolofInformationEngi-neering,XiangtanUniversity,Xiangtan411105DOI:10.3724/SP.J.1004.2009.00401
建立目标模型直方图驱动的MS跟踪算法,通过不断完善目标模型直方图的表达来提高跟踪性能.如基于核的跟踪[3],在分析前景的同时,加入对背景模型的考虑;空间直方图模型[4],同时考虑了目标区的彩色信息及像素间的空间位置关系,空间信息的引入使得获取目标颜色信息范围更合理,体现了局部性的考虑;颜色聚类的高斯分布直方图[5 6],引入聚类,使得直方图量化等级有了依据,且合理、准确.2)匹配(配准)驱动的MS跟踪算法,不计算颜色直方图,而直接度量两者的相似度,如基于相似度量的MS跟踪算法[7 8].该类MS算法给定抽样点、核函数、目标的空间位置与颜色联合概率密度函数(Probabilitydensityfunction,PDF),定义目标区与候选区的PDF的相似度量函数,逐点搜索比较,直到找到最佳匹配区,其优点是区别能力强.3)在概率表达及贝叶斯理论构架下建立目标模型驱动MS迭代,如联合特征下目标模型的概率表达迭代[9],随机抽取粒子迭代[10],MS迭代与粒子滤波器相结合[11 12],用粒子群优化(Particleswarmoptimization,PSO)算法减小MS迭代的样本数据点[13],均值平移置信传播(Meanshiftbeliefpropagation,MSBP)算法[14]把MS放在置信传播(Beliefpropagation,BP)框架下,BP生成样本,
一种分层Mean Shift目标跟踪算法
MS迭代加权样本.一种新的核密度估计法[15]用于
视觉跟踪,将核密度二次计算演变成线性计算.上述算法大多是通过减小参与迭代的样本数据量来提高计算效率
.
MS跟踪是基于目标颜色特征的区域匹配跟踪,区域颜色的分布是随机的、不连续的点状或小区域
片.传统MS跟踪算法存在以下不足:直方图驱动时,直方图的量化是均匀的、盲目的,造成没必要的存储和计算开销[6].而匹配(配准)驱动时,1)序列帧目标区域图像的像素颜色随时间、光照等影响会发生变化,直接匹配鲁棒性差;2)区域中所有数据参与迭代运算,需计算所有数据点的核函数与一阶矩,运算量大;3)匹配过程中,不能充分利用目标区域颜色信息的引导作用去减小搜索像素空间范围,造成没必要的匹配比较与计算量.
针对以上问题,本文提出一种分层MS跟踪算法,将目标模型区域与目标候选区域的整个匹配跟踪过程分为两层进行.第一层,MS迭代算法对目标区域特征量聚类,聚类模式点估计,通过聚类分割获得稳定的块,进行聚类块匹配.这样,聚类块可以体现区域的整体特征,能够克服像素受干扰而变化所带来的影响,而且聚类模式点以简洁的方式表达目标的分布特征,提高了匹配的鲁棒性与有效性.第二层,在匹配块内计算像素偏移量,进行像素匹配,取得跟踪目标质心模式点的估计.区域聚类于块状、块模式点聚于跟踪质心,即先块再像素点分层匹配迭代.