Dither: Ordered and Floyd-Steinberg, Monochrome & Colored

• Download source - 6.2 MB
• Download demo - 1.4 MB

Introduction

This article offers simple and fast, practical implementations of some dithering algorithms.
Over the Internet, there is a lot of theory, but lack of implementations. So I decided to offer the opposite - a practical, fast implementations, without theory.

Background

Early on in my career as a programmer, I had to implement an "HTML to WAP converter" plugin. This plugin had to work as part of a proxy server to allow mobile phones (I used my Nokia 3330 to test WAP transcoder) to browse regular web sites. Because mobile phones these days had monchrome displays, I had to convert all images to black/white on the fly.

So, I needed a fast algorithm for good-quality monochrome image dithering.

Finally, I implemented Floyd-Steinberg and my own ordered dithering algorithms. Later, I discovered the Bayer algorithm, which is better and faster.

Later, as part of my work on another project, I implemented a dithering algorithms on three planes (red, green, blue), which produced images with 6bpp, 12bpp and 15bpp. These dithering algorithm implementations are also included in this article.

Here are some samples, produced with the demo project:

Ordered monochrome (1 bpp)

Ordered 3bpp

Ordered 6bpp

Using the Code

There is a pair of files in the project: Dither.h and Dither.cpp
To use the code, you only need to put these files into your project and include the Dither.h file.
These files contain the implementations of all algorithms.

All functions receive as arguments:

• BYTE* pixels - an array of pixels in format 24 bit BGR (b,g,r, b,g,r, ..., b,g,r)
• int width - width in pixels of the image
• int height - height in pixels of the image

In functions that need an extra parameter ncolors, the parameter actually specifies how many dithering bands will be applied to the image. For example, black-white uses 1 band (from black to white); 6 bpp dither uses 3 bands (3 bits per color plane); 12 bpp dither uses 4 bands (4 bits per color plane), etc.

So, in order to perform a simple dither, you should do the following:

#include "Dither.h"

...

//  This will convert the color image to black/white using 16x16 matrix
makeDitherBayer16( pixels, width, height );

There are 3 blocks of functions:

1. Ordered dithering - functions for black/wait ordered dithering using different threshold matrix: 2x2, 3x3, 4x4, 8x8, 16x16.
2. Colored ordered dither - functions that convert a colored image to image with dithering applied to each of its color planes separately (red, green, blue). This means that the dithering is applied on red plane, on green plane and on blue plane.
3. Floyd-Steinberg dither - functions for error-diffusion algorithms: Floyd-Steinberg, Sierra (3-row) and Sierra Lite, as well as colored versions of them.

/////////////////////////////////////////////////////////////////////////////
//    Ordered dither using matrix
/////////////////////////////////////////////////////////////////////////////

void    makeDitherBayer16( BYTE* pixels, int width, int height );
void    makeDitherBayer8 ( BYTE* pixels, int width, int height );
void    makeDitherBayer4 ( BYTE* pixels, int width, int height );
void    makeDitherBayer3 ( BYTE* pixels, int width, int height );
void    makeDitherBayer2 ( BYTE* pixels, int width, int height );

/////////////////////////////////////////////////////////////////////////////
//    Colored Ordered dither, using 16x16 matrix 
//    (dither is applied on all color planes (r,g,b)
/////////////////////////////////////////////////////////////////////////////

void    makeDitherBayerRgbNbpp
        ( BYTE* pixels, int width, int height, int ncolors )    noexcept;

void    makeDitherBayerRgb3bpp ( BYTE* pixels, int width, int height )    noexcept;
void    makeDitherBayerRgb6bpp ( BYTE* pixels, int width, int height )    noexcept;
void    makeDitherBayerRgb9bpp ( BYTE* pixels, int width, int height )    noexcept;
void    makeDitherBayerRgb12bpp( BYTE* pixels, int width, int height )    noexcept;
void    makeDitherBayerRgb15bpp( BYTE* pixels, int width, int height )    noexcept;
void    makeDitherBayerRgb18bpp( BYTE* pixels, int width, int height )    noexcept;

/////////////////////////////////////////////////////////////////////////////
//    Floyd-Steinberg dither
/////////////////////////////////////////////////////////////////////////////

void    makeDitherFS        ( BYTE* pixels, int width, int height )    noexcept;

void    makeDitherFSRgbNbpp 
        ( BYTE* pixels, int width, int height, int ncolors )    noexcept;

void    makeDitherFSRgb3bpp ( BYTE* pixels, int width, int height )    noexcept;
void    makeDitherFSRgb6bpp ( BYTE* pixels, int width, int height )    noexcept;
void    makeDitherFSRgb9bpp ( BYTE* pixels, int width, int height )    noexcept;
void    makeDitherFSRgb12bpp( BYTE* pixels, int width, int height )    noexcept;
void    makeDitherFSRgb15bpp( BYTE* pixels, int width, int height )    noexcept;
void    makeDitherFSRgb18bpp( BYTE* pixels, int width, int height )    noexcept;

void    makeDitherSierraLiteRgbNbpp
        ( BYTE* pixels, int width, int height, int ncolors )    noexcept;
void    makeDitherSierraRgbNbpp    
        ( BYTE* pixels, int width, int height, int ncolors )    noexcept;
void    makeDitherSierraLite       ( BYTE* pixels, int width, int height )    noexcept;
void    makeDitherSierra           ( BYTE* pixels, int width, int height )    noexcept;

/////////////////////////////////////////////////////////////////////////////

The code itself is simple, and well readable. For example:

void    makeDitherBayer16( BYTE* pixels, int width, int height )    noexcept
{
    int    col    = 0;
    int    row    = 0;

    for( int y = 0; y < height; y++ )
    {
        row    = y & 15;    //    y % 16
        
        for( int x = 0; x < width; x++ )
        {
            col    = x & 15;    //    x % 16

            const pixel blue    = pixels[x * 3 + 0];
            const pixel green   = pixels[x * 3 + 1];
            const pixel red     = pixels[x * 3 + 2];

            pixel color  = ((red + green + blue)/3 < BAYER_PATTERN_16X16[col][row] ? 0 : 255);
            
            pixels[x * 3 + 0]    = color;    //    blue
            pixels[x * 3 + 1]    = color;    //    green
            pixels[x * 3 + 2]    = color;    //    red
        }

        pixels += width * 3;
    }
}

For those who need more speed, they could define custom table with values, pre-multiplied to 3, thus eliminate the division in converting RGB to Gray.

Points of Interest

Note that the color quantization used in dither algorithms, the resulting image has changed average contrast. For colored dither, the colors itself become brighter. This is normal.

Functions that dither with specified N (number of bands) produce wrong distribution of error diffusion with some values greater than 20. With other values, the brightness is decreased. This is due to the imperfect algorithm (use of poor basic discretization). So I would suggest to use specific algorithms, but not these with N parameter.

The color dither could be used to "compress" the image, preserving relatively good quality.
For example, the method RGB 6 bits uses 2 bits for each color component of a pixel, thus 6 bits for each pixel, instead of the original 24 bits. To restore the quality, a filter "average 2x2" or average "3x3" could be applied.

Note that in the source code, there are commented functions, that are marked as "Fast but inaccurate".
Their inaccuracy is only in the nuances of colors near white and near dark. But these algorithms are still good and usable. I leave it on you to play with code and check how they work (look at the grayscale and color bands on the test image).

History

• 27^th February, 2020: Initial version