Training an on-line handwriting recognizer

• US 20040213455A1
• Filed: 05/18/2004
• Published: 10/28/2004
• Est. Priority Date: 02/25/2003
• Status: Active Grant

• Current Assignee: Bending Spoons SpA
• Original Assignee: Parascript, LLC
• Inventors: Bagotskaya, Natalia, Lossev, Ilia
• Granted Patent: US 7,382,921 B2
• Time in Patent Office: Days
• US Class Current: 382/159
• 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 trained for on-line recognizer of handwritten text to optimize the correct recognition percentage of the recognizer, the method comprising:

creating 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 the word recognition error for each sample word;

calculating the gradient of the word recognition error as function of the adjustable parameters;

calculating a work set recognition error gradient;

adjusting the adjustable parameters of the character model graphs to update the set of adjustable parameters to provide an updated set;

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

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

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 act of adjusting adjusts the parameters based on the work set recognition error gradient.

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

retrieving a plurality of best answers for sample word;

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

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 the act of calculating a work set recognition error gradient comprises:

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

5. The method of claim 4 wherein the act of adjusting adjusts the parameters based on the work set recognition error gradient.

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

7. The method of claim 1 further comprises:

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

8. The method of claim 7 said act of iterating is performed a predetermined number of times and the act of selecting further comprises:

searching the recognition error values saved by the act of saving for the optimum value;

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

9. A system for optimizing the character model graphs in a character recognition system comprising:

a first recognition module recognizing sample words from a work set using character model graphs defined by a parameter set, the first recognition module generating a work set recognition error function for the work set;

a second recognition module in response to the work set recognition error function adjusting the parameters in the parameter set, recognizing test words from a test set with character model graphs using the parameter set, and generating a correct recognition value for the test set based on correct recognition of words in the test set; and

an iteration module repeatedly executing the first recognition module and the second recognition module with the parameter set, the parameter set being adjusted for each iteration so that when the correct recognition value reaches an optimum value the character model graphs will be optimized.

10. The system of claim 9 wherein the work set recognition error function is a gradient function and 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 performs 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 performs 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 module evaluating the word recognition error for a sample word in the work set;

a word error module calculating the rate of change of the word recognition error with a change in the parameter set; and

a work set error module calculating the average rate of change of word recognition error for the work set to provide the work set recognition error function.

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 act of repeating in the computer process further comprises:

saving the updated parameter set as the current parameter set for use by the act of recognizing words from a first set.

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

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

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 by the act of 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 by the act of recognizing words from the second set.

20. The computer readable medium of claim 15 wherein the act of recognizing words in the first set in the computer process 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 of reference characters for use by a character recognizer, the method comprising:

creating 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 all of the above acts for each reference character whereby character model graphs for the reference characters are created 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. The method of claim 21 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 21 wherein the act of 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 21 wherein the act of merging each character shape model graph further comprises:

recalculating 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 21 further 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 the acts of recognizing words in the first set, adjusting the parameters and 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.