1、Random Set/Point Process in Multi-Target Tracking,Ba-Ngu VoEEE Department University of MelbourneAustralia,.au/staff/bv/,SAMSI, RTP, NC, USA, 8 September 2008,Collaborators (in no particular order): Mahler R., Singh. S., Doucet A., Ma. W.K., Panta K., Clark D., Vo B.T., Canto

2、ni A., Pasha A., Tuan H.D., Baddeley A., Zuyev S., Schumacher D.,The Bayes (single-target) filter Multi-target tracking System representation Random finite set 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-

3、1),pk(Xk|Z1:k),pk|k-1(Xk|Z1:k-1),prediction,data-update,Multi-target Bayes filter: very expensive!,single-object Bayes filter,multi-object Bayes filter,state of system: random vector,first-moment filter (e.g. a-b-g filter),state of system: random set,first-moment filter (“PHD” filter),Single-object,

4、Multi-object,The PHD Filter,x0,state space,vS PHD (intensity function) of a RFS S,S,The Probability Hypothesis Density,vS(x)dx = expected number of objects in S,S,= mean of, NS(S), the random counting measure at S,The PHD Filter,state space,vk,vk-1,PHD filter,vk-1(xk-1|Z1:k-1),vk(xk|Z1:k),vk|k-1(xk|

5、Z1:k-1),PHD prediction,PHD update,Multi-object Bayes filter,pk-1(Xk-1|Z1:k-1),pk(Xk|Z1:k),pk|k-1(Xk|Z1:k-1),prediction,update,Avoids data association!,PHD Prediction,vk|k-1(xk |Z1:k-1) = fk|k-1(xk, xk-1) vk-1(xk-1|Z1:k-1)dxk-1 + gk(xk),fk|k-1(xk, xk-1) = ek|k-1(xk-1) fk|k-1(xk|xk-1) + bk|k-1(xk|xk-1

6、),probability of object survival,term for objects spawned by existing objects = intensity of Bk(xk-1),Markov transition density,PHD Update,vk(xk|Z1:k) , S,zZk,Dk(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)dx,Bayes-updated intens

7、ity,predicted intensity (from previous time),intensity of false alarms,sensor likelihood function,probability of detection,expected number of objects,measurement,Particle PHD filter,Particle approximation of vk-1,Particle approximation of vk,state space,Vo, Singh for k =1: kmax , for i =1: Jk , Samp

8、le: ; 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 & Doucet 05, Clark & Bell 06, Johansen et. al. 06,Gaussian Mixture PHD filter,Closed-form solution to the PH

9、D recursion exists for linear Gaussian multi-target model,PHD filter,Gaussian Mixture (GM) PHD filter Vo & Ma 05, 06,Gaussian mixture prior intensity Gaussian mixture posterior intensities at all subsequent times,Extended & Unscented Kalman PHD filter Vo & Ma 06 Jump Markov PHD filter Pasha et. al.

10、06 Track continuity Clark et. al. 06,Cardinalised PHD Filter,Drawback of PHD filter: High variance of cardinality estimate,Relax Poisson assumption: allows arbitrary cardinality distribution,Jointly propagate: intensity function & probability generating function of cardinality.,More complex PHD upda

11、te 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 prediction,intensity update,Gaussian Mixture CPHD Filter,wk-1, xk-1,i=1,Jk-1,(i),(i),wk|k-1, xk|k-1,i=1,Jk|k-1,(i),(i),wk, xk ,i=1,Jk,(i),(i),intensity prediction,intensity update,

12、cardinality prediction,cardinality update,pk-1(n),n=0,pk|k-1(n),n=0,pk(n),n=0,Particle CPHD filter Vo 08,Closed-form solution to the CPHD recursion exists for linear Gaussian multi-target model,Gaussian mixture prior intensity Gaussian mixture posterior intensities at all subsequent times Vo et. al.

13、 06, 07,Particle-PHD filter can be extended to the CPHD filter,CPHD filter Demonstration,1000 MC trial average,GMCPHD filter,GMPHD filter,CPHD filter Demonstration,1000 MC trial average,Comparison with JPDA: linear dynamics, sv = 5, sh = 10, 4 targets,Sonar images,CPHD filter Demonstration,MeMBer Fi

14、lter,(rk-1, pk-1),i=1,Mk-1,(i),(i),(rk|k-1, pk|k-1),i=1,Mk|k-1,(i),(i),(rk, pk ),i=1,Mk,(i),(i),prediction,update,Valid for low clutter rate & high probability of detection,Multi-object Bayes filter,pk-1(Xk-1|Z1:k-1),pk(Xk|Z1:k),pk|k-1(Xk|Z1:k-1),prediction,update,(Multi-target Multi-Bernoulli ) MeM

15、Ber filter Mahler 07, biased,Approximate predicted/posterior RFSs by Multi-Bernoulli RFSs,Cardinality-Balanced MeMBer filter Vo et. al. 07, unbiased,Cardinality-Balanced MeMBer Filter,(rk-1, pk-1),i=1,Mk-1,(i),(i),(rk|k-1, pk|k-1),i=1,Mk|k-1,(i),(i),(rk, pk ),i=1,Mk,(i),(i),prediction,update,(rP,k|k

16、-1, pP,k|k-1) (rG,k, pG,k),(i),(i),(i),(i),i=1,Mk-1,i=1,MG,k, fk|k-1(|), pk-1 pS,k,(i),pk-1, pS,k,(i),term for object births,Cardinality-Balanced MeMBer filter Vo et. al. 07,(rk-1, pk-1),i=1,Mk-1,(i),(i),(rk|k-1, pk|k-1),i=1,Mk|k-1,(i),(i),(rk, pk ),i=1,Mk,(i),(i),prediction,update,(rL,k, pL,k) (rU,

17、k,(z), pU,k(z),(i),(i),zZk,i=1,Mk|k-1,Cardinality-Balanced MeMBer Filter,rk|k-1(1- rk|k-1) pk|k-1, pD,kgk(z|),(1- rk|k-1pk|k-1, pD,k)2,(i),(i),(i),(i),(i),i=1,Mk|k-1,S,k(z) +,pD,kgk(z|),Cardinality-Balanced MeMBer filter Vo et. al. 07,Cardinality-Balanced MeMBer Filter,Closed-form (Gaussian mixture)

18、 solution Vo et. al. 07,Particle implementation Vo et. al. 07,(rk-1, pk-1),i=1,Mk-1,(i),(i),(rk|k-1, pk|k-1),i=1,Mk|k-1,(i),(i),(rk, pk ),i=1,Mk,(i),(i),prediction,update,wk-1, xk-1,j=1,Jk-1,(i,j),(i,j),j=1,Jk|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-1,j=1,Jk-1,(i,j)

19、,(i,j),(i,j),wk|k-1, mk|k-1, Pk|k-1,j=1,Jk|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,Performance comparison,Example:10 targets max on scene, with births/deaths 4D states: x-y position/velocity, linear Gaussian observations:

20、x-y position, linear Gaussian,/ start/end positions,Dynamics 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-2,Cardinality-Balanced Recursion,Mahlers MeMBer R

21、ecursion,1000 MC trial average,Gaussian implementation,Gaussian implementation,1000 MC trial average,CPHD Filter has better performance,Particle implementation,1000 MC trial average,CB-MeMBer Filter has better performance,Concluding Remarks,Thank You!,Random Finite Set framework Rigorous formulation

22、 of Bayesian multi-target filtering Leads to efficient algorithms Future research directions Track before detect Performance measure for multi-object systems Numerical techniques for estimation of trajectories,For more info please see .au/,References,D. Stoyan, D. Kend

23、all, J. Mecke, Stochastic Geometry and its Applications, John Wiley & Sons, 1995 D. 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 int

24、roduction 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 m

25、ethods 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 fi

26、lter 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, 2006 B. T. Vo, B. Vo, and A. Cantoni, Analytic implementations of the Cardinalized Probability Hypothesis Density Filter, I

27、EEE 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

28、. 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 Mu

29、lti-target Bayes Filter, ICIF, Xian, 2007. See also: .au/staff/bv/publications.html,Optimal Subpattern Assignment (OSPA) metric Schumacher et. al 08,Fill up X with n - m dummy points located at a distance greater than c from any points in Y Calculate pth order Wasserstein dis

30、tance between resulting sets Efficiently computed using the Hungarian algorithm,Representation of Multi-target state,Gaussian Mixture PHD Prediction,Gaussian mixture posterior intensity at time k-1:,Gaussian mixture predicted intensity to time k:,Gaussian Mixture PHD Update,Gaussian mixture predicte

31、d intensity to time k:,Gaussian mixture updated intensity at time k:,vk|k-1(xk) = pS,k(xk-1) fk|k-1(xk|xk-1) vk-1(xk-1)dxk-1 + gk(xk),intensity from previous time-step,intensity of spontaneous object births Gk,probability of survival,Markov transition density,predicted intensity,pk|k-1(n) = p,k(n -

32、j) k|k-1vk-1,pk-1(j),probability of n - j spontaneous births,predicted cardinality,probability of j surviving targets,Cardinalised PHD Prediction,Cjl j l-j,l,pk-1 (l),predicted cardinality distribution,kvk|k-1, Zk(n)pk|k-1(n),updated cardinality distribution,0,pk(n) =,0,Cardinalised PHD Update,Mahlers MeMBer Filter,(rk-1, pk-1),i=1,Mk-1,(i),(i),(rk|k-1, pk|k-1),i=1,Mk|k-1,(i),(i),(rk, pk ),i=1,Mk,(i),(i),prediction,update,Valid for low clutter rate & high probability of detection,Multi-object Baye