Fastest dithering / halftoning library in C

Question

I'm developing a custom thin-client server that serves rendered webpages to its clients. Server is running on multicore Linux box, with Webkit providing the html rendering engine.

The only problem is the fact that clients display is limited with a 4bit (16 colors) grayscale palette. I'm currently using LibGraphicsMagick to dither images (RGB->4bit grayscale), which is an apparent bottleneck in the server performance. Profiling shows that more than 70% of time is spent running GraphicsMagick dithering functions.

I've explored stackoverflow and the Interwebs for a good high performance solution, but it seems that nobody did any benchmarks on various image manipulation libraries and dithering solutions.

I would be more that happy to find out:

2. What are the highest performance libraries in regards to dithering / halftoning / quantizing RGB images to 4bit grayscale.
3. Are there any specilized dithering libs or any public domain code snippets that you could point me to?
4. What libraries do you prefer for manipulating graphics in regards to high performance?

C language libraries are prefered.

Margret

Answer 1

Dithering is going to take quite a bit of time depending on the algorithm chosen.

It's fairly trivial to implement Bayer (Matrix) and Floyd-Steinberg (Diffusion) dithering.

Bayer filtering can be made extremely fast when coded with with MMX/SSE to process parallel pixels. You may also be able to do the dithering / conversion using a GPU shader.

FWIW, you're already using GraphicsMagick but there's an entire list of OSS graphics libraries here

Dillard

Thanks for the huge list, I just wish there were some benchmarks out there already. – Margret

@Jamie: Edited links - old link (scien.stanford.edu/class/psych221/projects/02/mdeleon/…) wasn't working. – Dillard

Answer 2

From the list provided by Adisak, without any testing, I would bet on AfterImage. The Afterstep people are obsessed with speed, and also described a clever algorithm.

You could take an alternative approach, if your server could be equipped with a decent PCI-express graphics card featuring OpenGL. Here are some specs from Nvidia. Search for "index mode". What you could do is select a 16 or 256 color display mode, render your image as a texture on a flat polygon (like the side of cube) and then read the frame back.

When reading a frame from an OpenGL card, it is important that bandwidth is good from the card, hence the need for PCI-express. As the documentation says, you also have to choose your colors in indexed mode for decent effects.

Allan

@Spike0xff, actually, it is not even necessary for it to be general purpose GPU (programmable), it's enough with anything that works with OpenGL or DirectX. – Allan

Answer 3

Here is the solution you are looking for. This is a C function that performs Ordered Dither (Bayer) with a parameter for colors. It is fast enough to be used in realtime processing.

#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) )
#define     CLAMPED( x, xmin, xmax )    MAX( (xmin), 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  }
                                            };

//  This is the ultimate method for Bayer Ordered Diher with 16x16 matrix
//  ncolors - number of colors diapazons to use. Valid values 0..255, but interesed are 0..40
//  1       - color (1 bit per color plane,  3 bits per pixel)
//  3       - color (2 bit per color plane,  6 bits per pixel)
//  7       - color (3 bit per color plane,  9 bits per pixel)
//  15      - color (4 bit per color plane, 12 bits per pixel)
//  31      - color (5 bit per color plane, 15 bits per pixel)
void    makeDitherBayerRgbNbpp( BYTE* pixels, int width, int height, int ncolors )  noexcept
{
    int divider = 256 / ncolors;

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

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

            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) / divider; CLAMP( i1, 0, ncolors );
            int i2  = (green + corr) / divider; CLAMP( i2, 0, ncolors );
            int i3  = (red   + corr) / divider; CLAMP( i3, 0, ncolors );

            //  If you want to compress the image, use the values of i1,i2,i3
            //  they have values in the range 0..ncolors
            //  So if the ncolors is 4 - you have values: 0,1,2,3 which is encoded in 2 bits
            //  2 bits for 3 planes == 6 bits per pixel

            pixels[x * 3 + 0]   = CLAMPED( i1 * divider, 0, 255 );  //  blue
            pixels[x * 3 + 1]   = CLAMPED( i2 * divider, 0, 255 );  //  green
            pixels[x * 3 + 2]   = CLAMPED( i3 * divider, 0, 255 );  //  red
        }

        pixels  += width * 3;
    }
}

In your case, you need to call the function with parameter ncolors=4 This means that each color plane (for grayscale it is 1 plane) will use 4 bits per pixel.

So, you have to call:

makeDitherBayerRgbNbpp( pixels, width, height, 4 );

The input pixels are in BGR format. The output pixels are also in BGR format for visualisation purposes. To obtain the bits, you have to replace this code:

pixels[x * 3 + 0]   = CLAMPED( i1 * divider, 0, 255 );  //  blue
pixels[x * 3 + 1]   = CLAMPED( i2 * divider, 0, 255 );  //  green
pixels[x * 3 + 2]   = CLAMPED( i3 * divider, 0, 255 );  //  red

With something like this:

out.writeBit( i1 ); // blue
out.writeBit( i2 ); // green
out.writeBit( i3 ); // red

Here is a sample picture with your parameters (4bit grayscale)

For more dithering source code and demo app, you can see here

Adobe

Answer 4

I know it's not a C library, but this got me curious about what's available for .NET to do error-diffusion which I used some 20 years ago on a project. I found this and specifically this method.

But to try be helpful :) I found this C library.

Albur

'C Library' link is currently broken. – Microgroove

Answer 5

Here is an implementation of the Floyd-Steinberg method for half-toning:

#include <opencv2/opencv.hpp>

using namespace cv;

int main(){

uchar scale = 128; // change this parameter to 8, 32, 64, 128 to change the dot size
Mat img = imread("../halftone/tom.jpg", CV_LOAD_IMAGE_GRAYSCALE);
for (int r=1; r<img.rows-1; r++) {
    for (int c=1; c<img.cols-1; c++) {
        uchar oldPixel = img.at<uchar>(r,c);
        uchar newPixel = oldPixel / scale * scale;
        img.at<uchar>(r,c) = newPixel;
        int quantError = oldPixel - newPixel;
        img.at<uchar>(r+1,c)   +=  7./16. * quantError;
        img.at<uchar>(r-1,c+1) +=  3./16. * quantError;
        img.at<uchar>(r,c+1) +=  5./16. * quantError;
        img.at<uchar>(r+1,c+1) +=  1./16. * quantError;
    }
}
imshow("halftone", img);
waitKey();
}

Trochlear