US5331429A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Digital generation of halftone images with error diffusion and frequency matched periodic screen rulings
Assignee: Individual
•
Filing: 1992-02-07
•
Granted: 1994-07-19
•
Expires: 2012-02-07
Abstract
Abstract An error diffusion, or adaptive dither method of producing halftone images includes an injected periodic screen pattern. The frequency of error diffusion dot formation is tuned to roughly match the frequency of the periodic screen pattern by adjustment of a hysteresis constant so that dot formation is phase and frequency locked to the phase and frequency of the periodic screen pattern. The resulting halftone, consisting of an orderly array of dots placed on a grid pattern at substantially the same angle and screen ruling as the periodic screen pattern, combines the advantages of both traditional screening such as precisely angled screens, and the advantages of error diffusion screening, such as better rejection of both internal and external moire artifacts. Any type of screen generation technique such as rational tangent, irrational tangent and rational supercell techniques can be used as a source of the periodic screen pattern.
Inventors
- 👤 Raphael L. Levien
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 18:53
CPC Classifications
H; H04; H04N; H04N1/00; H04N1/40; H04N1/405; H04N1/4051; H04N1/4052
Claims Analysis
Total Claims: 45
Claim 1
Independent Claim
122 words
A method of producing a halftone image comprising: scanning a plurality of input pixels of an original image and generating a numerical value representing a shade of gray for each input pixel scanned; generating output pixels forming halftone dots from said input pixels by error diffusion, wherein the error between an input pixel and an output pixel is distributed to at least one adjacent pixel; generating a periodic screen pattern; adjusting a frequency so that the frequency of said halftone dots and the frequency of said periodic screen pattern are substantially equal; and combining said periodic screen pattern with said halftone dots so as to lock the frequency of said halftone dots to substantially equal the frequency of said periodic screen pattern.
Claim 2
Independent Claim
122 words
A method of producing a halftone image comprising: scanning a plurality of input pixels of an original image and generating a numerical value representing a shade of gray for each input pixel scanned; generating output pixels forming halftone dots from said input pixels by error diffusion, wherein the error between an input pixel and an output pixel is distributed to at least one adjacent pixel; generating a periodic screen pattern; adjusting a frequency so that the frequency of said halftone dots and the frequency of said periodic screen pattern are substantially equal; and combining said periodic screen pattern with said halftone dots so as to lock the frequency of said halftone dots to substantially equal the frequency of said periodic screen pattern.
Claim 3
Dependent Claim
34 words
A method in accordance with claim 1, wherein said step of adjusting a frequency comprises adjusting the frequency of said halftone dots to be substantially equal to the frequency of said periodic screen pattern.
Claim 4
Dependent Claim
34 words
A method in accordance with claim 1, wherein said step of adjusting a frequency comprises adjusting the frequency of said periodic screen pattern to be substantially equal to the frequency of said halftone dots.
Claim 5
Dependent Claim
36 words
A method in accordance with claim 1, wherein said step of combining said periodic screen pattern with said halftone dots substantially locks the phase of said halftone dots to the phase of said periodic screen pattern.
Claim 6
Independent Claim
132 words
An apparatus for producing a halftone image comprising: means for scanning a plurality of input pixels of an original image and generating a numerical value representing a shade of gray for each input pixel scanned; means for generating output pixels forming halftone dots from said input pixels by error diffusion, wherein the error between an input pixel and an output pixel is distributed to at least one adjacent pixel; means for generating a periodic screen pattern; means for adjusting a frequency so that the frequency of said halftone dots and the frequency of said periodic screen pattern are substantially equal; and means for combining said periodic screen pattern with said halftone dots so as to lock the frequency of said halftone dots to substantially equal the frequency of said periodic screen pattern.
Claim 7
Independent Claim
132 words
An apparatus for producing a halftone image comprising: means for scanning a plurality of input pixels of an original image and generating a numerical value representing a shade of gray for each input pixel scanned; means for generating output pixels forming halftone dots from said input pixels by error diffusion, wherein the error between an input pixel and an output pixel is distributed to at least one adjacent pixel; means for generating a periodic screen pattern; means for adjusting a frequency so that the frequency of said halftone dots and the frequency of said periodic screen pattern are substantially equal; and means for combining said periodic screen pattern with said halftone dots so as to lock the frequency of said halftone dots to substantially equal the frequency of said periodic screen pattern.
Claim 8
Dependent Claim
36 words
An apparatus in accordance with claim 5, wherein said means for adjusting a frequency comprises means for adjusting the frequency of said halftone dots to be substantially equal to the frequency of said periodic screen pattern.
Claim 9
Dependent Claim
36 words
An apparatus in accordance with claim 5, wherein said means for adjusting a frequency comprises means for adjusting the frequency of said periodic screen pattern to be substantially equal to the frequency of said halftone dots.
Claim 10
Dependent Claim
39 words
An apparatus in accordance with claim 5, wherein said means for combining said periodic screen pattern with said halftone dots includes means for substantially locking the phase of said halftone dots to the phase of said periodic screen pattern.
Claim 11
Dependent Claim
222 words
An image reproducing system, comprising: a) a scanning means for reading input image data corresponding to the image to be reproduced; b) a screening device comprising: memory means for storing the input image data as gray scale values for sequences of pluralities of input points, and for storing a plurality of binary output signals which direct a marking device to mark and not mark indicia on a medium; means for generating a periodic screen pattern; means for generating signals forming halftone dots, said signals allocating the marking and not marking of the indicia on the medium based on said periodic screen pattern, a value of a current input point in a sequence of input points, a previous output signal corresponding to a previous input point in the sequence and an error representing a difference between the input points and the output signals scaled relative to a maximum gray scale, the error influencing output signals for subsequent input points in the sequence, said error being distributed to at least one adjacent pixel; adjusting a frequency so that the frequency of said halftone dots and the frequency of said periodic screen pattern are substantially equal; and c) a marking device to receive the output signals from the screening device, whereby the marking device marks variable size dots comprising indicia corresponding to said output signals.
Claim 12
Dependent Claim
222 words
An image reproducing system, comprising: a) a scanning means for reading input image data corresponding to the image to be reproduced; b) a screening device comprising: memory means for storing the input image data as gray scale values for sequences of pluralities of input points, and for storing a plurality of binary output signals which direct a marking device to mark and not mark indicia on a medium; means for generating a periodic screen pattern; means for generating signals forming halftone dots, said signals allocating the marking and not marking of the indicia on the medium based on said periodic screen pattern, a value of a current input point in a sequence of input points, a previous output signal corresponding to a previous input point in the sequence and an error representing a difference between the input points and the output signals scaled relative to a maximum gray scale, the error influencing output signals for subsequent input points in the sequence, said error being distributed to at least one adjacent pixel; adjusting a frequency so that the frequency of said halftone dots and the frequency of said periodic screen pattern are substantially equal; and c) a marking device to receive the output signals from the screening device, whereby the marking device marks variable size dots comprising indicia corresponding to said output signals.
Claim 13
Dependent Claim
33 words
The apparatus recited in claim 9, wherein the scanning device scans a plurality of lines corresponding to the image and the sequence corresponds to a plurality of points on at least one line.
Claim 14
Independent Claim
245 words
A method for reproducing a photographic image comprising the steps of: scanning a plurality of input points of an original image for reading input image data corresponding to the input pixels of the image to be reproduced; generating a periodic screen pattern; for a present input pixel, adding an error value previously generated for a first pixel adjacent in a first scanning direction to the present input pixel with an error value generated for a second pixel adjacent to the present input pixel in a second scanning direction orthogonal to the first scanning direction and creating a first result; dividing said first result by two and creating a second result; adding an input data to said second result creating a third result; adding an output value previously generated for the first pixel with an output value previously generated for the second pixel to create a fourth result; multiplying said fourth result by a hysteresis constant to create a fifth result; adding said periodic pattern and said fifth result to said third result to create a sixth result; storing a seventh result of 1 if said sixth result is not less than zero and if said sixth result is less than zero storing a seventh result of 0; multiplying said seventh result by a constant creating an eighth result; subtracting said eighth result from said third result to create a present error value and marking indicia on an output medium in accordance with said seventh result.
Claim 15
Independent Claim
245 words
A method for reproducing a photographic image comprising the steps of: scanning a plurality of input points of an original image for reading input image data corresponding to the input pixels of the image to be reproduced; generating a periodic screen pattern; for a present input pixel, adding an error value previously generated for a first pixel adjacent in a first scanning direction to the present input pixel with an error value generated for a second pixel adjacent to the present input pixel in a second scanning direction orthogonal to the first scanning direction and creating a first result; dividing said first result by two and creating a second result; adding an input data to said second result creating a third result; adding an output value previously generated for the first pixel with an output value previously generated for the second pixel to create a fourth result; multiplying said fourth result by a hysteresis constant to create a fifth result; adding said periodic pattern and said fifth result to said third result to create a sixth result; storing a seventh result of 1 if said sixth result is not less than zero and if said sixth result is less than zero storing a seventh result of 0; multiplying said seventh result by a constant creating an eighth result; subtracting said eighth result from said third result to create a present error value and marking indicia on an output medium in accordance with said seventh result.
Claim 16
Dependent Claim
119 words
A photographic image reproducing system comprising: a scanning device receiving an input array i(x,y) corresponding to an original image to be reproduced, wherein x and y represent scanning directions; means for receiving a periodic screen pattern a marking device receiving output signals o(x,y) from a screening device for marking indicia on an output medium in accordance with said output signals o(x,y); the screening device using said input array i(x,y) in a recurrence relation calculation means, the recurrence relation being: ##EQU4## wherein o(x,y) is an output array, fs is a maximum allowable value of members of said array i (x,y), sh is the coefficient for image sharpness enhancement, H is a hysteresis constant; and S(x,y) is said periodic screen pattern.
Claim 17
Dependent Claim
119 words
A photographic image reproducing system comprising: a scanning device receiving an input array i(x,y) corresponding to an original image to be reproduced, wherein x and y represent scanning directions; means for receiving a periodic screen pattern a marking device receiving output signals o(x,y) from a screening device for marking indicia on an output medium in accordance with said output signals o(x,y); the screening device using said input array i(x,y) in a recurrence relation calculation means, the recurrence relation being: ##EQU4## wherein o(x,y) is an output array, fs is a maximum allowable value of members of said array i (x,y), sh is the coefficient for image sharpness enhancement, H is a hysteresis constant; and S(x,y) is said periodic screen pattern.
Claim 18
Dependent Claim
21 words
A photographic image reproducing system as recited in claim 12 wherein: e(x, -1)=0; e(-1,y)=0;. e (width, y)=0; o(x,-1)=0; o(-1,y)=0; and o(width,y)=0.
Claim 19
Independent Claim
166 words
A method of producing a halftone image comprising the steps of: scanning a plurality of input points of an original image and generating a numerical value representing a shade of gray for each input point scanned; receiving a periodic screen pattern; outputting a screened image forming halftone dots, each of said halftone dots having a plurality of dots, each dot of said plurality of dots being one of black or white, the size of each plurality of dots being determined form a recursive relationship between said periodic screen pattern, a value of a current input point, a previous output, and an error representing a difference between a value of a previous input point and the previous output, said error being distributed to at least one adjacent pixel; adjusting a frequency so that the frequency of said halftone dots and the frequency of said periodic screen pattern are substantially equal; and transmitting signals representing the screened image to a marking device for marking on an output medium.
Claim 20
Independent Claim
166 words
A method of producing a halftone image comprising the steps of: scanning a plurality of input points of an original image and generating a numerical value representing a shade of gray for each input point scanned; receiving a periodic screen pattern; outputting a screened image forming halftone dots, each of said halftone dots having a plurality of dots, each dot of said plurality of dots being one of black or white, the size of each plurality of dots being determined form a recursive relationship between said periodic screen pattern, a value of a current input point, a previous output, and an error representing a difference between a value of a previous input point and the previous output, said error being distributed to at least one adjacent pixel; adjusting a frequency so that the frequency of said halftone dots and the frequency of said periodic screen pattern are substantially equal; and transmitting signals representing the screened image to a marking device for marking on an output medium.
Claim 21
Dependent Claim
24 words
The method recited in claim 14, wherein the recursive relationship employs a hysteresis constant, the hysteresis constant determining the coarseness of the screened image.
Claim 22
Dependent Claim
19 words
The method recited in claim 15, wherein the hysteresis constant defines an allowable excursion of the error around zero.
Claim 23
Dependent Claim
14 words
The method recited in claim 14, wherein the scanning is performed in two dimensions.
Claim 24
Dependent Claim
14 words
The method recited in claim 14, wherein the error is allocated in two dimensions.
Claim 25
Dependent Claim
18 words
The method recited in claim 18, wherein the error is allocated equally in each of the two dimensions.
Claim 26
Dependent Claim
23 words
The method recited in claim 14, wherein the black dots and white dots are produced by marking and not marking the medium, respectively.
Claim 27
Independent Claim
217 words
A method of producing a halftone image comprising the steps of: scanning a plurality of input points of an original image and generating a numerical value representing a shade of gray for each input point scanned; receiving a periodic screen pattern; outputting a screened image having a plurality of dots, each dot of said plurality of dots being one of black or white, the size of each plurality of dots being determined form a recursive relationship between said periodic screen pattern, a value of a current input point previous output, and an error representing a difference between a value of a previous input point and the previous output; and transmitting signals representing the screened image to a marking device for marking on an output medium, wherein the recursive relationship is defined as: ##EQU5## where x refers to pixels in a scan line, y refers to the scan lines, i(x, y) and o(x, y) are the input and output arrays, respectively, fs is the full scale input value, typically 255 in the case of an eight bit array, sh is the coefficient for image sharpness enhancement, H is a hysteresis constant typically of value 0.5 times the value of fs and where larger values of H result in a coarser screen, and S(x,y) is said periodic screen pattern.
Claim 28
Independent Claim
217 words
A method of producing a halftone image comprising the steps of: scanning a plurality of input points of an original image and generating a numerical value representing a shade of gray for each input point scanned; receiving a periodic screen pattern; outputting a screened image having a plurality of dots, each dot of said plurality of dots being one of black or white, the size of each plurality of dots being determined form a recursive relationship between said periodic screen pattern, a value of a current input point previous output, and an error representing a difference between a value of a previous input point and the previous output; and transmitting signals representing the screened image to a marking device for marking on an output medium, wherein the recursive relationship is defined as: ##EQU5## where x refers to pixels in a scan line, y refers to the scan lines, i(x, y) and o(x, y) are the input and output arrays, respectively, fs is the full scale input value, typically 255 in the case of an eight bit array, sh is the coefficient for image sharpness enhancement, H is a hysteresis constant typically of value 0.5 times the value of fs and where larger values of H result in a coarser screen, and S(x,y) is said periodic screen pattern.
Claim 29
Dependent Claim
29 words
The method in claim 21, wherein fs is a value representing a maximum gray shade and h is a product of fs and a number not less than zero.
Claim 30
Independent Claim
171 words
An apparatus for producing a halftone image comprising: means for scanning a plurality of input points of an original image and generating a numerical value representing a shade of gray for each input point scanned; means for receiving a periodic screen pattern; means for outputting a screened image forming halftone dots, each of said halftone dots having a plurality of dots, each dot of said plurality of dots being one of black or white, the size of each plurality of dots being determined form a recursive relationship between said periodic screen pattern, a value of a current input point, a previous output, and an error representing a difference between a value of a previous input point and the previous output, said error being distributed to at least one adjacent pixel; adjusting a frequency so that the frequency of said halftone dots and the frequency of said periodic screen pattern are substantially equal; and means for transmitting signals representing the screened image to a marking device for marking on an output medium.
Claim 31
Independent Claim
171 words
An apparatus for producing a halftone image comprising: means for scanning a plurality of input points of an original image and generating a numerical value representing a shade of gray for each input point scanned; means for receiving a periodic screen pattern; means for outputting a screened image forming halftone dots, each of said halftone dots having a plurality of dots, each dot of said plurality of dots being one of black or white, the size of each plurality of dots being determined form a recursive relationship between said periodic screen pattern, a value of a current input point, a previous output, and an error representing a difference between a value of a previous input point and the previous output, said error being distributed to at least one adjacent pixel; adjusting a frequency so that the frequency of said halftone dots and the frequency of said periodic screen pattern are substantially equal; and means for transmitting signals representing the screened image to a marking device for marking on an output medium.
Claim 32
Dependent Claim
24 words
The apparatus recited in claim 23, wherein the recursive relationship employs a hysteresis constant, the hysteresis constant determining the coarseness of the screened image.
Claim 33
Dependent Claim
19 words
The apparatus recited in claim 24, wherein the hysteresis constant defines an allowable excursion of the error around zero.
Claim 34
Dependent Claim
14 words
The apparatus recited in claim 23, wherein the scanning is performed in two dimensions.
Claim 35
Dependent Claim
14 words
The apparatus recited in claim 23, wherein the error is allocated in two dimensions.
Claim 36
Dependent Claim
18 words
The apparatus recited in claim 27, wherein the error is allocated equally in each of the two dimensions.
Claim 37
Dependent Claim
22 words
The apparatus recited in claim 23, wherein the black and white dots correspond to marking and not marking the output medium, respectively.
Claim 38
Independent Claim
223 words
An apparatus for producing a halftone image comprising: means for scanning a plurality of input points of an original image and generating a numerical value representing a shade of gray for each input point scanned; means for receiving a periodic screen pattern; means for outputting a screened image having a plurality of dots, each dot of said plurality of dots being one of black or white, the size of each plurality of dots being determined from a recursive relationship between said periodic screen pattern, a value of a current input point, a previous output, and an error representing a difference between a value of a previous input point and the previous output; and means for transmitting signals representing the screened image to a marking device for marking on an output medium wherein the recursive relationship is defined as: ##EQU6## where x refers to pixels in a scan line, y refers to the scan lines, i(x, y) and o(x, y) are the input and output arrays, respectively, fs is the full scale input value, typically 255 in the case of an eight bit array, sh is the coefficient for image sharpness enhancement, H is a hysteresis constant typically of value 0.5 times the value of fs and where larger values of H result in a coarser screen, and S(x,y) is said periodic screen pattern.
Claim 39
Independent Claim
223 words
An apparatus for producing a halftone image comprising: means for scanning a plurality of input points of an original image and generating a numerical value representing a shade of gray for each input point scanned; means for receiving a periodic screen pattern; means for outputting a screened image having a plurality of dots, each dot of said plurality of dots being one of black or white, the size of each plurality of dots being determined from a recursive relationship between said periodic screen pattern, a value of a current input point, a previous output, and an error representing a difference between a value of a previous input point and the previous output; and means for transmitting signals representing the screened image to a marking device for marking on an output medium wherein the recursive relationship is defined as: ##EQU6## where x refers to pixels in a scan line, y refers to the scan lines, i(x, y) and o(x, y) are the input and output arrays, respectively, fs is the full scale input value, typically 255 in the case of an eight bit array, sh is the coefficient for image sharpness enhancement, H is a hysteresis constant typically of value 0.5 times the value of fs and where larger values of H result in a coarser screen, and S(x,y) is said periodic screen pattern.
Claim 40
Dependent Claim
30 words
The apparatus recited in claim 30, wherein fs is a value representing a maximum gray shade and H is a product of fs and a number not less than zero.
Claim 41
Independent Claim
267 words
An apparatus for reproducing a photographic image comprising: means for scanning a plurality of input points of an original image for reading input image data corresponding to the input pixels of the image to be reproduced; means for generating a periodic screen pattern; means for isolating a present input pixel and adding an error value previously generated for a first pixel adjacent in a first scanning direction to the present input pixel with an error value generated for a second pixel adjacent to the present input pixel in a second scanning direction orthogonal to the first scanning direction and creating a first result; means for dividing said first result by two and creating a second result; means for adding an input data to said second result creating a third result; means for adding an output value previously generated for the first pixel with an output value previously generated for the second pixel to create a fourth result; means for multiplying said fourth result by a hysteresis constant to create a fifth result; means for adding said periodic pattern and said fifth result to said third result to create a sixth result; means for storing a seventh result of 1 if said sixth result is not less than zero and if said sixth result is less than zero storing a seventh result of 0; means for multiplying said seventh result by a constant creating an eighth result; means for subtracting said eighth result from said third result to create a present error value and means for marking indicia on an output medium in accordance with said seventh result.
Claim 42
Independent Claim
267 words
An apparatus for reproducing a photographic image comprising: means for scanning a plurality of input points of an original image for reading input image data corresponding to the input pixels of the image to be reproduced; means for generating a periodic screen pattern; means for isolating a present input pixel and adding an error value previously generated for a first pixel adjacent in a first scanning direction to the present input pixel with an error value generated for a second pixel adjacent to the present input pixel in a second scanning direction orthogonal to the first scanning direction and creating a first result; means for dividing said first result by two and creating a second result; means for adding an input data to said second result creating a third result; means for adding an output value previously generated for the first pixel with an output value previously generated for the second pixel to create a fourth result; means for multiplying said fourth result by a hysteresis constant to create a fifth result; means for adding said periodic pattern and said fifth result to said third result to create a sixth result; means for storing a seventh result of 1 if said sixth result is not less than zero and if said sixth result is less than zero storing a seventh result of 0; means for multiplying said seventh result by a constant creating an eighth result; means for subtracting said eighth result from said third result to create a present error value and means for marking indicia on an output medium in accordance with said seventh result.
Claim 43
Dependent Claim
195 words
An image reproducing system for generating on an output medium an image corresponding to an original image, the system comprising: a) a scanning means for reading input data of the original image to be reproduced, the scanning means generating signals representing gray scale values corresponding to each pixel of the original; b) a screening device comprising: memory means for storing the image data corresponding to each pixel and a plurality of output signals which direct a marking device to mark one of black or white indicia on the output medium for each output signal, each output signal corresponding to a pixel on the output medium; means for generating a periodic screen pattern; means for generating signals allocating the black or white indicia on the output medium based on said periodic screen pattern, the gray scale value of a current gray scale signal, a previous output signal and an error signal representing a difference between the current gray scale signals and at least one previously generated output signal; c) a marking device to receive the output signals from the screening device, the marking device thereby generating variable size dots comprising indicia corresponding to the output signals.
Claim 44
Dependent Claim
195 words
An image reproducing system for generating on an output medium an image corresponding to an original image, the system comprising: a) a scanning means for reading input data of the original image to be reproduced, the scanning means generating signals representing gray scale values corresponding to each pixel of the original; b) a screening device comprising: memory means for storing the image data corresponding to each pixel and a plurality of output signals which direct a marking device to mark one of black or white indicia on the output medium for each output signal, each output signal corresponding to a pixel on the output medium; means for generating a periodic screen pattern; means for generating signals allocating the black or white indicia on the output medium based on said periodic screen pattern, the gray scale value of a current gray scale signal, a previous output signal and an error signal representing a difference between the current gray scale signals and at least one previously generated output signal; c) a marking device to receive the output signals from the screening device, the marking device thereby generating variable size dots comprising indicia corresponding to the output signals.
Claim 45
Dependent Claim
23 words
The apparatus recited in claim 33, wherein the black and white indicia correspond to marking and not marking of the output medium, respectively.
References Cited (Backward Citations)
US4051536A
Cited
US4245258A
Cited
US4246614A
Cited
US4633327A
Cited
US4700235A
Cited
US4673971A
Cited
US4654721A
Cited
US4821109A
Cited
US4823189A
Cited
US4924301A
Cited
US4977458A
Cited
US4916545A
Cited
US4918622A
Cited
US5189529A
Cited
US5051844A
Cited
US5053887A
Cited
US4985779A
Cited
US5070413A
Cited
US5055942A
Cited
EP0454277A2
Cited
EP0454276A2
Cited
EP0454274A2
Cited
EP0454273A2
Cited
EP0454275A2
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-07-18 | 1998-01-17 | 1998-07-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-07-18 | 2002-01-17 | 2002-07-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-07-18 | 2006-01-17 | 2006-07-19 | $7700.00 | Window Closed / Lapsed |