Mr. Hains joined the Xerox Corporation in 1966. At that time all the xerographic copiers were light-lens devices, Xerox was starting to consider writing digital data to a xerographic drum. This report describes how digital halftoning evolved at Xerox through the 1970s to the present day. Xerox experimented with a method called "induction printing" using a modified Xerox 914 copier. It didn't take long to realize that xerography was a very non-linear process and that half-tones were needed to control it. Halftoning is a process where a continuous-tone image is quantized into two levels while maintaining the gray appearance of an image at a normal reading distance. Halftoning is usually required because the physical process is inherently binary in nature, such as in offset or lithographic printing where one prints either ink or no ink, and also in ink jet devices. Xerography is not inherently binary, but is extremely non-linear. It is possible to expose with multiple levels onto a photoreceptor but it is difficult to control the resulting electrical charges that are produced.

Xerography acts like a high-pass filter, enhancing edges but degrading flat areas. Halftoning turned out to be an excellent match for controlling xerography because the halftone dot edges are sharpened while the interior of the halftone dots are not degraded. The halftone dots control the xerography and allow for a more linear process.

Dispersed dots, clustered dots, line screens, and Error Diffusion were all investigated. Error Diffusion showed amazing detail on a computer display screen but not on a xerographic print. The problem is the dot gain of a laser scanning system. The solution for dot-gain problems is the same one that classical graphic arts printing has employed for the last century, clustered halftone dots. Cluster dots were chosen because they are the least susceptible to dot gain. Dot gain in a laser scanning system is more complicated than classical printing and the dot gain is non-symmetrical. There is also a problem with "negative dot gain" where the dots get smaller. The Error Defusion method produces isolated printer pixels through the density range so the dot gain is very unpredictable. Fortunately, for clustered dot printing, the dot gain is monotonic and predictable and can be compensated by the calibration process. Because of this, most xerographic products utilize cluster halftones.

From 1973 on some excellent work was done using laser scanning with analog circuits and a Xerox 6500 copier. The analog circuits had some drawbacks. They were real-time circuits which required scanning and printing at the same time, and they suffered from electronic drift. The analog approach soon gave way to purely digital. Digital halftoning requires comparing input image data at each point along a line with a halftoning function. This can be done in several different ways by adding the function to the image data and thresholding the sum, by subtracting the function from the data and testing the sign, or by table lookup.

Analog made a later comeback and then there was a trend to a hybrid approach where the analog line screens were used on a pixel-by-pixel basis to construct clustered rotated digital dots. The line screens were only used for pixels on the edges of the dots, but added enough effective gray levels to remove contour effects. The method is called Digital Analog Complement Screens (DACS).

Mr. Hains described three different halftone orientations used in Xerox products; dot-on-dot, rotated, and dot-off-dot. He also described many of the problems and techniques of color printing. He described this in considerable detail with many illustrations. In many cases, the technique selected depends on what it is that you are trying to accomplish.

Digital halftoning technology has evolved in complexity in the past 30 years. Screens have progressed from very simple threshold arrays through multi-center dots, high-addressability dots, non-orthogonal dots, and multi-beam raster written dots. Various methods of avoiding color moire have been developed. New developments in printer hardware development bring new trade-offs required for halftone technology and new challenges. Digital halftone technology has not yet reached an end point.

You can reach Chuck Hains at: CHains@cp10.es.xerox.com

There is no way you can obtain the advantage of viewing many highly informative displays and actually seeing the demonstrations provided by Mr. Hains. This article is only a short report obtained from his excellent presentation and from a paper titled "The 30-year evolution of digital halftoning from the viewpoint of a participant" that he provided to me.

This was the eighth meeting of the LA Chapter year and was attended by about 14 persons.
Mike Walsh, LA ACM Secretary