Creating word-level language models for large-vocabulary handwriting recognition

We discuss development of a word-unigram language model for online handwriting recognition. First, we tokenize a text corpus into words, contrasting with tokenization methods designed for other purposes. Second, we select for our model a subset of the words found, discussing deviations from an N-most-frequent-words approach. From a 600-million-word corpus, we generated a 53,000-word model which eliminates 45% of word-recognition errors made by a character-level-model baseline system. We anticipate that our methods will be applicable to offline recognition as well, and to some extent to other recognizers, such as speech recognizers and video retrieval systems. Received: November 1, 2001 / Revised version: July 22, 2002     

Diacritical processing for unconstrained online handwriting recognition using a forward search

Out-of-order diacriticals introduce significant complexity to the design of an online handwriting recognizer, because they require some reordering of the time domain information. It is common in cursive writing to write the body of an `i' or `t' during the writing of the word, and then to return and dot or cross the letter once the word is complete. The difficulty arises because we have to look ahead, when scoring one of these letters, to find the mark occurring later in the writing stream that completes the letter. We should also remember that we have used this mark, so that we don't use it again for a different letter, and we should also penalize a word if there are some marks that look like diacriticals that are not used. One approach to this problem is to scan the writing some distance into the future to identify candidate diacriticals, remove them in a preprocessing step, and associate them with the matching letters earlier in the word. If done as a preliminary operation, this approach is error-prone: marks that are not diacriticals may be incorrectly identified and removed, and true diacriticals may be skipped. This paper describes a novel extension to a forward search algorithm that provides a natural mechanism for considering alternative treatments of potential diacriticals, to see whether it is better to treat a given mark as a diacritical or not, and directly compare the two outcomes by score. Received October 30, 1998 / Revised January 25, 1999     

Online handwriting recognition: the NPen++ recognizer

This paper presents the online handwriting recognition system NPen++ developed at the University of Karlsruhe and Carnegie Mellon University. The NPen++ recognition engine is based on a multi-state time delay neural network and yields recognition rates from 96% for a 5,000 word dictionary to 93.4% on a 20,000 word dictionary and 91.2% for a 50,000 word dictionary. The proposed tree search and pruning technique reduces the search space considerably without losing too much recognition performance compared to an exhaustive search. This enables the NPen++ recognizer to be run in real-time with large dictionaries. Initial recognition rates for whole sentences are promising and show that the MS-TDNN architecture is suited to recognizing handwritten data ranging from single characters to whole sentences. Received September 3, 2000 / Revised October 9, 2000     

An unconstrained handwriting recognition system

In this paper, an integrated offline recognition system for unconstrained handwriting is presented. The proposed system consists of seven main modules: skew angle estimation and correction, printed-handwritten text discrimination, line segmentation, slant removing, word segmentation, and character segmentation and recognition, stemming from the implementation of already existing algorithms as well as novel algorithms. This system has been tested on the NIST, IAM-DB, and GRUHD databases and has achieved accuracy that varies from 65.6% to 100% depending on the database and the experiment.     

RAV (reparameterized angle variations) algorithm for online handwriting recognition

A new algorithm RAV (reparameterized angle variations) is proposed which makes explicit use of trajectory information where the time evolution of the pen coordinates plays a crucial role. The algorithm is robust against stroke connections/abbreviations as well as shape distortions, while maintaining reasonable robustness against stroke-order variations. Preliminary experiments are reported on tests against the Kuchibue_d-96-02 database from the Tokyo University of Agriculture and Technology. Received July 24, 2000 / Revised October 6, 2000     

An architecture for handwritten text recognition systems

This paper presents an end-to-end system for reading handwritten page images. Five functional modules included in the system are introduced in this paper: (i) pre-processing, which concerns introducing an image representation for easy manipulation of large page images and image handling procedures using the image representation; (ii) line separation, concerning text line detection and extracting images of lines of text from a page image; (iii) word segmentation, which concerns locating word gaps and isolating words from a line of text image obtained efficiently and in an intelligent manner; (iv) word recognition, concerning handwritten word recognition algorithms; and (v) linguistic post-pro- cessing, which concerns the use of linguistic constraints to intelligently parse and recognize text. Key ideas employed in each functional module, which have been developed for dealing with the diversity of handwriting in its various aspects with a goal of system reliability and robustness, are described in this paper. Preliminary experiments show promising results in terms of speed and accuracy. Received October 30, 1998 / Revised January 15, 1999     

Experiments with adaptation strategies for a prototype-based recognition system for isolated handwritten characters

This paper describes an adaptive recognition system for isolated handwritten characters and the experiments carried out with it. The characters used in our experiments are alphanumeric characters, including both the upper- and lower-case versions of the Latin alphabets and three Scandinavian diacriticals. The writers are allowed to use their own natural style of writing. The recognition system is based on the k-nearest neighbor rule. The six character similarity measures applied by the system are all based on dynamic time warping. The aim of the first experiments is to choose the best combination of the simple preprocessing and normalization operations and the dissimilarity measure for a multi-writer system. However, the main focus of the work is on online adaptation. The purpose of the adaptations is to turn a writer-independent system into writer-dependent and increase recognition performance. The adaptation is carried out by modifying the prototype set of the classifier according to its recognition performance and the user's writing style. The ways of adaptation include: (1) adding new prototypes; (2) inactivating confusing prototypes; and (3) reshaping existing prototypes. The reshaping algorithm is based on the Learning Vector Quantization. Four different adaptation strategies, according to which the modifications of the prototype set are performed, have been studied both offline and online. Adaptation is carried out in a self-supervised fashion during normal use and thus remains unnoticed by the user. Received June 30, 1999 / Revised September 29, 2000     

Segmentation and recognition of Chinese bank check amounts

This paper describes a system for the recognition of legal amounts on bank checks written in the Chinese language. It consists of subsystems that perform preprocessing, segmentation, and recognition of the legal amount. In each step of the segmentation and recognition phases, a list of possible choices are obtained. An approach is adopted whereby a large number of choices can be processed effectively and efficiently in order to achieve the best recognition result. The contribution of this paper is the proposal of a grammar checker for Chinese bank check amounts. It is found to be very effective in reducing the substitution error rate. The recognition rate of the system is 74.0%, the error rate is 10.4%, and the reliability is 87.7%. Received June 9, 2000 / Revised January 10, 2001     

Algebraic query optimisation for database programming languages

A major challenge still facing the designers and implementors of database programming languages (DBPLs) is that of query optimisation. We investigate algebraic query optimisation techniques for DBPLs in the context of a purely declarative functional language that supports sets as first-class objects. Since the language is computationally complete issues such as non-termination of expressions and construction of infinite data structures can be investigated, whilst its declarative nature allows the issue of side effects to be avoided and a richer set of equivalences to be developed. The language has a well-defined semantics which permits us to reason formally about the properties of expressions, such as their equivalence with other expressions and their termination. The support of a set bulk data type enables much prior work on the optimisation of relational languages to be utilised. In the paper we first give the syntax of our archetypal DBPL and briefly discuss its semantics. We then define a small but powerful algebra of operators over the set data type, provide some key equivalences for expressions in these operators, and list transformation principles for optimising expressions. Along the way, we identify some caveats to well-known equivalences for non-deductive database languages. We next extend our language with two higher level constructs commonly found in functional DBPLs: set comprehensions and functions with known inverses. Some key equivalences for these constructs are provided, as are transformation principles for expressions in them. Finally, we investigate extending our equivalences for the set operators to the analogous operators over bags. Although developed and formally proved in the context of a functional language, our findings are directly applicable to other DBPLs of similar expressiveness. Edited by Matthias Jarke, Jorge Bocca, Carlo Zaniolo. Received September 15, 1994 / Accepted September 1, 1995     

OPT++ : an object-oriented implementation for extensible database query optimization

In this paper we describe the design and implementation of OPT++, a tool for extensible database query optimization that uses an object-oriented design to simplify the task of implementing, extending, and modifying an optimizer. Building an optimizer using OPT++ makes it easy to extend the query algebra (to add new query algebra operators and physical implementation algorithms to the system), easy to change the search space, and also to change the search strategy. Furthermore, OPT++ comes equipped with a number of search strategies that are available for use by an optimizer-implementor. OPT++ considerably simplifies both, the task of implementing an optimizer for a new database system, and the task of evaluating alternative optimization techniques and strategies to decide what techniques are best suited for that database system. We present the results of a series of performance studies. These results validate our design and show that, in spite of its flexibility, OPT++ can be used to build efficient optimizers. Received October 1996 / Accepted January 1998     

Confidence modeling for handwriting recognition: algorithms and applications

Confidence scoring can assist in determining how to use imperfect handwriting-recognition output. We explore a confidence-scoring framework for post-processing recognition for two purposes: deciding when to reject the recognizer's output, and detecting when to change recognition parameters e.g., to relax a word-set constraint. Varied confidence scores, including likelihood ratios and posterior probabilities, are applied to an Hidden-Markov-Model (HMM) based on-line recognizer. Receiver-operating characteristic curves reveal that we successfully reject 90% of word recognition errors while rejecting only 33% of correctly-recognized words. For isolated digit recognition, we achieve 90% correct rejection while limiting false rejection to 13%.     

Stop word location and identification for adaptive text recognition

Abstract. We propose a new adaptive strategy for text recognition that attempts to derive knowledge about the dominant font on a given page. The strategy uses a linguistic observation that over half of all words in a typical English passage are contained in a small set of less than 150 stop words. A small dictionary of such words is compiled from the Brown corpus. An arbitrary text page first goes through layout analysis that produces word segmentation. A fast procedure is then applied to locate the most likely candidates for those words, using only widths of the word images. The identity of each word is determined using a word shape classifier. Using the word images together with their identities, character prototypes can be extracted using a previously proposed method. We describe experiments using simulated and real images. In an experiment using 400 real page images, we show that on average, eight distinct characters can be learned from each page, and the method is successful on 90% of all the pages. These can serve as useful seeds to bootstrap font learning. Received October 8, 1999 / Revised March 29, 2000     

Mathematical expression recognition: a survey

Abstract. Automatic recognition of mathematical expressions is one of the key vehicles in the drive towards transcribing documents in scientific and engineering disciplines into electronic form. This problem typically consists of two major stages, namely, symbol recognition and structural analysis. In this survey paper, we will review most of the existing work with respect to each of the two major stages of the recognition process. In particular, we try to put emphasis on the similarities and differences between systems. Moreover, some important issues in mathematical expression recognition will be addressed in depth. All these together serve to provide a clear overall picture of how this research area has been developed to date. Received February 22, 2000 / Revised June 12, 2000     

Handwriting recognition or reading? What is the situation at the dawn of the 3rd millenium?

During the last forty years, Human Handwriting Processing (HHP) has most often been investigated under the frameworks of character (OCR) and pattern recognition. In recent years considerable progress has been made, and to date HHP can be viewed much more as an automatic Handwriting Reading (HR) task for the machine. In this paper we propose the use of handwriting invariants, a physical model for a first segmentation, a logical model for segmentation and recognition, a fundamental equation of handwriting, and to integrate several sources of perception and of knowledge in order to design Handwriting Reading Systems (HRS), which would be more universal systems than is currently the case. At the dawn of the 3rd millennium, we guess that HHP will be considered more as a perceptual and interpretation task requiring knowledge gained from studies on human language. This paper gives some guidelines and presents examples to design systems able to perceive and interpret, i.e., read, handwriting automatically. Received October 30, 1998 / Revised January 30, 1999     

Maximum mutual information training for an online neural predictive handwritten word recognition system

In this paper, we present a hybrid online handwriting recognition system based on hidden Markov models (HMMs). It is devoted to word recognition using large vocabularies. An adaptive segmentation of words into letters is integrated with recognition, and is at the heart of the training phase. A word-model is a left-right HMM in which each state is a predictive multilayer perceptron that performs local regression on the drawing (i.e., the written word) relying on a context of observations. A discriminative training paradigm related to maximum mutual information is used, and its potential is shown on a database of 9,781 words. Received June 19, 2000 / Revised October 16, 2000     

Performance evaluation of pattern classifiers for handwritten character recognition

This paper describes a performance evaluation study in which some efficient classifiers are tested in handwritten digit recognition. The evaluated classifiers include a statistical classifier (modified quadratic discriminant function, MQDF), three neural classifiers, and an LVQ (learning vector quantization) classifier. They are efficient in that high accuracies can be achieved at moderate memory space and computation cost. The performance is measured in terms of classification accuracy, sensitivity to training sample size, ambiguity rejection, and outlier resistance. The outlier resistance of neural classifiers is enhanced by training with synthesized outlier data. The classifiers are tested on a large data set extracted from NIST SD19. As results, the test accuracies of the evaluated classifiers are comparable to or higher than those of the nearest neighbor (1-NN) rule and regularized discriminant analysis (RDA). It is shown that neural classifiers are more susceptible to small sample size than MQDF, although they yield higher accuracies on large sample size. As a neural classifier, the polynomial classifier (PC) gives the highest accuracy and performs best in ambiguity rejection. On the other hand, MQDF is superior in outlier rejection even though it is not trained with outlier data. The results indicate that pattern classifiers have complementary advantages and they should be appropriately combined to achieve higher performance. Received: July 18, 2001 / Accepted: September 28, 2001     

Adaptive target recognition

Target recognition is a multilevel process requiring a sequence of algorithms at low, intermediate and high levels. Generally, such systems are open loop with no feedback between levels and assuring their performance at the given probability of correct identification (PCI) and probability of false alarm (Pf) is a key challenge in computer vision and pattern recognition research. In this paper, a robust closed-loop system for recognition of SAR images based on reinforcement learning is presented. The parameters in model-based SAR target recognition are learned. The method meets performance specifications by using PCI and Pf as feedback for the learning system. It has been experimentally validated by learning the parameters of the recognition system for SAR imagery, successfully recognizing articulated targets, targets of different configuration and targets at different depression angles.     

PicoDBMS: Scaling down database techniques for the smartcard

Smartcards are the most secure portable computing device today. They have been used successfully in applications involving money, and proprietary and personal data (such as banking, healthcare, insurance, etc.). As smartcards get more powerful (with 32-bit CPU and more than 1 MB of stable memory in the next versions) and become multi-application, the need for database management arises. However, smartcards have severe hardware limitations (very slow write, very little RAM, constrained stable memory, no autonomy, etc.) which make traditional database technology irrelevant. The major problem is scaling down database techniques so they perform well under these limitations. In this paper, we give an in-depth analysis of this problem and propose a PicoDBMS solution based on highly compact data structures, query execution without RAM, and specific techniques for atomicity and durability. We show the effectiveness of our techniques through performance evaluation. Received: 15 October 2000 / Accepted: 15 April 2001 Published online: 23 July 2001     

A model-driven approach for real-time road recognition

This article describes a method designed to detect and track road edges starting from images provided by an on-board monocular monochromic camera. Its implementation on specific hardware is also presented in the framework of the VELAC project. The method is based on four modules: (1) detection of the road edges in the image by a model-driven algorithm, which uses a statistical model of the lane sides which manages the occlusions or imperfections of the road marking – this model is initialized by an off-line training step; (2) localization of the vehicle in the lane in which it is travelling; (3) tracking to define a new search space of road edges for the next image; and (4) management of the lane numbers to determine the lane in which the vehicle is travelling. The algorithm is implemented in order to validate the method in a real-time context. Results obtained on marked and unmarked road images show the robustness and precision of the method. Received: 18 November 2000 / Accepted: 7 May 2001