Automatic method of generating thematic summaries from a document image without performing character recognition

• US 5,848,191 A
• Filed: 12/14/1995
• Issued: 12/08/1998
• Est. Priority Date: 12/14/1995
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Chen, Francine R., Bloomberg, Dan S., Tukey, John W.
• Primary Examiner(s): SHALWALA, BIPIN H
• Application Number:
  US08/572,848
• Time in Patent Office: 1,090 Days
• Field of Search: 382/206, 382/229, 382/176, 382/177, 382/178, 382/179, 382/195, 382/180, 395/793, 395/751, 395/759, 704/1
• US Class Current: 382/229
• CPC Class Codes: G06V 30/226 of cursive writing
• CPC Class Codes: G06V 30/246 using linguistic properties, e.g. specific for English or German language
• CPC Class Codes: G06V 30/414 Extracting the geometrical structure, e.g. layout tree; Block segmentation, e.g. bounding boxes for graphics or text

Abstract

A method of automatically generating a thematic summary from a document image without performing character recognition to generate an ASCII representation of the document text. The method begins with decomposition of the document image into text blocks, and text lines. Using the median x-height of text blocks the main body of text is identified. Afterward, word image equivalence classes and sentence boundaries within the blocks of the main body of text are determined. The word image equivalence classes are used to identify thematic words. These, in turn are used to score the sentences within the main body of text, and the highest scoring sentences are selected for extraction.

Claims

1. A processor implemented method of generating a thematic summary of a document image without performing character recognition using a processor, the document including a first multiplicity of sentences and a second multiplicity of word occurrences, the processor implementing the method by executing instructions stored in electronic form in a memory coupled to the processor, the processor implemented method comprising the steps of:

a) analyzing the document image to identify sentence boundaries;

b) analyzing the document image to identify a plurality of word image equivalence classes, each word image equivalence class including at least one word occurrence of the second multiplicity of word occurrences;

c) selecting as thematic word images a first number of word image equivalence classes, the first number being less than a second number of thematic sentences to be extracted;

d) scoring each sentence of the first multiplicity of sentences based upon occurrence of thematic word images in each sentence; and

e) selecting the second number of thematic sentences from the first multiplicity of sentences based upon the score of each sentence.

2. The processor implemented method of claim 1 further comprising the step of:

f) presenting images of the thematic sentences to the user of the processor in an order in which the thematic sentences occur in the document image.

3. The processor implemented method of claim 1 wherein step d) comprises incrementing the score of each sentence for each thematic word image occurring in the sentence by an amount related to the frequency of occurrence of the thematic word image within the document.

4. The method of claim 1 prior to step c) further comprising the steps of:

d) receiving the second number from an input device coupled to the processor.

5. The processor implemented method of claim 4 wherein the first number is at least three.

6. A processor implemented method of generating a thematic summary of a document image without performing character recognition using a processor, the document including a first multiplicity of sentences and a second multiplicity of word occurrences, the processor implementing the method by executing instructions stored electronically in a memory coupled to the processor, the processor implemented method comprising the steps of:

a) analyzing the document image to identify sentence boundaries of the first multiplicity of sentences;

b) analyzing the document image to identify a plurality of word image equivalence classes, each word image equivalence class including at least one word occurrence of the second multiplicity of word occurrences, each word image equivalence class having a bounding box, each bounding box having a width;

c) determining a number of times each word image equivalence class occurs in the document;

d) identifying drop words within the word image equivalence classes based upon their bounding box width and the number of times each word image equivalence class occurs in the document;

e) generating a list of content words by eliminating the drop words from the word image equivalence classes;

f) selecting as thematic word images a first number of the word equivalence classes from the list of content words based upon the number of times each content word occurs in the document;

g) scoring each sentence of the first multiplicity of sentences that includes a thematic word image based upon occurrences of thematic word images within each sentence; and

h) selecting as thematic sentences a second number of the first multiplicity of sentences based upon the sentence scores.

7. The computer implemented method of claim 6 wherein step g) comprises incrementing the score of each sentence for each thematic word image occurring in the sentence by an amount related to the frequency of occurrence of the thematic word image within the document.

8. The method of claim 6 prior to step f) further comprising the steps of:

i) receiving the second number from an input device coupled to the processor.

9. The processor implemented method of claim 8 wherein the first number is at least three.

10. The processor implemented method of claim 6 wherein step d) comprises identifying drop word images based upon the number of times each word image equivalence class appears as a first non-short word in a sentence of the first multiplicity of sentences.

11. An article of manufacture comprising:

a) a memory; and

b) instructions stored in the memory for a method of generating a thematic summary of a document image without performing character recognition using a processor coupled to the memory, the document including a first multiplicity of sentences and a second multiplicity of word occurrences, the method comprising the steps of;

1) analyzing the document image to identify sentence boundaries;

2) analyzing the document image to identify word image equivalence classes, each word image equivalence class including at least one word occurrence of the second multiplicity of word occurrences;

3) selecting as thematic word images a first number of word image equivalence classes, the first number of thematic word images being less than a second number of thematic sentences to be extracted;

4) scoring each sentence of the first multiplicity of sentences based upon occurrence of thematic word images in each sentence; and

5) selecting the second number of thematic sentences from the first multiplicity of sentences based upon the score of each sentence.

12. A system for generating a thematic summary from a document image without performing character recognition, the system comprising:

a) a scanner for generating an electronic representation of the document image;

b) a processor coupled to the scanner;

c) a memory coupled to the processor for storing instructions for generating a thematic summary from the electronic representation of the document image, the instructions representing the steps of;

1) analyzing the document image to identify sentence boundaries;

2) analyzing the document image to identify a plurality of word image equivalence classes, each word image equivalence class including at least one word occurrence of the second multiplicity of word occurrences within the document;

3) selecting as thematic word images a first number of word image equivalence classes, the first number being less than a second number of thematic sentences to be extracted;

4) scoring each sentence of the first multiplicity of sentences based upon occurrence of thematic word images in each sentence; and

5) selecting the second number of thematic sentences from the first multiplicity of sentences based upon the score of each sentence.