%0 Journal Article %J IEEE Transactions on Pattern Analysis and Machine Intelligence %D 2010 %T Online Empirical Evaluation of Tracking Algorithms %A Wu,Hao %A Sankaranarayanan,A. C %A Chellapa, Rama %K Back %K Biomedical imaging %K Computer vision %K Filtering %K formal model validation techniques %K formal verification %K ground truth %K Kanade Lucas Tomasi feature tracker %K Karhunen-Loeve transforms %K lighting %K Markov processes %K mean shift tracker %K model validation. %K online empirical evaluation %K particle filtering (numerical methods) %K Particle filters %K Particle tracking %K performance evaluation %K receiver operating characteristic curves %K Robustness %K SNR %K Statistics %K Surveillance %K time reversed Markov chain %K tracking %K tracking algorithms %K visual tracking %X Evaluation of tracking algorithms in the absence of ground truth is a challenging problem. There exist a variety of approaches for this problem, ranging from formal model validation techniques to heuristics that look for mismatches between track properties and the observed data. However, few of these methods scale up to the task of visual tracking, where the models are usually nonlinear and complex and typically lie in a high-dimensional space. Further, scenarios that cause track failures and/or poor tracking performance are also quite diverse for the visual tracking problem. In this paper, we propose an online performance evaluation strategy for tracking systems based on particle filters using a time-reversed Markov chain. The key intuition of our proposed methodology relies on the time-reversible nature of physical motion exhibited by most objects, which in turn should be possessed by a good tracker. In the presence of tracking failures due to occlusion, low SNR, or modeling errors, this reversible nature of the tracker is violated. We use this property for detection of track failures. To evaluate the performance of the tracker at time instant t, we use the posterior of the tracking algorithm to initialize a time-reversed Markov chain. We compute the posterior density of track parameters at the starting time t = 0 by filtering back in time to the initial time instant. The distance between the posterior density of the time-reversed chain (at t = 0) and the prior density used to initialize the tracking algorithm forms the decision statistic for evaluation. It is observed that when the data are generated by the underlying models, the decision statistic takes a low value. We provide a thorough experimental analysis of the evaluation methodology. Specifically, we demonstrate the effectiveness of our approach for tackling common challenges such as occlusion, pose, and illumination changes and provide the Receiver Operating Characteristic (ROC) curves. Finally, we also s how the applicability of the core ideas of the paper to other tracking algorithms such as the Kanade-Lucas-Tomasi (KLT) feature tracker and the mean-shift tracker. %B IEEE Transactions on Pattern Analysis and Machine Intelligence %V 32 %P 1443 - 1458 %8 2010/08// %@ 0162-8828 %G eng %N 8 %R 10.1109/TPAMI.2009.135 %0 Conference Paper %B 2006 International Conference on Parallel Processing Workshops, 2006. ICPP 2006 Workshops %D 2006 %T Model-based OpenMP implementation of a 3D facial pose tracking system %A Saha,S. %A Chung-Ching Shen %A Chia-Jui Hsu %A Aggarwal,G. %A Veeraraghavan,A. %A Sussman, Alan %A Bhattacharyya, Shuvra S. %K 3D facial pose tracking system %K application modeling %K application program interfaces %K application scheduling %K coarse-grain dataflow graphs %K Concurrent computing %K data flow graphs %K Educational institutions %K face recognition %K IMAGE PROCESSING %K image processing applications %K Inference algorithms %K Message passing %K OpenMP platform %K parallel implementation %K PARALLEL PROCESSING %K parallel programming %K Particle tracking %K Processor scheduling %K SHAPE %K shared memory systems %K shared-memory systems %K Solid modeling %K tracking %X Most image processing applications are characterized by computation-intensive operations, and high memory and performance requirements. Parallelized implementation on shared-memory systems offer an attractive solution to this class of applications. However, we cannot thoroughly exploit the advantages of such architectures without proper modeling and analysis of the application. In this paper, we describe our implementation of a 3D facial pose tracking system using the OpenMP platform. Our implementation is based on a design methodology that uses coarse-grain dataflow graphs to model and schedule the application. We present our modeling approach, details of the implementation that we derived based on this modeling approach, and associated performance results. The parallelized implementation achieves significant speedup, and meets or exceeds the target frame rate under various configurations %B 2006 International Conference on Parallel Processing Workshops, 2006. ICPP 2006 Workshops %I IEEE %P 8 pp.-73 - 8 pp.-73 %8 2006/// %@ 0-7695-2637-3 %G eng %R 10.1109/ICPPW.2006.55 %0 Journal Article %J IEEE Transactions on Pattern Analysis and Machine Intelligence %D 2005 %T MCMC-based particle filtering for tracking a variable number of interacting targets %A Zia Khan %A Balch, T. %A Dellaert, F. %K algorithms %K Animals %K Artificial intelligence %K Computer simulation %K Computer vision %K Filtering %K filtering theory %K HUMANS %K Image Enhancement %K Image Interpretation, Computer-Assisted %K Index Terms- Particle filters %K Information Storage and Retrieval %K Insects %K interacting targets %K Markov chain Monte Carlo sampling step %K Markov chain Monte Carlo. %K Markov chains %K Markov processes %K Markov random field motion %K Markov random fields %K Models, Biological %K Models, Statistical %K Monte Carlo Method %K Monte Carlo methods %K MOTION %K Movement %K multitarget filter %K multitarget tracking %K particle filtering %K Particle filters %K Particle tracking %K Pattern Recognition, Automated %K Sampling methods %K Subtraction Technique %K target tracking %K Video Recording %X 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. %B IEEE Transactions on Pattern Analysis and Machine Intelligence %V 27 %P 1805 - 1819 %8 2005/11// %@ 0162-8828 %G eng %N 11 %0 Conference Paper %B IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2005. CVPR 2005 %D 2005 %T Multitarget tracking with split and merged measurements %A Zia Khan %A Balch, T. %A Dellaert, F. %K Application software %K Computer vision %K Detection algorithms %K Detectors %K filtering theory %K Markov chain Monte Carlo based auxiliary variable particle filter %K Markov processes %K merged measurements %K Monte Carlo methods %K multiple hypothesis tracker %K multitarget tracking %K parameter estimation %K Particle filters %K Particle tracking %K Rao-Blackwellized filter %K split measurements %K target tracking %K Trajectory %X 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. %B IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2005. CVPR 2005 %V 1 %P 605 - 610 vol. 1 %8 2005/06// %G eng %0 Conference Paper %B Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2004. CVPR 2004 %D 2004 %T A Rao-Blackwellized particle filter for EigenTracking %A Zia Khan %A Balch, T. %A Dellaert, F. %K analytically tractable integrals %K Computer vision %K EigenTracking %K Filters %K Gaussian processes %K modal analysis %K multi-modal distributions %K NOISE %K noisy targets %K optimisation %K optimization-based algorithms %K Particle filters %K Particle measurements %K Particle tracking %K Principal component analysis %K probabilistic principal component analysis %K Rao-Blackwellized particle filter %K Robustness %K SHAPE %K State estimation %K state vector %K subspace coefficients %K Subspace representations %K target tracking %K vectors %X Subspace representations have been a popular way to model appearance in computer vision. In Jepson and Black's influential paper on EigenTracking, they were successfully applied in tracking. For noisy targets, optimization-based algorithms (including EigenTracking) often fail catastrophically after losing track. Particle filters have recently emerged as a robust method for tracking in the presence of multi-modal distributions. To use subspace representations in a particle filter, the number of samples increases exponentially as the state vector includes the subspace coefficients. We introduce an efficient method for using subspace representations in a particle filter by applying Rao-Blackwellization to integrate out the subspace coefficients in the state vector. Fewer samples are needed since part of the posterior over the state vector is analytically calculated. We use probabilistic principal component analysis to obtain analytically tractable integrals. We show experimental results in a scenario in which we track a target in clutter. %B Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2004. CVPR 2004 %V 2 %P II - 980-II-986 Vol.2 %8 2004/06// %G eng %0 Journal Article %J IEEE Transactions on Image Processing %D 2004 %T Visual tracking and recognition using appearance-adaptive models in particle filters %A Zhou,Shaohua Kevin %A Chellapa, Rama %A Moghaddam, B. %K adaptive filters %K adaptive noise variance %K algorithms %K appearance-adaptive model %K Artificial intelligence %K Cluster Analysis %K Computer Graphics %K Computer simulation %K Feedback %K Filtering %K first-order linear predictor %K hidden feature removal %K HUMANS %K Image Enhancement %K Image Interpretation, Computer-Assisted %K image recognition %K Information Storage and Retrieval %K Kinematics %K Laboratories %K Male %K Models, Biological %K Models, Statistical %K MOTION %K Movement %K Noise robustness %K Numerical Analysis, Computer-Assisted %K occlusion analysis %K Particle filters %K Particle tracking %K Pattern Recognition, Automated %K Predictive models %K Reproducibility of results %K robust statistics %K Sensitivity and Specificity %K Signal Processing, Computer-Assisted %K State estimation %K statistical analysis %K Subtraction Technique %K tracking %K Training data %K visual recognition %K visual tracking %X We present an approach that incorporates appearance-adaptive models in a particle filter to realize robust visual tracking and recognition algorithms. Tracking needs modeling interframe motion and appearance changes, whereas recognition needs modeling appearance changes between frames and gallery images. In conventional tracking algorithms, the appearance model is either fixed or rapidly changing, and the motion model is simply a random walk with fixed noise variance. Also, the number of particles is typically fixed. All these factors make the visual tracker unstable. To stabilize the tracker, we propose the following modifications: an observation model arising from an adaptive appearance model, an adaptive velocity motion model with adaptive noise variance, and an adaptive number of particles. The adaptive-velocity model is derived using a first-order linear predictor based on the appearance difference between the incoming observation and the previous particle configuration. Occlusion analysis is implemented using robust statistics. Experimental results on tracking visual objects in long outdoor and indoor video sequences demonstrate the effectiveness and robustness of our tracking algorithm. We then perform simultaneous tracking and recognition by embedding them in a particle filter. For recognition purposes, we model the appearance changes between frames and gallery images by constructing the intra- and extrapersonal spaces. Accurate recognition is achieved when confronted by pose and view variations. %B IEEE Transactions on Image Processing %V 13 %P 1491 - 1506 %8 2004/11// %@ 1057-7149 %G eng %N 11 %R 10.1109/TIP.2004.836152 %0 Conference Paper %B 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2003. (IROS 2003). Proceedings %D 2003 %T Efficient particle filter-based tracking of multiple interacting targets using an MRF-based motion model %A Zia Khan %A Balch, T. %A Dellaert, F. %K collision avoidance %K computational cost %K Computational efficiency %K Educational institutions %K exponential complexity %K Filtering %K filtering theory %K Insects %K joint particle tracker %K Markov processes %K Markov random field motion %K Markov random fields %K multiple interacting targets %K particle filter-based tracking %K Particle filters %K Particle tracking %K Radar tracking %K social insect tracking application %K target tracking %K Trajectory %X We describe a multiple hypothesis particle filter for tracking targets that are influenced by the proximity and/or behavior of other targets. Our contribution is to show how a Markov random field motion prior, built on the fly at each time step, can model these interactions to enable more accurate tracking. We present results for a social insect tracking application, where we model the domain knowledge that two targets cannot occupy the same space, and targets actively avoid collisions. We show that using this model improves track quality and efficiency. Unfortunately, the joint particle tracker we propose suffers from exponential complexity in the number of tracked targets. An approximation to the joint filter, however, consisting of multiple nearly independent particle filters can provide similar track quality at substantially lower computational cost. %B 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2003. (IROS 2003). Proceedings %V 1 %P 254 - 259 vol.1 %8 2003/10// %G eng %0 Conference Paper %B IEEE Workshop on Detection and Recognition of Events in Video, 2001. Proceedings %D 2001 %T Multimodal 3-D tracking and event detection via the particle filter %A Zotkin,Dmitry N %A Duraiswami, Ramani %A Davis, Larry S. %K algorithms %K APPROACH %K audio data collection %K audio signal processing %K Bayesian inference %K Bayesian methods %K belief networks %K CAMERAS %K capture %K conversation %K echo %K Educational institutions %K Event detection %K event occurrence %K filtering theory %K flying echo locating bat behaviour %K Image motion analysis %K inference mechanisms %K Laboratories %K microphone arrays %K moving object tracking %K moving participants %K moving prey %K multimodal 3D tracking %K multiple cameras %K Object detection %K particle filter %K Particle filters %K Particle tracking %K Robustness %K search %K smart video conferencing setup %K target tracking %K Teleconferencing %K tracking filters %K turn-taking detection %K video data collection %K video signal processing %X Determining the occurrence of an event is fundamental to developing systems that can observe and react to them. Often, this determination is based on collecting video and/or audio data and determining the state or location of a tracked object. We use Bayesian inference and the particle filter for tracking moving objects, using both video data obtained from multiple cameras and audio data obtained using arrays of microphones. The algorithms developed are applied to determining events arising in two fields of application. In the first, the behavior of a flying echo locating bat as it approaches a moving prey is studied, and the events of search, approach and capture are detected. In a second application we describe detection of turn-taking in a conversation between possibly moving participants recorded using a smart video conferencing setup %B IEEE Workshop on Detection and Recognition of Events in Video, 2001. Proceedings %I IEEE %P 20 - 27 %8 2001/// %@ 0-7695-1293-3 %G eng %R 10.1109/EVENT.2001.938862