1-Bit Graphic & Dithering ResearchThis laboratory page houses experimental work on 1-bit monochrome graphics, error-diffusion algorithms, and retro hardware visual interfaces conducted by Binary & Bus, Sys. The Python and C code below was run against a test image, and the C and Python Atkinson versions were checked to give identical output.
Floyd-Steinberg Dithering
The Floyd-Steinberg algorithm distributes quantisation error to neighbouring pixels using fixed weights. For each pixel in raster order (left to right, top to bottom) it quantises the intensity to black or white, computes the error, and spreads it to four neighbours:
Floyd-Steinberg error distribution (* = current pixel)
x-1 x x+1
y * 7/16
y+1 3/16 5/16 1/16
Weights: 7/16 + 3/16 + 5/16 + 1/16 = 16/16 = 1.0
Python implementation:
def floyd_steinberg_dither(image, width, height):
"""Apply Floyd-Steinberg dithering to a greyscale image.
Args:
image: list of lists, values 0.0 (black) to 1.0 (white).
width: image width in pixels.
height: image height in pixels.
Returns:
New image with only values 0.0 and 1.0.
"""
# Work on a copy so the original is not modified.
buf = [row[:] for row in image]
for y in range(height):
for x in range(width):
old = buf[y][x]
# Quantise to the nearest of two values.
new = 0.0 if old < 0.5 else 1.0
buf[y][x] = new
error = old - new
# Distribute the error to four neighbours.
if x + 1 < width:
buf[y][x + 1] += error * 7.0 / 16.0
if y + 1 < height:
if x - 1 >= 0:
buf[y + 1][x - 1] += error * 3.0 / 16.0
buf[y + 1][x] += error * 5.0 / 16.0
if x + 1 < width:
buf[y + 1][x + 1] += error * 1.0 / 16.0
return buf
Atkinson Dithering
The Atkinson algorithm was developed by Bill Atkinson for the original Apple Macintosh in the early 1980s. It distributes only 6/8 (75%) of the quantisation error, to six neighbours, instead of all of it. The result is higher-contrast output with more pronounced patterns, which suits harsh monochrome displays.
Atkinson error distribution (* = current pixel)
x-1 x x+1 x+2
y * 1/8 1/8
y+1 1/8 1/8 1/8
y+2 1/8
Weights: 6 x 1/8 = 6/8 = 0.75
The remaining 25% of the error is discarded.
C implementation:
#include <stdlib.h>
/* Atkinson 1-bit dithering.
* image: 8-bit greyscale buffer, values 0-255, modified in place.
* Returns 0 on success, -1 if memory could not be allocated. */
int atkinson_dither(unsigned char *image, int width, int height) {
/* Six neighbours each receive 1/8 of the error: 75% in total. */
static const int dx[6] = { 1, 2, -1, 0, 1, 0 };
static const int dy[6] = { 0, 0, 1, 1, 1, 2 };
long n = (long)width * height;
float *buf = malloc((size_t)n * sizeof *buf);
if (!buf)
return -1;
for (long i = 0; i < n; i++)
buf[i] = image[i];
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
long idx = (long)y * width + x;
float old = buf[idx];
float val = (old < 128.0f) ? 0.0f : 255.0f;
float err = (old - val) / 8.0f;
image[idx] = (unsigned char)val;
for (int k = 0; k < 6; k++) {
int nx = x + dx[k], ny = y + dy[k];
if (nx >= 0 && nx < width && ny < height)
buf[(long)ny * width + nx] += err;
}
}
}
free(buf);
return 0;
}
Bayer Ordered Dithering (4x4 Matrix)
Ordered dithering uses a fixed threshold matrix instead of error diffusion. The 4x4 Bayer index matrix is tiled across the image, and each pixel is compared against the threshold for its position. It needs no neighbourhood lookups, so it is faster than error diffusion.
Bayer 4x4 index matrix (each value 0-15 appears once) [ 0 8 2 10 ] [ 12 4 14 6 ] [ 3 11 1 9 ] [ 15 7 13 5 ] Threshold = (index + 0.5) / 16, giving: [ 0.031 0.531 0.156 0.656 ] [ 0.781 0.281 0.906 0.406 ] [ 0.219 0.719 0.094 0.594 ] [ 0.969 0.469 0.844 0.344 ] For pixel (x, y) with intensity I between 0.0 and 1.0: output = 1 if I > threshold[y % 4][x % 4] else 0 The matrix repeats every 4 pixels in both directions. No error is propagated between pixels.
Python implementation:
# Bayer 4x4 index matrix: each value 0-15 appears exactly once.
BAYER_4X4 = [
[ 0, 8, 2, 10],
[12, 4, 14, 6],
[ 3, 11, 1, 9],
[15, 7, 13, 5],
]
def bayer_dither(image, width, height):
"""Apply 4x4 Bayer ordered dithering to a greyscale image.
Args:
image: list of lists, values 0.0 (black) to 1.0 (white).
width: image width in pixels.
height: image height in pixels.
Returns:
New image with only values 0.0 and 1.0.
"""
result = []
for y in range(height):
row = []
for x in range(width):
# Threshold for this position, centred in its band: 0.03 ... 0.97.
threshold = (BAYER_4X4[y % 4][x % 4] + 0.5) / 16.0
row.append(1.0 if image[y][x] > threshold else 0.0)
result.append(row)
return result
Algorithm Comparison
Measured with the Python implementations on this page (Atkinson as in dither-pass.py) on a 512x512 greyscale test image, a gradient with a little noise. Times are the best of three runs on one machine and will differ on yours.
Algorithm Time 1-bit PNG Character -------------------------------------------------------------- Floyd-Steinberg ~70 ms ~30 KB Smooth gradients Atkinson ~175 ms ~29 KB High contrast Bayer 4x4 ~20 ms ~7 KB Regular geometric pattern
Output sizes differ because the PNG compresses the regular Bayer pattern far better than the noisy error-diffusion output.
For web delivery, Atkinson dithering is generally preferred for photographic content because of its high contrast on low-resolution screens. Floyd-Steinberg gives smoother gradients and suits diagrams and technical illustrations. Bayer ordered dithering is useful when speed matters or when a regular geometric texture is acceptable.
Navigation & Lab Index: