Method and apparatus for recognizing a digitized form, extracting information from a filled-in form, and generating a corrected filled-in form

• US 7,487,438 B1
• Filed: 03/08/2005
• Issued: 02/03/2009
• Est. Priority Date: 03/08/2005
• Status: Active Grant

• Current Assignee: Accusoft Corporation
• Original Assignee: Pegasus Imaging Corporation (Accusoft Corporation)
• Inventors: Withers, William Douglas
• Primary Examiner(s): Le; Brian Q
• Assistant Examiner(s): ENTEZARI, MICHELLE M
• Application Number:
  US11/075,115
• Time in Patent Office: 1,428 Days
• Field of Search: 382/294, 715221-225
• US Class Current: 715/223
• CPC Class Codes: G06V 30/412 Layout analysis of documents structured with printed lines or input boxes, e.g. business forms or tables

Abstract

Methods and apparatus for comparing blank forms represented in a digital format to digitized filled-in forms are described. Different errors are attributed different weights when attempting to correlate regions of blank and filled-in forms. Foreground pixels in the blank form which are not found in a corresponding portion of a filled-in form are attributed greater error significance than foreground pixels, e.g., pixels which may correspond to added text, found in the filled-in form which correspond to a background pixel value in the blank form. A virtual filled-in form including content, e.g., pixel values, from the filled-in form is generated from the content of the filled-in form and pixel value location mapping information determined from comparing the blank and filled-in forms. Various analysis is performed on a block basis, but in some embodiments the final pixel mapping to the virtual form is performed on a pixel by pixel rather than a block basis.

Claims

1. A method of processing a filled-in form and a blank form to generate a virtual filled-in form, the filled-in form including a first plurality of pixel values, each of the first plurality of pixel values corresponding to one location in a first array of row and column pixel locations, the blank form including a second plurality of pixel values, each of the second plurality of pixel values corresponding to one location in a second array of row and column pixel locations, the method comprising:

processing the filled-in form to identify column borders defining a region in which a first predetermined majority of foreground pixel values are located;

processing the filled-in form to identify row borders defining a region in which a second predetermined majority of foreground pixel values are located, wherein the identified column and row borders define a rectangular filled-in main image region;

determining a main image aspect ratio as a function of the determined row and column borders;

comparing the determined main image aspect ratio of the filled-in form to a main aspect ratio of said blank form to determine if the determined main image aspect ratio is within a predetermined difference threshold of the main aspect ration of said blank form; and

if it is determined that the aspect ratios are within the predetermined difference threshold, determining a scaling factor which can be used on one of the blank and filled-in forms to resize the main image area of one of the blank and filled-in forms so that the size of the main image area of the blank form and main image area of the filled-in form will match.

2. The method of claim 1, further comprising:

if it is determined that the main image aspect ratio of the filled-in form is outside the predetermined difference when compared to said blank form main image aspect ratio rejecting said blank form as a possible match to the filled-in form.

3. The method of claim 1, wherein the step of processing the filled-in form to identify column borders defining a region in which a first predetermined majority of foreground pixel values are located includes:

generating at least one one-dimensional histogram based on the distribution of foreground pixels in said filled-in form.

4. The method of claim 1, further comprising:

calculating a global offset indicating a displacement between the main image area of said blank form and the main image area of said filled-in form, said global offset indicating a displacement in terms of row and column offsets which, when applied to one of the images, can be used to make the two main image areas correspond to the same row and column locations after one of the images has been scaled so that the two main image areas are the same size.

5. The method of claim 4, wherein said blank form pixel values are grouped into rectangular blocks, the method further comprising:

for each block of the blank form, generating a block position offset indicating a block position offset which tends to minimize a total block error corresponding to the individual block, the block error being indicative of a location error that exists between the position of the block in the blank form and a set of pixel values in the filled-in form determined to correspond to said particular block based on at least a similarity of pixel values in said block and said set of pixel values in the filled-in form.

6. The method of claim 5, wherein the total block error for each individual block is determined as a function of i) a block offset determined for the particular individual block, said block offset being in addition to said global offset and indicating a position shift to be used to map between the position of said block in the blank form and the position of the corresponding set of pixel values in the filled-in form, and ii) when a previously determined block offset for an adjacent block is available, the variance between the block offset of the particular block and the previously determined block offset of the adjacent block.

7. The method of claim 5, further comprising:

generating a virtual form from the filled-in form by mapping pixel values of the filled-in form to locations within the virtual form by applying position offsets determined from at least said global offset and the individual block offset for a block to which the pixel values in the filled-in form was determined to correspond.

8. The method of claim 7, wherein said generating of the virtual form includes setting a pixel value in said virtual filled-in form corresponding to a particular location to a foreground pixel value when a foreground pixel value in said filled-in form and a background pixel value in the blank form map to said particular location.

9. The method of claim 8, wherein said combining operation produces a foreground pixel values in said filled-in form only in locations to which a foreground pixel value is mapped from said filled-in form and a background pixel value is mapped from said blank form, the method further comprising:

storing the pixel values of said virtual form in a storage device along with information indicating the blank form to which said virtual form corresponds; and

generating a complete virtual filled-in form by combining pixel values from said blank form and pixel values from said virtual filled-in form, said complete virtual filled-in form including a foreground pixel value in any pixel value location in which either said blank form or said virtual filled-in form include a foreground pixel value.

10. The method of claim 5, wherein the total error of a block is determined as a function of a plurality of different types of errors, said plurality of different types of errors including a first type error which is based on the distance between the location in said blank form of at least one foreground pixel value and the proximity of a foreground pixel value, if present, in the corresponding set of pixel values in the filled-in form.

11. The method of claim 10, wherein the total block error is also a function of a second type error, the second type error being determined to occur when a foreground pixel in the filled-in form is determined to correspond to a location in the blank form which includes a background pixel.

12. The method of claim 11, wherein the first type error is weighted more heavily than the second type error when computing the total block error, the total block error being incremented more when a first type error is detected than when a second type error is detected.

13. The method of claim 10, further comprising:

sequentially determining total block error for multiple blocks in said blank form;

maintaining a cumulative first type error count indicative of the number of first type errors which are detected; and

determining a form mismatch between the blank form and the filled-in form if the cumulative error count exceeds an error threshold.

14. The method of claim 10, further comprising:

sequentially determining total block error for multiple blocks in said blank form;

maintaining a cumulative total block error count; and

determining a form mismatch between the blank form and the filled-in form if the cumulative total block error count exceeds an error threshold.

15. The method of claim 1, wherein said method is implemented by a general purpose processor operating under control of a set of program instructions, said program instructions being stored on a machine readable medium.

16. A system for processing a filled-in form and a blank form to generate a virtual filled-in form, the filled-in form including a first plurality of pixel values, each of the first plurality of pixel values corresponding to one location in a first array of row and column pixel locations, the blank form including a second plurality of pixel values, each of the second plurality of pixel values corresponding to one location in a second array of row and column pixel locations, the system comprising:

means for processing the filled-in form to identify column borders defining a region in which a first predetermined majority of foreground pixel values are located;

means for processing the filled-in form to identify row borders defining a region in which a second predetermined majority of foreground pixel values are located, wherein the identified column and row borders define a rectangular filled-in main image region;

means for determining a main image aspect ratio as a function of the determined row and column borders;

means for comparing the determined main image aspect ratio of the filled-in form to a main aspect ratio of said blank form to determine if the determined main image aspect ratio is within a predetermined difference threshold of the main aspect ration of said blank form; and

means for determining a scaling factor which can be used on one of the blank and filled-in forms to resize the main image area of one of the blank and filled-in forms so that the size of the main image area of the blank form and main image area of the filled-in form will match if it is determined that the aspect ratios are within the predetermined difference threshold.

17. The system of claim 16, further comprising:

means for rejecting said blank form as a possible match to the filled-in form if it is determined that the main image aspect ratio of the filled-in form is outside the predetermined difference when compared to said blank form main image aspect ratio.

18. A method of determining if a blank form matches a filled-in form, the blank and filled-in form having a plurality of corresponding regions, the method comprising:

comparing corresponding regions of the blank form and filled-in form to detect a plurality of different types of errors including;

first type errors in which one or more foreground pixel values in the blank form which are not present within a predetermined distance of one or more foreground pixel values in a corresponding region of a filled-in form;

second type errors in which one or more foreground pixel values in the filled-in form are not present within a predetermined distance of a foreground pixel value in a corresponding region of the blank form; and

generating a form mismatch estimate value indicative of the mismatch between the blank form and the filled-in form as a function of detected first type errors and second type errors.

19. The method of claim 18, wherein said step of generating an estimate of the mismatch between the blank form and the filled-in form includes:

weighting first type errors more heavily than second type errors thereby resulting in each first type error contributing more heavily to the total mismatch error estimate value than each detected second type error.

20. The method of claim 19, further comprising:

generating a signal indicating a mismatch between the blank form and filled-in form when the generated mismatch error estimate value exceeds a maximum total error threshold value.

21. The method of claim 20, wherein said form mismatch estimate value is generated by sequentially processing corresponding regions of said blank form and said filled-in form.

22. A method of processing a filled-in form and a blank form to generate a virtual filled-in form, the filled-in form including a first plurality of pixel values, each of the first plurality of pixel values corresponding to one location in a first array of row and column pixel locations, the blank form including a second plurality of pixel values, each of the second plurality of pixel values corresponding to one location in a second array of row and column pixel locations, wherein said blank form pixel values are grouped into rectangular blocks, each of the blank form and filled-in forms including main image areas in which a majority of the foreground pixels in the form are located, the method comprising:

calculating a global offset indicating a displacement between the main image area of said blank form and the main image area of said filled-in form, said global offset indicating a displacement in terms of row and column offsets which, when applied to one of the images, can be used to make the two main image areas correspond to the same row and column locations after one of the images has been scaled so that the two main image areas are the same size; and

for each block of the blank form, generating a block position offset indicating a block position offset which tends to minimize a total block error corresponding to the individual block, the block error being indicative of a location error that exists between the position of the block in the blank form and a set of pixel values in the filled-in form determined to correspond to said particular block based on at least a similarity of pixel values in said block and said set of pixel values in the filled-in form.

23. The method of claim 22, wherein the total block error for each individual block is determined as a function of i) a block offset determined for the particular individual block, said block offset being in addition to said global offset and indicating a position shift to be used to map between the position of said block in the blank form and the position of the corresponding set of pixel values in the filled-in form, and ii) when a previously determined block offset for an adjacent block is available, the variance between the block offset of the particular block and the previously determined block offset of the adjacent block.

24. The method of claim 22, further comprising:

generating a virtual form from the filled-in form by mapping pixel values of the filled-in form to locations within the virtual form by applying position offsets determined from at least said global offset and the individual block offset for a block to which the pixel values in the filled-in form was determined to correspond.

25. A machine readable medium comprising machine executable instructions which, when executed cause a machine to perform processing of a filled-in form and a blank form to generate a virtual filled-in form, the filled-in form including a first plurality of pixel values, each of the first plurality of pixel values corresponding to one location in a first array of row and column pixel locations, the blank form including a second plurality of pixel values, each of the second plurality of pixel values corresponding to one location in a second array of row and column pixel locations, the processing including the steps of:

processing the filled-in form to identify column borders defining a region in which a first predetermined majority of foreground pixel values are located;

processing the filled-in form to identify row borders defining a region in which a second predetermined majority of foreground pixel values are located, wherein the identified column and row borders define a rectangular filled-in main image region;

determining a main image aspect ratio as a function of the determined row and column borders;

comparing the determined main image aspect ratio of the filled-in form to a main aspect ratio of said blank form to determine if the determined main image aspect ratio is within a predetermined difference threshold of the main aspect ration of said blank form; and

if it is determined that the aspect ratios are within the predetermined difference threshold, determining a scaling factor which can be used on one of the blank and filled-in forms to resize the main image area of one of the blank and filled-in forms so that the size of the main image area of the blank form and main image area of the filled-in form will match.