System and method for implementing fast high addressability error diffusion process

• US 5,528,384 A
• Filed: 08/03/1994
• Issued: 06/18/1996
• Est. Priority Date: 08/03/1994
• Status: Expired due to Term

• 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): Coles, Sr., Edward L.
• Assistant Examiner(s): Stoll, Thomas L.
• Application Number:
  US08/285,572
• Time in Patent Office: 685 Days
• Field of Search: 358/447, 358/448, 358/451, 358/455, 358/456, 358/465
• US Class Current: 358/447
• CPC Class Codes: H04N 1/4053 with threshold modulated relative to input image data or vice versa

Abstract

A method and system implements a high addressability characteristic into an error diffusion process. A grey level value representing a pixel is received. The grey level value is interpolated to generate subpixel grey level values which correspond to a second resolution. A threshold circuit thresholds the interpolated grey level value. In parallel to the interpolation circuit and threshold circuit is an error circuit which generates a plurality of possible error values. One of the plurality of possible error values is selected based on the number of subpixels exceeding a threshold value. A portion of the selected error value is then diffused to adjacent pixels on a next scanline.

Claims

1. A method of diffusing an error generated from thresholding a grey level value representing a pixel, comprising the steps of:

(a) receiving grey level values representing pixels, each pixel having a single grey level value associated therewith;

(b) converting the grey level value of a pixel to a predetermined number of interpolated subpixel values;

(c) thresholding each of the interpolated subpixel values;

(d) generating a plurality of possible error values in parallel with the conversion and thresholding carried out by said steps (b) and (c);

(e) selecting one of the plurality of possible error values based on a number of interpolated subpixels values exceeding a threshold value determined in said step (c); and

(f) diffusing the selected error value to grey level values representing adjacent pixels.

2. The method as claimed in claim 1, wherein said step (b) comprises the substeps of:

(b1) computing a first interpolated subpixel value; and

(b2) computing a second interpolated subpixel value.

3. The method as claimed in claim 1, wherein said step (b) further comprises the substep of:

(b3) computing a plurality of interpolated subpixel values B_n, the interpolated subpixel values B_n being equal to P0+n(P1-P0)/N, wherein n is equal to 0 to N-1, P0 is equal to a grey level value of a first pixel, P1 is equal to a grey level value of a second pixel, and N is equal to a high addressability characteristic.

4. The method as claimed in claim 3, wherein said step (d) comprises the substeps of:

(d1) calculating a desired output;

(d2) calculating a plurality of possible actual outputs; and

(d3) calculating the plurality of possible error values, each error value being equal to the desired output minus a possible actual output.

5. The method as claimed in claim 1, further comprising the step of:

(g) screening the grey level value with a predetermined screen prior to the execution of said step (b).

6. A system for diffusing an error generated from thresholding a grey level value representing a pixel, comprising:

input means for receiving grey level values representing pixels, each pixel having a single grey level value associated therewith;

high addressability means for converting the grey level value of a pixel to a predetermined number of interpolated subpixel values;

threshold means for thresholding each of the interpolated subpixel values and for determining a number of interpolated subpixels values which exceed a threshold value;

error means, operatively connected in parallel with said high addressability means and said threshold means, for generating a plurality of possible error values;

selecting means, operatively connected to said error means and said threshold means, for selecting one of the plurality of possible error values based on the number of interpolated subpixels values exceeding a threshold value determined by said threshold means; and

error diffusing means for diffusing the selected error value to grey level values representing adjacent pixels.

7. The system as claimed in claim 6, wherein said high addressability means computes a first interpolated subpixel value and a second interpolated subpixel value.

8. The system as claimed in claim 6, wherein said high addressability means further computes a plurality of interpolated subpixel values B_n, the interpolated subpixel values B_n being equal to P0+n(P1-P0)/N, wherein n is equal to 0 to N-1, P0 is equal to a grey level value of a first pixel, P1 is equal to a grey level value of a second pixel, and N is equal to a high addressability characteristic.

9. The system as claimed in claim 6, wherein said error means comprises:

first means for calculating a desired output;

second means for calculating a plurality of possible actual outputs; and

third means for calculating the plurality of possible error values, each possible error value being equal to the desired output minus a possible actual output.

10. The system as claimed in claim 6, further comprising:

screening means for screening the grey level value with a predetermined screen prior to conversion by said conversion means.

11. A method of generating an error from a threshold process, comprising the steps of:

(a) thresholding a plurality of interpolated subpixel values associated with a pixel;

(b) generating a plurality of possible error values in parallel with the thresholding carried out by said step (a); and

(c) selecting one of the plurality of possible error values based on a number of interpolated subpixels values exceeding a threshold value determined in said step (a).

12. The method as claimed in claim 11, further comprising the step of:

(d) diffusing the selected error value to grey level values of pixels adjacent to the pixel being thresholded.

13. The method as claimed in claim 11, further comprising the steps of:

(d) converting a grey level value of a pixel to a predetermined number of interpolated subpixel values; and

(e) screening the grey level value with a predetermined screen prior to the execution of said step (d).

14. A system for generating an error from a threshold process, comprising:

threshold means for thresholding a plurality of interpolated subpixel values associated with a pixel and for determining a number of interpolated subpixels values which exceed a threshold value;

error means, operatively connected in parallel with said threshold means, for generating a plurality of possible error values; and

selecting means, operatively connected to said error means and said threshold means, for selecting one of the plurality of possible error values based on the number of interpolated subpixels values exceeding the threshold value determined by said threshold means.

15. The system as claimed in claim 14, further comprising:

diffusing means for diffusing the selected error value to grey level values of pixels adjacent to the pixel being thresholded.

16. The system as claimed in claim 14, further comprising:

converting means for converting a grey level value of a pixel to a predetermined number of interpolated subpixel values; and

screening means for screening the grey level value with a predetermined screen prior to converting by said converting means.

17. A printing system for rendering marks on a recording medium, comprising:

receiving means for receiving a grey level signal corresponding to a pixel;

interpolation means for converting the grey level value of a pixel to a predetermined number of interpolated subpixel values;

binarization means for binarizing the converted grey level signal so as to output a binary signal and for determining a number of interpolated subpixel values which exceed a threshold value;

error means, operatively connected in parallel with said interpolation means and said binarization means, for generating a plurality of possible error values; and

selecting means, operatively connected to said error means and said binarization means, for selecting one of the plurality of possible error values based on the number of interpolated subpixel values exceeding a threshold value determined by said binarization means;

diffusing means for diffusing the selected error value to grey level signals corresponding to pixels adjacent to the pixel being binarized; and

rendering means for converting the binary signal into a mark on the recording medium.