Jon A. Webb

School of Computer Science
Carnegie Mellon University, Pittsburgh, PA 15213

Table of Contents




By defining a performance metric in terms of a model of the human visual system, we can develop a criterion for the accuracy of a halftoning algorithm. Directly optimizing this criterion leads to an algorithm based on the Gibbs sampler. The resulting algorithm is more computationally expensive than error diffusion: however, it is local, highly parallel, and has a number of other desirable properties. For high quality halftoning, it is necessary to take into account the physical characteristics of the display device. The proposed algorithm can do this in a direct manner. For black and white monitors, this leads to an adjustment in the calculated brightness of the first pixel turned on in raster order; this brightness adjustment is significant, as the first pixel in such a run has been measured at only70% of the brightness of succeeding pixels. In printed halftoned images, ink overlap leads to a decrease in the perceived darkness of adjacent dark pixels; again, the difference is significant, having been measured at 16% effective overlap. On color printers, it is possible to directly measure the colors produced by the printer and use them in formulating the error measure for halftoning. Adjusting for these effects, which cannot be done with error diffusion algorithms, leads to perceivable increase in halftoned image quality.


Previously [3] we discussed how it is possible to treat halftoning as an inverse problem, meaning the inverse of a problem which is well-defined and easily calculated. Halftoning as an inverse problem is ill-posed; it has no unique solution. However, it is possible to find good solutions to the halftoning problem nevertheless through the use of the Gibbs sampler.

In treating halftoning as an inverse problem, we recognize that the goal of halftoning is to create a binary image that resembles an original continuous tone image as much as possible. In other words, the goal is to solve the equation
C= V{H}
for H, where C is the original continuous tone image, H is the halftoned binary image, and V is the transfer function of the human visual system. (We are ignoring here the fact that the continuous tone image is also subjected to V; the real equation to be solved is V{C} = V{H}. But it is easy to modify the method developed here to solve this equation instead, simply by pre-filtering C with V. We are also ignoring the fact that the halftoned image may be at a higher resolution as the continuous tone image; this is easily handled by first increasing the resolution of C by the desired amount.)

This equation is difficult to solve because there are many different values of H that serve equally well. In halftoning, however, we do not care which version of H we obtain, so long as it is a good approximation to C when filtered by V. As we have shown, it is possible to find one of these versions of H by an iterative method based on the Gibbs sampler [1] . The method works by starting with an initial approximation to H (calculated for instance by a simple halftoning method like ordered dithering) and then iteratively modifying it to minimize the error in (1) locally around each pixel, using a simulated annealing method. The method is computationally expensive, but produces high quality halftoned images, and is inherently parallel, making it suitable for implementation at low cost in the future on massively parallel computers.

In this paper we examine how the same method can be used to compensate for, and even take advantage of, idiosyncracies in image I/O devices. These idiosyncracies are a major source of difficulties for other halftoning algorithms, to the extent that their elimination results in constant effort on the part of manufacturers of displays and printers. However, we shall show that with a halftoning algorithm based on the direct solution of equation (1), such as we have developed, much of this effort is unnecessary, because it is possible for the halftoning algorithm itself to compensate for the characteristics of the display or printer, so long as the effects are consistent. In fact, in some cases we will show that properly taking advantage of these characteristics can lead to image quality better than images from displays and printers without the idiosyncracies.

We consider three such idiosyncracies here. The first is the finite time an electron beam takes to go from a value representing 0 to a value representing 1 on a CRT display, which results in the first pixel turned on in a raster-order scan having a brightness value less than succeeding pixels. The second is the ink spreading effect in black and white printers, which results in two isolated black pixels having a greater total darkness than two adjacent black pixels. The third is the impure color effect in color printers, resulting from ink color not being purely red, green, and blue, but rather a mixture of these colors.


The first pixel turned on in a raster-order run on a CRT display is not as bright as succeeding pixels. Figure 1 shows the reason. As the electron beam makes its raster-order scan, it takes a finite time to make the transition between the value representing 0 and the value representing 1 (throughout this paper, we use 0 for black and 1 for white, whether in a binary or continuous tone display). During this time the electron beam is moving. As a result, the first pixel in the run receives less electrical stimulation than succeeding pixels, so that it is not as bright.

    Figure 1 . Electron beam transition on a CRT display.

We have measured this effect in the Calibrated Imaging Laboratory at Carnegie Mellon University. Various vertical stripe patterns were displayed on a Sun bit-mapped monitor (model L71015-Y01). Brightness was measured directly from the screen using a 1/3 degree digital Minolta luminance meter from a distance of approximately two meters.

Results are shown in Table 1. Fitting the simple model
x = brightness of first pixel in run
y = brightness of second pixel in run
z = brightness of succeeding pixels in the run
to this data, we obtain x=38, y=54, and z=52. The first pixel is approximately 70% as bright as the next or succeeding pixels, and the next and succeeding pixels have approximately the same brightness. (It is important to note that this model, and in fact this method of data collection, has no way of distinguishing between a reduction in brightness of the first or the last pixel turned on in a run. The last pixel may also experience some reduction in brightness, or the first pixel turned off after an pixel turned on may experience an increase in brightness. However, in our application of this result, we will be concerned with calculating the brightness of short runs of pixels. Since we will be applying this result to calculating the total brightness of the run, it will not matter whether it is the first or the last pixel that is dimmed.)

Stripe Pattern Brightness (cd/m2)

1010101010101010 20

1100110011001100 24

1111000011110000 25

0001000100010001 9

0000001100000011 11

0000000000001111 12

1111111111111111 53

0000000000000000 0

Table 1 . Brightness of vertical stripe patterns on CRT display

We can apply this result as follows. The method previously described for halftoning using the Gibbs sampler must calculate the local error between a pixel in the continuous tone image and the halftoned image. This is done by the use of a 7*7 Gaussian filter (approximating the human visual system). The Gaussian filter is applied to the halftoned image, and the difference between the filtered halftoned value and the continuous value is the error. In halftoning for CRT displays, we simply discount the first pixel turned on in a run by a factor of 0.7.

This can be calculated efficiently by taking advantage of the decomposability of the Gaussian filter. The 7*7 Gaussian filter can be calculated in two steps, first by convolving a 7-element one-dimensional Gaussian filter with each row in the kernel, forming a 7-element vector, and then convolving a 7-element one-dimensional Gaussian filter with this vector. We can pre-calculate the first step for each of the 2**7 possible halftoned bit patterns, taking into account the 70% discounting of the first pixel turned on in a run. These pre-calculated values can be stored in a table, and retrieved by concatenating the seven halftoned bits together and using this as a table index. We can also take advantage of processing the image in raster order, reducing the overhead for forming the address. The result is that calculating the 7*7 Gaussian filter takes only seven bit shifts, seven logical ands, seven logical ors, seven table lookups, seven floating point multiplies, and six floating point adds.

The results cannot be displayed here, but are distinctly better than results from the standard Gibbs halftoning algorithm, which already produces quite good images. In particular, there is a more gradual transition from dark to light areas of the image; bright areas are not as harsh. Gray areas of the image are a more moderate gray, and do not inappropriately include bright pixels.

Note that this technique is difficult to apply with error diffusion in raster order, and impossible to apply in serpentine order, a necessary technique for the best error-diffused halftoned images. The first pixel turned on in a run cannot be discounted when making a reverse-raster order scan of a line in the image, because error diffusion depends on thresholding pixels at a single fixed value, and then propagating the error obtained to succeeding pixels. The actual error is not known in general in a reverse-raster order scan until the next pixel is thresholded, after the error must have already been propagated.

3 . Halftoning on a Black and White Printer

Adjacent black pixels on a black and white printer must merge into a single elongated black dot in order to form continuous black areas of paper to create printed letters and graphics. Now, the actual pixel shape of a black pixel is approximately circular. The only way to cause circles to merge into an elongated black dot is by overlapping them, as shown in Figure 2. The overlapped area is colored twice with black ink, but is not twice as dark as areas colored only once. The result is that two adjacent black pixels are not as dark as two black pixels that are not adjacent; they do not cover as much of the paper with black ink.

    Figure 2 . Adjacent black pixels

We have measured this effect as well. We printed vertical stripes patterns using an Apple Laserwriter Plus printer (model number M0166). The brightness of each pattern was measured as before.

Here we fit the model
where "darkness" is the difference between the brightness observed for all white pixels (130) and the pattern brightness.

Fitting this model to the data in Table 2 gives alpha = 150 and beta = 49. (The fit is significant at the Q>0.001 level assuming a standard deviation of measurement error of at least 5, which is reasonable for these data). alpha/beta = 0.33, so there is about at 33% overlap between any two black pixels, and a middle pixel is overlapped on both sides, so that there is a 16% overlap on both sides. Treating the pixels as if they were square, the situation can be idealized as shown in Figure 3. (Note that in this analysis we have ignored any overlap between pixels on diagonals, which is likely also to be significant though not as significant as horizontally or vertically adjacent pixels. We are also measuring only horizontal overlap and assuming overlap is the same horizontally or vertically.)

    Figure 3 . Idealized model of pixel overlapping on a black and white printer.

The effect is therefore significant. There are three ways of dealing with it:

  1. . Try to make the pixels more square. Since the pixels are laid out on a square grid, more nearly square pixels would suffer less from this effect.
  2. . Try to guarantee that black pixels are always printed adjacent to other black pixels. The result of this would be that the same amount of ink would be "lost" by each black pixel, so that all black pixels would contribute the same amount of darkness to the halftoned image.
  3. . Modify the halftoning algorithm itself to take into account this effect.
The first two of these methods have already been used in practical halftoning systems. Pixels can be made more square simply by reducing the resolution of the image, as shown in Figure 4. Printing each black pixel as a 2*2 square produces pixels that are much more nearly square, and which have a smaller percentage overlap with adjacent pixels while still being able to form continuous lines and characters.

    Figure 4 . Reducing resolution makes pixels more square.

The second method can be accomplished by printing the pixels in a spiral pattern, around centers spaced at regular intervals. This is the common halftone screening process, widely used in printing.

However, both of these methods sacrifice printer resolution. The first method reduces the resolution directly; if pixels are printed as 2*2 squares, a 300 dpi printer will effectively have only 150 dpi resolution. The second method introduces an undesirable (though familiar) low frequency component to the image at the resolution of the halftone screen.

It is better to work at the full printer resolution, without introducing artificial frequencies. This can be accomplished in the Gibbs sampler algorithm simply by changing the error measure, as in the case of halftoning for CRT displays. Recall that the estimate of the halftoned image grayvalue is calculated as the result of a 7*7 Gaussian filter applied to the halftoned image. We can modify this estimate by examining the 7*7 window and replacing each pixel with the value 1 by a fraction equal to the white area remaining after overlap from adjacent black pixels. If there are no adjacent black pixels, there is no change; if one pixel is adjacent, the new value is 0.84; if two are adjacent and are adjacent to each other, the new value is 0.71; if two are adjacent and opposite each other, the new value is 0.68; if three are adjacent, the new value is 0.57; if four are adjacent, the new value is 0.46. (These numbers can be calculated by considering the white area remaining in each of these situations according to Figure 3.) We then convolve this window with a 7*7 Gaussian.

Results are shown in Figure 5. For comparison we include the same image halftoned without the adjustment for overlapping pixels in Figure 6, and a continuous tone version of the same image in Figure 7. These images were supplied to the author by John Sullivan of the Electronic Imaging Research Laboratory of Eastman Kodak Company; the image is a standard benchmark image used to evaluate halftoning algorithms.

Comparing the two images, we see first that Figure 5 has more white space near the top of the building than Figure 6. This is a consequence of a thresholding effect in the Gibbs-based algorithm. Because the algorithm calculates the error in a small window, in this case 7*7, grayvalues very close to 0 or 1 cannot be approximated by a gray pattern, but instead are assigned a purely white or black value. Since the two algorithms calculate the grayness of a pattern slightly differently, this threshold occurs at a different value.

The region at the bottom of the image, showing a field before a lake, illustrates the superiority of the modified algorithm best. The image is sharper and more clear in Figure 5 than in Figure 6. This is a consequence of the algorithm's correct estimation of the effect of placing a black pixel next to a white pixel, a significant effect in this finely detailed area.

Further comparison of the images will validate this observation. The modification we have made to the Gibbs algorithm has resulted in an algorithm that more accurately captures finely detailed gray areas of the image.

    Figure 7 . Continuous tone image of the buildings.

4 . Halftoning on a Color Printer

Images are printed on a CMYK printer by overlaying different colors of ink --- chartreuse, maroon, yellow, or black. The combination of these colors of ink produces eight different colors.

Halftoning for color display has been treated in, for example, [2] , where an error diffusion algorithm based on Floyd-Steinberg is proposed. The algorithm works by, at each pixel, selecting the color closest to the color to be represented, and then propagating the error between the displayed and actual colors to pixels yet to be processed.

This algorithm suffers from all the problems of error diffusion halftoning algorithms, as we have previously described. We can develop an improved algorithm based on the Gibbs sampler that avoids these problems.

The method takes into account the actual colors that can be produced by the printer. First we measure these colors, by printing an image of them and then measuring their red, green, and blue components. Each of these values can be stored in a lookup table so that for a given halftoned pixel value, represented as a number from 0 to 7, we can look up the red, green, and blue values of the pixel.

We can then calculate the error measure by measuring the red, green, and blue value of the window surrounding the pixel by applying the 7*7 Gaussian filter to the red, green, and blue bands of the halftoned image independently. For example, in order to calculate the red value we determine the red value of each of the pixels in the window, then apply the Gaussian filter. The error measure is then the difference between this estimated red, green, blue value and the red, green, blue value to be represented.

We have applied this algorithm to color images, so far with less than satisfactory results. The resulting images do not display the correct true colors. We believe this may be due to errors in measurement of the colors of the original colored ink values; changes in brightness can seriously affect the measured values.

5 . Summary

We have shown that it is possible to compensate for, and even take advantage of, idiosyncracies in output device characteristics by correctly modifying the halftoning algorithm. This can be done only with algorithms that treat halftoning as an inverse problem, such as the one we have developed based on the Gibbs sampler. This algorithm is computationally expensive, but is well suited to parallel implementation, making it suitable for use in real systems in the near future.

6 . Acknowledgments

This research was supported by a grant from the Digital Technology Center of Eastman Kodak Corporation. Data for this research was provided by the Calibrated Imaging Laboratory at Carnegie Mellon University.

7 . Bibliography

[1] Geman, S. and Geman, D. Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images. IEEE Transactions on Pattern Analysis and Machine Intelligence. 6(6):721-741, November, 1984.

[2] Heckbert, P. Color Image Quantization for Frame Buffer Display. Computer Graphics. 16(3):297-307, July, 1982.

[3] Webb, J. A. Accurate Parallel Digital Halftoning. Society for Information Display International Symposium Digest of Technical Papers. 151-154. Anaheim, CA, 1991.