JEI Letters

Multilevel halftoning using multiscale error diffusion

[+] Author Affiliations
Yik-Hing Fung, Yuk-Hee Chan

The Hong Kong Polytechnic University, Center for Multimedia Signal Processing, Department of Electronic and Information Engineering, Hung Hom, Kowloon, Hong Kong

J. Electron. Imaging. 19(3), 030501 (August 18, 2010). doi:10.1117/1.3479749
History: Received January 29, 2010; Revised July 07, 2010; Accepted July 20, 2010; Published August 18, 2010; Online August 18, 2010
Text Size: A A A

Open Access Open Access

Advances in printing technology has made multilevel halftoning become important, as printers can now print inks of different intensities. This work presents a multilevel halftoning algorithm based on multiscale error diffusion. This algorithm takes care of constrained pixels before handling the unconstrained pixels, and diffuses errors with a noncausal filter such that halftones of better image quality can be achieved.

Figures in this Article

Multilevel halftoning (MH) is the process of converting a continuous-tone image to a multilevel image for its reproduction with a multilevel output device, and it is becoming more important as printers can now place dots of different intensities. Compared with conventional binary halftoning,1 MH can improve the rendition quality of a continuous-tone image.24

In theory, MH can be accomplished by an error diffusion algorithm equipped with a multilevel quantizer. However, when the number of quantization levels is small, typically 3 to 5, undesirable banding artifacts occur, as all signal levels close to an intermediate quantization level are quantized to a single output level, such that gradation reproducibility cannot be maintained.

Recently, Rodríguez, Arce, and Lau3 proposed a multitoning blue-noise model for MH. In this model, a multilevel halftone is treated as a stack of halftones. It is suggested that each of them should have blue-noise characteristics and their correlation should be little in low-frequency regions. A criterion measure called the magnitude squared coherence function (MSC) and a MH algorithm were then proposed accordingly. Around the same time, Suetake et al. 4 proposed a MH algorithm to tackle banding artifacts, such that gradation reproducibility can be maintained. Both algorithms decompose an input image into layers, halftone each layer with a binary error diffusion scheme, and finally combine the halftoning results of the layers to produce a multilevel halftone image.

Layers are processed one by one. When processing a particular layer, a constraint is imposed on some selected pixels based on the halftoning result of the last processed layer. These pixels are referred to as constrained pixels. The binary error diffusion scheme used to halftone a layer for Ref. 4 is a combined scheme of Refs. 56. In particular, pixels are processed in a predefined scanning order. When a constrained pixel is encountered, the output value is zero. Otherwise, the output value is the quantized value of the current intensity level of the pixel being processed. In either case, the error is then diffused with a causal filter.

Obviously, it is likely that the assigned value of a constrained pixel goes against the natural quantization result. Since pixels are processed one by one according to a predefined scanning order, and no precaution is taken before encountering a constrained pixel in the course, there is little room for one to compensate for this mismatch. Consequently, this mismatch disturbs the harmony of a local region and degrades the quality of the output.

In this work, we propose a framework for MH with a multiscale error diffusion algorithm called feature-preserving multiscale error diffusion (FMED).7 The proposed approach takes care of the constrained pixels before handling the unconstrained pixels. This allows one to have more room to compensate for the disturbance caused by the constrained pixels when handling the unconstrained pixels.

Suppose one wants to MH a continuous-tone image X to produce a multilevel image Y. Without loss of generality, we assume that X is of size N×N and X(u,v)[0,1], where X(u,v) is the pixel value of X at position (u,v). X can be decomposed into n images, denoted as Xm for m=0,,n1, such that we haveDisplay Formula

1X(u,v)=m=1n1Xm(u,v)(n1),foru,v=0,1,,N1.
In particular, the decomposition is done as follows:Display Formula
{X0(u,v)=1Xm(u,v)=Xm1(u,v)[X(u,v)]m1×[(n1)!(m1)!(nm)!][1X(u,v)]nm,form=1,2n1}
Display Formula
foru,v=0,1,,N1.

In the proposed framework, starting from m=1, we halftone Xm to obtain a binary output Ym under a constraint derived from Ym1 until Yn1 is obtained. Here, we note that Y0 is the binary halftoning output of X0, and hence we have Y0(u,v)=1 for all (u,v).

To produce Ym with Ym1 and Xm, we first assign 0 to some selected pixels of Ym as follows.Display Formula

3Ym(u,v)=0ifYm1(u,v)=0foru,v=0,1,,N1.
Xm is then updated byDisplay Formula
Xm(i+p,j+q)={0if(p,q)=(0,0)Xm(i+p,j+q)+b(i+p,j+q)W(p,q)[Xm(i,j)Ym(i,j)]sif(p,q)Ω,}
Display Formula
foreachconstrainedpixelYm(i,j)=0,
where W is a diffusion filter defined as W=[W(1,1),W(1,0),W(1,1);W(0,1),W(0,0),W(0,1);W(1,1),W(1,0),W(1,1)]=[1,2,1;2,0,2;1,2,1]12, Ω={(u,v)|u,v=0,±1}\{(0,0)}, b(u,v) is a masking bit for pixel Xm(u,v) defined asDisplay Formula
5b(u,v)={0ifYm(u,v)=0oru,v{0,1N1}1else}(u,v),
Display Formula
6ands=p=11q=11b(i+p,j+q)W(p,q).
After updating Xm, the remaining unprocessed pixels in Xm are processed with the FMED algorithm as usual to produce Ym.

After all Ym are obtained, a synthesis process is applied by averaging all Ym except Y0 to generate Y asDisplay Formula

7Y(u,v)=m=1n1Ym(u,v)(n1)foru,v=0,1,,N1.
Note that this framework handles all constrained pixels before processing those unconstrained pixels. Besides, it does not diffuse the quantization error along a predefined scanning direction when processing individual Xm. Hence, though the proposed approach also assigns a predefined value to a constrained pixel without concerning its original intensity, as the approach proposed in Ref. 4 does, it provides more flexibility to compensate for the negative effect of the assignment and, accordingly, provides a halftone of better visual quality.

Simulation was carried out to compare the performances of the algorithms in Refs. 34, and the proposed algorithm. In our simulation, n=3 and the three quantization levels are 0, 0.5, and 1. Figure 1 shows portions of the MH results of a constant gray level patch of size 256×256 when the gray level g is 108255.

Graphic Jump LocationF1 :

(a) Cropped regions of MH results of constant gray-level patch (g=108255), and (b) their corresponding magnitude frequency spectra.

Figure 1 shows the magnitude of the corresponding frequency spectra of Fig. 1. For display purposes, each of them is normalized with respect to its maximum magnitude value. One can see that the spectrum of the proposed algorithm is radially symmetric compared with the others, and possesses blue-noise characteristics. In fact, similar observations can be obtained for other g values. A halftone bearing blue-noise characteristics is visually pleasant, as our human visual system behaves as a low-pass filter that effectively removes the high-frequency noise components. The radially symmetric spectra of the proposed algorithm imply that dots of different intensities are distributed evenly in the corresponding halftones, and there is no pattern artifacts and directional hysteresis. The performances of Refs. 34 are inferior in this aspect. Figure 2 shows the corresponding radial MSC functions of Fig. 1. One can see that the proposed algorithm has low coherence values at the lower frequencies. Similar observations can be obtained for other g values.

Graphic Jump LocationF2 :

Radial MSC functions of Fig. 1.

For subjective evaluation, Figs. 3 show the MH results of Fig. 3. One can see that more feature details of the original image can be preserved by the proposed algorithm. For instances, the rope at the stern and the rigging of the boat are clearer in Fig. 3. Figure 3 shows the result of Ref. 7. By comparing it with Fig. 3, one can see the improvement achieved by MH.

Graphic Jump LocationF3 :

(a) Original, (b) MH output of Ref. 3, (c) MH output of Ref. 4, (d) MH output of the proposed algorithm, and (e) output of the FMED algorithm.7

The computational complexity of the proposed algorithm is roughly 1.5-fold that of Ref. 7, and much higher than that of Refs. 34. However, it can be reduced with the approach proposed in Ref. 8 to achieve real-time implementation.

We propose a MH algorithm based on FMED. By taking the constrained pixels into account ahead of time and diffusing the error with a noncausal filter, the proposed algorithm can produce halftones of better image quality. Simulation results show that the outputs of the proposed algorithm bear good blue-noise characteristics, have no directional artifacts, and preserve feature details of the original image.

We would like to thank the RGC of the HKSAR, China (PolyU 5123/08E) and Center for MSP, The Hong Kong Polytechnic University, Hong Kong, for supporting this research project.

Ulichney  R. A.,  Digital Halftoning. ,  MIT Press ,  Cambridge, MA  ((1987)).
Lin  G. Y., and Allebach  J., “ Multilevel screen design using direct binary search. ,” J. Opt. Soc. Am. A.  0740-3232 19, (10 ), 1969–1982  ((2002)).
Rodríguez  J. B., , Arce  G. R., , and Lau  D. L., “ Blue-noise multitone dithering. ,” IEEE Trans. Image Process..  1057-7149 17, (8 ), 1368–1382  ((2008)).
Suetake  N., , Sakano  M., , Nakashima  E., , and Uchino  E., “ Simple multilevel halftoning excelled in gradation reproducibility. ,” Opt. Lett..  0146-9592 33, (4 ), 339–341  ((2008)).
Floyd  R. W., and Steinberg  L., “ An adaptive algorithm for spatial greyscale. ,” Proc. S.I.D..  0734-1768 17, (2 ), 75–77  ((1976)).
Ostromoukhov  V., “ A simple and efficient error-diffusion algorithm. ,”  Proc. ACM 28th Ann. Conf. Computer Graphics Interactive Tech.. , pp. 567–572  ((2001)).
Chan  Y. H., and Cheung  S. M., “ Feature-preserving multiscale error diffusion for digital halftoning. ,” J. Electron. Imaging.  1017-9909 13, (3 ), 639  ((2004)).
Fung  Y. H., , Lui  K. C., , and Chan  Y. H., “ Low complexity high-performance multiscale error diffusion technique for digital halftoning. ,” J. Electron. Imaging.  1017-9909 16, (1 ), 013010  ((2007)).
© 2010 SPIE and IS&T

Citation

Yik-Hing Fung and Yuk-Hee Chan
"Multilevel halftoning using multiscale error diffusion", J. Electron. Imaging. 19(3), 030501 (August 18, 2010). ; http://dx.doi.org/10.1117/1.3479749


Figures

Graphic Jump LocationF1 :

(a) Cropped regions of MH results of constant gray-level patch (g=108255), and (b) their corresponding magnitude frequency spectra.

Graphic Jump LocationF2 :

Radial MSC functions of Fig. 1.

Graphic Jump LocationF3 :

(a) Original, (b) MH output of Ref. 3, (c) MH output of Ref. 4, (d) MH output of the proposed algorithm, and (e) output of the FMED algorithm.7

Tables

References

Ulichney  R. A.,  Digital Halftoning. ,  MIT Press ,  Cambridge, MA  ((1987)).
Lin  G. Y., and Allebach  J., “ Multilevel screen design using direct binary search. ,” J. Opt. Soc. Am. A.  0740-3232 19, (10 ), 1969–1982  ((2002)).
Rodríguez  J. B., , Arce  G. R., , and Lau  D. L., “ Blue-noise multitone dithering. ,” IEEE Trans. Image Process..  1057-7149 17, (8 ), 1368–1382  ((2008)).
Suetake  N., , Sakano  M., , Nakashima  E., , and Uchino  E., “ Simple multilevel halftoning excelled in gradation reproducibility. ,” Opt. Lett..  0146-9592 33, (4 ), 339–341  ((2008)).
Floyd  R. W., and Steinberg  L., “ An adaptive algorithm for spatial greyscale. ,” Proc. S.I.D..  0734-1768 17, (2 ), 75–77  ((1976)).
Ostromoukhov  V., “ A simple and efficient error-diffusion algorithm. ,”  Proc. ACM 28th Ann. Conf. Computer Graphics Interactive Tech.. , pp. 567–572  ((2001)).
Chan  Y. H., and Cheung  S. M., “ Feature-preserving multiscale error diffusion for digital halftoning. ,” J. Electron. Imaging.  1017-9909 13, (3 ), 639  ((2004)).
Fung  Y. H., , Lui  K. C., , and Chan  Y. H., “ Low complexity high-performance multiscale error diffusion technique for digital halftoning. ,” J. Electron. Imaging.  1017-9909 16, (1 ), 013010  ((2007)).

Some tools below are only available to our subscribers or users with an online account.

Related Content

Customize your page view by dragging & repositioning the boxes below.

Related Proceedings Articles

Related Book Chapters

Topic Collections

PubMed Articles
Advertisement
  • Don't have an account?
  • Subscribe to the SPIE Digital Library
  • Create a FREE account to sign up for Digital Library content alerts and gain access to institutional subscriptions remotely.
Access This Article
Sign in or Create a personal account to Buy this article ($20 for members, $25 for non-members).
Access This Proceeding
Sign in or Create a personal account to Buy this article ($15 for members, $18 for non-members).
Access This Chapter

Access to SPIE eBooks is limited to subscribing institutions and is not available as part of a personal subscription. Print or electronic versions of individual SPIE books may be purchased via SPIE.org.