PRUNING AND LABEL SELECTION IN HIDDEN MARKOV MODEL-BASED OCR

• US 20150186756A1
• Filed: 12/31/2013
• Published: 07/02/2015
• Est. Priority Date: 12/31/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Fujii, Yasuhisa
• Granted Patent: US 9,189,708 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 18/295 Markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding Markov models
• CPC Class Codes: G06F 40/279 Recognition of textual entities
• CPC Class Codes: G06V 30/10 Character recognition

Abstract

Systems and techniques are provided for pruning a node from a possible nodes list for Hidden Markov Model with label transition node pruning. The node may be a label transition node. A frame may be at a predicted segmentation point in decoding input with the Hidden Markov Model. The node may be scored at the frame. The node may be pruned from the possible nodes list for the frame when score for the node is greater than the sum of a best score among nodes on the possible nodes list for the frame and a beam threshold minus a penalty term. A possible nodes list may be generated for a subsequent frame using label selection. A second node may be pruned from the possible nodes list for the subsequent frame with early pruning.

Claims

1. A computer-implemented method performed by a data processing apparatus, the method comprising:

receiving a node of a Hidden Markov Model, wherein the node is a label transition node;

receiving a frame, wherein the frame is a predicted segmentation point; and

pruning the node from a possible nodes list with label transition node pruning,

wherein label transition node pruning comprises;

scoring the node at the frame to obtain a score, and

pruning the node when the score is greater than the sum of a best score at the frame and a beam threshold minus a penalty term.

2. The computer-implemented method of claim 1, further comprising:

generating a possible nodes list for a subsequent frame to the frame using label selection by;

scoring a label at the subsequent frame to obtain a label score;

ranking the label based on the label score to obtain a label rank; and

adding a first node of the label to the possible nodes list for the subsequent frame when the label score is less than or equal to a sum of a best label score at the subsequent frame and a first parameter or the label rank is less than or equal to a second parameter.

3. The computer-implemented method of claim 2, wherein the label comprises a label name associated with a character from a character set.

4. The computer-implemented method of claim 2, wherein scoring the label at the subsequent frame comprises using fast-match.

5. The computer-implemented method of claim 2, wherein scoring the label at the subsequent frame comprises scoring the initial state of an optical model for the label at the subsequent frame.

6. The computer-implemented method of claim 5, further comprising:

storing the label score; and

reusing the label score during decoding of the subsequent frame.

7. The computer-implemented method of claim 2, wherein the first parameter and the second parameter are tunable parameters for label selection.

8. The computer-implemented method of claim 2, further comprising pruning a second node from the possible nodes list for the subsequent frame with early pruning, wherein early pruning comprises:

scoring the second node at the subsequent frame with at least one observation feature function to obtain an observation score; and

pruning the second node when an early pruning score is greater than a sum of the current best score at the subsequent frame and the beam threshold, wherein the previous node score is a score for a previous node to the second node at a previous frame to the subsequent frame, and wherein the early pruning score is the sum of the observation score and the previous node score.

9. The computer-implemented method of claim 8, wherein early pruning further comprises:

estimating a parameter based on at least one transition feature function; and

adding the parameter to the early pruning score.

10. The computer-implemented method of claim 8 further comprising pruning the second node with histogram pruning, wherein histogram pruning comprises:

pruning the second node if the second node does not have an exact pruning score that is at least the n-th best exact pruning score at the subsequent frame, where n is a tunable parameter.

11. The computer-implemented method of claim 1, wherein the Hidden Markov Model is one of a model for optical character recognition and a model for automated speech recognition.

12. The computer-implemented method of claim 1, wherein the frame is a segment of an image of text.

13. The computer-implemented method of claim 1, wherein the possible nodes list is used in time-synchronous Viterbi decoding.

14. The computer-implemented method of claim 1, wherein the predicted segmentation point is a character boundary.

15. The computer-implemented method of claim 1, wherein the node is a state in the Hidden Markov Model and comprises emissions and emission probabilities and is associated with transitions and transition probabilities.

16. The computer-implemented method of claim 1, wherein the penalty term is the product of a label transition penalty factor and the beam threshold, and wherein the label transition penalty factor has a value greater than or equal to 0 and less than or equal to 1.

17. The computer-implemented method of claim 1, wherein the possible nodes list comprises nodes of the Hidden Markov Model connected to nodes in a second possible nodes list for a previous frame.

18. A computer-implemented method performed by a data processing apparatus, the method comprising:

receiving an input comprising frames and for each frame of the input that is at a predicted segmentation point;

receiving a possible nodes list comprising nodes, wherein the nodes are label transition nodes;

pruning the nodes having a score greater than a sum of a score for a best scoring node at the frame and a beam threshold minus a penalty term;

generating a possible nodes list for a subsequent frame of the input comprising nodes that are connected to the nodes not pruned from the possible nodes and are first nodes for labels having a label score less than or equal to the sum of a score for a best scoring label at the subsequent frame and a first parameter or a label rank less than or equal to a second parameter; and

pruning nodes from the possible nodes list for the subsequent frame having a sum of an observation score for the node and a score for a previous node to the node at a previous frame to the subsequent frame greater than the sum of the score for the best scoring node at the subsequent frame and a beam threshold.

19. The computer-implemented method of claim 18, further comprising, for each frame:

decoding a portion of the frame with a Hidden Markov Model and the possible nodes list; and

generating a possible nodes list, for a next frame of the input, comprising nodes of the Hidden Markov Model connected to nodes not pruned from the possible nodes list and not removed during the decoding.

20. The computer-implemented method of claim 18, wherein the possible nodes list comprises nodes of a Hidden Markov Model.

21. The computer-implemented method of claim 18, wherein the label comprises a label name associated with a character from a character set.

22. The computer-implemented method of claim 18, wherein the score comprises the sum of the observation score, a transition score, and the score for the previous node at the previous frame.

23. The computer-implemented method of claim 18, wherein pruning the nodes having a sum of an observation score for the node and a score for a previous node to the node at a previous frame to the subsequent frame greater than the sum of the score for the best scoring node at the subsequent frame and a beam threshold further comprises adding a parameter to the observation score, wherein the parameter is an estimate of a transition score.

24. The computer-implemented method of claim 18, wherein the label score is based on an optical model.

25. The computer-implemented method of claim 18, wherein the possible nodes list for a frame comprises nodes comprising emissions that correspond to an observation in the frame.

26. The computer-implemented method of claim 18, wherein the node is a label transition node when the node is the last node of one of the labels in a Hidden Markov Model.

27. The computer-implemented method of claim 18, wherein the frames comprising the input comprise an image of text.

28. A computer-implemented system for stitching tables comprising:

a Hidden Markov Model comprising nodes and transitions, where the nodes comprise emission probabilities and are associated with transition probabilities;

a decoder adapted to receive the Hidden Markov Model and frames, decode the frames, and output predictions;

a label transition node pruner adapted to receive a frame from the frames and a possible nodes list for the frame and prune one of the nodes from the possible nodes list based on a score for the one of nodes, a best scoring node from the possible nodes list, and a penalty term;

a label selector adapted to receive the frame and the possible nodes list for the frame and generate a possible nodes list for a subsequent frame to the frame comprising at least one node connected to one of the nodes from the possible nodes list based on a score for a label associated with the at least one node, a highest scoring label at the subsequent frame, a first parameter, a label rank for the label, and a second parameter; and

an early pruner adapted receive the subsequent frame and the possible nodes list for the subsequent frame and prune one of the nodes from the possible nodes list for the subsequent frame based on an observation score for the one of the nodes, a score for a previous node from a previous frame, and the best scoring node from the possible nodes list for the subsequent frame.

29. The computer-implemented system of claim 28 further comprising:

a node list generator adapted to generate a possible nodes list for a next frame based on the possible nodes list for the frame and the transitions, and wherein the decoder is further adapted to prune nodes from the possible nodes list during the decoding of the frame.

30. The computer-implemented system of claim 28, wherein the label transition node pruner is further adapted to prune one of the nodes from the possible nodes list when the one of the nodes is a label transition node and the score for the one of the nodes is greater than a sum of the score for a best scoring node at the frame and the beam threshold minus the penalty term.

31. The computer-implemented system of claim 28, wherein the early pruner is further adapted to prune one of the nodes from the possible nodes list for the subsequent frame when a sum of the observation score for the one of the nodes and the score for the previous node at the previous frame is greater than the sum of the score for the best scoring node at the subsequent frame and the beam threshold.

32. The computer-implemented system of claim 28, wherein the label selector is further adapted to add one of the nodes to the possible nodes list for the subsequent frame when the one of the nodes is a first node for a label and a score for the label is less than or equal to the sum of a score for a highest scoring label at the subsequent frame and the first parameter or the label rank is less than or equal to the second parameter.

33. The computer-implemented system of claim 28, wherein the decoder is further adapted to output predictions using time-synchronous Viterbi decoding, and wherein the predictions are label names associated with labels in the Hidden Markov Model.

34. The computer-implemented system of claim 33, wherein a label in the Hidden Markov Model comprises at least one node.

35. A system comprising:

one or more computers and one or more storage devices storing instructions which are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising;

receiving a node of a Hidden Markov Model, wherein the node is a label transition node;

receiving a frame, wherein the frame is a predicted segmentation point; and

pruning the node from a possible nodes list with label transition node, wherein label transition node pruning comprises;

scoring the node at the frame to obtain a score, and

pruning the node when the score is greater than the sum of a best score at the frame and a beam threshold minus a penalty term.

36. The system of claim 35, wherein the instructions which are operable, when executed by the one or more computers, cause the one or more computers to perform operations further comprising:

generating a possible nodes list for a subsequent frame to the frame using label selection by;

scoring a label at the subsequent frame to obtain a label score;

ranking the label based on the label score to obtain a label rank; and

adding a first node of the label to the possible nodes list for the subsequent frame when the label score is less than or equal to a sum of a best label score at the subsequent frame and a first parameter or the label rank is less than or equal to a second parameter.

37. The system of claim 36, wherein the instructions which are operable, when executed by the one or more computers, cause the one or more computers to perform operations further comprising pruning a second node from the possible nodes list for the subsequent with early pruning, wherein early pruning comprises:

scoring the second node at the subsequent frame with at least one observation feature function to obtain an observation score; and

pruning the second node when an early pruning score is greater than a sum of the current best score at the subsequent frame and the beam threshold, wherein the previous node score is a score for a previous node to the second node at a previous frame to the subsequent frame, and wherein the early pruning score is the sum of the observation score and the previous node score.