Document analysis system for integration of paper records into a searchable electronic database

• US 20070168382A1
• Filed: 01/03/2007
• Published: 07/19/2007
• Est. Priority Date: 01/03/2006
• Status: Abandoned Application

• Current Assignee: Kyos Systems Inc
• Original Assignee: Kyos Systems Inc
• Inventors: Tillberg, Michael, Gaines, George
• Application Number:
  US11/649,192
• Publication Number:
  US 20070168382A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 16/5846 using extracted text
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1444 Selective acquisition, locating or processing of specific regions, e.g. highlighted text, fiducial marks or predetermined fields
• CPC Class Codes: G06V 30/412 Layout analysis of documents structured with printed lines or input boxes, e.g. business forms or tables

Abstract

Electronic extraction of information from fields within documents comprises identifying a document by comparison to a template library, identifying data fields based on size and position, extracting data from the fields, and applying recognition. Line identification employs shaded region identification, line capture and gap filling, line segment clustering, and optional line rotation. Fingerprinting methods compare line segments found in a document with line definitions for templates to identify the template that best matches the document. Templates for new form types are defined by identifying and determining a location and size for lines, boxes, or shaded regions located within the form. Form fields based on location are then defined, any text within each field is recognized, and field identifiers and content descriptors are assigned and stored to define the template. Identification of unmatched documents is facilitated by clustering unidentified documents for use in identification or creation of a new form template.

Claims

1. A computer-readable medium, the medium being characterized in that:

the computer-readable medium contains code which, when executed in a processor, performs document analysis by the steps of;

electronically receiving at least one input scan containing at least one field for containing data;

analyzing the input scan to identify lines and fields within the input scan, by the steps of;

locating at least one. shaded region or line segment;

filtering any shaded region found;

detecting and filling in any gaps in any located line segment;

clustering any line segments co-located within a specified shift distance; and

determining a length and a location for each line segment or line segment cluster;

comparing the analyzed input scan against a library of form templates;

identifying the form template that best matches the input scan;

based on the identified form template, identifying at least one field or line within the input scan; and

extracting data from the identified field or line.

2. The computer-readable medium of claim 1, the medium further being characterized in that:

the computer-readable medium contains code which, when executed in a processor, performs the step of;

defining a plurality of templates for the form template dictionary, each template describing an individual form type in terms of at least the location of at least one field or line on a form having the individual form type.

3. The computer-readable medium of claim 1, the medium further being characterized in that:

the computer-readable medium contains code which, when executed in a processor, performs the step of;

applying rules for validation and automatic editing established for the identified template to the extracted data.

4. The computer-readable medium of claim 1, the medium further being characterized in that:

the computer-readable medium contains code which, when executed in a processor, performs the step of;

exporting the extracted data for validation and editing using a quality control system.

5. The computer-readable medium of claim 1, the medium further being characterized in that:

the computer-readable medium contains code which, when executed in a processor, performs the step of;

applying field specific business and search rules to the extracted data.

6. The computer-readable medium of claim 1, the medium further being characterized in that:

the computer-readable medium contains code which, when executed in a processor, performs the step of;

performing individual recognition activities in order to convert extracted data into a searchable and computable format.

7. The computer-readable medium of claim 1, the medium further being characterized in that:

the computer-readable medium contains code which, when executed in a processor, performs the step of extracting data by means of optical recognition.

8. The computer-readable medium of claim 1, the medium further being characterized in that:

the computer-readable medium contains code which, when executed in a processor, performs the step of identifying the form template that best matches the input scan by the step of;

discriminating between different versions of the same form type.

9. A computer-readable medium, the medium being characterized in that:

the computer-readable medium contains code which, when executed in a processor, matches an input scan to a form template by the steps of;

for every line segment identified on the input scan,

comparing the position and length of the line segment with at least one line definition from a form template contained in a form template library; and

determining the offset between the input scan line segment and the form template line definition;

using the determined offsets for all input scan line segments, determining a score related to the goodness of fit between the input scan and the form template; and

determining which form template most closely matches the input scan by comparing the score for each form template against scores for other form templates in the form template library.

10. The computer-readable medium of claim 9, the medium further being characterized in that:

the computer-readable medium contains code which, when executed in a processor, performs the step of;

setting a threshold score below which a form template will be immediately considered a match and the process will be terminated early.

11. The computer-readable medium of claim 9, the medium further being characterized in that:

the computer-readable medium contains code which, when executed in a processor, performs the step of;

setting a threshold score above which a form template cannot be considered a match and consideration of that form template will be terminated early.

12. A computer-readable medium, the medium being characterized in that:

the computer-readable medium contains code which, when executed in a processor, matches an input scan to a form template by the steps of;

determining an overall line length of identified line segments on the input scan;

ordering form templates in a form template library by comparing the overall line length definition for each template to the input scan overall line length;

separating the input scan line segments into a vertical line class and a horizontal line class;

ordering each class by clustering the perpendicular positioning of each line segment in the class and then sorting each cluster by the parallel positioning of each line segment in the cluster;

beginning with the first form template according to the form template order and employing dynamic programming methodologies, determining an alignment and score for each of the vertical and horizontal line classes based on comparisons of line position and length;

concatenating the alignments from the vertical and horizontal classes to obtain an overall score for the form template;

if more form templates remain in the library, repeating for each form template; and

determining which form template most closely matches the input scan by comparing the overall score for each form template against scores for other form templates in the form template library.

13. The computer-readable medium of claim 12, the medium further being characterized in that:

the computer-readable medium contains code which, when executed in a processor, performs the step of;

setting a threshold score below which a form template will be immediately considered a match and the process will be terminated early.

14. The computer-readable medium of claim 12, the medium further being characterized in that:

the computer-readable medium contains code which, when executed in a processor, performs the step of;

setting a threshold score above which a form template cannot be considered a match and consideration of that form template will be terminated early.

15. A computer-readable medium, the medium being characterized in that:

the computer-readable medium contains code which, when executed in a processor, performs form template definition by the steps of;

electronically receiving an instance of a new form type;

identifying at least some lines, boxes, or shaded regions located within the form instance;

determining a location and size for each identified line, box, or shaded region;

from the location and size determined for the identified lines, boxes, or shaded regions, defining at least one form field having an associated- form field location;

optionally recognizing any text within each defined form field;

based on the content of any recognized text for a form field and the associated form field location, assigning an associated form field identifier and an associated form field content descriptor for each form field; and

storing the line locations, form field identifiers, associated form field locations, and associated form field content descriptors to define a form template for the new form type.

16. The computer-readable medium of claim 15, the medium further being characterized in that:

the computer-readable medium contains code which, when executed in a processor, performs the step of;

defining a second form template for a second form type from the defined form template by the steps of;

identifying at least one second form type form field that, based at least on form field location, matches a defined form field from the defined form template; and

transferring the form field identifier and associated form field content descriptor for the matching defined form field from the defined form template to the second form template.

17. The computer-readable medium of claim 15, the medium further being characterized in that:

the computer-readable medium contains code which, when executed in a processor, performs the step of;

cleaning up scan artifacts, stray marks, or smudges on the received form instance prior to defining the form template.

18. The computer-readable medium of claim 15, the medium further being characterized in that:

the computer-readable medium contains code which, when executed in a processor, performs the step of;

exporting the defined form template for validation and editing using a quality control system.

19. The computer-readable medium of claim 15, the medium further being characterized in that:

the computer-readable medium contains code which, when executed in a processor, performs the step of identifying by the steps of;

locating at least one shaded region or line segment;

filtering any shaded region found;

detecting and filling in any gaps in any located line segment;

clustering any line segments co-located within a specified shift distance; and

determining a length and a location for each line segment or line segment cluster.

20. A computer-readable medium, the medium being characterized in that:

the computer-readable medium contains code which, when executed in a processor, performs identification of unidentified input scans by the steps of;

identifying a plurality of input scans that have failed to be matched to a template during a document analysis procedure;

performing a document analysis procedure by selecting one unidentified input scan as a template and using the remaining unidentified input scans as input scans;

placing any input scans that match into an unidentified input scan cluster; and

matching the unidentified input scan cluster to an existing form template from another source or to a new form template defined using the unidentified input scan cluster.

21. The computer-readable medium of claim 20, the medium further being characterized in that:

the computer-readable medium contains code which, when executed in a processor, performs the step of matching the unidentified input scan cluster to a form template by the steps of;

performing character recognition on each unidentified input scan within an unidentified input scan cluster to obtain strings of characters;

comparing strings from each scan within the cluster to identify similarities;

if strings from a particular scan do not match strings from the other scans within a specified tolerance, removing the particular scan from the cluster;

generating a set of consensus strings for the cluster, based on the content of the strings obtained for each form within the cluster as validated by scores from template matching or text alignment procedures;

searching the consensus string with known text strings from missing forms to locate terms that may be of assistance in determining the form identity; and

based on results obtained from template, text alignment, and character string matching, identifying a matching existing form template or creating a new form template that matches the unidentified form scan cluster.

22. The computer-readable medium of claim 20, the medium further being characterized in that:

the computer-readable medium contains code which, when executed in a processor, performs the step of matching the unidentified input scan cluster to a form template by the step of;

exporting the cluster for visual inspection and matching.