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:

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:

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:

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