Recognition graph

• US 20060239560A1
• Filed: 02/28/2006
• Published: 10/26/2006
• Est. Priority Date: 02/28/2005
• Status: Active Grant

• Current Assignee: Cerence Operating Company (Cerence Inc.)
• Original Assignee: Zi Decuma AB
• Inventors: Sternby, Jakob
• Granted Patent: US 7,756,335 B2
• Time in Patent Office: Days
• US Class Current: 382/187
• CPC Class Codes: G06V 30/2272 with lexical matching
• CPC Class Codes: G06V 30/347 Sampling; Contour coding; Stroke extraction

Abstract

A method for determining at least one recognition candidate for a handwritten pattern comprises selecting possible segmentation points in the handwritten pattern for use in segmenting and recognizing the handwritten pattern. The method further may comprise comparing segments of the handwritten pattern to templates. The comparison may return segment candidates forming possible recognition results of the segments of the handwritten pattern. The method further comprises forming a representation of sequences of segment candidates, said representation comprising data blocks corresponding to segmentation points, wherein a data block comprises references to data blocks corresponding to subsequent segmentation points. The reference may comprise information of segment candidates. The method further may comprise comparing the representation of the sequences of segment candidates to a dictionary, finding sequences of segment candidates that correspond to allowed sequences of symbols in the dictionary, and returning at least one of these allowed sequences of symbols as a recognition candidate for the handwritten pattern.

Claims

1. A method for determining at least one recognition candidate for a handwritten pattern comprising one or more curves and representing a plurality of symbols, said method comprising:

selecting possible segmentation points in the handwritten pattern for use in segmenting the handwritten pattern and recognizing these segments of the handwritten pattern as symbols,

comparing segments of the handwritten pattern to templates representing a symbol or a part of a symbol, wherein a segment of the handwritten pattern corresponds to a sequence of possible segmentation points from a first segmentation point to a second segmentation point, said comparison returning segment candidates associated to templates forming possible recognition results of the segments of the handwritten pattern, each segment candidate being associated with a measure of the match between the template and the segment of the handwritten pattern,

forming a representation of sequences of segment candidates, said representation comprising data blocks corresponding to segmentation points in the handwritten pattern, wherein a data block comprises references to data blocks corresponding to subsequent segmentation points, the reference comprising information of segment candidates and associated measures for the segment of the handwritten pattern between the segmentation points,

comparing the representation of the sequences of segment candidates to a dictionary, said dictionary being represented as sequences of symbols, wherein a symbol in a sequence holds references to allowed following symbols,

finding sequences of segment candidates that correspond to allowed sequences of symbols in the dictionary, and

returning at least one of these allowed sequences of symbols as a recognition candidate for the handwritten pattern.

2. The method according to claim 1, wherein said comparing of the representation of the sequences of segment candidates to a dictionary comprises looking forward in the sequence of segmentation points.

3. The method according to claim 1, wherein an accumulated measure of matching between a sequence of segment candidates and the handwritten pattern is used for determining a ranking order between the recognition candidates.

4. The method according to claim 1, wherein said forming of a representation of sequences of segment candidates comprises forming a recognition graph having nodes and edges, wherein each node represents a possible segmentation point and each edge represents a path along a sequence of segmentation points from one node to another node, said path corresponding to a possible symbol in the handwritten pattern and being associated with at least one measure corresponding to a matching between a segment candidate and the segment of the handwritten pattern.

5. The method according to claim 4, wherein said forming of a representation comprises allowing only a determined number of segment candidates ending in one node.

6. The method according to claim 5, wherein the determined number may be adjusted for controlling speed of the comparing the representation of sequences of segment candidates to the dictionary.

7. The method according to claim 5, wherein the allowed segment candidates are the segment candidates having best measure of matching.

8. The method according to claim 4, wherein the forming of the recognition graph comprises discarding doublets of paths corresponding to the same sequences of symbols between the same nodes.

9. The method according to claim 4, wherein the dictionary is represented as a Trie-graph.

10. The method according to claim 9, wherein said comparing of the representation of sequences of segment candidates to a dictionary comprises stepping through the nodes of the recognition graph and comparing these nodes to nodes in the Trie-graph.

11. The method according to claim 10, wherein said comparing comprises creating references from the edges in the recognition graph representing a segment candidate to corresponding nodes in the Trie-graph.

12. The method according to claim 10, wherein a sequence of segment candidates is discarded as soon as the sequence of segment candidates has no counterpart in the Trie-graph during the stepping through the nodes in the recognition graph.

13. The method according to claim 10, wherein said comparing of nodes in the recognition graph to nodes in the Trie-graph comprises checking the possible number of symbols in the rest of the sequence of segment candidates to allowed numbers of following symbols in the Trie-graph.

14. The method according to claim 1, wherein a sequence of segment candidates corresponding to an incomplete sequence of symbols in the dictionary is allowed.

15. The method according to claim 1, wherein an omitted segment in the handwritten pattern resulting in a missing segment candidate in the sequence of segment candidates is recognized by matching a segment candidate to a non-corresponding symbol in the dictionary and adding a penalty to the measure associated with the segment candidate.

16. The method according to claim 1, wherein the measure of a match is a calculated distance value of the discrepancy between features of the handwritten pattern and corresponding features of the template.

17. The method according to claim 1, wherein the handwritten pattern is written in cursive writing.

18. The method according to claim 1, wherein the handwritten pattern is detected on-line.

20. A computer readable memory device having stored thereon instructions that are executable by a computer, the instructions being capable of causing a computer to execute a method according to claim 1.

19. A device for determining at least one recognition candidate for a handwritten pattern comprising one or more curves and representing a plurality of symbols, said device comprising:

means for selecting possible segmentation points in the handwritten pattern for use in segmenting the handwritten pattern and recognizing these segments of the handwritten pattern as symbols,

means for comparing segments of the handwritten pattern to templates representing a symbol or a part of a symbol, wherein a segment of the handwritten pattern corresponds to a sequence of segmentation points from a first possible segmentation point to a second possible segmentation point, said comparison returning segment candidates for templates forming possible recognition results of the segments of the handwritten pattern, each segment candidate being associated with a measure of the match between the template and the segment of the handwritten pattern,

means for forming a representation of sequences of segment candidates, said representation comprising data blocks corresponding to segmentation points in the handwritten pattern, wherein a data block holds references to subsequent segmentation points, the reference holding information of segment candidates and associated measures for the segment of the handwritten pattern between the segmentation points,

means for comparing the representation of the sequences of segment candidates to a dictionary, said dictionary being represented as sequences of symbols, wherein a symbol in a sequence holds references to allowed following symbols,

means for finding sequences of segment candidates that correspond to allowed sequences of symbols in the dictionary, and

means for returning at least one of these allowed sequences of symbols as a recognition candidate for the handwritten pattern.