On-line handwriting recognizer

• US 20040165777A1
• Filed: 02/25/2003
• Published: 08/26/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,174,043 B2
• Time in Patent Office: Days
• 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 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.

2. The method of claim 1 wherein said act of describing comprises:

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 typical shape for 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 2 wherein said act of describing further comprises:

calculating a pen lift portion of the trajectory that the edge represents, the pen lift 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 a lift value indicative of the pen lift portion.

4. The method of claim 1 further comprises:

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 the act of evaluating comprises:

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

6. The method of claim 1 further comprises:

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

7. The method of claim 6 wherein the act of creating comprises:

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 typical shape, orientation, and lift;

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

8. 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 identifying 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 graphing 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 describing each edge based on the shape, orientation and air percentage of the trajectory segment associated with the edge; and

an evaluation module evaluating 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.

9. The system of claim 8 wherein said characters are alphanumeric characters and symbols.

10. The system of claim 8 wherein said graph module comprises:

a node assign module finding all singular points in an input character and assigning a node to each singular point;

an edge assign module creating multiple order edge candidates between nodes;

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

a reject module rejecting complex edge candidates and removing the complex edge candidates leaving the remaining edge candidates as the edges between nodes in the input graph.

11. The system of claim 10 wherein said evaluating module comprises

a load module loading model graphs for evaluation against the input graph;

pair path evaluating module computing 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 repeating 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.

12. The system of claim 11 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, orientation, and air percentage and where said path evaluating module comprises:

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.

13. The system of claim 12 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.

14. 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:

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 pen lift of the edge trajectory that the edge represents;

evaluating the input graph against model 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 and identifying the input character as an answer character represented by the model graph.

15. The computer readable medium of claim 14 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.

16. The computer readable medium of claim 14 wherein the act of describing during the computer process comprises:

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 a pen lift value (k) as the air percentage out of the two dimensional plane of the input character of the edge trajectory associated with the edge.

17. The computer-readable medium of claim 16 wherein the act of evaluating during the computer process comprises:

loading model graphs of all reference characters where 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 and edges between nodes representative of an edge trajectory formed by the sequence of points of the reference character between the singular points, and further each edge of the model graph includes an “

i”

vector, a “

j”

vector and a “

k”

vector for each edge in the model graph, the “

i,j,k”

vectors indicating similarity values for the edge trajectory, associated with the edge of the reference character, to typical shapes, a particular shape rotation and a particular air percentage, 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; and

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.

18. The computer-readable medium of claim 17 wherein the act of evaluating during the computer process further comprises:

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.

19. The computer-readable medium of claim 17 wherein the “

i,j,k”

vectors are “

i,j,k”

tables of similarity values indexed by “

i,j,k”

values respectively and the act of sequentially evaluating during the computer process comprises;

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.

20. The computer-readable medium of claim 19 wherein the computer process further comprises:

creating a form model graph for each reference character form;

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

building the “

i,j,k”

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

adjusting the similarity values in the “

i,j,k”

tables to minimize recognition error.

21. The computer-readable medium of claim 20 wherein the act of adjusting during the computer process further comprises:

providing a test input graph for a test character;

evaluating the test input graph against the model graph;

vary similarity values in “

i,j,k”

tables to establish an average change for each similarity value;

adjust similarity values;

test for optimum final answer; and

repeating test until final answer is optimum.