资源描述
http:/www.ee.unimelb.edu.au/staff/bv/SAMSI, RTP, NC, USA, 8 September 2008Collaborators (in no particular order):Mahler R., Singh. S., Doucet A., Ma. W.K., Panta K., Clark D., Vo B.T., Cantoni A., Pasha A., Tuan H.D., Baddeley A., Zuyev S., Schumacher D.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-update pk-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)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)observation 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 uncertaintyEstimate is correct but estimation error ?TrueMulti-target stateEstimatedMulti-target state| 2XXHow can we mathematically represent the multi-target state?2 targets2 targetsUsual practice: stack individual states into a large vector!Problem: Remedy: use()min | 0perm XXXTrueMulti-target stateEstimatedMulti-target State2 targetsno targetTrueMulti-target stateEstimatedMulti-target State2 targets1 targetWhat are the estimation errors? Error between estimate and true state (miss-distance)fundamental in estimation/filtering & controlwell-understood for single target: Euclidean distance, MSE, etcin the multi-target case: depends on state representationFor multi-target state:vector representation doesnt admit multi-target miss-distancefinite set representation admits multi-target miss-distance: distance between 2 finite setsIn fact the “distance” is a distance for sets not vectorsobservation produced by targetstarget motionstate spaceobservation space5 targets3 targetsXk-1XkNumber of measurements and their values are (random) variablesOrdering of measurements not relevant!Multi-target measurement is represented by a finite settargetstarget setobserved set X X observations X ZNeed suitable notions of density & integration pk-1(Xk-1|Z1:k-1) pk(Xk|Z1:k) pk|k-1(Xk|Z1:k-1)predictiondata-update Reconceptualize as a generalized single-target problem Mahler 94Bayesian: Model state & observation as Random Finite Sets Mahler 94S N(S) = | S|point process or random counting measurerandom finite set or random point pattern state space Estate space EBelief “density” of f : F(E) 0,) b (T ) = T f (X)dXBelief “distribution” of b (T ) = P( T ) , T EEProbability density of p : F(E) 0,) P (T ) = T p (X)m(dX)Probability distribution of P (T ) = P( T ) , T F(E)F(E) Collection of finite subsets of E State space Mahlers Finite Set Statistics (1994)Choquet (1968)TTConventional integralSet integralVo et. al. (2005)Point Process Theory (1950-1960s)xxXxdeathcreationXxspawnmotion fk|k-1(Xk |Xk-1 )Multi-object transition densityXk = Sk|k-1(Xk-1)Bk|k-1(Xk-1)GkEvolution of each element x of a given multi-object state Xk-1 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 & Doucet 03, 05, Sidenbladh 03, Vihola 05, Ma et al. 06 Restricted to a very small number of targetsMulti-target Bayes filterfor 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;( )000()iXq X( )( )( )00000()()iiiwp Xq X( )( )( )( )( )( )( )1|1111:(|)(|)(|,)iiiiiiikkkkkk kkkkkkkwwg ZXfXXq XXZ( )( )11:(|,)iikkkkkXq XXZ 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-object Bayes filter multi-object Bayes filter state of system: random vectorfirst-moment filter(e.g. a-b-g filter)state of system: random setfirst-moment filter(“PHD” filter) Single-object Multi-objectx0state spacev PHD (intensity function) of a RFS Sv(x0) = density of expected number of objects at x0 v(x)dx = expected number of objects in SS= mean of, N(S), the random counting measure at Sstate 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!vk|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 Gkfk|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 vk(xk|Z1:k) zZkDk(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) |11()kkk kkvv YFParticle approximation of vk-1 Particle approximation of vk state spaceVo, Singh & Doucet 03, 05, Sidenbladh 03, Mahler & Zajic 03The PHD (or intensity function) vk is not a probability densityThe PHD propagation equation is not a standard Bayesian recursionSequential MC implementation of the PHD filterNeed to cluster the particles to obtain multi-target estimatesInitialise;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;kikp )(x)()(1)()()(1|ikkikkkikkpJwxxgkikq)(x)(),()()(1)(1)(1|)(1|ikkikikikkkikkqwwxxxf)(1|1)(1|)(,)(,)()(1)()()()(1ikkZzLJjjkkjzkkizkiDikwwzpwkkk+xxxykyConvergence: Vo, Singh & Doucet 05, Clark & Bell 06, Johansen et. al. 06Closed-form solution to the PHD recursion exists for linear Gaussian multi-target model vk-1( . |Z1:k-1)vk(. |Z1:k) vk|k-1(. |Z1:k-1) 1| Fkk kY 1| Fkk kYwk-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)PHD filterGaussian Mixture (GM) PHD filter Vo & Ma 05, 06Gaussian mixture prior intensity Gaussian mixture posterior intensities at all subsequent times Extended & Unscented Kalman PHD filter Vo & Ma 06Jump Markov PHD filter Pasha et. al. 06Track continuity Clark et. al. 06Drawback of PHD filter: High variance of cardinality estimate Relax Poisson assumption: allows arbitrary cardinality distributionJointly propagate: intensity function & probability generating function of cardinality. More complex PHD update step (higher computational costs) CPHD filter Mahler 06,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 wk-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=0 pk|k-1(n)n=0 pk(n)n=0 Particle CPHD filter Vo 08Closed-form solution to the CPHD recursion exists for linear Gaussian multi-target modelGaussian mixture prior intensity Gaussian mixture posterior intensities at all subsequent times Vo et. al. 06, 07Particle-PHD filter can be extended to the CPHD filter 1020304050607080901000510TimeCardinality StatisticsTrueMeanStDev1020304050607080901000510TimeCardinality StatisticsTrueMeanStDev1000 MC trial averageGMCPHD filterGMPHD filter1000 MC trial average(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-object Bayes filter pk-1(Xk-1|Z1:k-1) pk(Xk|Z1:k) pk|k-1(Xk|Z1:k-1)predictionupdate (Multi-target Multi-Bernoulli ) MeMBer filter Mahler 07, biasedApproximate predicted/posterior RFSs by Multi-Bernoulli RFSsCardinality-Balanced MeMBer filter Vo et. al. 07, unbiased(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) (rG,k, pG,k) (i)(i)(i)(i)i=1Mk-1i=1MG,krk-1 pk-1, pS,k(i)(i) fk|k-1(|), pk-1 pS,k(i)pk-1, pS,k(i)term for object birthsCardinality-Balanced MeMBer filter Vo et. 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)rk|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-1(1 rk|k-1pk|k-1, pD,k)2(i)(i)(i)(i)(i)i=1Mk|k-1k(z) +1 rk|k-1(i)rk|k-1 pk|k-1(i)(i)i=1Mk|k-1pD,kgk(z|)rk|k-1pk|k-1, pD,kgk(z|)1 rk|k-1(i)(i)(i)i=1Mk|k-1Cardinality-Balanced MeMBer filter Vo et. al. 07Closed-form (Gaussian mixture) solution Vo et. al. 07, Particle implementation Vo et. 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)More useful than PHD filters in highly non-linear problems 10 targets max on scene, with births/deaths 4D states: x-y position/velocity, linear Gaussianobservations: x-y position, linear Gaussian -1000 -800 -600 -400 -2000200400600800 1000-1000-800-600-400-20002004006008001000 x-coordinate (m)y-coordinate (m)/start/end positionsDynamics constant velocity model:v = 5ms-2, survival probability:pS,k = 0.99,Observations additive Gaussian noise: =10m, detection probability: pD,k = 0.98, uniform Poisson clutter:c = 2.5x10-6m-210203040506070809010005101520TimeCardinality StatisticsTrueMeanStDev10203040506070809010005101520TimeCardinality StatisticsCardinality-BalancedRecursionMahlersMeMBerRecursion1000 MC trial average1000 MC trial averageCPHD Filter has better performance1020304050607080901000102030TimeOSPA Loc (m)(c=300, p=1) 1020304050607080901000100200300TimeOSPA Card (m)(c=300, p=1) 1020304050607080901000100200300TimeOSPA (m)(c=300, p=1) GM-CBMeMBerGM-PHDGM-CPHDGM-MeMBer1000 MC trial averageCB-MeMBerFilter has better performance1020304050607080901000100200300TimeOSPA (m)(c=300, p=1) SMC-CBMeMBerSMC-PHDSMC-CPHDSMC-MeMBer102030405060708090100050100TimeOSPA Loc (m)(c=300, p=1) 1020304050607080901000100200300TimeOSPA Card (m)(c=300, p=1) Thank You!For more info please see http:/randomsets.ee.unimelb.edu.au/D. Stoyan, D. Kendall, J. Mecke, Stochastic Geometry and its Applications, John Wiley & Sons, 1995D. Daley and D. Vere-Jones, An Introduction to the Theory of Point Processes, Springer-Verlag, 1988. I. Goodman, R. Mahler, and H. Nguyen, Mathematics of Data Fusion. Kluwer Academic Publishers, 1997.R. Mahler, “An introduction to multisource-multitarget statistics and applications,” Lockheed Martin Technical Monograph, 2000.R. Mahler, “Multi-target Bayes filtering via first-order multi-target moments,” IEEE Trans. AES, vol. 39, no. 4, pp. 11521178, 2003.B. Vo, S. Singh, and A. Doucet, “Sequential Monte Carlo methods for multi-target filtering with random finite sets,” IEEE Trans. AES, vol. 41, no. 4, pp. 12241245, 2005,.B. Vo, and W. K. Ma, “The Gaussian mixture PHD filter,” IEEE Trans. Signal Processing, IEEE Trans. Signal Processing, Vol. 54, No. 11, pp. 4091-4104, 2006. R. Mahler, “A theory of PHD filter of higher order in target number,” in I. Kadar (ed.), Signal Processing, Sensor Fusion, and Target Recognition XV, SPIE Defense & Security Symposium, Orlando, April 17-22, 2006B. T. Vo, B. Vo, and A. Cantoni, Analytic implementations of the Cardinalized Probability Hypothesis Density Filter, IEEE Trans. SP, Vol. 55, No. 7, Part 2, pp. 3553-3567, 2007.D. Clark & J. Bell, “Convergence of the Particle-PHD filter,” IEEE Trans. SP, 2006.A. Johansen, S. Singh, A. Doucet, and B. Vo, Convergence of the SMC implementation of the PHD filter, Methodology and Computing in Applied Probability, 2006. A. Pasha, B. Vo, H. D Tuan and W. K. Ma, Closed-form solution to the PHD recursion for jump Markov linear models, FUSION, 2006.D. Clark, K. Panta, and B. Vo, Tracking multiple targets with the GMPHD filter, FUSION, 2006. B. T. Vo, B. Vo, and A. Cantoni, “On Multi-Bernoulli Approximation of the Multi-target Bayes Filter, ICIF, Xian, 2007.See also: http:/www.ee.unimelb.edu.au/staff/bv/publications.htmlOptimal Subpattern Assignment (OSPA) metric Schumacher et. al 08Fill up X with n - m dummy points located at a distance greater than c from any points in YCalculate pth order Wasserstein distance between resulting setsEfficiently computed using the Hungarian algorithm vk-1(x) = wk-1N(x; mk-1, Pk-1)i=1Jk-1(i)(i)(i)vk|k-1(x) =pS,kwk-1N(x; mS,k|k-1, PS,k|k-1) +i=1Jk-1(i)(i)(i)wk-1wb,kN(x; mb,k|k-1, Pb,k|k-1) + gk(x)(i)(i,l)(i,l)l=1Jb,k(l) Gaussian mixture posterior intensity at time k-1: Gaussian mixture predicted 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)vk|k-1(x) = wk|k-1N(x; mk|k-1, Pk|k-1)i=1Jk|k-1(i)(i)(i) Gaussian mixture predicted intensity to time k: Gaussian mixture updated intensity 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) z Zk(i)(j)(i)j=1Jk|k-1pD,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 Gkprobabilityof survivalMarkov transition densitypredictedintensitypk|k-1(n) = p G,k(n - j) k|k-1vk-1,pk-1(j)probability of n - j spontaneous birthspredictedcardinalityj=0nprobability of j surviving targetsCjl j l-jl=jlpk-1 (l) vk(xk) = vk|k-1(xk)Yk, Zk(xk) predicted intensityupdated intensity zZkyk,z(xk)+1001(1pD,k(xk)predicted cardinality distribution kvk|k-1, Zk(n)pk|k-1(n) updated cardinality distribution0pk(n) =0kv, Z(n) =pK,k(|Z|j) (|Z|j)! Pj+u esfj(: zZk) n-(j+u)nnj=0min(|Z|,n)u ( ) z zSS Z,|S|=j esfj(Z) =likelihood functionprob. ofdetectionclutter intensitypD,k(xk)gk(z|xk)/kk(z)clutter cardinality distribution (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-object Bayes filter pk-1(Xk-1|Z1:k-1) pk(Xk|Z1:k) pk|k-1(Xk|Z1:k-1)predictionupdate (Multi-target Multi-Bernoulli ) MeMBer filter Mahler 07Approximate 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 =(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 =(1)1 rk|k-1(i)rk|k-1 pk|k-1(i)(i)i=1Mk|k-1vk|k-1 =*(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 filter Vo et. al. 07Linear Jump Markov PHD filter Pasha et. al. 06-6-4-20246x 104-6-4-20246x 104x coordinate (in m)y coordinate (in m)Aircraft 1 start of flight at k= 1;end of flight at k=90 Aircraft 2 start of flight at k= 3;end of flight at k=95 Aircraft 3 start of flight at k= 12;end of flight at k=100 Payload 1 separates from Aircraft 1at k= 31; end of flight at k=100 Payload 2 separates from Aircraft 2at k= 44; end of flight at k=88 102030405060708090100-505x 104time stepx coordinate (in m)PHD filter estimatesTrue tracks102030405060708090100-505x 104time stepy coordinate (in m)The number of points is random, The points have no ordering and are randomLoosely, an RFS is a finite set-valued random variableAlso known as: (simple finite) point process or random point patternPine saplings in a Finish forest Kelomaki & PenttinenChildhood leukaemia & lymphoma in North Humberland Cuzich & Edwards
展开阅读全文