Before we all mute the word ‘dithering’, I thought I’d explain a bit about why we needed to dither digital images in the first place. Although it is now an aesthetic matter, we had to trick our eyes into seeing more colors than they actually were.
So in the early days of computing, memory was small and we couldn’t store a lot of color details. To overcome this we used lookup tables or actually limited palettes with low bit depth colors to reduce the number of colors in the image, also known as quantization.
The problem with quantization is that it creates difficult steps where successive gradients must occur – we have no colors between them. This is where the deviation comes in. We can approximate this gradient by adding some noise with two neighboring colors.
Dithering is effective because of something called spatial averaging – basically your eye averages a small area of color. Dithering tricks our eyes into estimating a smooth phase between two edges of color, like a low pass filter.
So how do we segment an image? Well, there are lots of approaches so let’s start with the simple one, sequential dithering. For simplicity let’s use a monochrome image. Our goal is to recreate the gray tones in the image using only black and white.
To start, we create a 2×2 Bayer matrix, where the values are the order in which we will process the pixels. We then scale those values to the range we need, 0-255, which gives us a threshold map that we can use to compare pixels.
Next, we divide the image into 2×2 pixel groups and compare each pixel value to the values in our map in that weird criss-cross order. If it is greater than the value of our map, we make it white and if it is less, we make it black.
Because we have a 2×2 matrix, there are actually only 5 possible outcomes for any given quadrant, meaning there are only 3 shades of gray between white and black. Increasing the size of the threshold map increases the effective shades of gray and hence the detail level.
The problem with sequential dithering is that our threshold map produces patterns that are quite noticeable. A better approach is something called error propagation dithering, specifically the Floyd-Steinberg algorithm.
Instead of using a map, we set a single threshold value like 128. We evaluate each pixel against this threshold as before. This time, we take the difference between the original value and our new value and apply that difference, known as the error, to the surrounding pixels.
The idea is that if one pixel is brighter than the original, neighboring pixels are made darker to compensate. We propagate the error according to this matrix of weights by adding them to neighboring pixels. The error is signed, meaning it can be positive or negative.
There are actually lots of other dithering algorithms but these two are the most common. We don’t really have to worry about that much anymore because we have high bit-depth color so now it’s largely just a retro aesthetic.
Anyway, it’s dilemmatic. I put this together because I’m writing about dithering as well as other effects like Gaussian blurs, edge detection, noise, etc. for makesoftware.com. If you’re interested in this kind of thing, sign up to the mailing list.