International Journal of Pattern Recognition and Artificial Intelligence

We provide a tutorial on learning and inference in hidden Markov models in the context of the recent literature on Bayesian networks. This perspective makes it possible to consider novel generalizations of hidden Markov models with multiple hidden state variables, multiscale representations, and mixed discrete and continuous variables. Although exact inference in these generalizations is usually intractable, one can use approximate inference algorithms such as Markov chain sampling and variational methods. We describe how such methods are applied to these generalized hidden Markov models. We conclude this review with a discussion of Bayesian methods for model selection in generalized HMMs.

This paper presents a script-independent methodology for optical character recognition (OCR) based on the use of hidden Markov models (HMM). The feature extraction, training and recognition components of the system are all designed to be script independent. The training and recognition components were taken without modification from a continuous speech recognition system; the only component that is specific to OCR is the feature extraction component. To port the system to a new language, all that is needed is text image training data from the new language, along with ground truth which gives the identity of the sequences of characters along each line of each text image, without specifying the location of the characters on the image. The parameters of the character HMMs are estimated automatically from the training data, without the need for laborious handwritten rules. The system does not require presegmentation of the data, neither at the word level nor at the character level. Thus, the system is able to handle languages with connected characters in a straightforward manner. The script independence of the system is demonstrated in three languages with different types of script: Arabic, English, and Chinese. The robustness of the system is further demonstrated by testing the system on fax data. An unsupervised adaptation method is then described to improve performance under degraded conditions.

In this paper, a system for the reading of totally unconstrained handwritten text is presented. The kernel of the system is a hidden Markov model (HMM) for handwriting recognition. This HMM is enhanced by a statistical language model. Thus linguistic knowledge beyond the lexicon level is incorporated in the recognition process. Another novel feature of the system is that the HMM is applied in such a way that the difficult problem of segmenting a line of text into individual words is avoided. A number of experiments with various language models and large vocabularies have been conducted. The language models used in the system were also analytically compared based on their perplexity.

In this paper we consider a hidden Markov mesh random field (HMMRF) for character recognition. The model consists of a "hidden" Markov mesh random field (MMRF) and an overlying probabilistic observation function of the MMRF. Just like the 1-D HMM, the hidden layer is characterized by the initial and the transition probability distributions, and the observation layer is defined by distribution functions for vector-quantized (VQ) observations.

The HMMRF-based method consists of two phases: decoding and training. The decoding and the training algorithms are developed using dynamic programming and maximum likelihood estimation methods. To accelerate the computation in both phases, we employed a look-ahead scheme based on maximum marginal it a posteriori probability criterion for third-order HMMRF. Tested on a larget-set handwritten Korean Hangul character database, the model showed a promising result: up to 87.2% recognition rate with 8 state HMMRF and 128 VQ levels.

Although HMM is widely used for online handwriting recognition, there is no simple and well-established method of designing the HMM topology. We propose a data-driven systematic method to design HMM topology. Data samples in a single pattern class are structurally simplified into a sequence of straight-line segments, and then these simplified representations of the samples are clustered. An HMM is constructed for each of these clusters, by assigning a state to each straight-line segments. Then the resulting multiple models of the class are combined to form an architecture of a multiple parallel-path HMM, which behaves as a single HMM. To avoid excessive growing of the number of the states, parameter tying is applied such that structural similarity among patterns is reflected. Experiments on online Hangul recognition showed about 19% of error reductions, compared to the intuitive design method.

Conventional application of hidden Markov models to the task of recognizing human gesture may suffer from multiple sources of systematic variation in the sensor outputs. We present two frameworks based on hidden Markov models which are designed to model and recognize gestures that vary in systematic ways. In the first, the systematic variation is assumed to be communicative in nature, and the input gesture is assumed to belong to gesture family. The variation across the family is modeled explicitly by the parametric hidden Markov model (PHMM). In the second framework, variation in the signal is overcome by relying on online learning rather than conventional offline, batch learning.

In this paper, we describe a systematic approach to the lipreading of whole sentences. A vocabulary of elementary words is considered. Based on the vocabulary, we define a grammar that generates a set of legal sentences. Our lipreading approach is based on a combination of the grammar with hidden Markov models (HMMs). Two different experiments were conducted. In the first experiment a set of e-mail commands is considered, while the set of sentences in the second experiment is given by all English integer numbers up to one million. Both experiments showed promising results, regarding the difficulty of the considered task.

In this paper, we consider the problem of tracking an object and predicting the object's future trajectory in a wide-area environment, with complex spatial layout and the use of multiple sensors/cameras. To solve this problem, there is a need for representing the dynamic and noisy data in the tracking tasks, and dealing with them at different levels of detail. We employ the Abstract Hidden Markov Models (AHMM), an extension of the well-known Hidden Markov Model (HMM) and a special type of Dynamic Probabilistic Network (DPN), as our underlying representation framework. The AHMM allows us to explicitly encode the hierarchy of connected spatial locations, making it scalable to the size of the environment being modeled. We describe an application for tracking human movement in an office-like spatial layout where the AHMM is used to track and predict the evolution of object trajectories at different levels of detail.

This paper is concerned with an application of Hidden Markov Models (HMMs) to the generation of shape boundaries from image features. In the proposed model, shape classes are defined by sequences of "shape states" each of which has a probability distribution of expected image feature types (feature "symbols").The tracking procedure uses a generalization of the well-known Viterbi method by replacing its search by a type of "beam-search" so allowing the procedure, at any time, to consider less likely features (symbols) as well the search for an instantiable optimal state sequences. We have evaluated the model's performance on a variety of image and shape types and have also developed a new performance measure defined by an expected Hamming distance between predicted and observed symbol sequences. Results point to the use of this type of model for the depiction of shape boundaries when it is necessary to have accurate boundary annotations as, for example, occurs in Cartography.

An integrated approach to shape and color-based image retrieval, where the cues color and shape are both utilized in a local rather than a global way, is presented in this paper. An experimental retrieval system has been developed, which enables the user to search a color image database intuitively by presenting simple sketches. In order to be able to perform an elastic matching, which is especially needed in sketch-based image retrieval, objects in the images are represented by Hidden Markov Models. The use of streams (sets of features that are assumed to be statistically independent) within the HMM framework allows the integration of shape and color derived features into a single model, thereby allowing to control the influence of the different streams via stream weights. The approach has been evaluated on a color image database containing 120 different isolated objects with arbitrary orientation and showed good retrieval results with several users. Furthermore, the use of HMMs allows efficient pruning and thus a fast retrieval even with large databases.