On-line handwriting recognizer

• US 7,174,043 B2
• Filed: 02/25/2003
• Issued: 02/06/2007
• Est. Priority Date: 02/25/2003
• Status: Active Grant

• Current Assignee: Bending Spoons SpA
• Original Assignee: Evernote Corp. (Bending Spoons SpA)
• Inventors: Lossev, Ilia, Bagotskaya, Natalia
• Primary Examiner(s): MARIAM, DANIEL G
• Application Number:
  US10/374,482
• Publication Number:
  US 20040165777A1
• Time in Patent Office: 1,442 Days
• Field of Search: 382/159, 382/173, 382/181, 382186-188, 382/199, 382201-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

A character recognizer recognizes a handwritten input character. A sequence of points in two dimensional space representative of a stroke trajectory forming the input character is gathered. An input Directed Acyclic Graph is built with nodes representative of singular points at the beginning, end, and along the trajectory of the input character and with edges between nodes representative of an edge trajectory formed by the sequence of points of the input character between the singular points. Each edge in the input graph is described based on the shape, orientation and pen lift of the edge trajectory that the edge represents. The input graph is evaluated against model graphs, which are also Directed Acyclic Graphs, for all possible characters to find a path through a model graph that produces a best path similarity score with a corresponding path through the input graph. The input character is identified as an answer character represented by the model graph producing the best path similarity score. Each model graph for a reference character has nodes representative of singular points at the beginning, end, and along the stroke trajectory of the reference character. Edges between nodes in the model graph are representative of an edge trajectory formed by the sequence of points of the reference character between the singular points. Further each edge of the model graph has an “i” vector, a “j” vector and a “k” vector, and the “i,j,k” vectors indicate similarity values associated with the edge trajectory of the reference character and typical shapes, shape rotation and pen lift, respectively.

Claims

1. A method for recognizing an input handwritten character digitized as a sequence of coordinate points in two dimensional space representative of a trajectory making up an input character, the method comprising:

gathering the sequence of points for the input character;

building an input graph with nodes representative of significant points along the trajectory of the input character and with edges between nodes representative of the trajectory formed by the sequence of points of the input character between the significant points;

describing each edge in the input graph based on the shape and orientation of the trajectory that the edge represents, wherein describing each edge includes determining, for each described edge of the input graph, a character-part shape from one or more codebooks that is closest to a portion of the trajectory represented by that edge;

describing individual edges in one or more model graphs based on a similarity of a given edge in the model graph to multiple shapes in the one or more codebooks;

evaluating the input graph against the one or more model graphs, using the described edges of the input graph and the model graph, for all possible characters to find a model graph having the most similar path to a path of the input graph and identifying the input character as an answer character represented by the model graph with the most similar path.

2. The method of claim 1, wherein determining, for each described edge of the input graph, a character-part shape from a codebook includes:

selecting, from the one or more codebooks, a typical rotation-independent shape for the portion of the trajectory that the edge represents;

assigning to the edge a shape value representative of the typical shape;

measuring an orientation of the portion of the trajectory that the edge represents;

and assigning to the edge a rotation value indicative of the orientation of the shape.

3. The method of claim 1, wherein determining, for each described edge of the input graph, a character-part shape from a codebook includes:

calculating an air portion of the trajectory that the edge of the input graph represents, the air portion being that portion of the trajectory where the pen is lifted off of the two dimensional space of the input character, and

assigning to the edge an air percentage value indicative of the air portion.

4. The method of claim 1, further comprising:

identifying the significant points of the trajectory of the input character based on the rate of curvature of each of the points in the sequence of points making up the character.

5. The method of claim 1, wherein evaluating the input graph against the one or more model graphs includes:

finding corresponding best paths through the input graph and model graph based on the similarity of edges along the corresponding paths.

6. The method of claim 1, further comprising:

creating a model graph for each character against which the input graph is evaluated to find an answer character.

7. The method of claim 1, wherein gathering the sequence of points for the input character includes receiving any one of a cursive or mixed handwriting character set.

8. The method of claim 1, further comprising:

building a 3-dimensional trajectory by (i) connecting a last point of each stroke in the input trajectory and a first point of the next stroke by a segment comprising one or more artificial air points, and (ii) assigning a zero value of a third coordinate to original points and a non-zero value of a third coordinate to the one or more air points; and

wherein building an input graph with nodes representative of significant points along the trajectory includes building the input graph with nodes that are representative of significant points along the 3-dimensional trajectory.

9. The method of claim 1, wherein describing each edge in the input graph includes describing each edge (i) as a first shape from a shape codebook, the first shape from the codebook being closest to the trajectory represented by said edge;

(ii) as a first orientation from an orientation codebook, the first orientation being closest to the trajectory represented by said edge;

(iii) as a given air percentage value from an air percentage codebook, the given air percentage value being closest to a trajectory represented by said edge.

10. The method of claim 9, wherein describing individual edges in one or more model graphs includes identifying a shape similarity vector, an orientation similarity vector and an air percentage similarity vector for a given model graph, wherein, together the vectors indicate a similarity of each edge of the model graph to a shape, an orientation, and an air percentage of each typical letter part from a codebook.

11. The method of claim 10, wherein evaluating the input graph against the one or more model graphs includes computing an edge pair similarity score as a sum of the shape similarity value, the orientation similarity value, and the air percentage similarity value for each of the one or more model graphs.

12. The method of claim 1, wherein describing individual edges in one or more model graphs includes:

creating a predetermined number of typical trajectories for each character;

merging input graphs for typical trajectories of one character into one model graph with edges described by one or more parameters, so as to create a compressed generalized description of a set of typical trajectories for each character;

determining a set of similarity vectors based at least in part on the one or more parameters, wherein the set of similarity vectors are characterized by coordinate values that are adjustable to minimize mis-recognition.

13. A method for recognizing an input handwritten character digitized as a sequence of coordinate points in two dimensional space representative of a trajectory making up the input character, the method comprising:

gathering the sequence of points for the input character;

building an input graph with nodes representative of significant points along the trajectory of the input character and with edges between nodes representative of the trajectory formed by the sequence of points of the input character between the significant points;

describing each edge in the input graph based on the shape and orientation of the trajectory that the edge represents;

evaluating the input graph against model graphs for all possible characters to find a model graph having the most similar path to a path of the input graph and identifying the input character as an answer character represented by the model graph with the most similar path;

creating a model graph for each character against which the input graph is evaluated to find an answer character;

creating a form model graph for each character form;

merging form model graphs into a model graph for all character forms of the same character;

describing edges of each model graph based on similarity to multiple typical shapes, orientations, and lifts;

adjusting similarity values of all edges for optimum recognition of input characters.

14. The method of claim 13, wherein describing each edge in the input graph includes:

selecting a typical rotation-independent shape for the trajectory that the edge represents and assigning to the edge a shape value representative of the typical shape; and

measuring an orientation of the trajectory that the edge represents and assigning to the edge a rotation value indicative of the orientation of the trajectory.

15. The method of claim 13, wherein describing each edge in the input graph includes:

calculating an air portion of the trajectory that the edge represents, the air portion being that portion of the 3-dimensional trajectory where the pen is lifted off of the two dimensional space of the input character, and

assigning to the edge an air percentage value indicative of the air portion.

16. The method of claim 13, further comprising:

identifying the significant points of the trajectory of the input character based on the rate of curvature of each of the points in the sequence of points making up the character.

17. The method of claim 13, wherein the evaluating the input graph includes:

finding corresponding best paths through input graph and model graph based on the similarity of edges along the corresponding paths.

18. The method of claim 13, wherein gathering the sequence of points for the input character includes receiving any one of a cursive or mixed handwriting character set.

19. A system for recognizing handwritten characters based on trajectory segments of one or more strokes making up each character, the system comprising:

a find module that is configured to identify singular points of each character trajectory defining a beginning point and end point of each stroke of the character and points of significant curvature along each stroke of the character, wherein the character trajectory corresponds to any one of a cursive or mixed handwriting character set;

a graph module that is configured to graph each character as an input graph made up of nodes connected by edges in which each node corresponds to a singular point, each edge corresponds to one or more trajectory segments connecting two singular points;

an edge definition module that is configured to describe each edge based on the shape, orientation and air percentage value of the trajectory segment associated with the edge; and

an evaluation module that is configured to evaluate the input graph against all model graphs of a set of reference characters to identify the model graph of a reference character most similar to the input character.

20. The system of claim 19, wherein said characters include alphanumeric characters and symbols.

21. The system of claim 19, wherein said graph module comprises:

a node assign module that is configured to find all singular points in an input character and assigning a node to each singular point;

an edge assign module that is configured to create multiple order edge candidates between nodes;

an edge complexity test module that is configured to test the complexity of each edge; and

a reject module that is configured to reject complex edge candidates and removing the complex edge candidates leaving the remaining edge candidates as the edges between nodes in the input graph.

22. The system of claim 21, wherein said evaluating module comprises:

a load module that is configured to load model graphs for evaluation against the input graph;

pair path evaluating module that is configured to compute the similarity score between edges making up a path in the input graph and edges making up a path in the model graph;

said pair path evaluating module being configured to repeat the computing operation for the input graph against paths in all model graphs until locating the best path similarity score so as to identify the character most similar to the input character.

23. The system of claim 22, wherein each edge of a model graph includes a shape vector, an orientation vector and an air percentage vector, so that together the vectors indicate the similarity of each edge of the model graph to predefined shapes, orientations, and air percentages and where said path evaluating module is configured to perform steps comprising:

computing an edge pair similarity score indicative of the similarity of the edge in the input graph and the corresponding edge in the model graph; and

computing a path similarity score indicative of the similarity of all the edges along a path in the input graph to all corresponding edges along the pair path in the model graph.

24. A system for recognizing handwritten characters based on trajectory segments of one or more strokes making up each character, the system comprising:

a find module that is configured to identify singular points of each character trajectory defining a beginning point and end point of each stroke of the character and points of significant curvature along each stroke of the character;

a graph module that is configured to graph each character as an input graph made up of nodes connected by edges where each node corresponds to a singular point, each edge corresponds to one or more trajectory segments connecting two singular points;

an edge definition module that is configured to describe each edge based on the shape, orientation and air percentage value of the trajectory segment associated with the edge; and

an evaluation module that is configured to evaluate the input graph against all model graphs of a set of reference characters to identify the model graph of a reference character most similar to the input character;

wherein said graph module comprises;

a node assign module that is configured to find all singular points in an input character and assigning a node to each singular point;

an edge assign module that is configured to create multiple order edge candidates between nodes;

an edge complexity test module testing the complexity of each edge; and

a reject module that is configured to reject complex edge candidates and removing the complex edge candidates leaving the remaining edge candidates as the edges between nodes in the input graph;

wherein said evaluating module comprises;

a load module that is configured to load model graphs for evaluation against the input graph;

a pair path evaluating module that is configured to compute the similarity score between edges making up a path in the input graph and edges making up a path in the model graph;

said pair path evaluating module being configured to repeat the computing operation for the input graph against paths in all model graphs until locating the best path similarity score so as to identify the character most similar to the input character;

wherein each edge of a model graph includes a shape vector, an orientation vector and an air percentage vector, together the vectors indicate the similarity of each edge of the model graph to predefined shapes, orientations, and air percentage values and wherein said path evaluating module is configured to perform steps comprising;

computing a edge pair similarity score indicative of the similarity of the edge in the input graph and the corresponding edge in the model graph; and

computing a path similarity score indicative of the similarity of all the edges along a path in the input graph to all corresponding edges along the pair path in the model graph;

where said path evaluating module further comprises;

reducing the path similarity score for a unbalanced pair path where one path of the pair has more edges than the other path of the pair; and

varying correspondence between edge pairs in an unbalanced pair path until all variants of edge pairs for the unbalanced pair path have been evaluated for a path similarity score.

25. A computer readable medium readable by a computing system and encoding a computer program of instructions for executing a computer process for recognizing a handwritten input character, said computer process comprising steps that include:

gathering a sequence of points in two dimensional space representative of a trajectory forming the input character;

building an input graph with nodes representative of singular points at the beginning, end, and along the trajectory of the input character and with edges between nodes representative of an edge trajectory formed by the sequence of points of the input character between the singular points;

describing each edge in the input graph based on the shape, orientation and air lift of the edge trajectory that the edge represents, wherein describing each edge includes determining, for each described edge of the input graph, a character-part shape from one or more codebooks that is closest to a portion of the trajectory represented by that edge;

describing individual edges in one or more model graphs based on a similarity of a given edge in the model graph to multiple shapes in the one or more codebooks;

evaluating the input graph against one or more model graphs, using the described edges of the input graph and the model graph, for all possible characters to find a path through a model graph that produces a best path similarity score with a corresponding path through the input graph and identifying the input character as an answer character represented by the model graph.

26. The computer readable medium of claim 25, wherein the computer process further comprises:

examining each point in the sequence of points making up the trajectory of the input character;

marking as singular points, the beginning point and the end point of each stroke of the input character;

detecting a curvature rate for each examined point along the sequence of points, the curvature rate indicating the rate of change of direction of a stroke of the input character at the examined point; and

marking as singular points each examined point whose curvature rate exceeds a predetermined threshold value.

27. The computer readable medium of claim 25, wherein the step of describing each edge in the input graph includes:

smoothing each edge trajectory;

selecting a rotation-invariant shape value (i) for each edge based on the edge trajectory associated with the edge;

measuring a rotation value (j) for each edge based on the rotation of the shape of the edge trajectory associated with the edge; and

computing an air percentage value (k) as the length percentage of the air portion of the 3-dimensional trajectory of the input character associated with the edge.

28. The computer-readable medium of claim 27, wherein the step of evaluating the input graph includes:

loading model graphs of different characters where each model graph for a character is a generalized description of several input graphs created for several pre-selected trajectories of this character, and where each edge of the model graph corresponds to a part of the character, and further each edge of the model graph includes an “

i”

vector, a “

j”

vector and a “

k”

vector, the “

i,j,k”

vectors indicating similarity values for the character part, associated with the edge of the model graph, to typical shapes, typical orientations and typical air percentages, respectively;

setting a pair path, one path each in the input graph and a model graph, for evaluation of corresponding edge pairs along the two paths;

sequentially evaluating each edge pair along the pair path based on the “

i,j,k”

values of the edge in the input graph and the “

i,j,k”

vectors in the model graph to provide an edge similarity value for each edge pair;

summing the edge similarity values for all edge pairs along the pair path and generating a pair path similarity value;

repeating the acts of setting, sequentially evaluating and summing until all selected pair paths for the input graph and all model graphs have been evaluated; and

selecting an answer character for the input character based on the model graph producing the best pair path similarity value with the input graph.

29. The computer-readable medium of claim 28, wherein the step of evaluating the input graph includes:

subtracting a penalty for a skipped edge from the sum of edge similarity values, when the path in the input graph and the path in the model graph do not have the same number of edges, to generate the path similarity value;

setting correspondence of edge pairs to another skipped edge variation for the pair path; and

repeating the acts of sequentially evaluating, summing edge similarity values, subtracting a penalty, and setting correspondence, until all skipped edge variations of the pair path have been evaluated.

30. The computer-readable medium of claim 28, wherein the “

i,j,k”

vectors are “

i,j,k”

tables of similarity values indexed by “

i,j,k”

values respectively and the step of sequentially evaluating the input graph includes;

looking up the “

i”

th entry in the “

i”

table of an edge in the model graph to retrieve a similarity value for the shape value “

i”

of a corresponding edge in the input graph;

looking up the “

j”

th entry in the “

j”

table of the edge in the model graph to retrieve a similarity value for the rotation value “

j”

of the corresponding edge in the input graph;

looking up the “

k”

th entry in the “

k”

table of the edge in the model graph to retrieve a similarity value for the lift value “

k”

of the corresponding edge in the input graph; and

summing the similarity values retrieved from the “

i,j,k”

tables to generate the edge similarity value.

31. The computer-readable medium of claim 30, wherein the computer process further comprises steps that include:

creating an input graph for each reference trajectory of a character;

merging created input graphs for all reference trajectories representing the same character into a model graph for this character;

building the “

i,j,k”

tables for each edge in the model graph for the reference character; and

adjusting the similarity values in the “

i,j,k”

tables to minimize recognition error.

32. The computer-readable medium of claim 31, wherein the step of adjusting the similarity values include:

providing a test input graph for a test character;

evaluating the test input graph against the model graph;

adjust similarity values in “

i,i,k”

tables to minimize recognition error;

repeating above steps for all test input graphs and averaging change for each similarity value; and

repeating above process until final answer is optimum.

33. A method for recognizing an input handwritten character digitized as a sequence of coordinate points in two dimensional space representative of a trajectory making up the input character, the method comprising the acts of:

gathering the sequence of points for the input character;

building an input graph with nodes representative of significant points along the trajectory of the input character and with edges between nodes representative of the trajectory formed by the sequence of points of the input character between the significant points;

describing each edge in the input graph based on the shape and orientation of the trajectory that the edge represents;

evaluating the input graph against model graphs for all possible characters to find a model graph having the most similar path to a path of the input graph and identifying the input character as an answer character represented by the model graph with the most similar path;

creating a model graph for each character against which the input graph is evaluated to find an answer character

wherein describing each edge in the input graph includes calculating an air portion of the trajectory that the edge represents, the air portion being that portion of the trajectory where the pen is lifted off of the two dimensional space of the input character, and assigning to the edge an air percentage value indicative of the air portion.

34. The method of claim 33, wherein gathering the sequence of points for the input character includes receiving any one of a cursive or mixed handwriting character set.