Method and apparatus for character recognition of handwritten input

• US 5,742,705 A
• Filed: 08/28/1997
• Issued: 04/21/1998
• Est. Priority Date: 06/05/1995
• Status: Expired due to Term

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Kannan Parthasarathy
• Inventors: Parthasarathy, Kannan
• Primary Examiner(s): Mancuso, Joseph
• Application Number:
  US08/919,875
• Time in Patent Office: 236 Days
• Field of Search: 382/185, 382/186, 382/187, 382/188, 382/189, 382/209, 382/218, 178/18, 178/19, 178/70
• US Class Current: 382/185
• CPC Class Codes: G06V 30/1801 Detecting partial patterns, e.g. edges or contours, or configurations, e.g. loops, corners, strokes or intersections extracting features by contour coding G06V30/182
• CPC Class Codes: G06V 30/2504 Coarse or fine approaches, e.g. resolution of ambiguities or multiscale approaches

Abstract

A method and apparatus for recognition of handwritten input is disclosed where handwritten input composed of a sequence of (x, y, pen) points, is preprocessed into a sequence of strokes. A short list of candidate characters that are likely matches for the handwritten input is determined by finding a fast matching distance between the input sequence of strokes and a sequence of strokes representing each candidate character of a large character set where the sequence of strokes for each candidate character is derived from statistical analysis of empirical data. A the final sorted list of candidate characters which are likely matches for the handwritten input is determined by finding a detailed matching distance between the input sequence of strokes and the sequence of strokes for each candidate character of the short list. A final selectable list of candidate characters is presented to a user.

Claims

1. A method of recognizing a handwritten symbol comprising the steps of:

(A) receiving a handwritten input as a sequence of (x, y, pen)points where x and y are coordinates in a two dimensional coordinate system and pen is a binary value indicating an associated pen-down state;

(B) converting the sequence of points into a sequence of strokes, each stroke representing a basic unit used to construct any handwritten symbol in a vocabulary;

(C) determining a shortlist of candidate symbols in the vocabulary that are likely matches for the input by finding a fast matching distance between the input sequence of strokes and the sequence of strokes for each symbol in the vocabulary, said sequence of strokes for each symbol in the vocabulary being derived from statistical analysis on samples of the handwritten symbols; and

(D) determining a final sorted list of candidate symbols in the vocabulary that are likely matches for the input by finding a minimum dynamic programming matching distance between the input sequence of strokes and the sequence of strokes for each symbol in the shortlist of candidate symbols in the vocabulary that are likely matches for the handwritten input.

2. The method of claim 1, further comprising the steps of computing a dynamic programming match path and calculating a weighted sum of inter-stroke distances along the dynamic programming match path to find the final sorted list of candidate symbols in the vocabulary that are likely matches for the handwritten input.

3. The method of claim 1, further comprising the step of providing a selectable list of one or more candidate characters having the highest likelihood of corresponding to the handwritten input.

4. The method of claim 3, wherein the number of candidate characters of the selectable list is variable.

5. The method of claim 3, wherein the number of candidate characters of the selectable list is determined by a user.

6. The method of claim 3, wherein the number of candidate characters of the selectable list is ten.

7. The method of claim 3, wherein the handwritten input is displayed and the at least one candidate character is displayed simultaneously.

8. The method of claim 3, wherein the handwritten input is displayed and said selectable list of candidate characters is displayed simultaneously.

9. An apparatus for recognizing a handwritten symbol comprising;

(A) a digitizing tablet for receiving handwritten input, said handwritten input having a sequence of (x, y, pen) points where x and y coordinates are in a two dimensional coordinate system and pen is a binary value indicating an associated pen-up/pen-down state;

(B) a memory for storing an input sequence of strokes, said sequence of strokes representing the sequence of points, each stroke representing a basic unit used to construct at least one handwritten symbol of a character set;

(C) a processor for generating a shortlist of candidate symbols the character set that most likely represent the input by finding a fast matching distance between the input sequence of strokes and a sequence of strokes representing each symbol in a vocabulary, said sequence of strokes representing each symbol in the vocabulary being derived from statistical analysis of a plurality of samples of handwritten symbols; and

(D) a processor for generating a final sorted list of candidate symbols of the vocabulary which most likely represents the handwritten input by finding a detailed matching distance between the input sequence of strokes and the sequence of strokes for each symbol in the said shortlist of candidate symbols in the vocabulary that most likely represents the handwritten input.

10. The apparatus of claim 9, further comprising a display having a selectable list of one or more candidate characters having the highest likelihood of corresponding to the handwritten input.

11. The apparatus of claim 10, wherein the number of candidate characters of the selectable list is variable.

12. The apparatus of claim 10, wherein the number of candidate characters of the selectable list is determined by a user.

13. The apparatus of claim 10, wherein the number of candidate characters of the selectable list is ten.

14. The apparatus of claim 10, wherein the handwritten input is displayed and the selectable list is displayed simultaneously.

15. The apparatus of claim 10, wherein the handwritten input is displayed and said selectable list of candidate characters is displayed simultaneously.

16. A method of recognizing handwritten input comprising the steps of:

receiving handwritten input;

preprocessing the handwritten input to represent a string of strokes;

analyzing the handwritten input by matching of the string of strokes and a sequence of strokes for a plurality of symbols in a vocabulary to provide a shortlist of candidate characters which most likely correspond to the handwritten input;

accessing a plurality of reference templates corresponding to only the candidate characters of the shortlist and comparing the handwritten input with at least one of said reference templates to identify at least one candidate character most likely to represent said handwritten input.

17. A method of recognizing handwritten input comprising the steps of:

analyzing handwritten input to provide a plurality of candidate characters that most likely represent the handwritten input by finding a fast matching distance between an input sequence of strokes and a sequence of strokes for each symbol in a vocabulary of characters;

accessing a plurality of reference templates corresponding to the candidate characters and comparing the handwritten input with at least one of said reference templates to identify at least one of the candidate characters that most likely represents said handwritten input by finding a detailed matching distance between the input sequence of strokes and a sequence of strokes for each one of said reference templates;

providing a selectable list of a plurality of candidate characters, said list having candidate characters having the highest likelihood of corresponding to the handwritten input.

18. The method of claim 17, wherein the handwritten input has been preprocessed to represent a string of strokes.

19. The method of claim 17, wherein the number of candidate characters of the selectable list is variable.

20. The method of claim 17, wherein the number of candidate characters of the selectable list is determined by a user.

21. The method of claim 17, wherein the number of candidate characters of the selectable list is ten.

22. The method of claim 17, wherein the handwritten input is displayed juxtaposed at least one candidate character.

23. The method of claim 17, wherein the handwritten input is displayed in close juxtaposed said selectable list of candidate characters.

24. A method of recognizing handwritten input comprising the steps of:

analyzing a preprocessed sequence of strokes representing handwritten input to provide a short list of a plurality of candidate characters having a likelihood of corresponding to said preprocessed handwritten input;

analyzing said handwritten input and said short list of said plurality of candidate characters by comparison of each of said sequence of strokes of the handwritten input with at least one reference template having a sequence of strokes corresponding to each of said plurality of candidate characters in said short list;

providing a selectable list of at least one candidate character, said list of candidate characters having the highest likelihood of corresponding to the handwritten input.

25. A method of recognizing handwritten input comprising the steps of:

receiving preprocessed handwritten input as a sequence of strokes;

providing a shortlist of at least one of a plurality of candidate characters, by comparison of said handwritten input with a plurality of reference templates, each of said templates having a sequence of strokes representing a corresponding candidate character;

providing, by selection from said shortlist, a selectable list of at least one of a plurality of candidate characters, said list of candidate characters having the highest likelihood of corresponding to the handwritten input.

26. An apparatus for recognizing handwritten input comprising;

a memory for storing preprocessed handwritten input as a sequence of strokes;

a processor generating a shortlist of candidate characters, said shortlist generated by fast matching of said preprocessed handwritten input with a plurality of reference templates, each of said templates having a sequence of strokes representing a corresponding candidate character;

a processor generating a selectable list of at least one of a plurality of candidate characters, by detailed matching of said preprocessed handwritten input with reference templates for said shortlist of candidate characters, whereby said selectable list of candidate characters has the highest likelihood of corresponding to the handwritten input.

27. A method of recognizing a handwritten symbol comprising the steps of:

receiving a handwritten input as a sequence of (x, y, pen)points where x and y are coordinates in a two dimensional coordinate system and pen is a binary value indicating an associated pen-down state;

converting the sequence of points into a sequence of strokes, each stroke representing a basic unit used to construct any handwritten symbol in a vocabulary;

parametizing each stroke using a four dimensional vector having an x coordinate of the midpoint of the stroke, a y coordinate of the midpoint of the stroke, a length representing the length of the stroke, and an angle representing the angle of the stroke with respect to a reference axis.

determining a shortlist of candidate symbols in the vocabulary that are likely matches for the input by finding a fast matching distance between the input sequence of strokes and the sequence of strokes for each symbol in the vocabulary, said sequence of strokes for each symbol in the vocabulary being derived from statistical analysis on samples of the handwritten symbols; and

determining a final sorted list of candidate symbols in the vocabulary that are likely matches for the input by finding a detailed matching distance between the input sequence of strokes and the sequence of strokes for each symbol in the shortlist of candidate symbols in the vocabulary that are likely matches for the handwritten input.

28. A method of recognizing a handwritten symbol comprising the steps of:

providing a vocabulary of handwritten symbols, each symbol represented as a sequence of strokes, each stroke representing a basic unit used to construct any handwritten symbol in the vocabulary, said sequence of strokes for each symbol in the vocabulary being derived from statistical analysis on samples of the handwritten symbols;

receiving a handwritten input as a sequence of (x, y, pen) points where x and y are coordinates in a two dimensional coordinate system and pen is a binary value indicating an associated pen-down state;

converting the sequence of points into a sequence of strokes;

parametizing each stroke using a vector having an x coordinate of the midpoint of the stroke, a y coordinate of the midpoint of the stroke, a length representing the length of the stroke, and an angle representing the angle of the stroke with respect to a reference axis;

associating different weighting values to different strokes, said weighting values being derived from statistical analysis on a plurality of handwritten symbols;

determining a list of candidate symbols in the vocabulary that are likely matches for the input by finding a matching distance between the input sequence of strokes and the sequence of strokes for each symbol in the vocabulary, taking account of the weighting values.

29. The method of claim 28, further comprising calculating a stroke distance between two or more straight line strokes such that the stroke distance is equivalent to

30. A method, comprising the steps of:

receiving handwritten input as data representing a sequence of strokes;

determining a shortlist of a plurality of candidate symbols from stored templates that are likely matches for the handwritten input by comparing one or more stroke parameters between the sequence of strokes representing the handwritten input and the sequence of strokes for a plurality of symbols from the templates; and

determining one or more recognized symbols that are likely matches for the handwritten input by comparing two or more stroke parameters between the sequence of strokes representing the handwritten input and the sequence of strokes for each symbol in the shortlist that are likely matches for the handwritten input.

31. A method, comprising the steps of:

processing handwritten input as a sequence of handwritten strokes to provide data representing a sequence of straight strokes;

determining a shortlist of a plurality of candidate symbols from stored templates that are likely matches for the handwritten input by comparing one or more stroke parameters between the sequence of straight strokes representing the handwritten input and the sequence of strokes for a plurality of symbols from the templates; and

determining one or more recognized symbols that are likely matches for the handwritten input by comparing two or more stroke parameters between the sequence of straight strokes representing the handwritten input and the sequence of strokes for each symbol in the shortlist that are likely matches for the handwritten input.

32. A method, comprising the steps of:

receiving handwritten input as data representing a sequence of strokes;

determining an angle parameter for each of the sequence of strokes, the angle parameter representing an angle of the stroke from a reference axis;

determining a shortlist of a plurality of candidate symbols from stored templates that are likely matches for the handwritten input by comparing the angle parameter between the sequence of strokes representing the handwritten input and the sequence of strokes for a plurality of symbols from the templates; and

determining one or more recognized symbols that are likely matches for the handwritten input by comparing other stroke parameters between the sequence of strokes representing the handwritten input and the sequence of strokes for each symbol in the shortlist that are likely matches for the handwritten input.

33. A method, comprising the steps of:

receiving handwritten input as data representing a sequence of strokes;

determining stroke parameters for each of the sequence of strokes, the stroke parameters selected from the group of parameters consisting of;

an angle parameter representing an angle of the stroke from a reference axis;

a x coordinate midpoint parameter representing the x coordinate of the midpoint of the stroke;

a y coordinate midpoint parameter representing the y coordinate of the midpoint of the stroke;

a length parameter representing stroke length;

determining a plurality of candidate symbols from stored templates that are likely matches for the handwritten input by comparing one stroke parameter between the sequence of strokes representing the handwritten input and the sequence of strokes for a plurality of symbols from the templates; and

determining one or more recognized symbols that are likely matches for the handwritten input by comparing two or more stroke parameters between the sequence of strokes representing the handwritten input and the sequence of strokes for each symbol in the plurality of candidate symbols that are likely matches for the handwritten input.

34. An apparatus, comprising

a digitizing tablet for receiving handwritten input as a sequence of strokes;

a memory having data and instructions stored therein and having a plurality of templates representing characters or symbols some of which may correspond to the handwritten input;

a processor for processing the data or instructions in the memory to provide a shortlist of a plurality of candidate symbols by comparing at least one stroke parameter between the sequence of strokes representing the handwritten input and a sequence of strokes for one or more characters or symbols in the memory, and for providing a selectable plurality of recognized symbols by comparing two or more stroke parameters between the sequence of strokes representing the handwritten input and the sequence of strokes for each of the plurality of candidate symbols of the shortlist.

35. A method of recognizing a handwritten symbol comprising the steps of:

(A) receiving a handwritten input as a sequence of (x, y) points where x and y are coordinates in a two dimensional coordinate system;

(B) converting the sequence of points into a sequence of strokes, each stroke representing a basic unit used to construct any handwritten symbol in a vocabulary;

(C) determining a shortlist of candidate symbols in the vocabulary that are likely matches for the input by finding a fast matching distance between the input sequence of strokes and the sequence of strokes for each symbol in the vocabulary, said sequence of strokes for each symbol in the vocabulary being derived from statistical analysis on samples of the handwritten symbols, said step of determining a shortlist including comparing a difference between a number of strokes in an input sequence of strokes and a number of strokes in a template with a threshold; and

(D) determining a final sorted list of candidate symbols in the vocabulary that are likely matches for the input by finding a minimum dynamic programming matching distance between the input sequence of strokes and the sequence of strokes for each symbol in the shortlist of candidate symbols in the vocabulary that are likely matches for the handwritten input.

36. A method of recognizing a handwritten symbol comprising the steps of:

(A) receiving a handwritten input as a sequence of (x, y) points where x and y are coordinates in a two dimensional coordinate system;

(B) converting the sequence of points into a sequence of strokes, each stroke representing a basic unit used to construct any handwritten symbol in a vocabulary;

(C) determining a shortlist of candidate symbols in the vocabulary that are likely matches for the input by finding a fast matching distance between first and second sets of strokes, where one of the first and second sets of strokes is the input sequence of strokes and the other is the sequence of strokes for each symbol in the vocabulary, said sequence of strokes for each symbol in the vocabulary being derived from statistical analysis on samples of the handwritten symbols, said step of finding a fast matching distance including calculating distances between a stroke in one of the sets of strokes and neighboring strokes in the other of the sets of strokes; and

(D) determining a final sorted list of candidate symbols in the vocabulary that are likely matches for the input by finding a minimum dynamic programming matching distance between the input sequence of strokes and the sequence of strokes for each symbol in the shortlist of candidate symbols in the vocabulary that are likely matches for the handwritten input.