Skip to content
Computational Lab.

Error-Diffusion Dithering

Two gray levels, one honest average.

Beginner / quantization / error-diffusion

Floyd-Steinberg dithering quantizes each pixel to a small palette and pushes the rounding error onto four neighbors. Structure is lost, averages are kept: the metric shows the dithered image's mean luminance matching the original's to four decimals - which is why dithering fools the eye.

Tagged: Floyd-Steinberg, serpentine, error diffusion, quantization

Live simulation

Two gray levels, and the mean luminance still matches to four decimals.

Speed

Two gray levels, and the mean luminance still matches to four decimals.

Mathematics

Quantizing an image to k gray levels loses structure; error diffusion gives the structure back in disguise. Floyd-Steinberg quantizes each pixel and distributes the rounding error to four unprocessed neighbors (7/16, 3/16, 5/16, 1/16), so local errors cancel in the aggregate.

quantize: q = round(v (L-1)) / (L-1)

diffuse: err = v - q; neighbors += err * (7, 3, 5, 1)/16

invariant: mean(dithered) ~= mean(original)

The mean-luminance invariant is the theorem this page demonstrates: error diffusion is unbiased, so the average brightness survives quantization exactly to first order, and the metric verifies it to four decimals. Plain thresholding - the comparison mode - has no such mechanism: whole gray ranges vanish, and the mean visibly shifts.

How it works

The source pattern is generated procedurally; the serpentine scan (alternating direction per row) reduces directional worm artifacts of the classic kernel. The split view compares original and dithered at the same scale.

Levels 2 is true 1-bit dithering; push to 5 and the diffusion has almost nothing left to do.

Implementation

src/engine/experiments/dithering.ts · 168 lines · the module running above

TypeScript · fixed-timestep engine

1import { BaseExperiment } from "../core/base-experiment";
2import type { ParameterDef, ThemeColors } from "../core/types";
3
4const SIZE = 110;
5
6/**
7 * Floyd-Steinberg error-diffusion dithering: quantize each pixel and push
8 * the rounding error to the four neighbors. Averaging is the invariant -
9 * the dithered image's mean luminance must match the original's, and the
10 * metric shows it.
11 */
12export class DitheringExperiment extends BaseExperiment {
13 readonly id = "dithering";
14
15 private original = new Float64Array(SIZE * SIZE);
16 private dithered = new Float64Array(SIZE * SIZE);
17 private image: ImageData | null = null;
18 private scratch: HTMLCanvasElement | null = null;
19 private needsCompute = true;
20 private originalMean = 0;
21 private ditheredMean = 0;
22
23 protected params(): ParameterDef[] {
24 return [
25 {
26 key: "pattern",
27 label: "Source image",
28 options: [
29 { value: "gradient", label: "Gradient" },
30 { value: "shapes", label: "Shapes" },
31 ],
32 defaultValue: "shapes",
33 },
34 { key: "levels", label: "Gray levels", min: 2, max: 5, step: 1, defaultValue: 2 },
35 {
36 key: "mode",
37 label: "Method",
38 options: [
39 { value: "fs", label: "Floyd-Steinberg" },
40 { value: "threshold", label: "Plain threshold" },
41 ],
42 defaultValue: "fs",
43 },
44 ];
45 }
46
47 protected onReset(): void {
48 const pattern = this.str("pattern");
49 for (let y = 0; y < SIZE; y++) {
50 for (let x = 0; x < SIZE; x++) {
51 const u = x / SIZE;
52 const v = y / SIZE;
53 let value: number;
54 if (pattern === "gradient") {
55 value = u * 0.85 + 0.05;
56 } else {
57 const disk = Math.hypot(u - 0.4, v - 0.42) < 0.22 ? 0.55 : 0;
58 value = Math.min(1, 0.15 + v * 0.5 + disk + (Math.sin(u * 30) * 0.04 + 0.04));
59 }
60 this.original[y * SIZE + x] = Math.min(1, Math.max(0, value));
61 }
62 }
63 this.needsCompute = true;
64 }
65
66 protected onParameterChange(): void {
67 this.needsCompute = true;
68 }
69
70 private compute(): void {
71 const levels = this.num("levels");
72 const quantize = (v: number) => Math.round(v * (levels - 1)) / (levels - 1);
73 const work = Float64Array.from(this.original);
74 this.dithered.fill(0);
75 const fs = this.str("mode") === "fs";
76 for (let y = 0; y < SIZE; y++) {
77 const serpentine = y % 2 === 0;
78 for (let i = 0; i < SIZE; i++) {
79 const x = serpentine ? SIZE - 1 - i : i;
80 const idx = y * SIZE + x;
81 const old = Math.min(1, Math.max(0, work[idx]));
82 const newV = quantize(old);
83 this.dithered[idx] = newV;
84 const err = old - newV;
85 if (!fs) continue;
86 // Floyd-Steinberg kernel: 7/16 right, 3/16 below-left, 5/16 below, 1/16 below-right.
87 const right = serpentine ? -1 : 1;
88 if (x + right >= 0 && x + right < SIZE) work[idx + right] += (err * 7) / 16;
89 if (y + 1 < SIZE) {
90 if (x - right >= 0 && x - right < SIZE) work[idx + SIZE - right] += (err * 3) / 16;
91 work[idx + SIZE] += (err * 5) / 16;
92 if (x + right >= 0 && x + right < SIZE) work[idx + SIZE + right] += err / 16;
93 }
94 }
95 }
96 let oSum = 0;
97 let dSum = 0;
98 for (let i = 0; i < this.original.length; i++) {
99 oSum += this.original[i];
100 dSum += this.dithered[i];
101 }
102 this.originalMean = oSum / this.original.length;
103 this.ditheredMean = dSum / this.dithered.length;
104 this.needsCompute = false;
105 }
106
107 protected onUpdate(): void {
108 if (this.needsCompute) this.compute();
109 }
110
111 render(ctx: CanvasRenderingContext2D, theme: ThemeColors): void {
112 ctx.fillStyle = theme.bg;
113 ctx.fillRect(0, 0, this.width, this.height);
114 if (this.needsCompute) this.compute();
115 if (!this.image || this.image.width !== SIZE) {
116 this.image = new ImageData(SIZE, SIZE);
117 this.scratch = document.createElement("canvas");
118 this.scratch.width = SIZE;
119 this.scratch.height = SIZE;
120 }
121 const data = this.image.data;
122 for (let y = 0; y < SIZE; y++) {
123 for (let x = 0; x < SIZE; x++) {
124 const i = y * SIZE + x;
125 const v = x < SIZE / 2 ? Math.round(this.original[i] * 255) : Math.round(this.dithered[i] * 255);
126 const p = i * 4;
127 data[p] = v;
128 data[p + 1] = v;
129 data[p + 2] = v;
130 data[p + 3] = 255;
131 }
132 }
133 const offCtx = this.scratch!.getContext("2d")!;
134 offCtx.putImageData(this.image, 0, 0);
135 ctx.imageSmoothingEnabled = false;
136 // Split: original left, dithered right.
137 ctx.drawImage(this.scratch!, 0, 0, SIZE / 2, SIZE, 0, 0, this.width / 2, this.height);
138 ctx.drawImage(this.scratch!, SIZE / 2, 0, SIZE / 2, SIZE, this.width / 2, 0, this.width / 2, this.height);
139 ctx.strokeStyle = theme.fgSecondary;
140 ctx.beginPath();
141 ctx.moveTo(this.width / 2, 0);
142 ctx.lineTo(this.width / 2, this.height);
143 ctx.stroke();
144 ctx.font = "11px ui-monospace, monospace";
145 ctx.fillStyle = theme.fgTertiary;
146 ctx.fillText("ORIGINAL", 10, 16);
147 ctx.fillStyle = theme.accent;
148 ctx.fillText(this.str("mode") === "fs" ? `FLOYD-STEINBERG (${this.num("levels")} LEVELS)` : `THRESHOLD (${this.num("levels")} LEVELS)`, this.width / 2 + 10, 16);
149 }
150
151 getMetrics() {
152 return {
153 levels: this.num("levels"),
154 originalMean: this.originalMean.toFixed(4),
155 ditheredMean: this.ditheredMean.toFixed(4),
156 meanError: Math.abs(this.originalMean - this.ditheredMean).toFixed(4),
157 };
158 }
159
160 describe(): string {
161 return `Error-diffusion dithering to ${this.num("levels")} gray levels preserves the mean luminance to ${Math.abs(this.originalMean - this.ditheredMean).toFixed(4)} - the structure is quantized, the average is not.`;
162 }
163
164 entities(): number {
165 return SIZE * SIZE;
166 }
167}
168

Performance

Time per tick
O(pixels), one pass
Space
Two pixel buffers
Notes
Watch a flat gray region: it becomes a perfectly regular checkerboard, because uniform error diffuses into uniform structure.

Live numbers (FPS, frame time, steps per second, microseconds per step, entity count) are in the performance overlay on the simulation above: the pulse icon in its top-right corner.