Method and apparatus for computer understanding and manipulation of minimally formatted text documents

• US 5,164,899 A
• Filed: 05/01/1989
• Issued: 11/17/1992
• Est. Priority Date: 05/01/1989
• Status: Expired due to Term

• Current Assignee: Oath Inc. (Verizon Communications Inc.)
• Original Assignee: Resumix, Inc. (Randstad NV)
• Inventors: Tokuda, Lance, Sobotka, David, Inn, Yul J., Leung, Ka L.
• Primary Examiner(s): Shaw, Dale M.
• Assistant Examiner(s): Bodendorf, Andrew
• Application Number:
  US07/345,930
• Time in Patent Office: 1,296 Days
• Field of Search: 364/200, 364/900, 364/419
• US Class Current: 704/9
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique
• CPC Class Codes: G06V 30/416 Extracting the logical structure, e.g. chapters, sections or page numbers; Identifying elements of the document, e.g. authors

Abstract

A method and apparatus which enables a computer to understand and manipulate minimally formatted text of such documents as resumes, purchase order forms, insurance forms, bank statements and similar items is disclosed. The documents are digitized by an optical scanner and translated into ASCII text by an optical character reader. The invention manipulates the digital image of the document to find blocks of contiguous text. After separating the text by block, each block is converted into an ASCII character file. Next, these files are processed by a Grammar, which uses pattern matching techniques and syntax rules to enable the host computer to understand the text. After further manipulation by the invention, the text is either stored or outputted in a form which greatly facilitates its use and readability. In this manner documents whose information content is partially location dependent can be understood despite the fact that the documents'"'"' text is written using English language phrases with little or no grammatical structure.

Claims

1. An apparatus for analyzing a text document on a computer having a memory, said text document comprising one or more blocks of contiguous text, said blocks of contiguous text having one or more boundaries, said apparatus comprising:

digital imaging means for scanning the text document and for converting the text document into a matrix of picture elements representing a digital image of the text document;

spatial analysis means coupled to the digital imaging means for scanning the matrix of picture elements in two dimensions to identify horizontal and vertical boundaries of the blocks of contiguous text in the digital image;

character recognition means coupled to the spatial analysis means for converting the blocks of contiguous text into a text file, said text file comprising word patterns and block identifiers;

a grammar stored in said memory comprising predetermined word patterns and block identifiers;

extractor means coupled to the memory and character recognition means for matching the word patterns and block identifiers contained in the grammar with the word patterns and block identifiers in the text file; and

formatting means coupled to the extractor means for generating output in a predefined pattern using the matched word patterns and block identifiers.

2. The apparatus of claim 1, wherein each picture element is represented by a binary value, the spatial analysis means further comprising:

vertical boundary detection means for determining blocks of text which are vertically separated from one or more other blocks of text by summing a portion of pixel values in one or more rows of the matrix and identifying rows having sums above a first predetermined threshold; and

horizontal boundary detection means for determining blocks of text which are horizontally separated from one or more other blocks of text by summing a portion of pixel values in one or more columnar strips of the matrix, wherein a columnar strip has a width of a predetermined number of matrix columns, wherein the horizontal boundary detection means identifies columnar strips having sums above a second predetermined threshold.

3. The apparatus of claim 1, wherein the block identifiers indicate whether the block is a header block or a text block.

4. A method executing on a computer to analyze a text document comprising one or more blocks of contiguous text, said blocks of contiguous text having one or more boundaries, the method comprising the steps of:

making a digital image of the printed document, said digital image comprising a matrix of picture elements;

scanning the digital image in two dimensions to identify horizontal and vertical boundaries of the blocks of contiguous text in the digital image;

converting the blocks of contiguous text into a text file, the text file comprising word patterns and block identifiers;

storing a grammar in the computer, said grammar comprising predetermined word patterns and block identifiers;

matching the word patterns and block identifiers from the text file with the word patterns and block identifiers in the computer data base; and

generating output in a predefined format using the matched word patterns and block identifiers.

5. The method of claim 4 wherein the output is generated as printed output.

6. The method of claim 4 wherein the output is generated as computer storable digital data.

7. The method of claim 4 wherein the block identifiers indicate whether the block is a header block or text block.

8. The method of claim 4 wherein the step of converting the blocks comprises the steps of passing the digital image of the blocks through an optical character reader.

9. The method of claim 4 wherein the step of storing the computer data base further comprises:

determining information to be obtained from the document;

choosing individual words, word groups and alphanumeric groups which embody the information; and

organizing the word, word groups and alphanumeric groups so that they are in grammatical relationship to one another.

10. The method of claim 4 wherein the step of generating output comprises filling in predefined templates using the words, word groups and alphanumeric groups extracted from the document.

11. The method of claim 4 wherein each picture element is represented by a binary value, the step of scanning the digital image further comprising the steps of:

summing a portion of pixel values in one or more rows of the matrix and identifying rows having sums above a first predetermined threshold; and

summing a portion of pixel values in one or more columnar strips of the matrix, wherein a columnar strip has a width of a predetermined number of matrix columns, and identifying columnar strips having sums above a second predetermined threshold.

12. The method of claim 4, wherein the step of scanning the digital image in two dimensions to identify horizontal and vertical boundaries of the blocks of contiguous text is performed both before and after the step of converting the blocks into a text file.