Floyd-Steinberg dithering in JavaScript

There are many "smart" algorithms in 2D graphics and Floyd-Steinberg error diffusion is one of them. Attached demo demonstrates a dithering on webcam output (or Bucks Bunny video, when webcam is not available).

What is the problem

The problem is, that we have an image (table of pixels) in format, which uses lots of colors (hundreds, thousands, millions ...) and we want to display it with less colors, and we already have both palettes. There might be many reasons for doing that.

1. Compression: instead of 24 bits for pixel we can use only 16, 8, 2 or even 1 bit per pixel. E.g. GIF format uses 8 bits per pixel.
2. Displaying it on displays, which don't have many colors (e-book readers, LED boards, ...)
3. Printing an image on some special printers or plotters.
4. Embroiding an image on cloth using cross-stich.

What is the solution

The obvious solution is to round the color values from big palette to the "closest" values in the small palette. Let's say we have a grayscale image with 100 possible pixel values (1, 2, ... 100) and we want to "express" it using only 2 values (1 or 100). When we have an area in our image, where all the pixels have value 40 (let's call it 40v), we round it and we get 0v. When it is 70v, we round it and we get 100v.

Dithering is a little different attitude. When we draw that 40v area, we want to draw 0v pixels and sometimes 100v pixels between them, so the whole area looks like 40v.

One way of doing dithering is error distribution. Now we also round the pixel values, but when we are making a pixel darker (40v to 0v), we also say the neighbouring pixels to be a little lighter. An "error" is a difference between real (input) color and rounded (output) color and we somehow "split" that difference to neighbours. Neighbours can split their errors to their neighbours, sometimes the errors accumulate and a pixel becomes 100v.

Floyd-Steinberg algorithm

Floyd-Steinberg algorithm says, that we should add 7/16 of error to the right neighbour, 3/16 to the bottom left, 5/16 to bottom and 1/16 to bottom right neithbour. You can read more about it in Wikipedia article about Floyd-Steinberg.

JavaScript implementation

// byte shift by 4 (x = x>>4;) corresponds to integer division by 16

/*
   function converts values from grayscale (0-255) to black and white (0 or 255)
*/

function floydSteinberg(sb, w, h)   // source buffer, width, height
{
   for(var i=0; i<h; i++)
      for(var j=0; j<w; j++)
      {
         var ci = i*w+j;               // current buffer index
         var cc = sb[ci];              // current color
         var rc = (cc<128?0:255);      // real (rounded) color
         var err = cc-rc;              // error amount
         sb[ci] = rc;                  // saving real color
         if(j+1<w) sb[ci  +1] += (err*7)>>4;  // if right neighbour exists
         if(i+1==h) continue;   // if we are in the last line
         if(j  >0) sb[ci+w-1] += (err*3)>>4;  // bottom left neighbour
                   sb[ci+w  ] += (err*5)>>4;  // bottom neighbour
         if(j+1<w) sb[ci+w+1] += (err*1)>>4;  // bottom right neighbour
      }
}