blobcode - Dithering (and math)!

Note that this article is WIP

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? 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.

This gives us a nice base result to work off of.

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.

Ordered Dithering

Another approach to dithering is called ordered dithering, which instead of relying on error diffusion uses simple threshold matrices.