WO1994022109A1

WO1994022109A1 - Handwriting recognition device and method

Info

Publication number: WO1994022109A1
Application number: PCT/GB1994/000531
Authority: WO
Inventors: Paul Booth
Original assignee: Eden Group Ltd
Current assignee: Eden Group Ltd
Priority date: 1993-03-17
Filing date: 1994-03-16
Publication date: 1994-09-29
Anticipated expiration: 1995-09-17
Also published as: GB9305495D0

Abstract

A handwriting recognition engine for a pen computer is disclosed which can be trained to recognise a new graphically input character by generating a characterisation defining the new character and adding the characterisation of the new character to a library. The engine discards characterisations that are rarely selected as the best match to graphical input to be recognised.

Description

Handwriting recognition device and method

Field of the Invention

This invention relates to a hand writing recognition device and method, particularly one which can be used in a pen computer.

Description of the Prior Art

Pen computers are well known and generally comprise a stylus or pen that can co¬ operate with a digitising tablet overlying an LCD display. This is a particularly convenient design for small, hand held computers, known as "Personal Digital Assistants" or "PDAs", as exemplified by the Amstrad Penpad, Apple Newton and EO products.

Such computers allow the input of graphical data such as handwriting. For example, the user can use the stylus on the display just as if the stylus were a pen and the display were paper, i.e. where the user touches the stylus to the display the underlying pixels of the display are darkened. This is commonly called 'electronic inking'. In addition to storing such graphical input as a bit mapped image, most pen computers can also convert alpha-numeric graphics to ASCII by a handwriting recognition engine. They therefore closely mimic the conventional paper-based personal organiser to provide a high level of user-friendliness, but provide added functionality. Further reference may be made to GB 2229301 B.

There are a variety of approaches to handwriting recognition, all of which will be familiar to the skilled implementer. In brief, handwriting recognition is commonly achieved in one of two ways:

[ 1 ] In the vector approach, the path of the contact point of the stylus is defined by a series of vectors. The system traces the path, laying down a series of vectors whose angle and length define the shape of that path. The set of vectors for the input is then compared, by a recogniser, with a set of stored vectors which define each of the stored characters which the system can recognise. The recogniser then generates a score that indicates which of the stored characters the input is closest to. The recogniser causes the screen font of the closest stored character to be displayed in the field in which the user wrote the input. Where the character is a correct match, the user need do nothing. However, where the system outputs an incorrect match, then the user can overwrite the incorrect character to give the system a second chance.

[2] In the bit-mapped approach, the output from the digitising circuitry essentially defines a set of X,Y co-ordinates mapping the contact path of the pen, with a resolution determined by the sampling rate used. Generally, the contact points for each stroke will be separately stored in a separate stroke buffer. After all the strokes of a given character have been stored, the system takes a "time out" during which a 16 X 16 bit mapped version of the input is generated by a pre- processor which then scales the character to fill a 16 X 16 pixel grid. The scaled input is then compared against various characters that the recogniser has been programmed to recognise, and, as in the vector approach above, the recogniser outputs the closest character to the field in which the user wrote the input. Again, the user can overwrite the output if it is incorrect.

Conventional systems can also be customised to recognise a particular user's handwriting; this process is called 'training' and generally involves supplementing the pre-programmed characters against which the graphical input is matched with further characters supplied by the actual user. In this way, a given user's handwriting idiosyncrasies can be catered for, Additionally, training allows the user to program the computer to accept gestures or symbols, e.g.circling a piece of text, as command inputs. Conventionally, training is achieved by the user writing the alpha-numeric that the system is to be trained to recognise into a single recogniser field that can accept only a single alpha-numeric. The user can then dictate which character should be matched to the input by indicating the correct match by hitting the appropriate key on an on-screen keyboard. For example, in a typical system, beneath the single recogniser window there may be a simulated QWERTY keyboard. Consequently, if the user inputs a letter 'a' in natural handwriting, but the system mis-recognises this as an 'o', then the user could select the letter 'a' on the simulated keyboard, thus training the recogniser to characterise this input as an 'a'. The system stores the characteristics of the natural handwriting input letter 'a' and, when a further graphical input most closely matches these characteristics, then the system writes an 'a' on the display. In conventional recognisers, the new characterisations obtained through training are added to the end of a library consisting of a single linked list of the previously stored characterisations. This leads to the library gradually becoming larger, this has hitherto not been a significant problem since prior art recognisers are f le based. Thus, the increasing file size is not detrimental, so long as the mass storage device of the computer has adequate capacity.

Objects of the Invention

It is an object of the present invention to provide a hand writing recognition device and method, particularly one which can be used in a pen computer,, in which the library of stored characterisations is managed in a more economical way than in the prior art.

Statement of the Invention

In accordance with the present invention, a hand writing recognition device for a pen computer, which can be trained to recognise new graphically input characters and add the characterisations of the new characters to a library, is arranged to discard characterisations that are rarely selected as the best match to graphical input to be recognised. By providing for the discarding of redundant characterisations, the memory requirements of such a recognition device are less than the prior art file based devices; this enables the device to be implemented in a limited capacity ROM. Also, searching of the stored characterisations becomes faster since fewer have to be searched.

Preferably, management of the recogniser library in this way is achieved by adding new characterisations to the front of the single linked list of other characterisations, as opposed to the end, and by making the list have only a finite number of members. Consequently, old members will be discarded automatically when they reach the end of the list. Also, a library manager may be provided that allocates to each characterisation a number derived from how often that characterisation is regarded as the best fit to an input; those characterisations for a given character with 'hit counts' below a predetermined number will be automatically discarded. In another aspect of the present invention, there is provided a method of controlling a hand writing recognition device for a pen computer, which device can be trained to recognise a new graphically input character by generating a characterisation defining the new character and adding the characterisation of the new character to a library, the method comprising the step of discarding characterisations that are rarely selected as the best match to graphical input to be recognised.

The present invention may be implemented in hardware, software or firmware and may operate on a conventional pen computer and supplement the operation of conventional handwriting recognition engines. In a further aspect, the present invention therefore comprises the recordable media which, when used in conjunction with a conventional handwriting recognition engine implemented in hardware, software or firmware, allows the above described invention to be implemented.

In a still further aspect, the present invention comprises the recordable media which when used in conjunction with a conventional handwriting recognition engine implemented in hardware, software or firmware, results in a hand writing recognition device for a pen computer which is operable to be trained to recognise a new graphically input character by generating a characterisation defining the new character and adding the characterisation of the new character to a library, and which is further arranged to discard characterisations that are rarely selected as the best match to graphical input to be recognised.

The recordable media may be a magnetic floppy disc, ROM, CD-ROM, flash memory, or other memory device. In a yet further aspect, the invention comprises a method of manufacturing such a recordable media.

Similarly, the design of handwriting recognition engines is well known and there are numerous vendors supplying such engines, such as Nestor. It should also be noted that this invention may be utilised in all forms of recogniser, and its applicability is not simply limited to vector or bit mapped systems. Generally, the design of PDAs is also well known to those skilled in the art and will be described only briefly here. In particular, there are a number of well known different approaches to digitising technology; reference may be made to the products from, for example Wacom Co. Ltd, Numonics Inc. or Summagraphics Inc.

Brief Description of the Drawings

The invention will be further described with reference to the accompanying drawings which depict a pen computer in accordance with the present invention, and more particularly which show: in Figure 1 a schematic view of the main components of a pen computer incorporating a hand writing recognition device in accordance with the present invention; in Figure 2 a schematic view of the main components of a hand writing recognition device in accordance with the present invention;

Detailed Description

Referring now to Figure 1, a display means, preferably comprising a LCD type display 3, is shown forming part of a pen computer indicated generally at 1. The input arrangement for this type of pen computer is well known in this art and will only be briefly described here. Pen computer 1 comprises an electromagnetic induction digitising mat or tablet 2 underlying the display 3, together with an electromagnetic stylus 4. The digitising mat 2 comprises an electrically conducting grid with conductors running parallel to an X-axis, overlaying a similar grid with conductors running parallel to a Y-axis. The stylus 4 comprises an energisable coil (not shown) which can be excited with alternating current . The amplitude of the voltages induced in the conductive grids provide an indication of the position of the stylus 4 relative to the Cartesian co-ordinate system defined by the X and Y axes. The detailed operation of this form of digitiser is well known in this field. Further reference may be made, for example, to US 4570033. Using this digitising system, the user can easily and naturally input graphical information for storage and virtually simultaneous display on the display 3 as electronic ink. Whilst the transducer pad 2 is shown schematically underlying the LCD type display 3, it may in practice be embedded within it or positioned above it.

It will be appreciated that a variety of components, e.g. a power supply, is necessary for the functioning of the apparatus and will have to be present in the apparatus but these are not expressly detailed here in the interests of brevity and clarity.

Returning to Figure 1, the stylus 4 is touching the display 3 and electrical signals indicative of the position (X Y Co-ordinates) at which it contacts the display 3 are supplied to an A to D converter 11 feeding a data path or system bus 15. A CPU 12 is connected for bi-directional data flow to the bus 15, as is a RAM 17. A ROM 18 is also connected to bus 15, being programmed with the operating system for the apparatus, including the telecommunications procedures and the word processing and graphics software which allows users to input, amend and edit textual or graphic information on screen using the stylus. By way of example, the stylus can be used as an electronic pen to input handwritten graphics and can be used in an eraser mode whereby as it is moved over displayed text that text is deleted from display. More particularly, the user can use the stylus on the display area 3 displaying a simulated page just as if the stylus were a pen and the simulated page were paper, i.e. where the user touches the stylus to the screen the underlying pixels of screen 3 are darkened. This is commonly called 'electronic inking'.

CPU 12 provides all control signals via bus 15 and further includes an internal clock which allows all inputs to the device to be flagged with a time signal indicating when that input was made. RAM 17 stores the user input, i.e. all original input plus any annotations or amendments the device user might wish to make to that input. A display driver 14 is connected to bus 15 and drives the display 20. A communications port 19 is shown connected to the bus 15 and allows the present apparatus to be networked to other electronic devices, e.g. other apparatus like the present invention.

A handwriting recognition device, implemented as ROM 20 is shown connected to bus 15. The structure of the recogniser 20 is indicated schematically in Figure 2. The operation of much of the recogniser will be familiar to the skilled implementer, briefly, referring now to Figure 2, for a bit-mapped recogniser, the set of X,Y co- ordinates mapping the contact path of the pen is supplied from A to D converter 11 to a stroke buffer [not shown] and passes 33 from the stroke buffer to the pre¬ processor 21. Pre-processor then 21 scales the character to fill a 16 X 16 pixel grid and provides 34 this data to recogniser 22. There follows a series of comparisons, effected by recogniser 22, between the scaled character and characters called from 35 the library 23 of previously defined characters. In most systems, the comparison is made between different features of the stored characters; the recogniser determines which stored character the input is closest too overall and outputs 40 a signal which results in the appropriate character being displayed on the display 3. Library manager 24 allocates a recognition 'hit count' number to each characterisation so that it can determine which characterisations of any given character are the least popular. It periodically deletes those least popular characterisations from the single linked list, thus keeping the size of the list down and ensuring that only the more relevant records are searched.

When the user wishes to train the recogniser 20, then the user selects the training function using a drop-down menu or dedicated key. This results in a simulated alpha-numeric keyboard being displayed in the screen 3 within a window. Hence, when the user wants to train the system to recognise the letter 'a' better, the user then selects the letter 'a' on the simulated keyboard by touching d e stylus to the simulated 'a' key. The recogniser 20 then generates on screen a comb within a window, the comb comprising a series of four single recogniser fields. The user then writes a single letter 'a' into each of those four fields; as above, the set of X,Y co-ordinates mapping the contact path of the pen is supplied from A to D converter 11 to a stroke buffer [not shown] and passes 30 from the stroke buffer to the pre-processor 21. Pre-processor then 21 scales each of the four characters to fill a 16 X 16 pixel grid and provides 31 this data to recogniser 22. The recogniser 22 characterises each input and stores 32 in library 23 the characterisation of all four examples. In the present invention, these new characterisations are added to the front of the list of all other stored characterisations. These other stored characterisations may be factory set and supplemented by new characterisations derived from training. They form the basis for comparison with all later graphical input to be recognised. Library manager 24 is connected to the library 23 and performs the general library housekeeping functions, as well as allocating new characterisations to the front of the list and allocating a recognition hit count to each characterisation. If the user now writes in a letter 'a' whilst in normal recogniser mode, i.e. not train mode, and that input is closer to one of the four new definitions of the user's letter 'a', now stored in the library 23, than any other character, then the recogniser will determine that the letter 'a' has to be displayed.

Claims

1. A hand writing recognition device for a pen computer, which device can be trained to recognise a new graphically input character by generating a characterisation defining the new character and adding the characterisation of the new character to a library, and which is arranged to discard characterisations that are rarely selected as the best match to graphical input to be recognised.

2. A hand writing recognition device as claimed in Claim 1 wherein new characterisations are added to the front of a finite single linked list of other characterisations so that the characterisations at the end of the list are automatically discarded.

3. A hand writing recognition device as claimed in Claim 2 further comprising a library manager to allocate to each characterisation a number derived from how often that characterisation is regarded as the best fit to an input, whereby those characterisations for a given character with 'hit counts' below a predetermined number are arranged to be automatically discarded.

4. A method of controlling a hand writing recognition device for a pen computer, which device can be trained to recognise a new graphically input character by generating a characterisation defining the new character and adding the characterisation of the new character to a library, the method comprising the step of discarding characterisations that are rarely selected as the best match to graphical input to be recognised.

5. Recordable media which, when used in conjunction with a conventional handwriting recognition engine implemented in hardware, software or firmware, allows the device claimed in Claims 1 - 4 to be implemented.

6. Recordable media which when used in conjunction with a conventional handwriting recognition engine implemented in hardware, software or firmware, results in a hand writing recognition device for a pen computer which is operable to be trained to recognise a new graphically input character by generating a characterisation defining the new character and adding the characterisation of the new character to a library, and which is further arranged to discard characterisations that are rarely selected as the best match to graphical input to be recognised.

7. Recordable media as claimed in Claims 5 and 6, being a magnetic floppy disc, ROM, CD-ROM, flash memory, or other memory device.

8. A method of manufacturing the recordable media claimed in Claims 5 - 7.