Digital Image Halftoning as 2-D Delta-Sigma Modulation

Prof. Brian L. Evans
Laboratory for Image and Video Engineering
Dept. of Electrical and Computer Engineering
The University of Texas at Austin

research conducted in collaboration with
Mr. Thomas D. Kite (UT Austin), Prof. Alan C. Bovik (UT Austin), and Dr. Terry Sculley (ESS Inc.)

Digital image halftoning is the process of converting an image composed of many shades of grey into an image containing only black and white. The goal is to compute the locations of the black and white dots to retain as much subjective quality in the image as possible. Image halftoning is widely used in laser and ink jet printers, monochrome monitors, and newsprint.

This talk will focus on error diffusion algorithms which provide an efficient way of converting grayscale images into high quality halftones. We show that the form error diffusion algorithms for digital halftoning is equivalent to a nonseparable two-dimensional noise-shaping feedback coder, which is a class of delta-sigma modulator. By applying delta-sigma modulation analysis techniques, we explain features in halftones produced by classical error diffusion schemes, and allow the optimization of these schemes for high visual quality.

After describing delta-sigma modulation, we will analyze the behavior of the two key components in a noise-shaping feedback coder-- the quantizer and the two-dimensional filter in the feedback path. The quantization error is not white noise but instead highly correlated with the input image. To account for this correlation, we model the quantizer as a gain plus additive noise. This model accurately predicts the edge sharpening and noise shaping caused by all error diffusion schemes and permits an extension of error diffusion to oversampled imagery. Next, we derive a measure for subjective quality based on the gain value and filter coefficients. The measure gives us a formal, mathematical framework for analyzing and optimizing the subjective quality of image halftoning by error diffusion.


Brian L. Evans is an Assistant Professor in the Department of Electrical and Computer Engineering at The University of Texas at Austin, and the Director of the Embedded Signal Processing Laboratory within the Center for Vision and Image Sciences. His research interests include real-time embedded systems; signal, image and video processing systems; system-level design; symbolic computation; and filter design. Dr. Evans has published 40 conference and journal papers in these fields. He developed and currently teaches EE381K Multidimensional Digital Signal Processing, EE382C Embedded Software Systems, and EE379K Real-Time Digital Signal Processing Laboratory. His B.S.E.E.C.S. (1987) degree is from the Rose-Hulman Institute of Technology, and his M.S.E.E. (1988) and Ph.D.E.E. (1993) degrees are from the Georgia Institute of Technology. From 1993 to 1996, he was a post-doctoral researcher at the University of California at Berkeley with the Ptolemy Project. Ptolemy is a research project and software environment focused on design methodology for signal processing, communications, and controls systems. In addition to Ptolemy, he has played a key role in the development and release of six other computer-aided design frameworks, including the Signals and Systems Pack for Mathematica, which has been on the market since the Fall of 1995. He is a Senior Member of the IEEE, and the recipient of a 1997 National Science Foundation CAREER Award.

Mail comments about this page to