In my previous post, I described how to dither an image in
C# using the Floyd‑Steinberg algorithm. Continuing this theme,
this post will cover the Burkes algorithm.
I will be using the same demonstration application as from the
previous post, so I won't go over how this works again.
As with Floyd‑Steinberg, the Burkes algorithm is an error
diffusion algorithm, which is to say for each pixel an "error"
is generated and then distributed to pixels around the source.
Unlike Floyd‑Steinberg however (which modifies 4 surrounding
pixels), Burkes modifies 7 pixels.
Burkes is actually a modified version of the Stucki algorithm,
which in turn is an evolution of the Jarvis algorithms.
The diagram below shows the distribution of the error
8 for the pixel to the right of the current pixel
4 for the second pixel to the right
2 for the pixel below and two to the left
4 for the pixel below and to the left
8 for the pixel below
4 for the pixel below and to the right
2 for the pixel below and two to the right
Unlike Floyd‑Steinberg, the error result in this algorithm is
divided by 32. But as that's still a power of two, once again we
can use bit shifting to perform the division.
Due to the additional calculations I would assume that this
algorithm will be slightly slower than Floyd‑Steinberg, but as
of yet I haven't ran any form of benchmarks to test this.
Applying the algorithm
In my Floyd‑Steinberg example, I replicated the calculations
four times for each pixel. As there are now seven sets of
calculations with Burkes, I decided to store the coefficients in
a 2D array mimicing the diagram above, then iterating this. I'm
not entirely convinced this is the best approach, but it does
seem to be working.
This sets up the matrix as a static that is only created once.
I've also added some constants to control the offsets as I can't
create an array with a non-zero lower bound. This does smell a
bit so I'll be revisiting this!
Below is the code to dither a single pixel. Remember that the
demonstration program uses a 1D array of ArgbColor structs to
make it easy to read and understand, but you could equally use
direct pointer manipulation on a bitmap's bits, with lots of
extra code to handle different colour depths.
Due to the loop this code is now shorter than the
Floyd‑Steinberg version. It's also less readable due the
coefficients being stored in a 2D matrix. Of course, the
algorithm is fixed and won't change so perhaps that's not an
issue, but if performance really was a concern you can unroll
the loop and duplicate all that code. I'll stick with the loop!
The image below shows our sample image dithered using the Burkes
algorithm. It's very similar to the output created via
Floyd–Steinberg, albeit darker.
Again, by changing the threshold at which colours are converted
to black or white, we can affect the output of the dithering
even if the conversion is to solid black.
The latest source code for this demonstration (which will be
extended over time to include additional algorithms) can be
found at our GitHib page.
The source code from the time this article was created is
available from the link below, however may not be fully up to
2015-06-06 - First published
2020-11-21 - Updated formatting
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.
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.