Bill Atkinson and Dithering Algorithms - Engineer Dreams

Photo: Michel Baret/Getty Images

Landon Swartz

Engineers turn dreams into reality - The Wind Rises, Hayao Miyazaki

Follow

GitHub

RSS

Custom Social Profile Link

-->

Simple algorithms are one of my favorite things. They’re quick to learn, elegant, and fun to play with. But importantly, simple algorithms are often the simple solution to a simple problem. Nothing exemplifies this idea more than the Atkinson Dithering algorithm. It is neither the first or best dithering algorithm, but it was a perfect solution for the problem right in front of it on Apple’s original Macintosh. It’s creator, Bill Atkinson, recently passed1 (I know one year is not recently but I am slow at writing so forgive me). I think it’s only fair to honor him with a quick look at one simple algorithm.

Dithering

Dithering a signal is to intentionally add noise in some form or fashion that results in randomizing the quaternization error. Quaternization is when you take something with many inputs, such as 256 colors, and reduce it down to a smaller set of outputs, like 16 colors.

Much like it’s literary definition:

To act nervously or indecisively2

Dithering a signal allows for one to take a function that maps inputs to outputs and make it act a little more nervous in the way it processing pixels to present a more normal looking operation. When dithering images, a by-product of dithering is adding depth to colors.

Dithering algorithms became important in early computer graphics because of limitations of the time. Computer screens could only have so many colors on screen at a time (like black and white or 8 bits of color). Therefore, it became very important to not just be able to display images with the limited color sets but also keep their depth and color. In a few years, this same problem came up on the early internet where images needed to conform to a limited color palette and keep their depth.

One famous example of this is the GIF standard that limits color palettes to 256 colors. Without dithering, quaternization of reducing an image to 256 colors produces the artifact of color banding. It’s ugly, noticeable, and very easy to fix with dithering.

A sampling of algorithms

Floyd-Steinberg

There are many methods to perform dithering for various applications. One can do simple thresholding for a basic solution. Halftoning could be done as well for supporting dot printer operations. A real-time application could reach for a ordered approach that uses a fixed threshold matrix for rendering (like the Return to Obra Dinn3). For our purposes, we will focus on the branch of dithering explored by Bill Atkinson with the original Macintosh: error-diffusion.

Error-diffusion dithering focuses on dithering by “pushing” the error of the quantization process to neighboring pixels and processing the area of pixels versus a singular pixel at a time. It allows for sharper borders and generally cleaner images on early monitors.

I just want to explore two algorithms and leave the others for readers to explore (maybe even create your own!). The first is Floyd-Steinberg (FS) dithering. The FS algorithm was proposed way back in 1976 by Robert W. Floyd and Louis Steinberg. In case, you were wondering when I brought up the GIF standard earlier, this is the dithering algorithm used in the GIF standard. It is simple and efficient. The best way to understand the process of it to me is to work through the code step by step:

# This code is for black and white images for simplicity<br>import numpy as np<br>from PIL import Image

def find_closest_palette_color(pixel: np.float64) -> np.float64:<br>if(pixel 128):<br>return 0<br>else:<br>return 255

def Floyd_Steinberg_Dithering(src_image: np.array) -> np.array:<br># create an output image<br>dst_image = np.copy(src_image).astype(np.float64)<br># Find the bounds of the input<br>height, width = src_image.shape[:2]

# Perform dithering operation in raster order (by row then column)<br>for row in range(height):<br>for col in range(width):<br>old_pixel = dst_image[row, col]<br># Find closest match the old pixel color<br>new_pixel = find_closest_palette_color(old_pixel)<br># Set output to closest match new pixel<br>dst_image[row, col] = new_pixel<br># Find the error from old to new pixel color<br>quant_error = old_pixel - new_pixel

# Diffuse the error to neighboring pixels<br>if col + 1 width:<br>dst_image[row, col + 1] += quant_error * 7/16<br>if col - 1 >= 0 and row + 1 height:<br>dst_image[row + 1, col - 1] += quant_error * 3/16<br>if row + 1 height:<br>dst_image[row + 1, col] += quant_error * 5/16<br>if col + 1 width and row + 1 height:<br>dst_image[row + 1, col + 1] += quant_error * 1/16

return dst_image

Dithering starts by creating an output image of the same size and shape. The process is about taking something visually complex and making it simpler for later processing and displaying. It is important to keep track of bounds and other parameters that should change.

The process of dithering is performed in raster order....