CHAPTER 1

INTRODUCTION

1.1 OVERVIEW

Half toning is a technology that renders a continuous image with

limited number of tone levels. Traditionally, the number of the tone levels is two,
which means that the dot on the paper is either printed or not printed. Therefore,
such conventional half toning technology can also be called bi-level half toning.
Bi-level half toning can produce perceived similar images compared with other
continuous tone images, because the printer usually has very high printing
addressability or resolution. Due to the low-pass nature of human visual system,
the much higher-frequency content cannot be perceived by human eyes. Thus, the
high-resolution bi-level half toned image is perceived as a continuous image by
appropriate half toning algorithms [Faheem et al (2001)].

The quality of the halftone image can be improved not only by

increasing the printing resolution, but also by raising the number of tone levels
printers could render. I call the tone levels can be printed as native tone, since it
is the inner property of the device. If the printer produces the number of the
native tones which is greater than two, the half toning technology for such printer
is referred to multi toning.

Multi tone printing can be achieved by different mechanism in

different types of printers. Most of the printers can be cataloged as Laser electro
photographic printer and Inkjet printer. For a Laser electro photographic printer,
multilevel half toning is realized by Pulse Width Modulation (PWM). PWM
allows the laser printer to modulate the time duration of the laser beam to provide
sub

1
pixel addressability in laser scan direction, which means that the time of laser
bean turned on or off can be modulated within a fraction to the length of one
pixel. This mechanism basically supports multi tone outputs by increasing the
addressability in the scan direction.

For an Inkjet printer, multi tone writing capability can be achieved

by thermal head, dye diffusion, and multi-drop mechanism. Multi-drop
mechanism generates different number of drops at each addressable pixel to
accomplish multilevel rendering. In this paper, we focus on making Inkjet printer
multilevel outputs by varying the number of drops from the combination of two
pens with different levels of ink concentration.

Most of the traditional half toning technologies fall into three

categories: point operations (screening), neighborhood processes (error
diffusion), and the iterative algorithms (Direct Binary Search (DBS)) [Chandu et
al (2014)]. The quality of half toned image increases in this order. However the
computational complexity also grows in the same order. Screening requires a
pixel-by-pixel comparison between the continuous tone image and the threshold
matrix, so it is least computational. Error diffusion traverses the entire image and
the output is determined by the thresholding, while the quantization error is
diffused to its next neighboring pixels. Both screening and error diffusion can be
operated online and be implemented in the printing devices.

DBS finds the halftone image which is perceived most closely

compared with the continuous image. Although DBS can produce best image
quality, it usually requires several iterations and thus, very computational. It is
commonly not directly used in the printing devices, but DBS provides important

2
off-line design and supports other half toning technology, like Tone Dependent
Error Diffusion, which offers good image quality and can be operated in real
time.

The other two important catalogues for half toning are based on the
texture of half toned image: 1) if the texture is dispersed or clustered 2) if the
texture is periodic or aperiodic. All four combinations (2×2) are possible.
Clustered half toning is always used in the electro-photographic printers, because
the clustered-dot can provide more stable print and less dot-gain effect. The
printing devices which can generate more stable pixels usually employ dispersed
half toning. Clustered periodic half toning commonly provides more
homogeneous structure in mid tone region than the dispersed aperiodic half
toning, while the stochastic aperiodic half toning shows more preferred blue-
noise texture in highlight.

Halftoning or analog halftoning is a process that simulates shades of

gray by varying the size of tiny black dots arranged in a regular pattern. This
technique is used in printers, as well as the publishing industry. If you inspect a
photograph in a newspaper, you will notice that the picture is composed of black
dots even though it appears to be composed of grays. This is possible because of
the spatial integration performed by our eyes. Our eyes blend fine details and
record the overall intensity.

Digital halftoning is similar to halftoning in which an image is

decomposed into a grid of halftone cells. Elements (or dots that halftoning uses in
simulates shades of grays) of an image are simulated by filling the appropriate
halftone cells. The more number of black dots in a halftone cell, the darker the
cell appears. For example, in Fig 1.1, a tiny dot located at the center is simulated
in

3
digital halftoning by filling the center halftone cell; likewise, a medium size dot
located at the top-left corner is simulated by filling the four cells at the top-left
corner. The large dot covering most of the area in the third image is simulated by
filling all halftone cells.

Fig 1.1 A sample of digital halftoning

Three common methods for generating digital halftoning images are

1. Patterning

2. Dithering

3. Error diffusion

Patterning

Patterning is the simplest of the three techniques for generating

digital halftoning images. It generates an image that is of higher spatial resolution
than the source image. The number of halftone cells of the output image is the
same as the number of pixels of the source image. However, each halftone cell is
subdivided into a 4x4 grid. Each input pixel value is represented by a different

4
number of filled squares in the halftone cell. Since a 4x4 grid can only represents
17 different intensity levels, the source image must be quantized. Rylander's
recursive patterning matrices, which will be used in listing Fig1.2, and a sample
of the patterning operation.

Fig 1.2 The Patterning operation

Dithering

Another technique used for generating digital halftoning images is

dithering. Unlike patterning, dithering creates an output image with the same
number of dots as the number of pixels in the source image. Dithering can be
thought of as thresholding the source image with a dither matrix. The matrix is
laid repeatedly over the source image. Wherever the pixel value of the image is
greater than the value in the matrix, a dot on the output image is filled. A well-
known problem of dithering is that it produces artifacts of patterns introduced by
fixed thresholding matrices. Fig 1.3 shows a sample of the dithering operation.

5
 Fig 1.3 The dithering operation

Error Diffusion

Error diffusion is another technique used for generating digital

halftoned images. It is often called spatial dithering. Error diffusion sequentially
traverses each pixel of the source image. Each pixel is compared to a threshold. If
the pixel value is higher than the threshold, a 255 is outputted; otherwise, a 0 is
outputted. The error - the difference between the input pixel value and the output
value - is dispersed to nearby neighbors. Error diffusion is a neighborhood
operation since it operates not only on the input pixel, but also its neighbors.
Generally, neighborhood operations produce higher quality results than point
operations. Error diffusion, when compared to dithering, does not generate those
artifacts introduced by fix thresholding.

6
1.2 LITERATURE SURVEY

Puneet Goyala, Madhur Guptaa, Carl Staelinb, Mani Fischerb,

Omri Shachamc,Tamar Kashtic, Jan Allebacha et al (2011), proposed Electro-
Photographic Model Based Clustered-Dot Half Toning With Direct Binary
Search. The proposed design based on the half toning with direct binary search.
The stochastic model developed is based on microscopic absorptance and
variance measurements. The experimental results show that electro photography-
model based clustered dot half toning improves the homogeneity and reduces the
graininess of printed halftone images and reduces the tiling and mottle artifacts
due to poor development of unstable local halftone patterns.

G. Sarailidis and I. Katsavounidis et al (2012), A Multi Scale

Diffusion Techniques for Digital Half toning. The proposed design based on the
Multi scale Diffusion Techniques for Digital Half Toning. Its main application is
for printing and, similar to half toning, can be applied to both colored and gray
scale images. In this paper, they present a method to produce multi tones based
on the multi scale error diffusion technique. It gives visually pleasing half tones,
with good balance between crispness of edges and smoothness of flat areas.

Jing-Ming Guo, Jia-Yu Chang, Yun-Fu Liu, Guo-Hong Lai,

and Jiann-Der Lee et al (2015), Tone-Replacement Error Diffusion in
Multitoning. The Tone-Replacement Error Diffusion (TRED) which based on the
traditional error diffusion is proposed to improve the multitoning by the
elimination of the banding and noising artifacts.

7
1.3 PROBLEM FORMULATION

 Physically unstable isolated dots will be increased due to the diffusion

of neighbors.

 Increasing the spatial resolution for less visibility.

 Deterministic noise tends to give rise to unnatural repetitive patterns

that appear as unwanted texture.

 Binary toning reduces the image quality.

1.4 OBJECTIVES

 Improve the picture quality

 Reduce the color noise for clarity

 Reduce the unstable isolated Dots.

1.5 ORGANISATION OF THE REPORT

 Chapter1 gives introduction about the half toning, literature survey,

problem formulation, and objective organization of the report.
 Chapter 2 discuss about Existing Half toning Method.
 Chapter 3 deals with Proposed Multi toning Method.
 Chapter 4 deals with Result and Discussion.
 Chapter 5 deals with Conclusion and Future Work.

8
 CHAPTER 2
EXISTING HALF TONING METHOD

2.1 Direct Binary Search (DBS)

Direct Binary Search (DBS) is an iterative half toning

algorithm to minimize the perceived difference between the continuous-tone
image and the halftone image. As shown in Fig. 2.1

Fig 2.1 Objective of Direct Binary Search

The perceived difference is described by the term, mean

square error (MSE) of perceived error between the continuous-tone image
and the halftone image. Due to the low-pass characteristic of the human
vision, the perceived error is the error between the continuous-tone i m a g e
and the halftone image filtered by the Human Visual System(HVS) which is
essentially a low pass filter.

9
 The search strategy for the DBS is that it tries to toggle or swap
each pixel with its neighbor pixel in the raster order. Toggle/swap i s accepted
only if it reduces the error metric most. After all pixels, have been searched
in the image, we call that one iteration finished. After a certain number of
iterations have been finished or the error metric cannot be reduced after an
entire iteration, the DBS algorithm converges. The search strategy of DBS is
shown in Fig 2.2 By properly adding stacking constraint , DBS can
generate a DBS screen. Stacking constraint is the following condition:
Assuming that p[m, n; a0 ] is the dot profile function of the halftone image
at gray level a0 , if p[m, n; a0 ] = 1, then for all gray levels a > a0 , p[m, n; a]
= 1.

Fig 2.2 Search strategy of Direct Binary Search

10
2.2 Error diffusion

Error diffusion works by comparing the actual color of a pixel against its
nearest color and taking the difference between them. This difference is known as
the error. Portions of the error are split between neighbouring pixels causing the
error to be diffused hence the name “error diffusion”.

Fig 2.3 Simple Error Diffusion

With this form of error diffusion half of the error from the current pixel
(represented by the black dot) is diffused to the pixel on the right and half to the
pixel below. In a color image error diffusion, should be applied to the red, green
and blue channels separately.

An important point to note here is that the total amount of error

diffused should never exceed a value of 1. In most cases the total amount of error
diffused will equal 1 although I am aware of one type of error diffusion where the
total error diffused is less than 1.

11
 It is It is also important to ensure that when a portion of the error is
diffused to neighbouring pixels it does not cause invalid values (e.g. go below 0
or above 255). Should a value go outside of the valid range then it should be
truncated (e.g. -10 would be truncated to 0 and 260 would be truncated to 255).

Error diffusion was first proposed by Floyd and Steinberg in

1970s. Error Diffusion is a neighboring process which has two ways to be
viewed. One is to diffuse errors immediately after half toning pixel to all pixels
in the neighborhood; the other is to gather errors from neighboring pixels just
prior to half toning. The first way is helpful to implementation, and the
second way is easy to understand its formulas.

Fig 2.4 Floyd-Steinberg error diffusion

Fig 2.3 shows the diagram of a Floyd-Steinberg Error Diffusion

system, pixel value; g[m, n] is the output binary halftone image which is
determined by a threshold value t[m, n] in a thresholding/quantization
process;

12
d[m, n] is the quantized error; w[m, n] is the weight represents the impact of
the pixel on the it neighbor pixels. Where f [m, n] is the input continuous-tone
image; u [m, n] is the updated

The implementation process can be described as following: first,

we start with the pixel, u[m, n] ≡ f [m, n]; second, we scan the pixels in the
image in a predetermined order, and carry out the following computations:

1. Take threshold: g[m,n]={255 u[m,n] >= t[m,n] {0 otherwise

2. Compute the quantization error : d[m,n]=g[m.n]-u[m,n]
3. Diffuse the error to its neighboring pixels: u[m + 1, n + l] ← u[m + k,
n + 1] − w[k, l]d[m, n].

Specifically, the Floyd-Steinberg error diffusion algorithm scans a

continuous-tone image in the raster order and the quantize threshold is a
constant t[m, n] = 0.5. The error weight matrix is defined as w[0, 1] =
7/16, w[1, −1] = 3/16, w[1, 0] = 5/16, w[1, 1] = 1/16.

2.3 Tone Dependent Error Diffusion

Tone Dependent Error Diffusion (TDED) is an evolution of

Floyd-Steinberg error diffusion. It pre-optimized the weights matrix and the
threshold value dependent on different input continuous-tone. [Allebach et al
(2000)] optimized the parameter by the perception from HVS. For midtone,
highlight and shadow regions, they utilized different strategies to do optimization
and reduce artifacts. However, the optimization process is beyond the content of
their paper. We only use their parameters in the result of this paper.

13
 The halftone image by TDED can greatly reduce the wormlike, edge
effects, start-up artifacts and so on, which are typical visual artifacts in traditional
error diffusion. Fig 2.5 shows the method of TDED approaches that of DBS.

Fig 2.5 Tone Dependent Error Diffusion

2.4 Hybrid Screen

In traditional clustered-dot periodic screen design, there is always a

tradeoff between the screen frequency and the number of realizable gray levels.
The screen frequency is related to the detail rendering of the image. The higher
the screen frequency is, the more capable the clustered-dot periodic screen can
represent the details of the image. However, the increase in the screen frequency
leads to the decrease in the halftone cell size, which directly causes the drop in
the number of realizable gray levels by this halftone cell. Therefore, the super
cell is introduced by using the concept macro dot growing order.

Super cell is the composition of microcells. In- stead of growing the

clusters in each microcell simultaneously, one or several clusters are grown in
one super cell. It means that clusters in each microcell can grow together or grow

14
sequentially, which greatly improve the realizable number of gray levels from the
number of pixels in each microcell to the product of the macro dot growing order
and the number of pixels in each microcell. The realizable gray levels can be as
large as the number of all pixels in the super cell. Another important
improvement

in hybrid screen is the concept of core. Because the Bayer screen induces maze-
like artifacts in the highlight region, the natural replacement to it is the stochastic
and blue-noise half toning like DBS[Rodriguez et al (2008)].

The strategy here is that in each microcell, we set up an area called

cores. In the cores, the microcell growth order is not obeyed. Instead, pixels grow
randomly in the cores chosen by DBS. What‟s more is that the macro dot
growing order is determined by the growing order of the first turned on pixel in
each core.

The combination of super cell and the core not only solves the trouble
of limited number of realizable gray levels but also eliminates the maze-like
artifacts in the highlights. Hybrid screen keeps the advantages of clustered-dot
periodic screen, like the homogenous texture in the mid tones and has the
strength of DBS, such as the stochastic, blue-noise highlight texture.

2.5 MultiLevel Toning

The ink printer utilizes two different ink density pens of

multi-drop capability to generate multilevel native tones. The two drop pens
are called full drop pen and light drop pen due to the different density of the
pens. The density of the drop pens is subject to changing. In this Chapter, we
modulate that the density of three drops from the light drop pen are equal to

15
the density of one drop from the full drop pen. According to dot arrangement
in the Table 2.1, we can achieve at most 13 native tones. In this Chapter,
we refer to the number of native tones (including paper white) as N = 13.

Table 2.1 Dot arrangement for two drop pens

GL# Gray level Light Drops Full Drops

0 0 0 0
1 21 1 0
2 43 2 0
3 64 3 0
4 85 1 1
5 106 2 1
6 128 3 1
7 149 1 2
8 170 2 2
9 191 3 2
10 213 1 3
11 234 2 3
12 255 3 3

One principle for dot arrangement is that we hope to make the

arrangement in order, like light drops the order is 1 → 2 → 3 → 1 → · · · → 3.
Another notice is that no drop or 0 drop is probably unstable and is not
suggested. The Table 1.1 meets these principles. Anyhow, there are two drop
pens in the printer i n s t e a d of one in the bi-level Inkjet. Unfortunately,
there is a possible displacement between the two drop pens, which would
possible results in a misregistration like situation.

16
One-Two-Tone-Mixture Schedule S1−2 Half toning Design

A simple one-two-tone-mixture schedule S1−2 for multilevel half

toning that can be straightforwardly extended from bi-level half toning. In this
method extend the bi-level DBS screen, error diffusion, Tone Dependent Error

Diffusion, and hybrid screen to the corresponding multilevel versions. It first

describes the modification made on the traditional half toning methods. After
that, experimental results will be shown respectively. And the experiments from
different half toning are compared in the rest of this section.

Each absorptance is represented by one or two native tones, so the

sub-notation 1−2 is used here. A monotone absorptance increasing halftone ramp
is composed of several period-like textures. Each period contains only two native
tones. One period of the multilevel half toning is called multi tone cell. One-two-
tone-mixture schedule can be described by the Fig. 2.5. For example, in the gray
level region from α1 to α2, the fraction of native tone α1 pixel monotonically
decreases, while the fraction of native tone α2 pixel raises monotonically.

Fig 2.6 One-Two-Tone-Mixture Schedule S1−2

17
Multilevel DBS Screen

Multilevel half toning with DBS screen of four native tones.

Contouring artifacts are observed in the simple one-two schedule. However, with
the increase of the number of native tones to thirteen, which means the sharp

decreases of the gray level contrast between the adjacent native tones, we believe
that the quality will be greatly improved [Blum et al (2014)]. We first decide at
which multi tone cell, the output should be located. Meanwhile, it determines
which two of the native tone levels will be considered, according to Eq: i = f [m,
n]/ (256/ (N − 1))]

Where f [m, n] is the input continuous-tone image. N = 13 is the

number of native tones.

Fig. 2.7 Ramp half toned by multilevel DBS screen

We note that no texture at gray level α0, α1, . . . , α12, but the
contouring artifacts between the texture and no-texture area is not very
perceivable. And in every multi tone cell, it shows quite smooth texture.

18
Multilevel Tone Dependent Error Diffusion

Tone Dependent Error Diffusion is an evolutional version of Floyd-

Steinberg error diffusion proposed by [Allebach et al(2000)]. We can guess the
evolution in Tone dependent Error Diffusion from its name. The weights and the
threshold are all dependent on the input tones. The weights and threshold are
optimized with the assistance of DBS.

The TDED algorithm removes most of the visual artifacts of

conventional error diffusion. It produces halftone images with quality
approaching that of DBS, but with much lowers complexity. Due to the good
quality and low computation, TDED is widely used in InkJets. The modification
to TDED for multilevel is that we make the threshold periodic, but we did not
change the weights.

Fig 2.8 Tone Dependent Error Diffusion threshold

19
Summary and Comparison for Four Multilevel Half toning

Generally speaking, we can say that, from the ramps half toned
by the four-multilevel half toning, the DBS and hybrid screen surmount error
diffusion or Tone Dependent Error Diffusion, while hybrid screen even shows
more homogeneous texture in the mid tone area than DBS does. On the other
hand, although it is not obvious, all the four multilevel half toning technologies
show the contouring artifacts in the area where there is no texture. We hope to
eliminate such contouring by keeping the texture all along in the ramp.

Two-Four-Tone-Mixture Schedule S2−4 Half toning Design

Observing the contouring artifacts caused by the no texture

area in one-two tone-mixture schedule, we wish to use a schedule that contains
texture in the entire ramp. As the first step, we generate a 4 × 4 screen, before we
go further. There are thirteen native tones for choice, so the contrast graylevel or
density between two adjacent native tones is very small. Our objective is to keep
texture of a contrast of two intervals of native tones throughout the whole ramp.
The ideal checkerboard to achieve during the intermediate step is Table 2.2. In
the table, k is the index of native tones and 0 ≤ k ≤ 10.

Table 2.2 Ideal checkerboard texture to achieve during intermediate steps

Αk αk αk+2 αk+2

Αk αk αk+2 αk+2

αk+2 αk+2 Αk αk

αk+2 αk+2 Αk αk

20
 The principle for growing the dots is that: According to Table
2 . 3 . We separate the halftone cell into four quadrants. As we see in Table
2 . 2 , we hope in the intermediate steps the contrast between Quadrant I/IV
and Quadrant II/III is two intervals of native tones. In addition, in the
growing order, as long as we grow the pixel in Quadrant I/IV to the next
native tone, the pixel in Quadrant II/III has to be improved to the next native
tone in the following step. Referring to this principle, we generate a halftone
ramp, with the index matrix in Table 2.4

After carefully checking the dot growing order and the

halftone ramp generated, we can find that for every gray level, there are always
two or three or four native tones. Therefore, we can it the two-four-tone-
mixture schedule.

Table 2.3 Identification of the four quadrants in the halftone cell

I I II II
I I II II
III III IV IV
III III IV IV

Table 2.4 Index matrix for the two-four-tone-mixture schedule

13 5 10 14
9 1 2 6
8 4 3 11
16 12 7 15

21
 For comparison, we also generate a same size screen with a
similar index matrix (see Table 2.5), but of one-two-tone-mixture instead of
two-four-tone-mixture.

Table 2.5 Index matrix for the one-two-tone- schedule mixture

15 11 3 7
13 9 1 5
6 2 10 14
8 4 12 16

We can tell that a l t h o u g h the half tone ramp by two-four

schedules is noisier that that by one-two schedule, the entire ramp by two- four
schedule contains more similar structures. Instead, in the one-to-two
schedule, there is more obvious contouring. The 4 × 4 screen here is our
first step to test the two-to-four schedule, which is a very simple screening
half toning, so we perceive lots of artifacts resulted from the limitation of
quantization(Number of realizable gray levels by the screen is very limited.).
It is believable that t h e texture c a n be improved by better h a l f toning
technology. Two-four-tone-mixture schedule can be told as promising,
compared with one-two-tone-mixture schedule.

22
 CHAPTER 3
PROPOSED CLUSTERED DOT MULTI TONING

3.1 Introduction

Multi toning is used to render continuous-tone images with output

devices that are capable of directly printing or displaying only two or a small
number of different gray levels. For example, Inkjet systems may have light
and dark pens for a given color and/or they may be capable of placing 0, 1,
or 2 drops at a given addressable pixel location. The various combinations of
drop density and number of drops yield what we refer to as a set of native
tones. Multi toning succeeds by generating a high spatial frequency pattern of
alternating native tone values that i s not well resolved by the human observer
at normal viewing distances. Instead, a local spatial average of the texture is
perceived.

The three most widely used categories of half toning methods are
pixel method, neighboring method, and iterative method. Usually the
halftone output quality and computation timing both increase in the order
of pixel, neighboring and iterative. The pixel method i s known as screening,
or dither. For example, L i c h e n pro- posed a dither method to generate the
blue-noise which is visually pleasant halftone pattern [Lichen et al (2008)].
Pixel method compares or computes on the pixel of the screen and
corresponding pixel on the image only, so it is usually computational-
efficient. Another pixel method is look-up-table half toning.

Li and Allebach (2000) invented a look-up-table half toning using

the correlation information between different gray levels in order to
minimize

23
the artifact noise. The neighboring method is well-known as the Floyd-
Steinberg error diffusion. It diffuses the error between the halftone output
image and the continuous-tone input image to the afterward pixels in the
raster order. It is essentially serial algorithm, so error diffusion is more
computational inefficient than pixel method. Lots of work has been done to
improve the error diffusion algorithm [Goldschneider et al(1997)].

Tone Dependent Error Diffusion was invented by Li and Allebach,

which largely eliminated t h e artifacts c a u s e d by the conventional e r r o r
diffusion. The most visually pleasant halftone pattern can be generated by
the iterative m e t h o d , like Direct Bi- nary Search (DBS). DBS is
computational inefficient, but it is widely used combined with other
halftoning algorithms. Lin and Allebach invented the FM screen by DBS with
the stacking constraint.

Hybrid screen also use DBS to generate the blue-noise texture in the
highlight and shadow regions. Tone Dependent Error Diffusion trained the
coefficients and thresholds by the blue-noise DBS pattern in Fourier domain.
With the assistance of off-line design by DBS, screen or error diffusion can
significantly improve the halftone quality and remain the same computational
complexity.

On the other h a n d , according the halftone texture, we can also

separate the multi toning algorithm as AM, which is also called clustered-
dot, and FM, which is also called dispersed-dot. Using the modulation
con cept s in communication t h e o r y . We define the multi toning as AM,
when the pattern forms the clustered dots, as the absorptance glows , which
in Fourier domain produces a donut-like band-pass green- noise filter [Allebach
et al (1996)]. However, FM halftone pattern generates the high-frequency blue
noise in

24
Fourier domain. Usually, Ink-jet can produce much more robust single dots, so
it uses dispersed-dot multi toning more often. However, due to the instability
of the single dots produced by electro-photographical printers, they use
clustered-dot multi toning more often. Another classification of multi toning
according to the texture is periodic or aperiodic. Screen is a periodic multi
toning, while error diffusion and DBS are aperiodic.

All four combinations ( AM/FM, periodic/aperiodic, 2 × 2) are

possible. Multi toning is always used in the electro-photographic printers,
because the clustered- dot can provide more stable print and less dot-gain
effect. The printing devices which can generate more stable pixels usually
employ dispersed multi toning. Clustered periodic multi toning commonly
provides more homogeneous structure in mid tone region than the dispersed
aperiodic multi toning, while the stochastic aperiodic multi toning shows more
preferred blue-noise texture in highlight. The other multi toning algorithm
may apply hybrid texture, like hybrid screen, which has the blue-noise
dispersed dot in highlight and shadow region, also enjoys the homogenous
clustered periodic texture in the mid tone.

In multi toning, three categories: pixel, neighboring and iterative

m e t h o d s can all be adapted f o r multilevel output devices. For example,
[Sarailidis et al (2012)] describe an error-diffusion-like approach that is based
on the correlation between adjacent pixels. Ideally, the multilevel multi toning
has much better p r i n t i n g qu al it y than b i -level halftoning. However, multi
toning has its own trouble a s well. When the desired tone-value is near a
native tone, traditional multi toning approaches use the native tone of the
output device directly. In these areas of the output image, there will be no
halftone

25
texture. Consequently, as the gray value of the continuous- tone image to be
rendered changes smoothly, the output image transitions between regions
with halftone texture a n d regions with no halftone texture. This may cause
an objectionable c o n t o u r i n g a rt i f ac t . To overcome this problem, introduce
overmodulation implemented via a lookup-table-based approach.

Lin and Allebach ( 2 0 0 2 ) use a schedule-based framework to

control the number of native tones used to render any specific gray level.
Bacca Rodriguez (2008) implement stochastic, dispersed-dot multi toning by
applying error diffusion to separate channels of the image that has been
decomposed according to the range of gray levels.

All these approaches use stochastic, dispersed-dot halftone

textures. They all do eliminate contouring, but at the expense of an increase
in graininess relative to traditional multi toning. In addition, the
characteristics of the halftone texture changes continually as a function of
gray level, which further increases the visibility of these textures.

3.2 CLUSTERED DOT HYBRID SCREEN

GEOMETRIC PARAMETERS

In periodic screen multi toning, w e use a pair of linearly

independent screen tile vectors z = [z1 , z2 ] and w = [w1 , w2 ] to represent
the parallelogram multi tone screen. The parallelogram multi tone screen
limited by those vectors can be called continuous- parameter multi tone cell
(CPMC). By repeatedly t i l i n g the CPMC, we can cover the whole multi

26
tone image by it. In digital multi toning, w e assume a printing d o t as a
square dot.

Hence, by line quantization, we can define a discrete-parameter

multi tone cell (DPMC) from CPMC. We let Ω denote a single period or unit
cell of this pattern, which we refer to as a microcell. Microcell and it
relation wi th super cell will be discussed in the next subsection. The screen
matrix or periodic matrix of the DPMC

Ω is defined by the combination of the two vectors, such as M = [zT |wT

Microcell and Super cell

Each microcell can represent |Ω| + 1 gray levels 0, 1/|Ω|,

2/|Ω|, ..., (|Ω| − 1)/|Ω|, 1, by setting 0, 1, 2, ..., |Ω| − 1, |Ω|, pixels equal to 1,
respectively. As the example mentioned above, only |Ω| = det|M| = |3 × (−3)
− 1 × 1| = 10 pixels are in that microcell. Then the output gray levels that
c a n be rendered by that h a l f t o n e cell are limited by 10 + 1 = 11. We hope
that t h e possible gray levels can reach 256 or even larger, like 1024.
However, as |Ω| increases for an output device with fixed spatial resolution,
the number of realizable gray levels increases; but the halftone texture
becomes increasingly visible.

Super cell techniques a l l o w one to achieve a greater number of

output levels, while still keeping |Ω| relatively small. All the half toning
methods to be described in this paper will use the super cell method; In
particular, we will use a variant of the super cell method, known as the
hybrid screen that generates high quality stochastic, aperiodic, dispersed-dot
textures in the highlights and shadows that transition to periodic, clustered-
dot textures in the mid tones. There are two sets of orders in the half toning
27
screen. One is still the order of the microcell. Another is the macro dot
order which

represents the order among the microcell in one super cell. Although most
of the microcell or the tiling of microcells, super cell, are not square or
rectangular, we still hope to represent a periodic screen as a rectangular,
because it would be more convenient to store or process in the computer.

DOT PROFILE FUNCTION

We will describe our half toning processes in terms of the dot

profile function p[m, n; a], which is the halftone pattern used to represent
each level of constant tone 0 ≤ a ≤ 1, where level 0 denotes the absorptance of
paper only with no colorant; and level 1 denotes the absorptance of the
paper printed with the maximum amount of colorant. In the subsection
above, we let Ω denote a single period or unit cell of this pattern. We refer to
Ω as a microcell as well. Each microcell contains |Ω| = det(M) pixels.

3.3 Dot Hybrid Screen

Hybrid screen uses DBS to generate the blue-noise

highlight gray levels and uses the periodic clustered-dot screen to generate the
homogenous mid tone regions. Therefore, it is called ‟hybrid‟ screen. The most
significant concepts in the hybrid screen are super cell and core. We focus on
the advantage of using core. Because the Bayer screen induces maze-like
artifacts i n the highlight region, the natural re- placement to it is the stochastic
and blue-noise half toning like DBS. The strategy here is that i n each
microcell, we set up an area called cores. In the cores, the microcell growth
order is not obeyed. Instead, p i x e l s grow randomly in the cores chosen
28
DBS. What‟s more is that the macro dot growing order is determined by the
growing order of the first turned-on pixel in each core.

The combination of super cell and the core not only solves the
trouble of limited number of realizable gray levels but also eliminates the
maze-like artifacts in the high- lights. Hybrid screen keeps the advantages of
clustered-dot periodic screen, like the homogenous texture i n the mid tones
and has the strength o f DBS, such as the stochastic, blue-noise highlight
texture.

3.4 Multilevel Clustered-dot, Periodic Multi toning

Our choice of the prototype h a l f t o n e texture that we try

to maintain across the entire tone scale is based on two criteria: (1) it should
be the texture that would be used with a bi-level multi toning process to
represent a gray value near a = 1/2; and (2) it should have a simple and
regular geometric shape. The prototype half tone texture i s shown as having

levels α+ and α− . For a binary half toning process, these two levels would

be α+ = 1 and α− = 0. Note that o u r choice of prototype b i n a r y texture

corresponds to a gray level of 0.4 in absorptance units and the region with

level α+ is a 2 × 2 square. How- ever, our choice of the region with level α+
is not restricted t o square. It can be rectangular as well, which as if it
complies with the two criteria as close as possible.

29
 Fig 3.1 Prototype microcell p0 [m, n; a] and prototype mu l t i t o n e
texture p [m, n; a].
Optimizing the Dot Profile Transition Order

In the previous section, we described a process whereby

the native tone values are alternately incremented within the regions Ω+

and Ω− to maintain t h e form of the prototype h a l f t o n e texture, as specified

for example, by the index matrix illustrated in Fig. 3.2. This determines the

division of the indices 1, 2, ..., |Ω| between the two regions Ω+ and Ω− .
indices within these two regions. We also discussed, in general terms, the
tradeoff between maintaining constancy of the texture Specifically, {2, 4, 7, 9}

∈ Ω+ ; and {1, 3, 5, 6, 8, 10} ∈ Ω− , as shown in Fig. 3.1. However, it does

not specify the spatial arrangement of the two subsets of shape and
minimizing overall texture visibility.

30
 Fig. 3.2 Three steps to realize one-level-contrast multi toning.

INTER-ITERATIVE CLUSTERED-DOT DIRECT MULTI-BIT SEARCH

(CLU-DMS) SCREEN DESIGN

The method of generating stochastic clustered-dots for a green-noise

property preferred by laser printers is first introduced. Subsequently, the screen
construction which exploits the benefits of generated homogenous multi tone
outputs is detailed.

31
INTER-ITERATIVE CLU-DMS

CLU-DBS generated halftone clusters for a green-noise property

with the use of two-component cost function, which was majorly formulated by
both initial filter ci p˜ p˜ [m, n] and update filter cu p˜ p˜ [m, n]. Its purpose is to
minimize the perceived errors between the continuous tone image f [m, n] ∈ [0,
1] and the multi tone image g [m, n] ∈ {αi|0 ≤ αi ≤ 1}S i=1. There are two main
stages, trial and update, involved in the iterative process for each pixel of an
image. Prior to these stages, an initialization stage is required to form an initial ci
p˜e˜0 [m, n] with ci p˜ p˜ [m, n] for simulating the perceived error as ci p˜e˜0 [m,
n] = e0 [m, n] ∗ ci p˜ p˜[m, n], where e0 [m, n] = g0 [m, n] − f [m, n], where the
operator „∗‟ denotes convolution, and g0 [m, n] denotes the initial multi tone
pattern for being optimized. Subsequently, the trial and update stages are
performed with a different filter cu p˜ p˜ [m, n] in opposed to the use of ci p˜ p˜
[m, n].

Algorithm for Inter-Iterative CLU-DMS

Fig 3.3 Algorithm for CLU-DMS

32
Screen Design

The screens can be decomposed into multiple multi tone masks In

generated by the proposed inter-iterative CLU-DMS algorithm as introduced in
Section 3.5 with the given f [m, n] = η. In a practical case of screening a gray
scale image with 256 tones, there are 256 masks Iη obtained for various possible
absorptance levels η ∈ [0, 1]. To obtain a specific multi tone screening output q
[m, n] by threshold the stacking constraint is applied during the screen
construction: Iη [m, n] ≥ Iη−1/L [m, n], where L = 255 denotes the maximum
gray scale value [Chandu et al (2014)]..

Nowadays, many approaches have been presented to construct

screens in terms of the order of gray scales, such as 1) from one extreme tone (0
or 1) to another extreme tone (1 or 0), 2) inwardly change from both extreme
tones to mid tone, or 3) outwardly change from mid tone to both extreme tones.
The influences of the above different ways mainly depend upon the stacking
constraint that offers the least restriction at the beginning of screen construction
and the most restriction at the end. This ends up with noisy multitone texture
generated by the constructed screens at the tones which suffer the most from the
stacking constraint.

Consequently, the first way generates an obvious quality difference

between the optimized multitone masks Iη around two opposite extreme tones η
= 0 and η = 1. Conversely, the masks Iη at around opposite extreme tones
generated by the second way are quite similar in terms of their spectrum property
since almost no constraint is considered during their mask generation. The third
way also generates similar masks Iη around two opposite extreme tones because
the restrictions of the stacking constraint for them are identical.

33
Fig. 3.4 Generated screening outputs of size 32 × 32 with Chandu et al.’s
method (2014), where Dmin = 4. (a) η = 1/32. (b) η = 2/32. (c) η = 4/32. (d) η
= 8/32. (e) η = 16/32. (f) η = 24/32. (g) η = 28/32. (h) η = 30/32. (i) η = 31/32.

34
 CHAPTER 4
RESULT AND DISCUSSION

4.1 EXISTING SIMULATION RESULTS

HALF TONING
Digital half toning is a technique for converting continuous-tone
images into binary images. These binary images resemble the original images
when viewed from a distance because of the low-pass nature of human visual
system (HVS).

Many image rendering technologies only have binary output. For

example, printers can either “fire a dot” or not. Halftoning is a method for
creating the illusion of continuous tone output with a binary device. Effective
digital halftoning can substantially improve the quality of rendered images at
minimal cost.

HALF TONING SIMULATION RESULT

Fig 4.1 Half Toning Input image

35
 Fig 4.2 Half Toning Output image

The algorithm scans the image from left to right, top to bottom,
quantizing pixel values one by one. Each time the quantization error is
transferred to the neighboring pixels, while not affecting the pixels that already
have been quantized. Hence, if a number of pixels have been rounded
downwards, it becomes more likely that the next pixel is rounded upwards, such
that on average, the quantization error is close to zero.

The diffusion coefficients have the property that if the original pixel
values are exactly halfway in between the nearest available colors, the dithered
result is a checkerboard pattern. For example, 50% grey data could be dithered as
a black-and-white checkerboard pattern. For optimal dithering, the counting of
quantization errors should be in sufficient accuracy to prevent rounding errors
from affecting the result. Fig 4.2 Shows the Halftoning output image.

SPATIAL FREQUENCY

Spatial frequency refers to the level of detail present in a stimulus per

degree of visual angle. A scene with small details and sharp edges contains
more high spatial frequency information than one composed of large coarse
stimuli.

36
 Fig 4.3 Half Toning Spatial Frequency for Pixels/cycles

Spatial frequency is expressed by the number of cycles of

alternating dark and light bars per degree of visual angle. For example, the top
grating above has more light-dark bars per degree of visual angle so it is of
higher spatial frequency than the one below it. Since the visual angle of a
stimulus becomes smaller with increased viewing distance, moving away from a
particular stimulus increases its high spatial frequency content. Thus the
advantage of specifying spatial frequency this way is that it accounts for both the
size of the stimulus and its viewing distance from the eye .Fig 4.3 shows the
spatial frequency of Half toning image.

37
 Fig 4.4 Half Toning Threshold Values

Absorptance of the surface of a material is its effectiveness in

absorbing radiant energy. It is the fraction of incident electromagnetic power that
is absorbed at an interface, in contrast to the absorption coefficient, which is the
ratio of the absorbed to incident electric field. Absorptance value is larger means
the printed image will be darker. In Fig 4.4 shows the absorptance level is high so
the halftoning printed image is darker. So the quality of the output image is low.

38
DISADVANTAGE

 Physically unstable isolated dots will be increased due to the diffusion of

neighbors.

 Increasing the spatial resolution for less visibility.

 Deterministic noise tends to give rise to unnatural repetitive patterns that

appear as unwanted texture.

 Binary toning reduces the image quality.

4.2 PROPOSED SIMULATION RESULTS

Multi-Toning Technique:

The first multi tone screening method to generate stochastic clustered-dots

for a much better visual quality. The pixel validation map is mainly utilized to
restrain the possible dot growing region to form dot clusters. In this method, the
quantization error at each pixel was diffused to neighbors for error compensation.

Fig 4.5 Multi Toning Output image

39
 Fig 4.5 shows the concrete outputs with a real-world image -
nature. This image has high contrast, fine structure, various spatial frequencies,
and smooth regions of dark and light colors. Thus, it is a good natural benchmark
to evaluate the performance of the methods. To objectively evaluate the image
quality, the human-visual peak signal-to noise ratio (HPSNR) the higher the
better) with three various Gaussian kernel sizes, 7 × 7, 15 × 15, and 31 × 31, are
used to estimate the visual similarities at different configurations of viewing
distances and printing resolutions (dpi). As it can be seen, this method renders
noisier textures with lower HPSNR values in contrast to that of the proposed
method. In addition, a significant improvement is achieved in terms of the
homogeneity.

Fig 4.6 Multi Toning Spatial Freq For Cycles

40
 Cluster degree is directly proportional to the spatial frequency.
Spatial frequency refers to the level of detail present in a stimulus per degree of
visual angle. A scene with small details and sharp edges contains more
high spatial frequency information than one composed of large coarse stimuli.
Fig 4.6 shows the spatial frequency of the cycles for Multi toning. Compare to
halftoning the spatial resolution is low. So the Image visibility increased.

Fig 4.7 Multi Toning Threshold Values

41
 Figure 4.7 show an interesting property that the first and the last
absorptance states α1 and αS are utilized with a higher proportion over
rendering various absorptance levels η. In this case, the dot clusters grow by
firstly from their central positions and the values are gradually
decreased/increased to the opposite extreme absorptance levels (1 to 0 or 0 to
1), and then gradually change the values of nearby dots with the intermediate
absorptance states of each cluster. Absorptance level is low so the image quality
is high.

ADVANTAGES

 Improve the picture quality

 Reduce the color noise for clarity

 Reduce the unstable isolated Dots.

45
 CHAPTER 5

CONCLUSION AND FUTURE WORK

5.1 CONCLUSION

In this work, the inter-iterative CLU-DMS is proposed to design

screens for the generation of stochastic clustered dot multi tone results. For the
optimization, the tactic of coordinating intra-iteration and inter-iteration is
proposed to circumvent the potential issue of trapping in a local minimum cost
in the conventional approaches such as DBS and CLU-DBS. Formerly, simply
one inter-iteration is involved in the conventional methods. This works for the
DBS since the terms in its cost function are updated for approaching the
minimum cost. Yet, this is not feasible for CLU-DBS, since the optimized
output highly relies on the initial multi tone pattern. To ease this effect and
achieve a greater clustering rendition, the inter-iteration method is proposed to
ensure that the initial multi tone pattern can also be gradually updated to form a
uniformly distributed cluster. As documented in the experimental results,
apparent superiorities in terms of the dot homogeneity and noise reduction can
be achieved, ensuring its practical value compared to the state-of-the-art
methods.

5.2 FUTURE WORK

The pixel validation map is mainly utilized to restrain the possible dot
growing region to form dot clusters. In this method, the quantization error at
each pixel was diffused to neighbors for error compensation. Calculating the
clusters for inter iteration pixels. To avoid the overlapping for toner. A clustered
dot multi toning method to yield stable dots for the EP printers.

45
 REFERENCES

[1] [Link] and [Link],(2015) “Dot-diffused halftoning with improved

homogeneity,” IEEE Trans. Image Process., Vol. 24, No. 11.

[2] [Link], (2014) “Multilevel printing process and device using a raster
bitmap and assignment method for multilevel screens,” U.S. Patent
8675251.

[3] [Link], [Link], [Link], and [Link], (2014) “Hybrid halftoning

using direct multi-bit search (DMS) screen algorithm,” Proc. SPIE, Vol.
9015, p. 90150P.

[4] [Link], K. Chandu, [Link], and [Link],(2013) “A GPU based

implementation of direct multi-bit search (DMS) screen algorithm,” Proc.
SPIE, Vol. 8655, p. 86550Z.

[5] [Link] and [Link], (2012) “A multiscale error diffusion

technique for digital multi toning,” IEEE Trans. Image Process., Vol. 21,
No. 5.

[6] [Link], [Link], and [Link],(2007) “Method for

multilevel printing of digital images using reduced colorant amounts,” U.S.
Patent 7190485.

[7] [Link] and [Link],(1993) “Mean-preserving multilevel halftoning

algorithm,” in Human Vision, Visual Processing and Digital Display Vol.
1913.

[8] [Link] and T. Matika,(1995)“An improved multilevel error diffusion

method,” J. Imaging Sci., Vol. 39.
[9] [Link], [Link], and G. [Link], (2001)“Multilevel halftoning using
bilevel quantizers,” in in Proceeedings of IS& T‟s 2001 Processing
Images, Image Quality, Capturing Images, Systems (PICS) Conference
(Society for Imaging Science and Technology, Springfield), pp. 51–54.

[10] [Link], (2008)“Hybrid screen design and automatic portrait image

enhancement,” Phd Dissertation, p. 11.

[11] [Link] and [Link], “FM screen design using DBS algorithm,(1996)”
Vol. 1, pp. 549–552.

45
[12] C. H. Lee and J. P. Allebach,(2012) “The hybrid screen–improving the
breed,” IEEE Trans. on Image Processing, Vol. 19.

[13] [Link] and [Link],(2003) “Digital color halftones,” Digital

Color Imaging Handbook, [Link], Ed.

[14] [Link] and [Link], (2002)“Multilevel screen design using direct

binary search,” [Link].A, Vol. 19.
[15] [Link] and [Link], (2000)“Look-up-table based halftoning algorithm,”
IEEE Trans. Image Processing, vol. 9, pp. 1593–1603, September 2000.

[16] [Link], [Link], and P.W. Wong, (1997)“Embedded

multilevel error diffusion,” IEEE Trans. on Image Processing, Vol. 6, pp.
956–64.

[17] J. B. Rodriguez, G. R. Arce, and D. L. Lau,(2008) “Blue-noise multitone

dithering,” IEEE Trans. on Image Processing, Vol. 17, pp. 1368–1382.
[18] [Link]´c, [Link]´c, [Link]´c, and [Link],
(1999)“Cellular neural network for automatic multilevel halftoning of
digital images,” in Proceeedings of the IEEE International Symposium on
Circuits and Systems.

45