Using gestalt information to identify locations in printed information

• US 9,081,799 B2
• Filed: 12/06/2010
• Issued: 07/14/2015
• Est. Priority Date: 12/04/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: King, Martin T., Mannby, Claes-Fredrik, Valenti, William
• Primary Examiner(s): SOMERS, MARC S
• Application Number:
  US12/961,407
• Publication Number:
  US 20110167075A1
• Time in Patent Office: 1,681 Days
• Field of Search: 707/706, 707/736, 707/758
• US Class Current: 1/1
• CPC Class Codes: G06F 16/152 using file content signatures, e.g. hash values
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: G06F 16/5854 using shape and object relationship

Abstract

A facility for identifying a location in a printed document is described. The facility obtains an image of the printed document, and extracts gestalt information from text occurring in the image of the printed document. The facility compares the extracted gestalt information to an index of documents and, based upon this comparison, identifies a document that includes the gestalt information.

Claims

1. A computer-implemented method comprising:

obtaining an image of a rendered document that includes text;

determining a two dimensional geometric shape based at least on a first location in the image of the rendered document of a first space between a first pair of consecutive words, a second location in the image of the rendered document of a second space between a second pair of consecutive words, and a third location in the image of the rendered document of a third space between a third pair of consecutive words, wherein the first space, the second space, and the third space are not all included on a same line of text in the rendered document;

generating a document signature based on the two dimensional geometric shape; and

generating a query for an electronic document that is a counterpart to the rendered document, based at least on the document signature.

2. The method of claim 1, wherein the first location, the second location, and the third location each comprise an absolute location in the image and determining the two dimensional geometric shape comprises determining the two dimensional geometric shape using the absolute locations.

3. The method of claim 1, comprising:

determining a first distance between the first space and the second space;

determining a second distance between the first space and the third space; and

determining a third distance between the second space and the third space,

wherein determining the two dimensional geometric shape comprises determining the two dimensional geometric shape using the first distance, the second distance, and the third distance.

4. The method of claim 3, wherein the two dimensional geometric shape comprises a triangle and the document signature indicates a signature location of the triangle in the image.

5. The method of claim 3, wherein the two dimensional geometric shape comprises a word centroid and the document signature indicates a signature location of the centroid in the image.

6. The method of claim 5, wherein the signature location comprises a location of the center of the centroid in the image.

7. The method of claim 1, wherein the two dimensional geometric shape is defined by a first line that extends from the first location to the second location, a second line that extends from the second location to the third location, and a third line that extends from the third location to the first location.

8. The method of claim 1, wherein the two dimensional geometric shape comprises an outline that connects the first location, the second location, and the third location.

9. The method of claim 1, further comprising comparing the two dimensional shape to two dimensional shapes of other documents to identify a matching document that matches the rendered document.

10. A system comprising:

one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising;

obtaining an image of a rendered document that includes text;

determining a two dimensional geometric shape based at least on a first location in the image of the rendered document of a first space between a first pair of consecutive words, a second location in the image of the rendered document of a second space between a second pair of consecutive words, and a third location in the image of the rendered document of a third space between a third pair of consecutive words, wherein the first space, the second space, and the third space are not all included on a same line of text in the rendered document;

generating a document signature based on the two dimensional geometric shape; and

generating a query for an electronic document that is a counterpart to the rendered document, based at least on the document signature.

11. The system of claim 10, wherein the first location, the second location, and the third location each comprise an absolute location in the image and determining the two dimensional geometric shape comprises determining the two dimensional geometric shape using the absolute locations.

12. The system of claim 10, the operations comprising:

determining a first distance between the first space and the second space;

determining a second distance between the first space and the third space; and

determining a third distance between the second space and the third space,

wherein determining the two dimensional geometric shape comprises determining the two dimensional geometric shape using the first distance, the second distance, and the third distance.

13. The system of claim 12, wherein the two dimensional geometric shape comprises a triangle and the document signature indicates a signature location of the triangle in the image.

14. The system of claim 12, wherein the two dimensional geometric shape comprises a word centroid and the document signature indicates a signature location of the centroid in the image.

15. The system of claim 14, wherein the signature location comprises a location of the center of the centroid in the image.

16. A non-transitory computer-readable medium storing software comprising instructions executable by one or more computers which, upon such execution, cause the one or more computers to perform operations comprising:

obtaining an image of a rendered document that includes text;

determining a two dimensional geometric shape based at least on a first location in the image of the rendered document of a first space between a first pair of consecutive words, a second location in the image of the rendered document of a second space between a second pair of consecutive words, and a third location in the image of the rendered document of a third space between a third pair of consecutive words, wherein the first space, the second space, and the third space are not all included on a same line of text in the rendered document;

generating a document signature based on the two dimensional geometric shape; and

generating a query for an electronic counterpart to the rendered document, based at least on the document signature.

17. The computer-readable medium of claim 16, wherein the first location, the second location, and the third location each comprise absolute location in the image and determining the two dimensional geometric shape comprises determining the two dimensional geometric shape using the absolute locations.

18. The computer-readable medium of claim 16, the operations comprising:

determining a first distance between the first space and the second space

determining a second distance between the first space and the third space; and

determining a third distance between the second space and the third space,

wherein determining the two dimensional geometric shape comprises determining the two dimensional geometric shape using the first distance, the second distance, and the third distance.

19. The computer-readable medium of claim 18, wherein the two dimensional geometric shape comprises a triangle and the document signature indicates a signature location of the triangle in the image.

20. The computer-readable medium of claim 18, wherein the two dimensional geometric shape comprises a word centroid and the document signature indicates a signature location of the centroid in the image.

21. The computer-readable medium of claim 20, wherein the signature location comprises a location of the center of the centroid in the image.