Constraint driven-on line recognition of handwritten characters and symbols

• US 5,029,223 A
• Filed: 02/02/1990
• Issued: 07/02/1991
• Est. Priority Date: 02/02/1990
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Fujisaki, Tetsunosuke
• Primary Examiner(s): Moore, David K.
• Assistant Examiner(s): Santos, Dan
• Application Number:
  US07/474,271
• Time in Patent Office: 515 Days
• Field of Search: 382/13, 382/24, 382/37
• US Class Current: 382/187
• CPC Class Codes: G06V 30/196 using sequential comparisons of the image signals with a plurality of references
• CPC Class Codes: G06V 30/2268 using stroke segmentation

Abstract

Method and apparatus for identifying a valid symbol or a string of valid symbols from a sequence of handwritten strokes. A method includes the steps of (a) generating in response to one or more handritten strokes a plurality of stroke labels each having an associated score; (b) processing the plurality of stroke labels in accordance with a beam search-like technique to identify those stroke labels indicative of a valid symbol or portion of a valid symbol; and (c) associating together identified stroke labels to determine an identity of a valid symbol or a string of valid symbols therefrom. An aspect of the invention is that each of the constraint validation filters is switchably coupled into a serial filter chain. The switches function to either couple a filter input to a stroke label or decouple the input and provide a path around the filter block. An application writer has available a plurality of constraint filters. The application writer specifies which one or ones of the constraint filters are to be applied for a specific sequence of strokes.

Claims

1. A method for identifying a valid symbol or a string of valid symbols from a sequence of handwritten strokes comprising the steps of:

generating, in response to one or more handwritten strokes, a plurality of stroke labels each having an associated score; and

processing the plurality of stroke labels to identify stroke labels indicative of a valid symbol or portion of a valid symbol, the step of processing including the steps of

storing the stroke labels within a data structure by order of score, the data structure storing all or a portion of all paths through a search space defined by the plurality of stroke labels; and

reading a path from the data structure, extending the path with possible successor paths, and merging the extended paths back into the data structure as a function of score.

2. A method as set forth in claim 1 wherein the step of generating includes an initial step of inputting x-y coordinate data from an electronic tablet means, the x-y coordinate data being indicative of a handwritten stroke.

3. A method as set forth in claim 1 wherein the step of extending includes a step of evaluating the path with at least one constraint validation filter.

4. A method as set forth in claim 1 wherein the step of processing further includes the steps of:

1.) reading a top path from the data structure;

2.) extending the top path with all possible successor stroke labels to form one or more extended paths;

3.) merging the extended paths into the search space as a function of score; and

4.) repeating from step (1.) until an end of input condition is reached.

5. A method as set forth in claim 1 wherein the step of processing further includes the steps of:

1.) removing a top path from the data structure;

7. A method as set forth in claim 5 wherein as a result of the execution of Step 1.7 a plurality of possible results are obtained, including:

(a) the constraint validation filter eliminates the top path when the path violates the constraint represented by the constraint validation filter;

(b) the constraint validation filter penalizes the score associated with the top path; and

(c) the constraint validation filter validates the top path such that the score associated with the top path is unchanged.

8. A method as set forth in claim 4 wherein the step of merging includes a step of providing a pointer to another entry in the data structure.

9. A method as set forth in claim 5 wherein the steps of merging each include a step of providing a pointer to another entry in the data structure.

10. A method as set forth in claim 1 wherein the step of processing includes an initial step of specifying for use one or more constraint validation filters selected from the group consisting of dictionary constraint filters, syntactic constraint filters, semantic constraint filters, stroke topology constraint filters, n-gram constraint filters and variations and combinations thereof.

12. Apparatus as set forth in claim 10 wherein the means for generating includes means for inputting x-y coordinate data from an electronic tablet means, the x-y coordinate data being indicative of a handwritten stroke.

13. Apparatus as set forth in claim 10 wherein the means for processing includes at least one constraint validation filter means.

14. Apparatus as set forth in claim 10 wherein the means for processing further comprises:

means for reading a top path from the data structure;

means for extending the top path with all possible successor stroke labels to form one or more extended paths; and

means for merging the extended paths back into the data structure as a function of score.

15. Apparatus as set forth in claim 13 and further including one or more constraint validation filters switchably coupled in series between the extending means and the merging means and wherein the means for extending is comprised of:

means for extending a younger sister path from a parent of the top-path;

means for merging the younger sister path back into the data structure as a function of score;

means for directing the top path through the at least one constraint validation filter; and

means for extending the top path with a most probable one of the paths returned from the constraint validation filter.

16. Apparatus as set forth in claim 14 wherein the at least one constraint validation filter is selected from the group consisting of dictionary constraint filters, syntactic constraint filters, semantic constraint filters, stroke topology constraint filters, n-gram constraint filters and variations and combinations thereof.

18. A method as set forth in claim 16 wherein the step of storing within a second data structure includes a step of storing within a stack data structure all or a portion of all paths through a search space defined by the plurality of stroke labels.

20. A method as set forth in claim 18 and including a step of merging a processed stroke label into the stack data structure at a position that is a function of a modified score of the processed stroke label.

22. A method as set forth in claim 16 wherein the step of processing includes an initial step of specifying for use one or more constraint validation filters selected from the group consisting of dictionary constraint filters, syntactic constraint filters, semantic constraint filters, stroke topology constraint filters, n-gram constraint filters and variations and combinations thereof.

23. A method as set forth in claim 16 wherein the step of storing the stroke labels within a first data structure includes a step of forming a linked list of stroke labels associated with each handwritten stroke.

24. A method as set forth in claim 1 wherein the step of generating a plurality of stroke labels includes the steps of:

comparing a handwritten stroke to a plurality of stroke templates to identify a symbol or symbols of which the handwritten stroke may be a constituent; and

associating the handwritten stroke with a specific constituent stroke of each identified symbol.

25. A method as set forth in claim 23 wherein the associated score is assigned a value that is a function of a degree of correlation between the handwritten stroke and a stroke template corresponding to the identified symbol.

26. A method as set forth in claim 24 wherein the step of generating includes a step of ordering the stroke labels by order of associated score.

27. A method as set forth in claim 23 wherein the step of associating the handwritten stroke with a specific constituent stroke of each identified symbol includes a step of determining a stroke label having the form (m/nC), where C is the identified symbol, where m is indicative of a number of a specific stroke out of a sequence of strokes that comprise C, and wherein n is indicative of a total number of strokes in the sequence of strokes.

29. A method as set forth in claim 27 wherein the step of processing includes an initial step of storing the stroke labels within a data structure by order of score value, the data structure storing all or a portion of all paths through a search space defined by the stroke labels.

34. A method as set forth in claim 27 wherein the step of associating includes a step of generating a stroke label having the form (m/nC), where C is the identified symbol, where m is indicative of a number of a specific stroke out of a sequence of strokes that comprise C, and wherein n is indicative of a total number of strokes in the sequence of strokes.

6. 5) extending a younger sister path from a parent of the top-path;

1.6) merging the younger sister path back into the stack as a function or score;

1.7) sending the top path through at least one constraint validation filter;

if the top path survives the filter,

2.) extending the top path with the best one among candidates returned from the constraint validation filter;

3a.) merging the extended top path back into the data structure with an associated FLAG=OPEN;

3b.) merging the original top-path back into the data structure with an associated FLAG=CLOSED; and

4.) repeating the steps of the procedure from (1.) until an end of input condition is reached.

11. Apparatus for identifying a valid symbol or a string of valid symbols from a sequence of handwritten strokes comprising:

means for generating, in response to one or more handwritten strokes, a plurality of stroke labels each having an associated score; and

means for processing the plurality of stroke labels to identify stroke labels indicative of a valid symbol or portion of a valid symbol, the means for processing comprising

means for storing the stroke labels within a data structure by order of score, the data structure storing all or a portion of all paths through a search space defined by the plurality of stroke labels; and

means for reading a path from the data structure, means for extending the path with possible successor paths, and means for merging extended paths back into the data structure as a function of score.

17. A method for identifying a valid symbol or a string of valid symbols from a sequence of handwritten strokes comprising the steps of:

generating in response to one or more handwritten strokes a plurality of stroke labels each having an associated score;

storing the stroke labels within a first data structure; and

processing selected ones of the plurality of stored stroke labels with one or more constraint validation filter means to identify those stored stroke labels indicative of a valid symbol or portion of a valid symbol, the step of processing including a step of storing within a second data structure those stored stroke labels identified to be indicative of a valid symbol or portion of a valid symbol.

19. A method as set forth in claim 17 wherein the step of processing includes a step of inputting a selected one of the stored stroke labels to at least one of the constraint validation filter means, the step of inputting including a step of determining if the inputted stroke label is validated or invalidated by the at least one constraint validation filter means, and further includes a step of increasing the score associated with the inputted stroke label by an amount within a range of zero to some positive value, the amount being a function of whether the inputted stroke label is validated or invalidated by the constraint validation filter means.

21. A method as set forth in claim 19 wherein the step of merging includes a step of providing a pointer to another stroke label stored in the stack data structure.

28. A method for identifying a valid symbol from a sequence of handwritten strokes, for each handwritten stroke the method comprises the steps of:

comparing a handwritten stroke to a plurality of stroke templates to identify a symbol or symbols of which the handwritten stroke may be a constituent;

associating the handwritten stroke with a portion of each identified symbol to form a stroke label;

assigning a score to each stroke label, the score having a value that is a function of a degree of similarity between the handwritten stroke and the stroke template corresponding to the identified symbol;

ordering the stroke labels associated with the handwritten stroke by order of score; and

processing the stroke labels associated with the handwritten stroke by determining which stroke labels, if any, when combined with stroke labels associated with a subsequently written handwritten stroke, comprise a valid symbol or a portion of a valid symbol.

30. A method as set forth in claim 28 wherein the step of processing includes the steps of:

1.) reading a top path from the data structure;

2.) extending the top path with all possible successor stroke labels to form one or more extended paths;

3.) merging the extended paths into the search space as a function of score; and

4.) repeating from step (1.) until an end of input condition is reached.

31. A method for identifying a valid symbol from a sequence of handwritten strokes, for each handwritten stroke the method comprises the steps of:

comparing a handwritten stroke to a plurality of stroke templates to identify a symbol or symbols of which the handwritten stroke may be a constituent;

associating the handwritten stroke with a portion of each identified symbol to form a stroke label;

assigning a score to each stroke label, the score having a value that is a function of a degree of similarity between the handwritten stroke and the stroke template corresponding to the identified symbol;

ordering the stroke labels associated with the handwritten stroke by order of score; and

processing the stroke labels associated with the handwritten stroke by determining which stroke labels, if any, when combined with stroke labels associated with a subsequent handwritten stroke, comprise a valid symbol or a portion of a valid symbol,

wherein the step of processing includes an initial step of storing the stroke labels within a data structure by order of score value, the data structure storing all or a portion of all paths through a search space defined by the stroke labels, and wherein the step of processing includes the steps of;

32. ) removing a top path from the data structure;

1.5) extending a younger sister path from a parent of the top-path;

1.6) merging the younger sister path back into the data structure as a function of score;

1.7) sending the top path through at least one constraint validation filter;

if the top path survives the filter,

33. ) extending the top path with the best one among candidates returned from the constraint validation filter;

3a.) merging the extending top path back into the data structure with an associated FLAG=OPEN;

3b.) merging the original top-path back into the data structure with an associated FLAG=CLOSED; and

4.) repeating the steps of the procedure from (1.) until an end of input condition is reached.

35. Apparatus for identifying a valid symbol or a string of valid symbols from a sequence of handwritten strokes, comprising:

means for generating, in response to one or more handwritten strokes, a plurality of stroke labels each having an associated score;

means for storing the stroke labels within a first data structure; and

means for processing selected ones of the plurality of stored stroke labels with one more constraint validation filter means to identify stored stroke labels that are indicative of a valid symbol or portion of a valid symbol, the processing means including means for storing within a second data structure any stroke labels identified as being indicative of a valid symbol or portion of a valid symbol.