This post is about ordered dithering in Octave. What’s is dithering? You can find a very good explanation here in wikipedia. But briefly, the idea of dithering is to create the illusion of color depth in images with (in our case) only two color quantization. This technique is used in printers, scanners, etc. We print small dots black and leave white spaces and our eyes will do the rest of the job. For those who doesn’t know, our eyes has a low pass filter as frequency response.

The image on the left was generated by using the threshold algorithm. This is the direct way we normally would do, but as we can see the results are not that good. The main problem is that we can’t have a gray scale effect and we lose most of the details of the image. We can barely see the apple in the left corner. The algorithm used is called Ordered dithering and we used a Bayer matrix. Read more about it also here in wikipedia.

The second method we will show is Error Diffusion. The algorithm used is Floyd–Steinberg dithering. The idea is quite simple. We scan the image from top-left to right-bottom. Imagine that we set a gray pixel to white (once we have only two values). We add an error in the new image. We can spread this error to the four pixels which are connected to this pixel (right, bottom-left, bottom, bottom-right). In this way, we try to accumulate the error in order to be able to maintain the average of the brightness of the image. Floyd-Steinberg spreads the error in this way:

right: 7/16

bottom-left: 3/16

bottom: 5/16

bottom-right: 1/16

They chose this distribution because it gave them the most even distribution of textures in the output image with the fewest artifacts. We can notice that this algorithm brings better results.

Below, I put a gray tone scale image with the three methods to compare them closer.

We can notice that in the threshold method we would have to blocks black-white. The small white line was a noise in the original file (which I stole from internet LOL). In ordered dithering we see that we can’t represent high frequency (changes of pixel level by space). Using Floyd-Steinberg give us the best of the three. You can find several others methods, these three are the basic of digital image processing.

Here the source code for both algorithm.

function [image] = bayer(N, img) bayer4 = [0 8 2 10; 12 4 14 6; 3 11 1 9; 15 7 13 5]; bayer8 = [1 49 13 61 4 52 16 64; 33 17 45 29 36 20 48 32; 9 57 5 53 12 60 8 56; 41 25 37 21 44 28 40 24; 3 51 15 63 2 50 14 62; 35 19 47 31 34 18 46 30; 11 59 7 55 10 58 6 54; 43 27 39 23 42 26 38 22]; if N == 4 bayer_matrix = bayer8; else bayer_matrix = bayer8; end img_size = size(img); x_max = img_size(1); y_max = img_size(2); for x = 1:x_max, for y = 1:y_max, if (img(x,y) + bayer_matrix(mod(x,N) + 1, mod(y,N) + 1)) > 128 image_bayer(x,y) = 255; else image_bayer(x,y) = 0; end end end image = double(image_bayer); end

function [image] = floyd(img) img_size = size(img); x_max = img_size(1); y_max = img_size(2); img = double(img); for x = 1:x_max, for y = 1:y_max, % Read pixel value oldpixel = img(x,y); % check if more than 50% if(oldpixel > 128) newpixel = 255; else newpixel = 0; end % set pixel value into new image image_floyd(x,y) = newpixel; %calculate error quant_error = double(oldpixel - newpixel); % check boundaries and accumulate error if(x + 1 <= x_max) img(x+1,y) = double((img(x+1,y) + 7/16 * quant_error)); end if ((x-1 > 0) && (y+1 < y_max)) img(x-1,y+1) = double((img(x-1,y+1) + 3/16 * quant_error)); end if(y + 1 <= y_max) img(x,y+1) = double((img(x,y+1) + 5/16 * quant_error)); end if((x + 1 <= x_max) && (y + 1 <= y_max)) img(x+1,y+1) = double((img(x+1,y+1) + 1/16 * quant_error)); end end end image = image_floyd; end

Bye

Marcelo

how to get value bayer4, bayer8 ?

Hello,

Actually you could use any matrix. These were defined by Bayer himself.