一种分层Mean Shift目标跟踪算法

一种分层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迭代算法对目标区域特征量聚类,聚类模式点估计,通过聚类分割获得稳定的块,进行聚类块匹配.这样,聚类块可以体现区域的整体特征,能够克服像素受干扰而变化所带来的影响,而且聚类模式点以简洁的方式表达目标的分布特征,提高了匹配的鲁棒性与有效性.第二层,在匹配块内计算像素偏移量,进行像素匹配,取得跟踪目标质心模式点的估计.区域聚类于块状、块模式点聚于跟踪质心,即先块再像素点分层匹配迭代.

1分层MS跟踪算法(HMS)

1.1目标区域颜色与空间联合聚类分析

在基于颜色特征的区域匹配目标跟踪算法中,区域内像素颜色随时间受光照、噪声等影响会发生细微的变化,采用聚类可以提高像素颜色的抗干扰性,而且聚类模式点能以简洁的方式表达目标的分布特征.通常情况下,非参数MS聚类迭代算法及应用[16 17],都是对一幅给定的静态图像进行聚类、区域分割,而在动态图像序列跟踪帧中对目标区域聚类进行分析,目标在运动中除了平移,还会有尺度变化.因此,聚类带宽须能够随目标大小而变化、更新,即对序列帧需进行可变带宽聚类.带宽的更新有两种方式[18]:窗口内所有数据点采用相同尺度带宽核与不同尺度带宽核更新.由于目标区域内前景目标的颜色信息不会发生尺度变化,而位置信息会发生尺度变化,位置数据点是相邻的,则发生近似相同尺度变化,所以,所有数据点采用相同尺度带宽核的更新方式.在文献[17]的基础上,本文给出了适合于动态图像序列帧的MS变带宽聚类如式(1),式中

对目标区域数据点集{xn}Nn=1∈R5

进行自动聚类,收敛于模式点x.

m ω x x

2 nσ,s xn

fj=1xn∈setj

σ,s(x)= m ω x x

2

(1)nj=1xn

∈set

j

σ,s

式(1)中,xn={i,j,r,g,b}是颜色分量{r,g,b}与空间位置分量{i,j}的5D信息数据点;N个数据点预划分在m个子集setj(j=1,···,m)内,m在聚类过程中自动更新;ω(·)为带宽为σ的高斯核函数,聚类带宽σ控制聚类程度和聚类数;s是更新聚类带宽的尺度因子,由目标尺度变化大小来确定.

目标模型区域的颜色与空间5维联合信息按式(1)进行聚类分析,形成d个聚类块,每一聚类块的模式点Ck={Cxk,Cuk},k=1,···,d,其中Cxk为聚类空间位置,Cuk为聚类颜色,每类的像素数为nk.颜色与空间位置的联合聚类分析,使得目标区域特征表达鲁棒性强.图1显示了两种不同的RGB彩色目标模型区图像:颜色分布变化大的球员模型区和颜色分布变化细腻的人脸模型区,及经过5维空间、颜色联合特征聚类后的自适应聚类分割块.根据目标颜色分布变化情况,选择不同的聚类带宽,实现不同程度的聚类.球员各部分颜色分布变化大,设聚类带宽σ为38,自适应聚为10类.而相对于球员整体目标来讲,人脸是局部区域目标,其变化细腻,聚类带宽设为14,聚为84类,视觉上与原始图

(a)球员模型区(b)聚类的球员(a)Playerregion

(b)5Dclusteredplayer

(c)人脸模型区(d)聚类的人脸(c)Faceregion

(d)5Dclusteredface

图1两种不同的颜色分布目标模型区及5D聚类分析Fig.1

Twoobjectmodelregionswithdistinctcolordistributionsandtheir5Dclusteringanalysis

一种分层Mean Shift目标跟踪算法

像差别不大.

1.2目标模型聚类模式点描述

MS跟踪迭代算法是以目标区前景(fg)颜色信息引导及驱动得到跟踪平移量,所以目标模型的建立需去除掉背景.背景(bg)像素的混入对跟踪效果影响非常大,前景与背景能否准确分离是影响目标模型及MS跟踪性能好坏的关键要素之一.给定的目标区域经过颜色与空间的联合特征聚类分析,形成聚类分割块,并以聚类模式点Ck(k=1,···,d)描述.下面首先判别每一聚类块属于前景还是背景,然后再提取出前景类,建立目标模型描述.

图像区域矩特征具有不变性,目标质心是一个有效的矩特征,计算目标质心可进行前景与背景的区分判别,目标质心的计算过程如下:

1)初始化质心为目标区域中心xc=x (x 为目标模型区中心);

2)目标区域前景聚类块的组成部分是有序连接的,前景类、背景类与目标区域质心的距离远近不同,利用目标区域内各聚类的模式点Ck与质心的距离,区分判别

fg和bg,即

Ck∈fg,若|Cxk xc|<Td

C(2)

k∈bg,否则

聚类模式点位置距离质心xc较远者标记为bg,Td为最大距离阈值.

3)由于背景像素分布是随机的,可能会出现背景类模式点位置距离目标质心较近的情况,因此仅用距离信息可能会存在误判.这里,在步骤2)的基础上,进一步对被判为fg的聚类块及其模式点Ck进行分析,对目标区域聚类块计算对数似然函数比L(k)[19],通过比值

L的正负判别fg和bg,即

Ck∈fg,若L(k)>0

C≤0

(3)

k∈bg,若L(k)4)去掉背景类,再采用聚类模式点Ck定义质

心

Cxk·H(Cuk)

xCk∈fg

c=

H(Cu(4)

k)

Ck∈fg

其中H(Cuk)是该类在HSV色彩空间的H分量值,作为计算质心的图像属性.

5)重复步骤2)～4)求xc,直到质心的位置趋于不变.同时,也得到越来越准确的前景,目标区前景与质心相互制约、相互影响.

因此,根据图像矩特征去分离前景与背景,可以将目标区域d类分解为属于前景的有df类、属于背

景的有db类(d=df+db).这样,目标模型的聚类模式点描述为:Sxk={Cxk,Cuk},k=1,···,df.图2显示了图1目标区在联合空间多维信息聚类后前景与背景分离,提取出前景目标建立的聚类模式点描述的目标模型.球员前景目标呈区域片状,而人脸聚类程度低,几乎还是呈点状.

(a)球员模型(b)人脸模型(a)Playermodel

(b)Facemodel

图2聚类模式点描述的目标模型Fig.2Objectmodelinthedescriptionof

clustermodalpoints

1.3聚类块与像素点分层匹配的相似度量函数

给定目标模型区域抽样点集合Sx和核函数,利用核密度估计法对目标区的空间位置与颜色联合概率密度函数(PDF)估计,在前景颜色信息的引导下进行目标跟踪.假定Sx={xi,ui}Ni=1是源于PDF为P(x,u)分布的抽样点集合,xi为像素二维坐标点,ui=u(xi)为在位置xi处{r,g,b}三维彩色信息,则P(x,u)用多变量联合核密度函数估计[20]为

2 P (x,u)=1 N x x i N

ω k

2 u uii=1

σ h (5)

其中ω(·),k(·)分别是带宽为σ,h的高斯核函数,记作ωσ(·),kh(·).

经过以上聚类分割分析,确定了目标模型区域的前景类和背景类,建立了目标模型的聚类模式点描述,则目标模型区域前景的联合概率密度函数估计可表示为

P (x,u)=1 df nk Nω x x 2 2 i k

f

u ui k=1xi

∈Cσh k

其中N (6)

df

f=k=1nk是前景类的总像素数.

相应的后续跟踪帧中,候选目标区域的抽样点

集合Sy={yj,vj}Mj=1,聚类为d

类,聚类中心Cl={Cyl,Cvl},l=1,···,d ,前景有df 类,背景有db 类,每类的像素数为n l.目标候选模型的聚类模式

一种分层Mean Shift目标跟踪算法

点描述为:Syl={Cyl,Cvl},l=1,···,df .

通过匹配法在后续帧的候选区域找出与目标模型区域前景相似的前景,本文以两者前景颜色为引导信息,首先在两者间颜色相近的聚类块之间进行搜索匹配,即对目标模型区域df个前景聚类块与目标候选模型区域df 个前景聚类块进行匹配.

采取在HSV空间下,通过两者颜色的差别来衡量其是否相匹配,按以下两步为目标模型描述的每一类Ck找到与候选目标模型描述类Cl中最接近的相匹配的类.

1)将两者的聚类中心以颜色分量Cuk,Cvl的H分量值从大到小进行排序;

2)对于每一个值k,计算Cuk与Cvl的H分量的差别,取argminl|Cvl Cuk|且满足条件|Cvl Cuk|<Tc,得到第l类.若l存在,即为与Ck最相匹配的是Cl;若l不存在,即候选区中没有与其相匹配的类.其中1<k<df,1<l<df ,Tc是颜色相匹配所容许的误差范围阈值.

若每类模式点Ck都找到对应的类模式点Cl,设l=k=1,···,d,候选模型区与目标模型区的聚类块匹配对如图3(a).若找不到对应类或对应的数量太少,则重新选择目标.相比而言,原MS匹配法需逐点搜索(如图3(b))所有像素点对进行匹配.

在目标模型与目标候选模型的聚类模式点匹配后,即在前景聚类块匹配基础上,进一步再在匹配块内进行像素匹配,计算目标的运动平移量,定义目标模型区与候选模型区的相似度量函数为式(7).

式(7)中,δ(·)是delta函数,当候选目标模型聚类模式点Cl与目标模型聚类模式点Ck相匹配时为1,否则为0;Np为相匹配的总像素数;n l,nk分别为第l ,k类的像素数.即,在对应类块内进行像素点匹配搜索,而在非对应类区不进行任何操作,

只有d对对应类作累加.

(a)聚类匹配对(a)Pairsofmatchunder

cluster

(b)非聚类逐点匹配(b)Pointbypointmatch

undernon-cluster

图3Fig.3

聚类匹配与非聚类匹配

Clusterandnon-clustermatches

1.4分层MS迭代跟踪算法

在目标模型描述的前景颜色信息的引导下,先聚类块再像素点逐级分层确定两者相接近的待搜索像素空间.设目标模型区域中心为x ,跟踪帧候选区中心为y,若只考虑其平移运动,则式(7)可表示为式(8)的形式.

通过最大化目标模型与候选模型的相似度量函数J,确定跟踪目标在候选区的位置.采用梯度下降MS迭代算法寻找式(8)的极值.关于候选区位置中心向量y的梯度定义为

L(y)=

J(y)J(y)

(9)

其中 J(y)的定义见式(10).式(10)中, yj=

(yj y), xi=(xi x ),ω(·)表示求导.则进一步得到式(11).

在式(11)迭代确定目标在候选区位置y的计算

n df df nkl 1

J(Sxk,Syl)=δ(Cl,Ck)ωσ(yj xi)kh(vj ui)

Npl=1k=1

y∈Cx∈C

j

l

i

k

(7)

n df df nkl 1

J(Sxk,Syl)=δ(Cl,Ck)ωσ((yj y) (xi x ))kh(vj ui)

Npl=1k=1

y∈Cx∈C

j

l

i

k

(8)

n df df nkl

δ(Cl,Ck) J(y)=( xi yj)ωσ( yj xi)kh(vj ui)

l=1k=1

yj∈Clxi∈Ck

(10)

n df df nkl δ(Cl,Ck)(yj xi)ωσ( yj xi)kh(vj ui)

ms(y)=

l=1k=1

yj∈Clxi∈Ck

n dfdfnkl

δ(Cl,Ck)ωσ( yj xi)kh(vj ui)

l=1k=1

yj∈Clxi∈Ck

+x

(11)

一种分层Mean Shift目标跟踪算法

过程中,相匹配的前景类块内,采用FGF算法[7]计算高斯核,而本文给出结合邻域一致性[17]分层近似计算,效率更高,过程如下:

首先,第一层匹配中,MS聚类过程有Cxk= nk nl

(1/nk)xi∈Ckxi,Cyl=(1/n l)yj∈Clyj.因此,由邻域一致性,每对相匹配的聚类块有

nlnk yj∈Clxi∈Cknk xi∈Ck

ui)≈nk·n l·Cyl·ωσ((Cyl y) (Cxk x))×

n l·Cyl·ωσ((Cyl y) (xi x))kh(vCyl

其中,s是图像序列帧之间目标尺度变化因子.

相应地,通过函数J对目标位置y及尺度s求归一化梯度,可得 y与s更新迭代式(16) 和(17),其中,ωσ,s(·)=ω

2

Cxk x Cy yl σs

.

yjωσ((yj y) (xi x ))kh(vj ui)≈

kh(vCyl uCxk)≈nk·n l·Cyl·ωσ(·)kh(·)

nlnk

yj∈Clxi∈Ck

(12)

xiωσ((yj y) (xi x ))kh(vj ui)≈

(13)

HMS跟踪算法的整个原理过程如图4(见下页)

所示.首先手工选定待跟踪的目标模型区,对目标区的颜色与位置5D数据联合聚类分析及去背景,建立目标模型Sxk;然后在后续帧中分层匹配搜索目标,建立目标候选模型Syl;目标模型与候选模型聚类块模式点匹配后,再进行像素点匹配.候选区初始位置中心为y0,尺度为s0,执行式(16)和(17)迭代更新当前帧目标候选区中心y,尺度s,直至其收敛.

调节聚类带宽σ,可实现不同程度的聚类,当带宽非常小,以至于每类的大小nk=1时,则转化为Yang[7]的MS迭代跟踪.

2算法的复杂性分析

匹配驱动的MS跟踪,不计算直方图,直接度量目标模型区与候选区的相似性,如文献[7]没有利用颜色的引导性,在搜索过程中逐点比较目标模型区xi与候选区yj,匹配计算量为(M×N)2,并且每搜索一步还需计算所有数据点的核函数及计算一阶矩.与之相比,本文分层计算,先聚类块匹配,再像素匹配,结合邻域一致性,最后只需计算d个聚类模式点的核函数及数乘运算即可计算出目标运动的运动量.本文算法的计算代价:第一层,设聚类块匹配的计算量为N1,其中包括5维信息聚类过程,设其计算量为Nc,Nc的大小主要取决于聚类带宽σ[16 17],其次与子集数m及数据点数量N有关.σ越小,计算

n l·nk·Cxk·ωσ(·)kh(·)

所以,每一匹配对求和≈nk·n l·ωσ(·)kh(·)(Cyl Cxk),则式(11)最终化简为HMS跟踪迭代式(14).

在图像序列帧跟踪过程中,如果目标伴随有尺度变化,则根据文献[7,21]重新定义相似度量函数为

dfdf 1

J(Sxk,Syl)=δ(Cl,Ck)×

Np

l=1k=1

n l

nk

yj∈Clxi∈Ck

2 √ yj xi kh(vj ui)ω (15)

dfdf

δ(Cl,Ck)nk·n l·ωσ(·)kh(·)(Cyl Cxk)

ms(y)=l=1

k=1

dfdf

l=1k=1

+x

δ(Cl,Ck)nk·n l·ωσ(·)kh(·)

(14)

dfdf

Cxk)δ(Cl,Ck)nk·n l·ωσ,s(·)kh(·)(Cyl sC

ms(y)=

l=1k=1

dfdf

l=1k=1

dfdf

x +sx

δ(Cl,Ck)nk·n l·ωσ,s(·)kh(·)

Cyl

sσ

2

Cxkσ

2

s

(16)

δ(Cl,Ck)nk·n l·ωσ,s(·)kh(·)1+

dfdf

l=1k=1

ms(s)=

l=1k=1

(17)

δ(Cl,Ck)nk·n l·ωσ,s(·)kh(·)

一种分层Mean Shift目标跟踪算法

生的计算量Nm也很小.那么,N1=Nc+Nm.第二层,像素匹配的计算量为N2,若聚类块匹配后直接运算,d对相匹配的聚类逐点比较产生的计算量

2

N2=d×(nk×n l).而本文给出结合邻域一致性分层匹配,只需计算聚类模式点近似比较N2=d×1.令Ns为适应目标尺度s的变化而迭代搜索的尺度数目的计算量,那么执行一次分层MS匹配迭代算法总的计算代价为C=Ns(N1+N2)=Ns(Nc+Nm+d×1).显然,本文的匹配计算量C,除聚类计算量Nc较大之外,其他都是几个模式点的匹配及数乘运算.

3实验

实验平台环境:硬件为主频1.5GHz,内存512M的R50e的IBM笔记本电脑,软件为Matlab7.1.通过大量真实实验调试,与其他两种算法[3,7]相比,本文算法是有效可行的.在跟踪准确性方面,抗光照、遮挡、阴影噪声干扰等鲁棒性方面强于经典方法,搜索迭代次数随所选目标不同而有所不同,略高于经典方法.下面给出一些本文算法跟踪结果及性能分析,第一帧手动初始化目标模型区,匹配允许误差范围阈值Tc=1.

实验1.户外足球比赛图像序列,图像大小为720×560像素,共285帧.球员之间相互遮挡,存在较多的颜色特征相似的目标,对快速运动的球员目标进行跟踪.第一层初始聚类带宽及前景/背景分离距离参数为[σ,Th]=[35,18],第二层核函数带宽[σ,h]=[18,12].设定的聚类带宽较大,聚类程度较高,自适应聚类为15类.中途101～120帧、142～150帧出现运动目标遮挡及碰撞.序列帧90,105,114,162,188,233跟踪结果如图5所示,每帧迭代

图4

Fig.4

HMS跟踪原理框图

BlockdiagramofHMStrackingprocess

量越大,得到的聚类数d越大.σ太大,会使聚类分割丢掉太多细节;σ太小,不能起到增强颜色特征的鲁棒性的作用(本文初始σ参数是经过反复实验的经验值).设聚类后求质心、前景/背景分离、匹配模式点的计算量为Nm,由于聚类个数d很小,因而产

图5Fig.5

足球赛运动球员HMS算法跟踪结果

TrackingresultsoffootballplayerusingHMS

一种分层Mean Shift目标跟踪算法

图6

Fig.6

文献[3](左)与本文(右)每帧迭代次数的对比

Thenumbersofiterationswithregardtotheframeindexusingreference[3](left)andHMS(right)

次数如图6所示.与文献[3]算法相比,本文算法平均每帧迭代2.2512次,文献[3]算法为2.0461次.

实验2.室内人脸图像序列,图像大小为128×96像素,共100帧.人脸从正面转向反面,再转过来,遮挡严重.相对于实验1而言,实验2跟踪的目标颜色分布较细腻、变化较小.第一层初始聚类带宽及前景/背景分离距离参数为[σ,Th]=[26,20],第二层核函数带宽[σ,h]=[12,10].设定的聚类带宽较小,聚类程度较低.图7显示了本文算法与文献[3]算法对序列帧18,24,90的跟踪结果.与其他两种MS算法(文献[3]中的MS算法1,文献[7]中的MS算法2)相比,目标质心的跟踪误差如图8所示,本文算法的准确性更高

.

比,目标质心的跟踪误差如图10(见下页)所示,显然,本文算法的跟踪准确性更高.

从以上几个实验的跟踪效果图及性能图比较分析来看,与其他两种MS算法[3,7]相比,本文算法中,聚类块模式点增强了颜色特征表征的鲁棒性,在一定程度上克服了光照、噪声等的影响,

可获取稳定的

图7Fig.7

本文算法(上)与文献[3](下)的人脸跟踪结果TrackingresultsoffaceusingHMS(uprow)and

reference[3](downrow)

实验3.户外强光照下穿梭于草地、沙漠、公路

上的车辆图像序列.车辆较长时间行驶在强光照下,阴影影响较严重,目标的尺度变化大,背景环境变化大.图像序列来源于PETS2005,图像大小为160×107像素,共1810帧,并提供有真实数据.设定的聚类带宽及前景/背景分离距离参数为[σ,Th]=[30,23],核函数带宽[σ,h]=[18,12],聚为9类.序列帧60,210,580,1250,1510,1800的跟踪结果如图9(见下页)所示.与其他两种MS算法[3,7]相

图8Fig.8

室内人脸序列的文献[3,7]算法与本文

算法的跟踪误差比较

Comparisonoftrackingerrorsoffacesequenceindoorforthreedi erentalgorithms,

references[3,7],andHMS

一种分层Mean Shift目标跟踪算法

运动块,先聚类块匹配、再像素匹配提高了目标匹配的有效性,跟踪效果更好,分层匹配算法有效可行.

4结论

本文提出了一种分层Meanshift目标跟踪算法,通过多组实验,分别从直观跟踪效果、迭代运算次数和跟踪误差方面,与其他两种MS算法进行比较,分析了本文给出算法的性能及有效性.本文的贡献在于:1)将区域匹配的MS目标跟踪算法分层执行,提出分层搜索的思想,即先块匹配,再像素匹配;图9穿梭于草地、沙漠公路上的车辆HMS算法跟踪结果Fig.9Trackingresultsofrunningcarinthegrass,

desertandroadusing

HMS

图10车辆序列中文献[3,7]算法与本文算法跟踪误差比较Fig.10

Comparisonoftrackingerrorsincarsequenceforthreealgorithms,references[3,7]andHMS

2)以聚类块模式点描述目标模型,利用邻域一致性计算目标运动平移量,给出分层的MS匹配迭代跟踪算法.将N个数据点收敛于d个模式点,再收敛于目标质心模式点.与经典方法相比,分层处理提高了目标模型表达与匹配的鲁棒性,无需逐点计算高斯核,大大节省了计算量,但是增加了聚类的运算.

本文算法存在的主要问题是:在跟踪过程中,目标(参考)模型描述没有在线更新;环境的变化可能导致目标的前景颜色发生较大变化,而本文的匹配误差允许阈值不能设定的太大,这样可能使目标丢失而跟踪失败.因此将来的工作是着重解决如何在线更新目标(参考)模型描述的问题,以获得更为鲁棒的跟踪,以及研究效率更高的聚类算法.

References

1ComaniciuD,RameshV,MeerP.Real-timetrackingofnonrigidobjectsusingmeanshift.In:ProceedingsofIEEEComputerSocietyConferenceonComputerVisionandPat-ternRecognition.HiltonHeadIsland,USA:IEEE,2000.142 1492FukanagaK,HostetlerLD.Theestimationofthegradi-entofadensityfunctionwithapplicationsinpatternrecog-nition.IEEETransactionsonInformationTheory,1975,21(1):32 403ComaniciuD,RameshV,MeerP.Kernel-basedobjecttracking.IEEETransactionsonPatternAnalysisandMa-chineIntelligence,2003,25(5):564 5754BircheldST,RangarajanS.Spatiogramsversushistogramsforregion-basedtracking.In:ProceedingsofIEEECom-puterSocietyConferenceonComputerVisionandPatternRecognition.SanDiego,USA:IEEE,2005.1158 11635LiPH.Aclusteringbasedcolormodelandfastalgorithmforobjecttracking.In:Proceedingsofthe18thInternationalConferenceonPatternRecognition.HongKong,China:IEEE,2006.671 6746LiPei-Hua.Animprovedmeanshiftalgorithmforobjecttracking.ActaAutomaticaSinica,2007,33(4):347 354(李培华.一种改进的MeanShift跟踪算法.自动化学报,2007,33(4):347 354)

7YangCJ,DuraiswamiR,DavisLS.E cientMean-Shifttrackingviaanewsimilaritymeasure.In:ProceedingsofIEEEComputerSocietyConferenceonComputerVision

一种分层Mean Shift目标跟踪算法

andPatternRecognition.SanDiego,USA:IEEE,2005.176 183

8YangCJ,DuraiswamiR,ElgammalA,DavisLS.Real-timeKernel-basedTrackinginJointFeature-spatialSpaces,TechnicalReportCS-TR-4567,ComputerScienceDepart-ment,UniversityofMaryland,USA,20049ElgammalA,DuraiswamiR,DavisLS.Probabilistictrack-inginjointfeature-spatialspaces.In:ProceedingsofIEEEComputerSocietyConferenceonComputerVisionandPat-ternRecognition.Madison,USA:IEEE,2003.781 78810LeungAP,GongSG.Mean-Shifttrackingwithrandom

sampling.In:Proceedingsofthe17thBritishMachineVi-sionConference.Edinburgh,British:UniversityTrierPress,2006.729 73811NaeemA,MillsS,PridmoreT.Structuredcombinationof

particle lterandkernelMean-Shifttracking.In:Proceed-ingsofthe21stInternationalConferenceonImageandVi-sionComputing.GreatBarrierIsland,NewZealand:IEEE,2006.1 612HanB,JooSW,DavisLS.Probabilisticfusiontrackingus-ingmixturekernel-basedBayesian ltering.In:Proceedingsofthe11thInternationalConferenceonComputerVision.Janeiro,Brazil:IEEE,2007.1 813ThomasM,KambhamettuC.AnapproximationtoMean-Shiftviaswarmintelligence.In:Proceedingsofthe18thIn-ternationalConferenceonToolswithArti cialIntelligence.WashingtonD.C.,USA:IEEE,2006.583 59014ParkM,LiuYX,CollinsRT.E cientmeanshiftbelief

propagationforvisiontracking.In:ProceedingsofIEEEConferenceonComputerVisionandPatternRecognition.Alaska,USA:IEEE,2008.1 815HanB,ComaniciuD,ZhuY,DavisLS.Sequentialkernel

densityapproximationanditsapplicationtoreal-timevi-sualtracking.IEEETransactionsonPatternAnalysisandMachineIntelligence,2008,30(7):1186 119716MiguelA,´Carreira-Perp n´an.Fastnonparametricclustering

withGaussianblurringMean-Shift.In:Proceedingsofthe23rdInternationalConferenceonMachineLearning.Pitts-burgh,USA:IEEE,2006.153 16017ZhangK,TangM,KwokJT.Applyingneighborhoodcon-sistencyforfastclusteringandkerneldensityestimation.In:ProceedingsofIEEEComputerSocietyConferenceonComputerVisionandPatternRecognition.SanDiego,USA:IEEE,2005.1001 100718ComaniciuD,RameshV,MeerP.Thevariablebandwidth

meanshiftanddata-drivenscaleselection.In:Proceedingsofthe8thIEEEInternationalConferenceonComputerVi-sion.Vancouver,Canada:IEEE,2001.438 44519CollinsRT,LiuYX,LeordeanuM.On-lineselection

ofdiscriminativetrackingfeatures.IEEETransactionsonPatternAnalysisandMachineIntelligence,2005,27(10):1631 164320ParzenE.Onestimationofaprobabilitydensityfunction

andmode.AnnalsofMathematicalStatistics,1962,33(3):1065 107621RangarajanA,ChuiH,BooksteinFL.Thesoftassignpro-crustesmatchingalgorithm.In:Proceedingsofthe15thIn-ternationalConferenceonInformationProcessinginMedi-calImaging.Poultney,USA:IEEE,1997.29 42

许海霞

湖南大学电气与信息工程学院

自动化重点实验室博士研究生.主要研究方向为计算机视觉,目标跟踪和摄像机标定.本文通信作者.E-mail:xhxia2002@(XUHai-Xia

Ph.D.candidateat

theKeyLaboratoryofAutomation,In-stituteofElectricalandInformationEngineering,HunanUniversity.Herresearchinterestcoverscomputervision,objecttracking,andcameracalibration.Correspondingauthorofthispaper.)

王耀南湖南大学电气与信息工程学院

教授.主要研究方向为机器视觉,智能图像处理和智能机器人.E-mail:yaonan@(WANGYao-Nan

Professoratthe

InstituteofElectricalandInformationEngineering,HunanUniversity.Hisre-searchinterestcoverscomputervision,intelligentimageprocessing,andintelligentrobot.)

袁小芳湖南大学电气与信工程学院自

动化重点实验室博士研究生.主要研究方向为智能控制,神经网络.E-mail:yuanxiaof@(YUANXiao-Fang

Ph.D.candi-dateattheKeyLaboratoryofAutoma-tion,InstituteofElectricalandInfor-mationEngineering,HunanUniversity.Hisresearchinter-estcoversintelligentcontrolandneuralnetworks.)

周维湘潭大学信息工程学院硕士研

究生.主要研究方向为网络与信息安全,图像处理.

E-mail:bigdaddy2004@(ZHOUWei

Masterstudentat

theInstitueofInformationEngineer-ing,XiangtanUnivertity.Hisresearch

interestcoversnetworkandinformationsecurity,andimageprocessing.)

朱江湖南大学电气与信工程学院自

动化重点实验室博士研究生.主要研究方向为计算机视觉,机器人导航控制.E-mail:jiang126@(ZHUJiang

Ph.D.candidateatthe

KeyLaboratoryofAutomation,Insti-tuteofElectricalandInformationEn-gineering,HunanUniversity.Hisresearchinterestcoverscomputervisionandrobotnavigationcontrol.)

本文来源：https://www.bwwdw.com/article/9jhm.html