Patent US6310984B2 successfully refreshed from Google Patents.
US6310984B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Image processing system with image cropping and skew correction
Assignee: Hewlett Packard Development Co LP
•
Filing: 1998-04-09
•
Granted: 2001-10-30
•
Expires: 2018-04-09
Abstract
Abstract A system and method is described for automatically determining in a scanned document image the presence of unwanted extraneous information caused by an extraneous device and scanner background information. Once the presence of this information is determined, the system and method of the present invention can compute, for instance, skew and crop statistics. From this, the image can be automatically deskewed and cropped appropriately without the background and extraneous information. The system and method accomplishes this by first determining the presence of unwanted extraneous and background information and then appropriately processing the document image. The extraneous information is ignored during deskew and crop computations. Also, the scanner background and the extraneous information are prevented from being included in the final digital representation of the image.
Inventors
- 👤 Cindy Y. Sansom-Wai
- 👤 Irene H. Williams
- 👤 Daniel R. Tretter
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 10:15
CPC Classifications
H; H04; H04N; H04N1/00; H04N1/387; H04N1/3877; H04N1/3878; G; G06; G06V; G06V10/00; G06V10/20; G06V10/24; H04N1/38; H04N1/3872; H04N1/3873
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
145 words
A method using a digital processor for automatically determining a skew angle of a document image inside a scan image having a plurality of scan lines of pixels, comprising: (A) successively receiving the scan lines of pixels of the scan image by the digital processor; (B) automatically locating predefined background pixels in the scan image by the processor and comparing a neighborhood of pixels located around a group of scan lines with the background pixels to define left and right image boundaries for each group of scan lines; (C) digitally forming at least one edge segment by extending at least one image boundary between successive groups of scan lines during receipt of the scan lines; and (D) calculating a slope of all of the digitally formed edge segments that are longer than a predetermined length value to automatically determine the skew angle without manual guidance.
Claim 2
Independent Claim
145 words
A method using a digital processor for automatically determining a skew angle of a document image inside a scan image having a plurality of scan lines of pixels, comprising: (A) successively receiving the scan lines of pixels of the scan image by the digital processor; (B) automatically locating predefined background pixels in the scan image by the processor and comparing a neighborhood of pixels located around a group of scan lines with the background pixels to define left and right image boundaries for each group of scan lines; (C) digitally forming at least one edge segment by extending at least one image boundary between successive groups of scan lines during receipt of the scan lines; and (D) calculating a slope of all of the digitally formed edge segments that are longer than a predetermined length value to automatically determine the skew angle without manual guidance.
Claim 3
Dependent Claim
29 words
The method of claim 1 further comprising, after step (A) and before step (B), searching for known characteristics within the document image and ignoring the known characteristics if found.
Claim 4
Dependent Claim
73 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: (I) receiving a neighborhood of pixels located around a group of scan lines; and (II) comparing the group of scan lines of the scan image with corresponding background pixels to define left and right image boundaries for each group of scan lines.
Claim 5
Dependent Claim
89 words
The method of claim 3 , wherein step (II) further comprises: (i) comparing color of the group of scan lines with color of the corresponding background pixels; (ii) comparing color of adjacent pixels of the group of scan lines with color of the corresponding background pixels; and (iii) confirming the location of an image boundary when the color of the group of scan lines is different from that of the corresponding background pixels and the color of the adjacent pixels are different from that of the corresponding background pixels.
Claim 6
Dependent Claim
24 words
The method of claim 4 , wherein the color of each of the background pixels is approximately one-fourth red, one-half green, and one-eighth blue.
Claim 7
Dependent Claim
62 words
The method of claim 1 , wherein step (C) further comprises: (I) ending the edge segment and generating a new edge segment that extends from an end scan line of the group of scan lines if the group of scan lines do not continue the edge segment; and (II) repeating steps (A), (B) and (C) until all scan lines have been received.
Claim 8
Dependent Claim
60 words
The method of claim 1 , wherein step (C) further comprises: (I) ending the edge segment and generating a new edge segment that extends from an end scan line of the group of scan lines if the group of scan lines do not continue the edge segment; and (II) repeating steps (A), (B) and (C) a predetermined number of times.
Claim 9
Dependent Claim
66 words
The method of claim 1 , wherein step (C) further comprises: (I) ending the edge segment and generating a new edge segment that extends from an end scan line of the group of scan lines if the group of scan lines do not continue the edge segment; and (II) dynamically repeating steps (A), (B) and (C) until an appropriate number of edge segments has been located.
Claim 10
Dependent Claim
80 words
The method of claim 8 , wherein the step (D) further comprises: (a) determining if the document image has a rectangular shape by determining (1) if the edge segment is at least one of approximately perpendicular to previous edge segments and approximately parallel to previous edge segments and (2) if the edge segment is longer than the predetermined length value; and (b) setting the skew angle to a predetermined value if the document image does not have the rectangular shape.
Claim 11
Dependent Claim
24 words
The method of claim 9 , wherein the skew angle is set to zero if the document image does not have the rectangular shape.
Claim 12
Dependent Claim
18 words
The method of claim 9 , wherein the predetermined length value is approximately equal to twenty five pixels.
Claim 13
Independent Claim
180 words
An apparatus, comprising: (A) a storage medium; (B) a computer executable program stored on the storage medium, the computer executable program, when executed, automatically determines 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 receives the scan lines of pixels of the scan image; (II) a second set of instructions that automatically locates predefined background pixels in the scan image and compares a neighborhood of pixels located around a group of scan lines with the background pixels to define left and right image boundaries for each group of scan lines; (III) a third set of instructions that forms one or more edge segments by extending one or more image boundaries between continuous groups of scan lines during receipt of the scan lines; and (IV) a fourth set of instructions that calculates a slope of all of the formed edge segments that are longer than a predetermined length value to automatically determine the skew angle without manual guidance.
Claim 14
Independent Claim
180 words
An apparatus, comprising: (A) a storage medium; (B) a computer executable program stored on the storage medium, the computer executable program, when executed, automatically determines 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 receives the scan lines of pixels of the scan image; (II) a second set of instructions that automatically locates predefined background pixels in the scan image and compares a neighborhood of pixels located around a group of scan lines with the background pixels to define left and right image boundaries for each group of scan lines; (III) a third set of instructions that forms one or more edge segments by extending one or more image boundaries between continuous groups of scan lines during receipt of the scan lines; and (IV) a fourth set of instructions that calculates a slope of all of the formed edge segments that are longer than a predetermined length value to automatically determine the skew angle without manual guidance.
Claim 15
Dependent Claim
163 words
The apparatus of claim 12 , 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 receives a neighborhood of pixels located around a group of scan lines; (b) a second subset of the second set of instructions that compares color of the group of scan lines with color of the corresponding background pixels; (c) a third subset of the second set of instructions that compares color of adjacent pixels of the group of scan lines with color of the corresponding background pixels; and (d) a fourth subset of the second set of instructions that confirms the location of an image boundary when the color of the group of scan lines is different from that of the corresponding background pixels and the color of the adjacent pixels are different from that of the corresponding background pixels.
Claim 16
Dependent Claim
24 words
The apparatus of claim 13 , wherein the color of each of the background pixels is approximately one-half green, one-fourth red, and one-eighth blue.
Claim 17
Dependent Claim
53 words
The apparatus of claim 12 , further comprising a first subset of the third set of instructions that ends the edge segment and generates a new edge segment that extends from an end scan line of the group of scan lines if the group of scan lines do not continue the edge segment.
Claim 18
Dependent Claim
91 words
The apparatus of claim 14 , further comprising (a) a first subset of the fourth set of instructions that determines if the document image has a rectangular shape by determining (1) if the edge segment is at least one of approximately perpendicular and approximately parallel to previous edge segments and (2) it the edge segment is longer than a predetermined length value; and (b) a second subset of the fourth set of instructions that sets the skew angle to zero if the document image is not substantially in the rectangular shape.
Claim 19
Dependent Claim
29 words
The apparatus of claim 12 , further comprising a fifth set of instructions that searches for known characteristics within the document image and ignores the known characteristics if found.
Claim 20
Independent Claim
197 words
An apparatus, comprising: (A) a storage medium; (B) a computer executable program stored on the storage medium, the computer executable program, when executed, automatically determines a boundary of a document image inside a scan image of a plurality of received scan lines of pixels, wherein the computer executable program comprises, (I) a first set of instructions that automatically compares a neighborhood of pixels located around a group of scan lines of pixels of the scan image against predetermined 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) a second set of instructions that connects 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 during receipt of the scan lines to automatically define the boundary of the document image without manual guidance.
Claim 21
Independent Claim
197 words
An apparatus, comprising: (A) a storage medium; (B) a computer executable program stored on the storage medium, the computer executable program, when executed, automatically determines a boundary of a document image inside a scan image of a plurality of received scan lines of pixels, wherein the computer executable program comprises, (I) a first set of instructions that automatically compares a neighborhood of pixels located around a group of scan lines of pixels of the scan image against predetermined 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) a second set of instructions that connects 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 during receipt of the scan lines to automatically define the boundary of the document image without manual guidance.
Claim 22
Dependent Claim
106 words
The apparatus of claim 15 , further comprising a fourth set of instructions that determines if the document image has multiple skew angles and a fifth set of instructions that extends (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 23
Dependent Claim
30 words
The method of claim 2 , further comprising performing steps (B), (C), (D) based on a set of predefined parameters in direct response to user input regarding the document image.
References Cited (Backward Citations)
US4533959A
Cited
US4953230A
Cited
US4802229A
Cited
US4723297A
Cited
US4823395A
Cited
US4876730A
Cited
US4941189A
Cited
US5001766A
Cited
US5093653A
Cited
US5181260A
Cited
US5355420A
Cited
US5506918A
Cited
US5452374A
Cited
US5854854A
Cited
WO1995012271A1
Cited
US5818976A
Cited
US5517587A
Cited
US5901253A
Cited
US5940544A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-10-29 | 2005-04-30 | 2005-10-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-10-29 | 2009-04-30 | 2009-10-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-10-29 | 2013-04-30 | 2013-10-30 | $7700.00 | Window Closed / Lapsed |