Image analysis – Pattern recognition – Template matching
Reexamination Certificate
2000-04-19
2004-08-17
Chang, Jon (Department: 2623)
Image analysis
Pattern recognition
Template matching
Reexamination Certificate
active
06778703
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to document image processing, and specifically to methods for extraction of information that is filled into preprinted forms.
BACKGROUND OF THE INVENTION
In many document imaging systems, large numbers of forms are scanned into a computer, which then processes the resultant document images to extract pertinent information. Typically the forms comprise preprinted templates, containing predefined fields that have been filled in by hand or with machine-printed characters. In some applications, such as population censuses and tax processing systems, a wide variety of different forms are used, and may typically be input to the computer in any order. Before extracting the information that has been filled into any given form, the computer must first recognize which form it has received. Only then can the computer align the form with the proper template, in order to identify the fields of the template and decipher the characters in the fields.
There are a number of methods of form recognition known in the art. Fiducial marks and machine-readable identifying information, such as a bar code, may be printed on the form itself. This approach uses up valuable form “real estate,” however, and makes for an inflexible system, capable of processing only forms that have been designed in advance with the appropriate marks. Therefore, a preferred approach is to identify features in the scanned form image. For example, horizontal and vertical lines and text base lines (imaginary lines running through the bottom of the characters in a row), as well as the black background of the scanned paper, may be identified and located. Still, none of these features is guaranteed to exist in all forms of interest, and the text baseline features are generally expensive to compute. Because of the large number of different forms that must be processed in applications such as those mentioned above, there is a need for a form recognition method that is both accurate and fast.
U.S. Pat. No. 5,191,525, whose disclosure is incorporated herein by reference, describes a system and method for extraction of data from form documents for subsequent processing. In order to identify forms passing through the system, a number of identification areas are chosen in advance by a designer from existing printed forms, using an interactive computer display. The designer pre-selects a word or an area already present on the form. The coordinates of the identification area are stored in the computer and are accessed in order to “carve” the appropriate areas from the documents as they are processed. The spelling of the selected word or an electronic signature of the pixel pattern in the area are used to match the features of the processed document to the form. The electronic signature may include a histogram or intersection count. Once the form is identified, the relative location of the selected word or the electronic signature is used to adjust for misregistration and skew that may have arisen in printing or scanning the form.
Another method known in the art for matching pairs of images, such as the form and template images, uses multi-resolution pyramids. This method is most commonly used in motion estimation. Reduced, low-resolution versions of the images are first matched, and the displacement of one image relative to the other is estimated. The matching and displacement estimation are repeated and refined at a succession of higher resolutions (hence the name “pyramid”), until the exact, full-resolution result is found. This type of matching is problematic in relation to form images, however, since it is liable to be confused by information filled into the form.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide improved methods and apparatus for processing of images of form documents.
It is a further object of some aspects of the present invention to provide improved methods for automatically identifying which of a plurality of different form templates corresponds to a given form document.
It is yet a further object of some aspects of the present invention to provide methods for automatically selecting reference areas in form templates and for automatically matching areas of a form document to the reference areas.
In preferred embodiments of the present invention, a document processing system receives images of filled-in form documents to process. The documents are based on a plurality of different form templates whose order of input to the system is not known in advance. In order to determine on which template each document is based, reference areas are chosen on each template. Preferably, one reference area is chosen in each of a number of predefined sectors of the template, typically one reference area per quadrant. Most preferably, the reference areas are chosen automatically, based on a reference metric that embodies criteria designed to ensure that the features of the reference areas are clearly distinguishable from their immediate surroundings and that they are not in parts of the form that are going to be filled in. Thus, there is no need for fiducial marks on the forms or for other constraints on form design. There is also generally no need for a human operator to select the reference areas, as required by the method of the above-mentioned U.S. Pat. No. 5,191,525.
For each template that is a candidate to match the current document, reference areas on the document image are located and registered with the corresponding reference areas of the template. The reference areas on the template and the document are then compared to find a matching score. Generally, the template having the best overall matching score is recognized as the one belonging to this document. The correct template is thus chosen rapidly and, in most cases, completely automatically, even in the absence of lines on the form or other specific features that are commonly used for template recognition and registration. The entire document image is adjusted for fine registration with the chosen template, and the information filled into the document is extracted from the fields of the form, using any suitable method known in the art.
In some preferred embodiments of the present invention, prior to matching the reference areas, a reduced-scale image of the form document is compared to reduced-scale images of the templates. These reduced-scale images are referred to herein as icons. Matching of the icons is used to make a preliminary assessment of which templates are the best candidates to match the whole document. To generate such an icon, the full-scale image is binarized (if it is not already in binary form) and is divided into a matrix of blocks. A gray-scale icon is produced having one pixel for each block in the full-scale image. The gray-scale value of each pixel in the icon is equal to the sum of the binary values of the pixels in the corresponding block. Preferably, the gray-scale icon is then binarized, using any suitable binarization algorithm known in the art.
It has been found that icons produced in this manner represent the full-scale source images more faithfully than do icons generated by purely binary scaling algorithms, as are known in the art. Furthermore, the use of icon matching as a preliminary step to matching the reference areas saves processing time, by narrowing the field of candidate templates. On the other hand, combining one icon matching stage with the subsequent reference area matching stage is considerably faster and less computation-intensive than full, multi-resolution pyramid-based fitting algorithms, as are known in the art.
In some preferred embodiments of the present invention, the reference areas are used to register the form document with the candidate template or templates in a number of successive stages. In a first, coarse stage, a tentative identification is made of the reference areas in the document image that most closely correspond to the defined reference areas in the candidate template. Preferably, the tentative identification is
Chang Jon
Darby & Darby
International Business Machines - Corporation
LandOfFree
Form recognition using reference areas does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Form recognition using reference areas, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Form recognition using reference areas will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3348093