HP Laboratories Seminar

Interpolated Halftoning, Rehalftoning, and Halftone Compression

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


Collaboration with Mr. Niranjan Damera-Venkata and Dr. Thomas Kite and

Wednesday, November 4, 1998, 3:00 PM
Hewlett-Packard Laboratories
Palo Alto, CA

Slides in PDF Format


Digital halftoning of grayscale images converts a continuous-tone image to a binary image, or halftone, for printing or display on binary devices. Ordered dithered halftones contain aliased and blurred copies of the original plus noise, whereas error diffused halftones sharpen the original image and add noise. In this talk, we review our linear shift-invariant (LSI) model of error diffusion [3] which we used to measure the impact of frequency distortion and noise in error diffused halftones on the human visual system. Based on the LSI model, we show how to preprocess a grayscale image before error diffusion so that the halftone has no frequency distortion.

With increasing number of dots per inch on printers, grayscale images are often interpolated and then halftoned. Using our LSI model, we can compensate for the frequency distortion in interpolation and halftoning to produce halftones with the same frequency response of the original plus noise, using only raster image processing operations. In a similar manner, we can rehalftone a scanned error diffused halftone for a particular error diffusion printer in such a way as to eliminate all frequency distortion. Rehalftoning is essentially inverse halftoning followed by halftoning. Because the inverse halftone will be halftoned, we show that we can use a 4 x 4 FIR filter to perform the inverse halftoning. This is in contrast to sophisticated inverse halftoning algorithms [1,2].

Interpolated halftoning and rehalftoning are useful in compressing halftones. Halftone compression is a key issue in the emerging JBIG2 standard, which is intended for the next-generation fax machines, printers, and scanners. The key problem with current fax machines is that they expand halftones. In JBIG2, halftones may be (1) compressed directly or (2) converted to a higher bitwidth and then each bit plane is compressed. Lossless compression is high for clustered dot halftones (5:1) but low for error diffused halftones (2:1). We propose to apply our work in rehalftoning for JBIG2 codecs and interpolated halftoning in JBIG2 decoders to improve the coding gain for error diffused halftones. We also propose to use our quality assessment techniques to rate JBIG2 codecs.


  1. N. Damera-Venkata, T. D. Kite, M. Venkataraman, and B. L. Evans, "Fast Blind Inverse Halftoning", Proc. IEEE Int. Conf. on Image Processing, Chicago, IL, Oct. 4-7, 1998, vol. 2, pp. 64-68.
  2. T. D. Kite, N. Damera-Venkata, B. L. Evans, and A. C. Bovik, "A High-Quality, Fast Inverse Halftoning Algorithm for Error Diffused Halftoned Images", Proc. IEEE Int. Conf. on Image Processing, Chicago, IL, Oct. 4-7, 1998, vol. 2, pp. 59-63.
  3. T. D. Kite, B. L. Evans, T. L. Sculley, and A. C. Bovik, "Digital Halftoning As 2-D Delta-Sigma Modulation", Proc. IEEE Int. Conf. on Image Processing, vol. I, pp. 799-802, Oct. 26-29, 1997, Santa Barbara, CA.


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 over 50 refereed 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 an Associate Editor of the IEEE Transactions on Image Processing, a Senior Member of the IEEE, and the recipient of a 1997 National Science Foundation CAREER Award.

Mail comments about this page to bevans@ece.utexas.edu.