多目标跟踪英文

RandomSet/PointProcessinMulti-TargetTrackingBa-NguVo

EEEDepartment

UniversityofMelbourne

AustraliaSAMSI,RTP,NC,USA,8September2008Collaborators(innoparticularorder):MahlerR.,Singh.S.,DoucetA.,Ma.W.K.,PantaK.,ClarkD.,VoB.T.,CantoniA.,PashaA.,TuanH.D.,BaddeleyA.,ZuyevS.,SchumacherD.TheBayes(single-target)filterMulti-targettrackingSystemrepresentationRandomfiniteset&BayesianMulti-targetfilteringTractablemulti-targetfiltersProbabilityHypothesisDensity(PHD)filterCardinalizedPHDfilterMulti-BernoullifilterConclusionsOutlineTheBayes(single-target)Filterstate-vectortargetmotionstatespaceobservationspacexkxk-1zk-1zk

fk|k-1(xk|xk-1)MarkovTransitionDensityMeasurementLikelihoodgk(zk|xk)Objectivemeasurementhistory

(z1,…,zk)posterior(filtering)pdfofthestatepk(xk|z1:k)SystemModelstate-vectortargetmotionstatespaceobservationspacexkxk-1zk-1zkBayesfilterpk-1(xk-1

|z1:k-1)pk|k-1(xk|z1:k-1)pk(xk|z1:k)predictiondata-update

pk-1(xk-1|z1:k-1)

dxk-1

fk|k-1(xk|xk-1)gk(zk|xk)K-1pk|k-1(xk|z1:k-1)TheBayes(single-target)Filterpk-1(.

|z1:k-1)pk|k-1(.

|z1:k-1)pk(.

|z1:k)predictiondata-updateBayesfilterN(.;mk-1,Pk-1)N(.;mk|k-1,Pk|k-1)N(.;(mk,Pk)Kalmanfilteri=1N{wk|k-1,xk|k-1}i=1N(i)(i){wk,xk}

i=1

N(i)(i){wk-1,xk-1}(i)(i)Particlefilterstate-vectortargetmotionstatespaceobservationspacexkxk-1zk-1zk

fk|k-1(xk|xk-1)gk(zk|xk)TheBayes(single-target)FilterMulti-targettrackingobservation

producedbytargetstargetmotionstatespaceobservationspace5targets3targetsXk-1XkObjective:JointlyestimatethenumberandstatesoftargetsChallenges:RandomnumberoftargetsandmeasurementsDetectionuncertainty,clutter,associationuncertaintyMulti-targettrackingSystemRepresentationEstimateiscorrectbutestimationerror???TrueMulti-targetstateEstimatedMulti-targetstateHowcanwemathematicallyrepresentthemulti-targetstate?2targets2targetsUsualpractice:stackindividualstatesintoalargevector!Problem:Remedy:useTrueMulti-targetstateEstimatedMulti-targetState2targetsnotargetTrueMulti-targetstateEstimatedMulti-targetState2targets1targetSystemRepresentationWhataretheestimationerrors?Errorbetweenestimateandtruestate(miss-distance)fundamentalinestimation/filtering&controlwell-understoodforsingletarget:Euclideandistance,MSE,etcinthemulti-targetcase:dependsonstaterepresentationFormulti-targetstate:vectorrepresentationdoesn’tadmitmulti-targetmiss-distancefinitesetrepresentationadmitsmulti-targetmiss-distance:distancebetween2finitesetsInfactthe“distance”

isadistanceforsetsnotvectorsSystemRepresentationobservationproducedbytargetstargetmotionstatespaceobservationspace5targets3targetsXk-1XkNumberofmeasurementsandtheirvaluesare(random)variablesOrderingofmeasurementsnotrelevant!Multi-targetmeasurementisrepresentedbyafinitesetSystemRepresentationRFS&BayesianMulti-targetFilteringtargetstargetsetobservedsetXobservationsXZNeedsuitablenotionsofdensity&integrationpk-1(Xk-1|Z1:k-1)pk(Xk|Z1:k)pk|k-1(Xk|Z1:k-1)predictiondata-updateReconceptualizeasageneralizedsingle-targetproblem[Mahler94]Bayesian:Modelstate&observationasRandomFiniteSets[Mahler94]RFS&BayesianMulti-targetFilteringSNS(S)=|SS|pointprocessorrandomcountingmeasurerandomfinitesetorrandompointpatternSstatespaceEstatespaceEBelief“density”ofSfS:F(E)®[0,¥)bS(T)=òTfS(X)dXBelief““distribution””ofSbS(T)=P(SÍT),TÍEESProbabilitydensityofSpS:F(E)®[0,¥)PS(T)=òTpS(X)m(dX)ProbabilitydistributionofSPS(T)=P(SÎT),TÍF(E)F(E)SCollectionoffinitesubsetsofEStatespaceMahler’’sFiniteSetStatistics(1994)Choquet(1968)TTConventionalintegralSetintegralVoet.al.(2005)PointProcessTheory(1950-1960’’s)RFS&BayesianMulti-targetFilteringxx’X’xdeathcreationX’xspawnmotionMulti-targetMotionModelfk|k-1(Xk|Xk-1)Multi-objecttransitiondensityXk=Sk|k-1(Xk-1)ÈBk|k-1(Xk-1)ÈGkEvolutionofeachelementxofagivenmulti-objectstateXk-1Multi-targetObservationModelgk(Zk|Xk)Multi-objectlikelihoodZk=Qk(Xk)ÈKk(Xk)xzxlikelihoodmisdetectionclutterstatespaceobservationspaceObservationprocessforeachelementxofagivenmulti-objectstateXkpk-1(Xk-1|Z1:k-1)pk(Xk|Z1:k)pk|k-1(Xk|Z1:k-1)predictiondata-updateComputationallyintractableingeneralNoclosedformsolutionParticleorSMCimplementation[Vo,Singh&Doucet03,05,Sidenbladh03,Vihola05,Maetal.06]RestrictedtoaverysmallnumberoftargetsMulti-targetBayesFilterMulti-targetBayesfilterParticleMulti-targetBayesFilterAlgorithmfori=1:N,%Initialise=>Sample:Compute:end;normaliseweights;fork=1:kmax,fori=1:N,%Update=>Sample:Update:end;normaliseweights;resample;MCMCstep;end;pk-1(Xk-1|Z1:k-1)pk(Xk|Z1:k)pk|k-1(Xk|Z1:k-1)predictiondata-updateMulti-targetBayesfilter:veryexpensive!single-objectBayesfiltermulti-objectBayesfilterstateofsystem:randomvectorfirst-momentfilter(e.g.a-b-gfilter)stateofsystem:randomsetfirst-momentfilter(“PHD””filter)Single-objectMulti-objectThePHDFilterx0statespacevSPHD(intensityfunction)ofaRFSSSvS(x0)

=densityofexpectednumberofobjectsat

x0TheProbabilityHypothesisDensityvS(x)dx=expectednumberofobjectsinSS=meanof,NS(S),therandomcountingmeasureatSThePHDFilterstatespacevkvk-1PHDfiltervk-1(xk-1|Z1:k-1)vk(xk|Z1:k)vk|k-1(xk|Z1:k-1)PHDpredictionPHDupdateMulti-objectBayesfilterpk-1(Xk-1|Z1:k-1)pk(Xk|Z1:k)pk|k-1(Xk|Z1:k-1)predictionupdateAvoidsdataassociation!PHDPredictionvk|k-1(xk|Z1:k-1)=fk|k-1(xk,xk-1)vk-1(xk-1|Z1:k-1)dxk-1+gk(xk)intensityfromprevioustime-step

termforspontaneousobjectbirths

=intensityof

Gkfk|k-1(xk,xk-1)=ek|k-1(xk-1)fk|k-1(xk|xk-1)+bk|k-1(xk|xk-1)Markovtransitionintensityprobabilityofobjectsurvivaltermforobjectsspawnedbyexistingobjects=intensityofBk(xk-1)MarkovtransitiondensitypredictedintensityNk|k-1=vk|k-1

(x|Z1:k-1)dxpredictedexpectednumberofobjects(Fk|k-1a)(xk)

=

fk|k-1(xk,x)a(x)dx

+gk(xk)

vk|k-1=

Fk|k-1vk-1PHDUpdatevk(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)dxNk=vk(x|Z1:k)dxBayes-updatedintensitypredictedintensity(fromprevioustime)intensityoffalsealarmssensorlikelihoodfunctionprobabilityofdetectionexpectednumberofobjectsmeasurementvk

=

Ykvk|k-1(Yka)(x)

=zZk<yk,z,a>+kk(z)

yk,z(x)

+1-

pD,k(x)]a(x)[

SParticlePHDfilterParticleapproximationofvk-1Particleapproximationofvkstatespace[Vo,Singh&Doucet03,05],[Sidenbladh03],[Mahler&Zajic03]ThePHD(orintensityfunction)vkisnotaprobabilitydensityThePHDpropagationequationisnotastandardBayesianrecursionSequentialMCimplementationofthePHDfilterNeedtoclustertheparticlestoobtainmulti-targetestimatesParticlePHDfilterAlgorithmInitialise;fork=1:kmax,fori=1:Jk,Sample:;compute:;end;fori=Jk+1:Jk+Lk-1,Sample:;compute:;end;fori=1:Jk+Lk-1,Update:;end;RedistributetotalmassamongLkresampledparticles;end;Convergence:[Vo,Singh&Doucet05],[Clark&Bell06],[Johansenet.al.06]GaussianMixturePHDfilterClosed-formsolutiontothePHDrecursionexistsforlinearGaussianmulti-targetmodel

vk-1(.

|Z1:k-1)vk(.

|Z1:k)

vk|k-1(.

|Z1:k-1){wk-1,mk-1,Pk-1}i=1Jk-1(i)(i)(i){wk|k-1,mk|k-1,Pk|k-1}i=1Jk|k-1(i)(i)(i){wk,mk,Pk}

i=1

Jk(i)(i)(i)PHDfilterGaussianMixture(GM)PHDfilter[Vo&Ma05,06]GaussianmixturepriorintensityÞGaussianmixtureposteriorintensitiesatallsubsequenttimesExtended&UnscentedKalmanPHDfilter[Vo&Ma06]JumpMarkovPHDfilter[Pashaet.al.06]Trackcontinuity[Clarket.al.06]CardinalisedPHDFilterDrawbackofPHDfilter:HighvarianceofcardinalityestimateRelaxPoissonassumption:allowsarbitrarycardinalitydistributionJointlypropagate:intensityfunction&probabilitygeneratingfunctionofcardinality.MorecomplexPHDupdatestep(highercomputationalcosts)CPHDfilter[Mahler06,07]vk-1(xk-1|Z1:k-1)vk(xk|Z1:k)vk|k-1(xk|Z1:k-1)intensitypredictionintensityupdate

pk-1(n|Z1:k-1)pk(n|Z1:k)

pk|k-1(n|Z1:k-1)cardinalitypredictioncardinalityupdateGaussianMixtureCPHDFilter{wk-1,xk-1}i=1Jk-1(i)(i){wk|k-1,xk|k-1}i=1Jk|k-1(i)(i){wk,xk}i=1Jk(i)(i)intensitypredictionintensityupdatecardinalitypredictioncardinalityupdate{pk-1(n)}n=0{pk|k-1(n)}n=0{pk(n)}n=0ParticleCPHDfilter[Vo08]Closed-formsolutiontotheCPHDrecursionexistsforlinearGaussianmulti-targetmodelGaussianmixturepriorintensityÞGaussianmixtureposteriorintensitiesatallsubsequenttimes[Voet.al.06,07]Particle-PHDfiltercanbeextendedtotheCPHDfilterCPHDfilterDemonstration1000MCtrialaverageGMCPHDfilterGMPHDfilterCPHDfilterDemonstration1000MCtrialaverageComparisonwithJPDA:lineardynamics,sv=5,sh=10,4targets,SonarimagesCPHDfilterDemonstrationMeMBerFilter{(rk-1,pk-1)}i=1Mk-1(i)(i){(rk|k-1,pk|k-1)}i=1Mk|k-1(i)(i){(rk,pk)}i=1Mk(i)(i)predictionupdateValidforlowclutterrate&highprobabilityofdetectionMulti-objectBayesfilterpk-1(Xk-1|Z1:k-1)pk(Xk|Z1:k)pk|k-1(Xk|Z1:k-1)predictionupdate(Multi-targetMulti-Bernoulli)MeMBerfilter[Mahler07],biasedApproximatepredicted/posteriorRFSsbyMulti-BernoulliRFSsCardinality-BalancedMeMBerfilter[Voet.al.07],unbiasedCardinality-BalancedMeMBerFilter{(rk-1,pk-1)}i=1Mk-1(i)(i){(rk|k-1,pk|k-1)}i=1Mk|k-1(i)(i){(rk,pk)}i=1Mk(i)(i)predictionupdate{(rP,k|k-1,pP,k|k-1)}È{(rG,k,pG,k)}(i)(i)(i)(i)i=1Mk-1i=1MG,krk-1á

pk-1,pS,kñ(i)(i)áfk|k-1(·|·),pk-1pS,kñ(i)ápk-1,pS,kñ(i)termforobjectbirthsCardinality-BalancedMeMBerfilter[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=1Mk(i)(i)predictionupdate{(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-BalancedMeMBerFilterrk|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-1ápk|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-1ápk|k-1,pD,kgk(z|·)ñ1-

rk|k-1(i)(i)(i)i=1Mk|k-1SCardinality-BalancedMeMBerfilter[Voet.al.07]Cardinality-BalancedMeMBerFilterClosed-form(Gaussianmixture)solution[Voet.al.07],Particleimplementation[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=1Mk(i)(i)predictionupdate{wk-1,xk-1}j=1Jk-1(i,j)(i,j)j=1Jk|k-1(i,j)(i,j){wk|k-1,xk|k-1}{wk,xk}j=1Jk(i,j)(i,j){wk-1,mk-1,Pk-1}j=1Jk-1(i,j)(i,j)(i,j){wk|k-1,mk|k-1,Pk|k-1}j=1Jk|k-1(i,j)(i,j)(i,j){wk,mk,Pk}j=1Jk(i,j)(i,j)(i,j)MoreusefulthanPHDfiltersinhighlynon-linearproblemsPerformancecomparisonExample:10targetsmaxonscene,withbirths/deaths4Dstates: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-BalancedRecursionMahler’sMeMBerRecursion1000MCtrialaverageGaussianimplementationGaussianimplementation1000MCtrialaverageCPHDFilterhasbetterperformanceParticleimplementation1000MCtrialaverageCB-MeMBerFilterhasbetterperformanceConcludingRemarksThankYou!RandomFiniteSetframeworkRigorousformulationofBayesianmulti-targetfilteringLeadstoefficientalgorithmsFutureresearchdirectionsTrackbeforedetectPerformancemeasureformulti-objectsystemsNumericaltechniquesforestimationoftrajectoriesReferencesOptimalSubpatternAssignment(OSPA)metric[Schumacheret.al08]FillupXwithn-mdummypointslocatedatadistancegreaterthancfromanypointsinYCalculatepthorderWassersteindistancebetweenresultingsetsEfficientlycomputedusingtheHungarianalgorithmRepresentationofMulti-targetstateGaussianMixturePHDPrediction

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)Gaussianmixtureposteriorintensityattimek-1:Gaussianmixturepredictedintensitytotimek:Fk|k-1vk-1

mS,k|k-1=Fk-1mk-1

PS,k|k-1

=Fk-1Pk-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-1Pk-1

(Fb,k-1)T

+Qb,k-1(l)(l)(l)(i)(i)(l)GaussianMixturePHDUpdatevk|k-1(x)=wk|k-1N(x;mk|k-1,Pk|k-1)Si=1Jk|k-1(i)(i)(i)Gaussianmixturepredictedintensitytotimek:Gaussianmixtureupdatedintensityattimek:vk(x)=i=1Jk|k-1(i)(i)

N(x;

mk|k(z),

Pk|k)+(1-

pD,k)vk|k-1(x)

S

SzÎ

Zk(i)(j)(i)j=1Jk|k-1SpD,kwk|k-1qk(z)

+kk(z)pD,kwk|k-1qk(z)(j)

Pk|k

=(I-KkHk)Pk|k-1(i)(i)(i)

Kk

=Pk|k-1Hk(HkPk|k-1Hk+Rk

)-1(i)(i)(i)TT

mk|k(z)=mk|k-1+Kk(z-Hkmk|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)intensityfromprevioustime-stepintensityofspontaneousobjectbirthsGkprobabilityofsurvivalMarkovtransitiondensitypredictedintensitypk|k-1(n)=p,k(n-j)k|k-1[vk-1,pk-1](j)probabilityofn-jspontaneousbirthspredictedcardinalitySj=0nprobabilityofjsurvivingtargetsCardinalisedPHDPredictionCjl<pS,k,vk-1>j<1-pS,k,vk-1>l-jSl=j¥<1,vk-1>lpk-1(l)

vk(xk)=

vk|k-1(xk)Yk,Zk(xk)predictedintensityupdatedintensity

SzZkyk,z(xk)+<¡k[vk|k-1,Zk],pk|k-1><¡k[vk|k-1,Zk\{z}],pk|k-1>10<¡k[vk|k-1,Zk],pk|k-1><¡k[vk|k-1,Zk],pk|k-1>01(1-pD,k(xk))predictedcardinalitydistribution¡k[vk|k-1,Zk](n)pk|k-1(n)updatedcardinalitydistribution0<¡k[vk|k-1,Zk],pk|k-1>pk(n)=0CardinalisedPHDUpdate¡k[v,Z](n)=pK,k(|Z|–j)

(|Z|–j)!

Pj+u

S

esfj({<v,yk,z>:zZk})

<1-

pD,k,v>n-(j+u)<1,v>nnj=0min(|Z|,n)uS(P)

z

zSSÍ

Z,|S|=j

esfj(Z)=likelihoodfunctionprob.ofdetectionclutterintensitypD,k(xk)gk(z|xk)<1,kk>/kk(z)cluttercardinalitydistributionMahler’sMeMBerFilter{(rk-1,pk-1)}i=1Mk-1(i)(i){(rk|k-1,pk|k-1)}i=1Mk|k-1(i)(i){(rk,pk)}i=1Mk(i)(i)predictionupdateValidforlowclutterrate&highprobabilityofdetectionMulti-objectBayesfilterpk-1(Xk-1|Z1:k-1)pk(Xk|Z1:k)pk|k-1(Xk|Z1:k-1)predictionupdate(Multi-targetMulti-Bernoulli)MeMBerfilter[Mahler07]Approximatepredicted/posteriorRFSsbyMulti-BernoulliRFSsBiasedinCardinality(exceptwhenprobabilityofdetection=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=1Mk(i)(i)predictionupdate1-

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-1ápk|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-BalancedMeMBerFilterCardinality-BalancedMeMBerfilter[Voet.al.07]LinearJumpMarkovPHDfilter[Pashaet.al.06]ExtensionsofthePHDfilterExample:4-D,LinearJMtargetdynamicswith3models4targets,birthrate=3x0.05,deathprob.=0.01,clutterrate=40ExtensionsofthePHDfilterWhatisaRandomFiniteSet(RFS)?Thenumberofpointsisrandom,ThepointshavenoorderingandarerandomLoosely,anRFSisafiniteset-valuedrandomvariableAlsoknownas:(simplefinite)pointprocessorrandompointpatternPinesaplingsinaFinishforest[Kelomaki&Penttinen]Childhoodleukaemia&lymphomainNorthHumberland[Cuzich&Edwards]9、静夜夜四无无邻，，荒居居旧业业贫。。。12月月-2212月月-22Friday,December23,202210、雨中黄叶叶树，灯下下白头人。。。09:17:0609:17:0609:1712/23/20229:17:06AM11、以我独独沈久，，愧君相相见频。。。12月-2209:17:0609:17Dec-2223-Dec-2212、故人江江海别，，几度隔隔山川。。。09:17:0609:17:0609:17