Abstract

We present a clustered-minority-pixel error-diffusion halftoning algorithm for which the quantizer threshold is modified on the basis of the past output and a dot activation map. Dot area, dot shape, and dot distribution are more controllable than with other clustered-dot halftone algorithms such as Levien’s algorithm. This method also effectively reduces structured mazelike artifacts in midtones that occur in Levien’s algorithm. The dot distribution is further improved by using different error-diffusion weights for different input gray levels.

© 2004 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. R. W. Floyd, L. Steinberg, “An adaptive algorithm for spatial greyscale,” Proc. Soc. Inf. Display 17, 75–77 (1976).
  2. R. Levien, “Output dependent feedback in error diffusion halftoning,” in Proceedings of IS&T’s 46th Annual Conference (The Society for Imaging Science and Technology, Springfield, Va., 1993), pp. 115–118.
  3. D. L. Lau, G. R. Arce, N. C. Gallagher, “Green-noise digital halftoning,” Proc. IEEE 86, 2424–2442 (1998).
    [CrossRef]
  4. D. L. Lau, G. R. Arce, N. C. Gallagher, “Digital color halftoning with generalized error diffusion and multichannel green-noise masks,” IEEE Trans. Image Process. 9, 923–935 (2000).
    [CrossRef]
  5. D. L. Lau, G. R. Arce, N. C. Gallagher, “Digital halftoning by means of green-noise masks,” J. Opt. Soc. Am. A 16, 1575–1586 (1999).
    [CrossRef]
  6. R. Eschbach, “Pixel-based error-diffusion algorithm for producing clustered halftone dots,” J. Electron. Imaging 3, 198–202 (1994).
    [CrossRef]
  7. Z. Fan, “Method combining error diffusion and traditional halftoning with arbitrary screen orientation,” U.S. patent5,493,416 (February20, 1996).
  8. A. Moolenaar, P. A. M. Cornelissen, “Method and image reproduction device for reproducing grey values using a combination of error diffusion and cluster dithering for enhanced resolution and tone,” U.S. patent5,818,971 (October6, 1998).
  9. N. Damera-Venkata, B. L. Evans, “FM halftoning via block error diffusion,” in Proceedings of the IEEE International Conference on Image Processing (Institute of Electrical and Electronics Engineers, New York, 2001), Vol. 1, pp. 1081–1084.
  10. R. Eschbach, “High addressability error diffusion with minimum mark size,” U.S. patent5,374,997 (December20, 1994).
  11. S. A. Schweid, “System and apparatus for single subpixel elimination with local error compensation in an high addressable error diffusion process,” U.S. patent6,353,687 (March5, 2002).
  12. C. Billotet-Hoffmann, O. Bryngdahl, “On the error diffusion technique for electronic halftoning,” Proc. Soc. Inf. Display 24, 253–258 (1983).
  13. R. L. Miller, C. M. Smith, “Image processor with error diffusion modulated threshold matrix,” U.S. patent5,150,429 (September22, 1992).
  14. M. Analoui, J. P. Allebach, “Model-based halftoning using direct binary search,” in Human Vision, Visual Processing, and Digital Display III, B. E. Rogowitz, ed., Proc. SPIE1666, 96–108 (1992).
    [CrossRef]
  15. D. J. Lieberman, J. P. Allebach, “Efficient model based halftoning using direct binary search,” in Proceedings of 1997 IEEE International Conference on Image Processing (Institute of Electrical and Electronics Engineers, New York, 1997), Vol. 1, pp. 775–778.
  16. D. J. Lieberman, J. P. Allebach, “A dual interpretation for direct binary search and its implications for tone reproduction and texture quality,” IEEE Trans. Image Process. 9, 1950–1963 (2000).
    [CrossRef]
  17. R. Eschbach, “Reduction of artifacts in error diffusion by means of input-dependent weights,” J. Electron. Imaging 2, 352–358 (1993).
    [CrossRef]
  18. J. Shu, “Adaptive filtering for error diffusion quality improvement,” in SID Digest of Technical Papers (Society for Information Display, San Jose, Calif., 1995), pp. 833–836.
  19. V. Ostromoukhov, “Enhanced error-diffusion method for color or black-and-white reproduction,” U.S. patent5,737,453 (April7, 1998).
  20. V. Ostromoukhov, “A simple and efficient error-diffusion algorithm,” in Proceedings of SIGGRAPH 2001, Computer Graphics Proceedings, Annual Conference Series (Association for Computing Machinery, New York, 2001), pp. 567–572.
  21. P. Li, J. P. Allebach, “Tone-dependent error diffusion,” IEEE Trans. Image Process. 13, 201–205 (2004).
    [CrossRef] [PubMed]
  22. P. Li, J. P. Allebach, “Tone dependent error diffusion,” U.S. patent6,563,957 (May13, 2003).
  23. R. Näsänen, “Visibility of halftone dot textures,” IEEE Trans. Syst. Man Cybern. 14, 920–924 (1984).
    [CrossRef]
  24. A. Hurwitz, “Sur le problème des isopérimètres,” C. R. Acad. Sci. Paris 132, 401–403 (1901).

2004 (1)

P. Li, J. P. Allebach, “Tone-dependent error diffusion,” IEEE Trans. Image Process. 13, 201–205 (2004).
[CrossRef] [PubMed]

2000 (2)

D. L. Lau, G. R. Arce, N. C. Gallagher, “Digital color halftoning with generalized error diffusion and multichannel green-noise masks,” IEEE Trans. Image Process. 9, 923–935 (2000).
[CrossRef]

D. J. Lieberman, J. P. Allebach, “A dual interpretation for direct binary search and its implications for tone reproduction and texture quality,” IEEE Trans. Image Process. 9, 1950–1963 (2000).
[CrossRef]

1999 (1)

1998 (1)

D. L. Lau, G. R. Arce, N. C. Gallagher, “Green-noise digital halftoning,” Proc. IEEE 86, 2424–2442 (1998).
[CrossRef]

1994 (1)

R. Eschbach, “Pixel-based error-diffusion algorithm for producing clustered halftone dots,” J. Electron. Imaging 3, 198–202 (1994).
[CrossRef]

1993 (1)

R. Eschbach, “Reduction of artifacts in error diffusion by means of input-dependent weights,” J. Electron. Imaging 2, 352–358 (1993).
[CrossRef]

1984 (1)

R. Näsänen, “Visibility of halftone dot textures,” IEEE Trans. Syst. Man Cybern. 14, 920–924 (1984).
[CrossRef]

1983 (1)

C. Billotet-Hoffmann, O. Bryngdahl, “On the error diffusion technique for electronic halftoning,” Proc. Soc. Inf. Display 24, 253–258 (1983).

1976 (1)

R. W. Floyd, L. Steinberg, “An adaptive algorithm for spatial greyscale,” Proc. Soc. Inf. Display 17, 75–77 (1976).

1901 (1)

A. Hurwitz, “Sur le problème des isopérimètres,” C. R. Acad. Sci. Paris 132, 401–403 (1901).

Allebach, J. P.

P. Li, J. P. Allebach, “Tone-dependent error diffusion,” IEEE Trans. Image Process. 13, 201–205 (2004).
[CrossRef] [PubMed]

D. J. Lieberman, J. P. Allebach, “A dual interpretation for direct binary search and its implications for tone reproduction and texture quality,” IEEE Trans. Image Process. 9, 1950–1963 (2000).
[CrossRef]

M. Analoui, J. P. Allebach, “Model-based halftoning using direct binary search,” in Human Vision, Visual Processing, and Digital Display III, B. E. Rogowitz, ed., Proc. SPIE1666, 96–108 (1992).
[CrossRef]

D. J. Lieberman, J. P. Allebach, “Efficient model based halftoning using direct binary search,” in Proceedings of 1997 IEEE International Conference on Image Processing (Institute of Electrical and Electronics Engineers, New York, 1997), Vol. 1, pp. 775–778.

P. Li, J. P. Allebach, “Tone dependent error diffusion,” U.S. patent6,563,957 (May13, 2003).

Analoui, M.

M. Analoui, J. P. Allebach, “Model-based halftoning using direct binary search,” in Human Vision, Visual Processing, and Digital Display III, B. E. Rogowitz, ed., Proc. SPIE1666, 96–108 (1992).
[CrossRef]

Arce, G. R.

D. L. Lau, G. R. Arce, N. C. Gallagher, “Digital color halftoning with generalized error diffusion and multichannel green-noise masks,” IEEE Trans. Image Process. 9, 923–935 (2000).
[CrossRef]

D. L. Lau, G. R. Arce, N. C. Gallagher, “Digital halftoning by means of green-noise masks,” J. Opt. Soc. Am. A 16, 1575–1586 (1999).
[CrossRef]

D. L. Lau, G. R. Arce, N. C. Gallagher, “Green-noise digital halftoning,” Proc. IEEE 86, 2424–2442 (1998).
[CrossRef]

Billotet-Hoffmann, C.

C. Billotet-Hoffmann, O. Bryngdahl, “On the error diffusion technique for electronic halftoning,” Proc. Soc. Inf. Display 24, 253–258 (1983).

Bryngdahl, O.

C. Billotet-Hoffmann, O. Bryngdahl, “On the error diffusion technique for electronic halftoning,” Proc. Soc. Inf. Display 24, 253–258 (1983).

Cornelissen, P. A. M.

A. Moolenaar, P. A. M. Cornelissen, “Method and image reproduction device for reproducing grey values using a combination of error diffusion and cluster dithering for enhanced resolution and tone,” U.S. patent5,818,971 (October6, 1998).

Damera-Venkata, N.

N. Damera-Venkata, B. L. Evans, “FM halftoning via block error diffusion,” in Proceedings of the IEEE International Conference on Image Processing (Institute of Electrical and Electronics Engineers, New York, 2001), Vol. 1, pp. 1081–1084.

Eschbach, R.

R. Eschbach, “Pixel-based error-diffusion algorithm for producing clustered halftone dots,” J. Electron. Imaging 3, 198–202 (1994).
[CrossRef]

R. Eschbach, “Reduction of artifacts in error diffusion by means of input-dependent weights,” J. Electron. Imaging 2, 352–358 (1993).
[CrossRef]

R. Eschbach, “High addressability error diffusion with minimum mark size,” U.S. patent5,374,997 (December20, 1994).

Evans, B. L.

N. Damera-Venkata, B. L. Evans, “FM halftoning via block error diffusion,” in Proceedings of the IEEE International Conference on Image Processing (Institute of Electrical and Electronics Engineers, New York, 2001), Vol. 1, pp. 1081–1084.

Fan, Z.

Z. Fan, “Method combining error diffusion and traditional halftoning with arbitrary screen orientation,” U.S. patent5,493,416 (February20, 1996).

Floyd, R. W.

R. W. Floyd, L. Steinberg, “An adaptive algorithm for spatial greyscale,” Proc. Soc. Inf. Display 17, 75–77 (1976).

Gallagher, N. C.

D. L. Lau, G. R. Arce, N. C. Gallagher, “Digital color halftoning with generalized error diffusion and multichannel green-noise masks,” IEEE Trans. Image Process. 9, 923–935 (2000).
[CrossRef]

D. L. Lau, G. R. Arce, N. C. Gallagher, “Digital halftoning by means of green-noise masks,” J. Opt. Soc. Am. A 16, 1575–1586 (1999).
[CrossRef]

D. L. Lau, G. R. Arce, N. C. Gallagher, “Green-noise digital halftoning,” Proc. IEEE 86, 2424–2442 (1998).
[CrossRef]

Hurwitz, A.

A. Hurwitz, “Sur le problème des isopérimètres,” C. R. Acad. Sci. Paris 132, 401–403 (1901).

Lau, D. L.

D. L. Lau, G. R. Arce, N. C. Gallagher, “Digital color halftoning with generalized error diffusion and multichannel green-noise masks,” IEEE Trans. Image Process. 9, 923–935 (2000).
[CrossRef]

D. L. Lau, G. R. Arce, N. C. Gallagher, “Digital halftoning by means of green-noise masks,” J. Opt. Soc. Am. A 16, 1575–1586 (1999).
[CrossRef]

D. L. Lau, G. R. Arce, N. C. Gallagher, “Green-noise digital halftoning,” Proc. IEEE 86, 2424–2442 (1998).
[CrossRef]

Levien, R.

R. Levien, “Output dependent feedback in error diffusion halftoning,” in Proceedings of IS&T’s 46th Annual Conference (The Society for Imaging Science and Technology, Springfield, Va., 1993), pp. 115–118.

Li, P.

P. Li, J. P. Allebach, “Tone-dependent error diffusion,” IEEE Trans. Image Process. 13, 201–205 (2004).
[CrossRef] [PubMed]

P. Li, J. P. Allebach, “Tone dependent error diffusion,” U.S. patent6,563,957 (May13, 2003).

Lieberman, D. J.

D. J. Lieberman, J. P. Allebach, “A dual interpretation for direct binary search and its implications for tone reproduction and texture quality,” IEEE Trans. Image Process. 9, 1950–1963 (2000).
[CrossRef]

D. J. Lieberman, J. P. Allebach, “Efficient model based halftoning using direct binary search,” in Proceedings of 1997 IEEE International Conference on Image Processing (Institute of Electrical and Electronics Engineers, New York, 1997), Vol. 1, pp. 775–778.

Miller, R. L.

R. L. Miller, C. M. Smith, “Image processor with error diffusion modulated threshold matrix,” U.S. patent5,150,429 (September22, 1992).

Moolenaar, A.

A. Moolenaar, P. A. M. Cornelissen, “Method and image reproduction device for reproducing grey values using a combination of error diffusion and cluster dithering for enhanced resolution and tone,” U.S. patent5,818,971 (October6, 1998).

Näsänen, R.

R. Näsänen, “Visibility of halftone dot textures,” IEEE Trans. Syst. Man Cybern. 14, 920–924 (1984).
[CrossRef]

Ostromoukhov, V.

V. Ostromoukhov, “Enhanced error-diffusion method for color or black-and-white reproduction,” U.S. patent5,737,453 (April7, 1998).

V. Ostromoukhov, “A simple and efficient error-diffusion algorithm,” in Proceedings of SIGGRAPH 2001, Computer Graphics Proceedings, Annual Conference Series (Association for Computing Machinery, New York, 2001), pp. 567–572.

Schweid, S. A.

S. A. Schweid, “System and apparatus for single subpixel elimination with local error compensation in an high addressable error diffusion process,” U.S. patent6,353,687 (March5, 2002).

Shu, J.

J. Shu, “Adaptive filtering for error diffusion quality improvement,” in SID Digest of Technical Papers (Society for Information Display, San Jose, Calif., 1995), pp. 833–836.

Smith, C. M.

R. L. Miller, C. M. Smith, “Image processor with error diffusion modulated threshold matrix,” U.S. patent5,150,429 (September22, 1992).

Steinberg, L.

R. W. Floyd, L. Steinberg, “An adaptive algorithm for spatial greyscale,” Proc. Soc. Inf. Display 17, 75–77 (1976).

C. R. Acad. Sci. Paris (1)

A. Hurwitz, “Sur le problème des isopérimètres,” C. R. Acad. Sci. Paris 132, 401–403 (1901).

IEEE Trans. Image Process. (3)

P. Li, J. P. Allebach, “Tone-dependent error diffusion,” IEEE Trans. Image Process. 13, 201–205 (2004).
[CrossRef] [PubMed]

D. L. Lau, G. R. Arce, N. C. Gallagher, “Digital color halftoning with generalized error diffusion and multichannel green-noise masks,” IEEE Trans. Image Process. 9, 923–935 (2000).
[CrossRef]

D. J. Lieberman, J. P. Allebach, “A dual interpretation for direct binary search and its implications for tone reproduction and texture quality,” IEEE Trans. Image Process. 9, 1950–1963 (2000).
[CrossRef]

IEEE Trans. Syst. Man Cybern. (1)

R. Näsänen, “Visibility of halftone dot textures,” IEEE Trans. Syst. Man Cybern. 14, 920–924 (1984).
[CrossRef]

J. Electron. Imaging (2)

R. Eschbach, “Reduction of artifacts in error diffusion by means of input-dependent weights,” J. Electron. Imaging 2, 352–358 (1993).
[CrossRef]

R. Eschbach, “Pixel-based error-diffusion algorithm for producing clustered halftone dots,” J. Electron. Imaging 3, 198–202 (1994).
[CrossRef]

J. Opt. Soc. Am. A (1)

Proc. IEEE (1)

D. L. Lau, G. R. Arce, N. C. Gallagher, “Green-noise digital halftoning,” Proc. IEEE 86, 2424–2442 (1998).
[CrossRef]

Proc. Soc. Inf. Display (2)

R. W. Floyd, L. Steinberg, “An adaptive algorithm for spatial greyscale,” Proc. Soc. Inf. Display 17, 75–77 (1976).

C. Billotet-Hoffmann, O. Bryngdahl, “On the error diffusion technique for electronic halftoning,” Proc. Soc. Inf. Display 24, 253–258 (1983).

Other (13)

R. L. Miller, C. M. Smith, “Image processor with error diffusion modulated threshold matrix,” U.S. patent5,150,429 (September22, 1992).

M. Analoui, J. P. Allebach, “Model-based halftoning using direct binary search,” in Human Vision, Visual Processing, and Digital Display III, B. E. Rogowitz, ed., Proc. SPIE1666, 96–108 (1992).
[CrossRef]

D. J. Lieberman, J. P. Allebach, “Efficient model based halftoning using direct binary search,” in Proceedings of 1997 IEEE International Conference on Image Processing (Institute of Electrical and Electronics Engineers, New York, 1997), Vol. 1, pp. 775–778.

J. Shu, “Adaptive filtering for error diffusion quality improvement,” in SID Digest of Technical Papers (Society for Information Display, San Jose, Calif., 1995), pp. 833–836.

V. Ostromoukhov, “Enhanced error-diffusion method for color or black-and-white reproduction,” U.S. patent5,737,453 (April7, 1998).

V. Ostromoukhov, “A simple and efficient error-diffusion algorithm,” in Proceedings of SIGGRAPH 2001, Computer Graphics Proceedings, Annual Conference Series (Association for Computing Machinery, New York, 2001), pp. 567–572.

R. Levien, “Output dependent feedback in error diffusion halftoning,” in Proceedings of IS&T’s 46th Annual Conference (The Society for Imaging Science and Technology, Springfield, Va., 1993), pp. 115–118.

Z. Fan, “Method combining error diffusion and traditional halftoning with arbitrary screen orientation,” U.S. patent5,493,416 (February20, 1996).

A. Moolenaar, P. A. M. Cornelissen, “Method and image reproduction device for reproducing grey values using a combination of error diffusion and cluster dithering for enhanced resolution and tone,” U.S. patent5,818,971 (October6, 1998).

N. Damera-Venkata, B. L. Evans, “FM halftoning via block error diffusion,” in Proceedings of the IEEE International Conference on Image Processing (Institute of Electrical and Electronics Engineers, New York, 2001), Vol. 1, pp. 1081–1084.

R. Eschbach, “High addressability error diffusion with minimum mark size,” U.S. patent5,374,997 (December20, 1994).

S. A. Schweid, “System and apparatus for single subpixel elimination with local error compensation in an high addressable error diffusion process,” U.S. patent6,353,687 (March5, 2002).

P. Li, J. P. Allebach, “Tone dependent error diffusion,” U.S. patent6,563,957 (May13, 2003).

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (18)

Fig. 1
Fig. 1

Typical error-diffusion system.

Fig. 2
Fig. 2

Halftone image generated by using Floyd–Steinberg error diffusion.

Fig. 3
Fig. 3

Error-diffusion system with hysteresis.

Fig. 4
Fig. 4

Halftone image generated by use of Levien error diffusion with h[-1, 0]=h[0, -1]=0.5 and w[0, 1]=w[1, 0]=0.5.

Fig. 5
Fig. 5

Halftone image generated by using Levien error diffusion with h[-1, 0]=h[0, -1]=1.0 and w[0, 1]=0.6, w[1, 0]=0.4.

Fig. 6
Fig. 6

Clustered-minority-pixel error diffusion.

Fig. 7
Fig. 7

Halftone image generated by using CMPED with 2×2 dot activation regions.

Fig. 8
Fig. 8

Dot activation map with 2×2 dot activation regions.

Fig. 9
Fig. 9

Halftone image generated by using CMPED with 3×3 dot activation regions.

Fig. 10
Fig. 10

Dot activation map with 3×3 dot activation regions.

Fig. 11
Fig. 11

Halftone image generated by using CMPED with only dot activation feedback. The dot activation regions are 3×3.

Fig. 12
Fig. 12

Tone-dependent weights for CMPED with 2×2 dot activation regions.

Fig. 13
Fig. 13

Tone-dependent weights for CMPED with 3×3 dot activation regions.

Fig. 14
Fig. 14

Halftone image generated by using TD-CMPED with 2×2 dot activation regions.

Fig. 15
Fig. 15

Halftone image generated by using TD-CMPED with 3×3 dot activation regions.

Fig. 16
Fig. 16

Cluster area A¯(a) as a function of gray level a for different halftoning methods: (a) large-scale plot, (b) small-scale plot.

Fig. 17
Fig. 17

Standard deviation σA(a) of cluster area as a function of gray level a for different halftoning methods: (a) large-scale plot, (b) small-scale plot.

Fig. 18
Fig. 18

Eccentricity ¯(a) as a function of gray level a for different halftoning methods: (a) large-scale plot, (b) small-scale plot.  

Tables (1)

Tables Icon

Table 1 Cluster Statistics for Different Halftoning Methods

Equations (28)

Equations on this page are rendered with MathJax. Learn more.

g[m, n]=1ifu[m, n]T0otherwise.
d[m, n]=g[m, n]-u[m, n].
u[m+k, n+l]u[m+k, n+l]-w[k, l]d[m, n],
u[m, n]=f[m, n]-k,lw[k, l]d[m-k, n-l].
g[m, n]
=1ifu[m, n]+k,lh[k, l]g[m-k, n-l]T0otherwise,
ψm,n={[k, l] :0k-m1,0l-n1}
ψm,n={[k, l] :0k-m2,0l-n2},
H(u¯, v¯)=exp-180πu¯2+v¯2c ln(L)+d,
phvs(x, y)=1D2 hxD, yD.
e[m, n]=g[m, n]-f[m, n],
e˜(x, y)=mne[m, n]p˜(x-mX, y-nX),
E=|e˜(x, y)|2dxdy.
E=mne[m, n]cp˜e˜[m, n],
A¯=NumberofminoritypixelsNumberofdotactivationregions.
pcluster(x, y)=1if-A/2x, yA/20otherwise.
=kl[|Yˆ[k, l]|-|Sˆ[k, l]|]2.
A=ρ2smin2,
P=2(ρ2+1)smin.
=P/ 4A  .
=12ρ2+1ρ=12ρ+1ρ.
ddρ=121-1ρ2.
v[m, n]=1iff[m, n]0.50otherwise.
g[m, n]=1ifu[m, n]+k,lh[k, l]g[m-k, n-l]+αv[m, n]T0otherwise.
ψm,n={[m, n], [m+1, n], [m, n+1], [m+1][n+1]}
ψm,n={[m, n], [m+1, n], [m, n-1], [m+1][n-1]}.
N(v(i))={(w[0, 1; a], w[1, 0; a]):|w[k, l]-w(i)[k, l]|=0, 0.01}.
w[k, l; a]=w[k, l; 1-a].

Metrics