Revisiting Yliluoma’s ordered dither algorithm

30fps.net — Computer Graphics & Programming with Pekka Väänänen

Yliluoma’s 2nd dithering algorithm

EMA-Constant

Knoll (10% strength)

Summary: This article discusses Joel Yliluoma’s 2011 ordered dither algorithm (left), explains its internals in greater detail than other treatments, presents new simplified variants (middle), and compares the results to a state-of-the-art algorithm (right).<br>Source code is included at the end.

A 1-bit introduction

Let’s lay some foundations first.<br>I assume you know what ordered dithering looks like (if not, see above).<br>In black and white it’s easy to code.<br>First you acquire a threshold matrix from somewhere.<br>For example, a 4x4 Bayer matrix like this:

\begin{bmatrix}<br>0 & 8 & 2 & 10 \\<br>12 & 4 & 14 & 6 \\<br>3 & 11 & 1 & 9 \\<br>15 & 7 & 13 & 5<br>\end{bmatrix}

To apply the matrix to a grayscale image, you go over each pixel, find out which matrix element it corresponds to (conceptually, the matrix is tiled over the image), and read a threshold from the matrix.<br>If the input pixel’s gray value is higher than the threshold, you output a white pixel.<br>The code could look like this:

bayer_4x4 = np.array([<br>[ 0, 8, 2, 10],<br>[12, 4, 14, 6],<br>[ 3, 11, 1, 9],<br>[15, 7, 13, 5]])

def dither_bayer4x4_1bit(img: np.ndarray):<br>img_float = img / 255 # process in [0,1] range<br>H, W, _ = img.shape

# The floating point output image<br>out = np.zeros((H, W, 1), dtype=float)

for y in range(H):<br>for x in range(W):<br>color = img_float[y, x]<br>threshold = (bayer_4x4[y%4,x%4] + 0.5) / 16.0<br>if color > threshold:<br>out[y, x] = 1<br>else:<br>out[y, x] = 0

return out

And below you see what it produces.

Grayscale image

Dithered to 1-bit with a 4x4 threshold matrix

For 1-bit output, an ordered matrix like this creates pretty grainy results.<br>If I had to choose, something like Atkinson error diffusion dithering would work better in black and white.

But this was a mere warmup exercise.<br>The real question is how to do the same for color images.<br>To create something like this:

16-color indexed image with ordered dithering

Today we are discussing how exactly it’s done.

Ordered dithering in color is both harder and easier than you think

Doing ordered dithering well is surprisingly tricky.<br>Getting started is easy though.<br>We can reinterpret the threshold matrix as structured noise, repeat it over the whole image and add it to the original colors, and then find the closest color for each pixel.<br>The 1-bit example code turns into something like this:

# Assume "offset" is the average distance between two palette colors.

for y in range(H):<br>for x in range(W):<br># input color<br>color = img_float[y, x]

# (0, 1) range threshold<br>threshold = (bayer_4x4[y%4,x%4] + 0.5) / 16.0

# bias threshold to (-0.5, 0.5) range, then add<br>moved = color + offset * (threshold - 0.5)

# find closest palette color to 'moved'<br>idx = find_index_of_closest(moved)<br>inds[y, x] = idx

This actually works better than it should, at least with the palettes used for my test images.<br>The only question is the noise magnitude, the value of offset above.<br>There’s no right answer, but in my experiments this magic formula worked OK:

offset = dither_strength * 0.5 * median(pairwise_color_distances)

Here’s how this “greyscale offset” method looks:

Original

16-color image dithered with the above code

Not bad!<br>The black dots in the sky are a bit rough but those could be cleaned up by reducing dither strength.<br>For arbitrary palettes, this approach tends to produce desaturated results, unfortunately.<br>But when a palette is designed for the image like here, it works OK.

N-candidate methods

One family of more advanced solutions to the color selection problem involves collecting a set of N candidate palette colors for each pixel, assigning a probability to each, and then picking one either at random or via a threshold matrix.<br>These are called N-candidate methods.<br>I won’t go into detail here, but will point you to a 2023 blog post titled Ordered Dithering with Arbitrary or Irregular Colour Palettes that explains everything you need to know.<br>Please read at least its “The Probability Matrix” section.

A key property these algorithms try to satisfy is local mean reproduction:<br>when the dithered result is seen from afar (or blurred), it should look like the original.<br>This translates to minimizing the distance between the input pixel color \mathbf{p} and the weighted sum of all chosen candidates w_1 \mathbf{r}_1 + ... + w_N \mathbf{r}_N.<br>For more details, I suggest reading the blog post linked above.

Knoll’s algorithm

A 16-color image dithered with Knoll’s algorithm.

One algorithm that minimizes the above distance astonishingly well is Thomas Knoll’s dither algorithm, famously used in Adobe Photoshop (he’s its inventor after all).<br>Knoll’s algorithm first sets a goal color \mathbf{x}_1 to the palette color closest to the input color \mathbf{p}.<br>This palette color \mathbf{r}_1 is the first candidate color.<br>Then the algorithm measures how much...