What is a good, optimized C/C++ algorithm for converting a 24-bit bitmap to 16-bit with dithering?

Question

I've been looking for an optimized (i.e., quick) algorithm that converts a 24-bit RGB bitmap to a 16-bit (RGB565) bitmap using dithering. I'm looking for something in C/C++ where I can actually control how the dithering is applied. GDI+ seems to provide some methods, but I can't tell if they dither or not. And, if they do dither, what mechanism are they using (Floyd-Steinberg?)

Does anyone have a good example of bitmap color-depth conversion with dithering?

Haricot

565 will still look terrible even with optimal dithering. Just out of curiosity, why do this? – Federation

@stark, I disagree, see this example: https://mcmap.net/q/1325164/-how-can-i-correct-color-banding-in-windows-phone-7 – Klenk

@Federation - it's because I'm outputting to a piece of hardware that only supports RGB565. It won't be displayed on the user's monitor. – Haricot

@Mark I notice that's a single color image. – Federation

@Federation I'm happy to repeat the experiment on any image you'd like. – Klenk

@mark I would guess Lena has to be the standard 24-bit color image. – Federation

@Federation my dithering code isn't done yet but I tried a straight conversion of Lena to 565 and I can't tell the difference between the before and after. Certainly no worse than the typical JPEG artifacts. I noticed the same with one of my own pictures. I guess a natural image has enough variation and noise to work without dithering most of the time. – Klenk

@Federation in the end I decided to use a different image than Lena. See my answer, I hope you find the sample convincing. – Klenk

Answer 1

As you mentioned, the Floyd-Steinberg dithering method is popular because it's simple and fast. For the subtle differences between 24-bit and 16-bit color the results will be nearly optimal visually.

It was suggested that I use the sample picture Lena but I decided against it; despite its long history as a test image I consider it too sexist for modern sensibilities. Instead I present a picture of my own. First up is the original, followed by the conversion to dithered RGB565 (and converted back to 24-bit for display).

And the code, in C++:

inline BYTE Clamp(int n)
{
    n = n>255 ? 255 : n;
    return n<0 ? 0 : n;
}

struct RGBTriplet
{
    int r;
    int g;
    int b;
    RGBTriplet(int _r = 0, int _g = 0, int _b = 0) : r(_r), g(_g), b(_b) {};
};

void RGB565Dithered(const BYTE * pIn, int width, int height, int strideIn, BYTE * pOut, int strideOut)
{
    std::vector<RGBTriplet> oldErrors(width + 2);
    for (int y = 0;  y < height;  ++y)
    {
        std::vector<RGBTriplet> newErrors(width + 2);
        RGBTriplet errorAhead;
        for (int x = 0;  x < width;  ++x)
        {
            int b = (int)(unsigned int)pIn[3*x] + (errorAhead.b + oldErrors[x+1].b) / 16;
            int g = (int)(unsigned int)pIn[3*x + 1] + (errorAhead.g + oldErrors[x+1].g) / 16;
            int r = (int)(unsigned int)pIn[3*x + 2] + (errorAhead.r + oldErrors[x+1].r) / 16;
            int bAfter = Clamp(b) >> 3;
            int gAfter = Clamp(g) >> 2;
            int rAfter = Clamp(r) >> 3;
            int pixel16 = (rAfter << 11) | (gAfter << 5) | bAfter;
            pOut[2*x] = (BYTE) pixel16;
            pOut[2*x + 1] = (BYTE) (pixel16 >> 8);
            int error = r - ((rAfter * 255) / 31);
            errorAhead.r = error * 7;
            newErrors[x].r += error * 3;
            newErrors[x+1].r += error * 5;
            newErrors[x+2].r = error * 1;
            error = g - ((gAfter * 255) / 63);
            errorAhead.g = error * 7;
            newErrors[x].g += error * 3;
            newErrors[x+1].g += error * 5;
            newErrors[x+2].g = error * 1;
            error = b - ((bAfter * 255) / 31);
            errorAhead.b = error * 7;
            newErrors[x].b += error * 3;
            newErrors[x+1].b += error * 5;
            newErrors[x+2].b = error * 1;
        }
        pIn += strideIn;
        pOut += strideOut;
        oldErrors.swap(newErrors);
    }
}

I won't guarantee this code is perfect, I already had to fix one of those subtle errors that I alluded to in another comment. However it did generate the results above. It takes 24-bit pixels in BGR order as used by Windows, and produces R5G6B5 16-bit pixels in little endian order.

Klenk

Answer 2

I suggested to used ordered dithering (http://en.wikipedia.org/wiki/Ordered_dithering), since Floyd-Steinberg need more processing and calculating and only works on still image / doesn't works well for animated or constant changed on display.

I Created my own optimized ordered dithering from 24/32bit RGB color to 16bit RGB565 color, that seperate tresshold into subpixel (Used in my AROMA project). It was way faster then Floyd-Steinberg, because there is no expensive calculations (specially no multiplies and divs calculations), and able to used on animations because it used fixed tresshold.

It's quality also so much better than ordered dithering algorithm that defined on wiki.

Here an example of dithering result:

And here the source. Enjoy!

/* Dither Tresshold for Red Channel */
static const BYTE dither_tresshold_r[64] = {
  1, 7, 3, 5, 0, 8, 2, 6,
  7, 1, 5, 3, 8, 0, 6, 2,
  3, 5, 0, 8, 2, 6, 1, 7,
  5, 3, 8, 0, 6, 2, 7, 1,

  0, 8, 2, 6, 1, 7, 3, 5,
  8, 0, 6, 2, 7, 1, 5, 3,
  2, 6, 1, 7, 3, 5, 0, 8,
  6, 2, 7, 1, 5, 3, 8, 0
};

/* Dither Tresshold for Green Channel */
static const BYTE dither_tresshold_g[64] = {
  1, 3, 2, 2, 3, 1, 2, 2,
  2, 2, 0, 4, 2, 2, 4, 0,
  3, 1, 2, 2, 1, 3, 2, 2,
  2, 2, 4, 0, 2, 2, 0, 4,

  1, 3, 2, 2, 3, 1, 2, 2,
  2, 2, 0, 4, 2, 2, 4, 0,
  3, 1, 2, 2, 1, 3, 2, 2,
  2, 2, 4, 0, 2, 2, 0, 4
};

/* Dither Tresshold for Blue Channel */
static const BYTE dither_tresshold_b[64] = {
  5, 3, 8, 0, 6, 2, 7, 1,
  3, 5, 0, 8, 2, 6, 1, 7,
  8, 0, 6, 2, 7, 1, 5, 3,
  0, 8, 2, 6, 1, 7, 3, 5,

  6, 2, 7, 1, 5, 3, 8, 0,
  2, 6, 1, 7, 3, 5, 0, 8,
  7, 1, 5, 3, 8, 0, 6, 2,
  1, 7, 3, 5, 0, 8, 2, 6
};

/* Get 16bit closest color */
BYTE closest_rb(BYTE c) { 
  return (c >> 3 << 3); /* red & blue */
}
BYTE closest_g(BYTE c) {
  return (c >> 2 << 2); /* green */
}

/* RGB565 */
WORD RGB16BIT(BYTE r, BYTE g, BYTE b) {
  return ((WORD)((r>>3)<<11)|((g>>2)<<5)|(b>>3));
}

/* Dithering by individual subpixel */
WORD dither_xy(
  int x, 
  int y, 
  BYTE r, 
  BYTE g, 
  BYTE b
){
  /* Get Tresshold Index */
  BYTE tresshold_id = ((y & 7) << 3) + (x & 7);

  r = closest_rb(
          MIN(r + dither_tresshold_r[tresshold_id], 0xff)
       );
  g = closest_g(
          MIN(g + dither_tresshold_g[tresshold_id], 0xff)
       );
  b = closest_rb(
          MIN(b + dither_tresshold_b[tresshold_id], 0xff)
       );
  return RGB16BIT(r, g, b);
}

/* Dithering Pixel from 32/24bit RGB 
 *
 * GetR, GetG, GetB -> Function to get individual color in pixel
 *
 */
WORD dither_color_xy(int x, int y, DWORD col) {
  return dither_xy(x, y, GetR(col), GetG(col), GetB(col));
}

/* EXAMPLES */
void ExampleDither1(WORD * dest, DWORD * src, int width, int height){
  int x, y;
  for (y=0; y<height; y++){
    for (x=0; x<width; x++){
      int pos = y * width + x;
      dest[pos] = dither_color_xy(x,y,src[pos]);
    }
  }
}
void ExampleDither2(WORD * dest, BYTE * src, int width, int height){
  int x, y;
  for (y=0; y<height; y++){
    for (x=0; x<width; x++){
      int pos = y * width + x;
      dest[pos] = dither_xy(x,y,src[pos*3],src[pos*3+1],src[pos*3+2]);
    }
  }
}

Another Result (Top 24bit - Bottom Ordered RGB565-16bit): View full resolution image

Metencephalon

Answer 3

Floyd–Steinberg dithering

for each y from top to bottom
   for each x from left to right
      oldpixel := pixel[x][y]
      newpixel := find_closest_palette_color(oldpixel)
      pixel[x][y] := newpixel
      quant_error := oldpixel - newpixel
      pixel[x+1][y] := pixel[x+1][y] + 7/16 * quant_error
      pixel[x-1][y+1] := pixel[x-1][y+1] + 3/16 * quant_error
      pixel[x][y+1] := pixel[x][y+1] + 5/16 * quant_error
      pixel[x+1][y+1] := pixel[x+1][y+1] + 1/16 * quant_error

I bet a buck you can implement this easily!

Dome

Yeah, I saw that algorithm on the wikipedia article as well. But, my gut tells me there may be more optimal RGB565 dithering algorithms out there (even if they aren't Floyd-Steinberg). This one seemed a bit expensive. If no one can come up with one, I'll mark this as an answer. – Haricot

This is an algorithm where it's easy to make subtle mistakes. @JacobJ, I'll try to get a C/C++ implementation for you tonight. – Klenk

@MarkRansom, Thanks! I'm trying my own implementation now, but I'd love to compare against what you come up with! I just noticed I'm actually going from a 32-bit ARGB buffer (UINT32*) to an RGB565 buffer (UINT16*). Those last 4-lines are what seem the most challenging. I need to bit-shift carefully. If you do this tonight, please post as an answer! ;-) – Haricot

I wonder if you need to be careful to do the calculations in linear RGB and then convert to sRGB at the end. Do you think it would make much difference? – Whitley

@AdrianMcCarthy, any calculations on RGB involving addition or subtraction will be most correct in a linear space, but I've found that working directly with sRGB is "close enough" in most cases. – Klenk

Answer 4

Here is my code that does ordered (Bayer) dithering with 16x16 matrix. It produces 15 bits per pixel output. Both input and output are 3 bytes per pixel. The output uses 32 values, scaled to range 0..255 for visualising purposes. You can easily change the output as you wish by replacing these 3 lines:

pixels[x * 3 + 0]   = i1 * 8;
pixels[x * 3 + 1]   = i2 * 8;
pixels[x * 3 + 2]   = i3 * 8;

The code is optimized for speed and can be used for realtime processing.

The left picture is the original and the right is dithered.

Here is the code:

#ifndef MIN
#define MIN(a,b)            (((a) < (b)) ? (a) : (b))
#endif

#ifndef MAX
#define MAX(a,b)            (((a) > (b)) ? (a) : (b))
#endif

#ifndef CLAMP
//  This produces faster code without jumps
#define     CLAMP( x, xmin, xmax )      (x) = MAX( (xmin), (x) );   \
                                        (x) = MIN( (xmax), (x) )
#endif

const   int BAYER_PATTERN_16X16[16][16] =   {   //  16x16 Bayer Dithering Matrix.  Color levels: 256
                                                {     0, 191,  48, 239,  12, 203,  60, 251,   3, 194,  51, 242,  15, 206,  63, 254  }, 
                                                {   127,  64, 175, 112, 139,  76, 187, 124, 130,  67, 178, 115, 142,  79, 190, 127  },
                                                {    32, 223,  16, 207,  44, 235,  28, 219,  35, 226,  19, 210,  47, 238,  31, 222  },
                                                {   159,  96, 143,  80, 171, 108, 155,  92, 162,  99, 146,  83, 174, 111, 158,  95  },
                                                {     8, 199,  56, 247,   4, 195,  52, 243,  11, 202,  59, 250,   7, 198,  55, 246  },
                                                {   135,  72, 183, 120, 131,  68, 179, 116, 138,  75, 186, 123, 134,  71, 182, 119  },
                                                {    40, 231,  24, 215,  36, 227,  20, 211,  43, 234,  27, 218,  39, 230,  23, 214  },
                                                {   167, 104, 151,  88, 163, 100, 147,  84, 170, 107, 154,  91, 166, 103, 150,  87  },
                                                {     2, 193,  50, 241,  14, 205,  62, 253,   1, 192,  49, 240,  13, 204,  61, 252  },
                                                {   129,  66, 177, 114, 141,  78, 189, 126, 128,  65, 176, 113, 140,  77, 188, 125  },
                                                {    34, 225,  18, 209,  46, 237,  30, 221,  33, 224,  17, 208,  45, 236,  29, 220  },
                                                {   161,  98, 145,  82, 173, 110, 157,  94, 160,  97, 144,  81, 172, 109, 156,  93  },
                                                {    10, 201,  58, 249,   6, 197,  54, 245,   9, 200,  57, 248,   5, 196,  53, 244  },
                                                {   137,  74, 185, 122, 133,  70, 181, 118, 136,  73, 184, 121, 132,  69, 180, 117  },
                                                {    42, 233,  26, 217,  38, 229,  22, 213,  41, 232,  25, 216,  37, 228,  21, 212  },
                                                {   169, 106, 153,  90, 165, 102, 149,  86, 168, 105, 152,  89, 164, 101, 148,  85  }
                                            };

//  Color ordered dither using 15 bits per pixel (5 bit per color plane)
void    makeDitherBayerRgb15bpp( BYTE* pixels, int width, int height )  noexcept
{
    for( int y = 0; y < height; y++ )
    {
        int row = y & 15;   //  y % 16
        
        for( int x = 0; x < width; x++ )
        {
            int col = x & 15;   //  x % 16

            const int   t       = BAYER_PATTERN_16X16[col][row];
            const int   corr    = (t / 31);

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

            int i1  = (blue  + corr) / 8;       CLAMP( i1, 0, 31 );
            int i2  = (green + corr) / 8;       CLAMP( i2, 0, 31 );
            int i3  = (red   + corr) / 8;       CLAMP( i3, 0, 31 );

            pixels[x * 3 + 0]   = i1 * 8;   // Scale blue  back to 0..255
            pixels[x * 3 + 1]   = i2 * 8;   // Scale green back to 0..255
            pixels[x * 3 + 2]   = i3 * 8;   // Scale red   back to 0..255
        }

        pixels  += width * 3;
    }
}

You can check this article for more dithering algorythms:

Dithering implementations and demo

Bibber