blobcode - Dithering (and math)!

I love! (love)

I love it so much

dithering.

You might ask - what is dithering? It’s intentional noise applied to an image to prevent quantized error in some set of data

Dither - Wikipedia

. This data - at least for our purposes, is an image.

It can also either be used to represent gradients and increase the number of representative colors in an image, or to increase the ability of data to be compressed, or just to look cool!

Dithering is fundamentally about error diffusion - where the individual quantized pixel’s value is spread to a certain area of the unprocessed image’s pixels.

Let’s start by picking an image to play with - I like this one, but feel free to pick your own!

Floyd-Steinberg Dithering

The first, and arguably most famous example of an image dithering algorithm which we will cover is the Floyd-Steinberg algorithm, which in essence visits each pixel and then applies a kernel transformation to it of the form

[\begin{matrix} * & \frac{7}{16} \\ \frac{3}{16} & \frac{5}{16} & \frac{1}{16} \end{matrix}]

But how is a kernel transformation applied? For those unfamiliar, we first convert the image to grayscale

averaging sRGB color

, then take the value of the current pixel (indicated by the *), and then because of it being an error diffusion algorithm, by definition we add the value of the current pixel to the surrounding pixels based on their position in the kernel.

The algorithm (in pseudocode) goes something like the following:

for y = 0 to height-1:
       for x = 0 to width-1:
           old_pixel = image[y][x]
           new_pixel = quantize(old_pixel)
           image[y][x] = new_pixel
           error = old_pixel - new_pixel
           
           if x+1 < width:
               image[y][x+1] += error * 7/16
           if y+1 < height:
               if x-1 >= 0:
                   image[y+1][x-1] += error * 3/16
               image[y+1][x] += error * 5/16
               if x+1 < width:
                   image[y+1][x+1] += error * 1/16

This results in

This gives us a nice base result to work off of (and to compare to).

Atkinson Dithering

A popular variant of the approach used by the Floyd-Steinberg algorithm is Atkinson dithering, developed for the Macintosh. It uses the same error-diffusion approach, with the kernel

[\begin{matrix} * & \frac{1}{8} & \frac{1}{8} \\ . . . & \frac{1}{8} & \frac{1}{8} & \frac{1}{8} & . . . \\ . . . & \frac{1}{8} & . . . \end{matrix}]

This was useful because the

\frac{1}{8}

is simple to compute on limited hardware as opposed to the awkward fractions of steinberg dithering, as it can be performed by a bitshift of >> 3.

There are a number of other error diffusion methodologies to use, each of which have strengths and weaknesses and a unique look - you can also try your own kernel below!

Note that we see some interesting results for certain large values in the matrix, as the pixels become saturated and this is subsequently propagated - mildly interesting geometries, especially with shadows!

All in all, I hope you enjoyed this short exploration of dithering methods, with hopefully more to come at some indeterminate point in the future!