Patent US5276535A successfully refreshed from Google Patents.
US5276535A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for halftoning of images using grayscale error diffusion
Assignee: Individual
•
Filing: 1991-12-24
•
Granted: 1994-01-04
•
Expires: 2011-12-24
Abstract
Abstract Internal moire artifacts found in digital halftoning of photographic images are diffused by rearranging the order of grayscale levels in an original screen pattern cell to generate a new screen pattern cell having a different grayscale order of stored screen pattern pixels. The grayscale order of the original cell is modified by the addition of a bump function at each point in the original cell in order of grayscale. The new grayscale order is stored in the new cell. Adding the bump function at the chosen point in the original cell influences the choice of the next pixel in the grayscale so that the grayscale order in the new cell is, in general, somewhat different from the grayscale order in the original cell. Errors caused by internal moire effects are thus both diffused in the grayscale dimension, and also diffused isotropically in the spatial dimension. The effect of rearranging the order of the grayscale levels in the screen pattern cell is to diffuse the internal moire artifacts in the final halftone to nearby pixels, thereby rendering the internal moire artifacts less noticeable.
Inventors
- 👤 Raphael L. Levien
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 04:49
CPC Classifications
H; H04; H04N; H04N1/00; H04N1/40; H04N1/405; H04N1/4055; H04N1/4058
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
95 words
A method for generating a halftone screened image from an original image, said method comprising: storing a first screen pattern cell having a first grayscale order of stored screen pattern pixels; rearranging the order of grayscale levels of said stored first screen pattern pixels of said stored first screen pattern cell to generate a second screen pattern cell having a second grayscale order of stored screen pattern pixels; forming a generated screen pattern from said second screen pattern cell; and screening said original image with said generated screen pattern to form said halftone screened image.
Claim 2
Independent Claim
95 words
A method for generating a halftone screened image from an original image, said method comprising: storing a first screen pattern cell having a first grayscale order of stored screen pattern pixels; rearranging the order of grayscale levels of said stored first screen pattern pixels of said stored first screen pattern cell to generate a second screen pattern cell having a second grayscale order of stored screen pattern pixels; forming a generated screen pattern from said second screen pattern cell; and screening said original image with said generated screen pattern to form said halftone screened image.
Claim 3
Dependent Claim
88 words
A method in accordance with claim 1, wherein said step of rearranging the order of grayscale levels of said stored first screen pattern pixels of said first screen pattern cell to generate a second screen pattern cell having a second grayscale order of stored screen pattern pixels comprises: modifying said first screen pattern cell at each stored first screen pattern pixel by combining a function with said first screen pattern cell to alter the respective grayscale levels of pixels adjacent to said each stored first screen pattern pixel.
Claim 4
Dependent Claim
51 words
A method in accordance with claim 2, wherein said step of combining a function with said first screen pattern cell to alter the respective grayscale levels of pixels adjacent to said each stored first screen pattern pixel comprises combining a bump function with respective pixels in said first screen pattern cell.
Claim 5
Dependent Claim
18 words
A method in accordance with claim 3, wherein said bump function is substantially a Gaussian shaped distribution function.
Claim 6
Dependent Claim
38 words
A method in accordance with claim 3, wherein said step of combining said bump function with respective pixels of said first screen pattern cell comprises adding said bump function to respective pixels of said first screen pattern cell.
Claim 7
Dependent Claim
134 words
A method in accordance with claim 2, wherein the step of rearranging the order of grayscale levels of said stored first screen pattern pixels of said stored first screen pattern cell to generate said second screen pattern cell having a second grayscale order of stored screen pattern pixels further comprises: selecting each of said screen pattern pixels in said first screen pattern cell in grayscale order after combining said function with each respective said screen pattern pixels of said first screen pattern cell; and assigning the order of grayscale level of each said stored screen pattern pixels in said second screen pattern cell in the same order as said grayscale order of said modified first screen pattern cell after combining said function with each said screen pattern pixel of said first screen pattern cell.
Claim 8
Dependent Claim
67 words
A method in accordance with claim 2, wherein the step of combining said function with said first screen pattern cell to alter the respective grayscale levels of pixels adjacent to said each stored first screen pattern pixel includes wrapping around portions of said function in areas located outside of said first screen pattern cell, to modify respective screen pattern pixels inside of said first screen pattern cell.
Claim 9
Dependent Claim
94 words
A method in accordance with claim 2, wherein the step of combining said function with said first screen pattern cell to alter the respective grayscale levels of pixels adjacent to said each stored first screen pattern pixel includes wrapping around portions of said function in areas located outside of said first screen pattern cell to modify respective screen pattern pixels in proportion to the respective probability that each portion of said function located in areas outside of said first screen pattern cell corresponds to a pixel located inside of said first screen pattern cell.
Claim 10
Dependent Claim
232 words
A method in accordance with claim 1, wherein said step of rearranging the order of grayscale levels of said stored first screen pattern pixels of said stored first screen pattern cell to generate a second screen pattern cell having a second grayscale order of stored screen pattern pixels comprises: a) setting a reference cell equal to said first screen pattern cell; b) setting a new cell to an initial reset state; c) selecting the lightest pixel in said reference cell and marking the corresponding pixel in said new cell as the first gray shade in the grayscale order of said new cell; d) adding a bump function to the chosen pixel in said reference cell, said bump function darkening the chosen pixel and nearby pixels in said reference cell; e) selecting the next darker pixel in said reference cell excluding previously selected pixels, and marking the corresponding pixel in said new cell as the second gray shade in the grayscale order of said new cell; f) adding said bump function to said selected next darker pixel in said reference cell, said bump function darkening said next darker pixel and nearby pixels in said reference cell; g) repeating steps e) and f) until all pixels in said reference cell have been selected in grayscale order from the lightest to the darkest; and h) using said new cell as said second screen pattern cell.
Claim 11
Dependent Claim
78 words
A method in accordance with claim 2, wherein the step of combining said function with said first screen pattern cell to alter the respective grayscale levels of pixels adjacent to said each stored first screen pattern pixel includes, for each of a plurality of second screen pattern pixels, using the value of said function applied to an offset of said second screen pattern pixel relative to said each stored first screen pattern pixel in said generated screen pattern.
Claim 12
Dependent Claim
48 words
A method in accordance with claim 10, including using portions of said function applied to a plurality of offsets of said screen pattern pixel relative to said each stored first screen pattern pixel, said portions being proportional to relative probabilities of said offsets in said generated screen pattern.
Claim 13
Dependent Claim
39 words
A method in accordance with claim 11, wherein a portion of said function is used for each of said plurality of offsets, said portion being proportional to the relative probability of said offset occurring in said generated screen pattern.
Claim 14
Independent Claim
103 words
An apparatus for generating a halftone screened image from an original image, said apparatus comprising: means for storing a first screen pattern cell having a first grayscale order of stored screen pattern pixels; means for rearranging the order of grayscale levels of said stored first screen pattern pixels of said stored first screen pattern cell to generate a second screen pattern cell having a second grayscale order of stored screen pattern pixels; means for forming a generated screen pattern from said second screen pattern cell; and means for screening said original image with said generated screen pattern to form said halftone screened image.
Claim 15
Independent Claim
103 words
An apparatus for generating a halftone screened image from an original image, said apparatus comprising: means for storing a first screen pattern cell having a first grayscale order of stored screen pattern pixels; means for rearranging the order of grayscale levels of said stored first screen pattern pixels of said stored first screen pattern cell to generate a second screen pattern cell having a second grayscale order of stored screen pattern pixels; means for forming a generated screen pattern from said second screen pattern cell; and means for screening said original image with said generated screen pattern to form said halftone screened image.
Claim 16
Dependent Claim
91 words
An apparatus in accordance with claim 13, wherein said means for rearranging the order of grayscale levels of said stored first screen pattern pixels of said stored first screen pattern cell to generate a second screen pattern cell having a second grayscale order of stored screen pattern pixels comprises: means for modifying said first screen pattern cell at each stored first screen pattern pixel by combining a function with said first screen pattern cell to alter the respective grayscale levels of pixels adjacent to said each stored first screen pattern pixel.
Claim 17
Dependent Claim
53 words
An apparatus in accordance with claim 14, wherein said means for combining a function with said first screen pattern cell to alter the respective grayscale levels of pixels adjacent to said each stored first screen pattern pixel comprises means for combining a bump function with respective pixels in said first screen pattern cell.
Claim 18
Dependent Claim
18 words
An apparatus in accordance with claim 15, wherein said bump function is substantially a Gaussian shaped distribution function.
Claim 19
Dependent Claim
38 words
An apparatus in accordance with claim 15, wherein said means for combining said bump function with respective pixels of said first screen pattern cell comprises adding said bump function to respective pixels of said first screen pattern cell.
Claim 20
Dependent Claim
138 words
An apparatus in accordance with claim 14, wherein said means for rearranging the order of grayscale levels of said stored first screen pattern pixels of said stored first screen pattern cell to generate said second screen pattern cell having a second grayscale order of stored screen pattern pixels further comprises: means for selecting each of said screen pattern pixels in said first screen pattern cell in grayscale order after combining said function with each respective said screen pattern pixels of said first screen pattern cell; and means for assigning the order of grayscale level of each said stored screen pattern pixels in said second screen pattern cell in the same order as said grayscale order of said modified first screen pattern cell after combining said function with each said screen pattern pixel of said first screen pattern cell.
Claim 21
Dependent Claim
67 words
An apparatus in accordance with claim 14, wherein said means for combining said function with said first screen pattern cell to alter the respective grayscale levels of pixels adjacent to said each stored first screen pattern pixel includes wrapping around portions of said function in areas located outside of said first screen pattern cell, to modify respective screen pattern pixels inside of said first screen pattern cell.
Claim 22
Dependent Claim
94 words
An apparatus in accordance with claim 14, wherein said means for combining said function with said first screen pattern cell to alter the respective grayscale levels of pixels adjacent to said each stored first screen pattern pixel includes wrapping around portions of said function in areas located outside of said first screen pattern cell to modify respective screen pattern pixels in proportion to the respective probability that each portion of said function located in areas outside of said first screen pattern cell corresponds to a pixel located inside of said first screen pattern cell.
Claim 23
Dependent Claim
248 words
An apparatus in accordance with claim 13, wherein said means for rearranging the order of grayscale levels of said stored first screen pattern pixels of said stored first screen pattern cell to generate a second screen pattern cell having a second grayscale order of stored screen pattern pixels comprises: a) means for setting a reference cell equal to said first screen pattern cell; b) means for setting a new cell to an initial reset state; c) means for selecting the lightest pixel in said reference cell and marking the corresponding pixel in said new cell as the first gray shade in the grayscale order of said new cell; d) means for adding a bump function to the chosen pixel in said reference cell, said bump function darkening the chosen pixel and nearby pixels in said reference cell; e) means for selecting the next darker pixel in said reference cell excluding previously selected pixels, and marking the corresponding pixel in said new cell as the second gray shade in the grayscale order of said new cell; f) means for adding said bump function to said selected next darker pixel in said reference cell, said bump function darkening said next darker pixel and nearby pixels in said reference cell; g) means for repeating steps e) and f) until all pixels in said reference cell have been selected in grayscale order from the lightest to the darkest; and h) means for using said new cell as said second screen pattern cell.
Claim 24
Dependent Claim
80 words
An apparatus in accordance with claim 14, wherein the means for combining said function with said first screen pattern cell to alter the respective grayscale levels of pixels adjacent to said each stored first screen pattern pixel includes, for each of a plurality of second screen pattern pixels, means for using the value of said function applied to an offset of said second screen pattern pixel relative to said each stored first screen pattern pixel in said generated screen pattern.
Claim 25
Dependent Claim
52 words
An apparatus in accordance with claim 22, further including means for using portions of said function applied to a plurality of offsets of said screen pattern pixel relative to said each stored first screen pattern pixel, said portions being proportional to the relative probabilities of said offsets in said generated screen pattern.
Claim 26
Dependent Claim
38 words
An apparatus in accordance with claim 23, wherein a portion of said function is used for each of said plurality of offsets, said portion being proportional to relative probability of said offset occurring in said generated screen pattern.
References Cited (Backward Citations)
US4051536A
Cited
US4245258A
Cited
US4246614A
Cited
US4633327A
Cited
US4700235A
Cited
US4673971A
Cited
GB2169171A
Cited
US4654721A
Cited
US4821109A
Cited
US4823189A
Cited
US5014333A
Cited
US4924301A
Cited
WO1990006033A2
Cited
US4977458A
Cited
US4918622A
Cited
US4916545A
Cited
US5053887A
Cited
US4985779A
Cited
EP0441609A2
Cited
EP0454277A2
Cited
EP0454274A2
Cited
EP0454276A2
Cited
EP0454275A2
Cited
EP0454273A2
Cited
US5111310A
Cited
US5124803A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-01-03 | 1997-07-05 | 1998-01-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-01-03 | 2001-07-05 | 2002-01-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-01-03 | 2005-07-05 | 2006-01-04 | $7700.00 | Window Closed / Lapsed |