Trellis based word decoder with reverse pass

• US 9,639,783 B2
• Filed: 04/28/2015
• Issued: 05/02/2017
• Est. Priority Date: 07/19/2012
• Status: Expired due to Fees

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Baheti, Pawan Kumar, Barman, Kishor K., Krishna Kumar, Raj Kumar
• Primary Examiner(s): Bayat, Ali
• Application Number:
  US14/698,528
• Publication Number:
  US 20150242710A1
• Time in Patent Office: 735 Days
• Field of Search: 382177
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/262 using context analysis, e.g. lexical, syntactic or semantic context

Abstract

Systems, apparatuses, and methods to relate images of words to a list of words are provided. A trellis based word decoder analyses a set of OCR characters and probabilities using a forward pass across a forward trellis and a reverse pass across a reverse trellis. Multiple paths may result, however, the most likely path from the trellises has the highest probability with valid links. A valid link is determined from the trellis by some dictionary word traversing the link. The most likely path is compared with a list of words to find the word closest to the most.

Claims

1. A method to prepare and use a forward trellis and a reverse trellis in an optical character recognition (OCR) system, the method comprising:

loading the forward trellis containing characters from a list of words to form a loaded forward trellis;

loading the reverse trellis containing the characters from the list of words to form a loaded reverse trellis;

computing a forward path probability of a forward path through the loaded forward trellis;

determining a most-likely forward path based on the forward path probability;

computing a reverse path probability of a reverse path through the loaded reverse trellis;

determining a most-likely reverse path based on the reverse path probability; and

selecting a path based on a greater of the forward path probability and the reverse path probability, wherein the path represents a set of selected characters from the list of words in the OCR system.

2. The method of claim 1, wherein the list of words comprise a Devanagari list of words.

3. The method of claim 1, further comprising forming a linking vector that indicates valid and invalid links into a node.

4. The method of claim 1, further comprising, for each node in the forward trellis and the reverse trellis having a previous character position entering the node, forming a linking vector that indicates valid and invalid links into a node.

5. The method of claim 1, further comprising, for each node in the forward trellis and the reverse trellis having a previous character position entering the node, forming a set of words indicating which words from the list of words have a path through the node.

6. The method of claim 1, wherein loading the reverse trellis comprises, for each word in the list of words:

selecting a word from the list of words; and

loading the reverse trellis at;

a first character position with a final character;

a second character position with a second to the final character; and

a third character position with a third to the final character.

7. The method of claim 1, further comprising sending the loaded forward trellis and the loaded reverse trellis to a mobile device.

8. An apparatus to prepare and use a forward trellis and a reverse trellis in an optical character recognition (OCR) system, the apparatus comprising:

the forward trellis;

the reverse trellis; and

a processor coupled to receive a list of words and coupled to load the forward trellis and the reverse trellis, wherein the processor comprises program code to;

load the forward trellis containing characters from the list of words to form a loaded forward trellis;

load the reverse trellis containing characters from the list of words to form a loaded reverse trellis;

compute a forward path probability of a forward path through the loaded forward trellis;

determine a most-likely forward path based on the forward path probability;

compute a reverse path probability of a reverse path through the loaded reverse trellis;

determine a most-likely reverse path based on the reverse path probability; and

select a path based on a greater of the forward path probability and the reverse path probability, wherein the path represents a set of selected characters from the list of words in the OCR system.

9. The apparatus of claim 8, wherein the list of words comprise a Devanagari list of words.

10. The apparatus of claim 8, further comprising a linking vector that indicates valid and invalid links into a node.

11. The apparatus of claim 8, further comprising, for each node in the forward trellis and the reverse trellis having a previous character position entering the node, a linking vector that indicates valid and invalid links into a node.

12. The apparatus of claim 8, further comprising, for each node in the forward trellis and the reverse trellis having a previous character position entering the node, a set of words indicating which words from the list of words have a path through the node.

13. An apparatus to prepare and use a forward trellis and a reverse trellis in an optical character recognition (OCR) system, the apparatus comprising a processor and a memory, wherein the memory includes software instructions to:

load the forward trellis containing characters from a list of words to form a loaded forward trellis;

load the reverse trellis containing the characters from the list of words to form a loaded reverse trellis;

compute a forward path probability of a forward path through the loaded forward trellis;

determine a most-likely forward path based on the forward path probability;

compute a reverse path probability of a reverse path through the loaded reverse trellis;

determine a most-likely reverse path based on the reverse path probability; and

select a path based on a greater of the forward path probability and the reverse path probability, wherein the path represents a set of selected characters from the list of words in the OCR system.

14. A non-transitory computer-readable storage medium including program code stored thereon for an apparatus to prepare and use a forward trellis and a reverse trellis, the non-transitory computer-readable storage medium comprising program code to:

load the forward trellis containing characters from a list of words to form a loaded forward trellis;

load the reverse trellis containing the characters from the list of words to form a loaded reverse trellis;

compute a forward path probability of a forward path through the loaded forward trellis;

determine a most-likely forward path based on the forward path probability;

compute a reverse path probability of a reverse path through the loaded reverse trellis;

determine a most-likely reverse path based on the reverse path probability; and

select a path based on a greater of the forward path probability and the reverse path probability, wherein the path represents a set of selected characters from the list of words in the OCR system.

15. The non-transitory computer-readable storage medium of claim 14, wherein the list of words comprise a Devanagari list of words.

16. The non-transitory computer-readable storage medium of claim 14, further comprising forming a linking vector that indicates valid and invalid links into a node.

17. The non-transitory computer-readable storage medium of claim 14, further comprising, for each node in the forward trellis and the reverse trellis having a previous character position entering the node, forming a linking vector that indicates valid and invalid links into a node.

18. The non-transitory computer-readable storage medium of claim 14, further comprising, for each node in the forward trellis and the reverse trellis having a previous character position entering the node, forming a set of words indicating which words from the list of words have a path through the node.

19. The non-transitory computer-readable storage medium of claim 14, wherein loading the reverse trellis comprises, for each word in the list of words:

selecting a word from the list of words; and

loading the reverse trellis at;

a first character position with a final character;

a second character position with a second to the final character; and

a third character position with a third to the final character.

20. The non-transitory computer-readable storage medium of claim 14, further comprising sending the loaded forward trellis and the loaded reverse trellis to a mobile device.