目标一起跟踪

1994-2010ChinaAcademicJournalElectronicPublishingHouse.
Allrightsreserved.
http://www.
cnki.
net第22卷第4期Vol.
22No.
4控制与决策ControlandDecision2007年4月Apr.
2007收稿日期:2005211216;修回日期:2006201203.
基金项目:国家自然科学基金项目(60104009);山东省自然科学基金项目(Z2005G03).
作者简介:常发亮(1965—),男,山东寿光人,教授,从事模式识别、机器视觉等研究;马丽(1982),女,山东济宁人,硕士,从事计算机视觉、模式识别等研究.
文章编号:100120920(2007)0420418205视频序列中面向人的多目标跟踪算法常发亮,马丽,乔谊正(山东大学控制科学与工程学院,济南250061)摘要:针对视频序列中人的跟踪问题,提出一种基于运动检测的多目标跟踪算法.
跟踪系统由运动目标检测、关联矩阵建立、特殊情况判断及处理以及轨迹关联4部分构成.
提出一种基于改进的c2均值聚类的自适应运动分割方法;不同情况下建立不同的关联矩阵,以准确判断实际场景状况;对遮挡问题作出处理,在两个目标遮挡不严重的情况下,分别采用均值漂移算法对其进行跟踪.
实验结果表明,该算法具有较强的鲁棒性,能有效实现复杂场景下多目标跟踪.
关键词:多目标跟踪;运动检测;轨迹关联;遮挡;均值漂移中图分类号:TP391文献标识码:AHumanorientedmulti2targettrackingalgorithminvideosequenceCHANGFa2liang,MALi,QIAOYi2zheng(SchoolofControlScienceandEngineering,ShandongUniversity,Ji'nan250061,China.
Correspondent:ChangFa2liang,E2mail:flchang@sdu.
edu.
cn)Abstract:Aimingattrackinghumaninvideosequence,amulti2targettrackingalgorithmbasedonmovingdetectionisproposed.
Trackingsystemiscomposedoffourparts:Movingtargetsdetection,associationmatrixforming,specialcasesestimationandhandling,andtrackassociation.
Anadaptivemovingsegmentationmethodbasedonimprovedc2meanclutterispresented.
Differentassociationmatrixindifferentconditionisusedtoestimatetheactualscenestatesaccurately.
Handlingforocclusionisachieved,andinthecaseofmildocclusionoftwotargets,meanshiftalgorithmisappliedtotrackthemseparately.
Experimentalresultsshowthatitisrobustandhasgoodmulti2targettrackingperformancesundercomplexbackground.
Keywords:Multi2targettracking;Movingdetection;Trackassociation;Occlusion;Meanshift1引言面向人的视频跟踪技术是计算机视觉研究的难点之一,在安全监控、虚拟现实、人机交互等领域有着非常重要的实用价值和广阔的发展前景.
著名的基于运动检测的面向人的跟踪系统有Pfinder[1]和W4[2].
其中Pfinder能够对室内的单个人体进行检测、跟踪和行为解释;W4则能在户外跟踪多个人体和人体各主要部分,并可回答Who,Where,When,What等问题,解释目标行为.
文献[325]是基于运动检测的可以解决遮挡问题的多目标跟踪算法,利用目标的形状特征[3]或颜色特征[4]在遮挡期间跟踪目标,或在遮挡后辨识原目标[5].
本文针对人的跟踪中常出现的变形、遮挡以及多目标跟踪中常出现的目标合并、分裂、消失、新增等情况,提出基于运动检测的多目标跟踪算法.
系统主要由运动目标检测、关联矩阵建立、特殊情况判断及处理、轨迹关联等4部分构成.
首先利用背景差分进行运动目标检测,提出基于改进的c2均值聚类的自适应运动分割方法,结合背景的实时更新来准确提取运动目标;然后在不同情况下建立不同的关联矩阵,并根据关联矩阵判断特殊情况的发生,特别是对人的遮挡(对应合并、分裂)问题作出处理;最后进行当前观测目标与已有轨迹的正确关联.
图1为跟踪系统的结构框图.
2运动目标检测背景差分法是运动目标检测的重要方法,常见的背景模型有高斯模型[1]、混合高斯模型[6]及非参数模型[7]等.
文献[8]利用双背景进行运动目标检测.
本文将改进的c2均值聚类算法用于运动目标的自动分割,结合背景实时更新保证目标检测的实时1994-2010ChinaAcademicJournalElectronicPublishingHouse.
Allrightsreserved.
http://www.
cnki.
net第4期常发亮等:视频序列中面向人的多目标跟踪算法图1多目标跟踪系统结构框图性和准确性,有效克服了通常的固定分割阈值难以适应场景变化的缺点.
2.
1自适应运动分割在背景与当前帧的差分图像中,背景点对应值较小,运动目标点对应值较大.
将差分值聚成两类,分别代表背景和目标,聚类的收敛相当于运动目标的分割.
当前图像I与背景图像M的差分图像D为D(x,y)=|I(x,y)-M(x,y)|.
(1)选择背景的初始类心Z(0)1为(5,5,5),前景目标的初始类心Z(0)2为(50,50,50),前景与背景的初始标准差比为p(0)=(3,3,3),采用基于马氏距离的改进的c2均值算法对RGB三个颜色分量分别聚类.
若点(x,y)的RGB三个颜色分量都属于背景,则该点被判断为背景点;否则为目标点.
对于第i次迭代,ifd(Dj(x,y),Z(i)1j)*p(i)jn(k-1),(4)其中n(k)为第k次迭代时的目标点数量.
第k3次的迭代结果作为运动目标分割的初始结果;然后进行去噪,将面积小于一定阈值的连通成分去除(实验中阈值选为40);最后进行形态学滤波(用3*3结构元进行闭运算),填补初始分割中目标内部的洞,得到最终的分割结果.
图2为运动目标的分割,其中,图2(a)为第128帧R分量的差分图像直方图(为清楚显示运动类,只取运动目标集中区域的直方图),图2(b)为第128帧图像,图2(c)为自适应运动分割结果,图2(d)为经过消噪和闭运算后的最终分割结果.
图2运动目标分割2.
2背景实时更新背景更新的基本思想是使当前帧有一定置信度的背景点参与更新.
置信度通过两方面来估计,一是根据当前差分图象,由运动检测得到的非运动点不一定都是背景点,如较弱的阴影、噪声点等,所以,只有差分值小于一定较小阈值并位于运动目标一定邻域外的点才具有第1方面较高置信度.
将运动目标区域O用5*5结构元进行膨胀,记为O^,若(x,y)|O^且d(I(x,y),M(x,y))T2.
(11)3.
2特殊情况判断及轨迹关联若目标数量发生变化,表明发生了合并、分裂等特殊情况,具体由Area阵对应的R阵进行判断,方法如下:Step1:对R阵每一列Oj,计算该列的和cj=∑ni=1R(i,j).
(12)1)若cj=0,表明Oj没有与其相关联的轨迹,为新增目标,令轨迹数量n=n+1,增加Oj对应的新轨迹Tn;2)若cj=1,且对应R(i3,j)=1,则Oj与轨迹Ti3关联;3)若cj>1,表明有cj条轨迹合并为当前目标Oj,cj条轨迹全部与Oj进行关联.
Step2:对R阵每一行Ti,计算该行的和ri=∑mj=1R(i,j).
(13)1)若ri=0,表明轨迹Ti中断,其对应目标暂时消失,因为目标可能被静止物体暂时遮挡,所以只有该轨迹持续N帧都没有相关联的目标,再结束该轨迹;2)若ri=1,并对应R(i,j3)=1,则Ti与目标Oj3关联;3)若ri>1,表明轨迹Ti与ri个目标关联,分裂发生,对每一个分裂出去的目标,用直方图匹配方法将该目标与其合并前的轨迹进行关联.
4遮挡情况下的多目标跟踪遮挡是人的跟踪中常出现的难点问题,多目标之间的遮挡对应于上述的合并和分裂情况.
将遮挡分为两种情况进行处理,在两人轻微遮挡造成的合并情况下,为保证跟踪的准确性,采用基于颜色直方图的均值漂移算法分别跟踪两个目标,其余情况下将所合并目标一起跟踪,实时更新所有合并的轨迹,并在遮挡过程中使合并轨迹保持同样的关联.
遮挡结束后再分别跟踪,并与遮挡前的轨迹进行关联.
4.
1不严重遮挡情况下基于均值漂移算法的跟踪对应于上述Step1中的情况3),若cj=2,表明有两条轨迹在当前时刻t合并,设Ta,Tb两轨迹合并为目标Ok,若各目标的面积满足S(Otk)>0.
8*(S(Ot-1a)+S(Ot-1b)),(14)则判断遮挡不严重,标记mst(a,b)=1,用均值漂移算法[9,10]分别跟踪合并在一起的两个目标.
实时保存各目标的HSI三维颜色直方图qtu(i),i=1,…,m,其中u为三维颜色向量.
若mst(a,b)=1,则分别以Ot-1a和Ot-1b的质心Ca(x0,y0)和Cb(x0,y0)为均值漂移算法的初始位置,对跟踪窗内运动点标记fi(x,y)=1,i=a,b,非运动点标记fi(x,y)=0,按直方图qt-1u(i)对跟踪窗内每一点(x,y)赋权值,即wti(x,y)=qt-1u(i)*δ(g(x,y)-u)*fi(x,y),i=a,b.
(15)其中:g(x,y)为(x,y)点在直方图中颜色索引值,wti(x,y)为该点权值.
以Ci(x0,y0)作为初始跟踪位0241994-2010ChinaAcademicJournalElectronicPublishingHouse.
Allrightsreserved.
http://www.
cnki.
net第4期常发亮等:视频序列中面向人的多目标跟踪算法置,计算t帧各目标中心Ci(x1,y1)(i=a,b)的均值漂移算法步骤如下[10]:Step1:计算当前跟踪窗内各点(x,y)的权值wti(x,y),1≤x≤mi,1≤y≤ni.
mi和ni为各目标跟踪窗的长度和宽度.
Step2:计算新的漂移位置Ci(x1,y1),其中x1=∑x∑yx*wti(x,y)∑x∑ywti(x,y),y1=∑x∑yy*wti(x,y)∑x∑ywti(x,y).
(16)Step3:若Ci(x1,y1)-Ci(x0,y0)<ε,则停止计算;否则将Ci(x1,y1)作为Ci(x0,y0)返回Step1迭代,参数ε的设置应保证两次收敛到同一点.
4.
2遮挡结束后的轨迹关联遮挡结束对应目标分裂,关键是要判断分裂出的目标属于遮挡前的哪一条轨迹,采用颜色直方图匹配的判断方法能适应目标易变形的特点.
设当前分裂出的目标为Oj,直方图为pu,各合并目标(设有k个)直方图为{qu(i),i=1,…,k}.
用Bhattacharyya系数的离散形式表示直方图的匹配度[9]:ρ(i)=ρ[pu,qu(i)]=∑NH*NS*NIu=1pu*qu(i),i=1,2,…,k,(17)i3=argmaxi(ρ(i)).
(18)选择Ti3为该目标在遮挡前的轨迹.
若大的合并分裂为几个小的合并,也是通过直方图匹配使每个目标与其所属的小的合并关联[4].
5实验结果及分析5.
1遮挡不严重情况下对合并目标分别采用均值漂移算法跟踪图3左右分别对应运动分割图和原图像.
其中:图3(a)为遮挡前的跟踪;图3(b)为遮挡开始时基于运动分割的跟踪,两个目标发生合并而作为一个整体,其质心与两个目标的质心差别较大,跟踪不准确;图3(c)为采用均值漂移算法对两个目标分别跟踪的结果,可见跟踪效果更好;图3(d)为目标遮挡结束(分裂)后基于运动分割的跟踪.
5.
2存在严重遮挡的多目标跟踪图4为存在多目标严重遮挡的跟踪过程,左右分别为运动分割图和原图像,其中各曲线分别为各目标的运动轨迹.
图4(a)为其中2人发生轻微遮挡,图3遮挡不严重情况下对合并目标分别采用均值漂移跟踪图4存在严重遮挡的多目标跟踪对这两个目标的跟踪采用均值漂移算法,其余目标仍按运动分割跟踪;图4(b)为其中3人的严重遮1241994-2010ChinaAcademicJournalElectronicPublishingHouse.
Allrightsreserved.
http://www.
cnki.
net控制与决策第22卷挡,将其作为一个整体进行跟踪,3人的轨迹暂时合并为一条轨迹;图4(c)为遮挡结束,3人完全分裂开,用直方图匹配算法分别辨识分裂目标,并与遮挡前的相应轨迹进行关联;图4(d)为2人又发生轻微遮挡,使用均值漂移算法对其进行跟踪.
5.
3复杂场景下的多目标跟踪图5所示为复杂场景下的多目标跟踪结果,并实时描述各目标的运动轨迹.
图5(a)为在61帧时出现新目标(最右侧目标),相应的为其新增轨迹;图5(b)为3个目标发生合并,一起进行跟踪;图5(c)在图像左上又出现新增的目标,并且黑色轨迹对应目标接近消失;图5(d)为已经确定黑色轨迹对应目标消失,去除其对应轨迹,并且左下方又出现新的目标;图5(e)为跟踪结束时的场景.
可见,提出的关联矩阵和轨迹关联算法能对各种特殊情况进行准确判断并保证正确的跟踪.
图5复杂场景下的多目标跟踪6结论针对多人跟踪中常出现的遮挡等难题,提出了基于运动目标检测的多目标跟踪算法.
其特点有:1)基于改进c2均值聚类的自适应运动目标检测方法,有效克服了固定分割阈值不能适应场景变化的缺点,并实时进行背景更新;2)不同情况下采用不同的关联矩阵,可保证场景情况判断的准确性;3)对于常出现的两人不严重遮挡问题,采用基于颜色直方图的均值漂移算法对合并的目标分别跟踪,可保证跟踪的准确性;4)提出的轨迹关联方法和采用直方图匹配对分裂目标进行辨识,可保证多目标跟踪的可靠性.
参考文献(References)[1]WrenChristopherRichard,AzarbayejaniAli,DarrellTrevor,etal.
Pfinder:Real2timetrackingofthehumanbody[J].
IEEETransonPatternAnalysisandMachineIntelligence,1997,19(7):7802785.
[2]HaritaogluIsmail,HarwoodDavid,DavisLarryS.
W4:Real2timesurveillanceofpeopleandtheiractivities[J].
IEEETransonPatternAnalysisandMachineIntelligence,2000,22(8):8092830.
[3]MarecenaroL,FerrariM,MarchesottlL.
MultipleobjecttrackingunderheavyocclusionsbyusingKalmanfilterbasedonshapematching[C].
IEEEIntConfonImageProcessing.
NewYork,2002:3412344.
[4]StephenJMcKenna,SumerJabri,ZoranDuric,etal.
Trackinggroupsofpeople[J].
ComputerVisionandImageUnderstanding,2000,80(1):42256.
[5]TaoYang,StanZLi,QuanPan,etal.
Real2timemultipleobjectstrackingwithocclusionhandlingindynamicscenes[C].
ComputerVisionandPatternRecognition.
SanDiego,2005:9702975.
[6]LeeDar2Shayang.
Effectivegaussianmixturelearningforvideobackgroundsubtraction[J].
IEEETransonPatternAnalysisandMachineIntelligence,2005,27(5):8272832.
[7]ElgammalAhmed,HarwoodDavid,DavisLarry.
Non2parametricmodelforbackgroundsubtraction[C].
EuropeanConfonComputerVision.
Dublin,2000:7512767.
[8]EliasHerrero2Jaraba,CarlosOrrite2Urunuela,JesusSenar.
Detectedmotionclassificationwithadouble2backgroundandaneighborhood2baseddifference[J].
PatternRecognitionLetters,2003,24(1):207922092.
[9]ComaniciuDorin,RameshVisvanathan,MeerPeter.
Kernel2basedobjecttracking[J].
IEEETransonPatternAnalysisandMachineIntelligence,2003,25(5):5642577.
[10]BradskiGrayR.
Computervisionfacetrackingforuseinaperceptualuserinterface[J].
IntelTechnologyJ,1998,2:1215.
(上接第417页)[16]LiX,LiuL.
Peertrust:Supportingreputation2basedtrustinpeer2to2peercommunities[J].
IEEETransonKnowledgeandDataEngineering,2004,16(7):8432857.
[17]BreeseJ,HechermanD,KadieC.
Empiricalanalysisofpredictivealgorithmsforcollaborativefiltering[C].
Procofthe14thConfonUncertaintyinArtificialIntelligence.
SanFrancisco:MorganKaufmannPublishers,1998:43252.
[18]SarwarB,KarypisG,KonstanJ,etal.
Item2basedcollaborativefilteringrecommendationalgorithms[C].
Procofthe10thIntWorldWideWebConf.
HongKong:ACMPress,2001:2852295.
224