US5517587A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Positioning method and apparatus for line scanned images
Assignee: International Business Machines Corp
•
Filing: 1994-09-23
•
Granted: 1996-05-14
•
Expires: 2014-09-23
Abstract
Abstract A method and computer implementation are disclosed for correcting skew and shift which may occur as the image on a document or other field is scanned with line scanning apparatus. By selecting scans, lines are logically overlaid upon a memory map of the scanned image and a best-fit line is calculated through left-most image points near the left ends of the lines. The best-fit line substantially defines the left margin. The angle which complements the angle between the overlay lines and the best-fit line is calculated and the image map is rotated in storage, aligning the image with scanner's x-axis and y-axis. The method may be started while scanning is still in progress and the last portion of the image may be rotated according to the invention as it is being stored. The left margin is more accurately found by expanding the search for left-most pixels using search areas around the fit originally found left-most points. The best-fit line is further refined by calculating a standard deviation of each left-most point from the best-fit line and taking a new best-fit line through those points that deviate by less than for example two sigma from the original best-fit line.
Inventors
- 👤 Robert G. Baker
- 👤 Paul R. Swingle
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 11:21
CPC Classifications
G; G06; G06T; G06T3/00; G06T3/60; G06T3/608; G06V; G06V30/00; G06V30/10; G06V30/14; G06V30/146; G06V30/1475; G06V30/1478; H; H04; H04N; H04N1/00; H04N1/387; H04N1/3877; H04N1/3878
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
211 words
A computer program for use in a line scanning system, said line scanning system comprising: a scanner for scanning an image and generating image information representative of said image, said image information having background elements and image elements; storage connected to said scanner for storing said elements as they are received from said scanner, said storage storing said elements into said memory so as to preserve a record of the location of each of said elements in said image; a computer connected to said scanner and to said storage and controlled by said computer program, said computer program comprising: first programmed instructions responsive to said scanner for selecting a left-most image element from each of a plurality of selected horizontal line scans; second programmed instructions responsive to said first programmed instructions for listing the location in said image of each of said left-most image elements; third programmed instructions responsive to said second programmed instructions for generating a best-fit line through said listed locations of said left-most image elements; fourth programmed instructions responsive to said third programmed instructions for changing said record of said locations of said image elements so as to rotate said stored image through an angle which is the difference of the slope of said best-fit line from vertical.
Claim 2
Dependent Claim
211 words
A computer program for use in a line scanning system, said line scanning system comprising: a scanner for scanning an image and generating image information representative of said image, said image information having background elements and image elements; storage connected to said scanner for storing said elements as they are received from said scanner, said storage storing said elements into said memory so as to preserve a record of the location of each of said elements in said image; a computer connected to said scanner and to said storage and controlled by said computer program, said computer program comprising: first programmed instructions responsive to said scanner for selecting a left-most image element from each of a plurality of selected horizontal line scans; second programmed instructions responsive to said first programmed instructions for listing the location in said image of each of said left-most image elements; third programmed instructions responsive to said second programmed instructions for generating a best-fit line through said listed locations of said left-most image elements; fourth programmed instructions responsive to said third programmed instructions for changing said record of said locations of said image elements so as to rotate said stored image through an angle which is the difference of the slope of said best-fit line from vertical.
Claim 3
Dependent Claim
91 words
The computer program of claim 1 wherein said fourth programmed instructions further comprise: fifth programmed instructions for choosing a point lying on said best-fit line as a point of relation of said image, the x-coordinate of said point of rotation being the x-coordinate of a point on the left margin; and said computer program further comprising: sixth programmed instructions responsive to said fourth programmed instructions for changing said record of said locations so as to shift said image to provide a predetermined left margin without losing a portion of said image.
Claim 4
Dependent Claim
42 words
The computer program of claim 1 wherein said first programmed instructions are responsive to said scanner having scanned a predetermined upper portion of said image before beginning said selecting of said left-most image element from each of a plurality of subsequent scans.
Claim 5
Dependent Claim
16 words
The computer program of claim 1 wherein said fourth programmed instructions implement a three-shear rotation algorithm.
Claim 6
Dependent Claim
62 words
The computer program of claim 1 wherein said third programmed instructions further comprise: deviation calculation programmed instructions for removing from said list of locations, those locations of said left-most image elements that deviate from said best-fit line by more than a predetermined amount; new best-fit programmed instructions for calculating a new best-fit line through those locations remaining in said list of locations.
Claim 7
Dependent Claim
27 words
The computer program of claim 1 wherein said first programmed instructions select said left-most image element from each kth scan of said scans received from said scanner.
Claim 8
Dependent Claim
250 words
A computer program for use in a line scanning system, said line scanning system comprising: a scanner for scanning an image and generating image information in the form of a plurality of horizontal scan lines representative of said image, said image information having background elements and image elements; storage connected to said scanner for storing said elements as they are received from said scanner, said storage organizing said elements as a map representative of said image; said computer program comprising: first programmed instructions responsive to said scanner for selecting horizontal lines of information received during each kth scan; second programmed instructions responsive to said first programmed instructions for detecting the location on said map of a left-most intersection of each of said kth horizontal scan lines with an image element; third programmed instructions responsive to the detection of said left-most intersections for logically overlaying each of said intersections with a search area; fourth programmed instructions responsive to said third programmed instructions for detecting the location on said map of a left-most image element within each of said areas and substituting said detected location as said left-most image element; fifth programmed instructions responsive to said fourth programmed instructions for generating a best-fit line through said locations on said map of said left-most image elements; sixth programmed instructions responsive to said fifth programmed instructions for calculating an angle between said best-fit line and a vertical line; seventh programmed instructions responsive to said sixth programmed instructions for rotating said map through said angle.
Claim 9
Dependent Claim
250 words
A computer program for use in a line scanning system, said line scanning system comprising: a scanner for scanning an image and generating image information in the form of a plurality of horizontal scan lines representative of said image, said image information having background elements and image elements; storage connected to said scanner for storing said elements as they are received from said scanner, said storage organizing said elements as a map representative of said image; said computer program comprising: first programmed instructions responsive to said scanner for selecting horizontal lines of information received during each kth scan; second programmed instructions responsive to said first programmed instructions for detecting the location on said map of a left-most intersection of each of said kth horizontal scan lines with an image element; third programmed instructions responsive to the detection of said left-most intersections for logically overlaying each of said intersections with a search area; fourth programmed instructions responsive to said third programmed instructions for detecting the location on said map of a left-most image element within each of said areas and substituting said detected location as said left-most image element; fifth programmed instructions responsive to said fourth programmed instructions for generating a best-fit line through said locations on said map of said left-most image elements; sixth programmed instructions responsive to said fifth programmed instructions for calculating an angle between said best-fit line and a vertical line; seventh programmed instructions responsive to said sixth programmed instructions for rotating said map through said angle.
Claim 10
Dependent Claim
95 words
The computer program of claim 7 further comprising: eighth programmed instructions responsive to said seventh programmed instructions for logically overlaying said rotated map with horizontal lines; ninth programmed instructions responsive to said eighth programmed instructions for detecting the location on said map of a right-most intersection of each of said lines with an image element; tenth programmed instructions responsive to said ninth programmed instructions for determining the left margin and the right margin from said left-most intersections and said right-most intersections respectively; eleventh programmed instructions responsive to said tenth programmed instructions for shifting said map.
Claim 11
Dependent Claim
34 words
The computer program of claim 7 wherein said first programmed instructions are responsive to said scanner having scanned a predetermined upper portion of said image and beginning said horizontal line selection after said portion.
Claim 12
Dependent Claim
16 words
The computer program of claim 7 wherein said fourth programmed instructions implement a shear rotation algorithm.
Claim 13
Dependent Claim
67 words
The computer program of claim 7 wherein said fifth programmed instructions further comprise: deviation calculation programmed instructions for calculating a standard deviation of each of said locations of said left-most image elements from said best-fit line; new best-fit programmed instructions responsive to said deviation calculation programmed instructions for calculating a new best-fit line through only those locations that have a standard deviation less than a predetermined value.
Claim 14
Independent Claim
152 words
The method of correcting for skew in a line scanning system comprising the steps of: receiving image information from a scanner which scans a field and generates said image information in the form of a plurality of horizontal scan lines representative of an image, said image information having background elements and image elements; storing said elements as they are received from said scanner, said storage organizing said elements as a map representative of said image; selecting from said image information received from said scanner, horizontal lines of information received during each kth scan; listing the location in said image of a left-most image element of each of said kth horizontal scan lines; generating a best-fit line through said listed locations in said image of said left-most image elements; calculating an angle between said best-fit line and a line perpendicular to said kth horizontal scan lines; and rotating said map through said angle.
Claim 15
Independent Claim
152 words
The method of correcting for skew in a line scanning system comprising the steps of: receiving image information from a scanner which scans a field and generates said image information in the form of a plurality of horizontal scan lines representative of an image, said image information having background elements and image elements; storing said elements as they are received from said scanner, said storage organizing said elements as a map representative of said image; selecting from said image information received from said scanner, horizontal lines of information received during each kth scan; listing the location in said image of a left-most image element of each of said kth horizontal scan lines; generating a best-fit line through said listed locations in said image of said left-most image elements; calculating an angle between said best-fit line and a line perpendicular to said kth horizontal scan lines; and rotating said map through said angle.
Claim 16
Dependent Claim
39 words
The method of claim 12 wherein said step of selecting is responsive to said scanner having scanned a predetermined upper portion of said image before beginning said selecting of said left-most image element from each of said kth scans.
Claim 17
Dependent Claim
57 words
The method of claim 12 wherein said step of generating a best-fit line further comprises the steps of: removing from said list of locations, those locations of said left-most image elements that deviate from said best-fit line by more than a predetermined amount; calculating a new best-fit line through those locations remaining in said list of locations.
Claim 18
Dependent Claim
14 words
The method of claim 12 wherein said rotating step performs a shear rotation algorithm.
Claim 19
Independent Claim
188 words
The method of correcting for skew in a line scanning system comprising the steps of: receiving image information from a scanner which scans a field and generates said image information in the form of a plurality of horizontal scan lines representative of an image, said image information having background elements and image elements; storing said elements as they are received from said scanner, said storage organizing said elements as a map representative of said image; selecting from said image information received from said scanner, horizontal lines of information received during each kth scan; detecting the location on said map of a left-most intersection of each of said kth horizontal scan lines with an image element; generating a best-fit line through said locations on said map of said left-most image elements; calculating a standard deviation of each of said locations of said left-most image elements from said best-fit line; calculating a new best-fit line through only those locations that have a standard deviation less than a predetermined value; calculating an angle between said best-fit line and a line perpendicular to said horizontal lines; rotating said map through said angle.
Claim 20
Independent Claim
188 words
The method of correcting for skew in a line scanning system comprising the steps of: receiving image information from a scanner which scans a field and generates said image information in the form of a plurality of horizontal scan lines representative of an image, said image information having background elements and image elements; storing said elements as they are received from said scanner, said storage organizing said elements as a map representative of said image; selecting from said image information received from said scanner, horizontal lines of information received during each kth scan; detecting the location on said map of a left-most intersection of each of said kth horizontal scan lines with an image element; generating a best-fit line through said locations on said map of said left-most image elements; calculating a standard deviation of each of said locations of said left-most image elements from said best-fit line; calculating a new best-fit line through only those locations that have a standard deviation less than a predetermined value; calculating an angle between said best-fit line and a line perpendicular to said horizontal lines; rotating said map through said angle.
Claim 21
Dependent Claim
74 words
The method of claim 16 further comprising the steps of: logically overlaying said rotated map with horizontal lines; detecting the location on said rotated map of a right-most intersection of each of said lines with an image element; determining the left margin and the right margin from said left-most intersections and said right-most intersections respectively; shifting said map so as to provide for a predetermined left margin without losing a portion of said image.
Claim 22
Dependent Claim
57 words
The method of claim 16 wherein said step of detecting the location of said left-most intersections further comprises the steps of: logically overlaying each of said intersections with a search area; detecting the location on said map of a left-most image element within each of said areas and substituting said detected location as said left-most image element.
Claim 23
Dependent Claim
15 words
The method of claim 16 wherein said step of rotation performs a shear rotation algorithm.
Claim 24
Dependent Claim
242 words
In a line scanning system, the combination comprising: a scanner for scanning an image and generating image information in the form of a plurality of horizontal scan lines representative of said image, said image information having background elements and image elements; storage connected to said scanner for storing said elements as they are received from said scanner, said storage organizing said elements as a map representative of said image; first programmed instructions responsive to said scanner for selecting horizontal lines of information received during each kth scan; second programmed instructions responsive to said first programmed instructions for detecting the location on said map of a left-most intersection of each of said kth horizontal scan lines with an image element; third programmed instructions responsive to said second programmed instructions for generating a best-fit line through said locations on said map of said left-most image elements; fourth programmed instructions responsive to said third programmed instructions for calculating a standard deviation of each of said locations of said left-most image elements from said best-fit line; fifth programmed instructions responsive to said fourth programmed instructions for calculating a new best-fit line through only those locations that have a standard deviation less than a predetermined value; sixth programmed instructions responsive to said fifth programmed instructions for calculating an angle between said best-fit line and a line perpendicular to said horizontal lines; seventh programmed instructions responsive to said sixth programmed instructions for rotating said map through said angle.
Claim 25
Dependent Claim
242 words
In a line scanning system, the combination comprising: a scanner for scanning an image and generating image information in the form of a plurality of horizontal scan lines representative of said image, said image information having background elements and image elements; storage connected to said scanner for storing said elements as they are received from said scanner, said storage organizing said elements as a map representative of said image; first programmed instructions responsive to said scanner for selecting horizontal lines of information received during each kth scan; second programmed instructions responsive to said first programmed instructions for detecting the location on said map of a left-most intersection of each of said kth horizontal scan lines with an image element; third programmed instructions responsive to said second programmed instructions for generating a best-fit line through said locations on said map of said left-most image elements; fourth programmed instructions responsive to said third programmed instructions for calculating a standard deviation of each of said locations of said left-most image elements from said best-fit line; fifth programmed instructions responsive to said fourth programmed instructions for calculating a new best-fit line through only those locations that have a standard deviation less than a predetermined value; sixth programmed instructions responsive to said fifth programmed instructions for calculating an angle between said best-fit line and a line perpendicular to said horizontal lines; seventh programmed instructions responsive to said sixth programmed instructions for rotating said map through said angle.
Claim 26
Dependent Claim
72 words
The line scanning system of claim 20 wherein said second programmed instructions further comprise: expansion programmed instructions responsive to the detection of said left-most intersections for logically overlaying each of said intersections with a search area; search programmed instructions responsive to said expansion programmed instructions for detecting the location on said map of a left-most image element within each of said areas and substituting said detected location as said left-most image element.
Claim 27
Dependent Claim
96 words
The line scanning system of claim 20 further comprising: eighth programmed instructions responsive to said seventh programmed instructions for logically overlaying said rotated map with horizontal lines; ninth programmed instructions responsive to said eighth programmed instructions for detecting the location on said map of a right-most intersection of each of said lines with an image element; tenth programmed instructions responsive to said ninth programmed instructions for determining the left margin and the right margin from said left-most intersections and said right-most intersections respectively; eleventh programmed instructions responsive to said tenth programmed instructions for shifting said map.
References Cited (Backward Citations)
US3831146A
Cited
US4338588A
Cited
US4558461A
Cited
US4723297A
Cited
US5027227A
Cited
US5001766A
Cited
US5093653A
Cited
US5050225A
Cited
EP0433645A2
Cited
US5054098A
Cited
US5233168A
Cited
US5410417A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-05-14 | 1999-11-13 | 2000-05-14 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-05-14 | 2003-11-13 | 2004-05-14 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-05-14 | 2007-11-13 | 2008-05-14 | $7700.00 | Window Closed / Lapsed |