Digital generation of halftone images with error diffusion and frequency matched periodic screen rulings

• US 5,331,429 A
• Filed: 02/07/1992
• Issued: 07/19/1994
• Est. Priority Date: 02/07/1992
• Status: Expired due to Fees

• Current Assignee: Raphael L. Levien
• Original Assignee: Raphael L. Levien
• Inventors: Levien, Raphael L.
• Primary Examiner(s): Coles, Sr., Edward L.
• Assistant Examiner(s): NGUYEN, ANH-VINH THI
• Application Number:
  US07/832,555
• Time in Patent Office: 893 Days
• Field of Search: 358/456, 358/455, 358/457, 358/447, 358/445, 358/454, 358/458, 358/459, 358/428, 358/463
• US Class Current: 358/3.18
• CPC Class Codes: H04N 1/4052 by error diffusion, i.e. transferring the binarising error to neighbouring dot decisions

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

8. 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.

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

15. The method recited in claim 14, wherein the recursive relationship employs a hysteresis constant, the hysteresis constant determining the coarseness of the screened image.

16. The method recited in claim 15, wherein the hysteresis constant defines an allowable excursion of the error around zero.

17. The method recited in claim 14, wherein the scanning is performed in two dimensions.

18. The method recited in claim 14, wherein the error is allocated in two dimensions.

19. The method recited in claim 18, wherein the error is allocated equally in each of the two dimensions.

20. The method recited in claim 14, wherein the black dots and white dots are produced by marking and not marking the medium, respectively.

21. 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.

22. 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.

23. 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.

24. The apparatus recited in claim 23, wherein the recursive relationship employs a hysteresis constant, the hysteresis constant determining the coarseness of the screened image.

25. The apparatus recited in claim 24, wherein the hysteresis constant defines an allowable excursion of the error around zero.

26. The apparatus recited in claim 23, wherein the scanning is performed in two dimensions.

27. The apparatus recited in claim 23, wherein the error is allocated in two dimensions.

28. The apparatus recited in claim 27, wherein the error is allocated equally in each of the two dimensions.

29. The apparatus recited in claim 23, wherein the black and white dots correspond to marking and not marking the output medium, respectively.

30. 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.

31. 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.

32. 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.

33. 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.

34. The apparatus recited in claim 33, wherein the black and white indicia correspond to marking and not marking of the output medium, respectively.