Is this a correct implementation of ordered dithering?

Question

I am interested in dithering, ordered dithering to be more precise. I spent many hours on researching and experimenting. And hope that after all the effort my code works as it should.

I am going to provide my code that does the dithering, and some examples.

My questions

• How does it work?
• Is my code correct?
• Could there be any simplifications?

---

Here is the pseudo code for the dithering algorithm from this Wikipedia article, on which my code is based on.

And here are the variable explanations:

M(i, j) is the threshold map on the i-th row and j-th column, c′ is the transformed color, and r is the amount of spread in color space. Assuming an RGB palette with N³ evenly chosen colors where each color coordinate is represented by an octet, one would typically choose:

---

Now, here is my implementation (in pseudo code):

ditherMatrix = 4x4; // By 4x4 I mean the normal 4x4 dither matrix from the wikipedia article
ditherMatrixSize = 4;
offset = (ditherMatrixSize * (ditherMatrixSize / 2) - 0.5); 
/* In the wiki article it uses 0.5 as an offset, 
   but I have to do this instead. 
   Is this correct? Atleast it works. */

allowedChanelValues = 1; // example: 2 = (0 or 128 or 255 red, 0 or 128 or 255 green, 0 or 128 or 255 blue)
r = 255 / allowedChanelValues / (ditherMatrixSize * ditherMatrixSize);

// Applying the dither
transfromedColor.r = 
    currentPixel.r + r * ((ditherMatrix[x % ditherMatrixSize, y % ditherMatrixSize]) - offset);
transfromedColor.g = 
    currentPixel.g + r * ((ditherMatrix[x % ditherMatrixSize, y % ditherMatrixSize]) - offset);
transfromedColor.g = 
    currentPixel.g + r * ((ditherMatrix[x % ditherMatrixSize, y % ditherMatrixSize]) - offset);

// Quantizing, see https://youtu.be/0L2n8Tg2FwI 6:40 and 9:58 for explanation
transfromedColor.r = Round(allowedChanelValues * oldR / 255) * (255 / allowedChanelValues);
transfromedColor.g = Round(allowedChanelValues * oldG / 255) * (255 / allowedChanelValues);
transfromedColor.b = Round(allowedChanelValues * oldB / 255) * (255 / allowedChanelValues);

IMPORTANT: Now, this code could be optimized in many ways, but that's not my intention (for now) I just want it to work correctly, and then I'll look at what could be optimized.

SIDE NOTE: When I was just starting out I was hardcoding the values, for example, instead of ditherMatrixSize * (ditherMatrixSize / 2) - 0.5, I was hardcoding 7.5. But after trying other dither matrices I just used this code to get the value instead of hardcoding it.

---

Here are some examples

(Top - Dithered, Bottom - Original. The matrix is 4x4 and allowedChanelValues is 1)

---

(Left - Dithered, Right- Original. The matrix is 4x4 and allowedChanelValues is 1)

---

I talked earlier about if it was possible to simplify the code.

I found this pseudo code here

  Threshold = COLOR(256/4, 256/4, 256/4); /* Estimated precision of the palette */
  For each pixel, Input, in the original picture:
    Factor  = ThresholdMatrix[xcoordinate % X][ycoordinate % Y];
    Attempt = Input + Factor * Threshold
    Color = FindClosestColorFrom(Palette, Attempt)
    Draw pixel using Color

In order to implement this, I have to normalize the matrix so it ranges from 0 to 1. And this is how I implement it:

factor = 1;
offset = (ditherMatrixSize * (ditherMatrixSize / 2) - 0.5d) / (ditherMatrixSize * ditherMatrixSize); 
// This time the offset is a bit different because I normalized the matrix
r = 256 / factor; // r is the same as the Threshold

transformedPixelColor.R = 
   currentPixel.R + r * (ditherMatrix[(x) % ditherMatrixSize, (y) % ditherMatrixSize] - offset)
transformedPixelColor.G = 
   currentPixel.G + r * (ditherMatrix[(x) % ditherMatrixSize, (y) % ditherMatrixSize] - offset)
transformedPixelColor.B = 
   currentPixel.B + r * (ditherMatrix[(x) % ditherMatrixSize, (y) % ditherMatrixSize] - offset)

This works the same as the other one. I even found a third way to dither, but it's more complicated and dithers the same way as these two, so I won't cover it.

So what do you think? Is the algorithm working corectly?

Thank you in advance!

Answer 1

It does NOT look correct. Somewhere in the computations an error is accumulated.

Ordered dithering does not need float-point arythmetic. It can be achieved in purely integer computations.

Also it is good to pre-calculate the values in the matrix.

Here is a code in C that performs 3bpp ordered diter (Bayer) with matrix 16x16 for best result.

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 3 bits per pixel (1 bit per color plane)
void    makeDitherBayerRgb3bpp( 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

            pixels[x * 3 + 0]   = (pixels[x * 3 + 0] > BAYER_PATTERN_16X16[col][row] ? 255 : 0);
            pixels[x * 3 + 1]   = (pixels[x * 3 + 1] > BAYER_PATTERN_16X16[col][row] ? 255 : 0);
            pixels[x * 3 + 2]   = (pixels[x * 3 + 2] > BAYER_PATTERN_16X16[col][row] ? 255 : 0);
        }

        pixels  += width * 3;
    }
}

Here is the result of this implementation:

For more algorythms, source code and demo for dithering you can look here