This paper addresses the problem of estimating the optimal Hidden Markov Model (HMM) topology. The optimal topology is defined as the one that gives the smallest error-rate with the minimal number of parameters. The paper introduces a Bayesian model selection criterion that is suitable for Continuous Hidden Markov Models topology optimization. The criterion is derived from the Laplacian approximation of the posterior of a model structure, and shares the algorithmic simplicity of conventional Bayesian selection criteria, such as Schwarz's Bayesian Information Criterion (BIC). Unlike, BIC, which uses a multivariate Normal distribution assumption for the prior of all parameters of the model, the proposed HMM-oriented Bayesian Information Criterion (HBIC), models each parameter by a different distribution, one more appropriate for that parameter The results on an handwriting recognition task shows that the HBIC realizes a much smaller and efficient system than a system generated through the BIC.

This paper addresses the problem of hidden Markov model (HMM) topology estimation in the context of on-line handwriting recognition. HMM have been widely used in applications related to speech and handwriting recognition with great success. One major drawback with these approaches, however, is that the techniques that they use for estimating the topology of the models (number of states, connectivity between the states and the number of Gaussians), are usually heuristically derived, without optimal certainty. This paper addresses this problem, by comparing a couple of commonly used heuristically derived methods to an approach that uses the Bayesian information criterion (BIC) for computing the optimal topology. Experimental results on discretely written letters show that using BIC gives comparable results to heuristic approaches with a model that has nearly 10% fewer parameters.

We explore a novel approach for handwriting recognition tasks whose intrinsic vocabularies are too large to be applied directly as constraints during recognition. Our approach makes use of vocabulary constraints, and addresses the issue that some parts of words may be written more recognizably than others. An initial pass is made with an HMM recognizer, without vocabulary constraints, generating a lattice of character-hypothesis arcs representing likely segmentations of the handwriting signal. Arc confidence scores are computed using a posteriori probabilities. The most confidently recognized characters are used to filter the overall vocabulary, generating a word subset manageable for constraining a second recognition pass. With a vocabulary of 273000 words, we can limit to 50000 words in the second pass and eliminate 39.3% of the word errors made by a one-pass recognizer without vocabulary constraints, and 18.3% of errors made using a fixed 30000-word set.

We present a hierarchical approach for extracting homogeneous regions in on-line documents. The problem of identifying and processing ruled and unruled tables, text and drawings is addressed. The on-line document is first segmented into regions with only text strokes and regions with both text and non-text strokes. The text region is further classified as unruled table or plain text. Stroke clustering is used to segment the non-text regions. Each nontext segment is then classified as drawing, ruled table or underlined keyword using stroke properties. The individual regions are processed and the results are assembled to identify the structure of the on-line document.

Pen computing as a fieId broadly includes computers and applications in which a pen is the main input device. This field continues to draw a lot of attention from researchers because there are a number of applications where the pen is the most convenient form of input. These include: 1. preparing a first draft of a document and concentrating on content creation; 2. a socially acceptable form of capturing information in meetings, that is quieter than typing and creates minimal visual barrier; 3. applications that need privacy; 4. entering letters in ideographic languages like Chinese and Japanese and non-letter entries like graphics, music and gestures; and 5. interaction with multi-modal systems. The advent of electronic tablets in the late 1950s precipitated considerable activity in the area of pen computing. This interest ebbed in the 1970's, and was renewed in the 1980's, primarily due to advances in pen hardware technology and improvement in user-interfaces and handwriting recognition algorithms. There are still however, a number of challenges that need to be addressed before pen computing can address the needs listed above to a acceptable level of user satisfaction. In the paper, an overview of three aspects of pen computing are presented: pen input hardware, handwriting recognition and pen computer applications.

In a hidden Markov model system, the initialization of the model parameters is critical to the performance of the model after retraining. This paper proposes a number of new approaches to the problem of initialization, and demonstrates that a method of smooth alignment results in the best performance.

This paper describes a series of experiments that have been conducted to investigate the effect of duration modeling in a hidden Markov model (HMM) based online handwriting recognition system. The issues discussed include parametric vs. non-parametric distributions to model duration, different methods for training transition probabilities and the effect of weighting on duration terms.

In this paper, we present a framework for adapting a writer independent system to a user from samples of the user's writing. The writer independent system is modeled using hidden Markov models. Training for a writer involves recomputing the topology and parameters of the hidden Markov models using the writer's data. The framework uses the writer independent system to get an initial alignment of the writer's data. The system described reduces the error rate by an average of 65%. For the results presented, no language model was used.

We describe experiments on a writer dependent large vocabulary (20000) handwriting recognition system. The goal was to investigate the effects of different degrees of tying (and hence, of the number) of parameters on the error rate. The system recognizes cursive, printed or any combination thereof of script in real time on small PC platforms. Baseline results for a writer independent system are also included. Since we are only interested in the shape models no language models were used.

We treat the use of more complex higher degree polynomial curves and surfaces of degree higher than 2, which have many desirable properties for object recognition and position estimation, and attack the instability problem arising in their use with partial and noisy data. The scenario discussed in this paper is one where we have a set of objects that are modeled as implicit polynomial functions, or a set of representations of classes of objects with each object in a class modeled as an implicit polynomial function, stored in the database. Then, given partial data from one of the objects, we want to recognize the object (or the object class) or collect more data in order to get better parameter estimates for more reliable recognition. Two problems arising in this scenario are discussed: 1) the problem of recognizing these polynomials by comparing them in terms of their coefficients; and 2) the problem of where to collect data so as to improve the parameter estimates as quickly as possible. We use an asymptotic Bayesian approximation for solving the two problems. The intrinsic dimensionality of polynomials and the use of the Mahalanobis distance are discussed.

We address the problem of automatic recognition of unconstrained handwritten text. Statistical methods, such as hidden Markov models (HMMs) have been used successfully for speech recognition and they have been applied to the problem of handwriting recognition as well. We discuss a general recognition system for large vocabulary, writer independent, unconstrained handwritten text. "Unconstrained" implies that the user may write in any style e.g. printed, cursive or in any combination of styles. This is more representative of typical handwritten text where one seldom encounters purely printed or purely cursive forms. Furthermore, a key characteristic of the system is that it performs recognition in real-time on 486 class PC platforms without the large amounts of memory required for traditional HMM based systems. We focus mainly on the writer independent task. Some initial writer dependent results are also reported. An error rate of 18.9% is achieved for a writer-independent 21,000 word vocabulary task in the absence of any language models.

We present an approach to recognition that is based on partitioning and invariant recognition in a Bayesian framework. The intended application domain is that of complex articulated objects in arbitrary position and under considerable occlusion. First, since the performance of traditional model-based recognition strategies degrades with increasing object data-base size, with partial occlusion, and with articulation, we employ a partitioning that does not rely on apriori primitives or models. Rather, this scheme decomposes segmented shapes into parts, where the form of each part is not known apriori, but is derived based on generic geometric assumptions about objects and their projections. Specifically, two types of parts, neck-based and limb-based, give rise to a shape decomposition that remains invariant under occlusion in the visible portion of the object, unaltered under articulation of parts, is stable under slight changes in viewing geometry and finally is robust with changes in resolution and scale. Second, the parts derived from the first stage are described by implicit polynomial curves. These polynomials represent the parts well and are computationally simple to fit to the data. However, the great advantage in using implicit polynomials is the algebraic invariance associated with them. Each part is represented by a vector of invariants that remains essentially independent of viewing geometry, and as such is suitable for matching purposes. The matching process is a Bayesian engine based on asymptotic distributions. In the conclusion section, we briefly indicate how this technology fits into a complete object recognition system.

In an on-line handwriting recognition system, the motion of the tip of the stylus (pen) is sampled at equal time intervals using a digitizer tablet and the sampled points are passed to a computer which performs the handwriting recognition. In most cases, the basic recognition algorithm performs best for a nominal size of writing as well as a standard orientation (normally horizontal) and a nominal slant (normally fully upright). We discuss and provide solutions to these normalization problems in the context of on-line handwriting recognition. Most of the results presented are also valid for optical character recognition (OCR). Error rate reductions of 54.3% and 35.8% were obtained for the writer-dependent and writer-independent samples through using the proposed normalization scheme.>

This paper introduces and focuses on two problems. First is the representation power of closed implicit polynomials of modest degree for curves in 2-D images and surfaces in 3-D range data. Super quadrics are a small subset of object boundaries that are well fitted by these polynomials. The second problem is the stable computationally efficient fitting of noisy data by closed implicit polynomial curves and surfaces. The attractive features of these polynomials for Vision is discussed.>

The authors present a robust low-computational-cost system for recognizing freeform objects in 3-D range data or in 2-D curve data in the image plane. Objects are represented by implicit polynomials, i.e., 3-D algebraic surfaces or 2-D algebraic curves of degrees greater than two, and are recognized by computing and matching vectors of their algebraic invariants, which are functions of their coefficients that are invariant to translations, rotations, and general linear transformations. Implicit polynomials of fourth degree can represent complicated asymmetric free-form shapes. A design of Bayesian recognizers for these models and their invariants that results in low-computational-cost recognizers robust to noise, partial occlusion, and other perturbations of the data sets is considered. This work extends the work of D. Keren et al. (1992) by developing and using new invariants for 3-D surface polynomials and applying the Bayesian recognizer to operating on invariants.>

Two problems pertinent to using implicit higher degree polynomials in real-world robust systems are dealt with: (1) characterization and fitting algorithms for the subset of these algebraic curves and surfaces that is bounded and exists largely in the vicinity of the data; (2) a Mahalanobis distance for comparing the coefficients of two polynomials, to determine whether the curves or surfaces that they represent are close over a specified region. These tools make practical use of geometric invariants for determining whether one implicit polynomial curve or surface is a rotation, translation, or an affine transformation of another. The approach is ideally suited to smooth curves and smooth curved surfaces that do not have detectable features.>

An approach and algorithm for 3D primitive model recognition, parameter estimation, and segmentation from a sequence of images taken by one or more calibrated cameras are presented. Though the approach and algorithm are applicable to more general models, the experiments described are for primitive objects that are 3D planes. Given two or more images taken by one or more calibrated cameras, the algorithm simultaneously segments the images and 3D space into regions, each region associated with a single planar patch, and estimates the parameters of the 3D plane associated with each segmented region. The algorithm is suitable for parallel processing and should function at close to the best possible accuracy. Markov random fields are used to provide very coarse prior knowledge of the regions occupied by the planar patches, resulting in markedly enhanced accuracy.>