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,¹ 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 Lau³ 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 ⁴ 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).⁷ 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\times 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 $X_m$ for $m=0,\dots ,n-1$ , such that we have

In the proposed framework, starting from $m=1$ , we halftone $X_m$ to obtain a binary output $Y_m$ under a constraint derived from $Y_{m-1}$ until $Y_{n-1}$ is obtained. Here, we note that $Y_0$ is the binary halftoning output of $X_0$ , and hence we have $Y_0(u,v)=1$ for all $(u,v)$ .

To produce $Y_m$ with $Y_{m-1}$ and $X_m$ , we first assign 0 to some selected pixels of $Y_m$ as follows.

After all $Y_m$ are obtained, a synthesis process is applied by averaging all $Y_m$ except $Y_0$ to generate $Y$ as

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\times 256$ when the gray level $g$ is $108∕255$ .

Fig. 1

(a) Cropped regions of MH results of constant gray-level patch $(g=108∕255)$ , 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. 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.

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

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.