Real Time Viterbi Optimization of Hidden Markov Models for Multi Target Tracking
- 1 February 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1, 2
- https://doi.org/10.1109/wmvc.2007.33
Abstract
In this paper the problem of tracking multiple objects in im- age sequences is studied. A Hidden Markov Model describ- ing the movements of multiple objects is presented. Previ- ously similar models have been used, but in real time sys- tem the standard dynamic programming Viterbi algorithm is typically not used to find the global optimum state se- quence, as it requires that all past and future observations are available. In this paper we present an extension to the Viterbi algorithm that allows it to operate on infinite time sequences and produce the optimum with only a finite de- lay. This makes it possible to use the Viterbi algorithm in real time applications. Also, to handle the large state spaces of these models another extension is proposed. The global optimum is found by iteratively running an approximative algorithm with higher and higher precision. The algorithm can determine when the global optimum is found by main- taining an upper bound on all state sequences not evalu- ated. For real time performance some approximations are needed and two such approximations are suggested. The theory has been tested on three real data experiments, all with promising results.Keywords
This publication has 13 references indexed in Scilit:
- Video stabilization as a variational problem and numerical solution with the viterbi methodPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- An HMM/MRF-Based Stochastic Framework for Robust Vehicle TrackingIEEE Transactions on Intelligent Transportation Systems, 2004
- Sequential importance sampling filtering for target tracking in image sequencesIEEE Signal Processing Letters, 2003
- BraMBLe: a Bayesian multiple-blob trackerPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Multiframe detector/tracker: optimal performanceIEEE Transactions on Aerospace and Electronic Systems, 2001
- Novel approach to nonlinear/non-Gaussian Bayesian state estimationIEE Proceedings F Radar and Signal Processing, 1993
- A tutorial on hidden Markov models and selected applications in speech recognitionProceedings of the IEEE, 1989
- An algorithm for tracking multiple targetsIEEE Transactions on Automatic Control, 1979
- An Optimal Data Association Problem in Surveillance TheoryIEEE Transactions on Military Electronics, 1964
- A New Approach to Linear Filtering and Prediction ProblemsJournal of Basic Engineering, 1960