JPH0676102A - Determining method for setting classifing process - Google Patents

Abstract

PURPOSE: To provide a form recognition system for identifying the kind of an original in a new fixed form, clarifying a characteristic, using it, and adding it to a data base. CONSTITUTION: This method is provided with a step for inputting a master original at plural times, and generating plural master bit maps (200), step for extracting a characteristic from the plural master bit maps (300), step for generating an attribute by combining the characteristic with random model parameter distribution, and generating the plural attributes in the larger number of that of the plural master bit maps, step for operating cluster analysis from all the master originals to the attributes, and generating plural super classes expressing the family of the master originals and plural non-super classes expressing the master originals which are not the members of the family, and step for operating classification analysis into the super classes and the non-super classes, and generating the setting of a classification processing enabling the recognition of the master original.

Description

Detailed Description of the Invention

[0001]

FIELD OF THE INVENTION This invention relates to form recognition systems, and more particularly to form recognition systems that use random noise and systematic noise distortion models to increase recognition.

[0002]

BACKGROUND OF THE INVENTION One method of using computer systems to extract data from forms is RGCase.
y and DR Ferguson, "Intelligent Forms Processing," IBM Sy
stems Journal, Volume 29, No. 3, 1990, 435-450
Page). The technique disclosed therein is a form recognition process in which the form is scanned to produce an electronic bitmap representation of the image. When using various image processing techniques, the bitmap form is analyzed and compared until it matches another bitmap form stored in the database as a template. If there is no match, the user must enter the new type of form by interacting with the computer and identifying the new additional template in the template's database. Even though this disclosure deals with automatic form recognition, i.e. automatic data extraction, the system has a prior knowledge of the form before it is recognized and the data is successfully extracted. Is assumed. Further, what is dealt with in this document is a concept of correcting an image skew and an offset caused by an erroneous alignment scanning.
However, it does not accommodate other constant and stochastic errors that may occur in the system. Therefore, errors not captured in this system increase the unrecognized error rate. More complex systems are required.

Similar to the article by Casey and Ferguson, US Pat. No. 4,933,979 discloses a foam sheet reader. In this system, the form will be scanned to produce an electronic bitmap that will be displayed on the graphical display terminal for the user. Next, the user uses the graphic input interface to select the items constituting the blank form on the displayed bitmap. For example, the user may sketch a box with information that answers the questions raised about the form. The user's instructions are stored in the first file and later used as a template. The original having data in the field is scanned again and saved in the second file. Then, the bitmap of the first file, i.e. the template, is subtracted from the bitmap of the second file, so that only non-template information, i.e. data, is extracted and further analyzed. Once the form is stored as a template, subsequent forms that are scanned are matched against some stored template and data is extracted. However, U.S. Pat. No. 4,933,979 only compensates for image skew and does not address or compensate for other constant and stochastic errors that may occur in the system. Also, U.S. Pat.No. 4,933,979
At least one on the form to detect fields
It requires that there be two lines, thereby eliminating the possibility of recognizing forms that do not have lines that specify fields.

Therefore, a new approach for identifying, characterizing, utilizing, and adding new fixed format manuscript types to databases is both an advantage and a benefit. The new approach does not require form redesign, can be used for time-gathering and foreign forms, and is easy to extend to add and remove different types of forms. It can also identify and classify a large number (more than 1000) of different types of foam, take advantage of common sources of constant and stochastic errors found in the office environment, and compensate and endure them. Ensure sex.

[0005]

SUMMARY OF THE INVENTION The present invention identifies sources of systematic and random noise during run-time operation and during teaching the system which form the system should recognize (learn mode). Provide a form recognition system to use. Information is extracted from the form by first digitizing the form into a bitmap and using a recognition process to identify the bitmap as a known form. After this step, the information in the digitized form is extracted by a recognition process supported by knowledge about the form type. Moreover, the system is trainable and designed to handle different sources of random noise and achieve good recognition accuracy in the presence of large numbers of foam types.

The present invention provides a method for determining a classification process setting that enables recognition of a master document used in a document recognition system during a learning mode. The method includes the steps of generating a plurality of master bitmaps expressing the master original by inputting one master original a plurality of times, extracting a feature from the plurality of master bitmaps, and distributing the features to a random model parameter distribution. Generating an attribute by combining with, resulting in a plurality of attributes that is substantially greater than the number of master bitmaps, and repeating the above steps for all master manuscripts, Performing a cluster analysis on attributes from all master manuscripts, where the cluster analysis yields multiple superclasses and multiple non-superclasses representing a family of master manuscripts, with superclasses and non-superclasses Performs a classification analysis and, as a result, the master Comprising the steps of: causing the classification process settings that allow recognition of a document, the.

Further, the present invention provides a method for determining a classification number representing a fixed-format manuscript from a known set during run-time mode, the method for generating an electronic bitmap. Inputting the fixed format manuscript, processing the bitmap to generate a second bitmap containing only classification features, and extracting classification features from the second bitmap;
Combining the classification features with a random model parameter distribution to generate a plurality of attributes for the second bitmap, and classifying the attributes of the second bitmap, resulting in at least one class number. Prepare

[0008]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT Referring to FIG. 1, a general hardware system configuration utilizing the present invention is shown. System 1
Comprises a local (local) input service 2 which provides a manuscript and produces a digital electronic representation of the manuscript in the form of a bitmap. Also shown is a remote input service 3 that produces a bitmap image, which is in the form of a facsimile machine that digitizes the image and sends a digital representation of the image to a remote location using a telephone line or equivalent. Good. Alternatively, the remote input service 3
Information can also be obtained from other computers that represent in the form of a page description language (PDL), thus converting that page description language into a usable bitmap. The bitmaps generated by the local input service 2 and the remote input service 3 are received by the workstation 4. The workstation 4 allows the operator to view the bitmap and perform various other management functions regarding the bitmap, such as editing, template generation, and filing. The workstation 4 is connected to a computer service 5 that performs a bitmap processing function as described below. The computer service 5 also acts as a distributor for distributing information including bitmaps to other functional units in the system 1 such as the printer 6, the database storage unit 9, and the storage storage unit 8. The system 1 described above is an example of one possible hardware system configuration and is not meant to be limited to the components shown in FIG.

Referring now to FIG. 2, a schematic of form recognition system 10 is shown. The blocks of each subsystem shown in FIG. 2 are described in more detail below with reference to FIGS. 3-10. As will be appreciated, system 10 is operated in a training mode and a run time mode. The training mode or the learning mode is the system 10
This is a mode for teaching the system 10 a fixed format manuscript that the user needs to recognize. The operation in the run-time mode makes it possible to recognize the document and also to automatically extract the information on the document.

As shown schematically of system 10, at start block 100, a compressed bitmap image from a digitized source, such as local input service 2 or remote input service 3 of FIG. 1, is decompressed. , To the pre-processing block 200. Also, the bitmap image contains coded information about which external input device the input is from. Preprocessing block 2
00 performs image operations such as skew correction and resolution conversion, and prepares the bitmap for processing by the data extraction block 300 and the document recognition block 400. The manuscript recognition block 400 determines which form stored as a template matches the scanned bitmap form and places a ranked list of classification numbers or classification numbers belonging to that template in the data extraction block 300. Send out. The classification number identifies which form is used, identifies the template for that form, and identifies the area on the bitmap, along with the type of recognition system needed to process the extracted data. Find each field on the template to extract the data. For example, the template indicates where a field of text is found and where the text recognition of the textual data for that field applies. Using this classification number, the data extraction block 300 can extract information from the bitmap and represent some of the smaller bitmaps and / or the actual data to a later database. Will be the memory of.

The data verification block 500 determines if the information extracted from some smaller bitmaps is valid. If not valid, the data is manually corrected block 6 for additional inspection by the operator.
Sent to 00. If the data extracted from the bitmap is complete and accurate, it is sent to the database insert block 700 for storage in the database.
If the system needs a bitmap that has a new form format to be entered into the system, a special template that adds a template for this new form to recognize the field and allow data extraction. Processing must be performed. This happens during the learning mode. In this case, the recognition initialization system block 1
000 performs the functions required to add or remove templates to the system, allowing automatic recognition and data extraction later during runtime operation. In addition, the recognition initialization system block 1000 derives random model parameters and systematic model correction factors used throughout the system 10.

Referring to FIGS. 7-10, a detailed flow diagram of the recognition initialization system block 1000 is shown. The recognition initialization system block 1000 consists of three parts: a new form introduction block 1100, a new form training block 1500, and a scanner calibration block 1800. The function of the recognition initialization system block 1000 is to add a new template to the system 10 for form recognition using a durable and automated method. Also, implementing the recognition initialization system block 1000 is referred to as the learning mode of the system. Generally, to enable learning, an operator scans new blank forms or masters to generate bitmaps for these masters. Random model parameters and systematic model correction factors are applied, as will become apparent below. Feature extraction, attribute generation and bitmap classification are performed with training in the classification process used during run-time operations. Calibration of the equipment used to generate the master is performed to determine the constant error,
It is included in the learning process. When the process is complete, the master's representation with associated classification numbers and other useful information is added to the template store as a template.

Generally, a new foam introduction block 11
00 is a database information block 1180, a new form bitmap 1004, and a calibration sheet 100.
Take the input from 6, and prepare the new form training block 1500 with a bitmap representing the master to be added to the system 10. Scanner calibration block 18
00 provides systematic model correction factors 1860 and random model parameters 1880 using information from calibration sheet 1006. New Form Training Block 15
00 is a dictionary storage unit 1240 and a template storage unit 12
60, super classification 1544, and classification processing setting 1
554 is output. Scanner calibration system 1800
Outputs systematic model correction factors 1860 for scanners and printers along with random model parameters 1880 used to train the classification process. The following is a detailed description of the recognition initialization system 1000.

In particular, referring to FIG. 10, a detailed flow diagram of the daily scanner calibration block 1800 (FIG. 7) is shown. The purpose of block 1800 is to scan the calibration sheet 10 using the scanner calibration sheet scan block 1810.
06 (FIG. 7), reference marking extraction block 1
820 is used to extract data from the resulting bitmap 1812, block 1830 is used to derive a systematic distortion model, block 1840 is used to derive a random distortion model, and are described in detail below. Systematic model correction factors 1860 and random model parameters 18 for use in the rest of the recognition system.
80 is output.

To facilitate the derivation of the systematic model correction factor 1860, a sheet with fiducial marks is used as the calibration sheet 1006. Such sheets include a series of easily identifiable marks, or fiducials, for manual or mechanical measurement. For example, such a page may include a series of small crosses in a 0.25 inch (0.635 cm) grid pattern in both the X and Y directions throughout the page. Calibration sheet 1006
Must be measured by a device that has a higher placement accuracy than the accuracy of the scanner used.

Using printer distortion information model 1802, facsimile distortion information model 1803, photocopier distortion information model 1804, and various systematic correction factors, random distortion model derivation block 1840 provides random model parameters 1880. Random noise on the system comes from the random behavior of the equipment and the random use of the equipment. Therefore,
The measurement of random noise may be done in a variety of different ways. In the case of random instrument variations, the data collected, either in calibration measurements or tests performed on different instruments, will produce an amount of deviation or deviation pattern (model) from the systematic operation of the instrument. May be used for. For example, in the case of scanner calibration, the deviation of each point from the line fitting the least squares method to the row or column of fiducial marks gives a measure of noise. The distribution function may be determined by sufficient data (hundreds of samples). A curve fitting function may be applied to this data for use in generating the model and model parameters for the random noise distribution.

A second source of random noise results from the use of different equipment, or the use of equipment of unknown calibration, or the unknown order of use of different equipment. Consider a form printed on one of three printers on a random day. The form is then copied on a copier, delivered and scanned as input to system 10. At best, only the scanner used to scan the form into the system 10 can be corrected. Therefore, the variation in form is very significant and is very random as a result of many unknown factors.

The measurement of this second source of random noise may be accomplished by compiling data on systematic distortion measured on the various instruments used. Some of these instruments are out of the control of the operator of system 10 and require relying on default settings. To create a model of these noise sources, a series of measurements on the instrument are made at various times of the day over a period of time. Data may also be collected from manufacturers involved in alignment tolerances during maintenance. From this data, the variations that occur in the device can be plotted and these variations may be kept in the range as determined by the instrument specifications. Much data is needed to construct a true model of noise (generally the model is not constructed) and the model is considered to have a range of measurements that can be provided and some measurement points. Furthermore, a common scenario involves combining data from several different devices to find a global noise model.
The system operator can change the cutoff for these models. Each model can be augmented or relaxed with the required registration error rate.

Global noise model generation is one proposed means of determining random model parameters. In this method, the distortion to be measured is standardized (eg horizontal and vertical offsets and linear scaling). The measurements are then taken with a number of printers, fax machines and copiers that indicate the general condition of the equipment that is expected to be used or is available. Each individual instrument uses the calibration sheet and procedure for extracting systematic data described above. These tests are then run for a period of time. Copier use is evaluated and printer data is augmented by convolution with the copier distribution. Once the data growth is obtained, the combination of printer and copier convolved with the printer data is used to generate the entire printer data set. Generally, the data is weighted according to the proportion of printers (if printer A
%, And printers B and C are used for the rest of the work, the data for printer A is weighted by a factor of 2 times B and C). A suitable random model may be selected based on a plot of this data. A model suitable for the program may then be used to fit the data to this random model. Therefore, the random model parameter 1880 is generated.
Random model parameters are expressed as a distribution or range of errors that all of system 10 can affect.

Note that image distortion propagates throughout the image. For example, a skewed image has more distortion at the bottom of the page than at the top of the page.
Also, it is assumed that the distortions discussed here may be either linear or non-linear in nature. As an example of non-linear distortion, a printer that shows 101% linear scaling along the page length and 99.5% linear scaling across the width of the page has a position (100,100) and a position (2000,20).
Consider placing two pixels assumed to be at (00) and moving them to new locations at (101,99.5) and (2020,1990) respectively. If this printout is photocopied by a copier with 98% linear scaling in both directions, the two original positions are (99.0,97.
5) and (1979.6,1950.2), respectively. One point is not too far from where it left off, but the other is a considerable distance away. Therefore, it can be seen that there is a cumulative error in the nonlinear case. If something increases and decreases linearly with the same amount, the error goes away. However, that is not true for non-linear errors, so the same opposing non-linear function is needed to invert that error.

Referring now to FIG. 8, a detailed flow diagram of the new form introduction block 1100 is shown. The purpose of the new form introduction block 1100 is to add a new form, i.e. a master (i.e. blank form), to the system 10 in the form of a template. A master is a new form that has no fields populated by data, but includes all structures (eg lines, boxes, etc.) and fields.
The template is generated from the master. The template is used during run-time operation to help recognize forms and extract information from these forms. The template contains information about the coordinates that specify the master's fixed fields and attribute information that the recognition system uses to identify the information in each field. Line 1101 specifies the functional partition of block 1100. The function to the left of line 1101 is to correct the master bitmap that is about to be stored in system 10. The function to the right of line 1101 is the operation performed once the incoming bitmap has been corrected.

Further, the printer calibration sheet is printed by the printout of the master. The information obtained from the printer calibration sheet enters a set of processing routines that compensate for systematic printer error. Printer calibration is performed by the printer calibration scan block 1110, which provides a bitmap 1112. The bitmap 1112 representing the calibration sheet is used in the printer correction derivation block 11 in which the printer correction coefficient is determined.
20 is transmitted. In a similar way, scanner calibration
Scanner calibration scan block 11 providing a bitmap 1132 representing an electronic version of a calibration sheet
It is realized by 30. A bitmap 1132 is generated and systematic and random scanner correction factors 114
2 is passed to the scanner correction derivation block 1140, where 2 is derived. The original used to calibrate the scanner and printer in this case is block 18 in FIG.
Similar to the manuscript described in connection with 00.

Calibration is generally performed by at least one calibration sheet. Because different parts of the belt have different results, several sheets are needed for large printers that use belt systems.
Therefore, multiple printouts and multiple (eg, 5) scans to help generate master-specific systematic and random distortion calibration models are preferred. The method preferably prints out at least one calibration sheet, calibrates the scanner, scans the printer calibration sheet, derives the printer's corrections based on the scanner's corrections, both systematic and random parts. Is to derive the overall correction factor with. These random parameters help derive what goes into the template store 1260. Note that in the system there are actually two different sets of random parameters. The master-specific systematic distortion calibration model and the random distortion calibration model from the global correction block 1150 are calibrated only, while the system model considers many other factors. In terms of
Different from the system model. The random calibration parameters are
Derived from random correction factors for scanner and printer calibrations, and from the use of multiple master copies of the printout used when scanning. This provides the template tool 1190 with unique, highly tuned random calibration parameters that are unique to the set of masters when calibrated. These parameters change daily.

The global correction block 1150 combines the scanner correction factor and the printer correction factor into a set of correction factors used by the image realignment block 1170, a systematic distortion calibration model, and a random distortion calibration model. Occurs. Since the scanner correction factor 1142 and the printer correction factor 1122 are known, the new form scan block 1160 is used to scan the new master several times and the resulting bitmap 1162 is received, these predetermined systematic calibrations for the day. Depending on the coefficients, the image realignment block 1170 is used,
Re-register the image of bitmap 1162. The image realignment block 1170, which is the process of producing this nearly ideal master image, also produces the registration factor 308 (FIG. 5) from the master used in run-time operation. In addition, the image re-registration block 1170 uses template tools 1190 to compensate the random distortion calibration parameters to the range or distribution of random correction factors found in the calibration system.
Pass to.

The realigned master in the form of bitmap 1172 is passed to the template tool 1190 along with random distortion calibration parameters. The template tool 1190 is for assembling the template used in the recognition part and the data extraction part of the system 10 from its master. The template tool 1190 is manually executed by an operator who can display the master bitmap on a graphics workstation. The operator can specify on the screen of the graphic workstation where a field is in the bitmap.

When designating coordinates using the template tool 1190, the operator may select coordinates (x, y) such as the corners of a field in a bitmap. But,
According to the random model parameters, the coordinates (x + 2, y +
4) also represents the same corner of the same field. Therefore, for any coordinate in the field specified by the operator, a random calibration parameter must be applied. Applying the full range (or distribution) of random calibration parameters essentially specifies several templates for each master, and each template is shifted by a certain amount from the original template specified by the operator. Has been done. In other words, if the template has coordinates specified by the operator, then applying the distribution of statistical random calibration parameters to that template, the equivalent of some possible templates all represent the same master. Will be done. Basically, the model defines a fuzzy box around a designated field in the master. The random calibration parameter defines how thick the fuzzy layer is around the box. Blur is equal to the uncertainty that the blurred layer becomes thinner as the object becomes more certain.
The fuzzy factors used here are more about the clipper with respect to recognition. The recognition system uses system random model parameters to define the uncertainty by features and attributes. Although only one template is stored, the random distribution memory has the effect of storing many templates.

Since the master is likely to have no reference on its own, a registration function is required. Therefore, the system finds a particular marking on the form and uses it as an alignment point (eg, line intersection, etc.). The system can then find the set of fiducials and use the customized set of fiducials for the particular form to move and align the document. Thus, during the recognition process, the form to be recognized is still within the statistical error of the template and is of the same type as the master.

A bitmap 1192 is created from the template tool 1190 and the alignment feature processing block 1210 is used.
Passed to. This alignment feature processing block 1210
At, the template specified by the operator is corrected to compensate for the random calibration parameters described above.

The template tool 1190 includes an operator-defined template 1196 with corresponding random calibration parameters and a template form identification 1
And 198 are stored in the template storage unit 1260.
The template feature processing block 1210 stores the alignment parameter 1212 in the template storage unit 1260. The registration parameter 1212 is the distribution of the allowable error range regarding the template derived from the random calibration parameter. Therefore, for each template stored in the template storage unit 1260, the “best case” template and the distribution of the allowable error range applied to the template are stored. Another method stores some templates for each master by applying random calibration parameters to the ideal template before storing it in the template store.

Before the master form is generated, the ones that generate the master form often know what kind of fields are required in the form, and in some cases, the form. Know what information will be provided in those fields when used. For example, if a form requires a field that specifies the gender of the person using the form, then the creator of the form can expect the keywords "male" or "female" to appear in the field.
Computer database 1180 is often set up to have storage areas for easily storing information from the respective fields of the form, and to include information regarding what kind of data to expect. Information from the fields of the form is extracted and stored in the database 1180, as can be seen in the runtime recognition operation of the system 10. Bitmap 1192
To make intelligent use of the dictionary tool 1200 uses the information stored in the database 1180 prior to extracting the data. The dictionary tool 1200 is configured to retrieve fields from the bitmap 1192 using the keywords used in the completed database prediction form. These keywords are dictionary storage 1
Stored at 240 for later use by post processing functions of the recognition system.

The feature recognition processing block 1220 uses the bitmap 1194 to determine useful information to be stored with the template. For example, if a field of the template is designated for check box recognition, the feature recognition processing block 1220 determines how many bits in that field are set to master. With that information, the inspection box recognition system counts how many bits are set in the field from the form being filled in, and simply subtracts how many bits are set in the master to get the box for that field. Determines if is set. Another example is to alert the OCR preprocessor if a field intended for OCR processing has a colored background. The last example is the type of data entered in the field (eg a telephone number), which is conventionally known. Many other feature recognition processing functions are possible, but block 1220 is not limited to those described herein as examples.

The bitmap 1174 from the image realignment block 1170 is used to generate an image training (training) store 1280 where the image is trained in the new form training block 1500 (FIG. 9). Retained. As is apparent, only one bitmap is input to the template tool 1190, whereas multiple bitmaps generated from multiple scans of the master are input to the image training store 1280. The image training storage unit 1280 will be described in detail with reference to FIG.

Returning to FIG. 9, a detailed flow diagram of the new form training block 1500 is shown. The purpose of the new form training block 1500 is to allow the addition or deletion of recognizable forms and to generate a training set for the classification process used during runtime operation. If a master is added or removed from the recognition system, the classification process must be retrained each time a master is added or removed. As long as the features and attributes used for training remain unchanged,
Instead of re-executing the process each time a new master is added or deleted, the intermediate result of feature extraction may be stored in the intermediate result storage unit 1521. Image training storage unit 12
80 contains a bitmap of all master forms that the form recognition system must recognize at a given time. The amount of work required to retrain will change many times depending on the type of classification process used.

To have a complete training set of images in the image training store 1280, multiple copies of the master were scanned and printed several times (eg 3 to 5 times) and are described using FIG. The bitmap is stored as described above. For purposes of explanation, multiple bitmaps of images scanned multiple times for a single form are referred to below as a "raw family set". The feature extraction block 1510 extracts a feature for classification from each bitmap of the raw family set using the image processing function. For example, if the features to be extracted are horizontal lines, then to remove everything but the horizontal lines from the bitmap, use the morph filter (morph
(ological filter) may be used. Another example is to use OCR to determine the direction of text tilt in a bitmap. The features used in the classification are the position mode of the image on the medium (landscape versus portrait), the number of horizontal lines, the number of vertical lines, the number of halftone areas and where those areas are distributed on the page, It may include the number of text areas and where they are distributed, the distribution of boxes, the boxes within a box, the matrix of boxes, etc. Obviously, many other types of features may be considered and utilized. The feature and attribute dictionary 1511 defines what features and attributes are used throughout the training set.

When the bit map including only the related features is generated, the feature extraction block 1510 extracts the related features and sends the feature information to the data set generation block 1520 having the attribute of the classification process. Block 1
520 receives the features extracted from the raw family set and uses a random model parameter to generate a larger data set of features, the "total family feature set (tot
al family feature set) "is generated. Each feature set is a representation of a masterform. By applying a random distribution from the random model parameters 1880 to the features extracted from the raw family set,
The feature set is expanded to an entire family feature set, including, for example, 50 feature sets. For example, suppose the feature to be extracted is a horizon and one of the bitmaps in the raw data set has coordinates at x = 10. The random model is such that the error may span two coordinate points, the random model is applied to the features, and x =
It indicates that the horizon at 11 and x = 12 is also an acceptable definition of the master's horizon. A random distribution is applied to each feature extracted from each raw family set in the training store 1280 to generate a full family feature set. Note that the random distribution could have been applied to the raw family set bitmaps that produced more bitmaps, instead of being applied to the features extracted from the bitmaps.

The process of extracting features and generating a full family feature set is repeated for each master that the system needs to recognize. Usually only add,
It takes the whole process to get the features and attributes. This is because the results of feature extraction from all previously processed masters are stored in the intermediate result storage unit 1521. There is no reason to rerun a previously processed master as using the system uses the same features. In this case, it is only necessary to re-execute the classification process. However, if new classification parameters, such as new features for extraction, are added, all previously processed masters will need to be redone.

All full family feature sets from all masters represented in image training store 1280 are utilized by consistency check block 1530 and cluster analysis block 1540. The consistency check block 1530 performs a check to ensure that all bitmaps classified in the raw family set are actually from the same master. A consistency check on the raw family set may be done by analyzing the extracted features. For example, if
If one of the five raw family set bitmaps does not contain horizontal lines but the other four contain horizontal lines, the consistency check block 1530 will fail via the data error block 1532 due to human intervention. To report.

Theoretically, each bitmap derived from the same master should be put together, even if they are slightly different. Cluster analysis block 1540 uses cluster analysis to determine which forms are considered identical. That is, superimpose a set of very similar forms on a superclass. The cluster analysis used here is similar to the cluster analysis used in OCR systems. The output of the cluster analysis block 1540 is superclass 1
542 and non-superclass 1543. The purpose of the clustering process is to organize similar objects that are master forms for training, ie, to create clusters, and also to objects in other clusters that are non-superclass 1543. The goal is to generate independent and distinct clusters of dissimilar objects.

The classification process training block 1550 receives the superclass 1542 and non-superclass 1543 generated from the cluster analysis block 1540.
This information is then translated into the classification process settings 1554 used by the classification process 440 of FIG. 4 during runtime operation. The classification processing training block 1550 also includes a classification processing system. This classification process must be of the same type as the classification process 440 (Bayesian method, decision tree, etc.). Once the classification process settings 1554 are added to the hierarchical structure of the classification process 440, all masters represented in the image training store 1280 will be recognized by the classification process 440 during runtime operation. Also, a manual override is possible, and if for some reason the operator wants to
The operator can actually force two classifications into one superclass.

Once the classification process settings 1554 are derived, it is useful to check if the system 10 has been properly trained. One way to facilitate inspection is to use the cluster analysis block 1 to extract a random portion of the data from the dataset generation block 1520 with the attributes of the classification process.
540 and the classification process training block 1550 and the rest of the data to the classification process check block 1560. In general, if the system is trained on a random sample of data, it can recognize the rest of the data with a low recognition rate. Note that the system is not tested on the same data on which it was trained. In addition, some tests were done,
Determine how well the classification system is performing. Error rate and quality block 1564 reports the error rate for one training session. Even though the classification process used in the training process must be the same as that used in the runtime recognition process, different types of classification processes may be used in the test because the parameters must be the same. Having different types of classification processes improves the durability of the recognition system and keeps the recognition error rate to a minimum.

In summary, the new form training block 1
The 500 determines the classification process settings 1554 using its own classification process according to the aggregation technique. Next, the classification process setting 1554 is used to update the information in the classification process 440 of FIG. Thereby, when a form having a master-like structure previously processed by the new form training block 1500 is introduced at runtime, the document recognition block 400 can recognize the form. Therefore, the corresponding classification number can be provided. The output of the new form training block 1500 is the classification process setting 1554, the super class 154.
4, error rates and attributes 1564 resulting from checking the classification session, and data errors 1532 from the consistency check.

Referring again briefly to FIG. 2, once the recognition initialization system 1000 is activated and the classification process has been trained, the system 10 is ready for run-time operation, or mode. In run-time mode, the completed form is provided to the system for automatic recognition of the form and automatic extraction of data. Thousands of forms per day require processing. The following subsystems, which are described in detail below, are run during run-time mode. It is a start block 100, an image preprocessing block 200, a document recognition block 400, a data extraction block 300, a data verification block 500, a manual correction block 600 and a database insertion block 7.
00.

Referring now to FIG. 3, a detailed flow diagram of the image preprocessing block 200 is shown. The purpose of the image preprocessing block 200 is to prepare the input bitmap for additional processing and recognition. During run-time mode, the image pre-processing block 200 receives data from the start block 100 in the form of a bitmap, with information describing from which input device the bitmap was input. These bitmaps represent the form with its completed data fields. As described above, these bitmaps are input from a scanner or a facsimile, or as a result of a PDL (graphic description language) description converted into a bitmap.

The bitmap image input from start block 100 is received by noise filtering block 210. Noise filtering block 210
Removes impurities from the bitmap, such as salt and pepper noise, or false small spots throughout the image often caused by photocopying. The noise filtering block 210 also performs edge enhancement operations to remove jaggedness, or any other image processing function used for noise removal. The resulting filtered bitmap 212 is then processed by the input dependent correction block 220. Correction block 220 reads the encoded information in bitmap 212 that contains information about the input device for which the bitmap was generated and uses that information to apply additional corrections. Correction block 220 obtains correction data from a predetermined systematic model correction factor 1860. Systematic correction information such as offset and scaling errors associated with each input device in the system is utilized. The correction for these systematic errors is
It is performed on the bitmap using a correction factor associated with the input device for which the bitmap was generated. Note that even if correction factors are passed, they are not always used. For example, if the image is scaled, rescaling it will result in line splitting, and no one wants to scale again at this point, but retain the correction information for later use. Would hope.

Further, the correction block 220 performs resolution conversion if necessary (for example, an image scanned at 400 spi is
Convert to 300spi). The resulting bitmap 2
22 is advanced to skew correction block 240, where small angle skews in the bitmap are automatically detected and corrected.

The sub-image preparation block 260 modifies the bitmap 222 for viewing on the graphics workstation by the operator for later use if necessary (eg, error checking). The sub-image preparation block 260 may also provide an icon for the scanned image, or it may provide an image containing 10 sub-images to be viewed simultaneously among other desirable viewing orientation features. Good. The image preprocessing block 200 outputs the corrected bitmap 242 to the data extraction block 300 and the document recognition block 400, and also outputs the systematic correction factors 230 from the correction block 220 and the correction block 240 that are associated with the originating scanner. Output.

Referring now to FIG. 4, a detailed flow diagram of the document recognition block 400 is shown. Note that the operation depicted in FIG. 4 is very similar to the operation depicted in FIG. The purpose of the manuscript recognition block 400 is to determine which fixed-form manuscript type is currently passing through the system. The document recognition block 400 receives the corrected bitmap 242 from the image preprocessing block 200 of FIG. The manuscript recognition block 400 addresses two types of features present in the incoming bitmap. One is the features used for classification,
The other is the feature (ie, the alignment factor) used to align the incoming bitmap with the associated master stored as a template. The correction coefficient 230 together with the corrected bitmap 242
Is first used by the image-specific feature procedure block 410. Block 410 uses various image processing functions, such as morphological filters, to filter out certain relevant features and remove the rest of the image,
Determine classification features for processing the bitmap 242. The features used in the classification scheme have already been described in connection with FIG.

Once the bitmap containing only the relevant features is generated, the feature extraction block 420 extracts the relevant features and provides information about the features to the attribute generation block 43.
Send to 0. The feature extraction block 420 also provides the alignment factor 424 from the processed form for future use. The alignment factor becomes very important when trying to "line up" the template on the processed form. For example, when a feature such as a line is extracted, the alignment factor affects that line. One example is if the line starts at (x, y) according to the master template, but (x + 2, y + 4) to allow recognition and data extraction due to misalignment during scanning. It can be seen that the alignment factor may be used in to adjust the template.

Attribute generation block 430 receives the extracted features and processes the features to determine the attributes. The attributes are
At least more than one feature, only one feature, or features already used may be used. (All inputs must be independent or orthogonal for the Bayesian classification process to work properly.) However,
Some attributes may be made up of different parts of the feature. The main point is that multiple features may be one attribute and two different attributes may use the same feature. For example, the intersection of vertical and horizontal lines, or the number of lines in the first quarter of the page may be used as an attribute. Of course, many other feature combinations for generating attributes are possible. In addition, the feature generation block 430 applies the correction factor 230 to the attribute to correct any systematic distortion such as scanner offset or skew. Feature extraction and attribute generation occur several times, as discussed for the training system.

The classification process 440 is performed by the attribute generation block 43.
It receives attributes from 0 and determines the classification number 442 and the probability of correctness of the classification number corresponding to the template for the original bitmap form type. The classification process block 440 may be any type of classification process previously described, or as long as it is the same type of classification process used in the training system, as described below. It may be a hierarchical classification process. The hierarchical classification process would provide a classification list of several possible classifications instead of one classification number. The sorted list is a statistical listing by first best choice, then second choice, and so on. The use of a sorted list is convenient to help identify the correct template, and thus reduces the identification error rate. For example, a classification list may be generated for a given input, such that the first classification number in the list is 90% certain and the second classification number in the list is 10% certain. If so, the system automatically processes the incoming bitmap using the first classification number. However, the first classification number on the list is 55% certainty and the second classification number on the list is
If the classification number of is 45% certainty, the system will allow the operator, via the confidence checking function 441, to select which classification number to use for processing. It is also clear that the threshold value may be set to determine when the classification number is automatically selected and when the choice is left to the operator by the confidence check 441. Furthermore, note that some other classification processes, such as the Bayes classification process, also generate a classification list.

The hierarchical classification process is a tree structure set consisting of individual classification processes. There is a component of the classification processing system at each node of the tree. Each component is trained by the classification process training block 1550 of FIG. 9 with a predetermined set of features and classifications. Each outward edge of an interior node is identified by a classification outside the classification set and is valid for components at interior nodes. The hierarchical classification process may be thought of as a procedure for refining (subdividing) form classification as it traverses down the tree.

In the hierarchical classification process, form recognition occurs as follows. First, the form is classified using the valid classifications and features for the components at the root node. For example, it may be the number of horizontal lines. If the root node is a leaf, the hierarchical classification process returns to the classification or classification list predicted by the component, otherwise it is the edge (labeled) identified by the classification predicted by the component. Go down. The classification process is applied recursively until the classification list is determined.

The same type of classification processing may be used in each component, or different types of classification processing may be used in each component. The type of classification process is
It may include a decision tree, a Bayesian classification method, and a nearest neighbor classification process. In this application, form path features are at a higher level of the tree (eg, the number of horizontal or vertical lines on the page), and fine features are at a lower level of the tree (eg, the number of lines in the fine grid). Once the classification number or list of classification numbers is identified, this information is sent to the data extraction block 300. Although the hierarchical classification process are disclosed, it is clear that can be used in any type of system for combining the classification process.

Attribute generation block 4 which is another means
30 can generate attributes by using a random model parameter 1880 that represents a random correction to be applied to the bitmap. The attribute generation block 430 can obtain a random model correction factor 1880, applies the random distribution to one set of attributes, and provides several sets of attributes that differ only in the amount of random distribution applied. The set of all attributes generated by adding random noise to the form is examined at classification processing block 440.
The classification list also helps reduce the error rate due to improper allocation of classification numbers. It is believed that the resulting classification may be x or z, provided that it adds noise to the processed form. The taxonomy list simply increases the chances of selection, reducing changes in a single taxonomy number to be false changes.

Referring also to FIG. 5, a detailed flow diagram of the data extraction block 300 is shown. In general, the information provided by the data extraction system 300 identifies the type of form from which the information was extracted, the identification of the extracted data from the processed form, and the field from which it was extracted. And whether the data was entered. The extracted data will later be
It is sent to the database 1180 (FIG. 7) for storage.

The inputs to the data extraction block 300 are a correction factor 230, a bitmap 242, an alignment factor 424 from the form to be processed, an alignment factor 308 from the master, and a classification number 442 (or
Classification list). The classification number 442 is used by the template store 1260 to find the correct template associated with the bitmap 242.
The template tells you where to find certain fields on the form and enables data extraction. As described above, the template storage unit is a place where all the templates known to the system are stored together with the related information of each template such as the classification number, the field position, the extraction parameter, and the processing rule. Also,
The template information includes what type of recognition system is used to decode the data in each field.

The image realignment block 310 realigns the bitmap 242 into the form template supplied from the template store 1260 utilizing the registration factors 424 from the processed form and the registration factor 308 from the master. It aligns and sends the aligned bitmap to the clipper 314. Bitmap realignment is necessary for the clipper to find and use the correct coordinates. The clipper 314 uses the coordinates of the fields provided in the template information to split the bitmap into several smaller bitmaps 352, 354, 356,
Generate 360 and 362. These smaller clipped bitmaps are output to different recognition systems in the template store 1260 associated with each template, using the information from the templates, according to set instructions. The clipper traces the outer contour of the box. For example, if someone writes outside the allowed space and you want to get all of that information, the clipper will trace the outline of the mark beyond the boundaries of the designated box that captures all the information. .

After clipping, the bitmap 352 containing the textual information is sent to an OCR pre-processing unit 322 which removes noise that may interfere with OCR processing. One example is the noise caused by a colored background. The noise corrected bitmap 364 is sent to the OCR block 326 for decoding. The OCR block 326 is an OCR post-processing block 3 for checking the validity of the text information if possible.
Pass the text information to 30. The inspected text 388 from the OCR post processing block 330 is collected by the extract collection block 342. Also, the dictionary storage unit 1
240 provides information to OCR block 326 and OCR post-processing block 330. Also, status information may be provided in a system such as the OCR post-processing block 330. For OCR, the probability that one character will be corrected is useful information. As one can imagine, other recognition systems have their own extra data that is populated with the extracted information. The extraction collection block 342 is a temporary storage area for storing the extracted data before sending the extracted data as it is filed in the database.

Bitmap 35 from clipper 314
4 contains box inspection information, which is sent to box inspection block 334. Box inspection block 3
34 determines which boxes have been inspected and sends that information to the Box Inspect Post Processing block 338 in the type of Logic 368. Box inspection post-processing block 3
38 provides additional information about the box or boxes inspected. For example, the third box is inspected and the box inspect post-processing block 33.
If 8 knows that the third box means the third Tuesday of the month, then the additional information is that it is the third Tuesday of the month, and that information is extracted in the form of the value 389. It is sent to the collection block 342.

Bitmap 35 from clipper 314
6 is sent to the mark sensing block 346 which determines if the field has been marked. It also detects image cleanup, detection of marks outside the box due to specific fields, and which box is written. The result of mark sense block 346 is logic 370, which is sent to post mark sense processing block 350. Post-mark-sensing processing block 350 checks for errors and sends mark-sensing logic 386 and bitmap 384 to extract-gather block 342.

Similarly, the bitmap 360 is sent to a handprint recognition block 336 which examines what is written to the field and handprints both the text 372 and the bitmap 374 for further processing. Send to post processing block 390. The text 378 and bitmap 380 are then sent to the extract collection block 342. Bitmap 362 contains machine-readable encoded information, such as a barcode, which is decoded by machine-readable code block 340. Machine readable code (MRC) block 34
0 is post MRC post processing block 394 for additional processing.
Determine the text / number information 376 passed to. Next, the text / number information 376 is stored in the extraction collection block 34.
Sent to 2. Various information utilized in the post-processing functions described above may be provided by the recognition initialization system 1000 of FIG. For example, the information from the dictionary storage 1240 is useful for inspecting data in OCR post-processing or for other post-processing functions.

Finally, referring to FIG. 6, the system 10
(FIG. 2) inspection block 500, manual correction block 60
0, and the database insert block 700 is shown. Once the data is extracted from one form, it is convenient to manually inspect the data if an error occurs before entering it in the database. The information from the data extraction block 300 is sent to the range check block 510 of the check block 500, where, for example, a range of numbers and names may be checked if known. For additional checking, consistency check block 520 checks the consistency between the information. For example, a check for valid numbers associated with a recognized name may be performed. If you find a problem,
The data 604 is sent to the manual correction block 600, where the operator views the data to make error determinations and / or corrections. The system is set up to give the operator a hint as to where the error occurred on the form. This is accomplished by emphasizing the area associated with the graphical user interface, or many other ways to clearly indicate the error. If the data is fully examined, the insert database block 700 inserts the data into the database. Note that the template store 1260 provides information to the manual correction block 600, the consistency check block 520, and the range check block 510 to assist the operator.

[Brief description of drawings]

FIG. 1 is a schematic diagram showing the configuration of a general hardware system incorporating the present invention.

FIG. 2 is a top level flow diagram of a form recognition system depicting the major subsystems incorporating the present invention.

FIG. 3 is a flow diagram of an image processing subsystem.

FIG. 4 is a flowchart of a document recognition subsystem.

FIG. 5 is a flow diagram of a runtime data extraction subsystem.

FIG. 6 is a flow diagram of an inspection subsystem, a manual correction subsystem, and a database insertion subsystem.

FIG. 7 is a flow diagram of a recognition initialization subsystem.

FIG. 8 is a flowchart of a new form introduction subsystem.

FIG. 9 is a flow diagram of a new form training subsystem.

FIG. 10 is a flow diagram of a daily scanner calibration subsystem.

Front Page Continuation (72) Inventor Laximi Dasari United States 94306 Palo Alto, California Number 383 Alma Street 3375 (72) Inventor Julia Em. Pagaro United States 95014 Cupertino Stoneydale Drive 10181 California

Claims (1)

[Claims] 1. A method used in a document recognition system for determining settings for a classification process to enable recognition of a master document, the method comprising: a) inputting one master document a plurality of times and, as a result, Producing a plurality of master bitmaps representing a master document, b) extracting features from the plurality of master bitmaps, and c) generating attributes by combining the features with a random model parameter distribution, Resulting in a number of said plurality of attributes substantially greater than the number of said plurality of master bitmaps, d) repeating steps a) to c) for all said master documents, and e) all Cluster analysis is performed on the attributes from the master manuscript of the Generating a plurality of superclasses that represent a master script and a plurality of non-superclasses that represent a master manuscript that is not a member of the family; , A step of generating a classification process setting that enables recognition of the master document, and