Granted Patent B2

US 9,721,193 · App. 14/531,258 · Granted Aug 1, 2017

Inventors: Martin T. King (Vashon Island, WA); Dale L. Grover (Ann Arbor, MI); Clifford A. Kushler (Nevada City, CA); James Q. Stafford-Fraser (Cambridge, GB)

Assignee: Google Inc.

G06K9/72G06F17/30011G06K9/00456G06K9/00463G06K9/18G06K9/325G06K9/344G06K9/348G06K9/74G06F17/30253G06K2209/01

Abstract

Claims (62)

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.

Assignments (4)

Continuity (77)