US 5,521,991 AGrant
Method and System for Fast Forms Recognition of Document Form Images
Issue Date:1996-05-28
•12 Claims
•40 Drawing Sheets
Abstract
The pixel count value in each cell of an array of cells located on a set master forms. Each completed form is scanned into a data processing system and the scanned image is compressed and buffered. In accordance with the invention, when the compressed, completed form is ready to be analyzed, only its top part needs to be decompressed. A form signature set is prepared for the decompressed part of the completed form in the same manner as the master signature set was prepared. The first N rows of the form need to be decompressed and a form signature set created from a pixel count value on each cell of an array of cells located in the decompressed portion of the completed form. The form signature set is compared to the master signature set to determine the best match.
Metadata
Assignee
- International Business Machines Corporation
Inventor
- Douglas W. Billings
Application Information
Application Number:US 1435183
Filing Date:1993-10-29
Priority Date:1993-10-29
Art Unit:263
Classifications
IPC:
G06K 920
Field of Search:
38235839561;30;56;41;317;192;193;194;203;209;233;243;282453148;149
Patent Drawings (40 sheets)
Description
BACKGROUND OF THE INVENTION
1. Technical Field
The invention disclosed broadly relates to data processing and more particularly relates to forms recognition of document forms.
2. Background Art
This patent application is related to the U.S. Pat. No. 5,251,273 entitled "Data Processing System and Method for Sequentially Repairing Character Recognition Errors for Scanned Images of Document Forms," by T. S. Betts, et al., the application being assigned to the IBM Corporation and incorporated herein by reference.
This patent application is also related to the U.S. Pat. No. 5,305,396 entitled "Data Processing System and Method for Selecting Customized Character Recognition Processes and Coded Data Repair Processes for Scanned Images of Document Forms," by T. S. Belts, et al., the application being assigned to the IBM Corporation and incorporated herein by reference.
This patent application is also related to U.S. Pat. No. 5,140,650, entitled "A Computer Implemented Method for Automatic Extraction of Data From Printed Forms," by R. G. Casey, et al., the patent being assigned to the IBM Corporation and incorporated herein by reference.
This patent application is also related to the U.S. Pat. No. 5,455,872 entitled "System and Method for Enhanced Character Recognition Accuracy by Adaptive Probability Weighting," by M. P. T. Bradley, the application being assigned to the IBM Corporation and incorporated herein by reference.
This patent application is also related to copending U.S. patent application by D. W. Billings, et al. entitled "Method for Defining a Plurality of Form Definition Data Sets," Ser. No. 08/100,846, filed Aug. 2, 1993 now pending, the application being assigned to the IBM Corporation and incorporated herein by reference.
3. Background Art
The referenced Billings, et al patent application, describes how forms are created by a forms definition utility program. A forms definition data set is prepared at a data center, which characterizes the preprinted background of the master form. The forms definition data set is associated with a form ID. Copies of the master form are distributed to persons who will fill out the fields entering data by hand or by typewriter. The completed forms are returned to the data center and are scanned into the system. To accommodate sessions of high volume scanning of submitted forms, the image of each form is compressed and buffered until there is an opportunity to continue its processing.
The compressed form is then decompressed, and the image of the completed form is subjected to a forms recognition program to identify the ID of the form. Once identified, the master form definition data set can be accessed. This enables the system to locate the fields on the form and subtract out the preprinted background of the form. The extracted field images can then be presented to a character recognition program, which analyzes them and outputs alphanumeric strings representing the images of the data in the fields. If there are suspicious characters or errors in the recognition process, the character recognition program will also output error statistics.
Several problems surround conventional techniques to perform forms recognition. First, the speed of forms recognition is relatively slow, when compared to other steps in forms processing. Many conventional forms recognition algorithms are slow, such as line geography techniques. The process of decompressing the compressed image is also slow, since conventional techniques are based on analyzing the entire page of the form, requiring the entire form to be decompressed. In addition, significant problems appear with the condition of the completed forms, themselves. Many submitters fold, spindle, staple or otherwise mutilate the form, and each artifact will appear in the image of the form. Such artifacts reduce the accuracy of forms recognition and occasionally the wrong ID is attributed to a completed form image. This will not be apparent until the character recognition program returns high error statistics for the form.
OBJECTS OF THE INVENTION
It is therefore an object of the invention to increase the speed of forms recognition.
It is another object of the invention to provide a faster forms recognition method.
It is another object of the invention to provide a more accurate forms recognition method.
It is another object of the invention to provide a faster forms recognition method, that does not require the entire form to be decompressed.
It is another object of the invention to provide a more accurate forms recognition method, that compensates for the average condition of the completed forms.
It is another object of the invention to provide a more accurate forms recognition method, that compensates for the average artifacts which appear in the image of the form.
It is another object of the invention to provide a more accurate forms recognition method, that compensates for the average condition of the form in response to the character recognition program returning high error statistics for the form.
SUMMARY OF THE INVENTION
These and other objects, features and advantages are accomplished by the fast forms recognition invention disclosed herein. In one aspect of the present invention when a new master form is processed, a master signature set is computed.
The form signature set is compared with the master signature set. A difference matrix is computed, taking the difference between the pixel counts for each cell in the master and in the completed form. This is done for each master signature set in the system, until a best match is found between the completed form and one of the master forms. Several analytical processing techniques are disclosed to determine the best match. One technique which has been found superior to others, is squaring each difference value and summing the squares. This sum is then divided by the sum of the squares for the master form being tried in the matching process. That master form having the lowest ratio, is most likely the best match among the master forms. Several other matching techniques are also disclosed. These methods are faster than the line geography technique and they also contribute the an improvement in the speed of forms recognition.
When the best match master form is identified, its form ID is sent to the field extraction program and the character recognition program. The field extraction program locates the fields of the form, using the form definition data set identified by the ID value. The field images are separated from the image of the preprinted background. The extracted field images are then processed by the character recognition program.
Another aspect of the invention is an automatic learning process, by which the invention can make adjustments to the master signature set or alternately to a weighting mask used with the master signature set, in response to error statistics reported by the character recognition program for that master form. The adjustments are made to reduce the sensitivity to those cells which frequently bear random marks, that confuse the distinctions between otherwise different master forms. Adjustments can also be made to increase the sensitivity to those cells which are typically constant in their pixel value for one master form, and significantly different in the cell value for all other master forms stored in the system.
To make the adjustment to reduce the sensitivity to those cells which have randomly variable pel counts, the invention monitors the error statistics reported by the character recognition program. If one particular master form ID is found to be causing more than a predetermined threshold quantity of errors, the invention enters a learning mode. In this mode, the invention stores the form signature set for each completed form that is processed for forms recognition, having the ID of the master form causing the high error statistics. After a predetermined quantity of forms having that ID have been accumulated, their form signature sets are analyzed. The analysis computes the standard deviation for a given cell location over all of the accumulated forms having that ID. If a given cell location has a relatively large standard deviation in the pixel count, that cell is considered to have randomly variable markings in the completed forms. In accordance with the invention, the effect of that cell is reduced in the matching process, when that master form is being matched with a completed form. One technique for reducing the sensitivity of the matching process to a cell, is by modifying a weighting set associated with that master form's master signature. The weighting set is an array of multiplicative values, one for each cell. For example, when the master form is defined, all of the values in the weighting set can have the value of unity. Each time the master form signature set is compared with a form signature set, each value in the difference matrix can be multiplied by the weight for that cell in the weighting set. When the sensitivity of the matching process is to be reduced for a particular cell, the value of the weight for that cell is reduced. In this manner, the invention learns which of the cells are variable for a given master form, and those cells are less important to the natching process for finding the ID of a completed form.
DESCRIPTION OF THE FIGURES
These and other objects, features and advantages will be more fully appreciated with reference to the accompanying figures.
FIG. 1 is a architecture block diagram of the invention.
FIG. 2 illustrates an example image compression technique.
FIG. 3A shows the grid 102.
FIG. 3B shows the master A signature set 104A.
FIG. 3C shows the master A bit map image 110A.
FIG. 3D shows the values of master A signature set 104A from master A bit map image 110A.
FIG. 3E shows master B signature set 104B.
FIG. 3F shows master B bit map image 110 (1040EZ).
FIG. 3G shows the values of the master B signature set 104B for the master B bit map image 110B.
FIG. 3H shows the master C signature set 104C.
FIG. 3I shows the master C bit map image 110C (1040A).
FIG. 3J shows the values of master C signature set 104C for master signature C bit map image 110C.
FIG. 3K shows the square of values of master A signature set 104A for master A bit map image 110A.
FIG. 3L shows the square of values of master B signature set 104B for master B bit map image 110B.
FIG. 3M shows the square of values of master C signature set 104C for master bit map image 110C.
FIG. 4A shows the form 1 signature set 106(1).
FIG. 4B shows the form 1 bit map image 112(1).
FIG. 4C shows the values of form 1 signature set 106(1) for form 1 bit map image 112(1).
FIG. 4D shows the form 2 signature set 106(2).
FIG. 4E shows the form 2 bit map image 112(2).
FIG. 4F shows the values of form 2 signature set 106(2) for form 2 bit map image 112(2).
FIG. 4G shows the form 3 signature set 106(3).
FIG. 4H shows the form 3 bit map image 112(3).
FIG. 4I shows the values of form 3 signature set 106(3) for form 3 bit map image 112(3).
FIG. 5A shows the difference values between values of master A signature set 104A and values of form 1 signature 106(1).
FIG. 5B shows difference values between values of master B signature set 104B and values of form 1 signature set 106(1).
FIG. 5C shows difference values between values of master C signature set 104C and values of form 1 signature set 106(1).
FIG. 6A shows the square of difference values between values of master A signature set 104A and values of form 1 signature set 106(1).
FIG. 6B shows the square of difference values between values of master B signature set 104B and values of form 1 signature set 106(1).
FIG. 6C shows the square of difference values between values of master C signature set 104C and values of form 1 signature set 106(1).
FIG. 7A shows weighting values for master A signature set 104A.
FIG. 7B shows weighting values for master B signature set 104B.
FIG. 7C shows weighting values for master C signature set 104C before adaptive weighting step.
FIG. 7D shows weighting values for master C signature set 104C after adaptive weighting step.
FIG. 7E shows after the adaptive weighting step, the square of difference values between values of master C signature set 104C and values of form 1 signature set 106(1).
FIG. 7F shows after the adaptive weighting step, the square of values of master C signature set 104C for master C bit map image 110C.
FIG. 8A shows the flow diagram of the process to define the master signature set 300.
FIG. 8B shows the flow diagram of the training mode 345.
FIG. 8C shows the process of getting the next completed form when using the weight set, the program 375.
FIG. 9 depicts a bit map of a 1040 income tax form, showing the location of a cell array used for forms recognition, in accordance with the invention.
DISCUSSION OF THE PREFERRED EMBODIMENT
The invention disclosed herein solves the problem of increasing the speed of forms recognition while maintaining accurate forms recognition results. The invention provides faster forms recognition by not requiring the entire compressed form to be decompressed. The invention provides more accurate forms recognition that compensates for the average condition of completed forms. The invention provides more accurate forms recognition that compensates the average artifacts which appear in the image of a form. The invention provides a more accurate :forms recognition by compensating for the average condition of the form in response to the character recognition program returning high error statistics for the form.
FIG. 1 shows an overall functional block diagram of the invention. The system shown in FIG. 1 includes a forms definition processor 800 and a recognition processor 850. Both of these processors could be combined into a single workstation processor, however it is helpful to show them as separate processors to clarify the description of the system. The forms definition processor 800 includes the memory 802 which is connected by means of the bus 815 to the CPU 810, the keyboard and display 818, and the mouse pointing device 820. The bus 815 is also connected to the scanner 812, the disk drive 814, and the local area network (LAN) adapter 816. The local area network adapter 816 is connected over the local area network 845 to the local area network adapter 876 of the recognition processor 850.
The memory 802 of the forms definition processor 800, includes partitions for the signature definition program 300, three example master signature sets 104A, 104B, and 104C, of the form signature set 106. Also included are partitions for a scanned-in form partition 804, the training mode program 345, and the register for the form ID 303. A weight set storage 806 is included along with a document image handling program 807, a document image compression program 808, and an operating system 809. All of the programs stored in the memory 802 are sequences of executable instructions, which were executed on the CPU 810, perform the intended operations.
The recognition processor 850 includes the memory 852, which is connected over the bus 875 to the LAN adapter 876, the disk drive 874, the scanner 872, the CPU 870, the keyboard and display 878, and the mouse pointing device 880. The memory 852 of the recognition processor 850, includes partitions for the character recognition program 750, document image decompression program 854, form image partition 856, and a form ID register 303. Also included are three example master form definition data sets 125A, 125B and 125C. Also included are partitions for storing the output fields corresponding to the three different master form definition data sets 125A, 125B, and 125C, those partitions being the fields alphanumeric (A), fields alphanumeric (B), and fields alphanumeric (C), abbreviated "A/N(A), etc. Also included are partitions for storing the errors for suspicious characters and misrecognized characters output from the character recognition program 750, in conjunction with master form definition data set 125A, 125B and 125C, those partitions being the error partitions 865A, 865B and 865C. Also included in the memory 852 is the document image handling program 807 and the operating system 809. The program stored in the memory 852, are sequences of executable instructions which, when executed in the CPU 870, carry out the intended operations.
FIG. 2 is an illustration of the principles of image compression, as it is used in conjunction with the invention disclosure N. Additional information on image compression can be found in the above cited Billings patent application. FIG. 2 illustrates an example of a form image A3205 which the fields 208", 200" and 206" are shown with their corresponding run length encoding compression fields 208R, 200R and 206R, respectively. It is seen that near the top of the form 205, a line of characters 202 exist and also near the bottom of the form another several lines of characters 210 exist. In FIG. 2 it is seen that the corresponding lines of black and white pixels in the form 205, are arranged in a vertical manner. Compression proceeds from the top of the form to the bottom. Decompression would also proceed from the top of the form to the bottom, requiring the decompression operation to proceed through most of the lines of the form 205, before getting to the bottom portion of the lowest field of interest, 206". This would require a substantial amount of time for decompression.
One of the features of the invention disclosed herein, is that it reduces the amount of the compressed image which must be decompressed in order to perform a fast and accurate forms recognition operation.
Turning now to FIG. 3A, the figure shows a grid 102 which is laid out at the top of the form 100, for performing forms recognition in accordance with the invention. It is seen at the top portion of the form 100 is a decompressed image portion 108, and the remaining compressed image portion 108', is not decompressed in order to carry out a fast and accurate forms recognition operation.
FIG. 3B shows an example signature set 104A for a first master form, master A. In accordance with the invention, when a new master form is processed, the invention computes a master signature set. This is the pixel count value in each cell of an array of cells located near the top of the master form. The pixel cells in FIG. 3B are labeled in standard matrix notation, MA(1,1), etc. with the first index being the row and the second index being the column for the matrix of FIG. 3B. When each completed form is scanned into the system, it is compressed and buffered. In accordance with the invention, when the compressed completed form is ready to be analyzed, only its top part needs to be decompressed. A form signature set is prepared for the decompressed pan of the completed form in the same manner as the form signature set was prepared. One aspect of the invention is the limitation of the array of cells in the upper part of the form, thereby rendering unnecessary the need to decompress more than that part of the form. By merely decompressing the first N rows of the form, the rest of the form does not have to be decompressed. For example in FIG. 3B, the first eight rows of the form are decompressed. This makes one contribution to improving the speed of forms recognition, in accordance with the invention.
FIG. 3C shows the master A bit map image 110A which has been scanned into the system, compressed and buffered. Thereafter, the compressed image file was decompressed so that the top eight lines of the image are displayed, as is shown for the black pixel matrix 105A for the form 100A of FIG. 3C.
FIG. 3D shows the values of the master A signature set 104A for the master A bit map image 110A. This is for the form 100A which is shown in FIG. 3C and whose signature set notation is shown in FIG. 3B. The computation of the values for each cell in the master signature set 104A of FIG. 3D, is simply to count the number of pixels in each respective cell and as the value of the cell. In some applications, if the cell is large enough to encompass many pixels so that a very large number is encountered, all of the pixel counts for the all of the cells can be decreased by the same fraction for convenience of the computation.
FIGS. 3E, 3F and 3G pertain to a second master B form, with FIG. 3E showing the master B signature set notation, FIG. 3F showing the bit map image of the form, and FIG. 3G showing the values in the master B signature set for form 100B.
FIGS. 3H, 3I and 3J show a third master C form, with FIG. 3H showing the master C signature set notation, FIG. 3I showing the bit map image for master C form 100C, and FIG. 3J showing the values in the master C signature set 104C.
Later it will be shown that for one form of a matching process, the square of the values of each master signature set are required. This is provided in FIGS. 3K, 3L and 3M, for the master signature sets 104A, 104B and 104C, respectively, getting the square of the values 115A, 115B and 155C, respectively.
One aspect of the invention is the comparison of the form signature set with the master signature set. A difference matrix is computed, taking the difference between the pixel counts for each cell in the master and in the completed form. This is done for each master signature set in the system, until a best match is found between the completed form and one of the master forms. Reference is made to FIGS. 4A, 4B and 4C, which show a first completed form, form 1. FIG. 4A shows the notation for form 1 signature set 106(1), FIG. 4B shows the black pixel matrix 105(1) for the form 1 bit map image 112(1), and FIG. 4C shows the values of form 1 signature set 106(1) for form 1 bit map image 112(1). It is seen in FIG. 4C that each cell has a value equal to the number of pixels which appear in it.
FIGS. 4D, 4E and 4F show a similar set of three figures for a second completed form, form 2. FIG. 4D shows the signature set 106(2), FIG. 4E shows the bit map image 112(2), and FIG. 4F shows the values of the form 2 signature set 106(2).
FIGS. 4G, 4H and 4I show a similar set of three figures for a third completed form, form 3. FIG. 4G shows form 3 signature set 106(3), FIG. 4H shows the bit map image 112(3), and FIG. 4I shows the values of form 3 signature set 106(3).
Examination of FIGS. 4B, 4E and 4H will show that all three bit maps are the same basic master image form, a 1040A tax form. It should be noted that there is a mark sense box in the lower left corner of the grid 102. It should also be noted that there is an artifact contained in the box at the lower left corner which varies in its configuration between FIGS. 4B, 4E and 4H. One aspect of the invention is an automatic learning process, by which the invention can make adjustment to the master signature set or alternately to a weighting mask used with the master signature set, in response to error statistics recorded by the character recognition program for that master form. Adjustments are made to reduce the sensitivity to those cells which frequently bear random marks, that confuses the distinctions between otherwise different master forms. This is shown in the example of FIGS. 4B, 4E and 4H.
The comparison of the form signature set with the master signature set can be conducted in several methods. However in each, a difference matrix is computed, taking the difference between the pixel counts for each cell in the master and in the completed form. This is shown in FIGS. 5A, 5B and 5C, for the difference values between the form 1 signature set 106(1) and each of three master signature sets 104A, 104B and 104C. The array 120A for the difference values with respect to master A signature set, use the matrix notation DA(1,1), etc.; similarly for 120B in FIG. 5B and 120C in FIG. 5C.
Several analytic processing techniques can be used to determine the best match. One technique which has been found superior to the others, is squaring each difference value and summing the square. This sum is then provided by the sum of the squares for the master form being tried in the matching process. That master form having the lowest ratio, is most likely the best match among the master forms. If a form which has been identified as a best matching form using the squaring technique, is subsequently sent to the character recognition processor, character recognition operations will be performed using the forms definition data set corresponding to that identified master form. If the character recognition processor outputs a high error statistic while using that master form, this can be reported back from the recognition processor 850 back to the forms definition processor 800, and the second most likely candidate master form can then be substituted for a second trial.
FIGS. 6A, 6B and 6C prepare for the squaring process for matching. FIG. 6A is the array 130A which is the square of the difference values between values of master A signature set 104A, and values of form 1 signature set 106(1). FIG. 6B is a similar array 130B, for the master B signature set. FIG. 6C is a similar array 130C for the master C signature set 104C.
The sum of the square of the difference values in the master A signature set and the values of form 1 signature set is 482. The sum of the square of the difference values for the master B signature set in form 1 is 760. The sum of the square of the difference values between the master C signature set and form 1 is eight.
Referring back to FIGS. 3K, 3L and 3M, the square of the values of the master A signature set 115A is 493. The square of the value of the master B signature set is 605, and the square of the values of the master C signature set is 283.
The sum of the square is then divided by the sum of the squares for the master form being tried in the matching process. Thus, in comparing FIG. 6A with FIG. 3K, for the square of the difference values between master A and form 1 divided by the square of the values for the master A signature set, a ratio of 482 divided by 493 equal 0.98.
In comparing FIG. 6B and FIG. 3L, the square of the difference values between master B signature set and form 1 signature set and the square of the values of master B signature set, the ratio is 760 divided by 605 which equals 1.26.
Comparing FIG. 6C with FIG. 3M, the square of the difference values between the master C signature set and the form 1 signature set divided by the square of the values of the master C signature set is eight divided by 283 which equals 0.03.
That master form having the lowest ratio, is the most likely to be the best match among the master forms. Thus, in accordance with the operation of the invention for this example, the master C signature set 104C is the most likely match for the form 1 signature set 106(1).
When the best match master form is identified, its form ID is sent to the field extraction program and the character recognition program. The fields extraction program locates the fields on the form, using the form definition data set identified by the ID value. The field images are separated from the image of the preprinted background. The extracted field images are then processed by the character recognition program.
Another aspect of the invention is the automatic learning process, by which the invention can make adjustments to the master signature set or alternately to a weighting mask used with the master signature set. This is done in response to error statistics reported by the character recognition program for that master form. The adjustments are made to reduce the sensitivity to those cells which frequently bear random marks, that confuse the distinctions between otherwise different master forms.
In an alternate embodiment, adjustments can also be made to increase the sensitivity to those cells which are typically constant in their pixel value for one master form, and significantly different in the cell value for all other master forms stored in the system.
To make the adjustment to reduce the sensitivity to those cells which have randomly variable pel counts, the invention monitors the error statistics reported by the character recognition program. If one particular master form ID is found to be causing more than a predetermined threshold quantity of errors, the invention enters a learning mode. In this mode, the invention stores the form signature set for each completed form that is processed for forms recognition, having the ID of the master form causing the high error statistics. After a predetermined quantity of forms having that ID have been accumulated, their form signature sets are analyzed.
The analysis computes the standard deviation for a given cell location over all of the accumulated forms having that ID. If a given cell location has a relatively large standard deviation in the pixel count, that cell is considered to have randomly variable markings in the completed forms.
In accordance with the invention, the effect of that cell which is found to be variable, is reduced in the matching process, when that master form is being matched with a completed form. One technique for reducing the sensitivity in the matching process to a cell, is by modifying a weighting set associated with that master form's master signature. The weighting set is an array of multiplicative values, one for each cell. For example, when the master form is defined, all of the values in the weighting set can have the value of unity. Each time the master form signature set is compared with the form signature set, each value in the difference matrix can be multiplied by the weight for that cell in the weighting set. When the sensitivity of the matching process is to be reduced for a particular cell, the value of the weight for that cell is reduced. In this manner, the invention learns which of the cells are variable for a given master form, and those cells are made less important to the matching process for finding the ID of a completed form.
Reference to FIGS. 7A, 7B, 7C and 7D show weighting values. FIG. 7A shows the array 140A, which are the weighting values for the master A signature set 104A. The weighting value notation is a standard matrix notation, for example WA(1,1), etc. The weighting values for the master A form in FIG. 7A are all set equal to unity.
FIG. 7B shows the weighting values in the array 140B, for the master B signature set 104B. All of the weighting values in the array 140B in FIG. 7B are set equal to unity.
FIG. 7C shows the array 140C for the weighting values for the master C signature set 104C, before the adaptive weighting step. The array 140C has all of its cells set equal to unity before the adaptive weighting step.
FIG. 7D shows the array 140C', which are the weighting values for the master C signature set 104C, as were shown in FIG. 7C, except that FIG. 7D is after the adaptive weighting step. It is of particular significance that the four cells 142, namely WC(6,1), WC(6,2), WC(7,1), and WC(7,2), have been reduced in their value from their original value of one, to a new value of zero, in response to the invention determining that those four cells are variable cells. Those four cells must have their significance reduced in their matching process, in accordance with the invention.
FIG. 7E shows the array 120C, which is after the adaptive weighting step, which takes the square of the difference values between the values for the master C signature set 104C and the values of the form 1 signature set 106(1). FIG. 7E should be compared with FIG. 6C which shows the original values where the difference values between master C signature set and form 1 signature set.
FIG. 7F shows the array 115C, after the adaptive weighting step, which is the square of the values of the master C signature 104C. It is to be noted that the cells 122 have their values reduced to zero. Referring back to FIG. 7E, it should be noted that cells 132 have had their values reduced to zero. The sum of the squares of the difference values between master C and form 1 in FIG. 7E is equal to zero. In FIG. 7F, after the adaptive weighting step, the sum of the squares of the values of the master C signature set are equal to 279. The ratio of the squares of the difference values between master C signature set and form 1 signature set after adaptive weighting (FIG. 7E) are divided by the sum of the squares of the values in the master C signature set after adaptive weighting (FIG. 7F), is zero divided by 279 which equals zero. This recomputation of matching ratio for the master C signature set and the form 1 signature set, removes any sensitivity which may exists for the four cells in the master C form 100C, corresponding to the mark sense box in the lower left-hand corner.
FIG. 8A shows the flow diagram of the process 300 to define the master signature set. It goes from steps 302 to 342. Step 302 gets a compressed image of the master form. Step 304 decompresses the first N rows of the bit map image 110 of the master form. Step 306 builds a master signature set 104. Step 308 stores the master signature set 104 in signature storage. Step 320 gets the next completed form. Step 322 decompresses the first N rows of the bit map image 112 of the completed form. Step 234 builds the form signature set 106. Step 326 compares the form signature set 106 with each master signature set 104 in the signature storage until the best match master is found. Step 328 attributes the form ID of the completed form as the ID of the best match master. Step 330 outputs form ID to the character recognition process. Step 340 monitors error statistics for form ID from character recognition process. In step 342, if error statistics for form ID are greater than threshold, then begin the training mode.
FIG. 8B shows the program 345 to begin the training mode. The training mode program goes from step 350 to step 374. Step 350 begins the training mode. Step 352 saves each form signature set 106 for which the form ID is inferred. Step 354 accumulates the saved signature sets for the form ID until a statistically significant quantity is accumulated. Step 356 begins cell analysis for saved signature sets. Step 360 computes the standard deviation of the cell value for each cell of the form for quantity of the accumulated forms. Step 362 identifies the variable content cells by a relatively large value for the standard deviation. Step 364 identifies constant content cells by a relatively small value for the standard deviation. Step 366 computes the average cell value for each constant content cell of the form over quantity of the accumulated forms. In step 368, for each identified constant content cell, begin analysis over all master signature sets 104 in a signature storage for the cell in the same relative location. Step 370 identifies by chi-square analysis, all cells of the form having the distinct cell values. Step 371 identifies by chi-square analysis, that row of the form having the most distinct row value. Step 372 builds the weight set for the form, with the reduced weight values for the variable cells and the increased weight values for the constant cells, or builds the new master signature set 104' with the reduced values for the variable cells and the increased values for the constant cells. Step 374 stores the weight set for the form or stores the new master signature set 104'.
FIG. 8C shows the program 375 to get the next completed form. The program 375 goes from steps 380 to 392. Step 380 gets the next completed form. Step 382 decompresses the first N rows of the bit map image 112 of the completed form. Step 384 builds the form signature set 106'. Step 386 compares the form signature set 106 with each master signature set 104 using the weight set for comparison of the master form signature set 104' with the form signature set 106', continuing comparison with all master forms until the best match master is found. Step 388 attributes form ID of the completed form as the ID of the best match master. Step 390 outputs the form ID to the character recognition process. Step 392 then returns.
The resulting invention provides a more accurate forms recognition method which operates faster, and compensates for the average condition of the form in response to the character recognition program returning high error statistics for the form. The following are some examples in connection with FIG. 9, which is a bit map of a 1040 income tax form, showing the location of an eight row by 16 column cell array which is used for forms recognition, in accordance with the invention.
Example 1 is a description of the proposed steps for this method. Most of these steps have already been implemented in the prototype code. Also included is a simple example of how the process works.
Example 2 is a listing of the actual "forms signature" file with the prototype code. Seven different forms have been defined in a form set. For each form, there is a form name and a matrix of black pixel counts for the area of interest on the form. As can be seen by inspection that the matrices for the different form types are different. There are two versions of the "4562 back" form type which are slightly different.
Example 3 (refer to FIG. 9) is a listing of actual output from the prototype code. Included are runs from three different candidate images: a 1040 front, a 4562 back, and a Schedule B. Each run contains, among other things, the signature of the form (compare with those in the signature set file) and the output from four different methods for computing the difference between the candidate form and the forms in the signature set. The four differences are:
"0 deriv"- same as Method 1 in the text.
"1 deriv"- same as Method 4 in the text.
"squared"- same as Method 2 in the text.
"avg diff"- same as Method 3 in the text.
The results seem to show that the "squared" method is the best, as this emphasizes differences more than the other methods.
EXAMPLE 1
High-level Description of "Fast Forms Recognition" Steps:
Setup steps
For each form type to be included in the recognition list
Obtain a bit map image of the form type. This should be one that is most similar to those expected to be seen in the future, i.e. pick one that has average data on the form, average skew, average darkness, etc.
Decompress the first n rows of the image. The value of n is equal to the number of rows to skip on the top, plus the number of rows to process. Some rows should be skipped at the top because most forms have a white border at the top, which does not contain any form-specific information to store.
Build a 2-dimensional histogram of the form pixels using n rows and m columns of the image. The value of m is recommended to be the width of the form, not including any white borders which do not contain any form information. For example, a form which is 8 inches wide but with 1 inch white borders on each side should have 6 inches of pixels to process. The resulting histogram will be an n.times.m matrix of black pixel counts in the image. For simplicity, the pixel counts can be scaled down, such as by dividing each count by 10. Resolution independence can be achieved by scaling the counts based on the resolution of the input image. For 300 dpi images, for example, the pixel counts can be divided by 9. For 200 dpi images, the pixel counts can be divided by 4. This will produce comparable pixel counts regardless of the image resolution. Also, by not processing the borders of the image, any black borders commonly introduced during the scanning of the image will be properly ignored.
Store the pixel count matrix (hereafter named "form signature") in a file for later processing. Include the name of the form, also.
Repeat for each form type.
Form recognition steps
Decompress the first n rows of the candidate form.
Build a histogram in the same manner as above.
For each form type in the form signature set:
Compute the difference between the candidate form and the form in the form signature set. Methods for computing this difference are described below.
(Optional) If the difference is small enough, stop processing and return the current form type. This is assumed to be the form type of the candidate form.
Repeat for all form types or until done.
Choose the form type with the smallest difference between it and the candidate form. This is assumed to be the form type of the candidate form. (Optional) Mark the form as "unrecognized" if either a) the difference is too high, or b) the difference between the top choice and the second choice is too small (i.e. not confident enough between top choices).
(Optional) If the top 2 (or more) choices are close in total score (difference), then perform additional form recognition steps on just those form types. Or, if the top 2 (or more) choices are all part of the same form "class", then return just this form class as the recognized form class (not type). Example: there may be several varieties of a 1040 form (e.g. different years of the same form) which all score well. In this instance, the specific form type may not be recognized (e.g. 1988 vs 1989), but the general form class of "1040" is recognized.
Methods for computing difference
NOTE: Other, improved methods may be added in the future.
1) Sum the difference of all n.times.m matrix elements and divide by the greater of the total candidate or signature count.
2) Same as 1, but square each of the differences.
3) For each matrix element, divide the pixel count by the greater of the candidate or signature count. Sum these values.
4) Sum the first derivatives of the matrix elements, horizontally.
5) Sum the first derivatives of the matrix elements, vertically.
6) Sum the second derivatives of the matrix elements, horizontally.
7) Sum the second derivatives of the matrix elements, vertically.
EXAMPLE
Rows of interest on Form A look like: ##STR1##
Rows of interest on Form B look like: ##STR2##
Contents of signature file:
Candidate form looks like: ##STR3##
Candidate matrix looks like:
Difference calculations for some of the difference methods. Matrices shown am the difference matrices obtained with the appropriate method.
EXAMPLE 2
EXAMPLE 3
No definitions may be made to the specific embodiment disclosed. For example, a different number of rows may be decompressed to identify the specific document type.
Although a specific embodiment of the invention has been disclosed, it will be understood by those having skill in the art, that changes can be made to that specific embodiment without departing from the spirit and the scope of the invention.
Claims
What is claimed is:
1. In a data processing system, a method for forms recognition, comprising the steps of: computing a master signature set for a new master form, by computing a pixel count value in each cell of an array of cells located in a portion of the master form; scanning a completed form into the system, and compressing and buffering it as a compressed image; decompressing only said portion of said compressed image of said completed form: computing a form signature set for said decompressed portion of said completed form by computing a pixel count value in each cell of an array of cells located in said portion of said completed form; comparing said form signature set with said the master signature set, and computing a difference matrix; repeating said step of comparing said form signature set for each master signature set in the system, until a best match is found between said completed form and one master form; and selecting the best match as the master form type of the completed form.
2. In a data processing system, a method for forms recognition, comprising the steps of: computing a master signature set for a new master form, by computing a pixel count value in each cell of an array of cells located in a portion of the master form; scanning a completed form into the system, and compressing and buffering it as a compressed image; decompressing only said portion of said compressed image of said completed form; computing a form signature set for said decompressed portion of said completed form by computing a pixel count value in each cell of an array of cells located in said portion of said completed form; comparing said form signature set with said the master signature set, and computing a difference matrix; squaring each difference value in said difference matrix and summing the squares to obtain a sum; dividing said sum a sum of the squares for said master signature set to obtain a ratio; repeating said steps of comparing, squaring and dividing using said form signature set, for each master signature set in the system; identifying a master form in said system having a lowest value for said ratio, as a most likely the best match among all master forms in said system; and selecting the best match as the master form type of the completed form.
3. In a data processing system, a method for forms recognition, comprising the steps of: computing a master signature set for a new master form, by computing a pixel count value in each cell of an array of cells located in a portion of the master form; scanning a completed form into the system, and compressing and buffering it as a compressed image; decompressing only said portion of said compressed image of said completed form; computing a form signature set for said decompressed portion of said completed form by computing a pixel count value in each cell of an array of cells located in said portion of said completed form; comparing said form signature set with said the master signature set, and computing a difference matrix; repeating said step of comparing said form signature set for each master signature set in the system, until a best match is found between said completed form and one master form; selecting the best match as the master form type of the completed form; monitoring error statistics reported by a character recognition program using an ID of said best match one master form; identifying particular master form ID causing more than a predetermined threshold quantity of said error statistics, as having high error statistics; starting a learning mode by storing a plurality of form signature sets for completed forms processed having said ID of said master form causing said high error statistics; accumulating a predetermined quantity of forms signature sets having said ID; analyzing said form signature sets by computing a standard deviation for a given cell location over all of said accumulated forms having said ID; identifying a given cell location having a relatively large standard deviation in its pixel count, as having variable markings in said completed forms; and reducing the effect of said given cell in said matching process.
4. The method of claim 3, which further comprises: reducing the sensitivity of the matching process to a cell, by modifying a weighting set associated with said master form's master signature; said weighting set being an array of multiplicative values, one for each cell.
5. The method of claim 4, which further comprises: initially assigning all of the values in the weighting set to have the value of unity; during said comparing step, multiplying each value in the difference matrix by the weight for that cell in the weighting set.
6. The method of claim 5, which further comprises: reducing the sensitivity of the matching process for a particular cell, by reducing the value of the weight for that cell; whereby the system learns which of the cells are variable for a given master form, and those cells are made less important to the matching process for finding the ID of a completed form.
7. A data processing system for forms recognition, comprising: first computing means for computing a master signature set for a new master form, by computing a pixel count value in each cell of an array of cells located in a portion of the master form; scanning means for scanning a completed form into the system, and compressing and buffering it as a compressed image; decompressing means for decompressing only said portion of said compressed image of said completed form; said computing means computing a form signature set for said decompressed portion of said completed form by computing a pixel count value in each cell of an array of cells located in said portion of said completed form; comparing means for comparing said form signature set with said the master signature set, and computing a difference matrix; said comparing means repeating said comparing said form signature set for each master signature set in the system, until a best match is found between said completed form and one master form.
8. A data processing system for forms recognition, comprising: first computing means for computing a master signature set for a new master form, by computing a pixel count value in each cell of an array of cells located in a portion of the master form; scanning means for scanning a completed form into the system, and compressing and buffering it as a compressed image; decompressing means for decompressing only said portion of said compressed image of said completed form; said computing means computing a form signature set for said decompressed portion of said completed form by computing a pixel count value in each cell of an array of cells located in said portion of said completed form; comparing means comparing said form signature set with said the master signature set, and computing a difference matrix; said computing means squaring each difference value in said difference matrix and summing the squares to obtain a sum; said computing means dividing said sum a sum of the squares for said master signature set to obtain a ratio; said comparing means repeating said comparing, squaring and dividing using said form signature set, for each master signature set in the system; said comparing means identifying a master form in said system having a lowest value for said ratio, as a most likely the best match among all master forms in said system.
9. In a data processing system, a system for forms recognition, comprising: first computing means for computing a master signature set for a new master form, by computing a pixel count value in each cell of an array of cells located in a portion of the master form; scanning means for scanning a completed form into the system, and compressing and buffering it as a compressed image; decompressing means for decompressing only said portion of said compressed image of said completed form; said computing means computing a form signature set for said decompressed portion of said completed form by computing a pixel count value in each cell of an array of cells located in said portion of said completed form; comparing means for comparing said form signature set with said the master signature set, and computing a difference matrix; said comparing means repeating said comparing said form signature set for each master signature set in the system, until a best match is found between said completed form and one master form; monitoring means coupled to a character recognition means, for monitoring error statistics reported by said character recognition means using an ID of said best match one master form; said monitoring means identifying particular master form ID causing more than a predetermined threshold quantity of said error statistics, as having high error statistics; learning means for starting a learning mode by storing a plurality of form signature sets for completed forms processed having said ID of said master form causing said high error statistics; accumulating means for accumulating a predetermined quantity of forms signature sets having said ID; second computing means for analyzing said form signature sets by computing a standard deviation for a given cell location over all of said accumulated forms having said ID; said second computing means identifying a given cell location having a relatively large standard deviation in its pixel count, as having variable markings in said completed forms; said second computing means reducing the effect of said given cell in said matching process.
10. The system of claim 9, which further comprises: said second computing means reducing the sensitivity of the matching process to a cell, by modifying a weighting set associated with said master form's master signature; said weighting set being an array of multiplicative values, one for each cell.
11. The system of claim 10, which further comprises: said second computing means initially assigning all of the values in the weighting set to have the value of unity; said second computing means during said comparing step, multiplying each value in the difference matrix by the weight for that cell in the weighting set.
12. The system of claim 11, which further comprises: said second computing means reducing the sensitivity of the matching process for a particular cell, by reducing the value of the weight for that cell; whereby the system learns which of the cells are variable for a given master form, and those cells are made less important to the matching process for finding the ID of a completed form.
Patent Citations (14)
| Patent | Date | Inventor | Cited By |
|---|---|---|---|
| US4021777 | 1977-05-01 | Shepard | |
| US4410965 | 1983-10-01 | Moore | |
| US4503556 | 1985-03-01 | Scherl et al. | |
| US4533959 | 1985-08-01 | Sakurai | |
| US4741045 | 1988-04-01 | Denning | |
| US4748678 | 1988-05-01 | Takeda et al. | |
| US4933984 | 1990-06-01 | Nakano et al. | |
| US4949392 | 1990-08-01 | Barski et al. | |
| US5048112 | 1991-09-01 | Alves et al. | |
| US5123061 | 1992-06-01 | Pritchard | |
| US5140650 | 1992-08-01 | Casey et al. | |
| US5199081 | 1993-03-01 | Saito et al. | |
| US5317646 | 1994-05-01 | Sang, Jr. et al. | |
| US5428694 | 1995-06-01 | Betts et al. |
Non-Patent Literature (1)
- IBM Technical Disclosure Bulletin, H. Aghili, et al., "Converting Paper Document to Electronic Images With Automatic Document . . .", vol. 34, Mar. 1992; pp. 435-439.