1 July 2010 Multilevel halftoning using multiscale error diffusion
Author Affiliations +
Abstract
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.
Fung and Chan: Multilevel halftoning using multiscale error diffusion

1.

Introduction

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.2, 3, 4

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 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. 5, 6. 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.

2.

Proposed Algorithm

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 have

1

X(u,v)=m=1n1Xm(u,v)(n1),foru,v=0,1,,N1.
In particular, the decomposition is done as follows:

2.

{X0(u,v)=1Xm(u,v)=Xm1(u,v)[X(u,v)]m1×[(n1)!(m1)!(nm)!][1X(u,v)]nm,form=1,2n1}
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.

3

Ym(u,v)=0ifYm1(u,v)=0foru,v=0,1,,N1.
Xm is then updated by

4.

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)Ω,}
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 as

5

b(u,v)={0ifYm(u,v)=0oru,v{0,1N1}1else}(u,v),

6

ands=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 as

7

Y(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.

3.

Simulation Results

Simulation was carried out to compare the performances of the algorithms in Refs. 3, 4, 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 .

Fig. 1

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

030501_1_1.jpg

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. 3, 4 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.

Fig. 2

Radial MSC functions of Fig. 1.

030501_1_2.jpg

For subjective evaluation, Figs. 3, 3, 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.

Fig. 3

(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

030501_1_3.jpg

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

4.

Conclusions

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.

Acknowledgments

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.

references

1.  R. A. Ulichney, Digital Halftoning, MIT Press, Cambridge, MA (1987). Google Scholar

2.  G. Y. Lin and J. Allebach, “Multilevel screen design using direct binary search,” J. Opt. Soc. Am. A 19(10), 1969–1982 (2002). 10.1364/JOSAA.19.001969 Google Scholar

3.  J. B. Rodríguez, G. R. Arce, and D. L. Lau, “Blue-noise multitone dithering,” IEEE Trans. Image Process. 17(8), 1368–1382 (2008). 10.1109/TIP.2008.926145 Google Scholar

4.  N. Suetake, M. Sakano, E. Nakashima, and E. Uchino, “Simple multilevel halftoning excelled in gradation reproducibility,” Opt. Lett. 33(4), 339–341 (2008). 10.1364/OL.33.000339 Google Scholar

5.  R. W. Floyd and L. Steinberg, “An adaptive algorithm for spatial greyscale,” Proc. S.I.D. 17(2), 75–77 (1976). Google Scholar

6.  V. Ostromoukhov, “A simple and efficient error-diffusion algorithm,” Proc. ACM 28th Ann. Conf. Computer Graphics Interactive Tech., pp. 567–572 (2001). Google Scholar

7.  Y. H. Chan and S. M. Cheung, “Feature-preserving multiscale error diffusion for digital halftoning,” J. Electron. Imaging 13(3), 639 (2004). 10.1117/1.1758728 Google Scholar

8.  Y. H. Fung, K. C. Lui, and Y. H. Chan, “Low complexity high-performance multiscale error diffusion technique for digital halftoning,” J. Electron. Imaging 16(1), 013010 (2007). 10.1117/1.2435197 Google Scholar

© (2010) Society of Photo-Optical Instrumentation Engineers (SPIE)
Yik-Hing Fung, Yik-Hing Fung, Yuk-Hee Chan, Yuk-Hee Chan, } "Multilevel halftoning using multiscale error diffusion," Journal of Electronic Imaging 19(3), 030501 (1 July 2010). https://doi.org/10.1117/1.3479749 . Submission:
JOURNAL ARTICLE
3 PAGES


SHARE
Back to Top