A look at various simple dithering algorithms in C++ [shorts #3]

The previous short article investigated a simple method for scaling images using standard C++. In that article, I mentioned that I was working on a way to shrink images for displaying them on the Mac Classic CRT. I also mentioned that, to display the images on the Mac’s CRT, I’d also need to employ a dithering algorithm to prevent losing too much detail. Therefore, this article takes a look at three simple and popular dithering algorithms implemented in C++.

Why do we need dithering?

Dithering is a method for converting images from one color space into a typically more limited one (e.g., for displaying them on a black and white monitor). Besides that conversion, dithering has the goal of minimizing the loss of image information and detail. Throughout this article, I’ll convert standard 32-bit bitmap images (more than four billion possible colors) to single-bit black and white images (only two colors). The goal is to lose as little of the image detail as possible.

Threshold Dithering

This is the simplest and fastest dithering method. First, you define a threshold value. This is typically the midpoint between pure black and the maximum brightness. In my case, where I’m working with eight-bit grayscale data, this midpoint corresponds to a decimal value of 127. Next, you perform the dithering by setting all pixels below that threshold to black and all pixels above that threshold to white:

Figure 1: Threshold dithering. Note the loss of information especially around the bridge cables, the buildings in the background, and the bottom corners of the original image.

Note that you can shift the midpoint to achieve different effects. Furthermore, you can analyze the input image to determine an average threshold level for each image. Either way, this simple dithering method achieves good enough results in many cases. However, threshold dithering leads to a great loss in image detail and contrast in many real-world scenarios. Therefore, this method is perfect for text-only applications and simple graphics, but it’s usually insufficient for converting complex images such as photographs:

void ImageManipulator::performAverageDithering(Image* source, Image* result)
{
    unsigned char sourcePixel[3];

    for (int y = 0; y < source->getHeight(); y++)
    {
        for (int x = 0; x < source->getWidth(); x++)
        {
            // Get the current pixel
            source->getPixel(x, y, &sourcePixel[0]);

            // If the current pixel is less than the threshold
            // then set the current pixel to black
            if(sourcePixel[0] <= 0x7F)
                result->setPixel(x, y, 0x00, 0x00, 0x00);
            // Otherwise, change it to white
            else
                result->setPixel(x, y, 0xFF, 0xFF, 0xFF);
        }
    }
}

Random Dithering

This method is very similar to plain threshold dithering. However, instead of using a fixed threshold (which can either be completely fixed or determined by analyzing the image), this method calculates a random threshold value for each pixel. Applying this method eliminates some of the problems introduced by pure threshold dithering, such as sharp edges and stark loss in color information and detail. However, random dithering introduces an aliasing artifact known as snow, something that might remind you of the days of analog television and CRTs:

Figure 2: Random dithering outputs a better result than pure threshold dithering. Note how you can now make out more details around the dark areas. However, this method leads to strong snow-storm-like noise artifacts.

This snow artifact is caused by pixels that don’t match their neighboring pixels where they should. Suppose, for example, that your image has a completely black area. All pixels should be black in this area. With random dithering, however, the algorithm might set some of these black pixels to white, leading to the aforementioned snow artifact. This, again, is a very simple and cost-effective implementation of a dithering algorithm. It surely has its problems, but I think that random dithering overall achieves better results than pure threshold dithering.

void ImageManipulator::performRandomDithering(Image* source, Image* result)
{
    unsigned char sourcePixel[3];

    for (int y = 0; y < source->getHeight(); y++)
    {
        for (int x = 0; x < source->getWidth(); x++)
        {
            source->getPixel(x, y, &sourcePixel[0]);
            unsigned char randomValue = 0 + ( std::rand() % 256 );

            if(randomValue <= sourcePixel[0])
                result->setPixel(x, y, 0xFF, 0xFF, 0xFF);
            else
                result->setPixel(x, y, 0x00, 0x00, 0x00);
        }
    }
}

Floyd-Steinberg Dithering

The Floyd-Steinberg algorithm is a more sophisticated dithering algorithm, as it relies on error dispersion. Compared to the other two methods, this algorithm not only checks a single pixel at a time but instead always considers the neighborhood around the pixel it’s currently converting. As mentioned earlier, dithering converts an image from a larger color space to one with fewer available colors. Therefore, a pixel can typically not keep its original color. Instead, we need to assign it a color from the new pallet that’s as close to the original color as possible. This process, however, usually creates a bit of an error for each pixel. The Floyd-Steinberg algorithm remembers this error when it moves on to the next pixels and changes the color of the following pixels according to the conversion error. More concretely, the error is the difference between the target color and the closest color from the new palette. The algorithm distributes the error to the neighboring pixels using an asymmetric 3×2 filter).

Naturally, the computationally most expensive method of the three presented ones gives the best results. Floyd-Steinberg dithering nicely preserves contrast and details, and it even produces something similar to smooth gradients, even with a very limited palette of two colors:

Figure 3: Floyd-Steinberg produces the best result of the three methods discussed in this article. Note how most of the detail and contrast is preserved. Also note how the error eventually adds up and leads to larger white or black clusters. This may be due to a custom filter that I used because I prefer the way it looks compared to the standard filter kernel.

The source code for this algorithm looks like this:

void ImageManipulator::performFloydSteinbergDithering(Image* source, Image* result)
{
    for(int y = 0; y < source->getHeight(); y++)
    {
        for(int x = 0; x < source->getWidth(); x++)
        {
            if(x - 1 >= 0 && y + 1 < source->getHeight() && x + 1 < source->getWidth())
            {
                unsigned char oldPixel[3];
                unsigned char newPixel = 0xFF;
                unsigned char others[4][3];
                unsigned char otherValues[4];
                char error = 0x00;

                source->getPixel(x, y, &oldPixel[0]);
                source->getPixel(x+1, y, &others[0][0]);
                source->getPixel(x-1, y+1, &others[1][0]);
                source->getPixel(x, y+1, &others[2][0]);
                source->getPixel(x+1, y+1, &others[3][0]);

                if(oldPixel[0] < 0x80)
                    newPixel = 0x00;

                result->setPixel(x, y, newPixel, newPixel, newPixel);
                error = oldPixel[0] - newPixel;

                for(int i = 0; i < sizeof(ditheringFilter) / sizeof(unsigned char); i++)
                {
                    otherValues[i] = others[i][0] + error * ditheringFilter[i] * 0.0625;
                }

                result->setPixel(x+1, y,   otherValues[0], otherValues[0], otherValues[0]);
                result->setPixel(x-1, y+1, otherValues[1], otherValues[1], otherValues[1]);
                result->setPixel(x  , y+1, otherValues[2], otherValues[2], otherValues[2]);
                result->setPixel(x+1, y+1, otherValues[3], otherValues[3], otherValues[3]);
            }
        }
    }
}

Download the source code

You can download the complete source code here. Please make sure to include a link to this article if you share or use the code in your custom projects. Thanks!

Sources

Floyd-Steinberg Dithering – visgraf.impa.br

Leave your two cents, comment here!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.