Advanced

Real time viterbi optimization of hidden Markov Models for multi target tracking

Ardö, Håkan LU ; Åström, Karl LU and Berthilsson, Rikard LU (2007) 2007 IEEE Workshop on Motion and Video Computing, WMVC 2007 In 2007 IEEE Workshop on Motion and Video Computing, WMVC 2007 p.4118798-4118798
Abstract
In this paper the problem of tracking multiple objects in image sequences is studied. A Hidden Markov Model describing the movements of multiple objects is presented. Previously similar models have been used, but in real time system the standard dynamic programming Viterbi algorithm is typically not used to find the global optimum state sequence, 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 delay. 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.... (More)
In this paper the problem of tracking multiple objects in image sequences is studied. A Hidden Markov Model describing the movements of multiple objects is presented. Previously similar models have been used, but in real time system the standard dynamic programming Viterbi algorithm is typically not used to find the global optimum state sequence, 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 delay. 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 maintaining an upper bound on all state sequences not evaluated. 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. © 2007 IEEE. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
State sequences, Optimum state sequences, Viterbi optimization, Finite delays
in
2007 IEEE Workshop on Motion and Video Computing, WMVC 2007
pages
4118798 - 4118798
publisher
IEEE--Institute of Electrical and Electronics Engineers Inc.
conference name
2007 IEEE Workshop on Motion and Video Computing, WMVC 2007
external identifiers
  • scopus:34547234046
ISBN
0-7695-2793-0
DOI
10.1109/WMVC.2007.33
language
English
LU publication?
yes
id
a16dac38-9fd0-4088-a308-136674fc5a43 (old id 643550)
date added to LUP
2007-12-04 14:07:27
date last changed
2017-03-12 04:25:10
@inproceedings{a16dac38-9fd0-4088-a308-136674fc5a43,
  abstract     = {In this paper the problem of tracking multiple objects in image sequences is studied. A Hidden Markov Model describing the movements of multiple objects is presented. Previously similar models have been used, but in real time system the standard dynamic programming Viterbi algorithm is typically not used to find the global optimum state sequence, 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 delay. 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 maintaining an upper bound on all state sequences not evaluated. 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. © 2007 IEEE.},
  author       = {Ardö, Håkan and Åström, Karl and Berthilsson, Rikard},
  booktitle    = {2007 IEEE Workshop on Motion and Video Computing, WMVC 2007},
  isbn         = {0-7695-2793-0},
  keyword      = {State sequences,Optimum state sequences,Viterbi optimization,Finite delays},
  language     = {eng},
  pages        = {4118798--4118798},
  publisher    = {IEEE--Institute of Electrical and Electronics Engineers Inc.},
  title        = {Real time viterbi optimization of hidden Markov Models for multi target tracking},
  url          = {http://dx.doi.org/10.1109/WMVC.2007.33},
  year         = {2007},
}