System and method for automatic page registration and automatic zone detection during forms processing
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
21 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
-
-
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°
; andg) 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.
-
Specification