Lexicon-free, matching-based word-image recognition

• US 9,928,436 B2
• Filed: 07/08/2015
• Issued: 03/27/2018
• Est. Priority Date: 07/08/2015
• Status: Active Grant

• Current Assignee: Conduent Business Services, LLC (Conduent, Inc.)
• Original Assignee: Conduent Business Services, LLC (Conduent, Inc.)
• Inventors: Soldevila, Albert Gordo, Almazan, Jon
• Primary Examiner(s): Lefkowitz, Sumati
• Assistant Examiner(s): PERLMAN, DAVID S
• Application Number:
  US14/794,479
• Publication Number:
  US 20170011273A1
• Time in Patent Office: 993 Days
• Field of Search: None
• CPC Class Codes: G06F 18/29 Graphical models, e.g. Bayesian networks
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/19187 Graphical models, e.g. Bayesian networks or Markov models
• CPC Class Codes: G06V 30/1985 Syntactic analysis, e.g. using a grammatical approach syntactic image representation G06V30/18171
• CPC Class Codes: G06V 30/224 of printed characters having additional code marks or containing code marks
• CPC Class Codes: G06V 30/226 of cursive writing
• CPC Class Codes: G06V 30/268 Lexical context

Abstract

Methods and systems recognize alphanumeric characters in an image by computing individual representations of every character of an alphabet at every character position within a certain word transcription length. These methods and systems embed the individual representations of each alphabet character in a common vectorial subspace (using a matrix) and embed a received image of an alphanumeric word into the common vectorial subspace (using the matrix). Such methods and systems compute the utility value of the embedded alphabet characters at every one of the character positions with respect to the embedded alphanumeric character image; and compute the best transcription alphabet character of every one of the image characters based on the utility value of each embedded alphabet character at each character position. Such methods and systems then assign the best transcription alphabet character for each of the character positions to produce a recognized alphanumeric word within the received image.

Claims

1. A method of recognizing alphanumeric characters in an image comprising:

computing representations of all alphabet characters of an alphabet at every character position within a word transcription length;

embedding said representations of said alphabet characters in a common vectorial subspace using a matrix to produce embedded alphabet characters;

embedding a received image of an alphanumeric word into said common vectorial subspace using said matrix to produce an embedded alphanumeric character image, said embedded alphanumeric character image representing image characters at character positions;

computing a utility value in a directed acyclic graph (DAG) of every one of said embedded alphabet characters at each of said character positions of said embedded alphanumeric character image;

computing a highest-utility transcription alphabet character by finding a highest-utility path in said DAG for every one of said character positions based on said utility value of each said embedded alphabet character at each of said character positions, within said word transcription length; and

assigning said highest-utility transcription alphabet character for each of said character positions to produce a recognized alphanumeric word within said received image.

2. The method according to claim 1, said DAG having nodes,

each of said nodes represents one of said embedded alphabet characters at one of said character positions,

each of said character positions includes a different node for each different one of said embedded alphabet characters,

every edge between said nodes contains said utility value and a cost value of choosing each of said nodes, and

said finding said highest-utility path over said DAG begin based on said utility value and said cost value of choosing each of said nodes.

3. The method according to claim 2, said finding said highest-utility path over said DAG begin based on accumulating said utility value and said cost value of each different path in said DAG.

4. The method according to claim 3, said accumulating said utility value and said cost value comprising calculating a score of each path of said DAG by, for each said path:

summing utility values of all edges between nodes of a path to produce summed utility values for said path;

summing costs of all said edges of said path to produce summed cost values for said path;

calculating a normal cost value of said summed cost values; and

dividing said summed utility values by said normal cost value.

5. The method according to claim 2, said finding said highest-utility path comprising one of:

using an exhaustive search approach, where all paths are explored; and

using an approximate search approach, where only most promising paths are explored.

6. The method according to claim 1, said computing said utility value comprising processing said received image of said embedded alphanumeric character image with a tensor to produce a utility tensor that represents a utility of transcribing each of said image characters to each of said embedded alphabet characters.

7. The method according to claim 1, further comprising storing said embedded alphabet characters in a tensor.

8. A method of recognizing alphanumeric characters in an image comprising:

automatically performing initial processing using an image processor comprising;

computing representations of all alphabet characters of an alphabet at every character position within a word transcription length;

embedding said representations of said alphabet characters in a common vectorial subspace using a matrix to produce embedded alphabet characters; and

saving said embedded alphabet characters; and

after said initial processing repeatedly automatically performing subsequent processing without repeating said initial processing, said subsequent processing comprising;

receiving, into said image processor, an electronic image of an alphanumeric word from an image sensor device operatively connected to said image processor;

embedding said electronic image into said common vectorial subspace using said matrix to produce an embedded alphanumeric character image using said image processor, said embedded alphanumeric character image representing image characters at character positions;

computing a utility value in a directed acyclic graph (DAG) of every one of said embedded alphabet characters at each of said character positions of said embedded alphanumeric character image using said image processor;

computing a highest-utility transcription alphabet character by finding a highest-utility path in said DAG for every one of said character positions based on said utility value of each said embedded alphabet character at each of said character positions, within said word transcription length, using said image processor;

assigning said highest-utility transcription alphabet character for each of said character positions to produce a recognized alphanumeric word within said electronic image and determine a character length of said recognized alphanumeric word using said image processor; and

outputting said recognized alphanumeric word from said image processor.

9. The method according to claim 8, said DAG having nodes,

each of said nodes represents one of said embedded alphabet characters at one of said character positions,

each of said character positions includes a different node for each different one of said embedded alphabet characters,

every edge between said nodes contains said utility value and a cost value of choosing each of said nodes, and

said finding said highest-utility path over said DAG begin based on said utility value and said cost value of choosing each of said nodes.

10. The method according to claim 9, said finding said highest-utility path over said DAG begin based on accumulating said utility value and said cost value of each different path in said DAG.

11. The method according to claim 10, said accumulating said utility value and said cost value comprising calculating a score of each path of said DAG by, for each said path:

summing utility values of all edges between nodes of a path to produce summed utility values for said path;

summing costs of all said edges of said path to produce summed cost values for said path;

calculating a normal cost value of said summed cost values; and

dividing said summed utility values by said normal cost value.

12. The method according to claim 9, said finding said highest-utility path comprising one of:

using an exhaustive search approach, where all paths are explored; and

using an approximate search approach, where only most promising paths are explored.

13. The method according to claim 8, said computing said utility value comprising processing said electronic image of said embedded alphanumeric character image with a tensor to produce a utility tensor that represents a utility of transcribing each of said image characters to each of said embedded alphabet characters.

14. The method according to claim 8, further comprising storing said embedded alphabet characters in a tensor.

15. A system comprising:

an image sensor device;

an image processor device operatively connected to said image sensor device,

said image processor device automatically performing initial processing comprising;

computing representations of all alphabet characters of an alphabet at every character position within a word transcription length;

embedding said representations of said alphabet characters in a common vectorial subspace using a matrix to produce embedded alphabet characters; and

saving said embedded alphabet characters, after said initial processing, said image processor device repeatedly automatically performing subsequent processing without repeating said initial processing, said subsequent processing comprising;

receiving an electronic image of an alphanumeric word from said image sensor device;

embedding said electronic image into said common vectorial subspace using said matrix to produce an embedded alphanumeric character image, said embedded alphanumeric character image representing image characters at character positions;

computing a utility value in a directed acyclic graph (DAG) of every one of said embedded alphabet characters at each of said character positions of said embedded alphanumeric character image;

computing a highest-utility transcription alphabet character by finding a highest-utility path in said DAG for every one of said character positions based on said utility value of each said embedded alphabet character at each of said character positions, within said word transcription length; and

assigning said highest-utility transcription alphabet character for each of said character positions to produce a recognized alphanumeric word within said electronic image and determine a character length of said recognized alphanumeric word, and said image processor device automatically outputting said recognized alphanumeric word.

16. The system according to claim 15, said DAG having nodes,

each of said nodes represents one of said embedded alphabet characters at one of said character positions,

each of said character positions includes a different node for each different one of said embedded alphabet characters,

every edge between said nodes contains said utility value and a cost value of choosing each of said nodes, and

said finding said highest-utility path over said DAG begin based on said utility value and said cost value of choosing each of said nodes.

17. The system according to claim 16, said finding said highest-utility path over said DAG begin based on accumulating said utility value and said cost value of each different path in said DAG.

18. The system according to claim 17, said accumulating said utility value and said cost value comprising calculating a score of each path of said DAG by, for each said path:

summing utility values of all edges between nodes of a path to produce summed utility values for said path;

summing costs of all said edges of said path to produce summed cost values for said path;

calculating a normal cost value of said summed cost values; and

dividing said summed utility values by said normal cost value.

19. The system according to claim 16, said finding said highest-utility path comprising one of:

using an exhaustive search approach, where all paths are explored; and

using an approximate search approach, where only most promising paths are explored.

20. The system according to claim 15, said computing said utility value comprising processing said electronic image of said embedded alphanumeric character image with a tensor to produce a utility tensor that represents a utility of transcribing each of said image characters to each of said embedded alphabet characters.