Computer-implemented method for automatic extraction of data from printed forms

• US 5,140,650 A
• Filed: 02/02/1989
• Issued: 08/18/1992
• Est. Priority Date: 02/02/1989
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ferguson, David R., Casey, Richard G.
• Primary Examiner(s): Razavi, Michael
• Application Number:
  US07/305,828
• Time in Patent Office: 1,293 Days
• Field of Search: 382/61, 382/48, 382/40, 382/46, 382/33, 382/956, 382/57, 382/14, 382/22, 382/25, 382/30, 358/101, 358/102, 364/518, 364/514, 364/513
• US Class Current: 382/283
• CPC Class Codes: G06F 40/174 Form filling; Merging
• CPC Class Codes: G06V 30/412 Layout analysis of documents structured with printed lines or input boxes, e.g. business forms or tables

Abstract

A machine-implemented method for extracting character data from printed forms of the type having generally straight lines and data regions separated by lines utilizes a processor coupled to an image scanning device and a data storage device. The method includes the steps of scanning a blank form so as to create a digital image of a first array of pixels, identifying the pixels in the array which form generally straight lines of connected line pixels, creating data masks in the array at locations separated by the identified lines, the data masks corresponding to the data regions in the printed form, scanning a filled-in form so as to create a digital image of a second array of pixels, identifying pixels in the second array which form generally straight lines of connected pixels, calculating the offset of the lines in the second array from the lines in the first array, locating the data masks created in the first array into the second array by use of the calculated offset, and extracting data corresponding to character pixels from the data masks in the second array.

Claims

1. A machine-implemented method for extracting character data from printed forms of the type having generally straight lines and data regions separated by the lines, the method utilizing a processor coupled to an image scanning device and a storage means, the method comprising the steps of:

(a) scanning a blank form so as to create a digital image of a first array of pixels representing the blank form;

(b) identifying line pixels in the first array which form generally straight lines of connected pixels;

(c) creating data masks in the first array at locations separated by the line pixels, the data masks corresponding to data regions in the blank form;

(d) scanning a filled-in form so as to create a digital image of a second array of pixels representing the filled-in form;

(e) identifying line pixels in the second array which form generally straight lines of connected line pixels;

(f) using line pixels in the second array and line pixels in the first array, calculating an offset of lines in the second array from lines in the first array;

(g) applying the data masks created in the first array to the second array by use of the calculated offset;

(h) determining if any connected character pixels extend across the perimeter of a data mask;

(i) in response to said determination, enlarging the data mask until substantially all connected character pixels are located within the enlarged data mask; and

(j) extracting data corresponding to character pixels from the data masks in the second array.

2. The method according to claim 1 wherein the step of enlarging the data mask comprises enlarging the mask only in a region of the mask perimeter crossed by the connected character pixels.

3. The method according to claim 1 wherein the step of enlarging the data mask further comprises the steps of:

detecting if any connected character pixels extend across a line; and

selectively removing line pixels corresponding to the line which are not located in a portion of the line crossed by the connected character pixels.

4. The method according to claim 1 wherein the step of identifying pixels which form generally straight lines of connected pixels comprises the steps of:

selecting clusters of vertically-connected pixels, the clusters having a vertical height less than a predetermined number of pixels; and

connecting horizontally adjacent clusters.

5. The method according to claim 1 wherein the step of identifying pixels which form generally straight lines of connected pixels comprises the step of determining the rotational skew of the connected line pixels.

6. The method according to claim 1 wherein the method also utilizes a display coupled to the processor and wherein the step of creating data masks comprises the steps of:

displaying the identified lines on the display; and

storing in the data storage means the array locations of data masks selected by a user in response to the displayed lines.

7. The method according to claim 1 wherein the step of calculating an offset further comprises the steps of:

calculating the horizontal adjustment of the lines in the second array relative to the lines in the first array;

calculating the vertical adjustment of the lines in the second array relative to the lines in the first array; and

calculating the rotational skew of the lines in the second array.

8. The method according to claim 7 wherein the step of locating the data masks in the second array comprises rotating the data masks by the degree of calculated skew.

9. The method according to claim 7 wherein the step of locating the data masks in the second array comprises adjusting the vertical height of the data masks by the degree of calculated skew.