Coupled-color error diffusion

• US 5,210,602 A
• Filed: 02/25/1991
• Issued: 05/11/1993
• Est. Priority Date: 02/25/1991
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Mintzer, Frederick C.
• Primary Examiner(s): Coles, Sr., Edward L.
• Assistant Examiner(s): LAM, CHI
• Application Number:
  US07/660,776
• Time in Patent Office: 806 Days
• Field of Search: 358/80, 358/455, 358/456, 358/457, 358/458, 358/465, 358/466, 358/78, 358/447, 382/54, 382/56, 382/50, 382/52
• US Class Current: 358/518
• CPC Class Codes: H04N 1/52 Circuits or arrangements for halftone screening
• CPC Class Codes: H04N 1/644 using a reduced set of representative colours, e.g. each representing a particular range in a colour space

Abstract

A system and method for improving the quality of the output of a full-color image on a reproduction device, such as a display on a monitor or printout from a printer, that only consists of a small number of colors in comparison to the number of colors represented by the input signals. The disclosure involves specifying a new quantization method for multi-color images, rendered with orthogonal or separable color image palettes, that takes advantage of the calculations done by error diffusion. Accordingly, the image input signals are processed using the quantization error generated by one color component of a given pixel to influence the quantization of subsequent color components of the same pixel, and in such a way that the color image, so rendered, appears less grainy.

Claims

1. A computerized method for producing an improved quality output representation of full-color input images on devices that produce a comparatively small number of possible output colors, by processing the signals representing the input pixels of the color image, in order, comprising the steps of:

providing a source for a set of output signals corresponding to the possible output-pixel values for the output colors;

receiving input signals representing at least two color components of the input pixels at each pixel position of the color image;

choosing an initial pixel position among said pixel positions and selecting, in accordance with said input signals at said initial position, output-pixel values from among the possible output pixel-values for each of the color components, and providing signals indicative of said selected output-pixel values to said output source;

developing signals indicative of diffused errors for each of the color components at each pixel position following said initial pixel position;

summing said received input signals and said diffused error signals to produce signals indicative of respective modified-pixel values for each of the color components at said each pixel position;

selecting, in accordance with said signals indicative of the respective modified-pixel values, output-pixel values from among the possible output pixel-values for each of the color components at said each pixel position, and providing signals indicative of said selected output-pixel values to said output source;

determining the quantization errors for each of said color components as the difference between the modified-pixel value for a color component and the selected output-pixel value for said color component, and producing signals indicative of the quantization errors for each of the color components at said each pixel position; and

adding, at said each pixel position, the products of respective constants and the quantization errors of each of the preceding color components at the respective pixel position to the respective modified-pixel value for each color component at the respective position, prior to said selecting of the output-pixel values, such that said signals indicative of the respective modified-pixel values are modified by preceding color component quantization errors and effect the selection of the respective signals indicative of said selected output-pixel values provided to said output source.

2. A method as in claim 1 further comprising, beginning with the first pixel position following said initial pixel position, incrementing the diffused errors at pixel positions not yet processed, by the steps of:

incrementing the diffused error for said first color component at each such pixel position by an amount computed from the product of one of a first set of coefficients and said quantization error for said first color component at said first pixel position;

incrementing the diffused error for said second color component at each such pixel position by an amount computed from the product of one of a second set of coefficients and said quantization error for said second color component at said first pixel position;

incrementing the diffused error for a next color component at each such pixel position by an amount computed from the product of one of a third set of coefficients and said quantization error for said next color components at said first pixel position; and

incrementing the diffused error for further color components at each such pixel position by an amount computed from the product of one of a respective set of coefficients and the respective quantization error for the respective further color component at said first pixel position.

3. A method as in claim 2 further comprising generating the values for said sets of coefficients used in incrementing said diffused errors, comprising the steps of:

generating random numbers; and

computing the products of said generated random numbers and respectively selected constants from respective sets of constants and generating output signals indicative of the values of said products as the values for said sets of coefficients.

4. A method as in claim 3 wherein said sets of coefficients are regenerated after the processing of each pixel.

5. A method as in claim 1 further comprising the step of setting the diffused errors for each of the color components at each pixel position equal to zero, prior to processing the signals representing the input pixels of the color image.

6. Apparatus for producing an improved quality output representation of full-color input images on devices that produce a comparatively small number of possible output colors, by processing the signals representing the input pixels of the color image, in order, comprising:

output means for providing a set of output signals corresponding to the possible output-pixel values for the output colors;

means for receiving input signals representing at least two color components of the input pixels at each pixel position of the color image;

error diffusion means for providing signals indicative of diffused errors for each of the color components at each pixel position with respect to the color components at a selected initial pixel position;

first summing means for summing said received input signals and said diffused erro signals to produce signals indicative of respective modified-pixel values for each of the color components at said each pixel position;

quantizing means, responsive to said signals indicative of the respective modified-pixel values, for selecting output-pixel values from amoung the possible output pixel-values for each of the color components at said each pixel position, and providing signals indicative of said selected output-pixel values to said output means;

second summing means, responsive to the difference between the modified-pixel value for a color component and the selected output-pixel value for said color component, for producing signals indicative of the quantization errors for each of the colors components at said each pixel position; and

third summing means, connected to said quantizing means and responsive to said quantization error signals, for adding, at said each pixel position, the product of respective constants and the quantization errors of each of the preceding color components at the respective pixel position to the respective modified-pixel value for each color component at the respective position, prior to the providing of said signals indicative of the respective modified-pixel values to said quantizing means, and providing signals indicative of the results of said adding to said quantizing means.

7. Apparatus as in claim 6 wherein said quantizing means comprises a look-up-table.

8. Apparatus as in claim 6 further comprising means for setting the diffused errors for each of the color components at each pixel position equal to zero, prior to processing the signals representing the input pixels of the color image.

9. Apparatus as in claim 6 further comprising means, responsive to said selecting of output-pixel values by said quantizing means at a first pixel position following said initial pixel position, for incrementing the diffused errors at pixel positions not yet processed, by the steps of:

incrementing the diffused error for said first color component at each such pixel position by an amount computed from the product of one of a first set of coeffecients and said quantization error for said first color component at said first pixel position;

incrementing the diffused error for said second color component at each such pixel position by an amount computed from the product of one of a second set of coefficients and said quantization error for said second color component at said first pixel position;

incrementing the diffused error for a next color component at each such pixel position by an amount computed from the product of one of a third set of coefficients and said quantization error for said next color components at said first pixel position; and

incrementing the diffused error for further color components at each such pixel postiion by an amount computed from the product of one of a respective set of coefficients and the respective quantization error for the respective further color component at said first pixel position; and

means for activating said output means to provide output signals from said set of output signals corresponding to the selected output-pixel values for the color components at each pixel postion.

10. Apparatus as in claim 9 further comprising means for generating the values for said sets of coefficients used in said error diffusion means, comprising:

means for generating random numbers;

means for computing the products of said generated random numbers and respectively selected constants from respective sets of constants and generating output signals indicative of the values of said products as the values for said sets of coefficients.

11. Apparatus as in claim 10 wherein said sets of coefficients are generated after the processing of each pixel.

12. A computerized method for producing improved quality output representations of full-color images on devices that produce a comparatively small number of output colors, by processing the signals representing the input pixels of the color image, in order, according to the steps comprising:

providing a source of output signals corresponding to the possible output-pixel values for the output colors;

receiving input signals representing at least two color components of the input pixels at each pixel position of the color image;

choosing an initial pixel position amoung said pixel positions and selecting, in accordance with said input signals at said initial position, output-pixel values from amoung the possible output pixel-values for each of the color components, and providing signals indicative of said selected output-pixel values to said output source;

computing, at the first pixel position following said initial pixel position, the modified-pixel values of said color components;

selecting the output-pixel value for the first color component from amoung the possible output-pixel values near the modified-pixel value for the first color component;

computing the quantization error for the first color component as the difference between said modified-pixel value for the first color component and said selected output-pixel value for the first color component;

selecting the output-pixel value for the second color component from amoung the possible output-pixel values near the sum of the modified-pixel value of the second color component and the product of a first constant and said quantization error for the first color component;

computing the quantization error for the second color component as the difference between said modified-pixel value for the second color component and said output-pixel value for the second color component;

selecting the output-pixel value for a next color component from amoung the possible output-pixel values near the sum of the modified-pixel value for said next color component and the product of a second constant and said quantization error for the first color component and the product of a third constant and said quantization error for the second color component;

computing the quantization error for said next color component as the difference between said modified-pixel value and said output-pixel value of said next color component; and

selecting ouput pixel values for futher color components using the repective modified-pixel value summed with the products of successive constants and the repective quantization errors of said first color component and successive preceding color components, with the respective quantization errors being computed as the difference between the modified-pixel value and the output-pixel value of the respective color component; and

incrementing, at pixel positions not yet processed, the diffused error for said first color component at each such pixel position by an amount computed from the product of one of a first set of coefficients and said quantization error for said first color component at said first pixel position, incrementing the diffused error for said second color component at each such pixel position by an amount computed from the product of one of a second set of coefficients and said quantization error for said second color component at said first pixel position, and incrementing the diffused error for a next color component at each such pixel position by an amount computed from the product of one of a third set of coefficients and said quantization error for said next color components at said first pixel position;

incrementing the diffused error for further color components at each such pixel position by an amount computed from the product of one of a respective set of coefficients and the respective quantization error for the respective further color component at said first pixel position;

processing the signals representing the input pixels at the remaining pixel positions by repreating the computing, selecting, and incrementing steps in the same manner as the processing of the input pixel signals at said first pixel position; and

producing output corresponding to the selected output-pixel values for the output colors at each pixel position to reproduce the color image.

13. A method as in claim 12 further comprising generating the values for said sets of coefficients used in incrementing said diffused erros, by the steps of:

generating random numbers; and

computing the products of said generated random numbers and respectively selected constants from respective sets of constants and generating output signals indicative of the values of said products as the values for said sets of coefficients.

14. A method as in claim 13 wherein said sets of coefficients are regenerated after the processing of each pixel.

15. A method as in claim 12 further comprising the step of setting the diffused errors for each of the color components at each pixel position equal to zero, prior to processing the signals representing the input pixels of the color image, in order.

16. Apparatus for producing an improved quality output representation of full-color input images on devices that produce a comparatively small number of possible output colors, by processing the signals representing the input pixels of the color image, in order, comprising:

means for providing a set of output signals corresponding to the possible output-pixel values for the output colors;

means for receiving input signals representing at least two color components of the input pixels at each pixel position of the color image;

means for choosing an initial pixel position among said pixel positions and selecting, in accordance with said input signals at said initial position, output-pixel values from among the possible output pixel-values for each of the color components, and providing signals indicative of said selected output-pixel values to said means for providing a set of corresponding output signals;

means for processing said received input signals to produce modified-pixel values for each of the color components at each pixel position following said initial pixel position, wherein a modified-pixel value is the sum of the input-pixel value of a color component of an input signal and the diffused error for said color component;

means for selecting output-pixel values from among the possible output pixel-values for each of the color components at said each pixel position, using said modified-pixel values and quantization errors, wherein a quantization error is the difference between the modified-pixel value for a color component and the output-pixel value for said color component, by the steps of;

selecting an output-pixel value for the first color component at a given pixel position as one of the possible output-pixel values near the modified-pixel value for said first color component;

selecting an output-pixel value for the second color component at the given position as one of the possible output-pixel values near the sum of the modified-pixel value for said second color component and the product of a first constant and the quantization error for said first color component;

selecting an output-pixel value for the next color component at the given position as one of the possible output-pixel values near the sum of the modified-pixel value for said next color component and the product of a second constant and the quantization error for said first color component and the product of a third constant and the quantization error for said second color component; and

selecting output-pixel values for further color components at the given position as one of the possible output-pixel values near the sum of the modified-pixel value for the respective color component and the products of respective constants and the quantization errors for all of the preceding color components; and

means, responsive to said selecting of output-pixel values by said selecting means at the first pixel position following said initial pixel position, for incrementing the diffused errors at pixel positions not yet processed, by the steps of;

incrementing the diffused error for said first color component at each such pixel position by an amount computed from the product of one of a first set of coefficients and said quantization error for said first color component at said first pixel position;

incrementing the diffused error for said second color component at each such pixel position by an amount computed from the product of one of a second set of coefficients and said quantization error for said second color component at said first pixel position;

incrementing the diffused error for a next color component at each such pixel position by an amount computed from the product of one of a third set of coefficients and said quantization error for said next color components at said first pixel position; and

incrementing the diffused error for further color components at each such pixel position by an amount computed from the product of one of a respective set of coefficients and the respective quantization error for the respective further color component at said first pixel position;

means for repeatedly activating said processing, selecting, and incrementing means to produce a set of output signals corresponding to the selected output-pixel values for the color components at each of the pixel positions remaining after said initial pixel position; and

means for activating said output signal providing means to provide output signals from said set of output signals corresponding to the selected output-pixel values for the color components at each remaining pixel position.

17. Apparatus as in claim 16 further comprising means for generating the values for said sets of coefficients used in said error diffusion means, comprising:

means for generating random numbers;

means for computing the products of said generated random numbers and respectively selected constants from respective sets of constants and generating output signals indicative of the values of said products as the values for said sets of coefficients.

18. Apparatus as in claim 17 wherein said sets of coefficients are generated after the processing of each pixel.