TY - JOUR T1 - MCMC Data Association and Sparse Factorization Updating for Real Time Multitarget Tracking with Merged and Multiple Measurements JF - IEEE Transactions on Pattern Analysis and Machine Intelligence Y1 - 2006 A1 - Zia Khan A1 - Balch, T. A1 - Dellaert, F. KW - algorithms KW - approximate inference KW - Artificial intelligence KW - auxiliary variable particle filter KW - Computational efficiency KW - continuous state space KW - downdating KW - Image Enhancement KW - Image Interpretation, Computer-Assisted KW - Inference algorithms KW - Information Storage and Retrieval KW - laser range scanner KW - laser range scanner. KW - Least squares approximation KW - least squares approximations KW - Least squares methods KW - linear least squares KW - Markov chain Monte Carlo KW - Markov processes KW - MCMC data association KW - merged measurements KW - Monte Carlo methods KW - Movement KW - multiple merged measurements KW - multitarget tracking KW - particle filter KW - particle filtering (numerical methods) KW - Particle filters KW - Pattern Recognition, Automated KW - probabilistic model KW - QR factorization KW - Radar tracking KW - Rao-Blackwellized KW - real time multitarget tracking KW - Reproducibility of results KW - Sampling methods KW - Sensitivity and Specificity KW - sensor fusion KW - sparse factorization updating KW - sparse least squares KW - State-space methods KW - Subtraction Technique KW - target tracking KW - updating AB - In several multitarget tracking applications, a target may return more than one measurement per target and interacting targets may return multiple merged measurements between targets. Existing algorithms for tracking and data association, initially applied to radar tracking, do not adequately address these types of measurements. Here, we introduce a probabilistic model for interacting targets that addresses both types of measurements simultaneously. We provide an algorithm for approximate inference in this model using a Markov chain Monte Carlo (MCMC)-based auxiliary variable particle filter. We Rao-Blackwellize the Markov chain to eliminate sampling over the continuous state space of the targets. A major contribution of this work is the use of sparse least squares updating and downdating techniques, which significantly reduce the computational cost per iteration of the Markov chain. Also, when combined with a simple heuristic, they enable the algorithm to correctly focus computation on interacting targets. We include experimental results on a challenging simulation sequence. We test the accuracy of the algorithm using two sensor modalities, video, and laser range data. We also show the algorithm exhibits real time performance on a conventional PC VL - 28 SN - 0162-8828 CP - 12 ER - TY - JOUR T1 - MCMC-based particle filtering for tracking a variable number of interacting targets JF - IEEE Transactions on Pattern Analysis and Machine Intelligence Y1 - 2005 A1 - Zia Khan A1 - Balch, T. A1 - Dellaert, F. KW - algorithms KW - Animals KW - Artificial intelligence KW - Computer simulation KW - Computer vision KW - Filtering KW - filtering theory KW - HUMANS KW - Image Enhancement KW - Image Interpretation, Computer-Assisted KW - Index Terms- Particle filters KW - Information Storage and Retrieval KW - Insects KW - interacting targets KW - Markov chain Monte Carlo sampling step KW - Markov chain Monte Carlo. KW - Markov chains KW - Markov processes KW - Markov random field motion KW - Markov random fields KW - Models, Biological KW - Models, Statistical KW - Monte Carlo Method KW - Monte Carlo methods KW - MOTION KW - Movement KW - multitarget filter KW - multitarget tracking KW - particle filtering KW - Particle filters KW - Particle tracking KW - Pattern Recognition, Automated KW - Sampling methods KW - Subtraction Technique KW - target tracking KW - Video Recording AB - We describe a particle filter that effectively deals with interacting targets, targets that are influenced by the proximity and/or behavior of other targets. The particle filter includes a Markov random field (MRF) motion prior that helps maintain the identity of targets throughout an interaction, significantly reducing tracker failures. We show that this MRF prior can be easily implemented by including an additional interaction factor in the importance weights of the particle filter. However, the computational requirements of the resulting multitarget filter render it unusable for large numbers of targets. Consequently, we replace the traditional importance sampling step in the particle filter with a novel Markov chain Monte Carlo (MCMC) sampling step to obtain a more efficient MCMC-based multitarget filter. We also show how to extend this MCMC-based filter to address a variable number of interacting targets. Finally, we present both qualitative and quantitative experimental results, demonstrating that the resulting particle filters deal efficiently and effectively with complicated target interactions. VL - 27 SN - 0162-8828 CP - 11 ER - TY - CONF T1 - Multitarget tracking with split and merged measurements T2 - IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2005. CVPR 2005 Y1 - 2005 A1 - Zia Khan A1 - Balch, T. A1 - Dellaert, F. KW - Application software KW - Computer vision KW - Detection algorithms KW - Detectors KW - filtering theory KW - Markov chain Monte Carlo based auxiliary variable particle filter KW - Markov processes KW - merged measurements KW - Monte Carlo methods KW - multiple hypothesis tracker KW - multitarget tracking KW - parameter estimation KW - Particle filters KW - Particle tracking KW - Rao-Blackwellized filter KW - split measurements KW - target tracking KW - Trajectory AB - In many multitarget tracking applications in computer vision, a detection algorithm provides locations of potential targets. Subsequently, the measurements are associated with previously estimated target trajectories in a data association step. The output of the detector is often imperfect and the detection data may include multiple, split measurements from a single target or a single merged measurement from several targets. To address this problem, we introduce a multiple hypothesis tracker for interacting targets that generate split and merged measurements. The tracker is based on an efficient Markov chain Monte Carlo (MCMC) based auxiliary variable particle filter. The particle filter is Rao-Blackwellized such that the continuous target state parameters are estimated analytically, and an MCMC sampler generates samples from the large discrete space of data associations. In addition, we include experimental results in a scenario where we track several interacting targets that generate these split and merged measurements. JA - IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2005. CVPR 2005 VL - 1 ER -