Identifying a document by performing spectral analysis on the contents of the document

• US 8,418,055 B2
• Filed: 02/18/2010
• Issued: 04/09/2013
• Est. Priority Date: 02/18/2009
• Status: Active Grant

• Current Assignee: Kyocera Corporation
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: King, Martin T., Stephens, Redwood, Mannby, Claes-Fredrik, Peterson, Jesse, Sanvitale, Mark, Smith, Michael J.
• Primary Examiner(s): Hutton, Jr., Doug
• Assistant Examiner(s): DYER, ANDREW R
• Application Number:
  US12/660,154
• Publication Number:
  US 20110035656A1
• Time in Patent Office: 1,146 Days
• Field of Search: 715/230, 715/231, 715/234, 707/711
• US Class Current: 715/234
• CPC Class Codes: G01B 11/00 Measuring arrangements characterised by the use of optical techniques
• CPC Class Codes: G01B 11/14 for measuring distance or clearance between spaced objects or spaced apertures G01B11/26 takes precedence; rangefinders G01C3/00
• CPC Class Codes: G06F 16/434 using image data, e.g. images, photos, pictures taken by a user
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 40/103 Formatting, i.e. changing of presentation of documents automatic justification G06F40/189; automatic line break hyphenation G06F40/191
• CPC Class Codes: G06F 40/169 Annotation, e.g. comment data or footnotes
• CPC Class Codes: G06F 40/174 Form filling; Merging
• CPC Class Codes: G06T 2207/30176 Document
• CPC Class Codes: G06T 7/20 Analysis of motion motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/43, H04N19/51
• CPC Class Codes: G06T 7/70 Determining position or orientation of objects or cameras camera calibration G06T7/80
• CPC Class Codes: G06V 30/224 of printed characters having additional code marks or containing code marks
• CPC Class Codes: G06V 30/40 Document-oriented image-based pattern recognition
• CPC Class Codes: H04N 1/00307 with a mobile telephone apparatus constructional features of portable telephone sets H04M1/0202; mobile radio systems H04W84/00
• CPC Class Codes: H04N 1/00331 with an apparatus performing optical character recognition character recognition G06V30/10
• CPC Class Codes: H04N 1/00355 Mark-sheet input sensing record carriers G06K7/00; character recognition G06V30/10; document-oriented image-based pattern recognition G06V30/40
• CPC Class Codes: H04N 1/0036 Alphanumeric symbols
• CPC Class Codes: H04N 1/00374 on the same page as at least a part of the image
• CPC Class Codes: H04N 1/00408 Display of information to the user, e.g. menus
• CPC Class Codes: H04N 1/00469 with enlargement of a selected area of the displayed information
• CPC Class Codes: H04N 1/00689 Presence
• CPC Class Codes: H04N 1/00737 : using the scanning elements as detectors
• CPC Class Codes: H04N 1/00758 : using a prescan
• CPC Class Codes: H04N 1/00782 : Initiating operations
• CPC Class Codes: H04N 1/19594 : using a television camera or a still video camera
• CPC Class Codes: H04N 1/32144 : embedded in the image data, i.e. enclosed or integrated in the image, e.g. watermark, super-imposed logo or stamp
• CPC Class Codes: H04N 2201/0084 : Digital still camera
• CPC Class Codes: H04N 2201/0096 : Portable devices
• CPC Class Codes: H04N 2201/3249 : data relating to a linked page or object, e.g. hyperlink
• CPC Class Codes: H04N 2201/3266 : of text or character information, e.g. text accompanying an image H04N2201/3226 takes precedence
• CPC Class Codes: H04N 23/64 : Computer-aided capture of images, e.g. transfer from script file into camera, check of taken image quality, advice or proposal for image composition or decision on when to take image
• CPC Class Codes: H04N 23/66 : Remote control of cameras or camera parts, e.g. by remote control devices

Abstract

A system and method for identifying a document based on a spectral analysis of the text of the document is described. In some examples, the system generates a document identifier for a rendered document based on assigning values to words in the rendered document, such as values associated with the frequency of use of the word by the rendered document, the absolute or relative position of the word in the rendered document, and so on. The system may use the document identifier to generate a group of documents having similar document identifiers, and choose a likely match from the group of documents based on predictive analysis.

Claims

1. A method, comprising:

creating an index, with one or more entries, for a rendered document at a computer system, wherein each of the one or more index entries contains a word and one or more values, wherein each value represents a characteristic of the word;

selecting a subset of the one or more index entries from the index using the computer system;

creating an ordered sequence of values from the selected subset of the one or more index entries, wherein each value comprises a position of the entry relative to another entry in the selected subset of the one or more index entries;

building an identifier for the rendered document at the computer system based on the ordered sequence of the values, wherein each index entry in the subset satisfies an identifier rule for a document identifier; and

locating an electronic counterpart to the rendered document based on the identifier for the rendered document using the computer system.

2. The method of claim 1, wherein a value of an index entry is associated with a frequency of instances of the word contained with the index entry within the rendered document.

3. The method of claim 1, wherein a value of an index entry is associated with an absolute position of the word contained with the index entry within the rendered document.

4. The method of claim 1, wherein a value of an index entry is associated with a relative position of the word contained with the index entry within the rendered document.

5. The method of claim 1, further comprising:

performing a hash function on the identifier for the rendered document to generate a hash value for the rendered document; and

designating the hash value as the identifier of the rendered document.

6. The method of claim 1, further comprising:

querying a plurality of documents to identify one or more documents, each of the one or more documents associated with an identifier that at least partially matches the identifier for the rendered document.

7. The method of claim 1, wherein the ordered sequence of the values from the selected subset of the one or more index entries in the selected subset comprises a sequence of the values of the one or more index entries in the selected subset that is ordered based on absolute positions in the rendered document of the words contained with the one or more index entries in the selected subset.

8. The method of claim 1, wherein the ordered sequence of the values from the selected subset of the one or more index entries in the selected subset comprises a sequence of the values of the one or more index entries in the selected subset that is ordered based on positional offsets in the rendered document of the words contained with the index entries in the selected subset.

9. The method of claim 1, wherein the identifier rule comprises a rule to select index entries corresponding to words that appear N times or fewer within the rendered document, and wherein N >

0.

10. The method of claim 1, wherein building the identifier comprises determining offsets between the values of the ordered sequence of the values of the one or more index entries in the selected subset.

11. The method of claim 1, wherein building the identifier comprises:

determining an ordinal sequence for the words in the ordered subset of the one or more index entries;

replacing each word in the ordinal sequence with a replacement value representing an initial appearance of the word within the rendered document; and

building the identifier using the replacement values.

12. An article of manufacture comprising a non-transitory computer-readable medium having instructions stored thereon that, if the instructions are executed by a computer, cause the computer to perform functions comprising:

creating an index, with one or more entries, for a rendered document, wherein each of the one or more index entries contains a word and one or more values, wherein each value represents a characteristic of the word;

selecting a subset of the one or more index entries from the index;

creating an ordered sequence of values from the selected subset of one or more index entries, wherein each value comprises a position of the entry relative to another entry in the selected subset of the one or more index entries;

building an identifier for the rendered document based on the ordered sequence of the values, wherein each index entry in the subset satisfies an identifier rule for a document identifier; and

locating an electronic counterpart to the rendered document based on the identifier for the rendered document.

13. The article of manufacture of claim 12, wherein a value of an index entry is associated with a frequency of instances of the word contained with the index entry within the rendered document.

14. The article of manufacture of claim 12, wherein a value of an index entry is associated with an absolute position of the word contained with the index entry within the rendered document.

15. The article of manufacture of claim 12, wherein a value of an index entry is associated with a relative position of the word contained with the index entry within the rendered document.

16. The article of manufacture of claim 12, wherein the functions further comprise:

performing a hash function on the identifier for the rendered document to generate a hash value for the rendered document; and

designating the hash value as the identifier of the rendered document.

17. The article of manufacture of claim 12, wherein the functions further comprise:

querying a plurality of documents to identify one or more documents, each of the one or more documents associated with an identifier that at least partially matches the identifier for the rendered document.

18. The article of manufacture of claim 12, wherein the ordered sequence of the values from the selected subset of the one or more index entries in the selected subset comprises a sequence of the values of the one or more index entries in the selected subset that is ordered based on absolute positions in the rendered document of the words contained with the one or more index entries in the subset.

19. The article of manufacture of claim 12, wherein the ordered sequence of the values from the selected subset of the one or more index entries in the selected subset comprises a sequence of the values of the one or more index entries in the selected subset that is ordered based on positional offsets in the rendered document of the words contained with the index entries in the selected subset.