Combining error diffusion, dithering and over-modulation for...

Details Combining error diffusion, dithering and over-modulation for... Combining error diffusion, dithering and over-modulation for...

1998-12-11

2001-08-07

Rogers, Scott (Department: 2624)

Facsimile and static presentation processing

Static presentation processing

Attribute control

C358S451000, C358S451000

Reexamination Certificate

active

06271936

ABSTRACT:

FIELD OF THE INVENTION
This present invention relates to digital image processing and more particularly to a method for digitally multitoning a continuous-tone image using error diffusion, dithering and over-modulation methods.
BACKGROUND OF THE INVENTION
Digital halftoning is a technique employing digital image processing to produce halftone output image from a continuous-tone image. In the digital halftoning technique, a continuous-tone image is sampled, for example, with a scanner and the samples are digitized and stored in a computer. The digitized samples (or “pixels”) consist of discrete values typically ranging from 0 to 255. To reproduce this image on an output device capable of printing dots of one gray level (e.g. black), it is necessary to convert the continuous-tone image to a binary output image using some form of halftoning techniques. Halftoning methods rely on the fact that an observer's eye will spatially average over some local area of the image so that intermediate gray levels can be created by turning some of the pixels “on” and some of the pixels “off” in some small region. The fraction of the pixels that are turned on will determine the apparent gray level. Common prior art methods of digital halftoning include error diffusion and dithering.
Error diffusion is an adaptive algorithm that produces patterns with different spatial frequency content depending on the input image value.
FIG. 1
shows a block diagram describing a basic error diffusion technique disclosed in “An adaptive algorithm for spatial greyscale,”
Proceedings of the Society for Information Display
, vol. 17, no. 2, pp. 75-77, 1976, by R. W. Floyd and L. Steinberg. For purpose of illustration it will be assumed that the continuous-tone input values span the range from 0 to 255. The continuous-tone input value for the current input pixel is thresholded
10
to form the output value. The threshold operator will return a 0 for any continuous-tone input value below the threshold, and a 255 for any continuous-tone input value above the threshold. A difference signal generator
12
receives the continuous-tone input value and the output value, and produces a difference signal representing the error introduced by the thresholding process. The difference signal is multiplied by a series of error feedback weights using a weighted error generator
14
, and is provided to an adder
16
which adds the weighted difference signal to the continuous-tone input values of the nearby pixels that have yet to be processed to form modified continuous-tone input values. The propagation of the errors made during the thresholding process to the nearby pixels insures that the arithmetic mean of the pixel values is preserved over a local image region.
FIG. 2
illustrates a typical set of error feedback weights
14
which can be used to distribute the errors to the nearby pixels. The halftone output from error diffusion is considered to be of high quality generally, since most of the halftone noise is distributed in a high spatial frequency band where human visual sensitivity is relatively low. An artifact that is typically associated with error diffusion halftoning technique is known as “worms.” Worms are formed when the black or white output pixels appear to string together in an area that should be otherwise uniform. Worm artifacts can be clearly seen in several areas of the output gray wedge (c) in
FIG. 4
from the error diffusion halftoning technique, such as the light and dark ends of the gray wedge (c). Several of these worm artifacts are labelled as
40
A-C.
Compared to the error diffusion technique, halftoning with a dithering technique is simpler in implementation, which is shown in FIG.
3
. In this case, a periodic dither signal d(x′, y′) is determined by modularly addressing
30
,
32
a dithering matrix
34
with the row and column addresses of the input pixels. The size of the dither matrix in this example is M
x
by M
y
. The periodic dither signal is then provided to an adder
36
which adds the periodic dither signal to the input pixel value I(x,y) to form modified continuous-tone input values. The modified continuous-tone input pixel is then thresholded
38
to form the output value. The threshold operator will return a 0 for any modified continuous-tone input value below the threshold, and a 255 for any modified continuous-tone input value above the threshold. The modulo operations
30
,
32
have the effect of tiling the dither matrix
34
across the image in a repeating pattern. Obviously, the arrangement of the values stored in the dither matrix will determine the output halftone patterns. Commonly used dither matrices are the clustered-dot dither matrices and the “Bayer matrix”. However, due to the ordered structure imposed by these two matrices (thus called “ordered dithering”), the resulting halftone output normally contains distinct textures that are highly visible. Recent developments in the dithering technique have been concentrated on “blue-noise dithering” (for example see “Design of minimum visual modulation halftone patterns,”
IEEE Trans. Syst. Man. Cybern
. SMC-21(1), pp. 33-38, 1991, by J. R. Sullivan, et al.; “Digital halftoning technique using a blue-noise mask,”
Journal of Optical Society of America A
9(11), pp. 1920-1929, 1992, by K. J. Parker, et al.; “Methods for generating blue-noise dither matrices for digital halftoning,”
Journal of Electronic Imaging
, vol. 6, pp. 208-230, April 1997, by K. E. Spaulding, et al.; and, “Stochastic screen halftoning for electronic devices,”
Journal of Visual Communication and Image Representation
, vol. 8, pp. 423-440, December 1997, by Q. Yu and K. J. Parker), where blue-noise dither matrices are designed that minimize the low frequency content and maximize the high frequency content in the halftone patterns, thus producing similar results as error diffusion halftone patterns. The blue-noise dither matrices are typically relatively large in size, and can be seamlessly tiled to cover the image due to the built-in wrap-around properties. The major artifact associated with blue-noise dithering is increased graininess at mid-tone gray levels, relative to that associated with error diffusion. The graininess artifact can be seen in the gray wedge (b) in
FIG. 4
, which is labelled as
42
.
Recently, printing devices with multilevel output (N output levels, where N>2) capability have been brought to the market to achieve photographic image quality. Both dithering and error diffusion techniques can be generalized for these devices, in which case halftoning becomes multitoning. For multilevel dithering, the process is equivalent to the binary implementation in
FIG. 3
, except that the threshold operation
38
is replaced by a quantization operation. As before, the periodic dither signal is added to the input pixel value. The quantizer then associates one of the allowable output levels with each of the possible values of the modulated input pixel value. Similarly, for multilevel error diffusion, the process is equivalent to the binary implementation in
FIG. 1
except that the thresholding
10
step is replaced with a quantization step.
FIG. 4
shows a continuous-tone gray wedge (a) along with outputs from binary blue-noise dithering (b), binary error diffusion (c), multilevel blue- noise dithering (d) and multilevel error diffusion (e). In the multitoning cases (d and e), the total number of output levels (N) is 4. It can be observed that overall image quality is improved while texture visibility is reduced from blue-noise dithering to error diffusion as well as from halftoning to multitoning. Also, the typical artifacts
40
A-C,
42
associated with both error diffusion and blue-noise dithering are clearly visible.
It can be seen from
FIG. 4
that both the multilevel error diffusion and multilevel dithering halftoning algorithm produce distinct contours near the 4 pure printing states (or “boundaries”, or output gray levels). Additionally both of these two approaches result in distinct texture transitions near the 2 inte

Affiliated with

Also associated with

Rating

Combining error diffusion, dithering and over-modulation for... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Combining error diffusion, dithering and over-modulation for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combining error diffusion, dithering and over-modulation for... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2456668