US5901253A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Image processing system with image cropping and skew correction
Assignee: Ericsson Inc
•
Filing: 1996-04-04
•
Granted: 1999-05-04
•
Expires: 2016-04-04
Abstract
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.
Inventors
- 👤 Daniel R. Tretter
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 11:47
CPC Classifications
G; G06; G06T; G06T3/00; G06T3/60; G06T3/606
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
207 words
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.
Claim 2
Independent Claim
207 words
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.
Claim 3
Dependent Claim
82 words
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.
Claim 4
Dependent Claim
107 words
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.
Claim 5
Dependent Claim
23 words
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.
Claim 6
Dependent Claim
61 words
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).
Claim 7
Dependent Claim
69 words
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.
Claim 8
Dependent Claim
17 words
The method of claim 6, wherein the predetermined length value is approximately equal to twenty five pixels.
Claim 9
Dependent Claim
131 words
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.
Claim 10
Dependent Claim
19 words
The method of claim 8, further comprising the step of determining if the document image has multiple skew angles.
Claim 11
Dependent Claim
86 words
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.
Claim 12
Independent Claim
244 words
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.
Claim 13
Independent Claim
244 words
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.
Claim 14
Dependent Claim
174 words
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.
Claim 15
Dependent Claim
23 words
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.
Claim 16
Dependent Claim
57 words
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.
Claim 17
Dependent Claim
83 words
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.
Claim 18
Dependent Claim
17 words
The apparatus of claim 15, wherein the predetermined length value is approximately equal to twenty five pixels.
Claim 19
Dependent Claim
136 words
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.
Claim 20
Dependent Claim
22 words
The apparatus of claim 17, further comprising a sixth set of instructions that determine if the document image has multiple skew angles.
Claim 21
Dependent Claim
89 words
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.
References Cited (Backward Citations)
US4432009A
Cited
US4533959A
Cited
US4953230A
Cited
US4802229A
Cited
US4723297A
Cited
US4823395A
Cited
US4930088A
Cited
US4941189A
Cited
US4876730A
Cited
US5093653A
Cited
US5181260A
Cited
US5189711A
Cited
US5187753A
Cited
US5355420A
Cited
EP0434415A2
Cited
US5241626A
Cited
EP0469794A2
Cited
US5233168A
Cited
US5289297A
Cited
US5452374A
Cited
EP0703696A2
Cited
US5517587A
Cited
US5528387A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-05-03 | 2002-11-02 | 2003-05-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-05-03 | 2006-11-02 | 2007-05-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-05-03 | 2010-11-02 | 2011-05-04 | $7700.00 | Window Closed / Lapsed |