Although I should really be working on adding the dithering
algorithms into Gif Animator, I thought it would be useful
to expand the repertoire of algorithms available for use with it
and the other projects I'm working on.

Adding a general purpose base class

I decided to re-factor the class I created for the Burkes
algorithm to make it suitable for adding other error diffusion
filters with a minimal amount of code.

First, I added a new abstract class, ErrorDiffusionDithering.
The constructor of this class requires you to pass in the matrix
used to disperse the error to neighbouring pixels, the divisor,
and whether or not to use bit shifting. The reason for the last
parameter is the Floyd-Steinberg and Burkes algorithms
covered in my earlier posts had divisors that were powers of
two, and so could therefore be bit shifted for faster division.
Not all algorithms use a power of two divisor though and so we
need to be flexible.

The constructor then stores the matrix, and pre-calculates a
couple of other values to avoid repeating these each time the
Diffuse method is called.

The actual dithering implementation is unchanged from original
matrix handling code, with the exception of supporting bit
shifting or integer division, and not having to work out the
current pixel in the matrix, width or height.

Burkes Dithering, redux

The BurkesDithering class now looks like this

No code, just the matrix and the bit shifted divisor of 5, which
will divide each result by 32. Nice!

More Algorithms

As well as opening the door to allowing a user to define a
custom dither matrix, it also makes it trivial to implement a
number of other common error diffusion matrixes. The GitHub
Repository now offers the
following algorithms

Atkinson

Burkes

Floyd-Steinberg

Jarvis, Judice & Ninke

Sierra

Two Row Sierra

Sierra Light

Stucki

Which is a fairly nice array.

Random Dithering

There's a rather old (in internet terms anyway!) text file
floating around named DHALF.TXT (based in turn on an even
older document named DITHER.TXT) that has a ton of useful
information on dithering, and with the exception of the
Altkinson algorithm (I took that from here is where I have
pulled all the error weights and divisors from.

One of the sections in this document dealt with random
dithering. Although I didn't think I would ever use it myself, I
thought I'd add an implementation of it anyway to see what it's
like.

Unlike the error diffusion methods, random dithering affects
only a single pixel at a time, and does not consider or modify
its neighbours. You also have a modicum of control over it too,
if you can control the initial seed of the random number
generator.

The DHALF.TXT text sums it up succinctly: For each dot in our
grayscale image, we generate a random number in the range 0 -
255: if the random number is greater than the image value at
that dot, the display device plots the dot white; otherwise, it
plots it black. That's it.

And here's our implementation (ignoring the fact that it isn't
error diffusion and all of a sudden our IErrorDiffusion
interface is named wrong!)

(Although I reversed black and white from the original
description as otherwise it looked completely wrong)

I was surprised to see it actually doesn't look that bad.

Continuation

I've almost got a full house of useful dithering algorithms now.
About the only thing left for me to do is to implement a ordered
Bayer dithering as I really like the look of this type, and
reminds me of games and computers of yesteryear. So there's
still at least one more article to follow in this series!

The updated source code with all these algorithms is available
from the GitHub repository.

Update History

2015-06-13 - First published

2020-11-21 - Updated formatting

2024-08-10 - Corrected the blue and green error values being used in reverse, thanks to Kevin Cahalan for discovering this

Like what you're reading? Perhaps you like to buy us a coffee?

The founder of Cyotek, Richard enjoys creating new blog content for the site. Much more though, he likes to develop programs, and can often found writing reams of code. A long term gamer, he has aspirations in one day creating an epic video game - but until that time comes, he is mostly content with adding new bugs to WebCopy and the other Cyotek products.

Although I should really be working on adding the dithering algorithms into Gif Animator, I thought it would be useful to expand the repertoire of algorithms available for use with such tools. This article briefly mentions the expanded error diffusion algorithms that are now included, and in slightly more detail covers random dithering as well.

In my previous introductory post, I briefly described the concept of dithering an image. In this article, I will describe how to dither an image in C# using the Floyd–Steinberg algorithm.

When you reduce the number of colours in an image, it's often hard to get a 1:1 match, and so typically you can expect to see banding in an image - areas of unbroken solid colours where once multiple similar colours were present. Such banding can often ruin the look of the image, however by using dithering algorithms you can reduce such banding and greatly improve the appearance of the reduced image. This article briefly discusses dithering as a prelude to further articles with actual dithering implementations.