Halftoning with changeable error diffusion weights

Details Halftoning with changeable error diffusion weights Halftoning with changeable error diffusion weights

1998-02-05

2001-01-09

Coles, Edward L. (Department: 2722)

Facsimile and static presentation processing

Static presentation processing

Attribute control

C358S001100, C358S451000, C358S451000, C382S251000, C382S252000, C382S274000, C382S275000

Reexamination Certificate

active

06172768

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to halftoning by error diffusion, in which error diffusion weights are changeable and preferably depend on output error or on image source data plus accumulated error.
2. Description of the Related Art
Error diffusion halftoning, as generally described in the seminal works by Floyd, Steinberg and Stucki, has become one of the most popular techniques for producing halftoned image output based on a continuous tone image input. Particularly in connection with computerized images, where each input pixel is represented by an 8-bit gray scale or 24-bit color value, error diffusion halftoning has been found to yield pleasing results in images printed with binary or limited level output printers, such as color ink jet printers and the like. Error diffusion tends to enhance edge sharpness and further tends to preserve fine image detail while yielding an overall pleasing image.
Generally speaking, error diffusion halftoning proceeds in accordance with the following steps. First, image data for a target pixel in the continuous tone image is compared against a threshold (or, in the case of multi-level output devices, against a range of thresholds), so as to determine what output value the image output device should print for the target pixel. For example, in the case of a binary printer (meaning a printer that outputs at each pixel location either a dot or an absence of a dot), the threshold may be one half of the density range, with a pixel being printed if the continuous tone value for the target pixel exceeds one half and with no pixel being printed if the continuous tone value does not exceed one half. Then, the error between the continuous tone input value and the actual output value is calculated. This error is sometimes called the “output error”. The output error is diffused to adjacent pixels using predetermined weighting coefficients, so that predesignated proportions of the output error are added to existing continuous tone image values at pixels adjacent the target pixel. Processing then proceeds with another target pixel in a predetermined scan pattern. When it comes time to threshold one of the adjacent pixels so as to determine whether or not to print a dot, the determination is based on the original continuous tone image value plus any accumulated errors.
One problem with error diffusion halftoning is the creation of artifacts in the printed image that tend to degrade overall printed image quality. Two kinds of artifacts have been identified: unexpected continuous dot lines that appear in highlight regions (such as at extremely low and extremely high density regions), and repetitive textures or patterns that appear at mid density regions. These artifacts are illustrated in more detail in connection with
FIGS. 1 and 2
.
In
FIG. 1
,
10
represents a printout of standard error diffusion halftoning of an 8×4 grid of patches, with each patch having a constant gray level that increases serially from patch to patch. The 8×4 grid of
FIG. 1
includes patches only in the low density gray region and does not include patches of darkness exceeding around ten percent gray. Continuous dot lines are readily apparent, for example, at 11 and 12. These continuous dot line patterns are displeasing to a viewer.
FIG. 2
illustrates a gray level wedge proceeding from a full black density level to a full white density level. At mid density levels, repetitive patterns or texture are readily apparent, such as illustrated at 16. These textures are displeasing to a viewer, and degrade overall printed image quality.
The creation and presence of these artifacts are well-documented, and have been subjected to significant study so as to reduce their appearance and improve overall image quality. One previously-proposed technique is to modify error diffusion weights based on the image input. Examples of such techniques are described in Ostromoukhov, European 808,055; and Eschbach, “Reduction Of Artifacts In Error Diffusion By Means Of Input-Dependent Weights”, Journal of Electronic Imaging, October, 1993, pages 352 through 358. Other known techniques, although not necessarily known to reduce artifacts, include techniques that dynamically modify the threshold against which the continuous tone image value plus accumulated error is compared, including modification based on image value, as described for example in Eschbach, “Error-Diffusion Algorithm With Edge Enhancement”, Journal of The Optical Society of America, December, 1991, pages 1844 through 1850.
Such techniques are different from the present invention, since in the invention error diffusion weights and/or thresholds are modified based on accumulated output error, or based on image source data and accumulated output error.
SUMMARY OF THE INVENTION
It is an object of the invention to reduce output artifacts in error diffusion halftoning, by modifying error diffusion weights and/or thresholds based on output error, or based on image data and accumulated output error. Preferably, a look-up table is provided which, based on output error or based on image source data plus its accumulated error, directly provides actual error values and/or threshold or output values for error diffusion halftoning.
Thus, in one aspect the invention is error diffusion halftoning of image data for a target pixel in which a halftone output value for the target pixel is determined based on a comparison between a threshold and the image data for the target pixel and accumulated error, and in which error between the halftone output value and the image data and accumulated error for the target pixel is diffused in predetermined proportions to pixels adjacent the target pixel. The predetermined proportions depend at least in part on the value of the error, or depend at least in part on the value of the image data and accumulated error for the target pixel. The threshold may also depend at least in part on the value of the error or on the value of the image data and accumulated error. Preferably, the error diffusion weights depend in a cyclic manner on output error, or on image data plus accumulated error. For example, the error diffusion weights can be selected so as to vary cyclically from a set of coefficients that is neutral, to a set of coefficients that favors error diffusion in a rightward direction, and thence to error diffusion coefficients that favor error diffusion in a lower left hand direction. If thresholds are allowed to very, they also preferably vary cyclically, but with a cycle that is different from that of the error diffusion weights.
Because the error diffusion weights and/or thresholds depend on output error, or on image data and accumulated error, formation of regular patterns, such as continuous dot lines in highlight regions and textures in mid tone regions, is greatly reduced.
In further aspects, the invention is error diffusion halftoning that obtains access to a look-up table that stores pre-calculated error diffusion amounts, with the pre-calculated error diffusion amounts being accessible from the look-up table based on input data and accumulated error. Error diffusion values in the look-up table are pre-calculated based on error diffusion coefficients that vary based at least in part on the image data and accumulated error. Preferably, variation is cyclical, for example, varying between neutral values and values that favor error diffusion in a rightward direction and values that favor error diffusion in a downward left direction. Error diffusion using the look-up table proceeds by determining a halftone output value for a target pixel based on a comparison between a threshold and image data and accumulated error for the target pixel. The look-up table is accessed using the image data and accumulated error so as to obtain error diffusion amounts. The error diffusion amounts are added to adjacent pixels. Preferably, the look-up table can also include the halftone output value, thereby avoiding the need for a direct comparison between a threshold and image

Affiliated with

Also associated with

Rating

Halftoning with changeable error diffusion weights does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Halftoning with changeable error diffusion weights, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Halftoning with changeable error diffusion weights will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2526413