Click here to Skip to main content
15,867,488 members
Articles / Programming Languages / C

Dither: Ordered and Floyd-Steinberg, Monochrome & Colored

Rate me:
Please Sign up or sign in to vote.
5.00/5 (7 votes)
27 Feb 2020Public Domain3 min read 26.6K   1.4K   6   5
A collection of image dithering algorithms
This article includes implementation of some Dithering algorithms: Ordered Bayer matrix dithering with 2x2 , 3x3, 4x4, 8x8 and 16x16 matrix, Floyd-Steinberg; Sierra, Sierra Lite, and as a bonus - colored versions of the same algorithms.

Image 1

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.

Image 2

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)

Image 3

Ordered 3bpp

Image 4

Ordered 6bpp

Image 5

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:

C++
#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.
C++
/////////////////////////////////////////////////////////////////////////////
//    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:

C++
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

  • 27th February, 2020: Initial version

License

This article, along with any associated source code and files, is licensed under A Public Domain dedication


Written By
Technical Lead Brosix
Bulgaria Bulgaria
I am a software development engineer .

Programming Languages: C/C++, Java, Delphi, HTML, CGI, Assembly x86, CNC G-language
RDBMS Microsoft SQL Server, MySQL, SQLite, MS Access, ODBC, JDBC

Networking: TCP/IP, Winsock, HTTP, HTTPS, FTP, SMTP, POP3, TELNET, IMAP, SOCKS 4/5, RTSP, CGI, MS Internet Information Server

Projects I have worked on:
  • Brosix
  • Screen-Sharing product
  • Video chat application
  • Server software
  • Java Virtual Machine
  • Application Server + Internet Proxy Services
  • Instant Messenger - like MSN and Yahoo ones
  • Voicer - Freeware VoIP application
  • Web Server
  • SSH Proxy - SOCKS 4&5 Proxy that can relay TCP Connections through HTTPS Proxy
  • HTTP Proxy
  • SOCKS proxy
  • Battery Test Suite
  • MFC custom UI controls
  • Internet Address Book - Synchronizes local Outlook, Outlook Express, Netscape and Eudora address book with database on WEB server located in the Internet
  • Advertising Screen Saver - Screen Saver that sends e-mails and gain prizes for the computer owner
  • Proxy Send Mail - Send Mail service that can send e-mails through SOCKS 4, SOCKS 5 and HTTPS proxies
  • Proxy Hunter - Very fast, and also works as proxy checker
  • Java Disassembler
  • Java custom UI controls
  • Delphi custom UI controls
  • CNC Gravuring System
  • Font editor for DOS
  • Little DOS games
  • Graphics library for DOS (in Assembly)
  • Galaxian like game for Apple][ in assembly
  • Graphics editor for Apple][
  • Font editor for Apple][
  • More information about my current work you can find here:
    www.brosix.com


    Comments and Discussions

     
    PraiseJust what I needed Pin
    honey the codewitch16-Jun-21 15:41
    mvahoney the codewitch16-Jun-21 15:41 
    I'm a little late to the party but this is just the ticket for my GFX library.
    GFX Forever: The Complete Guide to GFX for IoT[^]

    My +5 vote. You earned it.

    One thing I noticed is your algorithm - at least the demo, does not do 16-bit color (rgb565) but only the less common 15-bit color. It's not a criticism. It's just curious. Smile | :) I'll have to adapt the code anyway as my library supports pixels of arbitrary bit depth
    Real programmers use butterflies

    GeneralRe: Just what I needed Pin
    Svetoslav Chekanov7-Jul-21 5:17
    Svetoslav Chekanov7-Jul-21 5:17 
    GeneralRe: Just what I needed Pin
    honey the codewitch7-Jul-21 6:14
    mvahoney the codewitch7-Jul-21 6:14 
    PraiseNice topic, a bit change to display the original image as expected Pin
    comms1-Mar-20 5:51
    comms1-Mar-20 5:51 
    GeneralRe: Nice topic, a bit change to display the original image as expected Pin
    Svetoslav Chekanov4-Mar-20 0:32
    Svetoslav Chekanov4-Mar-20 0:32 

    General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

    Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.