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 coefficients.
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.
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.
private static readonly byte[,] _matrix =
{
{
0, 0, 0, 8, 4
},
{
2, 4, 8, 4, 2
}
};
private const int _matrixHeight = 2;
private const int _matrixStartX = 2;
private const int _matrixWidth = 5;
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.
int redError;
int blueError;
int greenError;
redError = originalPixel.R - transformedPixel.R;
blueError = originalPixel.G - transformedPixel.G;
greenError = originalPixel.B - transformedPixel.B;
for (int row = 0; row < _matrixHeight; row++)
{
int offsetY;
offsetY = y + row;
for (int col = 0; col < _matrixWidth; col++)
{
int coefficient;
int offsetX;
coefficient = _matrix[row, col];
offsetX = x + (col - _matrixStartX);
if (coefficient != 0 && offsetX > 0 && offsetX < width && offsetY > 0 && offsetY < height)
{
ArgbColor offsetPixel;
int offsetIndex;
offsetIndex = offsetY * width + offsetX;
offsetPixel = original[offsetIndex];
offsetPixel.R = (offsetPixel.R + ((redError * coefficient) >> 5)).ToByte();
offsetPixel.G = (offsetPixel.G + ((greenError * coefficient) >> 5)).ToByte();
offsetPixel.B = (offsetPixel.B + ((blueError * coefficient) >> 5)).ToByte();
original[offsetIndex] = offsetPixel;
}
}
}
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 date.
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.
Another article in my C# image dithering mini-series, this time covering the Burkes error diffusion algorithm.
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.