System and method for automatic page registration and automatic zone detection during forms processing

• US 5,822,454 A
• Filed: 04/10/1995
• Issued: 10/13/1998
• Est. Priority Date: 04/10/1995
• Status: Expired due to Fees

• Current Assignee: Rebus Technology Incorporated
• Original Assignee: Rebus Technology Incorporated
• Inventors: Rangarajan, Vijayakumar
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): MEHTA, BHAVESH M
• Application Number:
  US08/419,135
• Time in Patent Office: 1,282 Days
• Field of Search: 382/180, 382/173, 382/174, 382/176, 382/240, 382/224, 382/197, 382/206, 382/306, 382/305, 382/289, 358/453, 358/462, 395/761, 395/770
• US Class Current: 382/180
• CPC Class Codes: G06T 3/608 by skew deformation, e.g. two-pass or three-pass rotation
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1444 Selective acquisition, locating or processing of specific regions, e.g. highlighted text, fiducial marks or predetermined fields

Abstract

A system and method automatically detects user defined zones in a document image of a form, compensating for skew and displacement of the image with respect to a original image of form. The system provides a mechanism to input an image for a form document, such as a scanner. The system processes the image to reduce its resolution and to remove significant skew. The image is presented to the user to define the zones. These zones are areas from which the user desires to extract meaningful data through optical character recognition, such as names, dates, addresses, and items on a invoice form. The system further processes the image to remove horizontal and vertical lines, and to create a number of blocks, representing either text or image data. The lines are removed and the blocks formed by runlength smoothing with various parameters. The blocks form clusters of connected pixels. The blocks are labeled such that any set of connected blocks share a unique identification value. Additional data is collected on the commonly labeled blocks to select those blocks useful to definition of a template. The template is a collection of vectors between the centroids of each of the selected blocks. A second document image for processing is obtained, and similarly processed to minimize, deskew, and identify blocks and vectors therein. The vectors in the second document image are compared with vectors in an user selected template to determine the location of user defined zones in the second document image.

Claims

1. A method for automatically extracting information from a plurality of user defined zones in a second image corresponding to a plurality of user defined zones in a first image and compensating for skew and displacement in the second image with respect to the first image, comprising the steps of:

receiving a user input defining at least one user defined zone in relationship to the first image, each user defined zone for extracting information from a portion of a second image corresponding to the user defined zone in the first image;

smoothing the first image to produce blocks of connected pixels;

identifying in the first image a first plurality of blocks from the blocks of connected pixels;

defining at least one first set of vectors among selected ones of the first plurality of blocks, wherein a first vector between any two of the first plurality of blocks describes a skew and displacement invariant relationship between the two blocks;

identifying in the second image a second plurality of blocks of connected pixels;

defining at least one second set of vectors among selected ones of the second plurality of blocks wherein a second vector between any two of the second plurality of blocks describes a skew and displacement invariant relationship between the two blocks;

comparing the at least one first set of vectors to the at least one second set of vectors to determine a percentage of the first set of vectors that are similar to the second set of vectors; and

,

responsive to the percentage being greater than a predetermined threshold, extracting information only from portions of the second image that correspond to each of the user defined zones of the first image.

2. The method of claim 1 further comprising, before smoothing the image, the steps of:

determining a skew angle and orientation in the first image;

deskewing the first image according to the skew angle and orientation;

removing horizontal lines from the first image; and

removing vertical lines from the first image.

3. The method of claim 2, further comprising the steps of:

distinctly identifying each of the first plurality of blocks; and

determining for each block a data classification.

4. The method of claim 3, wherein each block is classified as one of a group comprising:

a text block; and

an image block;

as a function of block height and block width.

5. The method of claim 2, wherein the step of determining a skew angle and orientation in the first image further comprises the steps of:

smoothing pixel data in the first image into a plurality of blocks;

identifying blocks forming connected sets of pixels, each block having a height and a width;

qualifying as valid blocks those blocks having a height and a width within predetermined ranges;

for each valid block, determining a block skew angle and orientation;

determining an orientation of a majority of the valid blocks; and

averaging the block skew angles of the valid blocks.

6. The method of claim 2, wherein the step of removing horizontal lines from the first image further comprises the steps of:

runlength smoothing the first image using a runlength parameter selected to convert broken horizontal line segments into continuous horizontal line segments;

identifying horizontal line segments having less than a maximum height; and

removing the identified horizontal line segments by converting set pixels in the horizontal line segments to unset pixels.

7. The method of claim 2, wherein the step of removing vertical lines from the first image further comprises the steps of:

normalizing the first image by adding temporary horizontal lines at the top and bottom of the image;

rotating the first image 90°

;

runlength smoothing the first image using a runlength parameter selected to convert broken vertical line segments into continuous vertical line segments;

identifying vertical line segments having less than a maximum height;

removing the identified vertical line segments by converting set pixels in the vertical line segments to unset pixels;

rotating the first image back 90°

; and

denormalizing the first image by removing the temporary horizontal lines.

8. The method of claim 2, wherein determining a skew angle and orientation in the first image comprises:

a) selecting the orientation held by a majority of the first plurality of blocks; and

b) determining the average skew of the first plurality of blocks.

9. The method of claim 1, wherein the step of defining at least one first set of vectors, further comprises the step of:

determining, for each selected block, a vector between a centroid of the selected block and a centroid in each other selected block.

10. The method of claim 9 further comprising the step of:

determining between a centroid of each user defined zone in the first image a vector to a centroid in each selected block in the first image.

11. The method of claim 1, wherein identifying in the first image a first plurality of blocks comprises:

selecting as the first plurality of blocks those blocks of connected pixels having a height within a predetermined height range and a width within a predetermined width range.

12. The method of claim 1, wherein defining at least one first set of vectors among selected ones of the first plurality of blocks comprises:

segmenting the image into a plurality of segments of substantially equal area;

determining for each segment, an average area for the blocks in the segment;

selecting in each segment those blocks having an area approximately equal to the average area for the blocks in the segment; and

defining at least one first set of vectors among the selected blocks.

13. The method of claim 1, wherein for each of the selected ones of the first plurality of blocks, there is a vector list V_i :

space="preserve" listing-type="equation">V.sub.i = v.sub.(i,j), v.sub.(i,j+1), v.sub.(i,n) !

where V_i is the vector list for a selected block i;

v.sub.(i,j) is a vector from the selected block B_i to another selected block B_j ; and

,

n is the number of selected blocks.

14. The method of claim 1, wherein a first vector in the first set is substantially similar to a second vector in the second set if the first vector is within a predetermined range of dimensional tolerance to the second vector, determined as a function of a resolution of the first image.

15. The method of claim 1, wherein extracting information only from portions of the second image that correspond to each of the user defined zones of the first image comprises:

locating the user defined zones on the second image according to positions of the selected ones of the second plurality of blocks in the second image and positions of the selected ones of the first plurality of blocks in the first image; and

extracting text or image data from each located user defined zone on the second image.

16. The method of claim 15, wherein locating the user define zones comprises:

a) determining an offset between the selected ones of the first plurality of blocks in the first image and the selected ones of the second plurality of blocks in the second image;

b) adding the offset to the user defined zones in the first image to determine a location for the user defined zones in the second image.

17. A computer readable memory for configuring and controlling a processor to perform the method of claim 1.

18. The method of claim 1, wherein defining at least one second set of vectors among selected ones of the second plurality of blocks comprises:

segmenting the image into a plurality of segments of substantially equal area;

determining for each segment, an average area for the blocks in the segment;

selecting in each segment those blocks having an area approximately equal to the average area for the blocks in the segment; and

defining at least one second set of vectors among the selected blocks.

19. A method for automatically identifying a plurality of user defined zones in a second image corresponding to a plurality of user defined zones in a first image and compensating for skew and displacement in the second image with respect to the first image, comprising the steps of:

identifying in the first image a first plurality of blocks of connected pixels;

defining at least one first set of vectors among selected ones of the first plurality of blocks, wherein a first vector between any two of the first plurality of blocks describes a skew and displacement invariant relationship between the two blocks;

identifying in the second image a second plurality of blocks of connected pixels, by;

i) determining a skew angle and orientation in the first image;

ii) deskewing the first image according to the skew angle and orientation;

iii) removing horizontal lines from the first image;

iv) removing vertical lines from the first image by;

a) normalizing the first image by adding temporary horizontal lines at the top and bottom of the image;

b) rotating the first image 90°

;

c) runlength smoothing the first image using a runlength parameter selected to convert broken vertical line segments into continuous vertical line segments;

d) identifying vertical line segments having less than a maximum height;

e) removing the identified vertical line segments by converting set pixels in the vertical line segments to unset pixels;

f) rotating the first image back 90°

; and

g) denormalizing the first image by removing the temporary horizontal lines;

v) smoothing the first image to produce the first plurality of blocks of connected pixels;

defining at least one second set of vectors among selected ones of the second plurality of blocks wherein a second vector between any two of the second plurality of blocks describes a skew and displacement invariant relationship between the two blocks;

comparing the at least one first set of vectors to the at least one second set of vectors to establish a degree of similarity therebetween; and

,

responsive to the at least one first set of vectors being similar to the at least one second set of vectors, applying the user defined zones of the first image to the second image.

20. A method for automatically identifying a plurality of user defined zones in a second image corresponding to a plurality of user defined zones in a first image and compensating for skew and displacement in the second image with respect to the first image, comprising the steps of:

identifying in the first image a first plurality of blocks of connected pixels;

defining at least one first set of vectors among selected ones of the first plurality of blocks, wherein a first vector between any two of the first plurality of blocks describes a skew and displacement invariant relationship between the two blocks;

identifying in the second image a second plurality of blocks of connected pixels by;

segmenting the image into a plurality of segments of substantially equal area;

determining for each segment, an average area for the blocks in the segment;

selecting in each segment those blocks having an area approximately equal to the average area for the blocks in the segment; and

defining at least one first set of vectors among the selected blocks;

defining at least one second set of vectors among selected ones of the second plurality of blocks wherein a second vector between any two of the second plurality of blocks describes a skew and displacement invariant relationship between the two blocks;

comparing the at least one first set of vectors to the at least one second set of vectors to establish a degree of similarity therebetween; and

,

responsive to the at least one first set of vectors being similar to the at least one second set of vectors, applying the user defined zones of the first image to the second image.

21. A computer implemented method for automatically identifying a second image as matching first image and compensating for skew and displacement in the second image with respect to the first image, comprising the steps of:

smoothing the first image to produce blocks of connected pixels;

identifying in the first image a first plurality of blocks from the blocks of connected pixels;

defining a first set of vectors among selected ones of the first plurality of blocks, wherein a first vector between any two of the first plurality of blocks describes a skew and displacement invariant relationship between the two blocks;

smoothing the second image to produce smoothed blocks of connected pixels;

identifying in the second image a second plurality of blocks from the smoothed blocks of connected pixels in the second image;

defining a second set of vectors among selected ones of the second plurality of blocks wherein a second vector between any two of the second plurality of blocks describes a skew and displacement invariant relationship between the two blocks;

comparing the first set of vectors to the second set of vectors to determine a percentage of the first set of vectors that are similar to the second set of vectors; and

,

responsive to the percentage being greater than a predetermined threshold, identifying the second image as matching the first image.