多目标跟踪英文课件

Random Set/Point Process in Random Set/Point Process in Multi-Target TrackingMulti-Target TrackingBa-Ngu VoBa-Ngu VoEEE Department EEE Department University of MelbourneUniversity of MelbourneAustraliaAustraliahttp:/www.ee.unimelb.edu.au/staff/bv/SAMSI,RTP,NC,USA,8September2008Collaborators(innoparticularorder):MahlerR.,Singh.S.,DoucetA.,Ma.W.K.,PantaK.,ClarkD.,VoB.T.,CantoniA.,PashaA.,TuanH.D.,BaddeleyA.,ZuyevS.,SchumacherD.The The BayesBayes(single-target)filter(single-target)filterMulti-target trackingMulti-target trackingSystem representationSystem representationRandom finite set&Bayesian Multi-target filteringRandom finite set&Bayesian Multi-target filteringTractable multi-target filtersTractable multi-target filtersProbability Hypothesis Density(PHD)filterProbability Hypothesis Density(PHD)filterCardinalizedCardinalized PHD filter PHD filterMulti-Bernoulli filterMulti-Bernoulli filterConclusionsConclusions Outline The Bayes(single-target)Filter state-vectortarget motionstate spaceobservation spacexkxk-1zk-1zk fk|k-1(xk|xk-1)Markov Transition DensityMeasurement Likelihoodgk(zk|xk)Objectivemeasurement history(z1,zk)posterior(filtering)pdf of the statepk(xk|z1:k)System Modelstate-vectortarget motionstate spaceobservation spacexkxk-1zk-1zkBayes filterpk-1(xk-1|z1:k-1)pk|k-1(xk|z1:k-1)pk(xk|z1:k)predictiondata-updatepk-1(xk-1|z1:k-1)dxk-1 fk|k-1(xk|xk-1)gk(zk|xk)K-1 pk|k-1(xk|z1:k-1)The Bayes(single-target)Filter pk-1(.|z1:k-1)pk|k-1(.|z1:k-1)pk(.|z1:k)predictiondata-updateBayes filterN(.;mk-1,Pk-1)N(.;mk|k-1,Pk|k-1)N(.;(mk,Pk)Kalman filteri=1Nwk|k-1,xk|k-1i=1N(i)(i)wk,xk i=1 N(i)(i)wk-1,xk-1(i)(i)Particle filterstate-vectortarget motionstate spaceobservation spacexkxk-1zk-1zk fk|k-1(xk|xk-1)gk(zk|xk)The Bayes(single-target)Filter Multi-target trackingobservation produced by targetstarget motionstate spaceobservation space5 targets3 targetsXk-1XkObjective:Jointly estimate the number and states of targetsChallenges:Random number of targets and measurementsDetection uncertainty,clutter,association uncertainty Multi-target tracking System RepresentationEstimateiscorrectbutestimationerror?TrueMulti-targetstateEstimatedMulti-targetstateHowcanwemathematically represent the multi-target state?2targets2targetsUsual practice:stackindividualstatesintoalargevector!Problem:Remedy:useTrueMulti-targetstateEstimatedMulti-targetState2targetsnotargetTrueMulti-targetstateEstimatedMulti-targetState2targets1target System RepresentationWhat are the estimation errors?Errorbetweenestimateandtruestate(miss-distance)fundamentalinestimation/filtering&controlwell-understoodforsingletarget:Euclideandistance,MSE,etcinthemulti-targetcase:dependsonstaterepresentationFor multi-target state:vector representationdoesntadmitmulti-targetmiss-distancefinite set representation admitsmulti-targetmiss-distance:distance between 2 finite setsInfactthe“distance”isadistanceforsetsnotvectors System Representationobservation produced by targetstarget motionstate spaceobservation space5 targets3 targetsXk-1XkNumberofmeasurementsandtheirvaluesare(random)variablesOrderingofmeasurementsnotrelevant!Multi-target measurementisrepresentedbyafinite set System Representation RFS&Bayesian Multi-target Filteringtargetstarget setobserved setX X observationsXZNeedsuitablenotionsofdensity&integration pk-1(Xk-1|Z1:k-1)pk(Xk|Z1:k)pk|k-1(Xk|Z1:k-1)predictiondata-update Reconceptualizeasageneralizedsingle-targetproblemMahler94Bayesian:Modelstate&observationasRandomFiniteSetsMahler94 RFS&Bayesian Multi-target FilteringS NS(S)=|S S|point process or random counting measurerandom finite set or random point patternSstate space Estate space EBelief“density”ofS fS:F(E)0,)bS(T)=T fS(X)dXBelief“distribution”ofSbS(T)=P(S T),T EESProbability densityofS pS:F(E)0,)PS(T)=T pS(X)m(dX)Probability distributionofSPS(T)=P(S T ),T F(E)F(E)SCollectionoffinitesubsetsofEStatespaceMahlers Finite Set Statistics(1994)Choquet(1968)TTConventional integralSet integralVo et.al.(2005)Point Process Theory(1950-1960s)RFS&Bayesian Multi-target FilteringxxXxdeathcreationXxspawnmotion Multi-target Motion Model fk|k-1(Xk|Xk-1)Multi-object transition densityXk=Sk|k-1(Xk-1)Bk|k-1(Xk-1)kEvolution of each element x of a given multi-object state Xk-1 Multi-target Observation Model gk(Zk|Xk)Multi-object likelihoodZk=Qk(Xk)Kk(Xk)xzxlikelihoodmisdetectionclutterstate spaceobservation space Observation process for each element x of a given multi-object state Xk pk-1(Xk-1|Z1:k-1)pk(Xk|Z1:k)pk|k-1(Xk|Z1:k-1)predictiondata-update Computationally intractable in generalNo closed form solutionParticle or SMC implementation Vo,Singh&Doucet03,05,Sidenbladh03,Vihola05,Maetal.06 Restricted to a very small number of targets Multi-target Bayes FilterMulti-targetBayesfilter Particle Multi-target Bayes FilterAlgorithmAlgorithmfor i=1:N,%Initialise=Sample:Compute:end;normalise weights;for k=1:kmax,for i=1:N,%Update =Sample:Update:end;normalise weights;resample;MCMC step;end;pk-1(Xk-1|Z1:k-1)pk(Xk|Z1:k)pk|k-1(Xk|Z1:k-1)predictiondata-update Multi-target Bayes filter:very expensive!single-objectBayesfilter multi-objectBayesfilter stateofsystem:random vectorfirst-momentfilter(e.g.a-b-g filter)stateofsystem:random setfirst-momentfilter(“PHD”filter)Single-object Multi-object The PHD Filterx0state spacevS PHD(intensity function)of a RFS S SvS(x0)=density of expected number of objects at x0 The Probability Hypothesis Density vS(x)dx=expected number of objects in SS=mean of,NS(S),the random counting measure at S The PHD Filterstate space vk vk-1 PHD filter vk-1(xk-1|Z1:k-1)vk(xk|Z1:k)vk|k-1(xk|Z1:k-1)PHD predictionPHD update Multi-object Bayes filter pk-1(Xk-1|Z1:k-1)pk(Xk|Z1:k)pk|k-1(Xk|Z1:k-1)predictionupdate Avoids data association!PHD Predictionvk|k-1(xk|Z1:k-1)=fk|k-1(xk,xk-1)vk-1(xk-1|Z1:k-1)dxk-1+gk(xk)intensity from previoustime-step term for spontaneousobject births =intensity of kfk|k-1(xk,xk-1)=ek|k-1(xk-1)fk|k-1(xk|xk-1)+bk|k-1(xk|xk-1)Markovtransitionintensityprobabilityof objectsurvivalterm for objectsspawned byexisting objects=intensity of Bk(xk-1)Markov transition densitypredictedintensityNk|k-1=vk|k-1(x|Z1:k-1)dxpredicted expected number of objects(Fk|k-1a)(xk)=fk|k-1(xk,x)a(x)dx+gk(xk)vk|k-1=Fk|k-1vk-1 PHD Update vk(xk|Z1:k)SzZkDk(z)+kk(z)pD,k(xk)gk(z|xk)+1-pD,k(xk)vk|k-1(xk|Z1:k-1)Dk(z)=pD,k(x)gk(z|x)vk|k-1(x|Z1:k-1)dx Nk=vk(x|Z1:k)dxBayes-updated intensitypredicted intensity(from previous time)intensity offalse alarmssensor likelihood functionprobabilityof detectionexpected number of objectsmeasurementvk=Ykvk|k-1(Yka)(x)=zZk+kk(z)yk,z(x)+1-pD,k(x)a(x)S Particle PHD filterParticle approximation of vk-1 Particle approximation of vk state spaceVo,Singh&Doucet03,05,Sidenbladh03,Mahler&Zajic03ThePHD(orintensityfunction)vk is not a probability densityThePHDpropagationequationis not a standard Bayesian recursionSequentialMCimplementationofthePHDfilterNeed to cluster the particles to obtain multi-target estimates Particle PHD filterAlgorithmAlgorithmInitialise;for k=1:kmax,for i=1:Jk,Sample:;compute:;end;for i=Jk+1:Jk+Lk-1,Sample:;compute:;end;for i=1:Jk+Lk-1,Update:;end;Redistribute total mass among Lk resampled particles;end;Convergence:Vo,Singh&Doucet05,Clark&Bell06,Johansenet.al.06 Gaussian Mixture PHD filterClosed-formsolutiontothePHDrecursionexistsforlinear Gaussian multi-target model vk-1(.|Z1:k-1)vk(.|Z1:k)vk|k-1(.|Z1:k-1)wk-1,mk-1,Pk-1i=1Jk-1(i)(i)(i)wk|k-1,mk|k-1,Pk|k-1i=1Jk|k-1(i)(i)(i)wk,mk,Pk i=1 Jk(i)(i)(i)PHDfilterGaussianMixture(GM)PHDfilterVo&Ma05,06GaussianmixturepriorintensityGaussianmixtureposteriorintensitiesatallsubsequenttimes Extended&UnscentedKalmanPHDfilterVo&Ma06JumpMarkovPHDfilterPashaet.al.06TrackcontinuityClarket.al.06 Cardinalised PHD FilterDrawback of PHD filter:HighvarianceofcardinalityestimateRelax Poisson assumption:allowsarbitrarycardinalitydistributionJointly propagate:intensityfunction&probabilitygeneratingfunctionofcardinality.More complex PHD update step(highercomputationalcosts)CPHDfilterMahler06,07 vk-1(xk-1|Z1:k-1)vk(xk|Z1:k)vk|k-1(xk|Z1:k-1)intensity predictionintensity update pk-1(n|Z1:k-1)pk(n|Z1:k)pk|k-1(n|Z1:k-1)cardinality predictioncardinality update Gaussian Mixture CPHD Filterwk-1,xk-1i=1Jk-1(i)(i)wk|k-1,xk|k-1i=1Jk|k-1(i)(i)wk,xk i=1 Jk(i)(i)intensity predictionintensity update cardinality predictioncardinality update pk-1(n)n=0pk|k-1(n)n=0pk(n)n=0ParticleCPHDfilterVo08Closed-form solution to the CPHD recursion exists for linear Gaussian multi-target modelGaussian mixture prior intensity Gaussian mixture posterior intensities at all subsequent times Voet.al.06,07Particle-PHD filter can be extended to the CPHD filter CPHD filter Demonstration1000MCtrialaverageGMCPHDfilterGMPHDfilter CPHD filter Demonstration1000MCtrialaverageComparison with JPDA:linear dynamics,Comparison with JPDA:linear dynamics,s sv v=5,=5,s sh h=10,=10,4 targets,4 targets,Sonar imagesSonar images CPHD filter Demonstration MeMBer Filter(rk-1,pk-1)i=1Mk-1(i)(i)(rk|k-1,pk|k-1)i=1Mk|k-1(i)(i)(rk,pk )i=1 Mk(i)(i)prediction update Valid for low clutter rate&high probability of detectionMulti-objectBayesfilter pk-1(Xk-1|Z1:k-1)pk(Xk|Z1:k)pk|k-1(Xk|Z1:k-1)predictionupdate(Multi-targetMulti-Bernoulli)MeMBerfilter Mahler07,biasedApproximate predicted/posterior RFSs by Multi-Bernoulli RFSsCardinality-BalancedMeMBerfilter Voet.al.07,unbiased Cardinality-Balanced MeMBer Filter(rk-1,pk-1)i=1Mk-1(i)(i)(rk|k-1,pk|k-1)i=1Mk|k-1(i)(i)(rk,pk )i=1 Mk(i)(i)prediction update(rP,k|k-1,pP,k|k-1)(r,k,p,k)(i)(i)(i)(i)i=1Mk-1i=1M,krk-1pk-1,pS,k(i)(i)fk|k-1(|),pk-1 pS,k(i)pk-1,pS,k(i)term for object birthsCardinality-BalancedMeMBerfilterVoet.al.07(rk-1,pk-1)i=1Mk-1(i)(i)(rk|k-1,pk|k-1)i=1Mk|k-1(i)(i)(rk,pk )i=1 Mk(i)(i)prediction update(rL,k,pL,k)(rU,k,(z),pU,k(z)(i)(i)z Zki=1Mk|k-11-pk|k-1,pD,k(i)pk|k-1(1-pD,k)(i)1-rk|k-1 pk|k-1,pD,k(i)(i)rk|k-1(1-pk|k-1,pD,k)(i)(i)Cardinality-Balanced MeMBer Filterrk|k-1(1-rk|k-1)pk|k-1,pD,kgk(z|)1-rk|k-1 pk|k-1,pD,k(i)(i)rk|k-1 pk|k-1,pD,kgk(z|)(i)(i)i=1Mk|k-1S(1-rk|k-1pk|k-1,pD,k)2(i)(i)(i)(i)(i)i=1Mk|k-1Sk(z)+1-rk|k-1(i)rk|k-1 pk|k-1(i)(i)i=1Mk|k-1SpD,kgk(z|)rk|k-1pk|k-1,pD,kgk(z|)1-rk|k-1(i)(i)(i)i=1Mk|k-1SCardinality-BalancedMeMBerfilterVoet.al.07 Cardinality-Balanced MeMBer FilterClosed-form(Gaussian mixture)solution Voet.al.07,Particle implementation Voet.al.07,(rk-1,pk-1)i=1Mk-1(i)(i)(rk|k-1,pk|k-1)i=1Mk|k-1(i)(i)(rk,pk )i=1 Mk(i)(i)prediction update wk-1,xk-1j=1Jk-1(i,j)(i,j)j=1Jk|k-1(i,j)(i,j)wk|k-1,xk|k-1 wk,xk j=1 Jk(i,j)(i,j)wk-1,mk-1,Pk-1j=1Jk-1(i,j)(i,j)(i,j)wk|k-1,mk|k-1,Pk|k-1j=1Jk|k-1(i,j)(i,j)(i,j)wk,mk,Pk j=1 Jk(i,j)(i,j)(i,j)MoreusefulthanPHDfiltersinhighlynon-linearproblems Performance comparisonExample:Example:10targetsmaxonscene,withbirths/deaths 4Dstates:x-yposition/velocity,linearGaussianobservations:x-yposition,linearGaussian/start/endpositionsDynamicsconstantvelocitymodel:v=5ms-2,survivalprobability:pS,k=0.99,ObservationsadditiveGaussiannoise:=10m,detectionprobability:pD,k=0.98,uniformPoissonclutter:c=2.5x10-6m-2Cardinality-BalancedRecursionMahlersMeMBerRecursion1000MCtrialaverage Gaussian implementation Gaussian implementation1000MCtrialaverageCPHDFilterhasbetterperformance Particle implementation1000MCtrialaverageCB-MeMBerFilterhasbetterperformance Concluding RemarksThank You!Random Finite Set frameworkRandom Finite Set frameworkRigorousformulationofBayesianmulti-targetfilteringRigorousformulationofBayesianmulti-targetfilteringLeadstoefficientalgorithmsLeadstoefficientalgorithmsFuture research directions Future research directions Track before detect Track before detect Performance measure for multi-object systems Performance measure for multi-object systems Numerical techniques for estimation of trajectories Numerical techniques for estimation of trajectoriesFormoreinfopleaseseehttp:/randomsets.ee.unimelb.edu.au/ReferencesD.Stoyan,D.Kendall,J.Mecke,Stochastic Geometry and its Applications,JohnWiley&Sons,1995D.DaleyandD.Vere-Jones,An Introduction to the Theory of Point Processes,Springer-Verlag,1988.I.Goodman,R.Mahler,andH.Nguyen,Mathematics of Data Fusion.KluwerAcademicPublishers,1997.R.Mahler,“Anintroductiontomultisource-multitargetstatisticsandapplications,”Lockheed Martin Technical Monograph,2000.R.Mahler,“Multi-targetBayesfilteringviafirst-ordermulti-targetmoments,”IEEE Trans.AES,vol.39,no.4,pp.11521178,2003.B.Vo,S.Singh,andA.Doucet,“SequentialMonteCarlomethodsformulti-targetfilteringwithrandomfinitesets,”IEEE Trans.AES,vol.41,no.4,pp.12241245,2005,.B.Vo,andW.K.Ma,“TheGaussianmixturePHDfilter,”IEEE Trans.Signal Processing,IEEE Trans.Signal Processing,Vol.54,No.11,pp.4091-4104,2006.R.Mahler,“AtheoryofPHDfilterofhigherorderintargetnumber,”inI.Kadar(ed.),SignalProcessing,SensorFusion,andTargetRecognitionXV,SPIEDefense&SecuritySymposium,Orlando,April17-22,2006B.T.Vo,B.Vo,andA.Cantoni,AnalyticimplementationsoftheCardinalizedProbabilityHypothesisDensityFilter,IEEE Trans.SP,Vol.55,No.7,Part2,pp.3553-3567,2007.D.Clark&J.Bell,“ConvergenceoftheParticle-PHDfilter,”IEEE Trans.SP,2006.A.Johansen,S.Singh,A.Doucet,andB.Vo,ConvergenceoftheSMCimplementationofthePHDfilter,Methodology and Computing in Applied Probability,2006.A.Pasha,B.Vo,H.DTuanandW.K.Ma,Closed-formsolutiontothePHDrecursionforjumpMarkovlinearmodels,FUSION,2006.D.Clark,K.Panta,andB.Vo,TrackingmultipletargetswiththeGMPHDfilter,FUSION,2006.B.T.Vo,B.Vo,andA.Cantoni,“OnMulti-BernoulliApproximationoftheMulti-targetBayesFilter,ICIF,Xian,2007.Seealso:http:/www.ee.unimelb.edu.au/staff/bv/publications.htmlOptimal Subpattern Assignment(OSPA)metric Schumacheret.al08FillupXwithn-mdummypointslocatedatadistancegreaterthan cfromanypointsinYCalculatepthorderWassersteindistancebetweenresultingsetsEfficientlycomputedusingtheHungarianalgorithm Representation of Multi-target state Gaussian Mixture PHD Prediction vk-1(x)=wk-1N(x;mk-1,Pk-1)Si=1Jk-1(i)(i)(i)vk|k-1(x)=pS,kwk-1N(x;mS,k|k-1,PS,k|k-1)+Si=1Jk-1(i)(i)(i)wk-1wb,kN(x;mb,k|k-1,Pb,k|k-1)+gk(x)S(i)(i,l)(i,l)l=1Jb,k(l)Gaussian mixtureposterior intensity at time k-1:Gaussian mixturepredicted intensity to time k:Fk|k-1vk-1 mS,k|k-1=Fk-1mk-1 PS,k|k-1=Fk-1 Pk-1 Fk-1+Qk-1(i)(i)T(i)(i)(i,l)(i,l)(l)mb,k|k-1=Fb,k-1mk-1+db,k-1 Pb,k|k-1=Fb,k-1 Pk-1(Fb,k-1)T+Qb,k-1(l)(l)(l)(i)(i)(l)Gaussian Mixture PHD Updatevk|k-1(x)=wk|k-1N(x;mk|k-1,Pk|k-1)Si=1Jk|k-1(i)(i)(i)Gaussian mixturepredicted intensity to time k:Gaussian mixture updatedintensity at time k:vk(x)=i=1Jk|k-1(i)(i)N(x;mk|k(z),Pk|k)+(1-pD,k)vk|k-1(x)SSzZk(i)(j)(i)j=1Jk|k-1SpD,k wk|k-1qk(z)+kk(z)pD,kwk|k-1qk(z)(j)Pk|k=(I-Kk Hk)Pk|k-1(i)(i)(i)Kk =Pk|k-1Hk(Hk Pk|k-1Hk+Rk)-1(i)(i)(i)TT mk|k(z)=mk|k-1+Kk(z-Hk mk|k-1)(i)(i)(i)(i)qk(z)=N(z;Hkmk|k-1,HkPk|k-1Hk+Rk)T(i)(i)(i)Ykvk|k-1vk|k-1(xk)=pS,k(xk-1)fk|k-1(xk|xk-1)vk-1(xk-1)dxk-1+gk(xk)intensity from previoustime-step intensity of spontaneousobject births kprobabilityof survivalMarkov transition densitypredictedintensitypk|k-1(n)=p,k(n-j)k|k-1vk-1,pk-1(j)probability of n-j spontaneous birthspredictedcardinalitySj=0nprobability of j surviving targets Cardinalised PHD PredictionCjl j l-jSl=jlpk-1(l)vk(xk)=vk|k-1(xk)Yk,Zk(xk)predicted intensityupdated intensitySzZkyk,z(xk)+1001(1-pD,k(xk)predicted cardinality distribution kvk|k-1,Zk(n)pk|k-1(n)updated cardinality distribution0pk(n)=0 Cardinalised PHD Updatekv,Z(n)=pK,k(|Z|j)(|Z|j)!Pj+u Sesfj(:zZk)n-(j+u)nnj=0min(|Z|,n)uS()zzSS Z,|S|=jesfj(Z)=likelihood functionprob.ofdetectionclutter intensitypD,k(xk)gk(z|xk)/kk(z)clutter cardinality distribution Mahlers MeMBer Filter(rk-1,pk-1)i=1Mk-1(i)(i)(rk|k-1,pk|k-1)i=1Mk|k-1(i)(i)(rk,pk )i=1 Mk(i)(i)prediction update Valid for low clutter rate&high probability of detectionMulti-objectBayesfilter pk-1(Xk-1|Z1:k-1)pk(Xk|Z1:k)pk|k-1(Xk|Z1:k-1)predictionupdate(Multi-targetMulti-Bernoulli)MeMBerfilter Mahler07Approximate predicted/posterior RFSs by Multi-Bernoulli RFSsBiased in Cardinality(except when probability of detection=1)(rk-1,pk-1)i=1Mk-1(i)(i)(rk|k-1,pk|k-1)i=1Mk|k-1(i)(i)(rk,pk )i=1 Mk(i)(i)prediction update 1-rk|k-1 pk|k-1,pD,k(i)(i)rk|k-1 pk|k-1(i)(i)i=1Mk|k-1vk|k-1=S(1-rk|k-1pk|k-1,pD,k)2(i)(i)rk|k-1(1-rk|k-1)pk|k-1(i)(i)(i)i=1Mk|k-1vk|k-1=S(1)1-rk|k-1(i)rk|k-1 pk|k-1(i)(i)i=1Mk|k-1vk|k-1=*S(rL,k,pL,k)(rU,k,(z),pU,k(z)(i)(i)z Zki=1Mk|k-1k(z)+vk|k-1,pD,kgk(z|)vk|k-1,pD,kgk(z|)(1)1-pk|k-1,pD,k(i)pk|k-1(1-pD,k)(i)vk|k-1,pD,kgk(z|)vk|k-1 pD,kgk(z|)*1-rk|k-1 pk|k-1,pD,k(i)(i)rk|k-1(1-pk|k-1,pD,k)(i)(i)Cardinality-Balanced MeMBer FilterCardinality-BalancedMeMBerfilterVoet.al.07LinearJumpMarkovPHDfilterPashaet.al.06 Extensions of the PHD filterExample:4-D,Linear JM target dynamics with 3 modelsExample:4-D,Linear JM target dynamics with 3 models4 targets,birth rate=3x0.05,death prob.=0.01,4 targets,birth rate=3x0.05,death prob.=0.01,clutter rate=40clutter rate=40 Extensions of the PHD filter What is a Random Finite Set(RFS)?Thenumber of pointsisrandom,Thepointshaveno orderingandarerandomLoosely,anRFSisafiniteset-valuedrandomvariableAlsoknownas:(simplefinite)pointprocessorrandompointpatternPinesaplingsinaFinishforestKelomaki&PenttinenChildhoodleukaemia&lymphomainNorthHumberlandCuzich&Edwards