Image and Video processing Laboratory 2 Dithering Solution

    • Fixed threshold method

Implement the dithering method based on xed thresholding. All pixels with intensity less or equal to half the dynamic range are assigned to black and the remaining to white. Apply this method to lena-y.png and wool.png.


    • Random threshold method

Repeat the exercise by adding a discrete uniform noise to the image (hint: use the function unidrnd). Choose the amplitude of the noise so as to achieve a good compromise between the rendered gray levels and the loss of quality due to the added noise.


    • Ordered threshold method

The ordered threshold method is given by a matrix of threshold values used to pave the image plane. An example is given in the following clustered dot matrix

34
29
17
21
30
35
3

S =
228
14
9
16
20
31

:

612  3
0
1
10  18
7


6






7


13
8
4
5

15
19
7


627
7
2
6

23
24



6






7


6






7


4






5


633
26
11
22
25
32
7

By convention the smallest threshold is always zero. The gray levels that a threshold matrix can represent, in a normalized scale [0; 1], are i=(N 1), i = 0; : : : ; N 1. In the previous example N = 37 gray levels.

The image is rst quantized to N gray levels where N is the number of gray levels represented by the matrix. Then, the quantized image is compared to the thresholds of the matrix. In other terms, the dithering is obtained by the relation

x^(k; l) > s(k; l);
(1)

where x^(k; l) is the quantized image and s(k; l) is the matrix obtained by paving the image plane with the matrix of thresholds. Note that x^(k; l) takes the integer values between 0 and N 1.

Find the adequate quantization function Q(x) to convert x(k; l) to x^(k; l). Find an equivalent expression for Q(x) that does not require operators such as floor, ceil or round (in other words, only using addition, substraction, multiplication or division). With this result, write a Matlab function that performs the thresholding. Set the image and the matrix of threshold values as inputs to the function.


2
    • Ordered matrix with centered points



2
30
13
9
5
12
24
3


6
34
25
21
17
29
33
7
C6
=

22102
3
4
16



6
18
6
1
0
8
20
7


6






7












6
26
14
7
11
15
28
7


6






7


4






5


6
35
31
19
23
27
32
7
is a matrix with a central white point over a black background (In other words, white points whose size depends on the gray level are drawn).



2
24
11
7
9

26
28
3


6
30
22
16
21
33
35
7
E6
=

15  3
1
4
12  18



6







7


6
13
5
0
2

14
19
7



27
8
6
10
25
29



6







7


6







7


4







5


6
32
20
17
23
31
34
7
is a matrix called balanced centered point.

Apply these two matrices to both images. See the shape of the white and black points in the dithered images. What is the main di erence between these two methods?


    • Diagonal ordered matrix with balanced centered points
















































O8;1   O8;2
O8 =  O8;2   O8;1  ;

where
    • 3


13
9
5
12
7


6
1
0
8

O8;1
614
7
11
15


=
10
2
3
4
7

6






4




5
and
    • 3
18  22  26  19
O8;2
=
6
25
30
31
23
7
;



21
29
28
27




4




5



6
17
24
20
16
7

is a matrix called diagonal ordered matrix with balanced centered point. Note that the element paving the image plane is rhombus-shaped:

18

    • 25  30


3
4
21
29
28

7
11
15
17
24
20
16
22
26
19
13
9
5
12

31
23
6
1
0



27
10
2





14




Apply O8 to both images. Compare the results with those obtained in the previous exercise. What do you notice regarding eye sensitivity to diagonal and horizontal/vertical orientations?
3
    • Ordered matrix with dispersed dots

Bayer proposed a recursive algorithm to create a threshold matrix with a sparse pattern. With a threshold matrix Dn of dimension n n one obtains the matrix 2n 2n

 
D2n =
4Dn
4Dn + 2Un
;

4Dn + 3Un
4Dn + Un


where Un is the n n matrix with all the elements equal to 1. The matrices obtained with this algorithm minimize the occurrence of low frequencies, more visible to the eye. Matrices with basis

 
0    2
D2=31
or
    • 3
8  4  5
3
0
1
5
D3=47
2
6

are usually used.

Use the matrix with sparse thresholds D6 with both images.


    • Error di usion method

The principle of this method is summarized in Figure 1. Each pixel in the image is thresholded. Then, the error introduced by the thresholding is calculated (err(i; j) = in(i; j) T (in(i; j)). Using the di usion lter given in Figure 1, the dithering error is distributed on the neighboring pixels using the indicated proportions. The pixels are processed in a line-by-line basis. Apply the error di usion method by using


In(k,l)
+
+




+








Floyd & Steinberg


*
7



3
5
1





Threshold T

Ib(k,l)


-

+



+





e(k,l)
Diffusion filter











Stucki

*
8
4






2
4
8
4
2







1
2
4
2
1







Figure 1: Block diagram of the error di usion method.


a normalized Floyd-Steinberg    lter, and then Stucki.


    • Discussion

Compare the various methods in terms of :

Visual quality.

Mean Square Error between the dithered image and the original. Complexity (number of operations).


4