This dissertation was presented to the Faculty of the Graduate School of The University of Texas at Austin in partial fulfillment of the requirements for the degree of

Ph.D. in Electrical Engineering


Design and Quality Assessment of Forward and Inverse Error Diffusion Halftoning Algorithms 


Thomas D. Kite, Ph.D.E.E.

The University of Texas at Austin, August 1998


Prof. Brian L. Evans
Prof. Alan C. Bovik


Dissertation - Defense


Digital halftoning is the process by which a continuous-tone image is converted to a binary image, or halftone, for printing or display on binary devices. Error diffusion is a halftoning method which employs feedback to preserve the local image intensity and reduce low frequency quantization noise. It is a highly nonlinear process, and it is therefore difficult to analyze mathematically. In this work, a linear gain model for the quantizer is presented which accurately predicts the edge sharpening and noise shaping effects of error diffusion. The model is used to construct a residual image that has a low correlation with the original image. By weighting this residual with a model of the human visual system, a measure of the subjective effect of the quantization noise on the viewer is obtained. A distortion metric for the halftoning scheme is also computed. By characterizing the edge sharpening, noise shaping, and distortion of an error diffusion scheme, objective measures of subjective quality of halftones are obtained. This permits the comparison of halftoning schemes.

A new, efficient inverse halftoning scheme for error diffused halftones is presented that produces results comparable to the best current methods, but at a fraction of the computational cost. A method of modeling inverse halftoning schemes is demonstrated, and is used to generate residual images, which are weighted with the human visual system model. An effective transfer function for the inverse halftoning scheme is also computed. By characterizing the degree of blurring and the noise content, objective measures of subjective quality of inverse halftones are obtained. This allows competing inverse halftoning algorithms to be compared. The linear gain model is further used to design and analyze the performance of applications which include error diffusion. The model of the human visual system is again used to obtain objective measures of the quality of images produced by these applications.


For more information contact: Thomas D. Kite <>