“Structure-aware error diffusion”
Conference:
Type(s):
Title:
- Structure-aware error diffusion
Session/Category Title: Perception
Presenter(s)/Author(s):
Moderator(s):
Abstract:
We present an original error-diffusion method which produces visually pleasant halftone images while preserving fine details and visually identifiable structures present in the original images. Our method is conceptually simple and computationally efficient. The source image is analyzed, and its local frequency content is detected. The main component of the frequency content (main frequency, orientation and contrast) serve as lookup table indices to a pre-calculated database of modifications to a standard error diffusion. The modifications comprise threshold modulation and variation of error-diffusion coefficients. The whole system is calibrated in such a way that the produced halftone images are visually close to the original images (patches of constant intensity, patches containing sinusoidal waves of different frequencies/orientations/contrasts, as well as natural images of different origins). Our system produces images of visual quality comparable to that presented in [Pang et al. 2008], but much faster. When processing typical images of linear size of several hundreds of pixels, our error-diffusion system is two to three orders of magnitude faster than [Pang et al. 2008]. Thanks to its speed combined with high visual quality, our error-diffusion algorithm can be used in many practical applications which may require digital halftoning: printing, visualization, geometry processing, various sampling techniques, etc.
References:
1. Analoui, M., and Allebach, J. P. 1992. Model based halftoning using direct binary search. SPIE 1666, 96–108.Google Scholar
2. Baqai, F. A., Taylor, C. C., and Allebach, J. P. 2003. Halftoning via direct binary search using analytical and stochastic printer models. IEEE Trans. Image Processing 12, 1–15. Google ScholarDigital Library
3. Bayer, B. E. 1973. An optimum method for two-level rendition of continuous-tone pictures. IEEE Intl. Conf. on Communications 1, 2611–2615.Google Scholar
4. Bracewell, R. N. 1980. Fourier Transform and Its Applications. McGraw-Hill Education.Google Scholar
5. Eschbach, R., and Knox, K. T. 1991. Error-diffusion algorithm with edge enhancement. JOSA (A) 8, 12, 1844–1850.Google ScholarCross Ref
6. Floyd, R. W., and Steinberg, L. 1976. An adaptive algorithm for spatial grey scale. Proc. Soc. Inf. Display 17, 75–77.Google Scholar
7. Gabor, D. 1946. Theory of communication. JIEE 93, 3, 429–459.Google Scholar
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. Jahne, B. 2004. Practical Handbook on Image Processing for Scientific and Technical Applications, Second Edition. CRC Press, Inc., Boca Raton, FL, USA. Google ScholarDigital Library
10. Kang, H., Lee, S., and Chui, C. K. 2009. Flow-based image abstraction. IEEE Transactions on Visualization and Computer Graphics 15, 1, 62–76. Google ScholarDigital Library
11. Kang, H. 1999. Digital Color Halftoning. SPIE Press. Google ScholarDigital Library
12. Knox, K. T. 1989. Edge enhancement in error diffusion. In Advance Printing of Paper Summaries, SPSE’s 42nd Annual Conference, 310–313.Google Scholar
13. 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
14. Lee, C., and Allebach, J. P. 2007. The hybrid screen: improving the breed. SPIE, R. Eschbach and G. G. Marcu, Eds., vol. 6493, 649318.Google Scholar
15. Marcu, G., and Abe, S. 1996. Halftoning by back error compensation. IS&T NIP 12, 132–135.Google Scholar
16. Ostromoukhov, V. 2001. A simple and efficient error-diffusion algorithm. In Proceedings of ACM SIGGRAPH 2001, Computer Graphics Proceedings, Annual Conference Series, 567–572. Google ScholarDigital Library
17. Pang, W.-M., Qu, Y., Wong, T.-T., Cohen-Or, D., and Heng, P.-A. 2008. Structure-aware halftoning. ACM Transactions on Graphics 27, 3 (Aug.), 89:1–89:8. Google ScholarDigital Library
18. Pappas, T. N., Allebach, J. P., and Neuhoff, D. L. 2003. Model-Based Digital Halftoning. IEEE Signal Processing Magazine 20, 4, 14–27.Google ScholarCross Ref
19. Pharr, M., and Humphreys, G. 2004. Physically Based Rendering: From Theory to Implementation. Morgan Kaufmann. Google ScholarDigital Library
20. Sharma, G. 2002. Digital Color Imaging Handbook. CRC Press, Inc., Boca Raton, FL, USA. Google ScholarDigital Library
21. Simoncelli, E. P., and Freeman, W. T. 1995. The steerable pyramid: A flexible architecture for multi-scale derivative computation. In Proc 2nd IEEE Int’l Conf on Image Proc, IEEE Sig Proc Society, Washington, DC, vol. III, 444–447. Google ScholarDigital Library
22. Turner, M. R. 1986. Texture discrimination by gabor functions. Biol. Cybern. 55, 2–3, 71–82. Google ScholarDigital Library
23. Ulichney, R. 1987. Digital Halftoning. MIT Press. Google ScholarDigital Library
24. Wang, Z., Bovik, A., Sheikh, H., and Simoncelli, E. 2004. Image quality assessment: from error visibility to structural similarity. IEEE Transactions on Image Processing 13, 4, 600–612. Google ScholarDigital Library
25. Wyszecki, G., and Stiles, W. S. 2000. Color Science: Concepts and Methods, Quantitative Data and Formulae (Wiley Series in Pure and Applied Optics), 2 ed. Wiley-Interscience.Google Scholar
26. Zhou, B., and Fang, X. 2003. Improving mid-tone quality of variable-coefficient error diffusion using threshold modulation. ACM Transactions on Graphics 22, 3, 437–444. Google ScholarDigital Library
