School of Computer Science
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.
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.
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.)
The effect is therefore significant. There are three ways of dealing with it:
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.
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.
[3] Webb, J. A. Accurate Parallel Digital Halftoning. Society for Information Display International Symposium Digest of Technical Papers. 151-154. Anaheim, CA, 1991.
