Algorithms for Digital Halftoning

Industrial Presenter: Chai Wah Wu, IBM T. J. Watson Research Center

If you have ever looked at an image in a magazine or a newspaper under a magnifying glass, you will see that the image, which looks like it has many shades and colors, is actually composed of dots of inks in only a handful of colors. Digital halftoning is the art of representing a full color picture using only a few colors and is necessary in all digital (and most analog) printers. Halftoning is possible due to the characteristics of the human visual system (HVS). Several types of algorithms exist in modern digital printers with usually a tradeoff between speed and quality. This tradeoff is important since digital printers can operate at speeds of a few pages a minute (a printer for home use) to thousands of pages a minute (a production class digital printer). The general problem can be formulated as a discrete optimization (IP) problem by an appropriate model of the human visual system. Some of the questions of interest are: 1) what HVS models result in easier to solve IP problems. 2) questions regarding the stability and efficiency of algorithms currently used to perform digital halftoning. 3) relationship between halftoning heuristics and IP algorithms. The type of mathematics useful for digital halftoning include linear algebra, dynamical systems theory, convex analysis, and mathematical programming

Useful References

1. C. W. Wu, Error diffusion: recent developments in theory and applications (Focal Paper), Proceedings of NIP 20: IS&T's International Conference on Digital Printing Technologies, Salt Lake City, UT, pp. 642-646, 2004
2. C. W. Wu, G. Thompson, M. Stanich, A unified framework for digital halftoning and dither mask construction: variations on a theme and implementation issues (Focal Paper), NIP 19: IS&T's International Conference on Digital Printing Technologies, New Orleans, LA, 2003, pp. 793-796.
3. R. L. Adler, B. P. Kitchens, M. Martens, C. P. Tresser and C. W. Wu, The Mathematics of Halftoning, IBM Journal of Research and Development, vol. 47, no. 1, pp. 5-15, 2003.
4. Jan P. Allebach, “DBS: Retrospective and Future Directions,” in Proc. of the 2001 SPIE Electronic Imaging Conf., pp. 358-376, San Jose, CA, SPIE Vol. 4300.