Training an on-line handwriting recognizer

• US 7,382,921 B2
• Filed: 05/18/2004
• Issued: 06/03/2008
• Est. Priority Date: 02/25/2003
• Status: Active Grant

• Current Assignee: Bending Spoons SpA
• Original Assignee: Evernote Corp. (Bending Spoons SpA)
• Inventors: Bagotskaya, Natalia, Lossev, Ilia
• Primary Examiner(s): MARIAM, DANIEL G
• Application Number:
  US10/848,650
• Publication Number:
  US 20040213455A1
• Time in Patent Office: 1,477 Days
• Field of Search: 382/159, 382/173, 382/181, 382186-188, 382/199, 382/201, 382202-203, 382/209, 382/218, 382/226, 382/229
• US Class Current: 382/187
• CPC Class Codes: G06V 30/1423 the instrument generating sequences of position coordinates corresponding to handwriting preprocessing or recognising digital ink G06V30/32
• CPC Class Codes: G06V 30/196 using sequential comparisons of the image signals with a plurality of references
• CPC Class Codes: G06V 30/228 of three-dimensional handwriting, e.g. writing in the air

Abstract

Character model graphs are created, and the parameters of the model graphs are adjusted to optimize character recognition performed with the model graphs. In effect the character recognizer using the model graphs is trained. The model graphs are created in three stages. First, a vector quantization process is used on a set of raw samples of handwriting symbols to create a smaller set of generalized reference characters or symbols. Second, a character reference model graph structure is created by merging each generalized form model graph of the same character into a single character reference model graph. The merging is based on weighted Euclidian distance between parts of trajectory assigned to graph edges. As a last part of this second stage “type-similarity” vectors are assigned to model edges to describe similarities of given model edge to each shape and to each possible quantized value of other input graph edge parameters. Thus, similarity functions, or similarity values, are defined by different tables on different model edges. In the third stage, model creation further consists of minimizing recognition error by adjusting model graphs parameters. An appropriate smoothing approximation is used in the calculation of similarity score between input graph and model graphs. The input graph represents a word from a work sample set used for training, i.e. adjusting the model graph parameters. A recognition error is calculated as a function of the difference between similarity scores for best answers and the one correct answer for the word being recognized. The gradient of the recognition error as a function of change in parameters is computed and used to adjust the parameters. Model graphs with adjusted parameters are then used to recognize the words in a test set, and a percent of correct recognitions in the test set is calculated. The recognition error calculation with the work set, the parameter adjustment process, and the calculation of the percent of correct recognitions with the test set is repeated. After a number of iterations of this process, the optimum set of parameters for the model graphs will be found.

Claims

1. A method for creating character model graphs for an on-line recognizer of handwritten text, the method comprising:

generating character model graphs from typical shapes of characters, the character model graphs having a set of adjustable parameters;

recognizing sample words in a work set using the character model graphs;

evaluating a recognition error for a sample word;

calculating a gradient of the recognition error;

adjusting the adjustable parameters of the character model graphs to provide an updated set of the adjustable parameters, based on at least one of the recognition error and the gradient of the recognition error;

recognizing test words in a test set using character model graphs with the updated set of adjustable parameters;

calculating a correct recognition value for the test set when using the model graphs with the updated set of adjustable parameters;

iterating the above sequence of acts until the correct recognition value reaches an optimum value; and

selecting the updated set of adjustable parameters yielding the correct recognition value having the optimum value as the set of adjustable parameters to be used in character model graphs.

2. The method of claim 1 wherein:

the recognition error includes a recognition error for the work set;

the gradient includes a gradient of the recognition error for the work set as a function of the adjustable parameters; and

the parameters are adjusted based on the gradient of the recognition error for the work set.

3. The method of claim 1 wherein evaluating the recognition error comprises:

retrieving one or more best answers for each sample word;

comparing recognition scores of the best answers to a recognition score of the correct answer for the sample word; and

generating a word recognition error based on the differences between recognition scores of the best answers relative to the recognition score of the correct answer.

4. The method of claim 3 wherein calculating the gradient of a the recognition error comprises:

calculating a gradient of the word recognition error; and

calculating the gradient of the recognition error for the work set by averaging the gradient of the word recognition error with gradients of word recognition errors of previous words in the work set recognized by the act of recognizing sample words.

5. The method of claim 4 wherein the parameters are adjusted based on the gradient of the recognition error for the work set.

6. The method of claim 1 wherein generating a correct recognition value comprises calculating the percentage of words in the test set where the best recognition answer is substantially same as the test word.

7. The method of claim 1 further comprises:

saving the recognition error value and the updated set of the adjustable parameters for each iteration.

8. The method of claim 7 wherein the iterating is performed a predetermined number of times, and selecting the updated set of adjustable parameters further comprises:

searching the saved recognition error values for the optimum value; and

retrieving the updated set of adjustable parameters saved with the recognition error value having the optimum value.

9. A system for optimizing character model graphs comprising:

a first recognition module to recognize sample words from a work set using character model graphs defined by a parameter set, the first recognition module is to generate recognition error information for the work set and to adjust the parameters in the parameter set based on the recognition error information;

a second recognition module coupled to the first recognition module, to recognize test words from a test set with character model graphs using the adjusted parameter set, and to generate a correct recognition value for the test set based on correct recognition of the test words in the test set; and

an iteration module coupled to the first and second recognition modules, to repeatedly execute the first recognition module and the second recognition module until the correct recognition value reaches an optimum value.

10. The system of claim 9 wherein the recognition error information for the work set is generated from a gradient function that indicates the change in error as a function of the change in parameters in the parameter set.

11. The system of claim 10 wherein the correct recognition value is a measure of the number of words in the test set correctly recognized during a given iteration.

12. The system of claim 9 wherein the iteration module is to perform iterations for a predetermined number of times sufficient for the correct recognition value to reach an optimum value.

13. The system of claim 9 wherein the iteration module is to perform iterations until the correct recognition value passes through an optimum value.

14. The system of claim 9 wherein the first recognition module comprises:

an evaluation sub-module to evaluate an recognition error for a sample word in the work set;

a word error sub-module coupled to the evaluation sub-module, to calculate the rate of change of the recognition error with a change in the parameter set; and

a work set error sub-module coupled to the evaluation sub-module and the word error sub-module, to calculate the average rate of change of the recognition error for the work set to provide a recognition error for the work set.

15. A computer readable medium for storing computer instructions for a computer process for training character model graphs to optimize the recognition of text by a recognizer using the character model graphs, the computer process comprising:

recognizing words from a first set of words using a current parameter set for the character model graphs and generating a recognition error gradient for the first set based on changes in the word recognition error as a function of changes in parameters in the current parameter set of the character model graphs;

adjusting the parameters of the character model graphs in response to the recognition error gradient to create an updated parameter set for the character model graphs;

recognizing words from a second set of words using the updated parameter set and generating a correct recognition value, the correct recognition value being associated with the updated parameter set for the character model graphs; and

repeating all of the above acts until the correct recognition value reaches a transition value and selecting the parameter set associated with the transition value as the optimum parameters for the character model graphs.

16. The computer readable medium of claim 15 wherein the repeating further comprises:

saving the updated parameter set as the current parameter set prior to recognizing words from a first set.

17. The computer readable medium of claim 16 wherein the repeating further comprises:

saving a correct recognition value in association with each updated parameter set; and

choosing an updated parameter set as an optimum parameter set when the associated correct recognition value represents a transition value.

18. The computer readable medium of claim 17 wherein the transition value is a maximum and the correct recognition value is a measure of correct answers when recognizing words from the second set.

19. The computer readable medium of claim 17 wherein the transition value is a minimum and the correct recognition value is a measure of mis-recognitions when recognizing words from the second set.

20. The computer readable medium of claim 15 wherein recognizing words in the first set comprises:

evaluating the word recognition error for a word in the first set;

calculating the rate of change of the word recognition error with a change in parameters between the current parameter set and a previous parameter set; and

calculating the average rate of change of the word recognition error for the first set to provide the recognition error gradient for the first set.

21. A method for creating character model graphs for a set of reference characters for use by a character recognizer, the method comprising:

determining a plurality of typical character shapes for a reference character;

creating a character shape model graph for each typical character shape of the reference character;

merging a plurality of the character shape model graphs for the reference character into a single character model graph by compressing data for the plurality of the character shape model graphs; and

repeating the determining, the creating and the merging for each reference character to create the character model graphs for the set of the reference characters for the character recognizer.

22. The method of claim 21 wherein the edges of each character model graph are defined by values in similarity vectors.

23. A method for creating character model graphs of reference characters for use by a character recognizer, the method comprising:

determining a predetermined number of typical character shapes for a reference character;

creating a character shape model graph for each typical character shape of the reference character;

merging all character shape model graphs for the reference character into a single character model graph; and

repeating the determining, the creating and the merging for each reference character to create character model graphs for the reference characters for use by the character recognizer,

wherein the edges of each model graph are described as a vectors of cosine coefficients.

24. The method of claim 23 further comprising:

converting the cosine coefficient vector for each edge of a character model graph into values in similarity vectors.

25. The method of claim 23 wherein creating typical character shapes comprises:

clustering all possible character shapes for a character into a predetermined number of clusters of similar shapes with each shape represented by a vector;

determining a center vector for each cluster; and

restoring a typical character shape for each cluster from the center vector for each cluster to create the predetermined number of typical character shapes for each character.

26. The method of claim 23 wherein merging each character shape model graph further comprises:

calculating the vector parameters of the character model graph to average the parameters of each character shape model graph, being merged with the character model graph, into the vector parameters for the character model graph.

27. The method of claim 26 wherein the vector parameters are cosine coefficients.

28. The method of claim 27 further comprising:

converting the cosine coefficient vector for each character model graph into a similarity vector.

29. The method of claim 23 further comprising:

recognizing words from a first set of words using a current parameter set for the character model graphs;

generating a recognition error gradient for the first set based on changes in the word recognition error as a function of changes in parameters in the current parameter set of the character model graphs;

adjusting the parameters of the character model graphs in response to the recognition error gradient to create an updated parameter set for the character model graphs;

recognizing words from a second set of words using the updated parameter set and generating a correct recognition value, the correct recognition value being associated with the updated parameter set for the character model graphs;

repeating the recognizing words in the first set, the adjusting the parameters and the recognizing words in the second set until the correct recognition value reaches an optimum value; and

selecting the parameter set associated with the optimum value as the optimum parameters for the character model graphs.