Lab Assignment

Implement the following halftoning algorithms.

Dithering Matrix

Halftoning an 8-bit grayscale image means quantizing it to a 1-bit binary image (that is, 8 bits per pixel is reduced to 1 bit per pixel). The dithering matrix method is a halftoning technique where the grayscale values in each local neighborhood (i.e., subblocks) of an image are replaced by a set of binary-valued intensities.

The resulting binary image on a coarse scale are supposed to retain the appearance of the original grayscale image. The darker the original subblock, the more 0s are placed in the corresponding binary subblock, the lighter the original subblock, the more 1s.

Image A1 (the lonely pixel)

Your assignment is to use a 1x1 subblock (1 pixel), and replace each 8-bit value I8 with its 1-bit quantized value as follows:

Image A2 (sixteen is a crowd)

<[p> To obtain a better visual approximation we can use larger subblocks. Here is an example showing how 3x3 subblocks are processed. Within each 3x3 subblock we compare each pixel to a fixed threshold taken from a table (matrix) of values. For example, let


20 50 80
30 35 90
15 85 95

be a 3x3 block taken from the 8-bit input image; call this subblock S. S is different for each subblock, of course. Let

70 60 30
90 45 10
20 80 30

be our 3x3 table of thresholds, called T. T is fixed during the entire dithering process.

Applying T to S, that is, running the mini-algorithm:

if S(i,j) < T(i,j) then output = 0;
If S(i,j) >= T(i,j) then output = 1

we get

0 0 1
0 0 1
0 1 1

where 0 represents black and 1 represents white (replace 1 with 255 (white) in your program so you can actually see the result). This procedure would be repeated for each 3x3 subblock in the input image using non-overlapping blocks.

Your assignment is to use 4x4 subblocks. Use the dithering matrix D on p. 86 of the lecture notes. This dithering matrix is given by

  8 136  40 168
200  72 232 104
 56 184  24 152
248 120 216  88

Error Diffusion

The disadvantage in using a dithering matrix is that it throws away image energy. For example, if a large area of the image is just below a particular threshold value, the quantization process discards a lot of energy that should have been kept. Error diffusion is a halftoning method that attempts to retain image energy by taking into account the amount of energy lost or gained during the quantization of a local neighborhood of pixels.

Image B: Floyd-Steinberg (i.e. holding a grudge)

One way to do error diffusion is shown in the block diagram of Figure 3.17 on page 87 of the lecture notes. Here we look at Floyd-Steinberg error diffusion, which is the process shown in the block diagram with the lowpass filter H(omega) defined as:


               1/16 5/16 3/16      
   7/16  X 

where X is the current pixel location. Note that X does not have a corresponding filter coefficient. This is a causal non-separable filter that is applied in raster-scan order. It is used to compute a weighted average of the quantization error accumulated in the "recent past". The quantization error for each pixel is given by

Error = Original value - Quantized value

The weighted average is then used to adjust the current input pixel value before it is quantized.

Following are the steps for the Floyd-Steinberg diffusion algorithm:

Step 1: Generate an error image with the size same as input image and initialize all the entries to 0.

Step 2: From top to bottom and left to right, you will accumlate each error pixel at current pixel location X with the weighted sum. In other words, you calculate recent error at X by summing all the terms around it in the error image with the weights in filter H.

Step 3: The output image value O at location X can be achieved by following equation, O=I-E, where I refers to the value in input image at location X, and E represents the pixel value in error image at location X. Then you quantize the value O according to the 1*1 subblock quantization scheme. The result QO is your solution image. 

Step 4: Update the error image at location X with the following equation E=QO-O. Where QO is the output image pixel value after quantization and O is the one without quantization.

Keep doing it until you finish scanning the whole image.


MSE calculation

Please calculate the MSE for the three above cases.

Compare Dithering with Error Diffusion

Write a Matlab script to compare the low frequency energy of the two error images.

Implementation details will be presented during the lab session.