“A simple and efficient error-diffusion algorithm” by Ostromoukhov

In this contribution, we introduce a new error-diffusion scheme that produces higher quality results. The algorithm is faster than the universally used Floyd-Steinberg algorithm, while maintaining its original simplicity. The efficiency of our algorithm is based on a deliberately restricted choice of the distribution coefficients. Its pleasing nearly artifact-free behavior is due to the off-line minimization process applied to the basic algorithm’s parameters (distribution coefficients). This minimization brings the Fourier spectra of the selected key intensity levels as close as possible to the corresponding “blue noise” spectra. The continuity of the algorithm’s behavior across the full range of intensity levels is achieved thanks to smooth interpolation between the distribution coefficients corresponding to key levels. This algorithm is applicable in a wide range of computer graphics applications, where a color quantization algorithm with good visual properties is needed.

1. J. P. Allebach. Private communication, 2001.
2. M. Analoui and J. P. Allebach. Model based halftoning using direct binary search. SPIE, 1666:96-108, 1992.
3. B. E. Bayer. An optimum method for two-level rendition of continuous-tone pictures. IEEE Intl. Conf. on Communications, 1:2611-2615, 1973.
4. R. Eschbach. Reduction of artifacts in error diffusion by mean of inputdependent weights. JEI, 2(4):352-358, 1993.
5. R. Eschbach and R. Hauck. A 2-D pulse density modulation by iteration for halftoning. Optics Communications, 62(5):300-304, 1987.
6. R. Eschbach and K. T. Knox. Error-diffusion algorithm with edge enhancement. JOSA (A), 8(12):1844-1850, 1991.
7. R. W. Floyd and L. Steinberg. An adaptive algorithm for spatial grey scale. Proc. Soc. Inf. Display, 17:75-77, 1976.
8. L. Golland and K. Sigmund. Exact thought in a demented time: Karl Menger and his viennese mathematical colloquium. Math. Intelligencer, 22(1):34-45, 2000.
9. J. F. Jarvis, C. N. Judice, and W. H. Ninke. A survey of techniques for the display of continuous tone pictures on bilevel displays. Computer Graphics and Image Processing, 5:13-40, 1976.
10. H.R. Kang. Digital Color Halftoning. SPIE Press, 1999.
11. K. T. Knox. Edge enhancement in error diffusion. In Advance Printing of Paper Summaries, SPSE’s 42nd Annual Conference, pages 310-313, Boston, MA, May 1989.
12. K. T. Knox. Error diffusion: A theoretical view. SPIE, 1913:326-331, 1993.
13. K. T. Knox. Evolution of error diffusion. JEI, 8(4):422-429, 1999.
14. D. J. Lieberman and J. P. Allebach. A dual interpretation for direct binary search and its implications for tone reproduction and texture quality. IEEE Trans. on Image Processing, 9:1950-1963, 2000.
15. G. Marcu. An error diffusion algorithm with output position constraints for homogeneous highlights and shadow dot distribution. JEI, 9(1):46-51, 2000.
16. T. Mitsa and K. J. Parker. Digital halftoning using a blue-noise mask. Journal of the Optical Society of America A, 9(11):1920-1929, 1992.
17. V. Ostromoukhov, R. D. Hersch, and I. Amidror. Rotated dispersion dither: a new technique for digital halftoning. Proceedings of SIGGRAPH 94, pages 123- 130, 1994.
18. W. H. Press, B. P. Flannery, S. A. Teukolsky, and W. T. Vetterling. Numerical Recipes. Cambridge University Press, 1989.
19. C. I. Rosenberg. Measurement-based evaluation of a printer dot model for halftone algorithm tone correction. JEI, 2(3):205-212, 1993.
20. J. Shiau and Z. Fan. Method for quantization gray level pixel data with extended distribution set, 1994. US patent 5,353,127.
21. J. Shiau and Z. Fan. A set of easily implementable coefficients in error diffusion with reduced worm artifacts. SPIE, 2658:222-225, 1996.
22. P. Stucki. Mecca-a multiple-error correcting computation algorithm for bilevel image hardcopy reproduction, 1981. Research Report RZ1060, IBM Res. Lab.
23. R. Ulichney. Digital Halftoning. MIT Press, 1987.
24. R. Ulichney. The void-and-cluster method for dither array generation. SPIE, 1913:332-343, 1993.
25. R. Ulichney. A review of halftoning techniques. SPIE, 3963:378-391, 2000.
26. L. Velho and J. Gomes. Digital halftoning with space filling curves. Computer Graphics (Proceedings of SIGGRAPH 91), 25(4):81-90, 1991.
27. L. Velho and J. Gomes. Stochastic screening dithering with adaptive clustering. Proceedings of SIGGRAPH 95, pages 273-276, 1995.
28. I. H. Witten and R. M. Neal. Using peano curves for bilevel display of continuous-tone images. IEEE Computer Graphics & Appl., 2:47-52, 1982.