Built-in dithering for 6COLOR does not correctly handle colors adjacent to blue (0x0000FF)

[TheHans255]

Whenever I attempt to read a 24-bit BMP, JPG, or PNG file from an SD card, the resulting image renders on my 6COLOR, but with cyan (0x00ffff) and magenta (0xff00ff) dithering as white, and other colors in between those and blue failing to dither.

Here is the image as it is meant to display:

And here is the image as it actually appears on my board:

Displaying as a BMP gives the same results as the PNG:

Function used to display images:

bool displayImage(SdFile *file) {
  int16_t byte1 = file->read();
  int16_t byte2 = file->read();
  file->rewind();
  bool result;
  if (byte1 == 0x42 && byte2 == 0x4d) {
    // it's a bitmap
    result = display.drawBitmapFromSd(file, 0, 0, 1, 0);
  } else if (byte1 == 0xff && byte2 == 0xd8) {
    // it's a JPEG
    result = display.drawJpegFromSd(file, 0, 0, 1, 0);
  } else if (byte1 == 0x89 && byte2 == 0x50) {
    // it's a PNG
    result = display.drawPngFromSd(file, 0, 0, 1, 0);
  }
  if (!result) {
    display.print("Cannot display ");
    printlnFilename(file);
    return 0;
  }
  display.display();
  return 1;
}

[TheHans255]

Looking at the code, I suspect the issue is in the findClosestPalette function:

uint8_t Image::findClosestPalette(uint32_t c)
{
    int mi = 0;
    for (int i = 1; i < sizeof pallete / sizeof pallete[0]; ++i)
    {
        if (COLORDISTSQR(c, pallete[i]) < COLORDISTSQR(c, pallete[mi]))
            mi = i;
    }

    return mi;
}

Cyan and magenta are both equidistant from three different colors in the palette - cyan is equidistant from white, blue, and green; while magenta is equidistant from white, blue, and red. White is chosen for both of them since it's is the first color in the palette for each, but the three colors should all really be chosen about evenly.

We could probably pull this off by passing a "bias" value into findClosestPalette to help it break ties. Ideally this would be a pseudorandom number, but we could probably get away with the X coordinate of the image and/or some sort of running checksum.

[TheHans255]

Upon further inspection, the root cause of this issue is actually because the resolution of the ditherBuffer is too low:

https://github.com/SolderedElectronics/Inkplate-Arduino-library/blob/master/src/include/Image.h#L133C50-L133C50

#if defined(ARDUINO_INKPLATECOLOR) || defined(ARDUINO_INKPLATE4) || defined(ARDUINO_INKPLATE7)
    int8_t ditherBuffer[3][16][E_INK_WIDTH + 20];
    // ....

If the error is off by a full color channel (as is the case for cyan and magenta), the resulting error adjustment for the next pixel covers over half the range (7/16ths) of the buffer pixel. A second such error like this, which would be likely to occur with this bias towards white, would overflow the buffer pixel and actually bring the error towards the overestimating color, further biasing towards white. When I implemented the random tiebreaker in findClosestPalette, this overflow instead manifested as patchy blobs of the multiple colors being chosen.

Increasing the element size of ditherBuffer to int16_t fixed this issue, and I also found better dithering performance by refactoring findClosestPalette to handle color values below 0 or above 255 (in order to avoid clamping the error values until the last possible moment, and thus allow larger opposite error values to correctly cancel each other out). I have a branch that does this (https://github.com/TheHans255/Inkplate-Arduino-library/tree/thehans255/increase-dithering-resolution), but also makes a few other adjustments specific to my project (such as defaulting to the Atkinson kernel), which I will rein back before submitting a PR.

[rsoric]

Hi @TheHans255

Good stuff, thank you for your detailed insight and a quickly proposed solution, you're welcome to do any adjustments and we'll take a look at your PR, which will likely be included in a new main release of the library with some fixes we have for the Inkplate6COLOR which we have in the pipeline for this week.

We're also going to try and replicate this issue on our own boards because we haven't noticed this issue with dithering.

-Rob

[TheHans255]

I've prepared my PR for this solution: https://github.com/SolderedElectronics/Inkplate-Arduino-library/pull/230

[rsoric]

Hi @TheHans255 , I've looked at your PR and tested it. Just to compare, this is a software-dithered image using software which we use on our desktops to review how a dithered image should look like on Inkplate with a fixed color palette (0x000000, 0xFFFFFF, 0x00FF00, 0x0000FF, 0xFF0000, 0xFFFF00, 0xFF8000) :

Here we can see magenta being represented as white and cyan nonexistant- just going from green to blue when the threshold is over 50% as to which color it mainly represents.

Here are the results of our tests of your branch:

.png

.jpg

Reading through your notes and code, I understand your methodology and what you were trying to do, this does resolve the issue partially, but during this moment I'd like to leave more time for testing and possibly improving the dithering algorithm, as, in my opinion, the defaulting-to-white at cyan and magenta, while not accurate, looks a bit better and maybe useable for images in a practical sense.

I will leave this issue open until there is more time for testing and improving the dithering algorithm, as we're currently finishing some deadlines before the holidays :)

Thanks once again for providing a great PR an an improvement to the Inkplate library, we'll continue from here when we're able to to make the algorithm fully correct.

[TheHans255]

Oh my goodness, that looks horrible. My apologies, I did not fully test the changes before submitting them as a PR - I bought and programmed the Inkplate as a gift for someone else.

Those blotches look like what happened originally when the dither buffer would overflow, and I do recall seeing some effects like this when I made the fixed-point decimal change, to which I responded by further increasing the buffer resolution to int32_t. I'll submit a revision that also removes the fixed-point decimal changes.

[rsoric]

No worries!

Testing new code on Inkplate is fairly quick to do so when you make the new changes, feel free to let me know and I'll try it out, if it tests OK I can merge your PR if you can get it to look like the first picture in my last comment, that's what we're aiming for, and as I've said, we'll happily do the rest of this ourselves as you pointed out the issue for us, it's just going to have to wait after the holidays.

[TheHans255]

I removed the fixed-point changes and also brought back the color clamping before calling findClosestPalette. Can we see if this improves the image?

[rsoric]

Just tested it!

It's looking pretty great like this, great work.

[rsoric]

This looks even better than the official dithering software, just showed my team and they're quite happy with it. We'll be testing it with some more images and likely merge your PR tomorrow during our working hours.

Thanks again! Great code contributions like this help make our products even better.

[TheHans255]

You're welcome! And thank you for your help.

Is your dithering software open source? Maybe I could take a crack at that too.

[rsoric]

Merged your PR this morning!

The dithering software we use to test is external from us and just a helper tool of sorts, we didn't write it.

Here are some test results of your improved dithering algorithm:

Would you mind if we posted about this improvement to our library on our social media, in the context of 'why open-source is awesome'?

[TheHans255]

I wouldn't mind at all!