“Space diffusion: an improved parallel halftoning technique using space-filling curves” by Zhang and Webber

  • ©Yuefeng Zhang and Robert E. Webber




    Space diffusion: an improved parallel halftoning technique using space-filling curves



    Dot diffusion has been proposed as a way of combining the strengths
    of ordered dithering and error diffusion to create a parallelizable
    halftoning technique. However, dot diffusion pays a price in image
    quality in order to achieve parallelizability. Space-filling curves
    have been used to improve error diffusion. We show that by combining dot diffusion with a space-filling curve traversal technique,
    a parallelizable halftoning technique results that does not pay a cost
    in image quality. This new technique we call space diffusion.
    KEYWORDS: Space-filling curves, dot diffusion, error diffusion,
    ordered dithering, digital halftoning, parallel algorithms.


    1. Cole, A. J. Halftoning Without Dither or Edge Enhancement. The Visual Computer 7 (1991), 232- 246.
    2. Floyd, R. W. and Steinberg, L. An Adaptive Algorithm for Spatial Greyscale. Proceedings of the S. I. D. 17, 2 (Second Quarter 1976), 75- 77.
    3. Jarvis, J. E, Judice, C. N., and Ninke, W. H. A Survey of Techniques for the Display of Continuous Tone Pictures on Bilevel Displays. Computer Graphics and Image Processing 5 (1976), 13- 17.
    4. Judice, C. N., Jarvis, J. F. and Ninke, W. H. Using Ordered Dither to Display Continuous Tone Pictures on an AC Plasma Panel. Proceeding of the S.I.D. 15, 4 (Fourth Quarter, 1974), 161- 169.
    5. Knowlton, K. and Harmon, L. Computer-Produced Grey Scales. Computer Graphics and Image Processing 1 (1972), 1 – 20.
    6. Knuth, D. E. Digital Halftones by Dot Diffusion. ACM Transactions on Graphics 6, 4 (October 1987), 245- 273.
    7. Ulichney, R. Digital Halftoning. The MIT Press, Cambridge, Massachusetts, 1988.
    8. Velho, L. and de M. Gomes, J. Digital Halftoning with Space Filling Curves. Proceedings of SIGGRAPH ’91 (Las Vegas, 28 July-2 August 1991). In Computer Graphics 25, 4 (July 1991), 81 – 90.
    9. Witten, I. H. and Neal, M. Using Peano Curves for Bilevel Display of Continuous Tone Images. IEEE Computer Graphics and Applications (May 1982), 47- 52.
    10. Witten, I. H. and Wyvill, B. On the Generation and Use of Space-filling Curves. Software Practice and Experience 13 (1983), 519- 525.
    11. Wyvill, G. and McNaughton, C. Three Plus Five Makes Eight: A Simplified Approach to Halftoning. Scientific Visualization of Physical Phenomena (Boston, 1991), Springer-Verlag, New York, 379- 392.

ACM Digital Library Publication:

Overview Page: