Error diffusion pattern shifting reduction through programmable threshold perturbation

• US 5,880,857 A
• Filed: 10/10/1996
• Issued: 03/09/1999
• Est. Priority Date: 12/01/1994
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Metcalfe, David J., Shiau, Jeng-Nan, Williams, Leon C.
• Primary Examiner(s): Moore, David K.
• Assistant Examiner(s): BRINICH, STEPHEN M
• Application Number:
  US08/728,416
• Time in Patent Office: 880 Days
• Field of Search: 358/455-456, 358/468, 358/462-463, 358/465-466
• US Class Current: 358/3.03
• CPC Class Codes: H04N 1/4053 with threshold modulated relative to input image data or vice versa

Abstract

A process eliminates pattern shifting artifacts in a printed image by perturbing a threshold/image signal value relationship when a multi-level grey level is binarized. The process utilizes a programmable multi-level grey signal modifying circuit for modifying the multi-level grey signal by a predetermined value according to its grey level. The modified multi-level grey signal is binarized to a binary pixel signal according to a relationship between the modified multi-level grey signal and a threshold value. The process further generates an error corresponding to the relationship and diffuses the error to neighboring pixels. The multi-level grey signal is modified with either random noise multiplied by a grey level dependent coefficient or by a predetermined value from a checkerboard or vertical line pattern. The value from the pattern is dependent upon the grey level and pixel location of the image data.

Claims

1. A system for processing image data having a multi-level grey signal having a first number of grey levels, comprising:

threshold means for generating a threshold value;

conversion means for generating an output having a second number of grey levels based on a relationship between the threshold value and a modified multi-level grey signal, the second number of grey levels being less than the first number of grey levels, and for generating an error corresponding to the relationship between the threshold value and the modified multi-level grey signal;

error diffusion means for adding an error value, corresponding to a predetermined number of errors previously generated by said conversion means, to the multi-level grey signal to generate the modified multi-level grey signal; and

perturbing means for perturbing, according to a grey level of the multi-level grey signal, the relationship between the threshold value and the modified multi-level grey signal by changing the threshold value by a predetermined value, said predetermined value is one of a plurality of values forming a predetermined pattern associated with a particular grey level, said predetermined value being added to the threshold value is determined from a pixel location and grey level of the multi-level grey signal, prior to being modified, being processed by said conversion means, thereby effecting the output and the error from said conversion means.

2. The system as claimed in claim 1, wherein the predetermined pattern is a checkerboard pattern.

3. The system as claimed in claim 1, wherein the predetermined pattern is a vertical line pattern.

4. The system as claimed in claim 1, wherein said perturbing means perturbs the relationship when the grey level is 1/2.

5. The system as claimed in claim 1, wherein said perturbing means perturbs the relationship when the grey level is 1/4.

6. The system as claimed in claim 1, wherein said perturbing means perturbs the relationship when the grey level is 1/3.

7. The system as claimed in claim 1, wherein said perturbing means administers a distinct perturbation to the relationship for each grey level.

8. A system for processing image data having a multi-level grey signal having a first number of grey levels, comprising:

threshold means for generating a threshold value;

conversion means for generating an output having a second number of grey levels based on a relationship between the threshold value and a modified multi-level grey signal, the second number of grey levels being less than the first number of grey levels, and for generating an error corresponding to the relationship between the threshold value and the modified multi-level grey signal;

error diffusion means for adding an error value, corresponding to a predetermined number of errors previously generated by said conversion means, to the multi-level grey signal to generate the modified multi-level grey signal; and

perturbing means for perturbing, according to a grey level of the multi-level grey signal, the relationship between the threshold value and the modified multi-level grey signal by changing the modified multi-level grey signal by a predetermined value, said predetermined value is one of a plurality of values forming a predetermined pattern associated with a particular grey level, said predetermined value being added to the modified multi-level grey signal is determined from a pixel location and grey level of the multi-level grey signal, prior to being modified, being processed by said conversion means, thereby effecting the output and the error from said conversion means.

9. The system as claimed in claim 8, wherein the predetermined pattern is a checkerboard pattern.

10. The system as claimed in claim 8, wherein the predetermined pattern is a vertical line pattern.

11. The system as claimed in claim 8 wherein said perturbing means administers a distinct perturbation to the relationship for each grey level.

12. A method of processing image data having a multi-level grey signal having a first number of grey levels, comprising the steps of:

(a) generating a threshold value;

(b) generating an output having a second number of grey levels based on a relationship between the threshold value and a modified multi-level grey signal, the second number of grey levels being less than the first number of grey levels;

(c) generating an error corresponding to the relationship between the threshold value and the modified multi-level grey signal;

(d) adding an error value, corresponding to a predetermined number of errors previously generated by said step (c), to the multi-level grey signal to generate the modified multi-level grey signal;

(e) perturbing according to a grey level of the multi-level grey signal the relationship, by a predetermined value, between the threshold value and the modified multi-level grey, thereby effecting the output of said step (b) and the error of said step (c);

(f) selecting a predetermined value from one of a plurality of values forming a predetermined pattern associated with a particular grey level; and

(g) determining the predetermined value from a pixel location and grey level of the multi-level grey signal being processed.

13. The method as claimed in claim 12, wherein said step (f) selects the predetermined pattern from a checkerboard pattern.

14. The method as claimed in claim 12, wherein said step (f) selects the predetermined pattern from a vertical line pattern.

15. A system for eliminating pattern shifting artifacts in a printed image, comprising:

image means for generating image data having a multi-level grey signal;

programmable multi-level grey signal modifying means for modifying an error diffused multi-level grey signal by a predetermined value according to the grey level of the multi-level grey signal to generate a modified multi-level grey signal;

binary means for outputting a binary pixel value according to a relationship between the modified multi-level grey signal from said programmable multi-level grey signal modifying means and a threshold value, for generating an error corresponding to the relationship, and for diffusing the error to neighboring pixels; and

error diffusion means for adding an error value, corresponding to a predetermined number of errors previously generated by said binary means, to the multi-level grey signal to generate the error diffused multi-level grey signal.

16. A system for processing image data having a multi-level grey signal having a first number of grey levels, comprising:

threshold means for generating a threshold value;

conversion means for generating an output having a second number of grey levels based on a relationship between a modified threshold value and the multi-level grey signal, the second number of grey levels being less than the first number of grey levels, and for generating an error corresponding to the relationship between the modified threshold value and the multi-level grey signal;

error diffusion means for adding an error value, corresponding to a predetermined number of errors previously generated by said conversion means, to the threshold value to generate the modified threshold value; and

perturbing means for perturbing, according to a grey level of the multi-level grey signal, the relationship between the modified threshold value and the multi-level grey signal by changing the modified threshold value by a predetermined value, said predetermined value is one of a plurality of values forming a predetermined pattern associated with a particular grey level, said predetermined value being added to the modified threshold value is determined from a pixel location and grey level of the multi-level grey signal being processed by said conversion means, thereby effecting the output and the error from said conversion means.

17. A system for processing image data having a multi-level grey signal having a first number of grey levels, comprising:

threshold means for generating a threshold value;

conversion means for generating an output having a second number of grey levels based on a relationship between a modified threshold value and the multi-level grey signal, the second number of grey levels being less than the first number of grey levels, and for generating an error corresponding to the relationship between the modified threshold value and the multi-level grey signal;

error diffusion means for adding an error value, corresponding to a predetermined number of errors previously generated by said conversion means, to the threshold value to generate the modified threshold value; and

perturbing means for perturbing, according to a grey level of the multi-level grey signal, the relationship between the modified threshold value and the multi-level grey signal by changing the multi-level grey signal by a predetermined value, said predetermined value is one of a plurality of values forming a predetermined pattern associated with a particular grey level, said predetermined value being added to the multi-level grey signal is determined from a pixel location and grey level of the multi-level grey signal being processed by said conversion means, thereby effecting the output and the error from said conversion means.

18. A system for processing image data having a multi-level grey signal having a first number of grey levels, comprising:

threshold means for generating a threshold value;

conversion means for generating an output having a second number of grey levels based on a relationship between the threshold value and a modified multi-level grey signal, the second number of grey levels being less than the first number of grey levels, and for generating an error corresponding to the relationship between the threshold value and the modified multi-level grey signal;

error diffusion means for adding an error value, corresponding to a predetermined number of errors previously generated by said conversion means, to the multi-level grey signal to generate the modified multi-level grey signal; and

perturbing means for perturbing, according to a grey level of the multi-level grey signal, the relationship between the threshold value and the modified multi-level grey signal by changing the threshold value by a weighted random noise signal;

said perturbing means including,

a random noise generator to produce random noise,

a weighting value generator to produce a predetermined value, said predetermined value being one of a plurality of values forming a predetermined pattern associated with a particular grey level, said predetermined value being determined from a pixel location and grey level of the multi-level grey signal being processed by said conversion means, and

a multiplier to generate said weighted random noise signal from said random noise and said predetermined value.

19. A system for processing image data having a multi-level grey signal having a first number of grey levels, comprising:

threshold means for generating a threshold value;

conversion means for generating an output having a second number of grey levels based on a relationship between the threshold value and a modified multi-level grey signal, the second number of grey levels being less than the first number of grey levels, and for generating an error corresponding to the relationship between the threshold value and the modified multi-level grey signal;

error diffusion means for adding an error value, corresponding to a predetermined number of errors previously generated by said conversion means, to the multi-level grey signal to generate the modified multi-level grey signal; and

perturbing means for perturbing, according to a grey level of the multi-level grey signal, the relationship between the threshold value and the modified multi-level grey signal by changing the threshold value by a weighted random noise signal;

said perturbing means including,

a random noise generator to produce random noise,

a weighting value generator to produce a predetermined value, said predetermined value being one of a plurality of values forming a predetermined pattern associated with a particular grey level, said predetermined value being determined from a pixel location and grey level of the multi-level grey signal being processed by said conversion means, and

a multiplier to generate said weighted random noise signal from said random noise and said predetermined value.

20. A system for processing image data having a multi-level grey signal having a first number of grey levels, comprising:

threshold means for generating a threshold value;

conversion means for generating an output having a second number of grey levels based on a relationship between a modified threshold value and the multi-level grey signal, the second number of grey levels being less than the first number of grey levels, and for generating an error corresponding to the relationship between the modified threshold value and the multi-level grey signal;

error diffusion means for adding an error value, corresponding to a predetermined number of errors previously generated by said conversion means, to the threshold value to generate the modified threshold value; and

perturbing means for perturbing, according to a grey level of the multi-level grey signal, the relationship between the modified threshold value and the multi-level grey signal by changing the multi-level grey signal by a weighted random noise signal;

said perturbing means including,

a random noise generator to produce random noise,

a weighting value generator to produce a predetermined value, said predetermined value being one of a plurality of values forming a predetermined pattern associated with a particular grey level, said predetermined value being determined from a pixel location and grey level of the multi-level grey signal being processed by said conversion means, and

a multiplier to generate said weighted random noise signal from said random noise and said predetermined value.

21. A system for processing image data having a multi-level grey signal having a first number of grey levels, comprising:

threshold means for generating a threshold value;

conversion means for generating an output having a second number of grey levels based on a relationship between a modified threshold value and the multi-level grey signal, the second number of grey levels being less than the first number of grey levels, and for generating an error corresponding to the relationship between the modified threshold value and the multi-level grey signal;

error diffusion means for adding an error value, corresponding to a predetermined number of errors previously generated by said conversion means, to the threshold value to generate the modified threshold value; and

perturbing means for perturbing, according to a grey level of the multi-level grey signal, the relationship between the threshold value and the modified multi-level grey signal by changing the modified threshold value by a weighted random noise signal;

said perturbing means including,

a random noise generator to produce random noise,

a weighting value generator to produce a predetermined value, said predetermined value being one of a plurality of values forming a predetermined pattern associated with a particular grey level, said predetermined value being determined from a pixel location and grey level of the multi-level grey signal being processed by said conversion means, and

a multiplier to generate said weighted random noise signal from said random noise and said predetermined value.