IEEE粒子濾波(課堂)課件

RandomFiniteSetsinStochasticFilteringBa-NguVo

EEEDepartment

UniversityofMelbourne

Australia.au/staff/bv/IEEEVictorianChapterJuly28,2009RandomFiniteSetsinStochastStochasticFilteringHistoryN.Wiener(1894-1964)

A.N.Kolmogorov(1903-1987)R.E.Kalman(1930-)1940’s:Wienerfilter PioneeringworkbyWiener,Kolmogorov1950’s:Kalmanfilter WorkbyBode&Shannon,Zadeh&Ragazzini,Levinson,Swerling,Stratonovich,etc.1970’s:Aerospaceapplications Sorenson&Alspach,Singer,Bar-Shalom,Reid,etc.1960’s:

PublicationoftheKalmanfilter,Kalman-Bucyfilter,Schmidt’s1stimplementation–ApolloprogramLMSalgorithmbyWidrow&Hoff2StochasticFilteringHistoParticleFilter(1990’s--) Computationaltoolsfornon-linearnon-Gaussianfiltering Gordon,Salmond&Smith,Doucet…RandomFiniteSet(1990’s--)

Unifiedframeworkformulti-objectfiltering&control ProbabilityHypothesisDensity(PHD)filters,Bernoullifilter PioneeringworkbyMahlerStochasticFiltering:ThePresent3ParticleFilter(1990’s--)RandTheBayes(nonlinear)FilterPracticalChallengesMulti-ObjectFilteringRandomFiniteSetPHD/CPHDFilters&ApplicationsConclusionsOutline4TheBayes(nonlinear)FilterTheBayes(nonlinear)Filterstate-vectorstatedynamicstatespaceobservationspacexkxk-1zk-1zk

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

(z1,…,zk)posteriorpdfofthestatepk(xk|z1:k)SystemModel5TheBayes(nonlinear)Filtstate-vectorstatedynamicstatespaceobservationspacexkxk-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)

pk|k-1(xk|z1:k-1)TheBayes(nonlinear)Filter

fk|k-1(xk|xk-1)gk(zk|xk)

gk(zk|xk)pk-1(xk-1|z1:k-1)dxk6state-vectorstatedynamicstatestate-vectorstatedynamicstatespaceobservationspacexkxk-1zk-1zkTheBayes(nonlinear)Filter

fk|k-1(xk|xk-1)gk(zk|xk)pk-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)Particlefilter7state-vectorstatedynamicstatestate-vectorstatedynamicstatespaceobservationspacexkxk-1zk-1zkPracticalChallenges

fk|k-1(xk|xk-1)gk(zk|xk)Sofar,weassumedexactly1observationateachtime

HoldsonlyforasmallnumberofapplicationsPracticalmeasuringdevice:mayfailtodetecttrueobservation(detectionuncertainty)&picksupfalseobservations(clutter)8state-vectorstatedynamicstatePracticalChallengesNotdetectedDetectionuncertainty:DetectedFalseobservations(clutter)orNumberoffalseobservationsunknownrandomFalse9PracticalChallengesNotdPracticalChallengesNoinformationonwhichistheobservationofthestateNumberofobservationsisarandomvariable.‘+’Observation=NotdetectedDetectedFalse10PracticalChallengesNoinstate-vectorstatedynamicstatespaceobservationspacexkxk-1zk-1zkPracticalChallengesSummaryofpracticalchallenges:Numberofobservationsisrandom&timevaryingTrueobservationmaynotbepresentDonotknowwhichobservationsarefalse/trueOrderingofobservationsnotrelevant11state-vectorstatedynamicstateobservation

producedbyobjectsstatedynamicstatespaceobservationspace5objects3objectsXk-1XkObjective:Jointlyestimatethenumber&statesofobjectsNumerousapplications:defence,surveillance,robotics,biomed,…Challenges:RandomnumberofobjectsandmeasurementsDetectionuncertainty,clutter,associationuncertaintyMulti-ObjectFiltering12observationproducedbyobjeEstimateiscorrectbutestimationerror???TrueMulti-objectstateEstimatedMulti-objectstateHowcanwemathematicallyrepresentthemulti-objectstate?2objectsUsualpractice:stackindividualstatesintoalargevector!2objectsRemedy:useFundamentalinconsistency:Multi-ObjectFiltering13EstimateiscorrectbutestimaTrueMulti-objectstateEstimatedMulti-objectState2objectsnoobjectTrueMulti-objectstateEstimatedMulti-objectState2objects1objectWhataretheestimationerrors?

Multi-ObjectFiltering14TrueEstimated2objectsnoobjecMiss-distance:errorbetweenestimateandtruestatemeasureshowcloseanestimateistothetruevaluewell-understoodforsingletarget:Euclideandistance,MSE,etcfundamentalinestimation/filtering&controlVectorrepresentationdoesn’tadmitmulti-objectmiss-distanceFinitesetrepresentationadmitsmulti-objectmiss-distance,e.g.Haussdorf,Wasserstein,OSPA[Schuhmacheret.al.08]Infactthe“distance” isadistanceforsetsnotvectorsMulti-ObjectFiltering15Miss-distance:errorbetweeneMulti-ObjectFilteringstatesmulti-objectstatemulti-objectobservationXobservationsXZ

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

pk(Xk|Z1:k)

pk|k-1(Xk|Z1:k-1)predictiondata-updateReconceptualiseasafiniteset-valuedfilteringproblemMulti-objectstate&observationrepresentedbyfinitesetsBayesianframeworktreatsstate/observationasrandomvariablesBayesianmulti-objectfiltering

requiresrandomfiniteset(RFS)16Multi-ObjectFilteringstatRandomFiniteSetThenumberofpointsisrandom,ThepointshavenoorderingandarerandomAnRFSisafiniteset-valuedrandomvariableAlsoknownas:pointprocessorrandompointpatternWhatisarandomfiniteset(RFS)?Example1:BernoulliRFSsample

u~uniform[0,1]if

u<r,

sample

x~p(.),end;

EExample2:multi-BernoulliRFS=

UnionofBernoulliRFSs17RandomFiniteSetThenumbeRandomFiniteSetESamplen

~Poiss(r),

fori=1:n,

sample

xi~p(.),end;

Example3:PoissonRFSESamplen

~c(.),

fori=1:n,

sample

xi~p(.),end;

Example4:i.i.d.clusterRFS18RandomFiniteSetESamplenRandomFiniteSetNeedsuitablenotionsofdensity/integrationforfiniteset

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

pk(Xk|Z1:k)

pk|k-1(Xk|Z1:k-1)predictiondata-update??statesmulti-objectstatemulti-objectobservationXobservationsXZMulti-objectBayesfilter19RandomFiniteSetNeedsuitRandomFiniteSetBelief“density”

ofS

fS:F(E)

?[0,￥)

bS

(T)

=

òT

fS

(X)dXBelief“distribution”

ofSbS

(T)=P(SíT),Tí

EESProbabilitydensity

ofS

pS:F(E)

?[0,￥)

PS

(T

)

=

òT

pS

(X)m(dX)Probabilitydistribution

ofSPS

(T

)=P(S?T),

T

í

F(E)F(E)SCollectionoffinitesubsetsof

E

Statespace

Mahler’sFiniteSetStatistics(1994)Choquet(1968)TTConventionalintegralSetintegralPointProcessTheory(1950-1960’s)VSD(2005)20RandomFiniteSetBelief“d

Computationallyexpensive!single-objectBayesfilter

multi-objectBayesfilter

stateofsystem:

randomvectorfirst-momentfilter(e.g.

a-b-g

filter)stateofsystem:

randomsetfirst-momentfilter(“PHD”filter)

Single-object

Multi-objectThePHDFilter

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

pk(Xk|Z1:k)

pk|k-1(Xk|Z1:k-1)predictiondata-updateMulti-objectBayesfilter21Computationallyexpensive!sinThePHDFilterx0statespacevPHD(intensityfunction)ofanRFSS

v(x)dx

=expectednumberofobjectsin

SSv(x0)

=densityofexpectednumberofobjectsat

x022ThePHDFilterx0statespacThePHDFilterstatespace

vk

vk-1

PHDfilter[Mahler03]vk-1(xk-1|Z1:k-1)vk(xk|Z1:k)

vk|k-1(xk|Z1:k-1)PHDpredictionPHDupdateMulti-objectBayesfilter

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

pk(Xk|Z1:k)

pk|k-1(Xk|Z1:k-1)predictionupdateAvoidsdataassociation!23ThePHDFilterstatespaceThePHDFilter:Predictionvk|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

termforspontaneousobjectbirthsfk|k-1(xk,xk-1)=ek|k-1(xk-1)fk|k-1(xk|xk-1)+bk|k-1(xk|xk-1)MarkovtransitionintensityprobabilityofobjectsurvivaltermforobjectsspawnedbyexistingobjectsMarkovtransitiondensitypredictedintensityNk|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-124ThePHDFilter:PredictionThePHDFilter: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-updatedintensitypredictedintensity(fromprevioustime)intensityoffalsealarmssensorlikelihoodfunctionprobabilityofdetectionexpectednumberofobjectsmeasurementvk

=

Ykvk|k-1(Yka)(x)

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

yk,z(x)

+1-

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

S25ThePHDFilter:Updatevk(ThePHDFilter

vk-1(.

|Z1:k-1)vk(.

|Z1:k)

vk|k-1(.

|Z1:k-1)GaussianMixturePHDFilter[VM05,06],

ParticlePHDFilter[VSD03,05],[Mahler&Zajic03],[Sidenbladh03]{wk-1,xk-1}j=1Jk-1(j)(j)j=1Jk|k-1(j)(j){wk|k-1,xk|k-1}{wk,xk}

j=1

Jk(j)(j){wk-1,mk-1,Pk-1}j=1Jk-1(j)(j)(j){wk|k-1,mk|k-1,Pk|k-1}j=1Jk|k-1(j)(j)(j){wk,mk,Pk}

j=1

Jk(j)(j)(j)26ThePHDFiltervk-1(.|Z1ThePHDfilterExtended&UnscentedKalmanPHDfilter[VM06]JumpMarkovPHDfilter[Pashaet.al.06]Trackcontinuity[Clarket.al.06]Convergence[Clarket.al.07]BritishPetrolium(Pipelinetracking)07Visualtracking[Phamet.al.07]Celltracking[Juanget.al.09]Bistaticradar[Tobias&Lanterman05]

Tracklabellingtrackassociation[Pantaet.al.07,Linet.al06]Convergence[VDS05,Johansenetal07,Clark&Bell06,]Computervision[Maggioet.al.07,Wanget.al.2008,]AuxiliaryparticlePHDfilter[Whitleyet.al.07]Trafficintensityestimation[Battistelliet.al.08]Particle-PHDfilter[VSD03,05]

GM-PHDfilter[VM05,06]27ThePHDfilterExtended&UThePHDfilterVideodata:trackingfootballplayers[Phametal.07]DatacourtesyofCzyzet.al.28ThePHDfilterVideodata:ThePHDfilterVideotrackingofpeoplewalking(340frames)[Phametal.07]DatacourtesyofK.SmithIDIAPResearchInstitute.29ThePHDfilterVideotrackiTheCardinalisedPHDFilterDrawbackofPHDfilter:Highvarianceofcardinalityestimate

RelaxPoissonassumption:allowsanycardinalitydistributionJointlypropagate:intensityfunction&cardinalitydistribution.

HighercomputationalcostthanPHDStillcheaperthanstate-of-the-arttraditionaltechniquesCPHDfilter[Mahler06,07],GaussianMixtureCPHDfilter[VVC06,07]vk-1(xk-1|Z1:k-1)vk(xk|Z1:k)

vk|k-1(xk|Z1:k-1)intensitypredictionintensityupdateck-1(n|Z1:k-1)ck(n|Z1:k)

ck|k-1(n|Z1:k-1)cardinalitypredictioncardinalityupdate30TheCardinalisedPHDFilteGMTIRadar[Ulmkeet.al.07]TestedbyFGAN(NATOBoldAvengerexercise)07,Acousticsourcetracking[Phamet.al.08]TestedonMSTWGandSEABARDatasets[Erdincet.al.08]ComparisonwithMHT[Svenssonetal.09]Convoytracking[Pollardet.al.09]Trackingfromaerialimage[Pollardet.al.09]LockheedMartin(SpaceFence)09.GM-CPHDfilter[VVC05,06]TheCardinalisedPHDFilter31GMTIRadar[Ulmkeet.al.07]GSonarimagesTheCardinalisedPHDFilter32SonarimagesTheCardinalisLargescalemultipletargettrackingwithsmallfalsealarmrateCourtesyofLockheedMartinTheCardinalisedPHDFilter33LargescalemultipletargettrUpto1500closelyspacedtargetsonastandardlaptop!CourtesyofLockheedMartinOSPAdistance(satisfiesallmetricaxioms)=pertargetcardinality&stateerrorTheCardinalisedPHDFilter34Upto1500closelyspacedtargSLAM(SimultaneousLocalisationandMapping)Objective:Jointlyestimaterobotpose&map(setoflandmarks)ThePHDFilterinSLAM35SLAM(SimultaneousLocalisatioThePHDFilterinSLAMRobotposeMapMeasurementsControlsMeasurementlikelihoodSetintegralTransitiondensityRFS-SLAMpredictionRFS-SLAMupdate(Feature)Map=finitesetoflandmarksBayesianSLAMrequiresmodellingthemapbyanRFSSetintegralRFS-SLAM[Mullaneet.al.08]36ThePHDFilterinSLAMRoboMapping:specialcaseofSLAMwithknownrobotposesPHDapproximation:propagate1stmomentofthemapRFSPHDoftheposteriormapRFSThePHDFilterinSLAM37Mapping:specialcaseofSLAMMapping:specialcaseofSLAMwithknownrobotposesThePHDFilterinSLAM38Mapping:specialcaseofSLAMExperiment:NanyangTechnologicalUniversityCampus

PHDSLAM(approximationofRFS-SLAMrecursion):AugmentlandmarkswiththevehicleposeRepresentsetofaugmentedlandmarksasamarkedpointprocessPropagatePHDofthemarkedpointprocessThePHDFilterinSLAM39Experiment:NanyangTechnologiLowclutter:All3algorithmscanclosetheloopHigherclutter:OnlyPHD-SLAMcanclosetheloopGroundtruthplottedingreenThePHDFilterinSLAM40Lowclutter:Higherclutter:GroConcludingRemarksThankYou!RandomFiniteSetFilteringBorneoutofpractical&fundamentalnecessity

SignificanttheoreticalextensionofclassicalfilteringYieldsefficientalgorithmssuchasthePHDfiltersBeyondthePHDfilters

Multi-Bernoulli,Gauss-PoissonfiltersFilteringwithimagedataRobustnessStochasticcontrolFormoreinfopleasesee.auSeealso:.au/staff/bv/publications.html41ConcludingRemarksThankYouSomeReferencesBooksD.DaleyandD.Vere-Jones,AnIntroductiontotheTheoryofPointProcesses,Springer-Verlag,1988.D.Stoyan,D.Kendall,J.Mecke,StochasticGeometryanditsApplications,JohnWiley&Sons,1995I.Goodman,R.Mahler,andH.Nguyen,MathematicsofDataFusion.KluwerAcademicPublishers,1997.R.Mahler,StatisticalMultisource-MultitargetInformationFusion,ArtechHouse,2007.M.Mallick,V.Krisnamurthy,B.-N.Vo(eds),AdvancedTopicsandApplicationsinIntegratedTracking,Classification,andSensorManagement,IEEE-Wiley(underreview)PapersR.Mahler,“Multi-targetBayesfilteringviafirst-ordermulti-targetmoments,”IEEETrans.AES,vol.39,no.4,pp.1152–1178,2003.B.-N.Vo,S.Singh,andA.Doucet,“SequentialMonteCarlomethodsformulti-targetfilteringwithrandomfinitesets,”IEEETrans.AES,vol.41,no.4,pp.1224–1245,2005.B.-N.Vo,andW.K.Ma,“TheGaussianmixturePHDfilter,”IEEETrans.SignalProcessing,IEEETrans.SignalProcessing,Vol.54,No.11,pp.4091-4104,2006.

R.Mahler,“PHDfilterofhigherorderintargetnumber,”IEEETrans.Aerospace&ElectronicSystems,vol.43,no.4,pp.1523–1543,2007B.T.Vo,B.-N.Vo,andA.Cantoni,"AnalyticimplementationsoftheCardinalizedProbabilityHypothesisDensityFilter,"IEEETrans.SignalProcessing,Vol.55,

No.7,

Part2,

pp.3553-3567,2007.B.-T.Vo,B.-NVo,andA.Cantoni,"TheCardinalityBalancedMulti-targetMulti-Bernoullifilteranditsimplementations,"IEEETrans.SignalProcessing,vol.57,no.2,pp.409–423,2009.J.Mullane,B.-N.Vo,M.AdamsandS.Wijesoma,"ARandomSetFormulationforBayesianSLAM,"InternationalConferenceonIntelligentRobotsandSystems,Nice,France,2008.

42SomeReferencesBooks42Collaborators(innoparticularorder)MahlerR., LockheedMartinSinghS., CambridgeDoucetA., U.BritishColumbiaMaW.K., ChineseU.HongKongPantaK., BAESystemsBaddeleyA., U.WesternAustraliaClarkD., Herriot-WattU.VoB.T., U.WesternAustraliaCantoniA., U.WesternAustraliaPashaA., U.NewSouthWalesTuanH.D., U.NewSouthWalesZuyevS., U.StrathclydeMullaneJ., NanyangTechnologicalU.AdamsM., NanyangTechnologicalU.WijesomaS., NanyangTechnologicalU.SchumacherD., U.BernRisticB., DSTOAustraliaGuernJ., LockheedMartinPhamT., INRIASuterD. U.Adelaide43Collaborators(innoparticRandomFiniteSetsinStochasticFilteringBa-NguVo

EEEDepartment

UniversityofMelbourne

Australia.au/staff/bv/IEEEVictorianChapterJuly28,2009RandomFiniteSetsinStochastStochasticFilteringHistoryN.Wiener(1894-1964)

A.N.Kolmogorov(1903-1987)R.E.Kalman(1930-)1940’s:Wienerfilter PioneeringworkbyWiener,Kolmogorov1950’s:Kalmanfilter WorkbyBode&Shannon,Zadeh&Ragazzini,Levinson,Swerling,Stratonovich,etc.1970’s:Aerospaceapplications Sorenson&Alspach,Singer,Bar-Shalom,Reid,etc.1960’s:

PublicationoftheKalmanfilter,Kalman-Bucyfilter,Schmidt’s1stimplementation–ApolloprogramLMSalgorithmbyWidrow&Hoff45StochasticFilteringHistoParticleFilter(1990’s--) Computationaltoolsfornon-linearnon-Gaussianfiltering Gordon,Salmond&Smith,Doucet…RandomFiniteSet(1990’s--)

Unifiedframeworkformulti-objectfiltering&control ProbabilityHypothesisDensity(PHD)filters,Bernoullifilter PioneeringworkbyMahlerStochasticFiltering:ThePresent46ParticleFilter(1990’s--)RandTheBayes(nonlinear)FilterPracticalChallengesMulti-ObjectFilteringRandomFiniteSetPHD/CPHDFilters&ApplicationsConclusionsOutline47TheBayes(nonlinear)FilterTheBayes(nonlinear)Filterstate-vectorstatedynamicstatespaceobservationspacexkxk-1zk-1zk

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

(z1,…,zk)posteriorpdfofthestatepk(xk|z1:k)SystemModel48TheBayes(nonlinear)Filtstate-vectorstatedynamicstatespaceobservationspacexkxk-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)

pk|k-1(xk|z1:k-1)TheBayes(nonlinear)Filter

fk|k-1(xk|xk-1)gk(zk|xk)

gk(zk|xk)pk-1(xk-1|z1:k-1)dxk49state-vectorstatedynamicstatestate-vectorstatedynamicstatespaceobservationspacexkxk-1zk-1zkTheBayes(nonlinear)Filter

fk|k-1(xk|xk-1)gk(zk|xk)pk-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)Particlefilter50state-vectorstatedynamicstatestate-vectorstatedynamicstatespaceobservationspacexkxk-1zk-1zkPracticalChallenges

fk|k-1(xk|xk-1)gk(zk|xk)Sofar,weassumedexactly1observationateachtime

HoldsonlyforasmallnumberofapplicationsPracticalmeasuringdevice:mayfailtodetecttrueobservation(detectionuncertainty)&picksupfalseobservations(clutter)51state-vectorstatedynamicstatePracticalChallengesNotdetectedDetectionuncertainty:DetectedFalseobservations(clutter)orNumberoffalseobservationsunknownrandomFalse52PracticalChallengesNotdPracticalChallengesNoinformationonwhichistheobservationofthestateNumberofobservationsisarandomvariable.‘+’Observation=NotdetectedDetectedFalse53PracticalChallengesNoinstate-vectorstatedynamicstatespaceobservationspacexkxk-1zk-1zkPracticalChallengesSummaryofpracticalchallenges:Numberofobservationsisrandom&timevaryingTrueobservationmaynotbepresentDonotknowwhichobservationsarefalse/trueOrderingofobservationsnotrelevant54state-vectorstatedynamicstateobservation

producedbyobjectsstatedynamicstatespaceobservationspace5objects3objectsXk-1XkObjective:Jointlyestimatethenumber&statesofobjectsNumerousapplications:defence,surveillance,robotics,biomed,…Challenges:RandomnumberofobjectsandmeasurementsDetectionuncertainty,clutter,associationuncertaintyMulti-ObjectFiltering55observationproducedbyobjeEstimateiscorrectbutestimationerror???TrueMulti-objectstateEstimatedMulti-objectstateHowcanwemathematicallyrepresentthemulti-objectstate?2objectsUsualpractice:stackindividualstatesintoalargevector!2objectsRemedy:useFundamentalinconsistency:Multi-ObjectFiltering56EstimateiscorrectbutestimaTrueMulti-objectstateEstimatedMulti-objectState2objectsnoobjectTrueMulti-objectstateEstimatedMulti-objectState2objects1objectWhataretheestimationerrors?

Multi-ObjectFiltering57TrueEstimated2objectsnoobjecMiss-distance:errorbetweenestimateandtruestatemeasureshowcloseanestimateistothetruevaluewell-understoodforsingletarget:Euclideandistance,MSE,etcfundamentalinestimation/filtering&controlVectorrepresentationdoesn’tadmitmulti-objectmiss-distanceFinitesetrepresentationadmitsmulti-objectmiss-distance,e.g.Haussdorf,Wasserstein,OSPA[Schuhmacheret.al.08]Infactthe“distance” isadistanceforsetsnotvectorsMulti-ObjectFiltering58Miss-distance:errorbetweeneMulti-ObjectFilteringstatesmulti-objectstatemulti-objectobservationXobservationsXZ

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

pk(Xk|Z1:k)

pk|k-1(Xk|Z1:k-1)predictiondata-updateReconceptualiseasafiniteset-valuedfilteringproblemMulti-objectstate&observationrepresentedbyfinitesetsBayesianframeworktreatsstate/observationasrandomvariablesBayesianmulti-objectfiltering

requiresrandomfiniteset(RFS)59Multi-ObjectFilteringstatRandomFiniteSetThenumberofpointsisrandom,ThepointshavenoorderingandarerandomAnRFSisafiniteset-valuedrandomvariableAlsoknownas:pointprocessorrandompointpatternWhatisarandomfiniteset(RFS)?Example1:BernoulliRFSsample

u~uniform[0,1]if

u<r,

sample

x~p(.),end;

EExample2:multi-BernoulliRFS=

UnionofBernoulliRFSs60RandomFiniteSetThenumbeRandomFiniteSetESamplen

~Poiss(r),

fori=1:n,

sample

xi~p(.),end;

Example3:PoissonRFSESamplen

~c(.),

fori=1:n,

sample

xi~p(.),end;

Example4:i.i.d.clusterRFS61RandomFiniteSetESamplenRandomFiniteSetNeedsuitablenotionsofdensity/integrationforfiniteset

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

pk(Xk|Z1:k)

pk|k-1(Xk|Z1:k-1)predictiondata-update??statesmulti-objectstatemulti-objectobservationXobservationsXZMulti-objectBayesfilter62RandomFiniteSetNeedsuitRandomFiniteSetBelief“density”

ofS

fS:F(E)

?[0,￥)

bS

(T)

=

òT

fS

(X)dXBelief“distribution”

ofSbS

(T)=P(SíT),Tí

EESProbabilitydensity

ofS

pS:F(E)

?[0,￥)

PS

(T

)

=

òT

pS

(X)m(dX)Probabilitydistribution

ofSPS

(T

)=P(S?T),

T

í

F(E)F(E)SCollectionoffinitesubsetsof

E

Statespace

Mahler’sFiniteSetStatistics(1994)Choquet(1968)TTConventionalintegralSetintegralPointProcessTheory(1950-1960’s)VSD(2005)63RandomFiniteSetBelief“d

Computationallyexpensive!single-objectBayesfilter

multi-objectBayesfilter

stateofsystem:

randomvectorfirst-momentfilter(e.g.

a-b-g

filter)stateofsystem:

randomsetfirst-momentfilter(“PHD”filter)

Single-object

Multi-objectThePHDFilter

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

pk(Xk|Z1:k)

pk|k-1(Xk|Z1:k-1)predictiondata-updateMulti-objectBayesfilter64Computationallyexpensive!sinThePHDFilterx0statespacevPHD(intensityfunction)ofanRFSS

v(x)dx

=expectednumberofobjectsin

SSv(x0)

=densityofexpectednumberofobjectsat

x065ThePHDFilterx0statespacThePHDFilterstatespace

vk

vk-1

PHDfilter[Mahler03]vk-1(xk-1|Z1:k-1)vk(xk|Z1:k)

vk|k-1(xk|Z1:k-1)PHDpredictionPHDupdateMulti-objectBayesfilter

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

pk(Xk|Z1:k)

pk|k-1(Xk|Z1:k-1)predictionupdateAvoidsdataassociation!66ThePHDFilterstatespaceThePHDFilter:Predictionvk|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

termforspontaneousobjectbirthsfk|k-1(xk,xk-1)=ek|k-1(xk-1)fk|k-1(xk|xk-1)+bk|k-1(xk|x