Text entity recognition

• US 9,256,795 B1
• Filed: 03/15/2013
• Issued: 02/09/2016
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Original Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Inventors: Gray, Douglas Ryan, Lin, Xiaofan, Dhua, Arnab Sanat Kumar, Lou, Yu
• Primary Examiner(s): Patel, Nirav G
• Application Number:
  US13/842,433
• Time in Patent Office: 1,061 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06F 3/14 Digital output to display device ; Cooperation and interconnection of the display device with other functional units
• CPC Class Codes: G06F 40/166 Editing, e.g. inserting or deleting
• CPC Class Codes: G06V 20/20 in augmented reality scenes
• CPC Class Codes: G06V 20/62 Text, e.g. of license plates, overlay texts or captions on TV images
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1452 based on positionally close symbols, e.g. amount sign or URL-specific characters
• CPC Class Codes: G06V 30/2504 Coarse or fine approaches, e.g. resolution of ambiguities or multiscale approaches
• CPC Class Codes: G06V 30/268 Lexical context

Abstract

Various embodiments enable the identification of semi-structured text entities in an imager. The identification of the text entities is a relatively simple problem when the text is stored in a computer and free of errors, but much more challenging if the source is the output of an optical character recognition (OCR) engine from a natural scene image. Accordingly, output from an OCR engine is analyzed to isolate a character string indicative of a text entity. Each character of the string is then assigned to a character class to produce a character class string and the text entity of the string is identified based in part on a pattern of the character class string.

Claims

1. A computer-implemented method, comprising:

displaying an image, captured by a camera of a computing device, on a display element of the computing device;

analyzing the image to locate a region of text in the image;

recognizing text within the region with an optical character recognition (OCR) engine, the OCR engine providing an output of recognized text including characters grouped by one or more text lines;

analyzing the one or more text lines to isolate a character string indicative of at least one of a phone number, an email address, or a uniform resource locator (URL), each character of the isolated character string being assigned to a character class to produce a character class string;

based at least in part on a pattern of the character class string, determining a matching score for the isolated character string with respect to at least one of a phone number, an email address, or a URL, the isolated character string being identified as the at least one of a phone number, an email address, or a URL if the matching score is greater than a threshold score, wherein determining the matching store comprises assigning costs to edits made to the character class string, wherein a cost associated with mistaking characters that are similar in appearance is small and the cost associated with mistaking characters that are relatively different in appearance is greater than a threshold value;

determining an overlay template and respective functionality for the at least one of a phone number, an email address, or a URL; and

displaying the isolated character string on the display element using the overlay template as an overlay element in a live field of view being captured by the camera, the overlay element including at least one user-selectable element enabling the respective functionality associated with the at least one of a phone number, an email address, or a URL to be performed.

2. The computer-implemented method of claim 1, wherein various costs to various edits are provided in an N by M matrix where N represents a number possible ASCII characters and M represents a number of possible character classes.

3. The computer-implemented method of claim 1, wherein analyzing the one or more text lines to isolate groups of characters includes omitting groups of characters that do not fit a pattern indicative of at least one of the phone number, the email address, or the URL.

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

validating the isolated character string by comparing the isolated character string to a determined number of most popular URLs in response to the pattern of the character string being indicative of a URL.

5. A computer-implemented method, comprising:

receiving an output from an optical character recognition (OCR) engine;

analyzing the output to isolate a character string indicative of a text entity;

assigning each character of the isolated character string to a character class to produce a character class string; and

based at least in part on a pattern identified for the character class string, identifying the isolated character string as being the text entity, wherein the isolated character string is identified as the text entity in response to determining a matching score above a threshold for the isolated character string, the matching score being based at least in part on a number of edits made to the character class string, and wherein determining the matching store comprises assigning costs to edits made to the character class string, wherein a cost associated with mistaking characters that are similar in appearance is small and the cost associated with mistaking characters that are relatively different in appearance is greater than a threshold value.

6. The computer-implemented method of claim 5, wherein analyzing the output to isolate the character string indicative of the text entity includes performing one or more heuristic tests.

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

converting the output into text lines; and

omitting characters that do not fit a pattern indicative of the text entity.

8. The computer-implemented method of claim 5, wherein various costs to various edits are provided in an N by M matrix where N represents a number possible ASCII characters and M represents a number of possible character classes.

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

autocorrecting a character in the character string to a character of a character class associated with the text entity in response to identifying the character belonging to a character class not associated with the text entity type.

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

validating the isolated character string by comparing the isolated character string to a determined number of most popular URLs in response to the pattern of the character string being indicative of a URL.

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

validating the isolated character string by comparing the isolated character string to valid area codes in response to the pattern of the character string being indicative of a phone number.

12. A computing device, comprising:

a processor;

a display screen; and

memory including instructions that, when executed by the processor, cause the computing device to;

receive an output from an optical character recognition (OCR) engine;

analyze the output to isolate a character string indicative of a text entity;

assign each character of the isolated character string to a character class to produce a character class string; and

based at least in part on a pattern of the character class string, identify the isolated character string as being the text entity, wherein the isolated character string is identified as the text entity in response to determining a matching score above a threshold for the isolated character string, the matching score being based at least in part on a number of edits made to the character class string, and wherein determining the matching store comprises assigning costs to edits made to the character class string, wherein a cost associated with mistaking characters that are similar in appearance is small and the cost associated with mistaking characters that are relatively different in appearance is greater than a threshold value.

13. The computing device of claim 12, wherein analyzing the output to isolate the character string indicative of the text entity includes performing one or more heuristic tests.

14. The computing device of claim 13, wherein the instructions, when executed by the processor, further enable the computing device to:

convert the output into text lines; and

omit characters that do not fit a pattern indicative of the text entity.

15. A non-transitory computer-readable storage medium storing instructions that, when executed by at least one processor, cause a computing device to:

receive an output from an optical character recognition (OCR) engine;

analyze the output to isolate a character string indicative of a text entity;

assign each character of the isolated character string to a character class to produce a character class string; and

based at least in part on a pattern of the character class string, identify the isolated character string as being the text entity, wherein the isolated character string is identified as the text entity in response to determining a matching score above a threshold for the isolated character string, the matching score being based at least in part on a number of edits made to the character class string, and wherein determining the matching store comprises assigning costs to edits made to the character class string, wherein a cost associated with mistaking characters that are similar in appearance is small and the cost associated with mistaking characters that are relatively different in appearance is greater than a threshold value.

16. The non-transitory computer-readable storage medium of claim 15, wherein various costs to various edits are provided in an N by M matrix where N represents a number possible ASCII characters and M represents a number of possible character classes.

17. The non-transitory computer-readable storage medium of claim 15, wherein the instructions that, when executed by the at least one processor, further cause the computing device to:

autocorrecting a character in the character string to a character of a character class associated with the text entity in response to identifying the character belonging to a character class not associated with the text entity type.

18. The non-transitory computer-readable storage medium of claim 15, wherein the instructions that, when executed by the at least one processor, further cause the computing device to:

validating the isolated character string by comparing the isolated character string to a determined number of most popular URLs in response to the pattern of the character string being indicative of a URL.