15,999,861 members
Articles / Programming Languages / C

# Dither: Ordered and Floyd-Steinberg, Monochrome & Colored

Rate me:
27 Feb 2020Public Domain3 min read 28.9K   1.6K   6   9
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.

## 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:

## 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.

• `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

Written By
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][
www.brosix.com

 First Prev Next
 Reference of Ordered Dithering algorithm Thành Long Võ7-Aug-24 22:15 Thành Long Võ 7-Aug-24 22:15
 Re: Reference of Ordered Dithering algorithm Svetoslav Chekanov7-Aug-24 22:50 Svetoslav Chekanov 7-Aug-24 22:50
 Re: Reference of Ordered Dithering algorithm Thành Long Võ11-Aug-24 17:33 Thành Long Võ 11-Aug-24 17:33
 Re: Reference of Ordered Dithering algorithm Svetoslav Chekanov11-Aug-24 23:52 Svetoslav Chekanov 11-Aug-24 23:52
 Just what I needed honey the codewitch16-Jun-21 15:41 honey the codewitch 16-Jun-21 15:41
 Re: Just what I needed Svetoslav Chekanov7-Jul-21 5:17 Svetoslav Chekanov 7-Jul-21 5:17
 Re: Just what I needed honey the codewitch7-Jul-21 6:14 honey the codewitch 7-Jul-21 6:14
 Nice topic, a bit change to display the original image as expected comms1-Mar-20 5:51 comms 1-Mar-20 5:51
 Re: Nice topic, a bit change to display the original image as expected Svetoslav Chekanov4-Mar-20 0:32 Svetoslav Chekanov 4-Mar-20 0:32
 Last Visit: 31-Dec-99 18:00     Last Update: 17-Sep-24 8:58 Refresh 1