Automatic method of identifying drop words in a document image without performing character recognition

• US 5,850,476 A
• Filed: 12/14/1995
• Issued: 12/15/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., Tukey, John W.
• Primary Examiner(s): Coles, Edward L.
• Assistant Examiner(s): Lee, Cheukfan
• Application Number:
  US08/572,847
• Time in Patent Office: 1,097 Days
• Field of Search: 382/177, 382/203, 382/173, 382/179, 382/187, 382/165, 395/144, 395/145, 395/146
• US Class Current: 382/177
• CPC Class Codes: G06V 30/226 of cursive writing
• CPC Class Codes: G06V 30/40 Document-oriented image-based pattern recognition

Abstract

A method of automatically identifying drop words in a document image without performing character recognition to generate an ASCII representation of the document text. First, the document image is analyzed to identify word equivalence classes, each of which represents at least one word of the multiplicity of words included in the document. Second, for each word equivalence class, the likelihood that it is not a drop word is determined. Third, document length is analyzed to determine whether the document is short. For a short document, the number of word equivalence classes identified as drop words based upon their likelihood is proportional to document length. For long documents, a fixed number of word equivalence classes are identified as drop words based upon the likelihood that they are not drop words.

Claims

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

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

b) for each word equivalence class determining the likelihood that word equivalence class is a drop word;

c) designating a number of the word equivalence classes as drop words based upon the likelihood that the word equivalence classes are drop words.

2. The method of claim 1 wherein each word equivalence class has a bounding box having a width and wherein the determination of step b) is based upon the width of the bounding boxes for each word equivalence class.

3. The method of claim 2 further comprising the step of:

f) determining the number of occurrences of each word equivalence class in the document; and

wherein step b) includes considering the number of times each word equivalence class occurs in the document.

4. The method of claim 3 further comprising the step of:

g) identifying sentence boundaries within the document image;

h) determining a number of times each word equivalence class is the first non-short word of a sentence; and

wherein the determination step b) is further based upon the number of times each word equivalence class is the first non-short word of a sentence.

5. The method of claim 4 wherein step b) comprises:

determining the relative likelihood that a word equivalence class is not a drop word using the formula;

space="preserve" listing-type="equation">L=(ω

.sub.i /ω

.sub.the)*(1+b.sub.i /f.sub.i)+(c*W/f.sub.i)

where;

L is the indicator of the likelihood a word is not a drop word;

ω

_i is the width of the word i in pixels;

ω

_the is the width of the word "the" in pixels;

b_i is the number of times the word i occurs as the first non-short word of a sentence in one of the conforming text blocks;

f_i is the number of occurrences of the word i in the conforming text blocks;

C is a constant weighting factor between the two terms; and

W is the total number of word occurrences in the document.

6. The method of claim 1 further comprising the step of:

f) determining the number of occurrences of each word equivalence class in the document; and

wherein step b) includes considering the number of times each word equivalence class occurs in the document.

7. The method of claim 1 further comprising the step of:

f) identifying sentence boundaries within the document image;

g) determining a number of times each word equivalence class is the first non-short word of a sentence; and

wherein the determination step b) is further based upon the number of times each word equivalence class is the first non-short word of a sentence.

8. A method of identifying drop words in a document image without performing character recognition, the document image including a first multiplicity of sentences and a second multiplicity of word occurrences, each word occurrence of the second multiplicity of word occurrences having a font size, a processor implementing the method by executing instructions stored in electronic form in a memory coupled to the processor, the method comprising the steps of:

a) identifying a dominant font size within the document image;

b) identifying sentence boundaries for sentences of the dominant font size within the document image;

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

d) for each word equivalence class determining the likelihood that word equivalence class is not a drop word based upon a width of each word equivalence class, a number of occurrences of the word equivalence class, and a number of occurrences of the word equivalence class as a first non-short word of a sentence;

e) designating a number of the word equivalence classes as drop words based upon the likelihood that the word equivalence classes are drop words.

9. The method of claim 8 wherein step d) comprises:

determining the likelihood that a word equivalence class is not a drop word using the formula;

space="preserve" listing-type="equation">L=(ω

.sub.i /ω

.sub.the)*(1+b.sub.i /f.sub.i)+(c*W/f.sub.i)

where;

L is an indicator of the likelihood a word is not a drop word;

ω

_i is the width of the word i in pixels;

ω

_the is the width of the word "the" in pixels;

b_i is the number of times the word i occurs as the first non-short word of a sentence in one of the conforming text blocks;

f_i is the number of occurrences of the word i in the conforming text blocks;

C is a constant weighting factor between the two terms; and

W is the total number of words in the document.

10. An article of manufacture comprising:

a) a memory; and

b) instructions stored in the memory for a method of identifying drop words in a document image without performing character recognition, the document image including a first multiplicity of sentences and a second multiplicity of word occurrences, method comprising the steps of;

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

2) for each word equivalence class determining the likelihood that word equivalence class is not a drop word;

3) designating a number of the word equivalence classes as drop words based upon the likelihood that the word equivalence classes are drop words.

11. An article of manufacture comprising:

a) a memory; and

b) instructions stored in the memory for a method of identifying drop words in a document image without performing character recognition, the document image including a first multiplicity of sentences and a second multiplicity of word occurrences, each word occurrence of the second multiplicity of word occurrences having a font size, the method comprising the steps of;

1) identifying a dominant font size within the document image;

2) identifying sentence boundaries for sentences of the dominant font size within the document image;

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

4) for each word equivalence class determining the likelihood that word equivalence class is not a drop word based upon a width of each word equivalence class, a number of occurrences of the word equivalence, and a number of occurrences of the word equivalence class as a first non-short word of a sentence;

5) designating a number of the word equivalence classes as drop words based upon the likelihood that the word equivalence classes are