dithSerp palette issue

[jerch]

If dithSerp is set to true it seems to introduce colors that are not in the palette for small palettes, repro:

const createCanvas = require('canvas');
const canvas = createCanvas(204, 204);
const ctx = canvas.getContext('2d');
ctx.fillStyle = 'white';
ctx.fillRect(0, 0, canvas.width, canvas.height);

ctx.font = '30px Impact';
ctx.rotate(0.1);
ctx.fillStyle = 'black';
ctx.fillText('Awesome!', 50, 100);

// quantitize
const RgbQuant = require('rgbquant');
const q = new RgbQuant({colors: 16, dithKern: 'FloydSteinberg', dithSerp: true});
q.sample(canvas);
const pal = q.palette(true);
const out = q.reduce(canvas);

The palette now contains:

[ [ 0, 0, 0 ],
  [ 17, 17, 17 ],
  [ 27, 27, 27 ],
  [ 38, 38, 38 ],
  [ 54, 54, 54 ],
  [ 75, 75, 75 ],
  [ 86, 86, 86 ],
  [ 103, 103, 103 ],
  [ 126, 126, 126 ],
  [ 137, 137, 137 ],
  [ 154, 154, 154 ],
  [ 169, 169, 169 ],
  [ 194, 194, 194 ],
  [ 218, 218, 218 ],
  [ 231, 231, 231 ],
  [ 255, 255, 255 ] ]

the colors of out are (unordered):

[ [ 255, 255, 255, 255 ],
  [ 231, 231, 231, 255 ],
  [ 0, 0, 0, 255 ],
  [ 17, 17, 17, 255 ],
  [ 38, 38, 38, 255 ],
  [ 54, 54, 54, 255 ],
  [ 86, 86, 86, 255 ],
  [ 103, 103, 103, 255 ],
  [ 137, 137, 137, 255 ],
  [ 169, 169, 169, 255 ],
  [ 194, 194, 194, 255 ],
  [ 126, 126, 126, 255 ],
  [ 218, 218, 218, 255 ],
  [ 75, 75, 75, 255 ],
  [ 154, 154, 154, 255 ],
  [ 27, 27, 27, 255 ],
  [ 253, 253, 253, 255 ] ]

The last entry is not in the palette. If you add more colors or gradients to the original image, more spurious colors will pop up. Is this a missing/misplaced nearest color matching in reduce?

[leeoniya]

honestly, i think dithSerp is not implemented correctly to begin with. it's supposed to give better results, but instead looks worse. try the pool table image [1] at 16 colors with Floyd and then with Floyd + dithSerp.

the original dithering code was adapted from here [2] and even there, there's a comment questioning whether the hz kernel offsets should be reversed or not. it made sense to me to do this because the idea of error diffusion is never to spread the error to already processed pixels and if you're alternating the scan direction without reflecting the kernel horizontally, you're doing exactly that.

i think the dithering code in general needs a careful review, which i never really did given that the results looked subjectively correct.

[1] http://leeoniya.github.io/RgbQuant.js/demo/
[2] https://github.com/leeoniya/RgbQuant.js/blob/master/src/rgbquant.js#L140

[jerch]

@leeoniya Well I was planning to use your library as an easy to go dropin for my SIXEL encoding (https://github.com/jerch/node-sixel, currently only the decoder is implemented). SIXEL is bound to 16 or 256 palettes, thus the need for a quantization/dithering step. I dont want to deal with that on my own, advanced image processing is beyond the scope of the SIXEL lib.

So what do you suggest? Disabling the serpentine for now? Still works good enough for my purpose (well mostly), disabling whole dithering though is not an option as it produces to many artefacts.

[leeoniya]

if you need to use it today, i would avoid using dithSerp until the code has been reviewed. i'm pretty busy right now, so it could be a week or two before i can dive into it.

if you have any spare cycles and want to try reviewing the dithering loop yourself, go ahead. it's not super complicated, just needs to be carefully reviewed. you can use these as references: [1] [2].

the meat of the dither step is just 70 lines: https://github.com/leeoniya/RgbQuant.js/blob/master/src/rgbquant.js#L241-L310

[1] http://www.tannerhelland.com/4660/dithering-eleven-algorithms-source-code/
[2] https://en.wikipedia.org/wiki/Floyd–Steinberg_dithering

[jerch]

@leeoniya Will see if I find some time to look into it.

For now I do a second ED calculation to get rid of the suprious colors. You can already test this in a SIXEL capable terminal (like xterm started with xterm -ti vt340) by running img2sixel.js like this:

node img2sixel.js -p16 http://leeoniya.github.io/RgbQuant.js/demo/img/bluff.jpg

😸

[makew0rld]

it made sense to me to do this because the idea of error diffusion is never to spread the error to already processed pixels and if you're alternating the scan direction without reflecting the kernel horizontally, you're doing exactly that.

@leeoniya So the kernel should be reflected for serpentine dither, every time you go in reverse right? I'm implementing my own dithering library and I can't find any information on this. I know you're having trouble here, did you figure it out? In any case I can't see how not reflecting it would be a good idea.

[leeoniya]

yes, i think so. you can see that all the kernels are arranged with nothing to north or west of X, which would imply eastwards and southwards iteration. if you're reversing along x, then the kernel needs to be x-reflected.

https://hbfs.wordpress.com/2013/12/31/dithering/

[makew0rld]

Ok, thanks! And that's a helpful link.

Here, I just implemented serpentine dithering. Can't be 100% sure I'm doing it right, but I think I am.

Simple 2D matrix regular:

Simple 2D matrix serpentine:

Make sure to view these images at 100% size. The serpentine definitely looks smoother.

Not sure if that helps anything, but it might be useful as a reference for creating a black and white gradient test case.

[leeoniya]

nice :)

[leeoniya]

it does feel like serpentine may not provide the best "improvement" since it's pretty directional. you may want to look into Riemersma Dither, particularly one that follows a Hilbert space-filling curve. this might give you less directional dithering.

https://www.compuphase.com/riemer.htm
https://www.compuphase.com/hilbert.htm

i think igor implemented this in his RgbQuant offshoot: https://github.com/ibezkrovnyi/image-quantization

also, here is way too much additional dithering info: https://bisqwit.iki.fi/story/howto/dither/jy/

[makew0rld]

Yep, I'm aware of those methods and plan on implementing them later. I just also wanted to have serpentine available.