US5124803A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for generating digital, angled halftone screens using pixel candidate lists and screen angle correction to prevent moire patterns
Assignee: ECRM Inc
•
Filing: 1991-02-25
•
Granted: 1992-06-23
•
Expires: 2011-02-25
Abstract
Abstract In digital halftone color printing, low spatial frequency patterning can occur due to the interaction of the overlapping angled halftone screens. The moire patterning can be minimized by automatically constructing digital haltone angled screens from screen tiles which are designed to minimize the low spatial frequency patterning. The screen tile boundaries are generated in response to selected integers which, together with the number of screen dots along a side of the tile in the direction of screen pitch measurement, determine the a limit on the magnitude of screen angle error. Based upon these values, each pixel within the tile boundary is associated with one of the screen dots of the image. Typically, the pixels are added to potential candidate lists from which they can be selected for inclusion within a particular screen dot.
Inventors
- 👤 Donald E. Troxel
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 09:29
CPC Classifications
H; H04; H04N; H04N1/00; H04N1/40; H04N1/405; H04N1/4055; H04N1/4058
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
177 words
A method for automatically generating a digital halftone screen at an angle to a Cartesian coordinate system used for scanning and recording, the screen being composed of a plurality of repetitive screen tiles, the screen having a desired screen pitch "p" and ideal screen angle "s", and each tile containing an integer number, "N", of screen dots along a side of the tile in a direction of screen pitch measurement, the method comprising the steps of selecting integers "a", "b", and "N" for providing a screen angle error, equal to the magnitude of ((arctan (a/b))-s), less than a selected threshold and yielding the desired screen pitch, automatically generating a screen tile boundary configuration in response to values of "a" and "b", automatically assigning each pixel within said tile boundary to be associated with a selected one of said screen dots, generating threshold data, in response to said assigning step, representing a screen signal threshold value for each pixel of the tile; and generating an angled halftone digital screen using said threshold data in said Cartesian coordinate system.
Claim 2
Independent Claim
177 words
A method for automatically generating a digital halftone screen at an angle to a Cartesian coordinate system used for scanning and recording, the screen being composed of a plurality of repetitive screen tiles, the screen having a desired screen pitch "p" and ideal screen angle "s", and each tile containing an integer number, "N", of screen dots along a side of the tile in a direction of screen pitch measurement, the method comprising the steps of selecting integers "a", "b", and "N" for providing a screen angle error, equal to the magnitude of ((arctan (a/b))-s), less than a selected threshold and yielding the desired screen pitch, automatically generating a screen tile boundary configuration in response to values of "a" and "b", automatically assigning each pixel within said tile boundary to be associated with a selected one of said screen dots, generating threshold data, in response to said assigning step, representing a screen signal threshold value for each pixel of the tile; and generating an angled halftone digital screen using said threshold data in said Cartesian coordinate system.
Claim 3
Dependent Claim
87 words
The method of claim 1 wherein said assigning step comprises the steps of selecting centers for each of the screen dots within the tile; selecting pixels for approximating the center of each said screen dot; selecting from available pixels within said tile boundary, for each dot, a best fitting pixel for assignment to each said screen dot and assigning said selected pixel to said screen dot; and repeating said available pixel selecting step until all pixels within the tile boundary have been assigned to said screen dots.
Claim 4
Dependent Claim
40 words
The method of claim 2 wherein said repeating step comprises the step of sequentially performing said available pixel selecting step for all pixels assigned to one screen dot before performing said available pixel selecting step for a next screen dot.
Claim 5
Dependent Claim
48 words
The method of claim 3 wherein said repeating step comprises the step of selecting a said pixel for a said screen dot and thereafter selecting a said pixel for a different screen dot, whereby all screen dots are grown at a substantially equivalent rate and size in parallel.
Claim 6
Independent Claim
189 words
A method for automatically generating a digital halftone screen at an angle to a Cartesian coordinate system used for scanning and recording, the screen being composed of a plurality of repetitive screen tiles, the screen having a desired screen pitch "p" and ideal screen angle "s", and each tile containing an integer number, "N", of screen dots along a side of the tile in a direction of screen pitch measurement, the method comprising the steps of selecting integers "a", "b", and "N" for providing a screen angle error, equal to the magnitude of ((arctan (a/b))-s), less than a selected threshold and yielding the desired screen pitch, automatically generating a screen tile boundary configuration in response to values of "a" and "b", automatically assigning each pixel within said tile boundary to be associated with a selected one of said screen dots, storing said pixel associations in a mapping array, generating a threshold array in response to said assigning step having elements representing a screen signal threshold value for each pixel of the tile; and generating an angled halftone digital screen using said threshold array data in said Cartesian coordinate system.
Claim 7
Independent Claim
189 words
A method for automatically generating a digital halftone screen at an angle to a Cartesian coordinate system used for scanning and recording, the screen being composed of a plurality of repetitive screen tiles, the screen having a desired screen pitch "p" and ideal screen angle "s", and each tile containing an integer number, "N", of screen dots along a side of the tile in a direction of screen pitch measurement, the method comprising the steps of selecting integers "a", "b", and "N" for providing a screen angle error, equal to the magnitude of ((arctan (a/b))-s), less than a selected threshold and yielding the desired screen pitch, automatically generating a screen tile boundary configuration in response to values of "a" and "b", automatically assigning each pixel within said tile boundary to be associated with a selected one of said screen dots, storing said pixel associations in a mapping array, generating a threshold array in response to said assigning step having elements representing a screen signal threshold value for each pixel of the tile; and generating an angled halftone digital screen using said threshold array data in said Cartesian coordinate system.
Claim 8
Dependent Claim
145 words
The method of claim 5 wherein said assigning step comprises the steps of selecting centers for each of the screen dots within the tile; initializing a candidate list for each screen dot for recording pixels available for inclusion in said each screen dot; selecting pixels for approximating the center of each said screen dot; adding to said candidate list of a said screen dot, pixels adjacent to said selected center pixel for said screen dot; selecting, from the candidate list for each dot, a best fitting pixel for assignment to each said selected screen dot and assigning said selected pixel to said screen dot; adding to said candidate list, pixels horizontally and vertically adjacent to a last selected pixel; prioritizing each said candidate list; and repeating said pixel selecting and adding steps until all pixels within the tile have been assigned to said screen dots.
Claim 9
Dependent Claim
47 words
The method of claim 6 wherein said storing step comprises the steps of assigning, to each of said pixels contained in said screen tile, a screen dot identifier; and storing the screen dot identifier in said mapping array at a location corresponding to said pixel being selected.
Claim 10
Dependent Claim
38 words
The method of claim 7 wherein said threshold array generating step comprises the step of assigning threshold values in said threshold array for each pixel of a tile, said threshold values corresponding to screen signal dither threshold levels.
Claim 11
Dependent Claim
57 words
The method of claim 5 wherein said threshold array generating step further comprises the step of basing said screen signal threshold value for a selected pixel on an order in which said pixel was selected for inclusion in said screen dot, each succeeding pixel being assigned an incrementally different dither threshold value than a previously selected pixel.
Claim 12
Dependent Claim
36 words
The method of claim 2 wherein said available pixel selecting step comprises the step of selecting a pixel located nearest to a last chosen pixel if two or more pixel candidates have a same highest priority.
Claim 13
Dependent Claim
47 words
The method of claim 2 wherein said available pixel selecting step further, comprises the step of selecting a pixel minimizing an RMS error of a resulting dot with respect to an ideal dot model being employed if two or more pixel candidates have a same highest priority.
Claim 14
Dependent Claim
30 words
The method of claim 5 wherein said assigning step for pixel selection comprises the step of proceeding in parallel for all of the screen dots contained within the tile boundary.
Claim 15
Dependent Claim
39 words
The method of claim 2 wherein said available pixel selecting step further comprises the step of selecting the pixel which minimizes the error associated with aligning neighboring dots, if two or more pixel candidates have a same highest priority.
Claim 16
Dependent Claim
50 words
The method of claim 6 further wherein said assigning step comprises the step of choosing a next pixel on said list, if the pixel chosen from the candidate list has already been assigned to another screen dot, until either an unused pixel is chosen or the candidate list is exhausted.
Claim 17
Dependent Claim
20 words
The method of claim 5 further comprising the step of providing a tile having "N" screen dots along each side.
Claim 18
Dependent Claim
46 words
The method of claim 1 further comprising the step of receiving, from a data source, Cartesian coordinate data, and recording said Cartesian coordinate data on a recording medium using a scanning line moving at an angle to said ideal screen angle and using the threshold data.
Claim 19
Dependent Claim
19 words
The method of claim 1 further comprising the step of tiling a plane using said screen tile boundary configuration.
Claim 20
Dependent Claim
50 words
The method of claim 2 wherein the step of selecting from available pixels comprises the steps of determining how many exposed pixel edges result from adding a pixel to a said screen dot, and using said resulting exposed pixel edges in determining whether the pixel is a best fitting pixel.
References Cited (Backward Citations)
US4115816A
Cited
US4149183A
Cited
US4185304A
Cited
US4566042A
Cited
US4498108A
Cited
US4809063A
Cited
US4924301A
Cited
US4926267A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1995-06-23 | 1995-12-23 | 1996-06-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1999-06-23 | 1999-12-23 | 2000-06-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2003-06-23 | 2003-12-23 | 2004-06-23 | $7700.00 | Window Closed / Lapsed |