Methods and apparatus for evolving a starter set of handwriting prototypes into a user-specific set

• US 5,319,721 A
• Filed: 04/14/1992
• Issued: 06/07/1994
• Est. Priority Date: 04/14/1992
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chefalas, Thomas E., Tappert, Charles C.
• Primary Examiner(s): Razavi, Michael T.
• Assistant Examiner(s): KLOCINSKI, STEVEN
• Application Number:
  US07/868,369
• Time in Patent Office: 784 Days
• Field of Search: 382/3, 382/13, 382/14, 382/15, 382/10, 382/24, 382/16, 382/37, 382/39, 395/20, 395/23
• US Class Current: 382/160
• CPC Class Codes: G06F 18/28 Determining representative reference patterns, e.g. by averaging or distorting; Generating dictionaries

Abstract

A method for use in a handwriting recognition system, and apparatus for accomplishing the method, that generates a User set of prototype symbols. The method includes the steps of (a) inputting one or more strokes for representing a predetermined symbol; and (b) comparing characteristics of the inputted strokes to stroke characteristics associated with one or more predetermined Starter prototype symbols. If the stroke characteristics match to within a predetermined threshold, the method further includes a step of (c) averaging the characteristics of the inputted stroke or strokes with the characteristics of a corresponding one or ones of the strokes of the matching one of the Starter prototype symbols to form a User prototype symbol. Further steps include (d) storing the User prototype symbol for subsequent use; and (e) deleting one or more Starter prototype symbols of the same label as the input symbol. If the stroke characteristics do not match, the method further includes the steps of (f) storing the characteristics of the one or more inputted strokes as the User prototype symbol for subsequent use; and (g) deleting the one or more Starter prototype symbols. A counter is maintained and deletes the Starter set only after a predetermined number of instances of the symbol have been entered by the user.

Claims

1. A method of generating a User-specific set of prototype symbols for use in a symbol recognition system, comprising the steps of:

(a) inputting an instance of a symbol to be recognized, the symbol having an identifying label;

(b) comprising characteristics of the inputted symbol to members of a set comprised of Starter prototype symbols each having an associated identifying label;

if the characteristics of the inputted symbol match characteristics associated with one or more Starter prototype symbols, to within a predetermined threshold,

(c) combining the characteristics of the inputted symbol with the characteristics of a best matching one of the Starter prototype symbols that has a same identifying label as the identifying label of the inputted symbol, the step of combining operating to form a User prototype symbol having a same identifying label as the identifying label of the inputted symbol;

(d) storing the User prototype symbol for subsequent use; and

(e) deleting those Starter prototype symbols having the same identifying label as the User prototype symbol;

otherwise, if the characteristics of the inputted symbol do not match characteristics associated with the one or more predetermined Starter prototype symbols, to within the predetermined threshold,

(f) storing the inputted symbol as a User prototype symbol for subsequent use, the stored User prototype symbol having the same identifying label as the inputted symbol; and

(g) deleting those Starter prototype symbols having the same identifying label as the User prototype symbol.

2. A method as set forth in claim 1 wherein each of the steps of deleting includes the initial steps of:

incrementing a counter means that is associated with each individual one of the Starter prototype symbols that has a same identifying label as the identifying label of the inputted symbol;

comparing a value of the counter means to a predetermined value; and

if the value of the counter means is less than the predetermined value, repeating step (a) to input one or more strokes for representing another instance of the predetermined symbol or an instance of another predetermined symbol, and performing step (b), and steps (c) and (d) or step (f), without deleting the one or more Starter prototype symbols;

otherwise, if the value of the counter means is equal to the predetermined value, performing the step (e) or (g) of deleting the one or more Starter prototype symbols.

3. A method as set forth in claim 1 wherein the step of combining includes a step of averaging the characteristics of the inputted symbol with the characteristics of a best matching one of the Starter prototype symbols that has a same identifying label as the identifying label of inputted symbol.

4. A method as set forth in claim 3 wherein the step of averaging employs a weighted average so as to more heavily weight a contribution of the characteristics of the best matching one of the prototype symbols to the resulting User prototype symbol.

5. A method as set forth in claim 1 wherein the step of inputting includes a step of generating one or more strokes by a movement of a stylus relative to an electronic tablet, and wherein the inputted symbol is comprised of one or more strokes.

6. A method as set forth in claim 5 wherein the step of comparing includes an initial step of performing an elastic matching technique between the stroke or strokes of the inputted symbol and a stroke or strokes of individual ones of the Starter prototype symbols.

7. Apparatus for generating a User-specific set of prototype symbols for use in a symbol recognition system, comprising:

means for inputting an instance of a symbol to be recognized, the symbol having an identifying label;

means for comparing characteristics of the inputted symbol to a set of prototype symbols comprised of Starter prototype symbols, each of the Starter prototype symbols having an associated identifying label;

combining means, responsive to a condition wherein the characteristics of the inputted symbol match characteristics associated with one or more Starter prototype symbols, to within a predetermined threshold, for combining the characteristics of the inputted symbol with the characteristics of a best matching one of the Starter prototype symbols that has a same identifying label as the identifying label of the inputted symbol, said combining means operating to form a User prototype symbol having the same identifying label as the identifying label of the inputted symbol;

means, responsive to said combining means forming a User prototype symbol, for storing the formed User prototype symbol within the set of prototype symbols for subsequent use;

said storing means being further responsive to a condition wherein said combining means does not form A User prototype symbol because the characteristics of the inputted symbol do not match characteristics associated with the one or more predetermined Starter prototype symbols, to within the predetermined threshold, for instead storing the inputted symbol within the set of prototype symbols as a User prototype symbol for subsequent use, wherein a stored User prototype symbol has a same identifying label as the inputted symbol; and

means for deleting from the set of prototype symbols those Starter prototype symbols having the same identifying label as the User prototype symbol.

8. Apparatus as set forth in claim 7 wherein said deleting means includes;

means for incrementing first counter means that is associated with each individual one of the Starter prototype symbols that has a same identifying label as the identifying label of the inputted symbol; and

means for comparing a value of the first counter means to a first predetermined value; and

wherein

said deleting means is responsive to the comparing means operation for deleting the one or more Starter prototype symbols only if the value of the associated first counter means is equal to the first predetermined value.

9. Apparatus as set forth in claim 7 wherein said combining means includes means for averaging the characteristics of the inputted symbol with the characteristics of the best matching one of the Starter prototype symbols that has a same identifying label as the identifying label of an inputted symbol.

10. Apparatus as set forth in claim 9 wherein said averaging means employs a weighted average so as to more heavily weight a contribution of the characteristics of the best matching one of the Starter prototype symbols to the resulting User prototype symbol.

11. Apparatus as set forth in claim 7 wherein said inputting means includes means for generating stroke information in response to a movement of a stylus relative to an electronic tablet, and wherein the inputted symbol is represented by information expressive of one or more strokes.

12. Apparatus as set forth in claim 11 wherein said comparing means includes means for performing an elastic matching technique between a stroke or strokes of the inputted symbol and a stroke or strokes of individual ones of the Starter prototype symbols.

13. Apparatus as set forth in claim 8 and further comprising:

second counter means that is associated with each individual one of the User prototype symbols for counting occurrences of the associated User prototype symbol being combined with an inputted symbol;

second comparing means for comparing a value of a second counter means to a second predetermined value; and

wherein

said combining means is responsive to the second comparing means operation for combining a User symbol prototype with an inputted symbol only if the value of the second counting means associated with the User symbol prototype is less than the second predetermined value.

14. A method of generating a User-specific set of handwriting prototype symbols for use in a handwriting recognition system, comprising the steps of:

establishing a prototype set S having as elements a plurality of predetermined Starter prototype symbols, each Starter prototype symbol having an associated identifying label;

inputting instances of training symbols T, each training symbol T having an associated identifying label;

for each instance of T, performing the steps of,

matching the instance of T to the elements of S to obtain a Match List comprised of prototype symbols and corresponding scores, each score being indicative of a difference between the instance of T and the corresponding prototype symbol;

reducing the Match List to form a Reduced Match List in accordance with one or more criteria, wherein the Reduced Match List is comprised of from zero to a plurality of prototype symbols, each prototype symbol having a corresponding prototype symbol in the prototype set S;

processing the Reduced Match List to generate a User prototype symbol for inclusion within the prototype set S, the User prototype symbol having an associated identifying label; and

removing from the prototype set S any Starter prototype symbols having a same label as the label of the instance of T.

15. A method as set forth in claim 14, wherein the step of reducing reduces the Match List by removing entries having a score that is greater than a first predetermined threshold.

16. A method as set forth in claim 14, wherein the step of processing includes a step of comparing the instance of T to elements of the Reduced Match List to identify one of the following cases:

an Empty case wherein the Reduced Match List does not contain a prototype symbol having a same label as the instance of T;

a Found_-- Alone case wherein the Reduced Match List contains a single prototype symbol having a same label as the instance of T;

a Found_-- Best case wherein the Reduced Match List contains a plurality of prototype symbols, and wherein a prototype symbol having a score that indicates a best match with the instance of T has a same label as the instance of T; and

a Found_-- Not_-- Best case wherein the Reduced Match List contains a plurality of prototype symbols including at least one prototype symbol having a same label as the instance of T, and wherein a prototype symbol having a score that indicates a best match with the instance of T has a different label than the instance of T.

17. A method as set forth in claim 16 wherein for the Empty case, the method includes a step of adding the instance of T to the prototype set S marked as a User prototype symbol.

18. A method as set forth in claim 16 wherein for the Found_-- Alone case, the method includes the steps of:

combining the instance of T with the single prototype in the Reduced Match List;

replacing the corresponding symbol prototype in the prototype set S with the combined prototype symbol; and

marking the combined prototype symbol in the prototype set S as a User prototype symbol.

19. A method as set forth in claim 16 wherein for the Found_-- Best case, the method includes the steps of:

combining the instance of T with the prototype symbol in the Reduced Match List that has the score that indicates a best match with the instance of T;

matching the instance of T with the combined prototype symbol and determining a score for the combined prototype symbol;

comparing the score of the combined prototype symbol with the score of the prototype symbol in the Reduced Match List that has the score that indicates a best match with the instance of T; and

if the score of the combined prototype symbol is less than the score of the prototype symbol in the Reduced Match List that has the score that indicates a best match with the instance of T, replacing the corresponding prototype symbol in the prototype set S with the combined prototype symbol and marking the replaced prototype symbol in S as a User prototype symbol;

else

marking the corresponding prototype symbol in the prototype set S as a User prototype symbol.

20. A method as set forth in claim 16 wherein for the Found_-- Not_-- Best case, the method includes the steps of:

combining the instance of T with the prototype symbol in the Reduced Match List that has the same label as the instance of T;

matching the instance of T with the combined prototype symbol and determining a score for the combined prototype symbol;

comparing the score of the combined prototype symbol with the score of a prototype symbol in the Reduced Match List having the score that indicates a best match with the instance of T; and

if the score of the combined prototype symbol is less than the score of the prototype symbol in the Reduced Match List having the score that indicates a best match with the instance of T, replacing the corresponding prototype symbol in the prototype set S with the combined prototype symbol and marking the replaced prototype symbol in S as a User prototype symbol;

else

adding the instance of T to the prototype set S as a User prototype symbol.

21. A method as set forth in claim 19 wherein the step of combining the instance of T with the prototype symbol in the Reduced Match List includes an initial step of comparing a value of a counter means that is associated with the corresponding prototype symbol in the prototype set S to a predetermined value, wherein the steps of combining, matching, and comparing are executed only if the value of the counter means is less than the predetermined value;

and wherein the step of replacing the corresponding prototype symbol in the prototype set S with the combined prototype symbol includes a step of incrementing the counter means that is associated with the replaced prototype symbol.

22. A method as set forth in claim 20 wherein the step of combining the instance of T with the prototype symbol in the Reduced Match List includes an initial step of comparing a value of a counter means that is associated with the corresponding prototype symbol in the prototype set S to a predetermined value, wherein the steps of combining, matching, and comparing are executed only if the value of the counter means is less than the predetermined value;

and wherein the step of replacing the corresponding prototype symbol in the prototype set S with the combined prototype symbol includes a step of incrementing the counter means that is associated with the replaced prototype symbol.

23. A method as set forth in claim 22 wherein if the step of comparing a value of the counter means to a predetermined value indicates that the value of the counter means is equal to or greater than the predetermined value, the method includes a step of adding the instance of T to the prototype set S as a User prototype symbol.

24. A method as set forth in claim 14 and further including a step of, for each instance of T, incrementing a counter means associated with all Starter prototype symbols in the prototype set S that have a same label as the instance of T, and wherein the step of removing from S any Starter prototype symbols having a same label as the label of the instance of T includes a step of comparing a value of the counter means to a predetermined value, and wherein the step of removing is executed only if the value of the counter means is equal to the predetermined value.

25. A method as set forth in claim 15, wherein the step of reducing the Match List includes a step of removing any entries marked as a Starter prototype symbol.