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

• US 20110035656A1
• Filed: 02/18/2010
• Published: 02/10/2011
• Est. Priority Date: 02/18/2009
• Status: Active Grant

• Current Assignee: Kyocera Corporation
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: King, Martin T., Smith, Michael J., Stephens, Redwood, Sanvitale, Mark, Peterson, Jesse, Mannby, Claes-Fredrik
• Granted Patent: US 8,418,055 B2
• Time in Patent Office: Days
• 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 in a computing system for generating a signature for a rendered document, the method comprising:

creating an index for the rendered document that stores entries associated with words in the rendered document, wherein each of the entries contains a value for the word associated with the entry, the value representing the word relative to other words in the rendered document; and

building an identifier for the rendered document based on the representative values contained in the index.

2. The method of claim 1, wherein the representative values are associated with a frequency of instances of the words in the rendered document.

3. The method of claim 1, wherein the representative values are associated with absolute positions of the words in the rendered document.

4. The method of claim 1, wherein the representative values are associated with relative positions of the words in 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 corpus of documents for documents associated with identifiers that at least partially match the identifier for the rendered document; and

identifying one or more documents associated with identifiers that match the identifier for the rendered document.

7. The method of claim 1, wherein building an identifier for the rendered document based on the representative values contained in the index includes ordering a sequence of representative values based on absolute positions of their associated words in the document.

8. The method of claim 1, wherein building an identifier for the rendered document based on the representative values contained in the index includes ordering a sequence of representative values based on positional offsets of their associated words in the document.

9. A computer-readable medium, whose contents, when executed by a computing system, cause the computing system to generate a signature for a rendered document, the method comprising:

creating an index for the rendered document that stores entries associated with words in the rendered document, wherein each of the entries contains a value for the word associated with the entry, the value representing the word relative to other words in the rendered document; and

building an identifier for the rendered document based on the representative values contained in the index.

10. The computer-readable medium of claim 9, wherein the representative values are associated with a frequency of instances of the words in the rendered document.

11. The computer-readable medium of claim 9, wherein the representative values are associated with absolute positions of the words in the rendered document.

12. The computer-readable medium of claim 9, wherein the representative values are associated with relative positions of the words in the rendered document.

13. The computer-readable medium of claim 9, 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.

14. The computer-readable medium of claim 9, further comprising:

querying a corpus of documents for documents associated with identifiers that at least partially match the identifier for the rendered document; and

identifying one or more documents associated with identifiers that match the identifier for the rendered document.

15. The computer-readable medium of claim 9, wherein building an identifier for the rendered document based on the representative values contained in the index includes ordering a sequence of representative values based on absolute positions of their associated words in the document.

16. The computer-readable medium of claim 9, wherein building an identifier for the rendered document based on the representative values contained in the index includes ordering a sequence of representative values based on positional offsets of their associated words in the document.

17. A system for identifying a document, the system comprising:

a capture component, wherein the capture component is programmed to capture a subset of text from a rendered document;

an index component, wherein the index component is programmed to generate an index for the rendered document using the captured text, the generated index including values representing the text in rendered document relative to other text in the rendered document;

an identifier component, wherein the identifier component is programmed to generate an identifier that is based on the values in the generated index;

a document identification component, wherein the document identification component is programmed to identify a group of candidate documents that have identifiers similar to the generated identifier;

a constraint component, wherein the constraint component is programmed to apply one or more constraints to the group of candidate documents; and

a document selection component, wherein the document selection component is programmed to select one of the candidate documents based on the applied constraints.

18. The system of claim 17, wherein the values representing the text in rendered document relative to other text in the rendered document include values that represent a frequency of the text in the rendered document.

19. The system of claim 17, wherein the values representing the text in rendered document relative to other text in the rendered document include values that represent absolute positions of the text in the rendered document.

20. The system of claim 17, wherein the values representing the text in rendered document relative to other text in the rendered document include values that represent relative positions of the text in the rendered document