Method and system for extracting information from a document

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.

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;  
   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, the line pattern including the identification of the type of character at each position in the line;  
 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.  
   
   
   
       2 . 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;  
   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, the line pattern including the identification of the type of character at each position in the line;  
 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 2:   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.  
 
   
   
   
       4 . The method as in  claim 2  wherein recognizing characters of an imaged training document comprises: 
 performing optical character recognition (OCR) on the training document.    
   
   
       5 . The method as in  claim 2  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.    
   
   
       6 . 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.    
   
   
       7 . The method as in  claim 2  further comprising: 
 assessing the degree to which the captured data element corresponds to the data element type.    
   
   
       8 . The method as in  claim 2  further comprising: 
 assessing the degree to which the subject document structure surrounding each identified subject document data element corresponds to the modeled document structure.    
   
   
       9 . The method as in  claim 8  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.    
   
   
       10 . The method as in  claim 8  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.    
   
   
       11 . The method as in  claim 8  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.    
   
   
       12 . The method as in  claim 2:   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.  
   
   
   
       13 . 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;    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, the line pattern including the identification of the type of character at each position in the line;  
 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.  
   
   
   
       14 . The computer program product as in  claim 13:   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.  
 
   
   
   
       15 . A computer-implemented method for modeling a document structure, the method comprising: 
 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, the line pattern including the identification of the type of character at each position in the line; 
 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.  
   
   
   
       16 . A computer implemented method for aligning at least two pages of a document comprising: 
 collecting a predetermined number of similar line pattern pairs, one line pattern of each pair being from each of the at least two pages, wherein a line pattern includes the identification of the type of character at each position in the line;    calculating a horizontal offset for each pair by measuring between correlated character positions;    determining similar offsets among multiple pairs to form a cluster of similar offsets;    calculating an average offset for the similar offsets in the cluster.    
   
   
       17 . The method of  claim 16 , wherein determining the similarity between line patterns includes: 
 generating line patterns;    identifying strings within each of the line patterns;    determining the length of the strings within the line patterns;    calculating the distance between the strings in each of the line patterns;    comparing the calculated distances among line patterns to determine similar line patterns.