Document fingerprints using block encoding of text

• US 8,838,657 B1
• Filed: 09/07/2012
• Issued: 09/16/2014
• Est. Priority Date: 09/07/2012
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Malone, James A., Thompson, Derick A.
• Primary Examiner(s): AL HASHEMI, SANA A
• Application Number:
  US13/607,420
• Time in Patent Office: 739 Days
• Field of Search: 707/609, 707/687, 707/790, 707/813, 707/821, 707/964, 707/953
• US Class Current: 707/821
• CPC Class Codes: G06F 16/93 Document management systems

Abstract

Methods and apparatus for document encoding using block encoding of text are disclosed. A computing device is configured to detect, within a digitized image object, a plurality of element groups, where each group comprises one or more text image elements and is separated from other groups by at least one delimiter. The device generates a numerical representation of the groups, comprising a plurality of numerical values, where a particular value corresponding to a particular group is determined based at least in part on a combined size of text image elements of the particular group. The device stores at least a subset of the numerical representation as a fingerprint representing text contents of the digitized image object.

Claims

1. A system comprising one or more computing devices, the system configured to:

detect, within a digitized image object comprising a plurality of text image elements, a plurality of element groups, wherein each element group comprises one or more text image elements and is separated, within the digitized image object, from other element groups of the plurality of element groups by at least one delimiter;

generate a first representation of the plurality of element groups, each element group being represented within the first representation as a respective two-dimensional block whose size is proportional to the combined size of the text image elements of the element group;

generate a second representation based at least in part on the first representation, each two-dimensional block of the first representation being represented within the second representation by a respective numerical encoding, a particular numerical encoding used for a particular two-dimensional block being based at least in part on the size of the particular two-dimensional block; and

store, as a fingerprint representing text contents of the digitized image object, at least a subset of the second representation, the subset of the second representation comprising a plurality of numerical encodings.

2. The system as recited in claim 1, wherein the one or more computing devices are further configured to:

identify, within the first representation, the smallest two-dimensional block and the largest two-dimensional block;

compute a difference between the sizes of the smallest and largest two-dimensional blocks;

generate a mapping between the difference and a range of numerical values, wherein a low end of the range corresponds to the size of the smallest two-dimensional block, and a high end of the range corresponds to the size of the largest two-dimensional block; and

determine the particular numerical encoding to be used for the particular two-dimensional block from the range of numerical values based at least in part on (a) the mapping and (b) a difference between the size of the particular two-dimensional block and the size of the smallest two-dimensional block.

3. The system as recited in claim 1, wherein the one or more computing devices are configured to:

in response to a comparison request from a client,

compare the fingerprint representing text contents of the digitized image object to a second fingerprint representing text contents of a second digitized image object, and

provide a metric of similarity between the respective text contents of the digitized image object and the second digitized image object, based at least in part on the comparison of the fingerprint and the second fingerprint.

4. The system as recited in claim 1, wherein the digitized image object is obtained by generating an image of at least a portion of a particular document, wherein the one or more computing devices are configured to:

in response to a search request, identify, using the fingerprint as a search parameter, a corresponding document from a collection of documents for which respective fingerprints are available, wherein the fingerprint of the corresponding document meets a similarity criterion with respect to the fingerprint of the particular document.

5. The system as recited in claim 1, wherein the one or more computing devices are configured to:

implement one or more programmatic interfaces enabling a client to specify one or more of;

(a) a range of numerical values to be used to generate the second representation, or (b) a sensitivity setting of at least one delimiter.

6. A computer-implemented method comprising:

under control of one or more computing devices configured with specific computer-executable instructions,

detecting, within a digitized image object comprising a plurality of text image elements, a plurality of element groups, wherein each element group comprises one or more text image elements and is separated, within the digitized image object, from other element groups of the plurality of element groups by at least one delimiter;

programmatically generating a numerical representation of the plurality of element groups, comprising a respective plurality of numerical values, wherein a particular numerical value corresponding to a particular element group is selected based at least in part on a combined size of text image elements of the particular element group; and

storing, in an electronic memory, as a fingerprint representing text contents of the digitized image object, at least a subset of the numerical representation.

7. The computer-implemented method as recited in claim 6, wherein said programmatically generating the numerical representation comprises:

generating a first representation of the plurality of element groups, each element group being represented within the first representation as a respective two-dimensional block whose size is proportional to the combined size of the text image elements of the element group; and

obtaining the numerical value for the particular element group from a range of numerical values based at least in part on a mapping between a range of sizes of the two-dimensional blocks of the first representation and the range of numerical values.

8. The computer-implemented method as recited in claim 6, wherein the at least one delimiter belongs to a set of delimiters including a character delimiter, a word delimiter, a paragraph delimiter, and a page delimiter, wherein the numerical representation comprises a numerical encoding of at least one delimiter of the set of delimiters.

9. The computer-implemented method as recited in claim 6, further comprising:

in response to a comparison request from a client,

comparing the fingerprint representing text contents of the digitized image object to a second fingerprint representing text contents of a second digitized image object, and

providing a metric of similarity between the respective text contents of the digitized image object and the second digitized image object, based at least in part on the comparison of the fingerprint and the second fingerprint.

10. The computer-implemented method as recited in claim 6, wherein the digitized image object is obtained by generating an image of at least a portion of a particular document, further comprising:

in response to a client search request, identifying, using at least a portion of the fingerprint as a search parameter, a corresponding document from a collection of documents for which respective fingerprints are available, wherein the fingerprint of the corresponding document meets a similarity criterion with respect to the fingerprint of the particular document.

11. The computer-implemented method as recited in claim 6, further comprising:

implementing a programmatic search interface enabling a client to indicate text for which a search is to be performed in a fingerprint collection;

generating a particular fingerprint for a set of text elements indicated in a search request received from the client via the programmatic search interface;

comparing the particular fingerprint with at least a subset of fingerprints of the fingerprint collection to identify one or more similar fingerprints in the collection based on a similarity criterion; and

providing to the client an indication of one or more documents corresponding to the one or more similar fingerprints.

12. The computer-implemented method as recited in claim 6, wherein the at least one delimiter comprises a plurality of delimiters, further comprising:

implementing one or more programmatic interfaces enabling a client to specify one or more of;

(a) a range of numerical values to be used for the numerical representation, or (b) a whitespace-based property of a delimiter of the plurality of delimiters.

13. The computer-implemented method as recited in claim 6, further comprising:

implementing a programmatic interface enabling a client to request, from within an e-mail client program, a generation of a fingerprint for a document received as an e-mail attachment;

wherein the digitized image object is obtained from at least a portion of the document in response to a request received via the programmatic interface.

14. The computer-implemented method as recited in claim 6, further comprising:

obtaining one or more metrics indicative of one or more of;

(a) resource usage associated with generating fingerprints for a plurality of images obtained from text-containing documents, or (b) a client satisfaction level associated with a use of fingerprints for document comparison and search; and

modifying one or more parameters associated with generating fingerprints based at least in part on the one or more metrics, wherein the one or parameters include at least one of (a) a delimiter property used in the detection of element groups, or (b) a range of numerical values used for the numerical representation.

15. The computer-implemented method as recited in claim 6, wherein the numerical value is selected from a first range of numerical values, further comprising:

generating and storing a second fingerprint representing text contents of the digitized image object, wherein the second fingerprint is generated using at least one of;

(a) a second plurality of element groups identified using a different set of one or more delimiters, or (b) a second range of numerical values;

in response to a comparison request specifying the digitized image object, determining whether to use the second fingerprint for the comparison based on one of;

(a) a desired comparison granularity indicator included in the request, or (b) one or more resource constraints.

16. A non-transitory computer-readable storage medium storing program instructions that when executed on one or more processors:

detect, within a digitized image object comprising a plurality of text image elements, a plurality of element groups, wherein each element group comprises one or more text image elements and is separated, within the digitized image object, from other element groups of the plurality of element groups by at least one delimiter;

generate a numerical representation of the plurality of element groups, comprising a respective plurality of numerical values, wherein a particular numerical value corresponding to a particular element group is determined based at least in part on a combined size of text image elements of the particular element group; and

store, as a fingerprint representing text contents of the digitized image object, at least a subset of the numerical representation.

17. The storage medium as recited in claim 16, wherein to generate the numerical representation, the instructions when executed on the one or more processors:

generate a first representation of the plurality of element groups, each element group being represented within the first representation as a respective two-dimensional block whose size is proportional to the combined size of the text image elements of the element group; and

obtain the numerical value for the particular element group from a range of numerical values based at least in part on a mapping between a range of sizes of the two-dimensional blocks of the first representation and the range of numerical values.

18. The storage medium as recited in claim 17, wherein the instructions when executed on the one or more processors:

generate, based at least in part on the first representation, an intermediate encoding of a size of the particular element group; and

determine the numerical value based at least in part on the intermediate encoding.

19. The storage medium as recited in claim 18, wherein the intermediate encoding comprises a color-coded representation of the particular element group.

20. The storage medium as recited in claim 17, wherein a particular two-dimensional block representing the particular element group in the first representation has a shape other than a rectangle.

21. The storage medium as recited in claim 20, wherein to obtain the numerical value, the instructions when executed on the one or more processors:

determine an angle between two sides of the particular two-dimensional block to obtain a metric of the size of the particular element group.

22. The storage medium as recited in claim 16, wherein the at least one delimiter belongs to a set of delimiters including a character delimiter, a word delimiter, a paragraph delimiter, and a page delimiter, wherein the numerical representation comprises a numerical encoding of at least one delimiter of the set of delimiters.

23. The storage medium as recited in claim 16, wherein the instructions when executed on the one or more processors:

in response to a comparison request from a client,

compare the fingerprint representing text contents of the digitized image object to a second fingerprint representing text contents of a second digitized image object, and

provide a metric of similarity between the respective text contents of the digitized image object and the second digitized image object, based at least in part on the comparison of the fingerprint and the second fingerprint.

24. The storage medium as recited in claim 16, wherein the digitized image object is obtained by generating an image of at least a portion of a particular document, wherein the instructions when executed on the one or more processors:

in response to a client search request, identify, using the fingerprint as a search parameter, a corresponding document from a collection of documents for which respective fingerprints are available, wherein the fingerprint of the corresponding document meets a similarity criterion with respect to the fingerprint of the particular document.

25. The storage medium as recited in claim 16, wherein the at least one delimiter comprises a plurality of delimiters, wherein the instructions when executed on the one or more processors:

implement one or more programmatic interfaces enabling a client to specify one or more of;

(a) a range of numerical values to be used for the numerical representation, or (b) a sensitivity property of a delimiter of the plurality of delimiters.

26. The storage medium as recited in claim 16, wherein the instructions when executed on the one or more processors:

implement a programmatic interface enabling a client to request, from within an e-mail client program, a generation of a fingerprint for a document received as an e-mail attachment.

27. The storage medium as recited in claim 16, wherein the instructions when executed on the one or more processors:

obtain one or more metrics indicative of one or more of;

(a) resource usage associated with generating fingerprints for a plurality of images obtained from text-containing documents, or (b) a client satisfaction level associated with a use of fingerprints for document comparison and search; and

modify, based at least in part on the one or more metrics, at least one of;

(a) a property of a particular delimiter used in the detection of element groups, or (b) a range of numerical values used for the numerical representation.

28. The storage medium as recited in claim 16, wherein the digitized image object is obtained by generating an image of at least a portion of a particular document comprising a plurality of document sections, wherein the instructions when executed on the one or more processors:

generate a plurality of additional fingerprints, wherein each fingerprint represents text contents of a respective document section of the plurality of document sections;

store metadata identifying the respective document section for each of the plurality of additional fingerprints; and

utilize the metadata to respond to a comparison request specifying a particular document section of the particular document.

29. The storage medium as recited in claim 16, wherein the digitized image object is generated by a camera incorporated within a computing device that comprises the one or more processors.

30. The storage medium as recited in claim 16, wherein the digitized image object is obtained in response to a request to display a document on a viewing interface.