Marcelo Jo

Hello there!

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.

Threshold Ordered dithering – Bayer Error diffusion – Floyd-Steinberg

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

Marcelo Jo

Marcelo Jo is an electronics engineer with 10+ years of experience in embedded system, postgraduate in computer networks and masters student in computer vision at Université Laval in Canada. He shares his knowledge in this blog when he is not enjoying his wonderful family – wife and 3 kids. Live couldn’t be better.