Digital halftoning with error diffusion

Details Digital halftoning with error diffusion Digital halftoning with error diffusion

1995-05-05

2001-10-23

Grant, II, Jerome (Department: 2624)

Facsimile and static presentation processing

Facsimile

Specific signal processing circuitry

Reexamination Certificate

active

06307647

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to digital image processing and, more particularly, to digital halftoning using error diffusion.
BACKGROUND OF THE INVENTION
Digital halftoning converts continuous tone images from gray scale pixel values to a reduced number of pixel values. These smaller number of pixel values are utilized to convert the continuous tone images into images for use in a binary output device such as a binary printer, for example, through carefully arranging the position of printed dots produced by the binary printer. Halftoning may be applied to monochrome images or to a number of color planes of a color image.
Halftoning algorithms for producing patterns that are pleasing to the human eye can be categorized as either point or neighborhood algorithms according to the number of pixels from the input gray scale image required to calculate a single binary pixel output. In point algorithms, halftoning is accomplished by a comparison of the gray scaled image for a specific pixel against a halftone mask such as a Blue Noise mask or a Void and Cluster mask, for example, that is tiled across the image being scanned. For every point in the input image, a corresponding pixel of the output image is assigned a “1” or “0” depending on whether the value of the input pixel is larger than the value of the corresponding pixel in the halftone mask.
A gray scale, binary, printing process forms a black and white image by either placing a dot or not placing a dot of black ink at each printable pixel location. An input value of I=0 at a pixel location (x, y) represents the lightest printable color, white, which is produced by printing no dot at the location (x, y). An input value of I=255 at the pixel location (x, y) represents the darkest printable color, black, which is produced by printing a dot at the location (x, y).
Shades of gray other than white or black cannot be produced at the pixel location by this printing process since a dot is either printed or not printed at each location. Therefore, the shades of gray must be simulated by printing a pattern of dots over a wider area than just one pixel.
Accordingly, an input shade of gray having a value of I is produced over a selected area by printing a dot at each location of the selected area with a probability of I/255. On average, I dots out of every 255 locations are printed. If the selected area is too small, it may be impossible to place exactly on average I dots out of 255 locations over this area. Therefore, the shade of gray is not accurately reproduced but only approximated.
Table 1 represents an 8×8 square pixel mask.
TABLE 1
0
168
48
220
72
244
100
248
84
148
116
20
228
12
152
60
196
32
184
128
68
188
124
224
56
216
112
44
200
96
36
172
164
8
136
212
28
232
204
104
108
180
80
160
88
132
4
236
144
24
240
52
192
64
156
76
252
92
140
120
16
208
40
176
It should be noted that the threshold values in Table 1 are uniformly distributed with the threshold values spaced every four units from 0 to 252. The threshold values of Table 1 can be used to govern the probability of a dot being printed.
For example, if a gray level value of I=33 is to be produced over an entire 8×8 square pixel area with the threshold values given by Table 1, nine dots will be printed at the positions having threshold values of 0, 4, 8, 12, 16, 20, 24, 28, and 32. Therefore, the gray level value of I=33 is approximated by 9 dots out of 64 where 9/64 locations is approximately equal to 33/255. The nine dots are placed at the locations marked by X in Table 2. It is assumed that Table 2 was constructed so that this pattern of nine dots is a desirable arrangement of nine dots for a gray level value of I=33.
TABLE 2
X
X
X
X
X
X
X
X
X
Neighborhood algorithms such as error diffusion, for example, do not need a halftone mask. The halftoning technique of error diffusion is generally attributed to Robert Floyd and Louis Steinberg as set forth in “An Adaptive Algorithm for Spatial Gray Scale,” 1975
SID International Symposium, Digest of Technical Papers
, pp. 36-37. This algorithm is unlike a halftoning mask in that the decision to place or not to place a dot at the specific location (x, y) depends on the image values at other pixel locations.
If a black-and-white image having image values of I(x, y) is to be printed on a binary printer, assume that each pixel has associated with it a threshold value T which is invariant for x and y values. If I(x, y) equals only either 0 or 255, the image can be reproduced as intended since not printing a dot corresponds to printing a value of I=0 while printing a dot corresponds to printing a value of I=255.
The problem occurs when I(x, y) is not equal to 0 or 255 for some x and y location; this is usually the situation with items such as photographs, for example. In this situation, printing or not printing a dot causes there to be an error from the actual value of the input image. If a dot is placed at the position (x, y), an error equal to the amount of 255−I(x, y) is generated at the position (x, y). If a dot is not placed, an error equal to the amount I(x, y) is generated at the position (x, y).
The error diffusion algorithm calculates the error at the specific position as the result of quantization and diffuses this error to neighboring dots. If a dot is printed at the position (x, y), some amount of the error is subtracted from neighboring dots to decrease their probability of being printed to compensate for overprinting at the position (x, y). Similarly, if a dot is not printed at the position (x, y), some amount of the error is added to neighboring dots to increase their probability of being printed to compensate for underprinting at the position (x, y). The algorithm proposed by Floyd and Steinberg spreads {fraction (7/16)} of the error generated at the position or location (x, y) to a location (x+1, y), {fraction (3/16)} to a location (x−1, y+1), {fraction (5/16)} to a location (x, y+1), and {fraction (1/16)} to a location (x+1, y+1).
When the value I(x, y) is between 0 and 255, this value can be thought of as the number of dots out of 255 to printed. If I(x, y) is constant over a wide area, on average, I(x, y) dots out of 255 will be printed in this area.
Numerous enhancements have been suggested to enhance the output quality of error diffusion. These include varying the threshold value by some amount as a function of x and y, varying the order in which pixels are quantized, and varying the amount of error spread to neighboring pixels as well as the choice of pixels to which the error is spread.
The relatively simple Floyd and Steinberg technique requires, for each pixel, calculation of four separate error terms, weighted according to an error diffusion filter, with these four error terms being added to the four corresponding neighboring pixels. Thus, known error diffusion techniques are computationally intensive and time consuming.
With the pixel located at a specific location (x, y), the first error term of the Floyd and Steinberg technique is produced by {fraction (7/16)} of the quantization error being distributed to the next pixel (x+1, y) to be scanned in the same line. The pixel at a location (x+1, y+1) in the next scan line and one unit to the right (if scanning from left to right) has {fraction (1/16)} of the quantization error distributed thereto. The pixel disposed at a location (x, y+1) in the next scanned line below the processing pixel has {fraction (5/16)} of the quantization error distributed thereto. The pixel at a location (x−1, y+1) in the next scanned line and one pixel prior to the processing pixel has {fraction (3/16)} of the quantization error distributed thereto. The weight of the quantization error for each pixel is provided by the error diffusion filter.
Thus, the Floyd and Steinberg technique is computationally intensive. As a result, the Floyd and Steinberg technique is time consuming.
Furthermore, the Floyd and Steinberg technique produces halftone im

Affiliated with

Also associated with

Rating

Digital halftoning with 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 Digital halftoning with error diffusion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Digital halftoning with error diffusion will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2609026