Image processing system with image cropping and skew correction

• US 5,901,253 A
• Filed: 04/04/1996
• Issued: 05/04/1999
• Est. Priority Date: 04/04/1996
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.), Ericsson, Inc. (Telefonaktiebolaget LM Ericsson)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Tretter, Daniel R.
• Primary Examiner(s): Shalwala, Bipin
• Assistant Examiner(s): Mariam, Daniel G.
• Application Number:
  US08/628,044
• Time in Patent Office: 1,125 Days
• Field of Search: 382/289, 382/290, 382/291, 382/292, 382/294, 382/296, 358/452, 358/455, 358/537
• US Class Current: 382/289
• CPC Class Codes: G06T 3/606 by memory addressing or mapping

Abstract

An arrangement is described for determining the skew angle of a document image without requiring text or other skew detection information in the document or without human intervention. The arrangement accomplishes this by determining an edge of the document image within a scan image and uses that edge to determine the skew angle of the document image. The edge can be determined by locating the first or last document image pixel of each scan line of pixels in the scan image that belongs to the document image. This is accomplished by comparing each pixel of each scan line of pixels with a predetermined scan line of background pixels. The skew angle of the document image is then determined by computing the slope of the detected edge in the scan image. An arrangement of determining the boundary of the document image is also described. The arrangement does this by locating (1) a first document image pixel and a last document image pixel for the first scan line of the document image in the scan image, (2) a first document image pixel and a last document image pixel for the last scan line of the document image in the scan image, (3) a leftmost document image pixel of the document image in the scan image, and (4) a rightmost document image pixel of the document image in the scan image.

Claims

1. A method of determining a skew angle of a document image inside a scan image having a plurality of scan lines of pixels, comprising the steps of:

(A) receiving a scan line of pixels of the scan image;

(B) automatically detecting an edge segment of the document image by

detecting a first/last document image pixel of the scan line of pixels that belongs to the document image without dividing the scan line into a number of multiple-pixel blocks and without any user intervention and input;

(C) if the first/last document image pixel of the scan line continues the edge segment having the first/last document image pixel of previous scan lines of the scan image, then automatically extending the edge segment to the first/last document image pixel of the scan line;

(D) repeating the steps of (A) and (B) until the edge segment cannot be further extended without any user intervention and without requiring that the document image contains text, wherein the edge segment forms an edge of the document image;

(E) determining if the edge segment is longer than a predetermined length value;

(F) determining the skew angle by determining a slope of the edge segment if the edge segment is longer than the predetermined length value.

2. The method of claim 1, wherein the scan image includes document image pixels of the document image and background pixels of the scan image, wherein the step (B) further comprises the steps of:

(I) receiving a corresponding scan line of predetermined background pixels;

(II) comparing the scan line of pixels of the scan image with the corresponding scan line of predetermined background pixels to locate the first/last document image pixel of the scan line of pixels that belongs to the document image.

3. The method of claim 2, wherein the step (II) further comprises the steps of:

(i) comparing color of the first/last document image pixel with color of its corresponding background pixel;

(ii) comparing color of an adjacent pixel of the first/last document image pixel with color of its corresponding background pixel;

(iii) determining that the first/last document image pixel is indeed the first/last document image pixel of the document image along the scan line if the color of the first/last document image pixel is different from that of its corresponding background pixel and the color of the adjacent pixel is different from that of its corresponding background pixel.

4. The method of claim 3, wherein the color of each of the background pixels is approximately one-fourth red, one-half green, and one-eighth blue.

5. The method of claim 1, wherein the step (C) further comprises the steps of:

(I) if the first/last document image pixel of the scan line does not continue the edge segment, then ending the edge segment and generating a new edge segment that extends to the first/last document image pixel of the scan line;

(II) repeating the steps (A) and (B).

6. The method of claim 5, wherein the step (F) further comprises the steps of:

(a) determining if the document image has a rectangular shape by determining (1) if the edge segment is perpendicular or parallel to previous edge segments and (2) if the edge segment is longer than the predetermined length value;

(b) setting the skew angle to zero if the document image does not have the rectangular shape.

7. The method of claim 6, wherein the predetermined length value is approximately equal to twenty five pixels.

8. The method of claim 1, further comprising the step of determining boundary the document by

(A) checking each of the scan lines against a predetermined scan line of background pixels to locate

(1) a first document image pixel and a last document image pixel for a first scan line of the scan lines,

(2) a first document image pixel and a last document image pixel of a last scan line of the scan lines,

(3) a leftmost document image pixel of the document image, and

(4) a rightmost document image pixel of the document image;

(B) connecting the first and last document image pixels of the first and last scan lines, the leftmost document image pixel, and the rightmost document image pixel together to define the boundary of the document image.

9. The method of claim 8, further comprising the step of determining if the document image has multiple skew angles.

10. The method of claim 9, further comprising the step of extending (1) a first horizontal line through the first and last document image pixels of the first scan line, (2) a second horizontal line through the first and last document image pixels of the last scan line, (3) a first vertical line through the leftmost document image pixel, and (4) a second vertical line through the rightmost document image pixel to define the boundary of the document image if the document image has multiple skew angles.

11. An apparatus, comprising:

(A) a storage medium;

(B) a computer executable program stored on the storage medium, the computer executable program, when executed, determining a skew angle of a document image inside a scan image having a plurality of scan lines of pixels, wherein the computer executable program comprises

(I) a first set of instructions that receive and examine a scan line of pixels of the scan image;

(II) a second set of instructions that detect an edge segment of the document image by

detecting a first/last document image pixel of the scan line of pixels that belongs to the document image without dividing the scan line into a number of multiple-pixel blocks and without any user intervention and input;

and extending the edge segment having the first/last document image pixel of previous scan lines of the scan image to the first/last document image pixel of the scan line;

wherein the first and second sets of instructions are repeatedly executed until the edge segment cannot be further extended without any user intervention and without requiring that the document image contains text if the first/last document image pixel of the scan line continues the edge segment;

(III) a third set of instructions that determine if the edge segment is longer than a predetermined length value;

(IV) a fourth set of instructions that determine the skew angle by determining a slope of the edge segment if the edge segment is longer than the predetermined length value.

12. The apparatus of claim 11, wherein the scan image includes image pixels of the document image and background pixels of the scan image, wherein the second set of instructions further comprises

(a) a first subset of the second set of instructions that receive a corresponding scan line of predetermined background pixels;

(b) a second subset of the second set of instructions that compare color of the first/last document image pixel with color of its corresponding background pixel;

(c) a third subset of the second set of instructions that compare color of an adjacent pixel of the first/last document image pixel with color of its corresponding background pixel;

(d) a fourth subset of the second set of instructions that decide that the first/last document image pixel is indeed the first/last document image pixel of the document image along the scan line if the color of the first/last document image pixel is different from that of its corresponding background pixel and the color of the adjacent pixel is different from that of its corresponding background pixel.

13. The apparatus of claim 12, wherein the color of each of the background pixels is approximately one-half green, one-fourth red, and one-eighth blue.

14. The apparatus of claim 13, wherein the second set of instructions further comprise a fifth subset of instructions that end the edge segment and generate a new edge segment that extends to the first/last document image pixel of the scan line if the first/last document image pixel of the scan line does not continue the edge segment.

15. The apparatus of claim 14, further comprising

(a) a first subset of the fourth set of instructions that determine if the document image has a rectangular shape by determining (1) if the edge segment is perpendicular or parallel to previous edge segments and (2) if the edge segment is longer than a predetermined length value;

(b) a second subset of the fourth set of instructions that set the skew angle to zero if the document image is not substantially in the rectangular shape.

16. The apparatus of claim 15, wherein the predetermined length value is approximately equal to twenty five pixels.

17. The apparatus of claim 11, further comprises a fifth set of instructions that determine boundary of the document image by

(I) checking each of the scan lines against a predetermined scan line of background pixels to locate

(1) a first document image pixel and a last document image pixel for a first scan line of the scan lines,

(2) a first document image pixel and a last document image pixel for a last scan line of the scan lines,

(3) a leftmost document image pixel of the document image, and

(4) a rightmost document image pixel of the document image;

(II) connecting the first and last document image pixels of the first and last scan lines, the leftmost document image pixel, and the rightmost document image pixel together to define the boundary of the document image.

18. The apparatus of claim 17, further comprising a sixth set of instructions that determine if the document image has multiple skew angles.

19. The apparatus of claim 18, further comprising a seventh set of instructions that extend (1) a first horizontal line through the first and last document image pixels of the first scan line, (2) a second horizontal line through the first and last document image pixels of the last scan line, (3) a first vertical line through the leftmost document image pixel, and (4) a second vertical line through the rightmost document image pixel to define the boundary of the document image if the document image has multiple skew angles.