Method and system for extracting information from a document

• US 20030215137A1
• Filed: 05/17/2002
• Published: 11/20/2003
• Est. Priority Date: 05/17/2002
• Status: Active Grant

• Current Assignee: Leidos, Inc. (Leidos Holdings, Inc.)
• Original Assignee: Science Applications International Corporation
• Inventors: Wnek, Janusz
• Granted Patent: US 7,142,728 B2
• Time in Patent Office: Days
• US Class Current: 382/181
• 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 computer-implemented method for extracting information from a population of subject documents. The method includes modeling a document structure. The modeled document structure includes at least a document component hierarchy with at least one record type. Each record type includes at least one record part type and at least one record part type comprising at least one data element type. For a subject document exhibiting at least a portion of the modeled document structure, preferred embodiments of the invention identifying data of a type corresponding to at least one modeled data element type. Identified subject document data is then associated with the corresponding modeled data element type.

Claims

1. A computer-implemented method for extracting information from a population of one or more subject documents, the method comprising:

modeling a document structure representative of the population,

the modeled document structure comprising a document component hierarchy,

the document component hierarchy comprising

at least one record type,

each record type comprising at least one record part type, and

at least one record part type comprising at least one data element type;

for a subject document exhibiting at least a portion of the modeled document structure,

identifying subject document data of a type corresponding to at least one modeled data element type and

associating the identified data with the corresponding modeled data element type.

2. The method as in claim 1:

wherein modeling a document structure further comprises, in a computer;

obtaining an imaged and recognized training document;

accepting from a user;

information regarding the document component hierarchy, and information regarding the relationship between at least one element of the document component hierarchy and a corresponding portion of the imaged and recognized training document;

specifying at least one data element type of the data component hierarchy, and its corresponding record type and line pattern, based on at least the imaged and recognized training document, the document component hierarchy, and the association information;

wherein the modeled document structure further comprises the imaged and recognized training document, each specified data element type, each specified line pattern type, and each specified record type; and

wherein identifying data of a type corresponding to at least one specified data element type comprises, in a computer;

imaging the subject document;

recognizing characters of the imaged subject document;

locating, within the imaged and recognized subject document, at least one data element of a type specified in the document model

capturing at least one data element found to be of a type specified in the document model.

3. The method as in claim 1:

wherein modeling a document structure further comprises, in a computer;

imaging a training document;

recognizing characters of the imaged training document;

accepting, from a user;

information regarding the document component hierarchy, and information regarding the relationship between at least one element of the document component hierarchy and a corresponding portion of the imaged and recognized training document;

specifying at least one data element type of the data component hierarchy, and its corresponding record type and line pattern, based on at least the imaged and recognized training document, the document component hierarchy, and the association information;

wherein the modeled document structure further comprises the imaged and recognized training document, each specified data element type, each specified line pattern type, and each specified record type; and

wherein identifying data of a type corresponding to at least one specified data element type comprises, in a computer;

imaging the subject document;

recognizing characters of the imaged subject document;

locating, within the imaged and recognized subject document, at least one data element of a type specified in the document model

capturing at least one data element found to be of a type specified in the document model.

4. The method as in claim 3:

wherein identifying data of a type corresponding to at least one specified data element type further comprises, in a computer determining a subject document line pattern for each subject document line;

wherein a line sequence pattern comprises a plurality of ordered line patterns;

wherein locating, within the imaged and recognized subject document, at least one data element of a type specified in the document model comprises;

for each record type in the document model containing a data element of interest,

locating, within the subject document, at least one of a line pattern and a line sequence pattern that corresponds to the record type,

locating the data element of interest based on its specified relationship to the structure of the record type.

5. The method as in claim 3 wherein recognizing characters of an imaged training document comprises:

performing optical character recognition (OCR) on the training document,

6. The method as in claim 3 wherein imaging a training document comprises at least one of the following:

deskewing, the training document image,

despecklizing the training document image,

horizontally aligning a target page of the training document with reference to a base page of the training document.

7. The method as in claim 5 wherein horizontally aligning one region of the training document with reference to a base region of the training document comprises:

generalizing a plurality of lines in the target page and the base page;

determining an edit distance for each generalized target page line, generalized base page line pair;

determining a target page line offset for those pairs characterized by an edit distance not greater than a threshold;

determining a target page offset as a function of the target page line offsets, and

offsetting the target page by the offset.

8. The method as in claim 3 further comprising:

assessing the degree to which the captured data element corresponds to the data element type.

9. The method as in claim 3 further comprising:

assessing the degree to which the subject document structure surrounding each identified subject document data element corresponds to the modeled document structure.

10. The method as in claim 9 wherein assessing the degree to which the subject document structure surrounding each identified subject document data element corresponds to the modeled document structure comprises:

determining a ratio of the number of data elements extracted from a subject document record and the number of data elements specified for a record of that type.

11. The method as in claim 9 wherein assessing the degree to which the subject document structure surrounding each identified subject document data element corresponds to the modeled document structure comprises:

comparing the horizontal and vertical alignment of record, record parts, and data elements of the subject document against the horizontal and vertical alignment of the corresponding types in the modeled document.

12. The method as in claim 9 wherein assessing the degree to which the subject document structure surrounding each identified subject document data element corresponds to the modeled document structure comprises:

determining a ratio of the number of data elements extracted from a subject document record part and the number of data elements specified for a record part of that type.

13. The method as in claim 3:

wherein capturing at least one data element found to be of a type specified in the document model comprises;

adjusting a capture window boundary to the dimensions of the actual data element in the subject document.

14. A method for horizontally aligning a first region of a document with a second region of a document, each region characterized by a plurality of sub-regions, the method comprising:

determining a type for each of a plurality of sub-regions in each region;

determining an edit distance for each typed first region sub-region, typed second region sub-region pair;

determining a first region sub-region offset for those pairs characterized by an edit distance not greater than a threshold;

determining a first region offset as a function of the first region sub-region offsets

offsetting the first region by the offset.

15. The method as in claim 14, wherein

each region comprises a page,

each sub-region comprises a line.

16. The method as in claim 14, wherein

determining a type for each of a plurality of sub-regions in each region comprises generalizing each sub-region.

17. The method as in claim 14, wherein

determining a first region offset as a function of the first region sub-region offsets comprises calculating the average offset between the largest cluster of similar offsets.

18. A computer program product for extracting information from a population of subject documents, the computer program product comprising:

a computer-readable medium;

a modeling module stored on the medium and operative to model a document structure,

the modeled document structure comprising a document component hierarchy,

the document component hierarchy comprising

at least one record type,

each record type comprising at least one record part type and

at least one record part type comprising at least one data element type;

an identification module, operative to identify subject document data of a type corresponding to at least one modeled data element type, and

an association module, operative to associate the identified data with the corresponding modeled data element type.

19. The computer program product as in claim 18

wherein the modeling module further comprises:

a imaging and character recognition module, operative to obtain the image and characters of a training document;

a user interface module, operative to prompt for and accept information from a user, regarding the document component hierarchy and regarding the relationship between at lease one element of the document component hierarchy and a corresponding portion of the imaged and recognized training document;

a specification module, operative to specify at least one data element type of the data component hierarchy, and its corresponding record type and line pattern, based on at least the imaged and recognized training document, the document component hierarchy, and the association information; and

wherein the modeled document structure further comprises the imaged and recognized training document, each specified data element type, each specified line pattern type, and each specified record type; and

wherein the identification module further comprises;

an imaging and character recognition module, operative to image and recognize the characters of the subject document;

a locating module, operative to locate, within the imaged and recognized subject document, at least one data element of a type specified in the document model; and

a capture module, operative to capture at least one data element found to be of a type specified in the document model.

20. The computer program product as in claim 19:

wherein the subject document imaging and character recognition module is further operative to determine a subject document line pattern for each subject document line;

wherein a line sequence pattern comprises a plurality of ordered line patterns

wherein the locating module is further operative to;

for each record type in the document model containing a data element of interest,

locate, within the subject document, at least one of a line pattern and a line sequence pattern that corresponds to the record type,

locate the data element of interest based on its specified relationship to the structure of the record type.