Method and system for character recognition

• US 9,721,193 B2
• Filed: 11/03/2014
• Issued: 08/01/2017
• Est. Priority Date: 04/19/2004
• Status: Active Grant

• Current Assignee: Kyocera Corporation
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: King, Martin T., Grover, Dale L., Kushler, Clifford A., Stafford-Fraser, James Q.
• Primary Examiner(s): Seth, Manav
• Application Number:
  US14/531,258
• Publication Number:
  US 20150193672A1
• Time in Patent Office: 1,002 Days
• CPC Class Codes: G06F 16/5846 using extracted text
• CPC Class Codes: G06F 16/93 Document management systems
• 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/153 using recognition of characters or words
• CPC Class Codes: G06V 30/158 using character size, text spacings or pitch estimation
• CPC Class Codes: G06V 30/224 of printed characters having additional code marks or containing code marks
• CPC Class Codes: G06V 30/413 Classification of content, e.g. text, photographs or tables
• CPC Class Codes: G06V 30/414 Extracting the geometrical structure, e.g. layout tree; Block segmentation, e.g. bounding boxes for graphics or text

Abstract

Character recognition is described. In one embodiment, it may use matched sequences rather than character shape to determine a computer-legible result.

Claims

1. A computer-implemented method comprising:

obtaining an image of a sequence of symbols, based on a document capture process performed on a rendered document;

segmenting a portion of the image into multiple segmented sub-images, each of the segmented sub-images corresponding to a single symbol in the sequence of symbols;

for each segmented sub-image of at least a subset of the segmented sub-images, in an order that corresponds to the sequence of symbols;

determining whether one or more features of the segmented sub-image are classified as being similar to one or more corresponding features of any stored sub-image in a cache of stored sub-images;

based on determining that one or more features of the segmented sub-image are not classified as being similar to one or more corresponding features of any stored sub-image, selecting an unassigned symbol identifier, and storing the segmented sub-image in association with the selected symbol identifier in the cache of stored sub-images; and

attributing the selected identifier to any segmented sub-images that follow the segmented sub-image and have one or more features that are classified as being similar to one or more corresponding features of the stored segmented sub-image; and

generating an encoding of the sequence of symbols that is based on the identifiers attributed to the segmented sub-images.

2. The computer-implemented method of claim 1, wherein the rendered document is a printed document.

3. The computer-implemented method of claim 1, wherein the rendered document is a dynamically displayed document.

4. The computer-implemented method of claim 1, wherein segmenting a portion of the image into multiple segmented sub-images comprises determining that space exists between each of the multiple segmented sub-images.

5. The computer-implemented method of claim 1, wherein determining whether one or more features of the segmented sub-image are classified as being similar to one or more corresponding features of any stored sub-image in the cache of stored sub-images comprises:

determining a probability that the segmented sub-image corresponds to a stored sub-image; and

determining that the probability meets a predetermined threshold.

6. The computer-implemented method of claim 1, wherein determining whether one or more features of the segmented sub-image are classified as being similar to one or more corresponding features of any stored sub-image in the cache of stored sub-images comprises:

determining a pattern corresponding to a difference between the segmented sub-image and a stored sub-image; and

determining that a size of the pattern meets a predetermined threshold.

7. The computer-implemented method of claim 1, wherein determining whether one or more features of the segmented sub-image are classified as being similar to one or more corresponding features of any stored sub-image in the cache of stored sub-images comprises:

determining a first set of vectors that correspond to the segmented sub-image;

determining a second set of vectors that correspond to a stored sub-image; and

determining that the first set of vectors and the second set of vectors meet a predetermined similarity threshold.

8. The computer-implemented method of claim 7, wherein the predetermined similarity threshold for the first and second sets of vectors is expressed in terms of length and direction.

9. A system, comprising:

one or more computing processors; and

a computer-readable storage device including instructions executable by the one or more computing processors and upon such execution cause the one or more computing processors to perform operations comprising;

obtaining an image of a sequence of symbols, based on a document capture process performed on a rendered document;

segmenting a portion of the image into multiple segmented sub-images, each of the segmented sub-images corresponding to a single symbol in the sequence of symbols;

for each segmented sub-image of at least a subset of the segmented sub-images, in an order that corresponds to the sequence of symbols;

determining whether one or more features of the segmented sub-image are classified as being similar to one or more corresponding features of any stored sub-image in a cache of stored sub-images;

based on determining that one or more features of the segmented sub-image are not classified as being similar to one or more corresponding features of any stored sub-image, selecting an unassigned symbol identifier, and storing the segmented sub-image in association with the selected symbol identifier in the cache of stored sub-images; and

attributing the selected identifier to any segmented sub-images that follow the segmented sub-image and have one or more features that are classified as being similar to one or more corresponding features of the stored segmented sub-image; and

generating an encoding of the sequence of symbols that is based on the identifiers attributed to the segmented sub-images.

10. The system of claim 9, wherein segmenting a portion of the image into multiple segmented sub-images comprises determining that space exists between each of the multiple segmented sub-images.

11. The system of claim 9, wherein determining whether one or more features of the segmented sub-image are classified as being similar to one or more corresponding features of any stored sub-image in the cache of stored sub-images comprises:

determining a probability that the segmented sub-image corresponds to a stored sub-image; and

determining that the probability meets a predetermined threshold.

12. The system of claim 9, wherein determining whether one or more features of the segmented sub-image are classified as being similar to one or more corresponding features of any stored sub-image in the cache of stored sub-images comprises:

determining a pattern corresponding to a difference between the segmented sub-image and a stored sub-image; and

determining that a size of the pattern meets a predetermined threshold.

13. The system of claim 9, wherein determining whether one or more features of the segmented sub-image are classified as being similar to one or more corresponding features of any stored sub-image in the cache of stored sub-images comprises:

determining a first set of vectors that correspond to the segmented sub-image;

determining a second set of vectors that correspond to a stored sub-image; and

determining that the first set of vectors and the second set of vectors meet a predetermined similarity threshold.

14. The system of claim 13, wherein the predetermined similarity threshold for the first and second sets of vectors is expressed in terms of length and direction.

15. A memory storage apparatus storing instructions executable by a data processing apparatus and that upon such execution cause the data processing apparatus to perform operations comprising:

obtaining an image of a sequence of symbols, based on a document capture process performed on a rendered document;

segmenting a portion of the image into multiple segmented sub-images, each of the segmented sub-images corresponding to a single symbol in the sequence of symbols;

for each segmented sub-image of at least a subset of the segmented sub-images, in an order that corresponds to the sequence of symbols;

determining whether one or more features of the segmented sub-image are classified as being similar to one or more corresponding features of any stored sub-image in the cache of stored sub-images;

based on determining that one or more features of the segmented sub-image are not classified as being similar to one or more corresponding features of any stored sub-image, selecting an unassigned symbol identifier, and storing the segmented sub-image in association with the selected symbol identifier in the cache of stored sub-images; and

attributing the selected identifier to any segmented sub-images that follow the segmented sub-image and have one or more features that are classified as being similar to one or more corresponding features of the stored segmented sub-image; and

generating an encoding of the sequence of symbols that is based on the identifiers attributed to the segmented sub-images.

16. The memory storage apparatus of claim 15, wherein determining whether one or more features of the segmented sub-image are classified as being similar to one or more corresponding features of any stored sub-image in the cache of stored sub-images comprises:

determining a probability that the segmented sub-image corresponds to a stored sub-image; and

determining that the probability meets a predetermined threshold.

17. The memory storage apparatus of claim 15, wherein determining whether one or more features of the segmented sub-image are classified as being similar to one or more corresponding features of any stored sub-image in the cache of stored sub-images comprises:

determining a pattern corresponding to a difference between the segmented sub-image and a stored sub-image; and

determining that a size of the pattern meets a predetermined threshold.

18. The memory storage apparatus of claim 15, wherein determining whether one or more features of the segmented sub-image are classified as being similar to one or more corresponding features of any stored sub-image in the cache of stored sub-images comprises:

determining a first set of vectors that correspond to the segmented sub-image;

determining a second set of vectors that correspond to a stored sub-image; and

determining that the first set of vectors and the second set of vectors meet a predetermined similarity threshold.