Halftoning with error feedback and image dependent enhancement

• US 5,243,443 A
• Filed: 12/06/1991
• Issued: 09/07/1993
• Est. Priority Date: 12/06/1991
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Eschbach, Reiner
• Primary Examiner(s): Coles, Sr., Edward L.
• Assistant Examiner(s): Rogers, Scott A.
• Application Number:
  US07/802,809
• Time in Patent Office: 641 Days
• Field of Search: 358/466, 358/455, 358/456, 358/465, 358/458, 358/460, 358/298, 382/50, 382/52, 359/447, 359/445
• 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 method and arrangement for quantizing gray level pixels using a combination of halftoning and error diffusion which initially determines a best fit halftone cell, and propagates halftoning error in order to maintain gray density, while reducing halftoning and error diffusion artifacts.

Claims

1. A method of quantizing pixel values in an image formed by a plurality of pixels, each pixel representing an optical density of the image at a location within the image, and having an original optical density value associated therewith selected from one of a set of `c` original optical density values that has a number of members larger than a desired output set of `d` optical density values, including the steps:

for each group of pixels to be quantized, determining an average gray level input value for the image over an area of a halftone cell including the pixels;

determining a screen sum that is the addition of a stored screen value for the pixels determined by a position of the pixel within the area of the halftone cell, and the pixel value to produce screened pixel values;

thresholding the screened pixel value with a value T to obtain output optical density values that are a member of the output set of `d` optical density values, and directing said values to an output;

determining from the thresholded pixel values an average gray output value for the image over the area of the halftone cell;

determining an error value, that is a difference between the average gray output value and the average gray input value;

storing a weighted portion of the error value for each of a set of halftone cells in an error distribution neighborhood;

updating an error buffer holding error terms to be added to unprocessed halftone cells in the image with the weighted error value;

determining an error sum that is the addition of an error term, and the average input gray level value,

comparing the error sum and the average gray output value; and

responsive to said comparison, adjusting value T so that the average gray level between of the input image and the output image are substantially equal.

2. A method of quantizing pixel values in an image formed by a plurality of pixels, each pixel representing an optical density of the image at a location within the image, and having an original optical density value associated therewith selected from one of a set of `c` original optical density values that has a number of members larger than a desired output set of `d` optical density values, including the steps:

for each group of pixels to be quantized, determining an average gray level input value for the image over an area of a halftone cell including the pixels;

determining a screen sum that is the addition of a stored screen value for the pixel determined by a position of the pixel within the area of the halftone cell, and the pixel value to produce a screened pixel value;

thresholding the screened pixel values with a value T to obtain an output optical density value that is a member of the output set of `d` optical density values, and directing said value to an output;

determining from the thresholded pixel values an average gray output value for the image over the area of the halftone cell;

modifying the average gray input value by an error term determined in quantizing pixels in at least one previous halftone cell to produce a modified gray input value;

determining an error value, that is a difference between the average gray output value and the modified average gray input value;

determining a weighted error value, that is a function of the error value, for each of a set of pixels in an error distribution neighborhood;

updating an error buffer holding error terms to be added to unprocessed halftone cells in the image with the weighted error value;

comparing the modified gray input value sum and the average gray output value; and

responsive to said comparison, adjusting value T so that the average gray level between of the input image and the output image are substantially equal.

3. A method of quantizing pixel values in an image formed by a plurality of pixels, each pixel representing an optical density of the image at a location within the image, and having an original optical density value associated therewith selected from one of a set of `c` original optical density values that has a number of members larger than a desired output set of `d` optical density values, including the steps:

thresholding an optical density value of each pixel having an original optical density value against at least one threshold value T, to obtain an optical density value that is a member of the output set of `d` optical density values;

for a set of pixels in the image forming a halftone cell determining a difference between an average input gray value of the image and an average gray output value of the thresholded image, and distributing a weighted portion of said difference to at least one unprocessed halftone cell;

comparing a sum of the average gray input level and a weighted portion of the difference determined for a previously processed halftone cell, with the average output gray level value for the cell, and dynamically varying said at least one threshold value T in accordance with the comparison, so that said input gray level value and said output gray level values are substantially equal.

4. A method of quantizing pixel values in an image formed by a plurality of pixels, each pixel representing an optical density of the image at a location within the image, and having an original optical density value associated therewith selected from one of a set of `c` original optical density values that has a number of members larger than a desired output set of `d` optical density values, including the steps:

thresholding an optical density value of each pixel having an original optical density value against at least one threshold value T, to obtain an optical density value that is a member of the output set of `d` optical density values;

for a set of pixels in the image forming a halftone cell, determining an error that is the difference between an average input gray value of the image modified by the addition of a weighted error portion from at least one previously processed halftone cell, and an average gray output value of the thresholded image, and distributing a weighted portion of said error to at least one unprocessed halftone cell;

comparing the modified average gray input level, with the average output gray level value for the cell, and dynamically varying said at least one threshold value T in accordance with the comparison, so that said input gray level value and said output gray level values are substantially equal.

5. An arrangement for quantizing pixel values in an image formed by a plurality of pixels, each pixel having a value representing an optical density of the image at a location within the image, and having an original optical density value associated therewith selected from one of a set of `c` original optical density values that has a number of members larger than a desired output set of `d` optical density values, comprising:

a source of pixels having one of `c` original optical density values;

an adder for summing a stored screen value and a pixel value of a pixel to be quantized, said screen value received from a screen memory and determined by a position of the pixel to be quantized within the area of a halftone cell, to produce a screened pixel value;

an adjustable thresholding means for thresholding the screened pixel value with a value T to obtain an output optical density value that is a member of the output set of `d` optical density values;

an image data output, directing pixels having an output optical density value that is one of `d` optical density values out of the arrangement;

an input integrator, determining an average gray input value for the image over an area of the halftone cell including the pixel to be processed;

an output integrator, determining from the output of the adjustable thresholding means, an average gray level value for output image data, over an area of the halftone cell including the pixel;

a gray error comparator, for comparing the average gray output value of the image and the average gray input value, and producing a gray error that is the difference therebetween;

a gray error memory, storing gray error terms, each gray error term a weighted portion of the determined gray error, to be applied to each halftone cell in a predetermined neighborhood thereof; and

an adder for summing a gray error term stored in the gray error term memory and the average gray input value, to produce a modified average gray input value; and

means for adjusting T, having as inputs the modified average gray input value and the output gray value, so that the average gray input value and the average gray output value are substantially equal.

6. An arrangement for quantizing pixel values in an image formed by a plurality of pixels, each pixel representing an optical density of the image at a location within the image, and having an original optical density value associated therewith selected from one of a set of `c` original optical density values that has a number of members larger than a desired output set of `d` optical density values, comprising:

a source of image data including pixels having an original optical density value that is one of `c` original optical density values;

an adder for summing a stored screen value and a pixel value of a pixel to be quantized, said screen value received from a screen memory and determined by a position of the pixel to be quantized within the area of a halftone cell, to produce a screened pixel value;

an adjustable thresholding means for thresholding the screened pixel value with a value T to obtain an output optical density value that is a member of the output set of `d` optical density values;

an image data output, directing pixels having an output optical density value that is one of `d` optical density values out of the arrangement;

an input integrator, determining an average gray input value for the image over an area of the halftone cell including the pixel to be processed;

an adder for summing a gray error term stored in a gray error term memory and the average gray input value, to produce a modified average gray input value; and

an output integrator, determining from the output of the adjustable thresholding means, an average gray level value for output image data, over an area of the halftone cell including the pixel;

a gray error comparator, for comparing the average gray output value of the image and the modified average gray input value, and producing a gray error that is the difference therebetween;

a gray error term memory, storing gray error terms, each gray error term a weighted portion of the determined gray error, to be applied to each halftone cell in a predetermined neighborhood thereof; and

means for adjusting T so that the modified average gray input value and the average gray output value are substantially equal.

7. An arrangement for quantizing pixel values in an image formed by a plurality of pixels, each pixel representing an optical density of the image at a location within the image, and having an original optical density value associated therewith selected from one of a set of `c` original optical density values that has a number of members larger than a desired output set of `d` optical density values, comprising:

means for thresholding an optical density value of each pixel having an original optical density value against at least one threshold value T, to obtain an optical density value that is a member of the output set of `d` optical density values;

means for determining, for a set of pixels in the image forming a halftone cell, a difference between an average input gray value of the image and an average gray output value of the thresholded image, and distributing a weighted portion of said difference to at least one unprocessed halftone cell;

means for comparing the sum of the average gray input level and the determined difference, with the average output gray level value for the cell, and dynamically varying said at least one threshold value T in accordance with the comparison, so that said input gray level value and said output gray level values are substantially equal.

8. An arrangement for quantizing pixel values in an image formed by a plurality of pixels, each pixel representing an optical density of the image at a location within the image, and having an original optical density value associated therewith selected from one of a set of `c` original optical density values that has a number of members larger than a desired output set of `d` optical density values, comprising:

means for thresholding an optical density value of each pixel having an original optical density value against at least one threshold value T, to obtain an optical density value that is a member of the output set of `d` optical density values;

means for determining, for a set of pixels in the image forming a halftone cell, a difference between an average input gray value of the image modified by the addition of an error term from at least one previously processed halftone cell, and an average gray output value of the thresholded image, and distributing a weighted portion of said difference to at least one unprocessed halftone cell;

means for comparing the sum of the average gray input level and the determined difference, with the average output gray level value for the cell, and dynamically varying said at least one threshold value T in accordance with the comparison, so that said input gray level value and said output gray level values are substantially equal.

9. A method of quantizing pixel values in an image formed by a plurality of pixels, each pixel representing an optical density of the image at a location within the image, and having an original optical density value associated therewith selected from one of a set of `c` original optical density values that has a number of members larger than a desired output set of `d` optical density values, including steps:

receiving input pixel values for the image;

averaging pixels values in an area corresponding to a halftone cell in the image, to produce an average gray input value for the halftone cell;

adding a gray error term stored in an error term buffer from at least one previously processed halftone cell, to the average gray input value, and storing the modified average gray input value;

calculating an integer part and fractional part of the modified gray input value, where the integer part is the modified average gray input value in integer pixel units, while the fractional part is the difference between the integer part and the modified gray input value;

storing to the error term buffer a set of gray error terms, each gray error term a weighted portion of the fractional part of the modified gray input value, to be applied to each halftone cell in a predetermined neighborhood thereof;

determining a screen sum that is the addition of an input pixel value and a stored screen value for the pixel value determined by a position of the pixel within the area of the halftone cell;

for the cell, arranging the screen sums in order of value;

beginning with the first screen sum, setting a number of pixels represented by the screen sums in the halftone cell to a selected state, the number of pixels set to the selected state equal to the integer calculated integer part.