Extracting information from symbolically compressed document images

• US 6,658,151 B2
• Filed: 04/08/1999
• Issued: 12/02/2003
• Est. Priority Date: 04/08/1999
• Status: Expired due to Fees

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Hull, Jonathan J., Lee, Dar-Shyang
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): DESIRE, GREGORY M
• Application Number:
  US09/289,772
• Publication Number:
  US 20020150300A1
• Time in Patent Office: 1,699 Days
• Field of Search: 382/155-156, 382/159-160, 382/177, 382/224-225, 382/228-232, 382/235, 382/244, 707/5, 707/102, 704/1, 704/2, 704/9, 704/10
• US Class Current: 382/229
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/262 using context analysis, e.g. lexical, syntactic or semantic context
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99939 Privileged access

Abstract

A method and apparatus for extracting information from symbolically compressed document images. A deciphering module generates first and second text strings by deciphering respective sequences of template identifiers in first and second symbolically compressed document images. A conditional n-gram module receives the first and second text strings from the deciphering module and extracts n-gram terms therefrom based on a predicate condition. A comparison module generates a measure of similarity between the first and second symbolically compressed document images based on the n-gram terms extracted by the conditional n-gram module.

Claims

1. A method comprising:

representing an input document image as a symbolically compressed representation with a sequence of template identifiers;

replacing the template identifiers with alphabet characters according to language statistics to generate a text string representative of text in the input document image; and

extracting conditional n-gram indexing terms from the text string by selecting alphabet characters in the text stream that satisfy a predicate that indicates a subset of combinations of characters in the text string.

2. The method of claim 1 wherein the conditional n-grams are trigrams.

3. A The method of claim 1 wherein the predicate is a condition that substantially all selected characters follow respective spaces in the text string.

4. The method of claim 1 further comprising comparing the input document image with a plurality of symbolically compressed document images in a database based on the conditional n-gram indexing terms to determine whether one or the plurality of documents matches the input document image.

5. The method of claim 4 further comprising determining whether the one of the plurality of document images is a confidential document if the one of the plurality of document images matches the input document image.

6. The method of claim 5 further comprising prompting a user for authorization before operating on the input document image if the one of the plurality of document images matches the input document image and is a confidential document.

7. The method of claim 4 further comprising determining whether the one of the plurality of document images forms a sub-portion of an encompassing document image if the one of the plurality of document images matches the input document image.

8. The method of claim 4 further comprising prompting the user to select between hardcopy output of the one of the plurality of document images or the encompassing document image if the one of the plurality of document images matches the input document image and forms a sub-portion of a larger document image.

9. The method of claim 4 further comprising determining whether the one of the plurality of document images is copyrighted if the one of the plurality of document images matches the input document image.

10. The method of claim 1 wherein replacing the template identifiers with alphabet characters comprises replacing at least one of the template identifiers with an alphabet character selected according to a sequence of at least two alphabet characters selected to replace template identifiers that precede the at least one template identifier in the sequence of template identifiers.

11. The method of claim 1 wherein replacing the template identifiers with alphabet characters comprises replacing at least one of the template identifiers with an alphabet character selected according to a sequence of all alphabet characters selected to replace template identifiers that precede the at least one template identifier in the sequence of template identifiers.

12. The method of claim 1 wherein replacing the template identifiers with alphabet characters according to language statistics comprises replacing the template identifiers with alphabet characters selected according to a hidden Markov model.

13. The method of claim 1 wherein replacing template identifiers with alphabet characters according to language statistics comprises solving a substitution cipher by mapping the alphabet characters to the template identifiers based at least partly on frequency of occurrence of the template identifiers.

14. The method of claim 1 wherein the predicate that indicates a subset of combinations of characters in the text string comprises selecting only alphabet characters that follow a space in the text string.

15. A The method of claim 1 wherein the predicate that indicates a subset of combinations of characters in the text string comprises selecting only alphabet characters that precede a space in the text string.

16. The method of claim 1 wherein the predicate that indicates a subset of combinations of characters in the text string comprises selecting only every mth alphabet character.

17. The method of claim 1 wherein the predicate that indicates a subset of combinations of characters in the text string comprises selecting only alphabet characters at predetermined spatial locations within the document.

18. A document processing system comprising:

a deciphering module to generate a first text string based on a sequence of template identifiers in a first symbolically compressed document image and to generate a second text string based on a sequence of template identifiers in a second symbolically compressed document image;

a conditional n-gram module coupled to receive the first and second text strings from the deciphering module, the conditional n-gram module being configured to extract n-gram indexing terms from the first and second text strings based on a predicate condition that indicates a subset of combinations of characters in the text string; and

a comparison module to generate a measure of similarity between the first and the second symbolically compressed document image based on the indexing terms extracted by the conditional n-gram module.

19. The document processing system of claim 18 wherein at least one of the deciphering module and the conditional n-gram module is implemented by a programmed processor.

20. The document processing system of claim 18 wherein the deciphering module generates the first text string by applying a hidden Markov model to the sequence of template identifiers in the first symbolically compressed document image.

21. The document processing system of claim 18 wherein the second symbolically compressed document image is obtained from a database of symbolically compressed document images.

22. The document processing system of claim 18 wherein the data processing system further comprises a scanning and compressing module that is configured to generate a digitized version of a source document and to perform symbolic compression of the digitized version to produce the first symbolically compressed document image.

23. The document processing system of claim 22 wherein the document processing system is a document copying system.

24. The document processing system of claim 22 wherein the document processing system is a facsimile transmission system.

25. The document processing system of claim 18 further comprising a second interface to couple the document processing system to a database of symbolically compressed document images and associated indexing terms, and wherein the conditional n-gram module is configured to store the n-gram indexing terms extracted from the second text string in the database.

26. The document processing system of claim 25 wherein the comparison module is configured to receive the n-gram indexing terms extracted from the first text string from the conditional n-gram module and to receive the n-gram indexing terms extracted from the second text string from the database via the second interface.

27. The document processing system of claim 18 wherein the measure of similarity is used to determine whether the first and second symbolically compressed document images match.

28. The document processing system of claim 27 wherein the data processing system further comprises a user interface to prompt a user to select between a decompressed version of the first symbolically compressed document image and a decompressed version of a third symbolically compressed document image that encompasses the second symbolically compressed document image if the first and second symbolically compressed document images match, the document processing system further comprising an output module to output the decompressed version of the first symbolically compressed document image or the decompressed version of a third symbolically compressed document image according to input received via to user interface.

29. The document processing system of claim 27 wherein the data processing system further comprises a security module to determine if the second symbolically compressed document image is a confidential document based on attribute information associated with the second symbolically compressed document image, the security module being configured to prompt a user to enter authorization information before permitting output of the first symbolically compressed document image if the second document image is a confidential document and if the first and second document images match.

30. The document processing system of claim 29 further comprising a printer configured to receive a signal from the security module indicating whether to print a decompressed version of the first symbolically compressed document image.

31. The document processing system of claim 29 further comprising an transmission module to receive a signal from the security module indicating whether to transmit the first symbolically compressed document image.

32. The document processing system of claim 27 wherein the data processing system further comprises an monitoring module to determine if the seconds symbolically compressed document image is a copyrighted document.

33. The document processing system of claim 32, wherein the monitoring module is configured to automatically charge a copyright license fee for output of a decompressed version of the first symbolically document image if the second symbolically compressed document image is a copyrighted document and if the first and second symbolically compressed document images match.

34. The document processing system of claim 18 wherein the predicate condition that indicates a subset of combinations of characters in the text string comprises selecting only alphabet characters that follow a space in the text string.

35. The document processing system of claim 18 wherein the predicate condition that indicates a subset of combinations of characters in the text string comprises selecting only alphabet characters that precede a space in the text string.

36. The document processing system of claim 18 wherein the predicate condition that indicates a subset of combinations of characters in the text string comprises selecting only every mth alphabet character.

37. The document processing system of claim 18 wherein the predicate condition that indicates a subset of combinations of characters in the text string comprises selecting only alphabet characters at predetermined spatial locations within the document.

38. An article of manufacture including one or more computer-readable media that embody a program of instructions to generate a text string from an input document image as a symbolically compressed representation with a sequence of template identifiers, wherein the program of instructions, when executed by one or more processors in one or more processing systems, causes the one or more processors to replace the template identifiers with alphabet characters according to language statistics to generate a text string representative of text in the input document image and to extract one or more conditional n-gram indexing structures from the text string by selecting alphabet characters in the text string that satisfy a predicate that indicates a subset of combinations of characters in the text string.

39. The article of claim 38 wherein the one or more computer-readable media include one or more non-volatile storage devices.

40. The article of claim 38 wherein the one or more computer-readable media include a propagated data signal.

41. The article of claim 38 where in n comprises being an integer.