Open AccessArticle

Neugebauer Models for Color Error Diffusion Halftoning

Kaiming Wu

Kohei Inoue

and

Kenji Hara

Department of Communication Design Science, Kyushu University, Fukuoka 815-8540, Japan

Author to whom correspondence should be addressed.

J. Imaging 2020, 6(4), 23; https://doi.org/10.3390/jimaging6040023

Submission received: 4 March 2020 / Revised: 14 April 2020 / Accepted: 16 April 2020 / Published: 17 April 2020

Download

Browse Figures

Figure 1
Error diffusion coefficients by Floyd–Steinberg [<a href="#B7-jimaging-06-00023" class="html-bibr">7</a>]. "> Figure 2
Grayscale Neugebauer model. "> Figure 3
Two-dimensional Neugebauer model. "> Figure 4
Three-dimensional Neugebauer model. "> Figure 5
Eight basic colors ordered on the brightness axis. "> Figure 6
MBVQ <math display="inline"><semantics> <mrow> <mo>{</mo> <msub> <mi mathvariant="bold-italic">s</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi mathvariant="bold-italic">s</mi> <mn>2</mn> </msub> <mo>,</mo> <msub> <mi mathvariant="bold-italic">s</mi> <mn>3</mn> </msub> <mo>,</mo> <msub> <mi mathvariant="bold-italic">s</mi> <mn>4</mn> </msub> <mo>}</mo> </mrow> </semantics></math> for a color <math display="inline"><semantics> <mi mathvariant="bold-italic">f</mi> </semantics></math>. "> Figure 7
Color image halftoning. "> Figure 8
Occurrence probabilities of basic colors. "> Figure 9
Absolute errors in occurrence probabilities in <a href="#jimaging-06-00023-f008" class="html-fig">Figure 8</a>. "> Figure 10
Results on the SIDBA images. "> Figure 11
Mean absolute errors of halftoned SIDBA images in <a href="#jimaging-06-00023-f010" class="html-fig">Figure 10</a>. "> Figure 12
Color image halftoning with zoomed parts. "> Figure 13
Occurrence probabilities of basic colors. "> Figure 14
Absolute errors in occurrence probabilities in <a href="#jimaging-06-00023-f013" class="html-fig">Figure 13</a>. "> Figure 15
Halftoned SIDBA images. "> Figure 16
Zoomed parts of Milkdrop images. "> Figure 17
Mean absolute errors of halftoned SIDBA images in <a href="#jimaging-06-00023-f015" class="html-fig">Figure 15</a>. ">

Versions Notes

Abstract

In this paper, we propose a method for halftoning color images based on an error diffusion technique, a color design criterion and Neugebauer models for expressing colors. For a natural extension of the conventional method for grayscale error diffusion to its color version, we first reformulate grayscale error diffusion with a one-dimensional Neugebauer model. Then we increase the dimension of the model to derive a color error diffusion method based on a three-dimensional Neugebauer model in RGB (red, green and blue) color space. Moreover, we propose a sparse Neugebauer model based on a color design criterion, or the minimal brightness variation criterion (MBVC), from which we derive a sparse Neugebauer model-based error diffusion method. Experimental results show that color halftone images produced by the proposed methods preserve the color contents in original continuous-tone images better than that by conventional color error diffusion methods. We also demonstrate that the proposed sparse method reduce halftone noise better than the state-of-the-art method based on MBVC.

Keywords:

halftoning; error diffusion; sparse Neugebauer model

1. Introduction

Digital halftoning is the process of converting a continuous-tone image into a pattern of a limited number of gray levels or colors. Recently, the techniques for digital halftoning have attracted the interest of researchers in the field of smart paper technology [1]. Smart paper is another name for the e-paper or electronic paper which is the electronic ink display technology designed to mimic the appearance of ordinary ink on paper. Electronic papers reflect light like ordinary papers, and can hold texts and images indefinitely without drawing electricity, while allowing the image to be changed later [2]. Therefore, it is said to be used for applications such as e-books, electronic newspapers, portable sings and foldable display [3]. Hsu et al. [4] mentioned the movie “Minority Report”, in which an electronic newspaper appears, and remarked that those technologies in the near future are becoming reality now. Kao et al. [5] proposed an integrated driving system for playing videos/animations on the electrophoretic display (EPD). The EPD system contains a real-time signal processing hardware engine for video halftoning based on Jarvis error diffusion. The proposed algorithm in this paper is a kind of error diffusion algorithms such as Jarvis error diffusion; therefore, the proposed algorithm can be applied to the EPD system by replacing the conventional error diffusion algorithm with the proposed one.

Error diffusion [6] is one of the typical digital halftoning techniques. Floyd and Steinberg [7] originated a grayscale error diffusion algorithm. A simple extension of grayscale error diffusion to color is to apply grayscale error diffusion to each color channel in a color image separately. These kinds of extensions are referred to as separable methods [8]. Shaked et al. formulated a color design criterion named the minimal brightness variation criterion (MBVC), and developed an ink relocation post-process applicable to arbitrary color halftone algorithms [9] and a color diffusion algorithm which decreases halftone noise successfully [10].

Neugebauer model for color representation can be used to infer the gamut boundaries of printed colorants on paper [11] by printers such as conventional CMYK (cyan, magenta, yellow and black) printers. Monga et al. [12] proposed an extension of tone-dependent error diffusion to color, which employs a Neugebauer printer model with a simple correction by Yule and Nielsen [13]. Inoue et al. [14] applied the Neugebauer model to the estimation of spectral reflectance.

In this paper, we propose a grayscale Neugebauer model for representing an arbitrary grayscale value by a linear combination of black and white, and apply it to grayscale error diffusion to derive a grayscale Neugebauer model-based method. Then we show the equivalence between conventional grayscale error diffusion and the Neugebauer model-based method. After that, we extend the grayscale Neugebauer model-based error diffusion method to its color version by extending the dimension of color space from 1D to 3D. Therefore, the proposed color error diffusion method can be expected as a good candidate for the color extensions of a standard grayscale error diffusion technique. Moreover, we propose a sparse Neugebauer model for improving the quality of halftone images. Experimental results show the effectiveness of the proposed color error diffusion method on real image data including standard images for image processing researches.

The rest of this paper is organized as follows: Section 2 summarizes grayscale error diffusion, and shows the equivalence between conventional grayscale error diffusion and Neugebauer model-based method. Section 3 extends grayscale Neugebauer model to its color version. Section 4 proposes a color Neugebauer model-based error diffusion method. Section 5 proposes a sparse color Neugebauer model-based error diffusion method. Section 6 shows experimental results for demonstrating the performance of the proposed methods. Finally, Section 7 concludes this paper.

2. Grayscale Error Diffusion

Let

F = [f_{i j}]

be a grayscale image, where

f_{i j} \in [0, 1]

for

i = 1, 2, \dots, m

and

j = 1, 2, \dots, n

denotes the pixel value at the position

(i, j)

in F. Then conventional error diffusion method is described as follows.

2.1. Conventional Method

Let

H^{F} = [h_{i j}^{F}]

be a halftoned binary image of F. Then each pixel value

h_{i j}^{F}

H^{F}

is given by

\begin{matrix} h_{i j}^{F} = \{\begin{matrix} 1, & if f_{i j} > θ \\ 0, & otherwise \end{matrix} \end{matrix}

(1)

in raster scan order, where

θ

denotes a threshold value for binarization, and is given as

θ = \frac{1}{2}

in this paper. This binarization in Equation (1) causes an error as follows:

\begin{matrix} e_{i j} = f_{i j} - h_{i j}^{F} \end{matrix}

(2)

which is diffused to subsequent adjoining pixels as follows:

\begin{matrix} f_{i + k, j + l}^{'} = f_{i + k, j + l} + w_{k l} e_{i j} \end{matrix}

(3)

where such a pixel

f_{i + k, j + l}

at the position

(i + k, j + l)

is updated to

f_{i + k, j + l}^{'}

by adding the error

e_{i j}

weighted by predetermined coefficients

w_{k l}

as shown in Figure 1, where “#” denotes the current pixel being processed, and “-” denotes the past pixel in the raster scan order.

For subsequent pixels, the updated values

f_{i j}^{'}

are binarized with Equation (1) instead of the original

f_{i j}

2.2. Grayscale Neugebauer Model-Based Method

We present a grayscale Neugebauer model as follows:

\begin{matrix} f_{i j} = p_{i j}^{K} K + p_{i j}^{W} W \end{matrix}

(4)

where

K = 0

and

W = 1

denote black and white, respectively, and the coefficients defined by

\begin{matrix} p_{i j}^{K} & = 1 - f_{i j} \end{matrix}

(5)

\begin{matrix} p_{i j}^{W} & = f_{i j} \end{matrix}

(6)

can be viewed as the occurrence probabilities of black and white because of

p_{i j}^{K} \geq 0, p_{i j}^{W} \geq 0

and

p_{i j}^{K} + p_{i j}^{W} = 1

. In other words, the grayscale Neugebauer model expresses an arbitrary grayscale value

f_{i j}

as an internally dividing point between black (K) and white (W) as illustrated in Figure 2.

Based on the grayscale Neugebauer model in Equation (4), we propose another expression of grayscale error diffusion as follows (the equivalence of these expressions will be discussed in the next subsection): A pixel value

h_{i j}^{F}

H^{F}

is given by selecting black or white which has larger probability than another as

\begin{matrix} h_{i j}^{F} = \arg max_{x \in {K, W}} \{p_{i j}^{x}\} \end{matrix}

(7)

After this binarization, the occurrence probabilities become

\begin{matrix} {\tilde{p}}_{i j}^{K} & = 1 - h_{i j}^{F} \end{matrix}

(8)

\begin{matrix} {\tilde{p}}_{i j}^{W} & = h_{i j}^{F} \end{matrix}

(9)

using which, we define the errors in occurrence probabilities

p_{i j}^{K}

and

p_{i j}^{W}

\begin{matrix} e_{i j}^{K} & = p_{i j}^{K} - {\tilde{p}}_{i j}^{K} \end{matrix}

(10)

\begin{matrix} e_{i j}^{W} & = p_{i j}^{W} - {\tilde{p}}_{i j}^{W} \end{matrix}

(11)

which are diffused to the subsequent pixels as follows:

\begin{matrix} {p'}_{i + k, j + l}^{K} & = p_{i + k, j + l}^{K} + w_{k l} e_{i j}^{K} \end{matrix}

(12)

\begin{matrix} {p'}_{i + k, j + l}^{W} & = p_{i + k, j + l}^{W} + w_{k l} e_{i j}^{W} \end{matrix}

(13)

where the occurrence probabilities

p_{i + k, j + l}^{K}

and

p_{i + k, j + l}^{W}

of the subsequent adjoining pixel

(i + k, j + l)

are updated to

{p'}_{i + k, j + l}^{K}

and

{p'}_{i + k, j + l}^{W}

, respectively.

For subsequent pixels, the updated values

{p'}_{i j}^{K}

and

{p'}_{i j}^{W}

are used for the binarization in Equation (7) instead of the original

p_{i j}^{K}

and

p_{i j}^{W}

2.3. Equivalence of the Two Methods

Here we show an equivalence of the above two methods for grayscale error diffusion.

When

h_{i j}^{F} = K = 0

in Equation (7), we have

p_{i j}^{K} \geq p_{i j}^{W}

1 - f_{i j} \geq f_{i j}

, which means that

f_{i j} \leq \frac{1}{2} = θ

, that is the condition for

h_{i j}^{F} = 0

in Equation (1). On the other hand, when

h_{i j}^{F} = W = 1

in Equation (7), we have

p_{i j}^{W} > p_{i j}^{K}

f_{i j} > 1 - f_{i j}

, which means that

f_{i j} > \frac{1}{2} = θ

, that is the condition for

h_{i j}^{F} = 1

in Equation (1). Therefore, the binarization in Equation (7) is equivalent to that in Equation (1).

Next, we describe the equivalence of error diffusion procedures. Assume that

h_{i j}^{F} = K = 0

in Equation (7). Then the occurrence probabilities in Equations (8) and (9) become

{\tilde{p}}_{i j}^{K} = 1 - h_{i j}^{F} = 1

and

{\tilde{p}}_{i j}^{W} = h_{i j}^{F} = 0

, and the errors in Equations (10) and (11) become

e_{i j}^{K} = p_{i j}^{K} - {\tilde{p}}_{i j}^{K} = p_{i j}^{K} - 1

and

e_{i j}^{W} = p_{i j}^{W} - {\tilde{p}}_{i j}^{W} = p_{i j}^{W}

, respectively. Substituting these errors into Equations (12) and (13), we have

\begin{matrix} {p'}_{i + k, j + l}^{K} & = p_{i + k, j + l}^{K} + w_{k l} (p_{i j}^{K} - 1) \end{matrix}

(14)

\begin{matrix} {p'}_{i + k, j + l}^{W} & = p_{i + k, j + l}^{W} + w_{k l} p_{i j}^{W} \end{matrix}

(15)

from both of which, using the relationships in Equations (5) and (6), we have

\begin{matrix} f_{i + k, j + l}^{'} = f_{i + k, j + l} + w_{k l} f_{i j} \end{matrix}

(16)

which coincides with Equation (3) with Equation (2) for

h_{i j}^{F} = K = 0

On the other hand, when

h_{i j}^{F} = W = 1

in Equation (7), the occurrence probabilities in Equations (8) and (9) become

{\tilde{p}}_{i j}^{K} = 1 - h_{i j}^{F} = 0

and

{\tilde{p}}_{i j}^{W} = h_{i j}^{F} = 1

, and the errors in Equations (10) and (11) become

e_{i j}^{K} = p_{i j}^{K} - {\tilde{p}}_{i j}^{K} = p_{i j}^{K}

and

e_{i j}^{W} = p_{i j}^{W} - {\tilde{p}}_{i j}^{W} = p_{i j}^{W} - 1

, respectively. Substituting these errors into Equations (12) and (13), we have

\begin{matrix} {p'}_{i + k, j + l}^{K} & = p_{i + k, j + l}^{K} + w_{k l} p_{i j}^{K} \end{matrix}

(17)

\begin{matrix} {p'}_{i + k, j + l}^{W} & = p_{i + k, j + l}^{W} + w_{k l} (p_{i j}^{W} - 1) \end{matrix}

(18)

from both of which, using the relationships in Equations (5) and (6), we have

\begin{matrix} f_{i + k, j + l}^{'} = f_{i + k, j + l} + w_{k l} (f_{i j} - 1) \end{matrix}

(19)

which also coincides with Equation (3) with Equation (2) for

h_{i j}^{F} = W = 1

Consequently, the grayscale Neugebauer model-based error diffusion in Equations (12) and (13) can be reduced to the conventional error diffusion in Equation (3) with Equation (2), that shows the equivalence of the two methods.

3. Extending Grayscale Neugebauer Model to Higher Dimensions

The grayscale Neugebauer model illustrated in Figure 2 has a one-dimensional structure, where a midpoint

f_{i j}

is expressed as a linear interpolant between K and W. This one-dimensional structure of grayscale Neugebauer model can be extended to two-dimensional bilinear interpolation as follows: Let

f_{i j} = (r_{i j}, g_{i j})

be a two-dimensional color vector on an RG (red and green) color plane as illustrated in Figure 3. Then

f_{i j}

can be expressed as a bilinear interpolant of four basic colors: K (black), R (red), G (green) and Y (yellow) as shown in Figure 3, where a linear interpolant between K and G is expressed as

g_{i j} G + (1 - g_{i j}) K

for a given green value

g_{i j}

. Similarly, a linear interpolant between R and Y is expressed as

g_{i j} Y + (1 - g_{i j}) R

. Using those expressions,

f_{i j}

on the RG color plane can be expressed as a linear interpolant of

g_{i j} G + (1 - g_{i j}) K

and

g_{i j} Y + (1 - g_{i j}) R

for a given red value

r_{i j}

as follows:

\begin{matrix} f_{i j} & = (1 - r_{i j}) [g_{i j} G + (1 - g_{i j}) K] + r_{i j} [g_{i j} Y + (1 - g_{i j}) R] \\ = (1 - r_{i j}) (1 - g_{i j}) K + r_{i j} (1 - g_{i j}) R + (1 - r_{i j}) g_{i j} G + r_{i j} g_{i j} Y \\ = p_{i j}^{K} K + p_{i j}^{R} R + p_{i j}^{G} G + p_{i j}^{Y} Y \end{matrix}

(20)

where four basic colors are given by

K = (0, 0), R = (1, 0), G = (0, 1)

and

Y = (1, 1)

, and the coefficients are given by

\begin{matrix} p_{i j}^{K} & = (1 - r_{i j}) (1 - g_{i j}) \end{matrix}

(21)

\begin{matrix} p_{i j}^{R} & = r_{i j} (1 - g_{i j}) \end{matrix}

(22)

\begin{matrix} p_{i j}^{G} & = (1 - r_{i j}) g_{i j} \end{matrix}

(23)

\begin{matrix} p_{i j}^{Y} & = r_{i j} g_{i j} \end{matrix}

(24)

Thus we have a two-dimensional Neugebauer model in Equation (20) with Equations (21)–(24).

Next, we further extend the above two-dimensional Neugebauer model to three-dimensional one in order to deal with arbitrary colors in three-dimensional color space. Figure 4 illustrates the derivation of three-dimensional Neugebauer model as a trilinear interpolation of eight basic colors in RGB color space for representing an arbitrary color as a linear combination of the basic colors.

Let

f_{i j} = (r_{i j}, g_{i j}, b_{i j})

be a three-dimensional color vector in an RGB color space as shown in Figure 4. Then the orthogonal projection of

f_{i j}

onto the bottom plane

K R Y G

of the RGB color cube is given by Equation (20) using two-dimensional Neugebauer model. Similarly, another orthogonal projection of

f_{i j}

onto the top plane

B M W C

of the RGB color cube is given by

(1 - r_{i j}) (1 - g_{i j}) B + r_{i j} (1 - g_{i j}) M + (1 - r_{i j}) g_{i j} C + r_{i j} g_{i j} W

. On the contrary,

f_{i j}

can be represented as an interpolant of the above two orthogonal projections of

f_{i j}

as follows:

\begin{matrix} f_{i j} = & (1 - b_{i j}) [(1 - r_{i j}) (1 - g_{i j}) K + r_{i j} (1 - g_{i j}) R + (1 - r_{i j}) g_{i j} G + r_{i j} g_{i j} Y] \\ + b_{i j} [(1 - r_{i j}) (1 - g_{i j}) B + r_{i j} (1 - g_{i j}) M + (1 - r_{i j}) g_{i j} C + r_{i j} g_{i j} W] \\ = & (1 - r_{i j}) (1 - g_{i j}) (1 - b_{i j}) K + r_{i j} (1 - g_{i j}) (1 - b_{i j}) R \\ + (1 - r_{i j}) g_{i j} (1 - b_{i j}) G + r_{i j} g_{i j} (1 - b_{i j}) Y \\ + (1 - r_{i j}) (1 - g_{i j}) b_{i j} B + r_{i j} (1 - g_{i j}) b_{i j} M \\ + (1 - r_{i j}) g_{i j} b_{i j} C + r_{i j} g_{i j} b_{i j} W \\ = & p_{i j}^{K} K + p_{i j}^{R} R + p_{i j}^{G} G + p_{i j}^{Y} Y + p_{i j}^{B} B + p_{i j}^{M} M + p_{i j}^{C} C + p_{i j}^{W} W \end{matrix}

(25)

where eight basic colors are given by

K = (0, 0, 0), R = (1, 0, 0), G = (0, 1, 0), Y = (1, 1, 0), B = (0, 0, 1), M = (1, 0, 1), C = (0, 1, 1)

and

W = (1, 1, 1)

, and the coefficients are given by

\begin{matrix} p_{i j}^{K} & = (1 - r_{i j}) (1 - g_{i j}) (1 - b_{i j}) \end{matrix}

(26)

\begin{matrix} p_{i j}^{R} & = r_{i j} (1 - g_{i j}) (1 - b_{i j}) \end{matrix}

(27)

\begin{matrix} p_{i j}^{G} & = (1 - r_{i j}) g_{i j} (1 - b_{i j}) \end{matrix}

(28)

\begin{matrix} p_{i j}^{Y} & = r_{i j} g_{i j} (1 - b_{i j}) \end{matrix}

(29)

\begin{matrix} p_{i j}^{B} & = (1 - r_{i j}) (1 - g_{i j}) b_{i j} \end{matrix}

(30)

\begin{matrix} p_{i j}^{M} & = r_{i j} (1 - g_{i j}) b_{i j} \end{matrix}

(31)

\begin{matrix} p_{i j}^{C} & = (1 - r_{i j}) g_{i j} b_{i j} \end{matrix}

(32)

\begin{matrix} p_{i j}^{W} & = r_{i j} g_{i j} b_{i j} \end{matrix}

(33)

This three-dimensional Neugebauer model in Equation (25) with Equations (26)–(33) is used for color error diffusion in the next section.

4. Color Neugebauer Model-Based Method

Analogous to the grayscale Neugebauer model-based method in Section 2.2, we propose a color error diffusion method based on the color Neugebauer model in Section 3.

In color image halftoning, it is common to use a limited number of basic colors instead of true color. Let

S = {K, R, G, Y, B, M, C, W}

be the set of eight basic colors. Then the color quantization of a pixel color

f_{i j}

of an RGB color image

F

to one of the eight basic colors can be described as

\begin{matrix} h_{i j}^{F} = \arg max_{x \in S} \{p_{i j}^{x}\} \end{matrix}

(34)

which is the corresponding pixel color in the color halftone image

H^{F} = [h_{i j}^{F}]

F

, and

p_{i j}^{x}

for

x \in S

are given by Equations (26)–(33). This expression in Equation (34) is a natural extension of grayscale binarization in Equation (7) to color quantization.

After this quantization, the occurrence probabilities become

\begin{matrix} {\tilde{p}}_{i j}^{x} = \{\begin{matrix} 1, & if x = h_{i j}^{F} \\ 0, & otherwise \end{matrix} \end{matrix}

(35)

using which, we define the errors in occurrence probabilities

p_{i j}^{x}

for

x \in S

\begin{matrix} e_{i j}^{x} = p_{i j}^{x} - {\tilde{p}}_{i j}^{x} \end{matrix}

(36)

which are diffused to the subsequent pixels as follows:

\begin{matrix} {p'}_{i + k, j + l}^{x} = p_{i + k, j + l}^{x} + w_{k l} e_{i j}^{x} \end{matrix}

(37)

where the occurrence probability

p_{i + k, j + l}^{x}

of the subsequent adjoining pixel

(i + k, j + l)

is updated to

{p'}_{i + k, j + l}^{x}

For subsequent pixels, the updated values

{p'}_{i j}^{x}

for

x \in S

are used for the quantization in Equation (34) instead of the original

p_{i j}^{x}

The above method is summarized in Algorithm 1.

Algorithm 1 Color Neugebauer model-based error diffusion

Require:: RGB color image $F = [f_{i j}]$ where $f_{i j} = (r_{i j}, g_{i j}, b_{i j})$
Ensure:: halftone image $H^{F} = [h_{i j}^{F}]$
1:: $S \leftarrow {K, R, G, Y, B, M, C, W}$
2:: $Ω \leftarrow {(i, j) | i = 1, 2, \dots, m and j = 1, 2, \dots, n}$
3:: for $i \leftarrow 1$ to m do
4:: for $j \leftarrow 1$ to n do
5:: Compute coefficients $p_{i j}^{x}$ for $x \in S$ by (26)–(33)
6:: end for
7:: end for
8:: for $i \leftarrow 1$ to m do
9:: for $j \leftarrow 1$ to n do
10:: $h_{i j}^{F} \leftarrow \arg {max}_{x \in S} \{p_{i j}^{x}\}$
11:: for $x \in S$ do
12:: ${\tilde{p}}_{i j}^{x} \leftarrow 1$ if $x = h_{i j}^{F}$ else 0
13:: $e_{i j}^{x} \leftarrow p_{i j}^{x} - {\tilde{p}}_{i j}^{x}$
14:: for $(k, l) \in {(0, 1), (1, - 1), (1, 0), (1, 1)}$ do
15:: if $(i + k, j + l) \in Ω$ then
16:: $p_{i + k, j + l}^{x} \leftarrow p_{i + k, j + l}^{x} + w_{k l} e_{i j}^{x}$
17:: end if
18:: end for
19:: end for
20:: end for
21:: end for
22:: return $H^{F} = [h_{i j}^{F}]$

In Algorithm 1, although we suppose that the error diffusion coefficients by Floyd–Steinberg [7] in Figure 1 is adopted, it is replaceable with other coefficients such as Jarvis–Judice–Ninke [15], Stucki [16] and Burkes [17].

5. Sparse Color Neugebauer Model-Based Method

The above Neugebauer model expresses an arbitrary color as a linear combination of eight basic colors in S. However, this expression is somewhat redundant, because a color in RGB color space exists in a tetrahedron, the vertices of which are selected from S, and therefore, four basic colors are sufficient for expressing an arbitrary color as a linear combination of basic colors.

Shaked et al. [10] proposed a high-quality color error diffusion method based on the MBVC, i.e., to reduce halftone noise, select from within all halftone sets by which the desired color may be rendered, the one whose brightness variation is minimal [9,10]. Based on MBVC, they derived the minimal brightness variation quadruples (MBVQs):

{C, M, Y, W,}, {M, Y, G, C}, {R, G, M, Y}, {K, R, G, B}, {R, G, B, M}

and

{C, M, G, B}

, which are the subsets of S, the elements of which are ordered on the brightness axis as shown in Figure 5. Although Shaked et al. [9] suggested a different brightness order,

K, B, R, M, G, C, Y

and W, for a CRT screen, we would like to use the order in Figure 5 for consistency with Shaked’s algorithm. That is, selecting a suitable brightness order is a problem-dependent on the display environment of colors.

For a given RGB color, we can determine the corresponding MBVQ uniquely by Shaked’s algorithm. Let

S_{f} = {s_{1}, s_{2}, s_{3}, s_{4}} \subset S

be the MBVQ for a color

f = (r, g, b)

. Then this situation can be illustrated as Figure 6, and we would like to express

f

as a linear combination of

S_{f}

as:

\begin{matrix} f = p_{1} s_{1} + p_{2} s_{2} + p_{3} s_{3} + p_{4} s_{4} \end{matrix}

(38)

where

p_{1}, p_{2}, p_{3}

and

p_{4}

are nonnegative coefficients satisfying

p_{1} + p_{2} + p_{3} + p_{4} = 1

As shown in Figure 6, the vector

f - s_{1}

can be expressed as a linear combination of the vectors

s_{2} - s_{1}, s_{3} - s_{1}

and

s_{4} - s_{1}

as follows:

\begin{matrix} f - s_{1} = p_{2} (s_{2} - s_{1}) + p_{3} (s_{3} - s_{1}) + p_{4} (s_{4} - s_{1}) \end{matrix}

(39)

Solving this simultaneous equations for

p_{2}, p_{3}

and

p_{4}

, we have the following expression of

f

\begin{matrix} f = (1 - p_{2} - p_{3} - p_{4}) s_{1} + p_{2} s_{2} + p_{3} s_{3} + p_{4} s_{4} \end{matrix}

(40)

Putting

p_{1} = 1 - p_{2} - p_{3} - p_{4}

, we have a sparse Neugebauer model as follows:

\begin{matrix} f = \sum_{ξ = 1}^{4} p_{ξ} s_{ξ} + \sum_{η = 1}^{4} q_{η} t_{η} \end{matrix}

(41)

where

q_{η} = 0

, and

t_{η} \in S ∖ S_{f}

for

η = 1, 2, 3, 4

, i.e., every

t_{η}

is the element of the complement of

S_{f}

in S. By replacing the standard Neugebauer model in Algorithm 1 with the above sparse Neugebauer model, we propose another color error diffusion algorithm as Algorithm 2, where the function

MBVQ (f)

computes an MBVQ for a given color

f

by Shaked’s algorithm.

Algorithm 2 Sparse Neugebauer model-based error diffusion

Require:: RGB color image $F = [f_{i j}]$ where $f_{i j} = (r_{i j}, g_{i j}, b_{i j})$
Ensure:: halftone image $H^{F} = [h_{i j}^{F}]$
1:: $S \leftarrow {K, R, G, Y, B, M, C, W}$
2:: $Ω \leftarrow {(i, j) | i = 1, 2, \dots, m and j = 1, 2, \dots, n}$
3:: for $i \leftarrow 1$ to m do
4:: for $j \leftarrow 1$ to n do
5:: Compute the MBVQ $S_{f} = {s_{1}, s_{2}, s_{3}, s_{4}} \leftarrow MBVQ (f)$ for each color $f \leftarrow (r_{i j}, g_{i j}, b_{i j})$
6:: Solve the following simultaneous equations for $p_{2}, p_{3}$ and $p_{4}$ : $f - s_{1} = p_{2} (s_{2} - s_{1}) + p_{3} (s_{3} - s_{1}) + p_{4} (s_{4} - s_{1})$
7:: Compute $p_{1} \leftarrow 1 - p_{2} - p_{3} - p_{4}$
8:: for $ξ \leftarrow 1$ to 4 do
9:: $p_{i j}^{s_{ξ}} \leftarrow p_{ξ}$
10:: end for
11:: Compute ${t_{1}, t_{2}, t_{3}, t_{4}} \leftarrow S ∖ S_{f}$
12:: for $η \leftarrow 1$ to 4 do
13:: $p_{i j}^{t_{η}} \leftarrow 0$
14:: end for
15:: end for
16:: end for
17:: for $i \leftarrow 1$ to m do
18:: for $j \leftarrow 1$ to n do
19:: $h_{i j}^{F} \leftarrow \arg {max}_{x \in S} \{p_{i j}^{x}\}$
20:: for $x \in S$ do
21:: ${\tilde{p}}_{i j}^{x} \leftarrow 1$ if $x = h_{i j}^{F}$ else 0
22:: $e_{i j}^{x} \leftarrow p_{i j}^{x} - {\tilde{p}}_{i j}^{x}$
23:: for $(k, l) \in {(0, 1), (1, - 1), (1, 0), (1, 1)}$ do
24:: if $(i + k, j + l) \in Ω$ then
25:: $p_{i + k, j + l}^{x} \leftarrow p_{i + k, j + l}^{x} + w_{k l} e_{i j}^{x}$
26:: end if
27:: end for
28:: end for
29:: end for
30:: end for
31:: return $H^{F} = [h_{i j}^{F}]$

6. Experimental Results

In this section, we demonstrate the performance of the proposed error diffusion methods using real images. Figure 7 shows an example of color image halftoning, where an original color image in Figure 7a is halftoned by conventional separable error diffusion method as shown in Figure 7b. The separable method [8] applies grayscale error diffusion to each color channel separately, and combines the resultant three grayscale halftone images into a single color halftone image. Figure 7c shows the result of the proposed color Neugebauer model-based error diffusion method summarized in Algorithm 1. Although Figure 7b,c look similar to each other from a distance, a close look at these images reveals that Algorithm 1 loses the clarity of the reproduction of contours. Algorithm 2 will improve the quality of contour reproduction as shown in the following results.

In order to show the difference between Figure 7b,c clearly, we show the occurrence probabilities of eight basic colors (

K = (0, 0, 0), R = (1, 0, 0), G = (0, 1, 0), Y = (1, 1, 0), B = (0, 0, 1), M = (1, 0, 1), C = (0, 1, 1)

and

W = (1, 1, 1)

) in each image in Figure 8, where the vertical and horizontal axes denote the occurrence probability and the basic colors, respectively, where the occurrence probability of a basic color

x \in S

is defined by

\begin{matrix} p^{x} = \frac{1}{m n} \sum_{i = 1}^{m} \sum_{j = 1}^{n} p_{i j}^{x} \end{matrix}

(42)

Blue, orange and green bars denote the original image and the halftoned images by the separable and the proposed methods, respectively. This figure shows that the occurrence probabilities for the separable method deviate from the original ones, on the other hand, that for the proposed method follow the original ones well. To confirm this difference quantitatively, we compute the absolute error of the occurrence probabilities defined by

\begin{matrix} E (p_{Orig}^{x}, p_{Half}^{x}) = |p_{Orig}^{x} - p_{Half}^{x}| \end{matrix}

(43)

for

x \in S

, where

p_{Orig}^{x}

and

p_{Half}^{x}

denote the occurrence probabilities of basic color

x

in an original and its halftoned images, respectively. Figure 9 shows

E (p_{Orig}^{x}, p_{Half}^{x})

for eight basic colors, where orange and green bars denote that the occurrence probabilities

p_{Half}^{x}

are computed from the halftoned images by the separable and proposed methods, respectively. This figure shows that the proposed method can decrease the absolute error compared with the separable method.

Figure 10 shows additional results on the standard image database SIDBA [18], which contains twelve color images as shown in Figure 10a. Figure 10b,c show the results of the separable and the proposed methods, respectively. Figure 11 shows the mean absolute error of the occurrence probabilities of the eight basic colors, where the vertical and horizontal axes denote the mean absolute error and the twelve images shown in Figure 10, respectively. The proposed method denoted by green bars achieved smaller errors compared with the separable method denoted by orange bars for all twelve SIDBA images.

Next, we compare the proposed sparse Neugebauer model-based method (Algorithm 2) with Shaked’s method [10]. Figure 12 compares conventional separable, Shaked’s and the proposed sparse methods, where Figure 12a shows an original color image, which is halftoned by the separable, Shaked’s and proposed methods as Figure 12b–d, respectively. Their zoomed parts are also shown at the bottom of them.

As shown in Figure 12f, separable method places dark and light pixels side by side with each other here and there, which conflicts with the MBVC. On the other hand, Shaked’s method reduces the brightness variation, however, the subtle gradations on the surface of ceramic ware are disturbed in Figure 12g. Compared with Shaked’s method, the proposed method achieves both the brightness variation reduction and the subtle gradation reproduction as shown in Figure 12h.

For evaluating the quality of halftoned images in Figure 12 quantitatively, we show the occurrence probabilities of eight basic colors in each image in Figure 13, where the vertical and horizontal axes denote the occurrence probability and the basic colors, respectively. Blue, orange and green bars denote the original image and the halftoned images by Shaked’s and the proposed methods, respectively.

This figure shows that the occurrence probabilities for the Shaked method deviate from the original ones, on the other hand, that for the proposed sparse method follows the original ones well. To confirm this difference quantitatively, we show the absolute error of the occurrence probabilities in Figure 14, which shows that the proposed sparse method can decrease the absolute error compared with Shaked’s method.

Figure 15 shows halftoned SIDBA images by Shaked’s and the proposed sparse methods, which produce visually similar halftone images to each other.

However, the produced halftone images are not identical as shown in Figure 16, where Figure 16a–d show the zoomed parts of the same subregions of Milkdrop images in Figure 10a,b, and Figure 15a,b, respectively. The original patch in Figure 16a is halftoned by the separable method as shown in Figure 16b, where all eight basic colors are used to reproduce the original colors. In Figure 16c, Shaked’s method succeeds in reducing black and white pixels for minimizing the brightness variation. However, in Figure 16c, the second darkest blue and the second lightest yellow pixels are still intermingled spatially. On the other hand, in Figure 16d, the proposed sparse method reduces the spatial mixture of blue and yellow pixels compared with Figure 16c. This result demonstrates that the proposed sparse method (Algorithm 2) can separate different colors spatially on the image plane better than Shaked’s method, which improves the clarity of the reproduction of contours, and therefore, Algorithm 2 can also be applicable to the reproduction of textual information as well as Shaked’s method.

To confirm the difference between Shaked’s and the proposed sparse methods quantitatively, we show the mean absolute error of the occurrence probabilities of the eight basic colors in Figure 17, where the proposed sparse method denoted by green bars achieved smaller errors compared with the Shaked’s method denoted by orange bars for all twelve SIDBA images.

7. Conclusions

In this paper, we proposed a method for color error diffusion by extending the grayscale Neugebauer model to its color version. The color Neugebauer model represents a color by a linear combination of basic colors, where the coefficients can be interpreted as the occurrence probabilities of the basic colors because they satisfy the probability axioms.

We also proposed a sparse Neugebauer model for color error diffusion halftoning. The proposed sparse method is based on the MBVC proposed by Shaked et al. Therefore, the proposed sparse method can also reduce halftone noise as well as Shaked’s method.

Experimental results demonstrated that the color halftone images given by the proposed method preserve the occurrence probabilities of the basic colors of the original images well. Compared with Shaked’s method, the proposed sparse method achieved a better performance both visually and quantitatively.

Author Contributions

Conceptualization, K.W. and K.I.; formal analysis, K.H.; funding acquisition, K.I.; investigation, K.I.; methodology, K.I.; project administration, K.I. and K.H.; software, K.W. and K.I.; supervision, K.I. and K.H.; validation, K.W., K.I. and K.H.; visualization, K.W. and K.I.; writing—original Draft, K.W. and K.I.; writing—review and editing, K.H. All authors have read and agreed to the published version of the manuscript.

Funding

This work was funded by JSPS KAKENHI grant number JP16H03019.

Conflicts of Interest

The authors declare no conflict of interest.

Abbreviations

The following abbreviations are used in this manuscript:

MBVC	Minimal Brightness Variation Criterion
MBVQ	Minimal Brightness Variation Quadruples

References

Potu, A.; Jayalakshmi, R.S.; Umpathy, D.K. Smart Paper Technology a Review Based On Concepts of E-Paper Technology. IOSR J. Electron. Commun. Eng. (IOSR-JECE) 2016, 11, 42–46. [Google Scholar]
Joseph, A. E-Paper Technology. Int. J. Eng. Res. Technol. (IJERT) 2016, 4, 1–3. [Google Scholar]
Mythili, G.A.; Pavithrah, B.R.; Manjubhashni, S. E-Paper Technology. Int. J. Trend Res. Dev. 2016, 3, 287–288. [Google Scholar]
Hsu, C.-Y.; Lu, C.-S.; Pei, S.-C. Temporal Frequency of Flickering-Distortion Optimized Video Halftoning for Electronic Paper. IEEE Trans. Image Process. 2011, 20, 2502–2514. [Google Scholar] [PubMed] [Green Version]
Kao, W.-C.; Liu, C.-H.; Liou, S.-C.; Tsai, J.-C.; Hou, G.-H. Towards Video Display on Electronic Papers. J. Disp. Technol. 2016, 12, 129–135. [Google Scholar] [CrossRef]
Lau, D.L.; Arce, G.R. Modern Digital Halftoning, 2nd ed.; CRC Press: Boca Raton, FL, USA, 2008. [Google Scholar]
Floyd, R.W.; Steinberg, L. An adaptive algorithm for spatial grey scale. Proc. Soc. Inf. Disp. 1976, 17, 75–77. [Google Scholar]
Monga, V.; Damera-venkata, N.; Evans, B.L. Image Halftoning by Error Diffusion: A Survey of Methods for Artifact Reduction. 2003. Available online: https://pdfs.semanticscholar.org/6b11/d03a00d55ca0a54eace96b5daf76108ab439.pdf?_ga=2.15849334.1131948977.1587112812-1824326568.1544955176 (accessed on 17 April 2020).
Shaked, D.; Arad, N.; Fitzhugh, A.; Sobel, I. Ink Relocation for Color Halftones; HP Labs Technical Reports; HPL-96-127R; InPICS: Portland, OR, USA, 1998; Volume 1, Available online: https://www.hpl.hp.com/techreports/96/HPL-96-127R1.html (accessed on 17 April 2020).
Shaked, D.; Arad, N.; Fitzhugh, A.; Sobel, I. Color Diffusion: Error-Diffusion for Color Halftones. In Color Imaging: Device-Independent Color, Color Hardcopy, and Graphic Arts IV; HP Labs Technical Reports; HPL-96-128R1; International Society for Optics and Photonics: Bellingham, WA, USA, 1999; Available online: https://www.hpl.hp.com/techreports/96/HPL-96-128R1.html (accessed on 17 April 2020).
Reinhard, E.; Khan, E.A.; Akyuz, A.O.; Johnson, G. Color Imaging: Fundamentals and Application; A K Peters/CRC Press: South Avenue Natick, MA, USA, 2008; Available online: https://www.routledge.com/Color-Imaging-Fundamentals-and-Applications/Reinhard/p/book/9781568813448 (accessed on 17 April 2020).
Monga, V.; Damera-Venkata, N.; Evans, B.L. Design of Tone-Dependent Color-Error Diffusion Halftoning Systems. IEEE Trans. Image Process. 2007, 16, 198–211. [Google Scholar] [CrossRef] [PubMed]
Yule, J.A.C.; Nielsen, W.J. The penetration of light into paper and its effect on halftone reproduction. Proc. TAGA 1951, 3, 65–71. [Google Scholar]
Inoue, K.; Hara, K.; Urahama, K. Spectral Reflectance Estimation and Color Reproduction Based on Sparse Neugebauer Model. Adv. Sci. Technol. Eng. Syst. J. 2017, 2, 958–966. [Google Scholar] [CrossRef] [Green Version]
Jarvis, J.F.; Judice, C.N.; Ninke, W.H. A survey of techniques for the display of continuous tone pictures on bilevel displays. Comput. Graph. Image Process. 1976, 5, 13–40. [Google Scholar] [CrossRef]
Stucki, P. MECCA—A Multiple-error Correction Computation Algorithm for Bi-level Image Hardcopy Reproduction. In Communications, Computer Science, Engineering Technology; IBM Thomas J. Watson Research Center: Ossining, NY, USA, 1991. [Google Scholar]
Crocker, L.D. DITHER.TXT. 1989. Available online: http://www.efg2.com/Lab/Library/ImageProcessing/DHALF.TXT (accessed on 20 June 2013).
Sakauchi, M.; Ohsawa, Y.; Sone, M.; Onoe, M. Management of the Standard Image Database for Image Processing Researches (SIDBA). ITEJ Tech. Rep. 1984, 8, 7–12. (In Japanese) [Google Scholar]

Figure 1. Error diffusion coefficients by Floyd–Steinberg [7].

Figure 2. Grayscale Neugebauer model.

Figure 3. Two-dimensional Neugebauer model.

Figure 4. Three-dimensional Neugebauer model.

Figure 5. Eight basic colors ordered on the brightness axis.

Figure 6. MBVQ

{s_{1}, s_{2}, s_{3}, s_{4}}

for a color

f

Figure 6. MBVQ

{s_{1}, s_{2}, s_{3}, s_{4}}

for a color

f

Figure 7. Color image halftoning.

Figure 8. Occurrence probabilities of basic colors.

Figure 9. Absolute errors in occurrence probabilities in Figure 8.

Figure 10. Results on the SIDBA images.

Figure 11. Mean absolute errors of halftoned SIDBA images in Figure 10.

Figure 12. Color image halftoning with zoomed parts.

Figure 13. Occurrence probabilities of basic colors.

Figure 14. Absolute errors in occurrence probabilities in Figure 13.

Figure 15. Halftoned SIDBA images.

Figure 16. Zoomed parts of Milkdrop images.

Figure 17. Mean absolute errors of halftoned SIDBA images in Figure 15.

© 2020 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Wu, K.; Inoue, K.; Hara, K. Neugebauer Models for Color Error Diffusion Halftoning. J. Imaging 2020, 6, 23. https://doi.org/10.3390/jimaging6040023

AMA Style

Wu K, Inoue K, Hara K. Neugebauer Models for Color Error Diffusion Halftoning. Journal of Imaging. 2020; 6(4):23. https://doi.org/10.3390/jimaging6040023

Chicago/Turabian Style

Wu, Kaiming, Kohei Inoue, and Kenji Hara. 2020. "Neugebauer Models for Color Error Diffusion Halftoning" Journal of Imaging 6, no. 4: 23. https://doi.org/10.3390/jimaging6040023

APA Style

Wu, K., Inoue, K., & Hara, K. (2020). Neugebauer Models for Color Error Diffusion Halftoning. Journal of Imaging, 6(4), 23. https://doi.org/10.3390/jimaging6040023

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

Neugebauer Models for Color Error Diffusion Halftoning

Abstract

1. Introduction

2. Grayscale Error Diffusion

2.1. Conventional Method

2.2. Grayscale Neugebauer Model-Based Method

2.3. Equivalence of the Two Methods

3. Extending Grayscale Neugebauer Model to Higher Dimensions

4. Color Neugebauer Model-Based Method

5. Sparse Color Neugebauer Model-Based Method

6. Experimental Results

7. Conclusions

Author Contributions

Funding

Conflicts of Interest

Abbreviations

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI