Dithering

Back

Aug 2024

A Deep Dive into Dithering

Intro

Chances are you’ve already seen dithering applied to real-world GUIs, video games, or images, but maybe you just never noticed or knew how it worked. Well, that was me about two weeks ago. After a very long rabbit hole on information, here we are. Now, let’s explore all the great and interesting things about dithering, its history, and how it’s been applied in various settings.

Definition

By definition, dithering is a technique in digital graphics that uses patterns to create the illusion of greater color depth in situations with real or self-imposed color constraints.² Simply put, it is a technique that creates the illusion of more colors by blending existing ones. There are various forms of dithering, such as Floyd-Steinberg, Bayer, and blue noise, which we’ll also explore in further sections to understand their unique characteristics and applications.

Examples

As mentioned earlier, dithering techniques have been widely used in GUIs, video games, images, and more. Here are some real-world examples where dithering-like applications are evident.

We’ll look at old versions of Windows, macOS, and Pokémon sprites. These examples demonstrate how using a limited number of pixel colors can create the illusion of depth and detail, highlighting how dithering techniques have been applied in different digital contexts.

Windows 98 components are all pixelated and use only a limited number of intensity values, similar to dithering. With this alert window, a clever trick is used with the buttons: the outer shadow is inverted, swapping the darker and lighter shadows to create the illusion that the button is being pressed.

Hello, Press me!

Hello, world!

Window Component⁵

Similarly, icons from Windows 98 and many other old GUIs used only a few pixel intensities. It was a clever design trick to make the icons and components appear to have depth and dimension.

Windows 98 Icons³

We see similar dithering-like art styles in old versions of macOS as well. If you want to see something in real time, Software Applications Incorporated's¹³, website replicates this MacOS.

Screenshot from MacOS9⁹

Pokémon sprites are nostalgic to look back on. Different pixel intensities on each Pokemon were used to create the illusion of shadows and depth. Now, with most Pokémon games on the Nintendo Switch using 3D models, the renders don’t feel as special.

Pokemon Sprites

Mechanics

First, we will look at Quantization and Error Diffusion, two essential processes in dithering. Quantization reduces the number of unique colors in an image while preserving visual information, allowing an image to use a finite palette and still appear similar to the original. Error Diffusion then spreads the quantization error to neighboring pixels, reducing these artifacts. We will examine how the formulas for these processes work, as they form the foundation for the dithering effect.

Quantization

Quantization allows an image to use a finite number of colors and still look like it did before the process. Let's examine the quantization process and how it sets the stage for dithering.

\[ Q(x) = \left\lfloor \frac{x}{\Delta} \right\rfloor \times \Delta + \frac{\Delta}{2} \]

Q(x) is the quantized intensity value.
x is the original intensity value.
Δ is the size of each quantization interval.

Uniform Quantization Formula⁸

This equation might seem like a lot at first, but let’s break it down step by step to understand how it works.

The equation processes an image pixel by pixel and assigns a value based on the intensity of each pixel, which is measured on a scale from 0 to 255. This 0-255 scale represents the RGB color spectrum. Depending on your desired intensity level (L), the image will be converted into only three intensity levels. Instead of having, say, 1,500 different values, it will be reduced to just three. Let’s work through an example to see how this equation applies in practice.
‍

Let's say you have a pixel with an intensity value of 177, and you want to quantize this to 3 intensity levels. To do this, we'll use the quantization formula with \(x = 177\) and \(\Delta = 127.5\). The value of \(\Delta\) is calculated by dividing the full intensity range of 255 by \(L - 1\), where \(L\) is the number of desired levels. For 3 levels, \(L - 1 = 2\), so \(\Delta = \frac{255}{2} = 127.5\).

\[ \text{For } x = 177 \text{ and } \Delta = 127.5: \] \[ \frac{177}{127.5} \approx 1.388 \] \[ \left\lfloor 1.388 \right\rfloor = 1 \] \[ Q(177) = 1 \times 127.5 + \frac{127.5}{2} \] \[ 1 \times 127.5 = 127.5 \] \[ \frac{127.5}{2} = 63.75 \] \[ Q(177) = 127.5 + 63.75 = 191.25 \] \[ \text{Rounded Result: } Q(177) \approx 191 \] \[ \text{Thus, the quantized intensity value is } 191. \]

Quantization of Intensity Value 177

Error Diffusion

After the quantization process, there might be an error in our quantization value, which is then distributed to the neighboring pixels as the process continues. The neighboring pixels are then adjusted by distributing this error value to them. This adjustment affects their quantization cycle, reducing the likelihood that error patterns become recurrent.

Unlike quantization, which works pixel by pixel, error diffusion operates collectively while considering the neighboring pixels, working as an area operation. This process works in a kernel pattern and can be defined by the following equation.

\[ \text{Error Distribution:} \] \[ \frac{1}{16} \begin{bmatrix} - & \# & 7 \\ 3 & 5 & 1 \\ \end{bmatrix} \]

Where "-" denotes a pixel in the current row which has already been processed, and "#" denotes the pixel currently being processed.
The error is distributed to the neighboring pixels as follows:
Right pixel: \(\frac{7}{16}\) of the error
Bottom-left pixel: \(\frac{3}{16}\) of the error
Bottom pixel: \(\frac{5}{16}\) of the error
Bottom-right pixel: \(\frac{1}{16}\) of the error

Error Diffusion Kernel Pattern⁶

After looking at all of this, you might be asking, so what does all of this really do? Basically, applying error diffusion to our dithering process enhances the edges in images. This happens because the algorithm spreads the quantization error to neighboring pixels in a way that emphasizes the shapes and distinctions between different intensity levels. As a result, it creates higher contrast and improves the overall legibility of the image.

You might be wondering why we’re looking at math equations before reaching the Mathematical Foundations section. This is because error diffusion and quantization are fundamental to many dithering techniques. By establishing these principles now, we’ll have a solid foundation for understanding the math behind these processes when we get to that part, which is up next.

Mathematical Foundations

Now the fun part, we will be looking at a few different dithering principles, including Bayer (Ordered) Dithering, Floyd-Steinberg, and a few honorable mentions. As there are too many to cover in a short section, these are the ones that I find myself coming back to and using the most often.

Ordered Dithering

Also known as Bayer Dithering, this technique was one of the first to be developed by Bayer in 1973. It uses a pre-set threshold map that tiles across an image. Below is an example of a Bayer Filter, showing what the matrices look like visually. This particular example is an 8x8 matrix, reflecting the 8x8 map. We can apply these principles to an image and observe the differences between 2x2, 4x4, and 8x8 threshold maps.

8x8 Bayer Filter with RGB Scale¹²

Another important aspect of Bayer dithering is the use of different threshold maps, such as 2x2, 4x4, and 8x8. Let’s explore how expanding from a 2x2 threshold map to an 8x8 map affects the dither patterns. As we increase the size of the threshold map, the dither patterns become more detailed and incorporate a more complex set of threshold values. The larger the threshold map, the more detailed the dither will be.

\[ \mathbf{M_{2}} = \frac{1}{4} \times \begin{bmatrix} 0 & 2 \\ 3 & 1 \end{bmatrix} \]

Bayer Threshold Map Formula for 2x2¹²

Looking at our equation, \( \mathbf{M_{2}} \) is our matrix size, with "2" indicating that this is a 2x2 map. The scaling factor of \( \frac{1}{4} \) is determined by the equation \( \frac{1}{N^2} \), where \( N \) is the matrix dimension. For a 2x2 matrix, \( N = 2 \), so the scaling factor is \( \frac{1}{2^2} = \frac{1}{4} \). This scaling factor helps in determining the threshold values in the matrix.

The maximum threshold value is calculated by \( N^2 - 1 \). For a 2x2 matrix, \( N^2 - 1 = 2^2 - 1 = 3 \). Thus, the maximum threshold value in our matrix is 3. The order of the threshold values (0,3,2,1) is not mathematically related but follows Bayer's pattern, which defines the dither pattern for image quantization.

To expand a Bayer matrix from a 2x2 to a larger size, such as 4x4 or 8x8, we use a scaling formula based on the original 2x2 matrix.

\[ \mathbf{M}_{2n} = \frac{1}{(2n)^2} \times \begin{bmatrix} (2n)^2 \times \mathbf{M}_{n} & (2n)^2 \times \mathbf{M}_{n} + 2 \\ (2n)^2 \times \mathbf{M}_{n} + 3 & (2n)^2 \times \mathbf{M}_{n} + 1 \end{bmatrix} \]

\(\mathbf{M}_{2n}\) is the scaled Bayer matrix of size \(2n \times 2n\).
\(\mathbf{M}_{n}\) is the original Bayer matrix of size \(n \times n\).
\((2n)^2\) is the scaling factor, where \(n\) is the dimension of the original matrix.

Steps:

Calculate the scaling factor: \((2 \times 2)^2 = 16\).
Apply the formula: \[ \mathbf{M}_{4} = \frac{1}{16} \times \begin{bmatrix} 16 \times \mathbf{M}_{2} & 16 \times \mathbf{M}_{2} + 2 \\ 16 \times \mathbf{M}_{2} + 3 & 16 \times \mathbf{M}_{2} + 1 \end{bmatrix} \]
Substitute \(\mathbf{M}_{2} = \frac{1}{4} \times \begin{bmatrix} 0 & 2 \\ 3 & 1 \end{bmatrix}\): \[ \mathbf{M}_{4} = \frac{1}{16} \times \begin{bmatrix} 0 & 8 & 12 & 4 \\ 2 & 10 & 14 & 6 \\ 3 & 11 & 15 & 7 \\ 1 & 9 & 13 & 5 \end{bmatrix} \]
Final result: \[ \mathbf{M}_{4} = \frac{1}{16} \times \begin{bmatrix} 0 & 8 & 2 & 10 \\ 12 & 4 & 14 & 6 \\ 3 & 11 & 1 & 9 \\ 15 & 7 & 13 & 5 \end{bmatrix} \]

Now with our 4x4 matrix, our threshold values range from 0 to 15, rather than 0 to 3 with the 2x2 matrix. This allows us to have a wider range of values in the threshold, resulting in a more detailed image. This principle stays true when expanding our threshold. If we expand to the 8x8 matrix, our range would be 0 to 63, resulting in the most detailed dither of the three.

In the example below, I took a gradient from black to white and processed it through each dither. The 2x2 Bayer dither doesn't blend the gradient as well as the 4x4 and 8x8, since the values are limited to a much smaller range. As we continue to expand, the dither becomes more detailed, and the distinction between colors becomes more apparent and refined.

2x2

4x4

8x8

For a real-world example, I applied an 8x8 Bayer Dither to an image of a goldfish.

Goldfish Cracker with 8x8 Bayer Dither

Floyd-Steinberg

This is another form of dithering, but takes a different approach, in that it does not use a predetermined pattern like the Bayer dither form. Rather, this method achieves dithering using error diffusion, meaning it pushes (adds) the residual quantization error of a pixel onto its neighboring pixels, to be dealt with later.¹⁰

The pixel indicated with a star (*) is the pixel currently being scanned.

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

Floyd Steinberg Algorithim¹⁰

If we look at our algorithm, the steps we would take when calculating for (*) our current pixel are as follows. The process occurs left to right in an image, hence why the top left value in our algorithim is blank, as it is the previous scanned pixel.

First, we will look at our pixel, and change our pixel to the nearest color, which would be black or white. Then, find out how much the color of the pixel had to be changed to reach that nearest color and we should share this value with the neighboring pixels. So lets say our value was 8, we take this value, and multiply it around our present pixel.

Fractions are drawn from our initial algorithm:

\[ \text{Right pixel: } \frac{7}{16} \times 8 = \frac{56}{16} = 3.5 \]

\[ \text{Bottom-left pixel: } \frac{3}{16} \times 8 = \frac{24}{16} = 1.5 \]

\[ \text{Bottom pixel: } \frac{5}{16} \times 8 = \frac{40}{16} = 2.5 \]

\[ \text{Bottom-right pixel: } \frac{1}{16} \times 8 = \frac{8}{16} = 0.5 \]

This method yields a much clearer and more natural image compared to the Bayer technique, reducing the blockiness. An online tool for creating Floyd-Steinberg images is DitherKitty¹¹, an open-source project that lets users upload and dither images.

The excerpt below highlights the Floyd-Steinberg code and its connection to our mathematical formula. It adjusts pixel values based on error terms multiplied by specific coefficients (our fractions), mirroring the error diffusion used in our initial algorithm.

Code source: Stellartux¹¹

When applying the Floyd-Steinberg dithering to a real-world object like a goldfish cracker, you can see a smoother transition between dark and light areas compared to the Bayer version. This improvement is due to the error diffusion technique used by Floyd-Steinberg, which adjusts neighboring pixels to create a more seamless effect.

Goldfish Cracker with Floyd-Steinberg Algorithim

Honorable Mentions

There are numerous other forms of dithering, but one I’d like to highlight is Blue Noise Dithering. This technique offers distinct benefits compared to Floyd-Steinberg and Bayer dithering. While Bayer dithering uses a recurrent pattern across the entire image and Floyd-Steinberg utilizes error diffusion to create smoother transitions between neighboring pixels, blue noise dithering takes a different approach to minimize artifacting or recurring patterns in the image.

One example of this is in the game Return of the Obra Dinn⁷, where the entire game features a dithered look. In a forum post, the game's developer, Lucas Pope, mentions that Obra Dinn uses two distinct patterns for different cases: an 8x8 Bayer matrix for a smoother range of shades, and a 128x128 blue noise field for a less ordered output.¹³

Ultimately, blue noise dithering is very useful when you want to achieve a smooth transition between colors, even more so than Floyd-Steinberg methods. It’s almost as though you are looking at the same gradient as before dithering. For more testing of different types, refer to the testing section below. For blue noise and some other dither generations, I am using Surma's dithering tool.¹

Top: Initial Gradient Middle: Bayer 8x8 Bottom: Blue Noise

Testing & Comparisons

There are many different dithering methods, some of which I previously mentioned, like Bayer, Floyd-Steinberg, and Blue Noise. Now, let’s explore some other methods for fun. Surma’s tool¹ for creating dithered images is a fantastic resource if you want to try dithering on your own images.

To start, I’m using this image of a beach in Italy from Google. There is a lot happening in this image, making it a good test for the dithering process on complex scenes.

Initial Image

For this example, we will process the image through the blue noise variation. As a reference, let's first look at our color palette below and see how it appears with the dither pattern. This will give us a good idea of how each specific color is rendered. Lighter colors are more tightly packed with white pixels, while the greens and shadows are less densely packed.

Original Color Palette

Now, let's see what these colors look like after being processed through the dithering tool.

Post Dither Palette

And after processing, we’re left with this beautifully dithered image of the beach.

Dithered Beach [Blue Noise]

Let’s try this with some additional photos. Here’s a photo of me that we can process.

Original Image (me)

Blue Noise Dither

It's a bit hard to see detailed images without zooming in, but below is a zoomed-in view of the photo. You can see how the blue noise technique spreads the pixels, creating smooth transitions between elements and a fluid array of pixels. Whereas the Bayer 8x8 method, the repetitive patterns become more noticeable.

Blue Noise Details

Bayer 8x8 Details

Closing

Dithering is pretty unique and beautiful when applied to real-life images. I still think it’s super cool to see complex images turned into intricate pixel grids of black and white. I’ve learned a lot about this process over the last few weeks and had a bunch of fun writing this. I also dove way deeper into the mathematics than I thought I would, and I still barely scratched the surface of what’s possible with this technique. For more information and resources used in this article, I listed the rabbit hole of references that I went through when writing this.

Resources

Index

Intro Definition Examples Mechanics Mathematical Foundations Testing & Comparisons Closing Resources