“Structure-aware halftoning” by Pang, Qu, Wong, Cohen-Or and Heng

  • ©Wai-Man Pang, Yingge Qu, Tien-Tsin Wong, Daniel Cohen-Or, and Pheng-Ann Heng




    Structure-aware halftoning



    This paper presents an optimization-based halftoning technique that preserves the structure and tone similarities between the original and the halftone images. By optimizing an objective function consisting of both the structure and the tone metrics, the generated halftone images preserve visually sensitive texture details as well as the local tone. It possesses the blue-noise property and does not introduce annoying patterns. Unlike the existing edge-enhancement halftoning, the proposed method does not suffer from the deficiencies of edge detector. Our method is tested on various types of images. In multiple experiments and the user study, our method consistently obtains the best scores among all tested methods.


    1. Baqai, F., and Allebach, J. 2003. Halftoning via direct binary search using analytical and stochastic printer models. IEEE Transactions on Image Processing 12 (January), 1–15. Google ScholarDigital Library
    2. Bartlett, M. S. 1955. Introduction to Stochastic Processes with Special Reference to Methods and Applications. Cambridge University Press, New York.Google Scholar
    3. Bayer, B. 1973. An optimum method for two-level rendition of continuous-tone pictures. In IEEE International Conference on Communications, IEEE, (26–11)–(26–15).Google Scholar
    4. Deussen, O., Hiller, S., van Overveld, C., and Strothotte, T. 2000. Floating points: A method for computing stipple drawings. Computer Graphics Forum 19, 3, 40–51.Google ScholarCross Ref
    5. Eschbach, R., and Knox, K. T. 1991. Error-diffusion algorithm with edge enhancement. J. Opt. Soc. Am. A 8, 12, 1844.Google ScholarCross Ref
    6. Floyd, R. W., and Steinberg, L. 1974. An adaptive algorithm for spatial grey scale. In SID International Symposium Digest of Technical Papers, Society for Information Display, 36–37.Google Scholar
    7. Geist, R., Reynolds, R., and Suggs, D. 1993. A markovian framework for digital halftoning. ACM Trans. Graph. 12, 2, 136–159. Google ScholarDigital Library
    8. Hwang, B.-W., Kang, T.-H., and Lee, T.-S. 2004. Improved edge enhanced error diffusion based on first-order gradient shaping filter. In IEA/AIE’2004: Proceedings of the 17th international conference on Innovations in applied artificial intelligence, Springer Springer Verlag Inc, 473–482. Google ScholarCross Ref
    9. Jarvis, J. F., Judice, C. N., and Ninke, W. H. 1976. A survey of techniques for the display of continuous tone pictures on bilevel displays. Comput Graphics Image Process 5, 1, 13–40.Google ScholarCross Ref
    10. Knuth, D. E. 1987. Digital halftones by dot-diffusion. ACM Transactions on Graphics 6, 4, 245–273. Google ScholarDigital Library
    11. Kopf, J., Cohen-Or, D., Deussen, O., and Lischinski, D. 2006. Recursive wang tiles for real-time blue noise. In SIGGRAPH ’06: ACM SIGGRAPH 2006 Papers, ACM, New York, NY, USA, 509–518. Google ScholarDigital Library
    12. Kwak, N.-J., Ryu, S.-P., and Ahn, J.-H. 2006. Edge-enhanced error diffusion halftoning using human visual properties. In ICHIT ’06: Proceedings of the 2006 International Conference on Hybrid Information Technology, IEEE Computer Society, Washington, DC, USA, 499–504. Google ScholarCross Ref
    13. Li, R., and Allebach, J. 2002. Tone dependent error diffusion. In Proceedings SPIE Cot Electronic Imaging, (San Jose, CA), 293–301.Google Scholar
    14. Li, X. 2006. Edge-directed error diffusion halftoning. IEEE Signal Processing Letters 13, 11 (November), 688–690.Google ScholarCross Ref
    15. Mitchell, D. P. 1987. Generating antialiased images at low sampling densities. In Proceedings of SIGGRAPH’87, vol. 21. Google ScholarDigital Library
    16. Mitsa, T., and Parker, K. J. 1992. Digital halftoning technique using a blue-noise mask. J. Opt. Soc. Am. A 9, 11, 1920.Google ScholarCross Ref
    17. Ostromoukhov, V., and Hersch, R. D. 1995. Artistic screening. In SIGGRAPH ’95: Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, ACM, New York, NY, USA, 219–228. Google ScholarDigital Library
    18. Ostromoukhov, V. 2001. A simple and efficient error-diffusion algorithm. In SIGGRAPH ’01: Proceedings of the 28th annual conference on Computer graphics and interactive techniques, ACM, New York, NY, USA, 567–572. Google ScholarDigital Library
    19. Pnueli, Y., and Bruckstein, A. 1996. Gridless half-toning: A reincarnation of the old method. 38–64.Google Scholar
    20. Secord, A. 2002. Weighted voronoi stippling. In NPAR ’02: Proceedings of the 2nd international symposium on Non-photorealistic animation and rendering, ACM, New York, NY, USA, 37–43. Google ScholarDigital Library
    21. Shaked, D., Arad, N., Fitzhugh, A., and Sobel, I. 1996. Color diffusion: Error-diffusion for color halftones. HP Labs Tech. Report HPL-96-128R1.Google Scholar
    22. Ulichney, R. A. 1987. Digital Halftoning. MIT Press, Cambridge, MA. Google ScholarDigital Library
    23. Verevka, O., and Buchanan, J. W. 1999. Halftoning with image-based dither screens. In Proceedings of the 1999 conference on Graphics interface ’99, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 167–174. Google ScholarDigital Library
    24. Wang, Z., Bovik, A., Sheikh, H., and Simoncelli, E., 2004. Image quality assessment: From error visibility to structural similarity.Google Scholar
    25. Zhou, B., and Fang, X. 2003. Improving mid-tone quality of variable-coefficient error diffusion using threshold modulation. In SIGGRAPH ’03: ACM SIGGRAPH 2003 Papers, ACM, New York, NY, USA, 437–444. Google ScholarDigital Library

ACM Digital Library Publication: