Facsimile and static presentation processing – Static presentation processing – Attribute control
Reexamination Certificate
1998-11-02
2002-03-12
Lee, Thomas D. (Department: 2724)
Facsimile and static presentation processing
Static presentation processing
Attribute control
C382S252000
Reexamination Certificate
active
06356362
ABSTRACT:
BACKGROUND OF THE INVENTION
This application is being filed with a microfiche appendix of computer program listings consisting of one (1) fiche having 42 frames.
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
FIELD OF THE INVENTION
The present invention relates to halftoning by error diffusion, enhanced so as to reduce the presence of structural artifacts in the halftoned output while avoiding an artificial increase in halftoning image noise. Specifically, error diffusion according to the invention divides the input gray level intensity range into different segments for purposes of both thresholding and error diffusion. Different error diffusion threshold masks are applied for each respective segment, and different error diffusion weights are applied for each respective segment, with a decision being made as to whether or not to apply a different threshold mask being based on the local image gradient of the image.
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 multi-level data such as 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 proceeds in accordance with the following steps. First, a pixel in the continuous tone image is compared against a threshold (or ranges of thresholds for an output device with several levels) so as to determine what output value should be printed by the image output device. For example, in the case of a binary printer (meaning a printer that outputs at each pixel either a dot or an absence of a dot), the threshold may be ½ of the intensity range, with a pixel being printed if the continuous tone value exceeds ½ and with no pixel being printed if the continuous tone value does not exceed ½. Then, the error between the continuous tone input and the actual output value is calculated. This error is diffused to adjacent pixels using predetermined weighting coefficients, so that predesignated proportions of the error are added to the original image value of adjacent pixels. Processing then proceeds with another pixel in a predetermined scan direction. 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 value plus any accumulated errors.
Because of the exceedingly good image output obtained from error diffusion halftoning, a tremendous amount of effort has been expended on variations of the basic Floyd Stucki Steinberg technique so as to yield images of improved quality. Thus, various researchers have proposed changes to thresholding, changes to error diffusion coefficients, and changes in scan patterns, so as to improve error diffusion output.
Despite the amount of research aimed at error diffusion, there are several lingering problems. One of these problems concerns the formation of artifacts in the halftoned output. These artifacts form when error diffusion leads to repetitive output. Repetitive output can cause worm-like structural artifacts to appear in the halftoned output, particularly in areas of highlights such as extremely light or dark areas of an image.
FIG. 1
, for example, is the output
10
from conventional error diffusion halftoning, for each of 24 gray patches representing the first 24 out of 256 continuous tone gray levels. As seen in
FIG. 1
at extremely light gray level highlights, repetitive output has caused worm-like artifacts such as those at
11
and
12
.
Repetitive output can also cause regular patterns such as a checkerboard pattern to appear in the output. For example,
FIG. 2
is the output of conventional error diffusion halftoning for a continuous tone gray wedge that varies from full dark gray (or black) to full light gray (or white). As seen at 50% gray, the halftoned output
16
has a regularized checkerboard artifact caused by repetitive output. The same artifact can be seen to a lesser degree at 25% gray and 75% gray.
Both kinds of structural artifacts are visually distracting and detract from the overall quality of the image. Moreover, in connection with color printing, the existence of regular patterns such as a checkerboard pattern can, when color components are overlaid, result in severe color shifts which manifest themselves as discolored halos of color around solid or gradually varying color regions. These structural artifacts manifest themselves in particularly displeasing ways at intensity values corresponding to integral fractions of the intensity range. Thus, a severe structural artifact is created at a intensity value of ½ (i.e., 50% gray), with structural artifacts of lesser visibility being observed at ⅓, ⅔, ¼, ¾, ⅕, ⅖, ⅗, etc. (i.e., integral fractions) of the intensity range.
The inventor of this application has previously proposed one technique for reducing the existence of artifacts. Thus, in U.S. Pat. No. 5,737,453, “Enhanced Error-Diffusion Method For Color Or Black-And-White Reproduction”, the inventor herein proposed a technique for reducing halftoning artifacts by adjusting the threshold used in the halftoning decision, and by adjusting the coefficients of weights used to diffuse error. The technique described therein produced significantly reduced structural artifacts through a process that can inaccurately be conceptualized as introducing noise into the thresholding and the error diffusion process.
SUMMARY OF THE INVENTION
The inventor has since recognized that improved performance can be obtained by adjusting the amount of noise introduced into the thresholding and error diffusion process based on the amount of higher frequency spatial characteristics of the input image, such that when an input image naturally possesses a fair degree of noise (as is often the case when the input image is a natural image rather than a computer-generated image), there is less reason to introduce additional noise into the halftoning process.
It is an object of the invention to capitalize on the inventor's recognition that certain images need lesser amounts of noise injected into the halftoning and error diffusion process, by providing improved error diffusion halftoning.
According to one aspect of the invention, plural threshold masks are provided for use during error diffusion processing. Each thresholding mask has only a limited number of values, such as three values, with two of the values being centered around a central value, and with each different one of the plural threshold masks being provided for a different segment of the input intensity range. Preferably, a separate threshold mask is provided for each and every input intensity value. The spread of values in each threshold mask varies based on its corresponding intensity level. The spread increases at each intensity range corresponding to formation of artifacts, and results, for example, in a large spread at ½ of the intensity range, and correspondingly smaller spreads at ⅓, ¼, ⅕, etc. of the intensity range. At intervening non-integral fractions of the intensity range, the spread is reduced. Preferably, the spread of each intensity mask is derived empirically, based on the input/output characteristi
Canon Kabushiki Kaisha
Fitzpatrick ,Cella, Harper & Scinto
LandOfFree
Halftoning by enhanced error diffusion 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 by enhanced error diffusion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Halftoning by enhanced error diffusion will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2852426