Pruning and label selection in Hidden Markov Model-based OCR

• US 9,672,448 B2
• Filed: 11/13/2015
• Issued: 06/06/2017
• Est. Priority Date: 12/31/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Fujii, Yasuhisa
• Primary Examiner(s): Patel, Jayesh A
• Application Number:
  US14/941,470
• Publication Number:
  US 20160070992A1
• Time in Patent Office: 571 Days
• Field of Search: None
• 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 method of performing optical text recognition on an input image using a Hidden Markov Model, the method comprising:

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

receiving a frame, wherein the frame is a portion of the input image and wherein the frame has been determined to be a predicted character boundary in the input image; and

pruning the node from a possible nodes list for the frame with label transition node pruning, wherein the possible nodes list for the frame is a list of nodes in the Hidden Markov Model that may be evaluated to determine whether they correspond to the frame, the pruning comprising;

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

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

2. The 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 method of claim 2, wherein the label comprises a label name associated with a character from a character set.

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

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

6. The method of claim 5, further comprising:

storing the label score; and

reusing the label score during decoding of the subsequent frame.

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

8. The 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 a current best score at the subsequent frame and the beam threshold, wherein the early pruning score is the sum of the observation score and a previous node score, and wherein the previous node score is a score for a previous node to the second node at a previous frame to the subsequent frame.

9. The 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 method of claim 1, wherein the possible nodes list is used in time-synchronous Viterbi decoding of the frame.

11. The method of claim 1, wherein the penalty term is a 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.

12. The 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.

13. A system comprising one or more computers and one or more storage devices storing instructions that when executed by the one or more computers cause the one or more computers to perform operations of performing optical text recognition on an input image using a Hidden Markov Model, the operations comprising:

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

receiving a frame, wherein the frame is a portion of the input image and wherein the frame has been determined to be a predicted character boundary in the input image; and

pruning the node from a possible nodes list for the frame with label transition node pruning, wherein the possible nodes list for the frame is a list of nodes in the Hidden Markov Model that may be evaluated to determine whether they correspond to the frame, the pruning comprising;

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

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

14. The system of claim 13, the 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.

15. The system of claim 14, wherein the label comprises a label name associated with a character from a character set.

16. The system of claim 14, wherein scoring the label at the subsequent frame comprises using fast-match.

17. The system of claim 14, wherein scoring the label at the subsequent frame comprises scoring the initial state of an optical model for the label at the subsequent frame.

18. The system of claim 17, the operations further comprising:

storing the label score; and

reusing the label score during decoding of the subsequent frame.

19. The system of claim 13, the operations 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 a current best score at the subsequent frame and the beam threshold, wherein the early pruning score is the sum of the observation score and a previous node score, and wherein the previous node score is a score for a previous node to the second node at a previous frame to the subsequent frame.

20. One or more non-transitory storage media storing instructions that when executed by one or more computers cause the one or more computers to perform operations of performing optical text recognition on an input image using a Hidden Markov Model, the operations comprising:

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

receiving a frame, wherein the frame is a portion of the input image and wherein the frame has been determined to be a predicted character boundary in the input image; and

pruning the node from a possible nodes list for the frame with label transition node pruning, wherein the possible nodes list for the frame is a list of nodes in the Hidden Markov Model that may be evaluated to determine whether they correspond to the frame, the pruning comprising;

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

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

21. The one or more non-transitory storage media of claim 20, wherein the operations further comprise:

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.

22. The one or more non-transitory storage media of claim 21, wherein the operations further comprise:

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 a current best score at the subsequent frame and the beam threshold, wherein the early pruning score is the sum of the observation score and a previous node score, and wherein the previous node score is a score for a previous node to the second node at a previous frame to the subsequent frame.

23. The one or more non-transitory storage media of claim 22, 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.

24. The one or more non-transitory storage media of claim 20, wherein the penalty term is a 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.

25. The one or more non-transitory storage media of claim 20, 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.