research-article

Structure-aware error diffusion

Authors:

Jianghao Chang,

Victor OstromoukhovAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 28, Issue 5

Pages 1 - 8

https://doi.org/10.1145/1618452.1618508

Published: 01 December 2009 Publication History

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.

Supplementary Material

Supplemental material. (162-chang.zip)

Download
16.95 MB

References

[1]

Analoui, M., and Allebach, J. P. 1992. Model based halftoning using direct binary search. SPIE 1666, 96--108.

[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.

Digital 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.

[4]

Bracewell, R. N. 1980. Fourier Transform and Its Applications. McGraw-Hill Education.

[5]

Eschbach, R., and Knox, K. T. 1991. Error-diffusion algorithm with edge enhancement. JOSA (A) 8, 12, 1844--1850.

[6]

Floyd, R. W., and Steinberg, L. 1976. An adaptive algorithm for spatial grey scale. Proc. Soc. Inf. Display 17, 75--77.

[7]

Gabor, D. 1946. Theory of communication. JIEE 93, 3, 429--459.

[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.

[9]

Jahne, B. 2004. Practical Handbook on Image Processing for Scientific and Technical Applications, Second Edition. CRC Press, Inc., Boca Raton, FL, USA.

Digital 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.

Digital Library

[11]

Kang, H. 1999. Digital Color Halftoning. SPIE Press.

Digital Library

[12]

Knox, K. T. 1989. Edge enhancement in error diffusion. In Advance Printing of Paper Summaries, SPSE's 42nd Annual Conference, 310--313.

[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.

Digital Library

[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.

[15]

Marcu, G., and Abe, S. 1996. Halftoning by back error compensation. IS&T NIP 12, 132--135.

[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.

Digital 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.

Digital 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.

[19]

Pharr, M., and Humphreys, G. 2004. Physically Based Rendering: From Theory to Implementation. Morgan Kaufmann.

Digital Library

[20]

Sharma, G. 2002. Digital Color Imaging Handbook. CRC Press, Inc., Boca Raton, FL, USA.

Digital 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.

Digital Library

[22]

Turner, M. R. 1986. Texture discrimination by gabor functions. Biol. Cybern. 55, 2--3, 71--82.

Digital Library

[23]

Ulichney, R. 1987. Digital Halftoning. MIT Press.

Digital 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.

Digital 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.

[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.

Digital Library

Cited By

Jiang HXiong DJiang XDing LChen LHuang K(2023)Efficient Halftoning via Deep Reinforcement LearningIEEE Transactions on Image Processing10.1109/TIP.2023.331893732(5494-5508)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1109/TIP.2023.3318937
Tsai MWu HLin D(2023)Auto ROI & mask R-CNN model for QR code beautification (ARM-QR)Multimedia Systems10.1007/s00530-022-01046-x29:3(1245-1276)Online publication date: 25-Jan-2023
https://doi.org/10.1007/s00530-022-01046-x
Morsy MBrunton AUrban P(2022)Shape dithering for 3D printingACM Transactions on Graphics10.1145/3528223.353012941:4(1-12)Online publication date: Jul-2022
https://doi.org/10.1145/3528223.3530129
Show More Cited By

Index Terms

Structure-aware error diffusion
1. Computing methodologies
  1. Artificial intelligence
    1. Computer vision
      1. Computer vision representations
        Image representations
  2. Computer graphics
    1. Image manipulation

Recommendations

Structure-aware error diffusion
SIGGRAPH Asia '09: ACM SIGGRAPH Asia 2009 papers

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 ...
Hierarchical error diffusion

This paper develops a distinctive class of color error diffusion algorithm, called hierarchical error diffusion (HED). It aims to achieve perceptually pleasing color halftone through neither conventional joint quantization nor interchannel error ...
Halftone image resampling by interpolation and error-diffusion
ICUIMC '08: Proceedings of the 2nd international conference on Ubiquitous information management and communication

Halftoning schemes are developed for reserving the quality after transforming continuous tone images to binary images under human vision. It is wildly used in printing and outputting. So far most of halftoning schemes focus on the algorithms for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 28, Issue 5

December 2009

646 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/1618452

Issue’s Table of Contents

Copyright © 2009 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 2009

Published in TOG Volume 28, Issue 5

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

33
Total Citations
View Citations
760
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jiang HXiong DJiang XDing LChen LHuang K(2023)Efficient Halftoning via Deep Reinforcement LearningIEEE Transactions on Image Processing10.1109/TIP.2023.331893732(5494-5508)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1109/TIP.2023.3318937
Tsai MWu HLin D(2023)Auto ROI & mask R-CNN model for QR code beautification (ARM-QR)Multimedia Systems10.1007/s00530-022-01046-x29:3(1245-1276)Online publication date: 25-Jan-2023
https://doi.org/10.1007/s00530-022-01046-x
Morsy MBrunton AUrban P(2022)Shape dithering for 3D printingACM Transactions on Graphics10.1145/3528223.353012941:4(1-12)Online publication date: Jul-2022
https://doi.org/10.1145/3528223.3530129
Chizhov VGeorgiev IMyszkowski KSingh G(2022)Perceptual Error Optimization for Monte Carlo RenderingACM Transactions on Graphics10.1145/350400241:3(1-17)Online publication date: 7-Mar-2022
https://dl.acm.org/doi/10.1145/3504002
Jiang HXiong DJiang XYin ADing LHuang K(2022)Halftoning with Multi-Agent Deep Reinforcement Learning2022 IEEE International Conference on Image Processing (ICIP)10.1109/ICIP46576.2022.9897198(641-645)Online publication date: 16-Oct-2022
https://doi.org/10.1109/ICIP46576.2022.9897198
Abedini FGooran SKitanovski VNyström D(2021)Structure-Aware Halftoning Using the Iterative Method Controlling the Dot PlacementJournal of Imaging Science and Technology10.2352/J.ImagingSci.Technol.2021.65.6.06040465:6(060404-1-060404-14)Online publication date: 1-Nov-2021
https://doi.org/10.2352/J.ImagingSci.Technol.2021.65.6.060404
Yoo ILuo XWang YYang FMilanfar P(2020)GIFnets: Differentiable GIF Encoding Framework2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)10.1109/CVPR42600.2020.01448(14461-14470)Online publication date: Jun-2020
https://doi.org/10.1109/CVPR42600.2020.01448
Azami RDoyle LMould DJorge JBartram LCatalano CKaplan CForbes ADiVerdi S(2019)Stipple removal in extreme-tone regionsProceedings of the 8th ACM/Eurographics Expressive Symposium on Computational Aesthetics and Sketch Based Interfaces and Modeling and Non-Photorealistic Animation and Rendering10.2312/exp.20191083(123-132)Online publication date: 5-May-2019
https://dl.acm.org/doi/10.2312/exp.20191083
Tsai MHsieh C(2019)The visual color QR code algorithm (DWT-QR) based on wavelet transform and human vision systemMultimedia Tools and Applications10.1007/s11042-019-7308-yOnline publication date: 19-Mar-2019
https://doi.org/10.1007/s11042-019-7308-y
Je SAbileva YBianchi ABazin J(2019)A computational approach for spider web‐inspired fabrication of string artComputer Animation and Virtual Worlds10.1002/cav.190430:3-4Online publication date: 26-Jun-2019
https://doi.org/10.1002/cav.1904
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents