Optimization of kernel weights for error diffusion halftoning method
V.A. Fedoseev

PDF, 406 kB

Full text of article: Russian language.

DOI: 10.18287/0134-2452-2013-37-3-368-376

Pages: 368-375.

Abstract:
This paper describes a study to find the best error diffusion kernel for halftone screening under various restrictions on the number of non-zero coefficients and their set of values. As an objective measure of quality WSNR was used. The problem of multidimensional optimization was solved numerically using several well-known algorithms: Nelder–Mead, BFGS, etc. The study found a kernel function that provides a quality gain of about 5% in comparison with the best of the commonly used kernel introduced by Floyd and Steinberg. Other obtained kernels allows to significantly reduce the computational complexity of the algorithm without reducing its quality. Since the method of error diffusion, significantly outperforming the methods used in the printing industry by quality, though not widely used in this area because of the relatively low speed, the results obtained in this work can contribute to improving its use.

Key words:
digital halftoning, errod diffusion, Floyd-Steinberg algorithm, Jarvis algorithm, contrast sensitivity function, WSNR, multidimensional optimization, Nelder–Mead method.

References:

  1. Kipphan, H. Handbuch der Printmedien / H. Kipphan. – Heidelberg: Springer, 2000. – 1280 p.
  2. Lau, D.L. Modern digital halftoning / D.L. Lau, G.R. Arce. – CRC Press, 2011.
  3. Soifer, V.A. Computer Image Processing, Part I: Basic concepts and theory / V.V. Myasnikov, S.B. Popov, V.V. Sergey­ev, V.A. Soifer; ed. by V.A. Soifer. – VDM Verlag, 2010. – 296 p.
  4. Knuth, D.E. Digital halftones by dot diffusion / D.E. Knuth // ACM Transactions on Graphics. – 1987. – Vol. 6(4). – P. 245-273.
  5. Floyd, R.W. An adaptive algorithm for spatial gray-scale / R.W. Floyd and L. Steinberg // Proceedings Society Information Display. – 1976. – Vol. 17(2). – P. 75-78.
  6. Anastassiou, D. Neural net based digital halftoning of images / D. Anastassiou. – IEEE International Symposium on Circuits and Systems 1988, 1988. – P. 507-510.
  7. Barnard, E. Optimal error diffusion for computer-genera­ted holograms / E. Barnard // JOSA A. – 1988. – Vol. 5(11). – P. 1803-1817.
  8. Ulichney, R.A. Digital Halftoning / R.A. Ulichney. – MIT Press, 1987.
  9. Jarvis, J.F. A survey of techniques for the display of continuous-tone pictures on bilevel displays / J.F. Jarvis, C.N. Judice, W.H. Ninke // Comp. Graf. Im. Pr. – 1976. – Vol. 5. – P. 13-40.
  10. Stucki, P. MECCA – a multiple-error correcting computation algorithm for bilevel image hardcopy reproduction / P. Stucki // Tech. Rep. RZ1060, Zurich, Switzerland, 1981.
  11. Velho, L. Digital halftoning with space filling curves / L. Velho, J.M. Gomes // Computer Graphics. – 1991. – Vol. 25(4). – P. 81-90.
  12. Kite, T.D. Modeling and quality assessment of halftoning by error diffusion / T.D. Kite, B.L. Evans, A.C. Bovik // IEEE Trans. Image Processing. – 2000. – Vol. 9. – P. 909-922.
  13. Axelson, P.E. Quality measures of halftoned images (a review), Master Thesis / P.E. Axelson. – Norrköping: Department of Science and Technology, Linköping University, 2003.
  14. Gonzalez, R.F. Digital Image Processing; 2nd edition / R.F. Gonzalez, R.E. Woods. – New Jersey: Prentice Hall, 2002.
  15. Nasanen, R. Visibility of halftone dot textures / R. Nasanen // IEEE Trans. Syst., Man. Cybern. – 1984. – Vol. 14(6). – P. 920-924.
  16. Waterloo Grey Set. – University of Waterloo Fractal coding and analysis group: Mayer Gregory Image Repository, 2009.  [http://links.uwaterloo.ca/Repository.html
  17. Eschbach, R. Error-diffusion algorithm with edge enhancement / R. Eschbach, K. Knox // JOSA A. – 1991. – Vol. 8(12). – P. 1844-1850.
  18. Wang, Z. A universal image quality index / Z. Wang, A.C. Bovik // Signal Processing Letters, IEEE. – 2002. – Vol. 9(3). – P. 81-84.
  19. Kolpatzik, B.W. Optimized error diffusion for image display / B.W. Kolpatzik, C.A. Bouman // Journal of Electronic Imaging. – 1992. – Vol. 1(3). – P. 277-292.
  20. Press, W.H. Numerical recipes in C+: the art of scientific computing / W.H. Press. – Cambridge: Cambridge University Press, 2009.
  21. Martin,  D. A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics / D. Martin, C. Fowlkes, D. Tal, J. Malik // Proceedings of the Eighth IEEE International Conference on Computer Vision. – 2001. –Vol. 2. – P. 416-423.
  22. Monga, V. Halftoning Toolbox for MATLAB / Vishal Monga, Niranjan Damera-Venkata, Hamood Rehman, Brian L. Evans. – [http://users.ece.utexas.edu/~bevans/ projects/halftoning/toolbox/]
© 2009, IPSI RAS
Institution of Russian Academy of Sciences, Image Processing Systems Institute of RAS, Russia, 443001, Samara, Molodogvardeyskaya Street 151; e-mail: ko@smr.ru; Phones: +7 (846 2) 332-56-22, Fax: +7 (846 2) 332-56-20