Digital Image Processing

Some Special Techniques

Dithering

01/29/16

Duong Anh Duc - Digital Image Processing

Dithering
Dithering, also called Halftoning or Color
Reduction, is the process of rendering an
image on a display device with fewer colors
than are in the image. (Mateus Pins and
Hermann Hild)
The number of different colors in an image or
on a device is used called its Color Resolution.

01/29/16

Duong Anh Duc - Digital Image Pro

Dithering
If the display device has a higher spatial resolution
than the image that you are trying to reproduce, it can
show a very good image even if its color resolution is
less. This is what we will call 'dithering' and is the
subject of this work.
Dithering is a one-way operation.
Once an image has been dithered, although it may look like
a good reproduction of the original, information is
permanently lost.
Many image processing functions fail on dithered images.

01/29/16

Duong Anh Duc - Digital Image Pro

Dithering

01/29/16

Duong Anh Duc - Digital Image Pro

Dithering
Grey-scale and colour simulation
Dithering on a screen or printer is analogous
to the half-toning techniques used in the print
industry.
A CRT can be considered to be a complex
colour dithering device with variable colour
intensity.

01/29/16

Duong Anh Duc - Digital Image Pro

Dithering
Grey-scale and colour simulation
We need to display colour and grey-scale
images on output devices that have a lower
information-carrying capacity.
Cheap printers are bi-level or CMYK - clearly
we need to add colours/intensities to
approximate an image.

01/29/16

Duong Anh Duc - Digital Image Pro

Dithering Methods
(Digital Halftoning)
Threshold dithering
ordered dither
stochastic dither
dot diffusion
....

01/29/16

Error diffusion
dithering
Floyd-Steinberg
Burkes
Stucki
Sierra
Jarvis, Judice and Ninke
Stevenson and Arce

Duong Anh Duc - Digital Image Pro

Dithering in Printing Industry

Newspapers
black

ink on light paper, rasterization of theimages

enables also grey levels, equal pointdensity
everywhere, variable size

Color printing
every

primary color is rasterized

separately,different printing angles ensure
unbiased results
01/29/16

Duong Anh Duc - Digital Image Pro

Simple shading techniques

A series of examples
Original picture, half-toning
simulation by a non-PostScript
laser printer.
The original image has an 8bit grey scale palette.
The laser printer has only got
a 1-bit palette (ie bi-level,
black and white) and must
simulate the original shading.
01/29/16

Duong Anh Duc - Digital Image Pro

Simple shading techniques

An example
Bayer - Ordered Dithering
This method uses a set of
regular arrays of values,
leading to a regular (and
visually poor) output.
This method creates abrupt
changes between areas,
changes that do not exist on
the original. Such artefacts are
not desirable.
01/29/16

Duong Anh Duc - Digital Image Pro

10

Simple shading techniques

An example
Burkes
This method uses an errordistribution algorithm to
minimise percieved errors.
Changes in the average
intensity vary quite smoothly,
resolution permitting, leading
to a more acceptable image.

01/29/16

Duong Anh Duc - Digital Image Pro

11

Simple shading techniques

An example
Floyd-Steinberg
FS dithering is popular and
commonly used. It is
robust and quite general.
FS dithering works best on
images with few highcontrast transitions.

01/29/16

Duong Anh Duc - Digital Image Pro

12

Threshold Dithering
every pixel is compared to a threshold t:
pt a
p>t b

t can be:
equal

everywhere (e.g. (ba)/2,arbitrary value,

mean value, median, ...)
location dependent (defined locally or globally)

01/29/16

Duong Anh Duc - Digital Image Pro

13

Constant Threshold Dithering

sample image

threshold values

result

(values between 0 and 9)

corresponds to rounding
01/29/16

Duong Anh Duc - Digital Image Pro

14

Principle of Dithering
Available values a, b
Missing value x between a and b shall
besimulated by mixing a-pixels and b-pixels

01/29/16

Duong Anh Duc - Digital Image Pro

15

Principle of Dithering

01/29/16

Duong Anh Duc - Digital Image Pro

16

Dithering a Uniform Area

for a uniform area regular application of
this pattern
will produce
this grey tone
interval borders
all grey levels in this interval
will be mapped to 1/4
01/29/16

Duong Anh Duc - Digital Image Pro

17

Dithering a Uniform Area

This can be done by using a different threshold
for every pixel (using the interval borders)

01/29/16

Duong Anh Duc - Digital Image Pro

18

Threshold Matrix
Distances between interval borders are equal,
therefore it suffices to define the sequence of the
pixel values in the matrix:
instead of

only

i.e. for an nxn matrix: values [0,n21]

Value k corresponds to threshold value: 2k+1/2n 2
01/29/16

Duong Anh Duc - Digital Image Pro

19

Dither Matrix Example

dither matrix

threshold matrix

Value k corresponds to threshold value: 2k+1/2n2

01/29/16

Duong Anh Duc - Digital Image Pro

20

Threshold Matrix Dithering Example

sample image

threshold values

result

(values between 0 and 9)

01/29/16

Duong Anh Duc - Digital Image Pro

21

Generation of Threshold Matrices

recursive method: 4 copies of smaller matrices

01/29/16

Duong Anh Duc - Digital Image Pro

22

Generation of Threshold Matrices

Direct method: use of magic squares
example

magic squares produce

fewer diagonal stripes
01/29/16

Duong Anh Duc - Digital Image Pro

23

Dithering between Grey Levels

threshold values have to lie between a and b:

calculation is done separately for every pixel

(not once for a dithering matrix)
01/29/16

Duong Anh Duc - Digital Image Pro

24

Grey Level Dithering Example

01/29/16

Duong Anh Duc - Digital Image Pro

25

Dot Diffusion Dithering

01/29/16

Duong Anh Duc - Digital Image Pro

26

Stochastic Dithering?
Use of random numbers as threshold
values
expectation

value of total error = 0

no regular artificial patterns possible

Unfortunately: very bad results!

(due to bad distribution of random
numbers)
01/29/16

Duong Anh Duc - Digital Image Pro

27

Forced Random Matrix Dithering

Improved "random" matrices very good results
Method: insert threshold values one by one into
matrix, always use the position farthest away from all
previous points
Repulsive force field:
precalculate large threshold matrices: 300x300
very good results!
01/29/16

Duong Anh Duc - Digital Image Pro

28

Error distribution algorithms

Floyd-Steinberg (1975)
If an image has a pixel with a normalised value of
0.5, ie half intensity, we cannot accurately
represent it with a black or white dot.
However, we can remember the error and feed it
into the approximation calculation for the
surrounding pixels.
The error value gets distributed locally and the eye
reintegrates the values, recreating the grey scale.
01/29/16

Duong Anh Duc - Digital Image Pro

29

Floyd-Steinberg
Distribution Weighting
Current
scan line of
image
Next scan
line of
image

01/29/16

Current 3/8
Pixel
error
3/8
error

1/4
error

Duong Anh Duc - Digital Image Pro

30

Dithering
Some drawbacks
A dithered image is an image with less information in
it than the original.
Resolution and apparent colour content are a tradeoff, particularly with thermal wax transfer printers etc.
Accurate conversion between original images and
dithered images is generally one-way.
Some dithering methods cause ugly banding on some
images. Careful choice of dithering methods can
minimise this problem.
01/29/16

Duong Anh Duc - Digital Image Pro

31

Diffusion Direction Variations

to gain better results, the error is distributed
toseveral neighbors (with weights)

01/29/16

Duong Anh Duc - Digital Image Pro

32

Error Diffusion Dithering Example

sample image

threshold values

result

(values between 0 and 9)

corresponds to rounding
01/29/16

Duong Anh Duc - Digital Image Pro

33

Serpentine Method
Artificial stripes can be reduced drastically
byprocessing the scanlines in serpentine order

no additional memory necessary

01/29/16

Duong Anh Duc - Digital Image Pro

34

Colour Systems
Colour in the environment
Diffuse reflection of white light gives an object
its colour.
Perception of colour is, therefore, dependent
upon lighting.
Specular reflection has the colour content of
the light source - what is the colour of a mirror?
Colour is an everyday experience.
01/29/16

Duong Anh Duc - Digital Image Pro

35

Colour Systems
Colour in the environment
Colour can be measured in terms of the
frequency or wavelength of electromagnetic
radiation (light).
Some light sources have a narrow band of
frequencies, eg lasers, but this is rare.
Incandescent lighting has a broad range of
frequencies.
Sodium lamps have two bright frequencies.
01/29/16

Duong Anh Duc - Digital Image Pro

36

Colour Systems
Measuring Colour
Violet

Blue Cyan Green

400

480 500 520

Yellow

580 600

Orange

Red

650

700

720

Light Wavelength (nanometres)

Wavelength and intensity are measurable

quantities - intensity expresses the energy per
unit area carried by the radiation.
This is not an intuitive way of specifying colours!
01/29/16

Duong Anh Duc - Digital Image Pro

37

Colour Systems
Colour Matching
The eye cannot discern between a colour made
of a single wavelength and a visually identical
colour made of a mixture of wavelengths.
This allows monitors (RGB) and magazines
(CMYK) to show the same pictures.
The eye is very sensitive to colour and can
distinguish between approximately 300 000
different shades of colour.
01/29/16

Duong Anh Duc - Digital Image Pro

38

Colour Systems
Colour Matching
For practical purposes, the physical description of colour is abandoned in favour of a more
natural way of describing what we see.
Any colour shade can be matched by mixing
three monochromatic primary colours, by
definition.
Colour matching is an important problem for
commercial users of print and video.
01/29/16

Duong Anh Duc - Digital Image Pro

39

Colour Systems
Primary Colours
In the real world we do not have pure, singlewavelength colour sources to add - this means
that some colour shades are impossible to
match.
A way of specifying colours in a sensible way
was developed by the CIE (Comission
Internationale de LEclairage) in 1931.
The CIE chromaticity diagram is widely used.
01/29/16

Duong Anh Duc - Digital Image Pro

40

Colour Systems
The CIE Chromaticity Diagram

Green
Yellow
Cyan
White

Blue

01/29/16

Red

The CIE diagram represents

all hue and saturation values,
with normalised intensity.
The outer curve represents
all the visible 100% saturated
or pure colours.

Magenta

Duong Anh Duc - Digital Image Pro

41

Colour Systems
The RGB colour cube
A system with three
independent variables
can be represented by a
three-dimensional
position.
The RGB colour cube
represents all of the
colours that an RGB
monitor can create, in a
non-normalized form.
01/29/16

Yellow

Green

Cyan
White
(Greys)
Black

Blue

Duong Anh Duc - Digital Image Pro

Red

Magenta

42

Colour Systems
The RGB colour cube
A system with three
independent variables
can be represented by a Cyan
three-dimensional
position.
The RGB colour cube
represents all of the
Blue
colours that an RGB
monitor can create, in a
non-normalized form.
01/29/16

Green

Duong Anh Duc - Digital Image Pro

Yellow
White

Red

Magenta

43

Colour Systems
The HSV model
Hue, Saturation, Value is a
more intuitive model.
Value is brightness,
constant value hexagons
lie parallel to the top
surface.
Grey shades run up the
vertical axis, black at the
bottom and white at the
top.
01/29/16

Green 120 Yellow 60

Cyan 180

V=1

Magenta 300

Blue 240

Duong Anh Duc - Digital Image Pro

Red 0

V=0

44

Colour Systems
The HLS model
The Hue, Lightness, Saturation
L=1
model was developed by
Tektronix.
HLS is similar to HSV but with a Green 120
double cone.
Yellow 180
This and other models are
Red 240
combinations of the CIE, RGB
and HSV models.
Translations are always possible.
01/29/16

Duong Anh Duc - Digital Image Pro

Cyan 60
Blue 0
Magenta 300

L=0

45

References
http://www.efg2.com/Lab/Library/
ImageProcessing /DHALF.TXT - dither.txt
everything you ever wanted to know about
dithering!
Computer Graphics, (C version) by D. Hearn and
P. Baker:
Section

4 of Chapter 15, Halftone Patterns and

Dithering Techniques
Chapter 15, Colour Models and Colour Applications
01/29/16

Duong Anh Duc - Digital Image Pro

46

Digital Image Processing

Some Special Techniques
Thinning (Lc xng)

01/29/16

Duong Anh Duc - Digital Image Processing

47

Thinning

Cc pixel trn mt nh c th chia lm 2 loi:

Pixel nn
Pixel thuc mt i tng
y ta ch quan tm n loi sau.

Cc pixel thuc mt i tng li c th chia

lm 2 loi:

im bin
im bn trong

Thinning l qu trnh bin i trn nh ch

cn cc im bin v nn.
01/29/16

Duong Anh Duc - Digital Image Pro

48

Thinning

Thinning l qu trnh loi b cc pixel ph

(d tha) lm i tng tr nn n g in
hn, ch gm cc thnh phn mnh, khng
c din tch.
Thinning rt ging vi php co: xa lin tip
cc pixel d tha cho n khi ch cn khung
xng i tng.

01/29/16

Duong Anh Duc - Digital Image Pro

49

Thinning
Thinning phi tha cc tnh cht c bn sau:
i

tng kt qu phi mnh, c rng 1 pixel

Cc pixel to nn khung xng phi nh v gn
tm ca mt ct i tng.
m bo tnh lin thng ging nh i tng ban
u.

01/29/16

Duong Anh Duc - Digital Image Pro

50

Thut ton Zhang Suen

T tng c bn:

Vic gii quyt c xa hay khng xa 1 pixel s

ch ph thuc vo 8 pixel ln cn vi n.

Bn quy tc quyt nh xa hay khng

xa 1 pixel:

01/29/16

Duong Anh Duc - Digital Image Pro

51

Quy tc 1

Pixel p c th c xa nu 1 < N8(p) < 7 vi

N8(p) l s ln cn 8 ca p.
iu kin N8(p) > 1 m bo im u mt ca i
tng khng b xa, khng b bo mn.
iu kin N8(p)<7 m bo i tng khng b c
l (trong trng hp N8(p)=8) hoc bo mn qu
mc (trong trng hp N8(p)=7).

01/29/16

Duong Anh Duc - Digital Image Pro

52

Quy tc 2:

Pixel p c xa nu ch s m (counting
index hay crossing index - CI) ca n bng 1.

nh ngha: Ch s m l s ng r t pixel
ang xt.

01/29/16

Duong Anh Duc - Digital Image Pro

53

Cch tnh crossing index - CI

V d:

1
p

01/29/16

CI=1

1
p

CI=0

CI=2

CI=2

CI=3

1
1
p

Duong Anh Duc - Digital Image Pro

1
CI=4

54

Quy tc 3:

Trong pha th nht, nh s c qut t

trn xung di v t tri sang phi. Mt
pixel ch c xa nu tha c 2 iu kin :

C t nht 1 trong cc ln cn 1, 3, 5 l pixel nn.

C t nht 1 trong cc ln cn 3, 5, 7 l pixel nn.
1
7

5
01/29/16

Duong Anh Duc - Digital Image Pro

55

Quy tc 4:

Trong pha th nht, nh s c qut t

di ln trn v t phi sang tri. Mt pixel
ch c xa nu tha c 2 iu kin :

C t nht 1 trong cc ln cn 1, 3, 7 l pixel nn.

C t nht 1 trong cc ln cn 1, 5, 7 l pixel nn.
1
7

5
01/29/16

Duong Anh Duc - Digital Image Pro

56