Put It In Cursive Writing

Neural net research may lead to connected recognition faster than we think

No matter how much distance pen-based vendors try to put between stylus systems and handwriting recognition, the holy grail of pen-based computing is recognition of connected, cursive writing. Certainly the technological barriers of achieving connected recognition are formidable — even AT&T Bell Lab researchers assert that “machine reading of unformatted, hand-written script is a dream we are unlikely to see come true in the near future…” This after more than a quarter century of research in this field. Of course, not all pen-based applications — particularly the first-generation data-collection programs we’ll initially see — require cursive recognition. Forms completion, editing, communication, and other such “non-handwriting dependent apps” will make up the bulk of the initial round of pen-based software.

Nevertheless, researchers still look for solutions to the puzzle and breakthroughs may be closer than we think.

Identifying the Problem

Among the most challenging snags that must be negotiated before acceptable recognition can be realized are feature extraction, segmentation, and context sensitivity. Feature extraction is simply the process of extracting relevant patterns from the stream of data. A feature is any aspect of the data deemed useful to the recognition process.

A key step in building a recognizer is deciding what constitutes a feature, and how a set of features represents a character. Features usually (but not always) have to do with a character’s shape. One way of categorizing character shapes is by their edges. Another approach may discard information about edges and only work with the core image, or “skeleton” of a character. Early approaches to image recognition did not use shape data directly, but relied on a more subtle feature of graphical objects, their two-dimensional visual frequency (Fourier transform).

Whatever method is used, however, it must be able to deal with the wide range of distortions found in individuals’ handwriting. For example, my cursive c and e look very similar; on the other hand, your handwriting may clearly differentiate these characters, and muddle others. This variation is dealt with by storing more than one version of a character’s shape, sometimes many such versions.

Another issue is segmentation, which refers to the need to divide a field of data into zones, and the zones into individual characters, so that the character recognizer can work with manageable chunks of data. Each chunk will hopefully correspond to a single character in the recognizer’s library of prototype shapes. This segmentation process is complicated, particularly when characters touch as they do in cursive handwriting. Here, the classic example is a word like “better” which has consecutive t’s. For many people, the letters “tt” come out looking like an uppercase “H.” One key decision in building a recognition system is the order in which segmentation and shape matching are undertaken. Early systems segment first, then match shapes. More sophisticated systems have a fluid dialogue between the segmentor and the character recognizer, each adjusting their results in response to each other’s work.

Having context sensitivity can simplify this complicated process. For instance, a recognition system that provides context sensitivity will know when you are writing the letter “O,” the number “0,” drawing a circle, or using a circular gesture command. This guidance can be external to the recognizer, when an application program gives “hints” to the recognition system about what kind of input to expect. For instance, a spreadsheet application might tell the recognition engine to expect numeric input (a zero), while a drawing program can tell it to expect circles. Context sensitivity can also come from a component internal to the recognition system, that may be aware of word lists (dictionary) or grammatical usage.

In short, there is a sequence of steps that must be taken before recognition occurs, each of which can require extensive computing power: acquiring the character, identifying the zones for processing, extracting the features, and performing the recognition. In sophisticated systems, all of these processes are effectively going on at the same time. Coordinating the results of these efforts can be tricky. PenPoint implements an AI technique called “blackboarding” to coordinate efforts, “weigh” results from the multiple participants in the recognition effort.

Different Strokes

Before going further, it’s important to distinguish between “stroked” characters and “image” characters. Stroked characters are those generated by pen-based computer users — they appear as you write on the computer and are ultimately translated to ASCII. Image characters, however, might be machine generated and appear as bit images. One difference is that image characters are typically much more uniform than stroked images and therefore easier to recognize. Image characters also include hand-printed characters, but only those for which the stroke information has been lost or discarded, and only the bitmap image of the character is available.

Pen-based systems usually need to handle both stroked and image characters. With PenPoint, for instance, recognition of strokes begins immediately as you start writing; otherwise recognition would have to occur at the end of the line or word, thereby inhibiting performance. Once the character(s) is complete, the system looks at the “image” and translates it to an ASCII character. Managing both stroked and image characters enhances the speed and accuracy of recognition performance.

Another application of image/stroke recognition might be with pen-based systems that recognize “stroke” input while also recognizing and translating “images” from an incoming FAX. The recognized characters could then be loaded into the word processor for editing and rewriting. Obviously this would require a high-speed, highly accurate recognition engine, a multitasking operating system, and quite possibly a coprocessor.

Searching for Solutions

There are a variety of software techniques that enable recognition of both cursive and disconnected handwriting. These techniques include traditional procedural methods as well as newer approaches like neural networks or fuzzy logic, or a combination of the above. Here, we’ll focus on some of the current work underway with neural networks.

While a general discussion of neural net technology is beyond the scope of this article, there are a number of sources you can turn to, some of which deal specifically with the topic of neural nets and handwriting recognition. For instance, see “Untangling Neural Nets” by Jet Stanley (Dr. Dobb’s Journal, April, 1990) and “Divide and Conquer” by David Wright and Chris Scofield (Byte, April, 1991). There are many more technical papers, magazine articles, and books available on neural nets (bibliography available on request).

Neural network systems are formed by simulated neurons connected in much the same way as the brain’s neurons. They operate by making associations and generalizations, solving the kinds of problems that humans do: association, evaluation, and pattern recognition. Even with this thumbnail sketch, you can expect that they could be especially valuable for recognizing characters, handwritten and machine-generated. And neural nets are also valuable because they can make good conclusions from incomplete or imprecise data (like handwritten characters), they can identify patterns even when “noise” exists, and they can be trained to “learn” individual characteristics.

Interestingly, neither Go’s PenPoint nor Microsoft’s PenWindows use neural net technology for character recognition, although the open architecture of both environments allows developers to “plug in” third-party recognizers, including neural net recognition engines. Likewise, most existing commercial OCR machines are based on the traditional procedural or rule-based approaches. However, research outfits that have been working on the problem of text recognition for a long time are turning towards neural nets as a possible means for overcoming hurdles that have stymied progress.

Single-Layer Neural Nets in Silicon

At Bell Labs, neural networks for handwriting recognition has been an active area of research because, says Larry Jackel, “we’ve found that the neural network method is the fastest to implement the heuristic solution [e.g., in software] and that it is also easy to implement in hardware.” That is, after long years of hand-coding procedural programs to get, say, a 97 percent accuracy in recognition, they’ve found they can implement neural net approaches in much less time and quickly achieve 90-93 percent accuracy. There are still, of course, several yards to go before a touchdown, but researchers are very optimistic.

Much of AT&T’s work has centered upon a custom analog single-layer neural net processor nicknamed “ANNA” that’s used in conjunction with a 386-based PC containing an optional AT&T DSP32c digital signal processor (DSP) chip/board. (AT&T isn’t alone in developing neural net chips. Intel has had its ETANN (Electronic Trainable Artificial Neural Network) chip on the market for at least a year, along with a PC-board that uses the chip. Currently, Intel is developing the N1000, a more powerful chip that’s ideal for applications like handwriting recognition. Motorola has also been developing a neural net technology that could presumably be implemented in a standalone chip or integrated into a CPU.) A hardware configuration like this can come close to providing real-time recognition, especially when DSP is implemented.

In the AT&T system, text recognition is handled by the neural net at the rate of 1 character per second on a plain-vanilla Sun 3 workstation; when DSP is added, the rate increases to 10 characters per second; when implemented in silicon, the rate goes up to 500 characters per second. (Keep in mind that the recognizer in Go’s Penpoint system operates at 3 characters/second.)

According to Jackel, however, AT&T’s current focus is with segmentation. The AT&T approach is to break characters up so that various components can be identified. They do this by making many cuts on the image, then try to recognize the bit map with each cut. They then compare and look for the set of cuts over the entire field that yields the highest confidence score. Jackel says that repetitive techniques means that lots of recognition must occur, but by using a preprocessor to normalize the image along with a combination segmentary/recognizer, a postprocessor can then pick out the most likely segments. All of this recognition takes a lot of computing horsepower but computing horsepower is cheap, especially when custom VLSI neural net chips and DSP come into play.

Obviously no one can write at the rate of 500 characters per second so putting neural net silicon in pen-based systems would be overkill. However, using neural nets in software while utilizing DSP coprocessors could dramatically improve performance. The main benefit of this would be to offload processing from the CPU to the coprocessor, thereby enabling the CPU to attend to other tasks, perhaps attending to higher recognition accuracy or display refresh.

The AT&T system is currently not a commercial product, although it is being used under contract for proprietary character recognition systems. Perhaps the trickle-down effect of this research will provide support for pen-based computers sometime in the future.

Multiple Neural Nets in Software

Although Nestor Inc. is also using neural nets to tackle the handwriting recognition problem, the company’s tactic with its Nestor-Reader is to implement a multiple neural net architecture in software. In this case, some neural nets extract features, while others classify data — and all nets are capable of both extraction and classification.

One advantage of the multiple neural net approach is that, even more so than the single-layer style, it lends itself to parallel processing architectures since different neural nets can be controlled by different processors. A parallel architecture provides a couple of benefits. For one thing, speed increases linearly with the addition of transputers — if one processor recognizes at 10 cps, three processors recognize at 30 cps. Also, a system safety nets exists; if one processor fails, backup is already on-line. Furthermore, multiple nets and parallel processors can easily split up tasks — upper/lower case differentiation on one net or processor, numeric/alpha differentiation on another.

Currently, Nestor supports transputer-based architectures from Inmos, recognizing at the rate of about 10 characters per second. This approach has proven to be very efficient, especially when the transputer’s load balancing capabilities spreads the processing work around. The company is also working with Intel in the development of the N1000 neural net chip which will be capable of character recognition at rates of 5000 to 10000 character/second.

Nestor supplies two recognition-related products: the NestorReader, an recognizer for OEM customers; and NestorWriter, a pen/pad input device for desktop PCs that replaces the mouse and keyboard. NestorReader currently has a Windows 3 interface with an interface to PenWindows coming shortly and a PenPoint system down the road.

Speed Versus Accuracy

Up to now, we’ve been discussing mostly one side of the coin — speed; the other side is accuracy. What’s the good of recognizing several thousand characters per second if several hundred of them are incorrect?

Nestor claims that the multiple neural net architecture provides higher accuracy rates than single-layer approaches like that of AT&T. One reason for this is that singlelayer back-propagating (“backprop,” for short) neural nets use about 10,000 “weights,” which are a means of measuring the strength of a specific neural connection as defined by the relationship between the receiving neuron and the sending neuron. But to accurately train a net, you need roughly 10 times the number of training patterns as available weights — 100,000 in this case. Nestor charges that single-layer nets haven’t been trained on this number of weights so that worst case accuracy results are therefore very poor. In short, it is very difficult to scale single-layer nets to larger applications; multiple neural nets can be more accurate and just as fast with a fewer number of weights.

To test accuracy, Nestor compared a four-layer multiple neural net to a single-layer backprop neural net like that used by AT&T; the results were presented at the IEEE’s CompCon Conference in February 1991. In the performance measurement, P is measured by a formula that weighs errors 10 times more than rejects: P=100-10x(%error)-(%reject). The multiple neural net data consisted of 4767 digits from the National Institute of Standards and Technology while the data used to measure single-layer performance was from the 2000 ZIP code digits from the US Postal Service. The four-layer net performed at P=89.7 while the single-layer backprop net performed at P=81 and P=80.5.