estimationyahoo.cn

SVDBasedKalmanParticleFilterforRobustVisualTrackingXiaoqinZhang1,WeimingHu1,ZixiangZhao2,Yan-guoWang1,XiLi1,QingdiWei11NationalLaboratoryofPatternRecognition,InstituteofAutomation,Beijing,China{xqzhang,wmhu,ygwang,lixi,qdwei}@nlpr.
ia.
ac.
cn2BeijingUniversityofAeronautics&Astronauticszhaozx531@yahoo.
cnAbstractObjecttrackingisoneofthemostimportanttasksincomputervision.
Theunscentedparticlelteralgorithmhasbeenextensivelyusedtotacklethisproblemandachievedagreatsuccess,becauseitusestheUKF(un-scentedKalmanlter)togenerateasophisticatedpro-posaldistributionswhichincorporatesthenewestob-servationsintothestatetransitiondistributionandthusovercomesthesampleimpoverishmentproblemsufferedbytheparticlelter.
However,UKFoftenencounterstheill-conditionedproblemwhensolvingthesquarerootofthecovariancematrixinpractice.
Inthispaper,weproposeanovelKalmanparticlelterbasedonSVD(singularvaluedecomposition),andapplyitforvisualtracking.
Experimentalresultsdemonstratethat,com-paredwiththeparticlelterandtheunscentedparticlelter,theproposedalgorithmismorerobustintrackingperformance.
1.
IntroductionObjecttrackinghasreceivedsignicantattentionduetoitscrucialvalueinvisualapplicationsinclud-ingsurveillance,human-computerinteraction,intelli-genttransportation,augmentedrealityandvideocom-pression.
Theparticlelter[1,2]hasbeenextensivelystud-iedinthetrackingliteratureduetoitseffectivenessandexibility.
FromaBayesianview,particlelterisessen-tiallyasequentialMonteCarloapproachtosolvethere-cursiveBayesianlteringproblem,whichcombinestheMonteCarlosamplingtechniqueswithBayesianinfer-ence.
ItrelaxesthelinearityandGaussianityconstraintsoftheKalmanlterandprovidesatractablesolutiontonon-linearandnon-Gaussiansystems.
Thebasicideaofparticlelteristouseanumberofindependentran-domvariablescalledparticles,sampleddirectlyfromaproposaldistribution,torepresenttheposteriorprob-ability,andupdatetheposteriorbyinvolvingthenewobservations.
Althoughithasachievedaconsiderablesuccessinthetrackingliterature,itisfacedwithafatalproblem-sampleimpoverishmentduetoits'suboptimalsampling'mechanism.
Fortheconventionalparticlel-ter,theparticlesaredirectlysampledfromstatetransi-tiondistribution.
However,itisnotthe'optimal'pro-posalsamplingdistribution.
Whenthestatetransitiondistributionliesinthetailoftheobservationlikelihooddistribution,theweightsofmostparticlesarelow,lead-ingtothepoorperformanceinpractice.
Muchefforthasbeenexpendedtoovercomethisproblemandimprovetheperformanceofparticlel-terinrecentyears[3,4,5,6,7,8].
Amongthem,theunscentedparticlelter[4]isthesuccessfulone.
Intheunscentedparticlelter,theUKFbasedproposaldistributionisintroducedasfollows.
Firstly,asetthesigmasamplesaregeneratedbyUT(unscentedtrans-formation)withcorrespondingweights,andthenarepropagatedthroughthestatetransitionmodel,nallytheweightedmeanandcovariancearefurthercalcu-latedtoformabetterproposaldistribution.
ComparedwiththeEKF(extendedKalmanlter)whichapproxi-matestotherst-orderaccuracyfornon-Gaussiandata,theestimationaccuracyofUKFisimprovedtoatleastsecond-order.
However,UKFoftenencounterstheill-conditionedproblemwhensolvingthesquarerootofthecovariancematrixinpractice.
Toovercomethisproblem,weproposeaSVDbasedKalmanparticlel-ter,wherethesigmasamplesaregeneratedbySVDoftheeigen-covariancematrix.
Whilemaintainingthesamecomputationalcomplexity,theproposedtrackingalgorithmperformsquiterobustlyintrackingperfor-mance.
Thefollowingpaperisarrangedasfollows.
Section2presentstheunscentedparticlelteringframework.
ThedetailoftheproposedSVDbasedKalmanlterisdescribedinSection3.
Section4introducestheincre-mentalsubspaceleaningbasedappearancemodel.
Ex-perimentalresultsareshowninSection5,andSection6isdevotedtoconclusion.
2.
UnscentedParticleFilteringFrameworkTomakethispaperself-contained,werstbrieyreviewtheparticlelteranditsmajorlimitation,andthenpresenttheunscentedparticlelterindetail.
2.
1.
ParticleFilterParticlelter[2]isanonlineBayesianinferencepro-cessforestimatingtheunknownstatextattimetfromasequentialobservationsy1:tperturbedbynoises.
Adynamicstate-spaceformemployedintheBayesianin-ferenceframeworkisshownasfollows,xt=f(xt1,t)p(xt|xt1)(1)yt=h(xt,νt)p(yt|xt)(2)wherext,ytrepresentsystemstateandobservation,t,νtarethesystemnoiseandobservationnoise.
f(.
,.
)andh(.
,.
)arethestatetransitionandobservationmod-els,whichcharacterizethestatetransitiondistributionp(xt|xt1)andtheobservationdistributionp(yt|xt)re-spectively.
Thekeyideaofparticlelteristoapprox-imatetheposteriorprobabilitydistributionp(xt|y1:t)byasetofweightedsamples{xit,wit}Ni=1,whicharesampledfromaproposaldistributionq(·),i.
e.
xitq(xt|xit1,y1:t),(i=1,N),andtheneachparti-cle'sweightissettowit∝p(yt|xit)p(xit|xit1)q(xt|xit1,y1:t)(3)Finally,theposteriorprobabilitydistributionisapprox-imatedasp(xt|y1:t)=Ni=1witδ(xtxit),whereδ(·)istheDiracfunction.
Doucetetal.
[9]provethatthe'optimal'proposaldistributionisp(xt|xit1,yt)inthesenseofminimizingthevarianceoftheimportanceweights.
Sotheques-tionis,howtoincorporatethecurrentobservationytintothetransitionmodelp(xt|xt1)toformaneffec-tiveproposaldistribution.
2.
2.
UnscentedParticleFilterInordertoutilizethecurrentobservations,Freitasetal.
[4]proposeahigh-performanceunscentedparti-clelter(UPF)byusingUKFtogeneratetheproposaldistribution.
Intheimplementation,thestatespaceisexpandedas:xat1=[xTt1Tt1νTt1],whosedimensionandco-variancematrixareNa=Nx+N+NνandPat1respectively.
Considerthenonlineartrackingproblemmodeledbythestate-spaceequations(1)and(2),thepseudo-codeoftheunscentedKalmanlterispresentedasfollows.
1.
Calculate2Nasigmapointsasin[4]X(i)a0,t1=x(i)at1X(i)aj,t1=[x(i)at1x(i)at1±(na+λ)Pat1j]W(m)0=λNa+λ,W(c)0=λNa+λ+(1α2+β)W(m)j=W(c)j=12(Na+λ),λ=α2(Na+κ)Naj=1,2Na2.
Timeupdate:X(i)xj,t|t1=f(X(i)xj,t1,X(i)j,t1),x(i)t|t1=2Naj=0W(m)jX(i)xj,t|t1P(i)t|t1=2Naj=0W(c)j[X(i)xj,t|t1x(i)t|t1][X(i)xj,t|t1x(i)t|t1]TY(i)j,t|t1=h(X(i)xj,t1,X(i)νj,t1),y(i)t|t1=2Naj=0W(m)jY(i)j,t|t13.
Measurementupdate:Pyt,yt=2Naj=0W(c)j[Y(i)j,t|t1y(i)t|t1][Y(i)j,t|t1y(i)t|t1]TPxt,yt=2Naj=0W(c)j[X(i)xj,t|t1x(i)t|t1][Y(i)j,t|t1y(i)t|t1]TKt=Pxt,ytP1yt,yt,x(i)t=x(i)t|t1+Kt(yty(i)t|t1)P(i)t=P(i)t|t1KtPyt,ytKTtAsaresult,theproposaldistributionisobtainedasq(xit|xit1,y1:t)=N(x(i)t,P(i)t),andtheunscentedpar-ticlelterisanaturalcombinationoftheUKFproposaldistributionandtraditionalparticlelteraspresentedinSection2.
1.
3.
SVDBasedKalmanFilterHowever,UKFoftenencounterstheill-conditionedproblemwhensolvingthesquarerootofthecovariancematrixPat1inpractice.
Therefore,weproposeanSVDbasedKalmanltertoovercomethisproblem.
Togiveaclearview,theowchartoftheSVDbasedKalmanlterframeworkisschematicallyshowninFig.
1.
TheSVDbasedKFsharesaclosespirittoUKF,rstly,themeanstateandeigen-covariancematrixofthesigmasamplesattimet1arecalculated,andweapplytheSVDtotheeigen-covariancematrixtoobtain/86:22:=95-52;+82;35/0,.
=>82;35.
5B2:=95Figure1.
OverviewoftheSVDbasedKalmanlteritseigenvectors.
Thentheobtainedmeanandeigen-vectorsarecombinedtogeneratenewsigmasamples.
Finally,thenewsamplesarelteredbythestandardKalmanlter.
ThethedetailSVD-basedKalmanl-terprocessispresentedasfollows.
1.
ComputetheSVDoftheeigen-pointcovariancema-trixPat1=Ut1St1VTt12.
Calculatenewsigmasamples:X(i)a0,t1=x(i)at1X(i)aj,t1=[x(i)at1x(i)at1±ρUj,t1√sj,t1]whereUj,t1,sj,t1arethejtheigenvectorandeigen-valuerespectively,andρisthescaleparameter.
3.
ThefollowingstepisthesameasthestandardKal-manltering.
ThebasicmotivationbehindSVD-KFisthatthecovariancematrixcanbecharacterizedbyitseigen-vectors,andSVDismorenumericallyrobustthanCholeskyfactorizationintheunscentedtransformation.
4.
IncrementalSubspaceLeaningBasedAppearanceModelInourpaper,weadoptasubspacebasedappearancemodel[10]forobservationevaluation,whichmodelstheappearanceofanobjectbyincrementallylearningalow-ordereigenspacerepresentation.
ObservationLikelihood:Asshownin[10],giventhelearnedthesubspaceUandthenewobservationyt,theobservationlikelihoodisbasedonthereconstructioner-roroftheobservationyiintheobjectsubspace,whichisdenedasfollows.
RE=||ytUUTyt||2(4)Asaresult,theobservationlikelihoodisnaturallyformedasp(yt|xt)=exp(RE)(5)IncrementallySubspaceLearning:GiventheSVDofthepreviousappearancedataA={I1,It},i.
e.
A=UΣVT,whereeachcolumnIiistheobservationoftheobjectintheithframe.
Aftertrackingkframes,wehaveobtainedknewestobservationsoftheobjectE={It+1,It+k},theR-SVDalgorithm[11]ef-cientlycomputestheSVDofthematrixA=(A|E)=UΣVTbasedontheSVDofAasfollows:1.
ApplyQRdecompositiontoandgetorthonormalba-sisEofE,andU=(U|E).
2.
LetV=V00IkwhereIkisak*kidentitymatrix.
Itfollowsthen,Σ=UTAV=UTE(A|E)V00Ik=UTAVUTEETAVETE=ΣUTE0ETE3.
ComputetheSVDofΣ=UΣVTandtheSVDofAisA=U(UΣVT)VT=(UU)Σ(VTVT)Inthisway,theR-SVDalgorithmcomputestheneweigenbasisefciently.
5.
ExperimentalResultsInourexperiment,theobjectisinitializedman-uallyandafnetransformationsisconsideredonly.
Specically,themotionischaracterizedbys=(tx,ty,a1,a2,a3,a4)where{tx,ty}denotethe2-Dtranslationparametersand{a1,a2,a3,a4}aredeforma-tionparameters.
Eachcandidateimageisrectiedtoa20*20patch,andthefeatureisa400-dimensionvectorwithzero-mean-unit-variancenormalization.
Inordertodemonstratetheeffectivenessofourap-proach,weconductacomparisonexperimentamongtheSVDbasedKPF(Kalmanparticlelter),astandardPF(particlelter)1andUPF[4]onavideowithmanu-allylabeledgroundtruth.
TheDavidsequence2issampledalternatelytoformarapidmotiontestingsequence.
Inourimplementa-tion,theparametersaresetto{N=200,var()=1Here,aGaussiantransitiondistributionxtN(xt1,Σ)istakenastheproposaldistribution2WeacknowledgetotheauthorofthesourcedataavailableattheURL:http://www.
cs.
toronto.
edu/dross/ivt/TrackingMethodFramesTrackedMSE(bypixels)PF16/6126.
9481UPF61/617.
1875SVDbasedKPF61/613.
9868Table1.
QuantitativeresultsofSVDbasedKPFtrackeranditscomparisonwithPFtrackerandUPFtracker[52,52,0.
012,0.
022,0.
0022,0.
0012]}correspondingtothenumberofparticlesandthecovariancematrixofthetransitiondistributionrespectively.
AsshownintherstcolumnofFig.
2,theparticlelterbasedtrackerfailstotracktheobjectatframe31,becausetheparticlesaresampledfromthetransitiondistributiontocatchtheob-jectmotion.
Whentheobjecthasrapidandarbitrarymotion,theparticlesdrawnfromthisdistributiondonotcoverasignicantregionofthelikelihood,andthustheweightsofmostparticlesarelow,leadingtothetrackingfailure.
Moreparticlesandanenlargementforthediag-onalelementsofthecovariancematrixwouldimproveitsperformance,butthisstrategyinvolvesmorenoisesandaheavycomputationalload.
ThesecondcolumnofFig.
2showsthetrackingperformanceoftheunscentedparticlelter,fromwhichwenoticethatthetrackerfollowstheobjectthroughoutthesequence.
However,Choleskyfactorizationisnotnumericallyrobustandof-tenencounterstheill-conditionedproblem,therebyre-sultingtotheinaccuratelocalizationandsize.
Incom-parison,ourmethodachievesthemoreaccurateresults,becausethecovariancematrixisfullycharacterizedbyitseigenvectors,andSVDismorenumericallyrobustthanCholeskyfactorization.
Meanwhile,wehavecon-ductedaquantitativeevaluationofthesealgorithms,andhaveacomparisoninthefollowingaspects:framesofsuccessfultracking,MSE(meansquareerror)betweentheestimatedpositionandthelabeledgroundtruth.
Intable1,itisclearthatthePFtrackerfailsatframe31whiletheUPFandSVDbasedKPFtrackerssucceedintrackingthroughoutthesequence.
Additionally,theSVDbasedKPFtrackeroutperformstheUPFtrackerintermofaccuracy.
6.
ConclusionThispaperpresentsanSVDbasedKalmanparticlelterforvisualtracking.
Inouralgorithm,asetofsigmasamplesaregeneratedbySVDofthecovariancema-trix,andthenthesesigmapointsarepropagatedbythestandardKalmanltertogenerateasophisticatedpro-posaldistribution.
Theobtainedproposaldistributionisincorporatedintotheparticleltertoformarobusttrackingalgorithm.
Experimentalresultsdemonstratetheeffectivenessandpromisingofourapproach.
Figure2.
Thetrackingresults(rstcol-umn:PF,secondcolumn:UPF,thirdcol-umn:SVDbasedKPF)7.
AcknowledgmentThisworkispartlysupportedbyNSFC(GrantNo.
60672040,60705003)andtheNational863High-TechR&DProgramofChina(GrantNo.
2006AA01Z453).
References[1]M.
IsardandA.
Blake,"Condensation:conditionaldensitypropagationforvisualtracking",IJCV.
,29(1):5-28,1998.
[2]M.
Arulampalam,S.
Maskell,N.
Gordon,andT.
Clapp,"Atutorialonparticlesltersforonlinenonlinear/non-gaussianbayesiantracking",IEEETrans.
onSignalProcessing,50(2):174-188,2002.
[3]J.
Deutscher,A.
Blake,I.
Reid,"Articulatedbodymotioncap-turebyannealedparticleltering",Proc.
CVPR'00,pp.
126-133,2000.
[4]R.
Merwe,A.
Doucet,N.
Freitas,andE.
Wan,"Theunscentedparticlelter",TechnicalReportCUED/F-INFENG/TR380,CambridgeUniversityEngineeringDepartment,2000.
[5]Y.
RuiandY.
Chen,"Betterproposaldistributions:objecttrackingusingunscentedparticlelter",Proc.
CVPR'01,pp.
786-793,2001.
[6]Y.
Wu,T.
Huang,"RobustVisualTrackingbyIntegratingMul-tipleCuesBasedonCo-InferenceLearning",IJCV.
,58(1):55-71,2004.
[7]B.
Han,Y.
Zhu,D.
ComaniciuandL.
Davis,"Kernel-BasedBayesianFilteringforObjectTracking",Proc.
CVPR'05,pp.
227-234,2005.
[8]X.
Zhang,W.
Hu,G.
Luo,andS.
Maybank,"Kernel-BayesianFrameworkforObjectTracking",Proc.
ACCV'07,pp.
821-831,2007.
[9]A.
Doucet,S.
Godsill,andC.
Andrieu,"OnsequentialMonteCarlosamplingmethodsforBayesianltering",StatisticsandComputing,10(3):197-208,2000.
[10]J.
Lim,D.
Ross,R.
S.
Lin,andM.
H.
Yang,"Incrementallearn-ingforvisualtracking",InAdvancesinNeuralInformationProcessingSystems,pp.
793-800,2004,TheMITPress.
[11]A.
LevyandM.
Lindenbaum,"SequentialKarhunen-Loeveba-sisextractionanditsapplicationtoimages",IEEETrans.
onImageProcessing,9(8):1371-1374,2000.