Real time handwriting recognition system

• US 5,991,441 A
• Filed: 06/07/1995
• Issued: 11/23/1999
• Est. Priority Date: 06/07/1995
• Status: Expired due to Term

• Current Assignee: 3M Innovative Properties Company (3M Company)
• Original Assignee: Wang Laboratories Incorporated
• Inventors: Jourjine, Alexander N.
• Primary Examiner(s): COUSO, YON JUNG
• Assistant Examiner(s): Nguyen, Ha Tran
• Application Number:
  US08/476,826
• Time in Patent Office: 1,630 Days
• Field of Search: 382/187, 382/186, 382/185, 382/188, 382/189, 382/309, 382/310, 382/311
• US Class Current: 382/187
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06V 30/347 Sampling; Contour coding; Stroke extraction
• CPC Class Codes: G06V 30/373 using a special pattern or subpattern alphabet

Abstract

A handwritten character recognizer having an input cluster buffer and a point buffer with dynamic and static stroke feature extraction and segment analysis by conical boundaries for identification of stroke segments dynamic stroke feature extractor static stroke feature extractor. A stroke recognizer compares single copies of idealized stroke representations with hierarchically approximated multiple scaled topological representations of a current stroke, followed by stroke proportion discrimination comparing a selected topological representation of the current stroke with boundaries defined by linear combinations of features of direct and reversed ideal stroke prototypes to provide a stroke identification. A cluster recognizer maintains a time ordered current stroke buffer and previous stroke buffer and constructs a per stroke area of influence list. The time ordered buffers are scanned to generate a spatially ordered window buffer. A position discriminator assigns character meanings to clusters of stokes in the window buffer. The buffer scanner is responsive to a current stroke having spatial coordinates located between previous strokes for reordering the stroke buffers and determining a new cluster meanings. An editor is responsive to an editing gesture or combination of two strokes for directing the stroke buffer controller to modify the strokes in the stroke buffer accordingly.

Claims

1. A handwritten character recognition system for use in a data processing system including a tablet and pen for user entry of handwritten characters and a processing unit connected from the tablet and pen for operating upon the user input under control of the character recognition system, the handwritten character recognition system comprising:

a pen input detector for detecting and indicating user inputs through the tablet and pen, the user inputs including pen strokes and pen states,

an input cluster buffer connected from the pen input detector for storing stroke descriptor information of a current stroke as the current stroke is entered by the user,

a point buffer connected from the input cluster buffer for storing the stroke descriptor information of the current stroke,

a point detector connected from the input cluster buffer and responsive to the pen states for transferring the stroke descriptor information of the current stroke into the point buffer,

a stroke feature recognizer including a dynamic stroke feature extractor connected ftom the point buffer and responsive to a pen down state for dynamically extracting stroke recognition features from the stroke descriptor information of the current stroke as the current stroke is entered by the user and for assigning a meaning to the current stroke,

wherein the stroke recoriition features describe the current stroke with variable degrees of hierarchical approximations, the hierarchical approximations including multiple scalar representations of the current stroke, and

a cluster recognizer connected ftom the stroke feature recognizer and responsive to the meaning assigned to each stroke for recognizing and assigning a character meaning to a current cluster of strokes.

2. The handwritten character recognition system of claim 1 wherein the stroke feature recognizer further comprises:

a static stroke feature extractor connected from the point buffer and responsive to the pen states for extracting stroke recognition features from the stroke descriptor information of the current stroke when the current stroke is completed.

3. The handwritten character recognition system of claim 2 wherein:

the static stroke feature extractor is responsive to a pen up state for statically extracting stroke recognition features from the stroke descriptor information of the current stroke when the current stroke is completed.

4. The handwritten character recognition system of claim 1 wherein the stroke descriptor information comprises:

for each stroke,

a sequence of coordinate points along the line of the stroke, including at least the first and last points of the line of the stroke, and

a direction string indicating, for each point of the string, the direction of movement of the line of the stroke at the point.

5. The handwritten character recognition system of claim 4 wherein the stroke feature extractor further comprises:

a segment analyzer for identifying segments of a stroke wherein a segment of a stroke includes at least a beginning point of the segment and an end point of the segment and wherein a segment does not contain a change in direction of movement of the line of the stroke,

a direction analyzer for identifying changes in the direction of movement of the line of a stroke wherein

a change in direction of movement of the line of a stroke occurs when an angle between two lines connecting three consecutive points along the stroke exceeds a predetermined boundary defined by two lines extending from any one of the three points, the two lines extending from that point in the direction of movement of the pen at that point and the angle between the two lines being defined by predetermined displacement perpendicular to the direction of movement of the pen at that point.

6. The handwritten character recognition system of claim 5 wherein the segment analyzer further comprises:

a segment constructor responsive to the direction analyzer for inserting an additional point at a change in direction of the line of a stroke,

the additional point is located at the end point of the segment before the change in direction of the line of the stroke and operating as the beginning point of the segment following the change in direction of the line of the stroke.

7. The handwritten character recognition system of claim 1 wherein the stroke feature recognizer further comprises:

a stroke recognition feature data structure for storing the stroke recognition features extracted from the current stroke, wherein

the stroke recognition features describe the current stroke with variable degrees of hierarchical approximations, the hierarchical approximations including multiple scalar representations of the current stroke and including the direction string indicating, for points along the line of the stroke, the direction of movement of the line of the stroke at each point.

8. The handwritten character recognition system of claim 7 wherein the stroke recognition features further include:

the coordinates of at least the beginning and end points of the line of the stroke.

9. The handwritten character recognition system of claim 7 wherein the stroke recognition features further include:

an array of coordinates of all points along the line of the stroke as received as input coordinates from the tablet.

10. A handwritten character recognition system for use in a data processing system including a tablet and pen for user entry of handwritten characters and a processing unit connected from the tablet and pen for operating upon the user input under control of the character recognition system, the handwritten character recognition system comprising:

a pen input detector for detecting and indicating user inputs through the tablet and pen, the user inputs including pen strokes and pen states,

an input cluster buffer connected from the pen input detector for storing stroke descriptor information of a current stroke as the current stroke is entered by the user,

a point buffer connected ftom the input cluster buffer for storing the stroke descriptor information of the current stroke,

a point detector connected from the input cluster buffer and responsive to the pen states for transferring the stroke descriptor information of the current stroke into the point buffer,

a stroke feature recognizer connected from the point buffer and responsive to the pen states for extracting stroke recognition features from the stroke descriptor information of the current stroke and assigning a meaning to the current stroke, and

a cluster recognizer connected from the stroke feature recognizer and responsive to the meaning assigned to each stroke for recognizing and assigning a character meaning to a current cluster of strokes,

wherein the stroke feature recognizer includes

a multiple scale stroke representation generator for

reading the stroke recognition features from the stroke recognition feature data structure,

generating a plurality of scaled topological representations of the current stroke,

each scaled topological representation being a progressively smoothed representation of the current stroke generated from the stroke representation features,

selecting a scaled topological representation of the current stroke, the scaled topological representation of the current stroke being selected to provide the maximum signal to noise ratio of the stroke representation,

a stroke proportion discriminator responsive to the scaled topological representation of the current stroke for storing a list of ideal prototype representations corresponding to possible meanings of the current stroke from a plurality of ideal prototype representations of strokes, and

a stroke boundary discriminator responsive to the scaled topological representation of the current stroke and to the ideal prototype representations of the list of ideal prototype representations for comparing the scaled topological representation of the current stroke and

boundaries of the ideal prototype representations of the list of ideal prototype representations wherein the boundaries of the ideal prototype representations are determined by linear combinations of features of the ideal prototype representations, and

assigning to the current stroke an identification of an ideal prototype representation having boundaries including the scaled topological representation of the current stroke, the assigned identification of the matching ideal prototype representation representing a stroke meaning assigned to the current stroke.

11. The handwritten character recognition system of claim 10 wherein the stroke feature recognizer further comprises:

a stroke recognition feature data structure for storing the stroke recognition features extracted from the current stroke, wherein

the stroke recognition features describe the current stroke with variable degrees of hierarchical approximation, and include

the direction string indicating, for points along the line of the stroke, the direction of movement of the line of the stroke at each point.

12. The handwritten character recognition system of claim 11 wherein the stroke proportion discriminator further generates, for each ideal prototype representation, a corresponding reversed ideal prototype representation having a reversed direction string for use in the comparison of features of the topological representations of the current stroke and of the ideal prototype representations.

13. A handwritten character recognition system for use in a data processing systern including a tablet and pen for user entry of handwritten characters and a processing unit connected from the tablet and pen for operating uDon the user input under control of the character recognition system, the handwritten character recognition system comprising:

a pen input detector for detecting and indicating user inputs through the tablet and pen, the user inputs including pen strokes and pen states,

an input cluster buffer connected from the pen input detector for storing stroke descriptor information of a current stroke as the current stroke is entered by the user,

a point buffer connected from the input cluster buffer for storing the stroke descriptor information of the current stroke,

a point detector connected from the input cluster bufer and responsive to the pen states for transferring the stroke descritor informration of the current stroke into the point buffer,

a stroke feature recognizer including a dynamic stroke feature extractor connected from the point buffer and responsive to a pen down state for dynamically extracting stroke recognition features from the stroke descriptor information of the current stroke as the current stroke is entered by the user and for assiliini a meaning to the current stroke, and

a cluster recognizer connected from the stroke feature recognizer and responsive to the meaning assigned to each stroke for recognizing and assigning a character meaning to a current cluster of strokes,

wherein the stroke feature recognizer is responsive to the stroke recognition features for assigning a meaning to each current stroke and the cluster recognizer includes

a stroke buffer, including

a current stroke buffer for storing the strokes of a current cluster of strokes in the time order of their entry, and

a previous stroke buffer for storing the strokes of a cluster of strokes immediately preceding the current cluster of strokes,

a window buffer for storing a contiguous group of strokes in spatial order according to the coordinates of the strokes of the group,

a stroke buffer controller responsive to the stroke feature recognizer for constructing an influence list containing an identification of an area of influence of each stroke of the current cluster of strokes,

receiving a current stroke,

determining an area of influence of the current stroke, when the area of influence of the current stroke indicates that the current stroke is a part of the current cluster of strokes,

writing the current stroke into the current stroke buffer, and

when the area of influence of the current stroke indicates that the current stroke is not a part of the current cluster of strokes,

transferring the strokes of the current cluster of strokes into the previous stroke buffer, and

writing the current stroke into the current stroke buffer to begin a new current cluster of strokes,

a stroke buffer scanner for scanning the influence list, and

writing the strokes of the current stoke buffer into the window buffer in spatial order,

a position discriminator for storing a cluster data structure containing a plurality of cluster meanings,

each cluster meaning representing a cluster of strokes and a corresponding meaning assigned to the cluster of strokes,

reading combinations of strokes from the window buffer,

comparing the combinations of strokes from the window buffer with the cluster meanings stored in the cluster data structure,

determining when a combination a strokes from the window buffer corresponds to a cluster meaning,

providing as an output an identification of the cluster meaning corresponding to the combination of strokes from the window buffer,

removing the combination of strokes from the window buffer, and transferring the combination of strokes fom the current cluster buffer to the previous stroke buffer.

14. The handwritten character recognition system of claim 13 wherein:

the stroke buffer controller is responsive to a current stroke having spatial coordinates located between strokes which are previous in time for

reordering the strokes in the current and previous stroke buffers,

the stroke buffer scanner is responsive to the reordering of the current and previous stroke buffers for rewriting the strokes of the current stoke buffer into the window buffer in a corresponding new spatial order, and

the position discriminator is responsive to the rewriting of the window buffer for determining a new cluster meaning from the new combinations of strokes in the window buffer.

15. The handwritten character recognition system of claim 14 wherein the new stroke is an editing gesture and the handwritten character system further comprises:

an editor responsive to the editing gesture for directing the stroke buffer controller to modify the strokes stored in the stroke buffer as indicated by the editing gesture.

16. The handwritten character recognition system of claim 13 wherein a combination of two consecutive strokes comprises an editing command and wherein:

the position discriminator is responsive to the combination of two consecutive strokes comprising an editing command for providing an output indicating the editing command, and

the handwritten character recognition system further includes an editor responsive to the editing command for directing the stroke buffer controller to modify the strokes stored in the stroke buffer as indicated by the editing command.

17. In a data processing system including a tablet and pen for user entry of handwritten characters and a processing unit connected from the tablet and pen for operating upon the user input, a method for recognizing handwritten characters, comprising the steps of:

storing stroke descriptor information of a current stroke in a stroke buffer as the current stroke is entered by the user,

responsive to the pen states, transferring the stroke descriptor information of the current stroke into a point buffer,

in response to a pen down state, dynamically extracting stroke recognition features from the stroke descriptor information of the current stroke and dynamically assigning a meaning to the current stroke,

wherein the stroke recognition features describe the current stroke with variable degrees of hierarchical aIproximations, the hierarchical approximations including mutiple scalar representations of the current stroke, and

recognizing and assigning a character meaning to a current cluster of strokes.

18. The method for recognizing handwritten characters of claim 17, further comprising the steps of:

extracting stroke recognition features from the stroke descriptor information of the current stroke when the current stroke is completed.

19. The method for recognizing handwritten characters of claim 18 wherein:

the static extraction of stroke recognition features from the stroke descriptor information of the current stroke when the current stroke is completed is in response to a pen up state.

20. The method for recognizing handwritten characters of claim 17 wherein the stroke descriptor information comprises:

for each stroke,

a sequence of coordinate points along the line of the stroke, including

at least the first and last points of the line of the stroke, and

a direction string indicating, for each point of the string, the direction of movement of the line of the stroke at the point.

21. The method for recognizing handwritten characters of claim 20, further comprising the steps of:

identifying segments of a stroke wherein a segment of a stroke includes at least a beginning point of the segment and an end point of the segment and wherein a segment does not contain a change in direction of movement of the line of the stroke, and

identifying changes in the direction of movement of the line of a stroke wherein

a change in direction of movement of the line of a stroke occurs when an angle between two lines connecting three consecutive points along the stroke exceeds a predetermined boundary defined by two lines extending from any one of the three points, the two lines extending from that point in the direction of movement of the pen at that point and the angle between the two lines being defined by predetermined displacements perpendicular to the direction of movement of the pen at that point.

22. The method for recognizing handwritten characters of claim 21, further comprising the steps of:

inserting an additional point at a change in direction of the line of a stroke, wherein

the additional point is located at the end point of the segment before the change in direction of the line of the stroke and operating as the beginning point of the segment following the change in direction of the line of the stroke.

23. The method for recognizing handwritten characters of claim 17, further comprising the steps of:

storing the stroke recognition features extracted from the current stroke, wherein

the stroke recognition features describe the current stroke with variable degrees of hierarchical approximations the hierarchical approximations including multiple scalar representations of the current stroke and including the direction string indicating, for points along the line of the stroke, the direction of movement of the line of the stroke at each point.

24. The method for recognizing handwritten characters of claim 23 wherein the stroke recognition features further include:

the coordinates of at least the beginning and end points of the line of the stroke.

25. The method for recognizing handwritten characters of claim 23 wherein the stroke recognition features firther include:

an array of coordinates of all points along the line of the stroke as received as input coordinates from the tablet.

29. The method for recognizing handwritten characters of claim 17 wherein the stroke feature recognizer is responsive to the stroke recognition features for assigning a meaning to each current stroke and further comprising the steps of:

storing the strokes of a current cluster of strokes in the time order of their entry,

storing the strokes of a preceding cluster of strokes,

storing a contiguous group of strokes of the current cluster of strokes in spatial order according to the coordinates of the strokes of the group,

constructing an influence list containing an identification of an area of influence of each stroke of the current cluster of strokes,

receiving a current stroke,

determining an area of influence of the current stroke, and

when the area of influence of the current stroke indicates that the current stroke is a part of the current cluster of strokes,

writing the current stroke into the current cluster of strokes, and

when the area of influence of the current stroke indicates that the current stroke is not a part of the current cluster of strokes,

transferring the strokes of the current cluster of strokes into the preceding cluster of stroke, and

writing the current stroke into a new current cluster of strokes,

scanning the influence list, and

writing the strokes of the current stoke buffer into the spatially ordered contiguous group of strokes,

storing plurality of cluster meanings,

each cluster meaning representing a cluster of strokes and a

corresponding meaning assigned to the cluster of strokes,

reading combinations of strokes from the spatially ordered contiguous group of strokes,

comparing the combinations of strokes from the spatially ordered contiguous group of strokes with the cluster meanings,

determining when a combination a strokes from the spatially ordered contiguous group of strokes corresponds to a cluster meaning,

providing as an output an identification of the cluster meaning corresponding to the combination of strokes from the spatially ordered contiguous group of strokes,

removing the combination of strokes from the spatially ordered contiguous group of strokes, and

transferring the combination of strokes from the current cluster of strokes to the preceding cluster of strokes.

31. The method for recognizing handwritten characters of claim 29 wherein the new stroke is an editing gesture, firther comprising the step of:

responsive to the editing gesture, modifying the strokes stored in the current and

preceding clusters of strokes as indicated by the editing gesture.

26. In a data processing system including a tablet and pen for user entry of handwritten characters and a processing unit connected from the tablet and pen for operating upon the user input, a method for recognizing handwritten characters. comprising the steps of:

storing stroke descriptor information of a current stroke in a stroke buffer as the current stroke is entered by the user,

responsive to the pen states, transferring the stroke descriptor information of the current stroke into a point buffer,

extracting stroke recognition features from the stroke descriptor information of the current stroke and assigning a meaning to the current stroke, and

recognizing and assigning a character meaning to a current cluster of strokes, including

reading the stroke recognition features from the stroke recognition feature data structure,

generating a plurality of scaled topological representations of the current stroke,

each scaled topological representation being a progressively smoothed representation of the current stroke generated from the stroke representation features,

selecting a scaled topological representation of the current stroke, the scaled topological representation of the current stroke being selected to provide the maximum signal to noise ratio of the stroke representation,

storing a list of ideal prototype representations corresponding to possible meanings of the current stroke from a plurality of ideal prototype representations of strokes,

comparing the scaled topological representation of the current stroke and boundaries of the ideal prototype representations of the list of ideal prototype representations wherein the boundaries of the ideal prototype representations are determined by linear combinations of features of the ideal prototype representations, and

assigning to the current stroke an identification of an ideal prototype representation having boundaries including the scaled topological representation of the current stroke, the assigned identification of the matching ideal prototype representation representing a stroke meaning assigned to the current stroke.

27. The method for recognizing handwritten characters of claim 26, further comprising the steps of:

storing the stroke recognition features extracted from the current stroke, wherein

the stroke recognition features describe the current stroke with variable degrees of hierarchical approximation, and include

the direction string indicating, for points along the line of the stroke, the direction of movement of the line of the stroke at each point.

28. The method for recognizing handwritten characters of claim 27, further comprising the step of:

generating, for each ideal prototype representation, a corresponding reversed ideal prototype representation having a reversed direction string for use in the comparison of features of the topological representations of the current stroke and of the ideal prototype representations.

30. The method for recognizing handwritten characters of claim 28, further comprising the step of:

responsive to a current stroke having spatial coordinates located between strokes which are previous in time,

reordering the strokes in the current and preceding clusters of strokes to accommodate the current stroke,

rewriting the strokes of the current cluster of strokes into the spatially ordered contiguous group of strokes in a corresponding new spatial order, and

determining a new cluster meaning from the new combinations of strokes in the spatially ordered contiguous group of strokes.

32. The method for recognizing handwritten characters of claim 28 wherein a combination of two consecutive strokes comprises an editing command, further comprising the steps of:

responsive to the combination of two consecutive strokes comprising an editing command,

providing an output indicating the editing command, andmprising the steps of;

modifying the strokes stored in the current and preceding clusters of strokes as indicated by the editing command.