Approximate Viterbi decoding for 2D-hidden Markov models

Mérialdo, Bernard; Marchand-Maillet, Stéphane; Huet, Benoit
ICASSP 2000, 25th IEEE International conference on acoustic, speech and signal, June 5-9, 2000, Istanbul, Turkey

While one-dimensional Hidden Markov Models have been very successfully applied to numerous problems, their extension to two dimensions has been shown to be exponentially complex, and this has very much restricted their usage for problems such as image analysis. In this paper we propose a novel algorithm which is able to approximate the search for the best state path (Viterbi decoding) in a 2D HMM. This algorithm makes certain assumptions which lead to tractable imputations, at a price of loss in full optimality. We detail our algorithm, its implementation, and present some experiments on handwritten character recognition.
Because the Viterbi algorithm serves as a basis for many applications, and 1D HMMs have shown great exibility in their usage, our approach has the potential to make 2D HMMs as useful for 2D data as 1D HMMs are for 1D data such as speech.

Data Science
Eurecom Ref:
© 2000 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
See also: