UK Mirror |   Australia Mirror

Tutorial on Random-set filtering


Bayesian Multi-Object Filtering

The multi-object filtering problem

Multi-object states and measurement representation

Why random finite sets for Bayesian multi-object filtering?

Probability Hypothesis Density (PHD) Filters

Random Finite Sets and Mahler's Finite Set Statistics (FISST)

Sequential Monte Carlo PHD filter implementations

Gaussian mixture PHD filter implementations

The Cardinalised PHD filter


The multi-object filtering problem

Many engineering problems involve the on-line estimation of the state vector of a system that changes over time using a sequence of noisy observation vectors. Examples of these problems span various disciplines, ranging from econometric to biomedical engineering. Arguably, the most intuitively appealing example is target tracking. Here, the state vector contains the kinematic characteristics of the target under surveilance, and the observation vector is a (noise corrupted) sensor measurement such as a radar return. In many applications, a recursive filtering approach is employed as it allows an estimate to be made each time a new observation is received without having to reprocess existing observations.

An important generalisation of the (vector) filtering problem arises in multi-object systems where the state and observation are finite collections of vectors. In the context of the target tracking example, this corresponds to a multiple target scenario where the number of targets changes with time due to new targets appearing and old targets disappearing from the scene. Apart from occasionally failing to detect some of the existing targets, a real sensor also receives a set of spurious measurements. As a result, the observation at each time step is a set of indistinguishable elements, only some of which are generated by detected targets.

The objective of multi-object filtering is to estimate, at each time step, the multi-object state from a sequence of noisy and cluttered observation sets. Note that even in the special case where the sensor observes all targets and receives no false alarms, classical filtering methods are not applicable since there is no information on which target has generated which observation.


Multi-object states and measurements representations

Why represent the multi-object state and measurement as finite sets? can't we represent them as vectors? To address these questions, consider the fundamentals of estimation theory. Before we can even start to develop a multi-object filtering/estimation algorithm, we need some notion of estimation error for multi-object states.

Suppose we represent the multi-target state by stacking individual states into a single vector.

Clearly, a vector representation cannot represent all occurrences of multi-target state (can't represent the case with no target) and, more importantly, does not admit a meaningful and mathematically consistent notion of estimation error. A finite set, on the other hand, can represent all possible occurrences of multi-target states, and distances between sets is a well understood concept. In fact, the estimation error defined earlier (the minimum Euclidean distance over all permutations of the individual states), is a distance for sets. Similarly, stacking individual measurements into a large vector is not a satisfactory representation and the collection of measurements at each time must be represented as a finite set.


Why random finite sets for Bayesian multi-object filtering?

In the Bayesian filtering paradigm, the probability distribution/density of the state at time k given all observations up to time k is of central importance. This so-called posterior (or filtering) distribution/density, is considered to encapsulated information about the state at time k. The Bayesian paradigm treats the state and measurements as realisations of random variables. Since the (multi-object) state and (multi-object) observation are finite sets, we need the concept of a random finite set to cast the multi-object filtering problem in the Bayesian framework.


Random Finite Set and Mahler's Finite Set Statistics

The first systematic treatment of multi-sensor multi-target filtering using random set theory was conceived by Mahler in 1994 [1], [2], which later developed into finite set statistics (FISST). Moreover, this treatment was developed as part of a unified framework for data fusion using random set theory. An over view of this treatment appeared as a chapter in [3] , while the mathematical details of the treatment are given in [4]. The 2000 monograph [5] also provides an overview of FISST and how this addresses the pitfalls of traditional Bayesian multi-target filtering techniques.

The FISST Bayes multi-object recursion is generally intractable. In 2000 Mahler proposed to approximate the multi-object Bayes recursion by propagating the Probability Hypothesis Density (PHD) of the posterior multi-object state [6], [7], [8], [9]. This strategy is reminiscent of the constant gain Kalman filter that propagates the mean of the posterior single-object state. The PHD filter is an innovative and elegant engineering approximation that captivated many researchers in multi-target tracking. More importantly, it provides an important step towards the practical application of FISST. The PHD recursion still involves multiple integrals with no closed forms in general.

Mahler refined FISST to what he called generalised FISST and published this along with the derivation of the PHD filter in 2003 [9]. In addition to the FISST concepts of set derivatives and set integrals, generalised FISST adopts the construct of probability generating functionals which can be traced back to the the work of Moyal [10] in the 1960's (see also [11], [12]). In fact the derivation of the PHD filter presented in [9] was elegantly accomplished using probability generating functionals. Additionally, the relationship between FISST set derivatives and probability density (as Radon Nikodym derivatives of probability measures) for random finite sets are established in [13] [14] along with generic sequential Monte Carlo (SMC) implementations of the multi-object Bayes filter and PHD filter accompanied by convergence analysis.

Sequential Monte Carlo PHD filter implementations.

In 2003, several sequential Monte Carlo (SMC) implementations of the PHD filter were independently proposed [15], [16], [13]. Additionally, there were also SMC implementations of the multi-object Bayes filter [13], [17]. Convergence of properties of these SMC implementations were later established in [14], [18], [19].

Inspired by the SMC-PHD or particle-PHD filter implementations, important generalisations to maintain track continuity have also been proposed in [20], [21], [22], [23], [24], [25] and [26]. The SMCPHD filter requires additional processing such as clustering of the particles to extract multi-object state estimate. A study of the SMC-PHD filter performance for various clutering schemes was also given in [26].

Due to its flexibility the SMC-PHD filter was quickly adopted to solve a host of practical problems. These include feature point tracking in image sequences [27], tracking acoustic sources from time difference of arrival (TDOA) measurements [28], tracking using bistatic radar data [29],tracking in sonar images [30], [31], tracking in millimetre-wave images [32] and tracking in video [33] . See also [34] for more applications.

Gaussian mixture PHD filter implementations.

In 2005 a closed-form solution to the PHD recursion for linear Gaussian multi-target model was discovered [35]. This result was reported in [36] together with the Gaussian mixture PHD filter for linear and mildly non-linear multi-target models. While more restrictive than SMC approaches, Gaussian mixture implementations are much more efficient. Moreover, they obviate the need for clustering--an expensive step in the SMC implementation. Convergence results for the GMPHD filter were established in [37]. In [38] the Gaussian mixture PHD filter is extended to linear Jump Markov multi-target model for tracking maneuvering targets, while in [39], [40] it is extended to produce track-valued estimates.

The GMPHD filter has been applied to various problems. In [41], tracking in sonar images was demonstrated. Tracks were obtained using the technique proposed in [39] (see the sonar demonstration here). This approach was recently deployed by SeeByte Ltd on an underwater vehicle for oil pipeline tracking in commercial trials with BP, where it achieved a world record for the length of pipeline tracked. The algorithm successfully tracked 22km of pipeline continuously over 5-6 hours, which is substantially more than the previous 4km record. This work played a crucial role in the navigational control of the vehicle. A demonstration of the GMPHD tracker on radar data at Rotterdam harbour can be found here. The GMPHD filter on video data was reported in [42]. See also [34] for more applications of the GMPHD filter.

The Cardinalised PHD filter.

In 2006 Mahler published the cardinalized PHD (CPHD) recursion--a generalization of the PHD recursion that jointly propagates the posterior PHD and the posterior distribution of the number of targets [43], [44].Moreover, in [45], [46] it was shown that the CPHD recursion admits a close form solution under linear Gaussian assumptions, and Gaussian mixture implementations were proposed for linear and mildly nonlinear multi-object models. It was demonstrated in [46] that while GMCPHD filter is cubic in complexity it outperforms the NP-hard JPDA filter. Extensions to the GMPHD filter such as linear jump Markov models and track continuity apply directly to the GMCPHD filter.

The GMCPHD is demonstrated on sonar data here. The GMCPHD filter has been applied to the problem of detection and tracking of road constrained ground targets using ground moving target indicator (GMTI) radar in [47]. It has also been applied to tracking acoustic sources from TDOA measurements [48].

References

[1] Mahler R.; "Global integrated data fusion," Proc. 7th Nat. Symp. on Sensor Fusion, Vol. 1, (Unclassified) Sandia National Laboratories, Albuquerque, ERIM Ann Arbor MI, pp. 187-199, 1994.

[2] Mahler R.; "Random-set approach to data fusion" 29 July 1994 SPIE Vol: 2234.

[3] Goutsias J., Mahler R., and Nguyen H. (eds.); Random Sets Theory and Applications, Springer-Verlag New York, 1997.

[4] Goodman I., Mahler R., and Nguyen H.; Mathematics of Data Fusion, Kluwer Academic Publishers, 1997.

[5] Mahler R.; An Introduction to Multisource-Multitarget Statistics and Applications, Lockheed Martin Technical Monograph, March 15, 2000.

[6] Mahler R.; "A theoretical foundation for the Stein-Winter Probability Hypothesis Density (PHD) multi-target tracking approach," Proc. MSS Nat'l Symp. on Sensor and Data Fusion, Vol. I (Unclassified), San Antonio TX, June 2000.

[7] Mahler R.; "Multi-target moments and their application to multi-target tracking," Proc. Workshop on Estimation, Tracking and Fusion: A tribute to Yaakov Bar-Shalom, Monterey, pp. 134-166, 2001.

[8] Mahler R.; "Random set theory for target tracking and identification," Data Fusion Hand Book, D. Hall and J. Llinas (eds.), CRC press Boca Raton, pp. 14/1-14/33, 2001.

[9] Mahler R.; "Multi-target Bayes filtering via first-order multi-target moments", IEEE Trans. Aerospace & Electronic Systems, Vol. 39, No. 4, pp. 1152-1178, 2003.

[10] Moyal J. E.; "The general theory of stochastic population processes," Acta Mathematica, 108 (1962), pp. 1-31.

[11] Daley D. J., and Vere-Jones D.; An Introduction to the Theory of Point Processes, Springer, New York, 1988.

[12] Stoyan D., Kendall W., and Mecke .; Stochastic Geometry and its applications, Wiley, 2nd ed., 1995.

[13] Vo B.-N, Singh S., and Doucet A.; "Sequential Monte Carlo implementation of the PHD filter for multi-target tracking," in Proc. Int'l Conf. on Information Fusion, Cairns, Australia, pp. 792–799, 2003. preprint

[14] Vo B.-N, Singh S., and Doucet A.; "Sequential Monte Carlo methods for multi-target filtering with random finite sets," in IEEE Trans. Aerospace & Electronic Systems, vol. 41, no. 4, pp. 1224–1245, 2005. preprint

[15] Zajic T., Ravichandran R., Mahler R., Mehra R., and Noviskey M.; "Joint tracking and identification with robustness against unmodeled targets," in Signal Processing, Sensor Fusion and Target Recognition XII, SPIE Proc., vol. 5096, pp. 279–290, 2003.

[16] Sidenbladh H.; "Multi-target particle filtering for the Probability Hypothesis Density," in Proc. Int'l Conf. on Information Fusion, Cairns, Australia, pp. 800–806, 2003. pdf

[17] Sidenbladh, H., and S.-L. Wirkander; "Tracking random sets of vehicles in terrain," Proc. 2003 IEEE Workshop on Multi-Object Tracking, Madison WI, June 21 2003 paper

[18] Clark, D.E., Bell, J.,"Convergence results for the particle PHD filter,"Signal Processing, IEEE Transactions on [see also Acoustics, Speech, and Signal Processing, IEEE Transactions on] Volume 54, Issue 7, July 2006 Page(s):2652 - 2661 preprint

[19] Johansen A., Singh S., Doucet A., and Vo B.-N.; "Convergence of the SMC-PHD filter," Methodology and Computing in Applied Probability, Vol. 8, No. 2, pp. 265-291, 2006. pdf

[20] Panta, K., Vo B.-N., Singh S., and Doucet A., "Probability Hypothesis Density filter versus multiple hypothesis tracking," in I. Kadar (ed.), Signal Processing, Sensor Fusion, and Target Recognition XIII, Proc. SPIE, vol. 5429, pp. 284–295, 2004.

[21] Panta, K., Vo B.-N., and Singh S., "Improved PHD filter for multi-target tracking," in Proc. Intl. Conference on Intelligent Sensing and Information Processing, Bangalore, India, pp. 213–218, 2005. pdf

[22] Panta, K., Vo B.-N., and Singh S., "Novel data association schemes for the Probability Hypothesis Density filter," IEEE Trans. Aerospace & Electronic Systems, Vol. 43, No. 2, pp. 556-570, 2007. preprint

[23] Lin L., Bar-Shalom Y., and Kirubarajan T., "Data association combined with the Probability Hypothesis Density filter for multitarget tracking," in O. E. Drummond (ed.) Signal and Data Processing of Small Targets, Proc. SPIE, vol. 5428, pp. 464–475, 2004.

[24] Lin L.; Bar-Shalom, Y.; Kirubarajan, T., "Track labeling and PHD filter for multitarget tracking," Aerospace and Electronic Systems, IEEE Transactions on Volume 42, Issue 3, July 2006 Page(s):778 - 795

[25] Clark D.E., and Bell J., "Data association for the PHD filter," in Proc. Intl. Conference on Intelligent Sensors, Sensor Networks and Information Processing, pp. 217–222, 2005. preprint

[26] Clark, D.E.; Bell, J., "Multi-target state estimation and track continuity for the particle PHD filter," Aerospace and Electronic Systems, IEEE Transactions on Volume 43, Issue 4, October 2007. pdf

[27] Ikoma N., Uchino T., and Maeda H., "Tracking of feature points in image sequence by SMC implemention of the PHD filter," in Proc. SICE Annual Conference., vol. 2, pp. 1696–1701, 2004.

[28] Vo B.-N., Singh S., and Ma W.-K., "Tracking Multiple Speakers with Random Sets," Proc. Int. Conf. Acoustics, Speech & Signal Processing, Vol. 2, pp. 357-60, Montreal, Canada, 2004.

[29] Tobias M. and Lanterman A., "A Probability Hypothesis Density-based multitarget tracking with multiple bistatic range and doppler observations," in Proc. IEE Radar Sonar and Navigation, vol. 152, no. 3, pp. 195–205, 2005.

[30] Clark D.E., and Bell J., "Bayesian multiple target tracking in forward scan sonar images using the PHD filter," in Proc. IEE Radar Sonar Navig., vol. 152, no. 5, part 1, pp. 327–334, 2005. postprint

[31] Clark, D.; Ruiz, I.T.; Petillot, Y.; Bell, J.; Particle PHD filter multiple target tracking in sonar images Aerospace and Electronic Systems, IEEE Transactions on Volume 43, Issue 1, January 2007 Page(s):409 - 416 preprint

[32] Haworth C.D., Saint-Pern Y., Clark D.E., Trucco E., Petillot Y.R., Detection and Tracking of Multiple Metallic Objects in Millimetre-Wave Images International Journal of Computer Vision, v.71 n.2, p.183-196, February 2007 preprint

[33] Maggio, E.; Piccardo, E.; Regazzoni, C.; Cavallaro, A.; Particle PHD Filtering for Multi-Target Visual Tracking Acoustics, Speech and Signal Processing, 2007. ICASSP 2007. IEEE International Conference on Volume 1, 15-20 April 2007 Page(s):I-1101 - I-1104 pdf

[34] Mahler R., "A survey of PHD filter and CPHD filter implementations," Signal Processing, Sensor Fusion, and Target Recognition XV, SPIE Defense & Security Symposium, April 2007.

[35] Vo, B.-N.; Ma, W.-K.; "A closed-form solution for the probability hypothesis density filter," Proc. Information Fusion, 2005 8th International Conference on Volume 2, 25-28 July 2005. pdf

[36] Vo, B.-N.; Ma, W.-K., "The Gaussian mixture Probability Hypothesis Density filter," IEEE Trans. Signal Processing, IEEE Trans. Signal Processing, Vol. 54, No. 11, pp. 4091-4104, 2006. preprint

[37] Clark D.E., and Vo B.-N., "Convergence analysis of the Gaussian mixture Probability Hypothesis Density filter," IEEE Trans. Signal Processing, Vol. 55, No. 4, pp. 1204-1212, 2007. link

[38] Pasha A., Vo B.-N., Tuan H.D., and Ma W.-K., "Closed-form solution to the PHD recursion for jump Markov linear models," Proc. 9th Annual Conf. Information Fusion, Florence, Italy, 2006.

[39] Clark D.E., Panta K., and Vo B.-N., "The Gaussian mixture PHD filter Multiple Target Tracker," Proc. 9th Annual Conf. Information Fusion, Florence, Italy, 2006. pdf

[40] Panta K., Clark D.E., and Vo B.-N., "An Efficient Track Management Scheme for the Gaussian-Mixture Probability Hypothesis Density Tracker," IEEE Trans. Aerospace & Electronic Systems, 2008 (to appear). pdf

[41] Clark D.E., Vo B.-N., and Bell J., "GM-PHD filter multi-target tracking in sonar images," Proc. SPIE'06, Florida, USA, 2006. paper

[42] Pham, N.T.; Huang W.; Ong, S. H.; Tracking Multiple Objects using Probability Hypothesis Density Filter and Color Measurements Multimedia and Expo, 2007 IEEE International Conference on 2-5 July 2007 Page(s):1511 - 1514.

[43] Mahler, R., A theory of PHD filters of higher order in target number Date: 17 May 2006 SPIE Vol: 6235

[44] Mahler, R.;PHD filters of higher order in target number Aerospace and Electronic Systems, IEEE Transactions on Volume 43, Issue 4, October 2007 Page(s):1523 - 1543.

[45] Vo B. T., Vo B.-N., and Cantoni A., "The Cardinalized Probability Hypothesis Density Filter for linear Gaussian multi-target models," Proc. 40th Conf. on Info. Sciences & Systems, Princeton, USA, 2006. link

[46] Vo B. T., Vo B.-N., and Cantoni A., "Analytic implementations of the Cardinalized Probability Hypothesis Density Filter," IEEE Trans. Signal Processing, Vol. 55, No. 7, Part 2, pp. 3553-3567, 2007. link

[47] Ulmke, M.; Erdinc O.; Willett, P.; Gaussian mixture cardinalized PHD filter for ground moving target tracking Information Fusion, 2007 10th International Conference on 9-12 July 2007 Page(s):1 - 8.

[48] Pham, N.T.; Huang W.; Ong, S. H.; "Tracking multiple speakers using CPHD filter" AMC Multimedia, Germany 2007.


Heriot-Watt University and the University of Melbourne 2008