Dizzy dithering

An example of a color image processed using Dizzy dithering

Dizzy dithering is an error diffusion dithering algorithm developed by Liam Appelbe in 2024. Unlike traditional error diffusion algorithms that traverse pixels linearly or along a space-filling curve, Dizzy dithering visits pixels in a randomized order. This approach suppresses directional artifacts and regular patterns typical of Floyd–Steinberg dithering, producing visual results comparable to blue noise dithering while preserving sharp image details.

Algorithm

A 1-bit image of the Statue of David, dithered with the Dizzy algorithm

Like other error diffusion methods, Dizzy dithering operates by quantizing pixel values one at a time and diffusing the resulting quantization residual (error) to adjacent unprocessed pixels.

The algorithm proceeds as follows:

1. Initialization: Generate a shuffled or pseudorandom traversal sequence covering all pixel coordinates in the image.
2. Traversal: Iterate through pixels according to the sequence. For each pixel:
   1. Calculate the quantization error:

${\text{error}}={\text{color}}_{\text{input}}-{\text{color}}_{\text{quantized}}$

1. 1. Identify all adjacent neighboring pixels (up to 8 in a 3×3 neighborhood) that have not yet been processed.
   2. Calculate a weighting factor for each unprocessed neighbor. To reduce spatial grid structure, orthogonally adjacent pixels are assigned significantly higher weights (e.g., $10\times$) than diagonally adjacent pixels.
   3. Distribute fractions of the quantization error to the unprocessed neighbors proportional to their weights:

${\text{neighbor}}_{\text{error}}+={\text{error}}\times {\frac {{\text{weight}}_{\text{neighbor}}}{\sum {\text{weights}}_{\text{unprocessed}}}}$

1. Completion: Mark the pixel as processed and repeat until all pixels are quantized.

Comparison with other techniques

• Floyd–Steinberg dithering: Processes pixels line-by-line, creating noticeable diagonal or axial streaking and artifact patterns in homogeneous regions. Dizzy dithering eliminates these directional biases due to its randomized traversal.
• Ordered dithering (e.g., Bayer dithering): Highly efficient and suitable for real-time GPU implementation, but introduces repeating geometric grid patterns. Dizzy dithering yields organic, isotropic noise distribution.
• Blue noise dithering: Typically generated via time-expensive algorithms like void-and-cluster. While blue noise removes low-frequency clumping, it can obscure fine edge details (such as thin lines). Dizzy dithering offers a similar isotropic distribution without severe loss of high-frequency detail.
• Riemersma dithering: Uses space-filling curves (such as Hilbert curves) to randomize scan direction. However, it can still produce symmetrical patterns or structural artifacts in gradient regions compared to pure randomized traversal.

Optimizations

A naive implementation of Dizzy dithering requires maintaining memory state for pixel traversal order, a tracking bitmask for processed pixels, and an error distribution buffer. These requirements can be optimized to achieve $O(1)$ auxiliary memory overhead beyond the image buffer:

Applications

Dizzy dithering has been adapted for use in electronic paper (e-paper) display systems, such as e-readers and custom e-paper laptops.

E-paper display rendering

Traditional error diffusion algorithms like Floyd–Steinberg dithering are poorly suited for dynamic e-paper user interfaces. Because error diffuses globally across the screen, minor local updates (such as moving a mouse cursor or a blinking text caret) trigger wide-area recalculations. On e-paper displays, this results in visual flickering and persistent "ghosting" artifacts.

In contrast, the randomized nature of Dizzy dithering keeps error propagation highly localized. This local confinement makes the algorithm well-suited for partial screen updates—updating only the modified bounding box of an interface without disturbing the surrounding display area or accumulating ghosting.

GPU parallelization

Although standard error diffusion is inherently sequential and traditionally executed on a single CPU thread, Dizzy dithering's localized error boundaries allow for massive parallelization on modern GPUs.

By structuring the image traversal into multiple non-overlapping spatial layers of randomly selected pixels, GPUs can process large batches of pixels concurrently without memory write collisions. Implementations of Dizzy dithering on graphics processors have demonstrated performance up to $280\times$ faster than single-threaded CPU Floyd–Steinberg dithering, enabling real-time general-purpose desktop rendering on monochrome and greyscale e-paper displays.

In-place error diffusion

Quantization errors can be added directly into the image's floating-point color channels of unprocessed neighboring pixels, eliminating the need for a separate error accumulation matrix.

Stateless pseudorandom traversal

Instead of storing a fully shuffled list of pixel coordinates ($O(N)$ memory), pixels can be visited using a stateless pseudorandom permutation. By rounding the total pixel count up to the nearest power of two ($2^n$), a sequence of modular multiplication by an odd constant and bitwise XOR operations can generate a bijective permutation in $O(1)$ space:

$i_{k+1}=\left((i_{k}\cdot r_{\text{odd}}){\bmod {2}}^{n}\right)\oplus r_{\text{any}}$

Indices exceeding the actual pixel resolution are simply skipped during traversal.

Key characteristics

• Temporal coherence: Unlike traditional error diffusion algorithms, which exhibit severe spatial flickering across dynamic frames when input pixels change slightly, Dizzy dithering achieves strong temporal stability if the same pseudorandom iteration sequence is reused across frames. Empirical measurements show that over 99% of quantization errors decay within a radius of 8 pixels rather than propagating across the entire image.
• Arbitrary palette support: Because it is based on error diffusion, Dizzy dithering inherently supports arbitrary, non-grid color palettes (such as optimized 256-color GIF palettes), a scenario where standard ordered dithering fails.
• Orthogonal error propagation: Experimentation demonstrated that restricting error propagation strictly to the 4 orthogonally adjacent pixels (excluding diagonals) yields visually equivalent results while significantly simplifying spatial layer generation for parallel execution.

Limitations

While Dizzy dithering addresses several artifacts of traditional methods, it introduces specific trade-offs:

• Computational and memory overhead: On the CPU, Dizzy dithering is slightly slower and requires more memory than Floyd–Steinberg dithering due to the necessity of tracking unprocessed neighbors and generating pseudorandom index sequences.
• Multi-pass GPU execution: Parallel GPU implementations ("Layered Dizzy dithering") require a multi-pass pipeline (typically iterating sequentially through ~8 spatial layers). This makes it computationally heavier than single-pass ordered dithering techniques like Bayer or pre-baked blue noise.
• Pre-computed spatial masks: Real-time GPU execution relies on pre-generating spatial layer masks (e.g., via a randomized greedy algorithm) to guarantee that pixels processed simultaneously are separated by a minimum Euclidean distance, preventing GPU memory write race conditions.

See also

• Dithering
• Error diffusion
• Floyd–Steinberg dithering
• Ordered dithering
• Blue noise