Show HN: An attempt to make a reduce-palette/dither filter for 2d canvas images | Hacker News Reader

Show HN: An attempt to make a reduce-palette/dither filter for 2d canvas images

scrawl-v8.rikweb.org.uk

21 pointsrikroots12 comments

The performance is worse than I would expect with a correctly implemented Floyd-Steinberg algorithm, I'd expect it to rasterize well even with a 2 color palette (that's easier to get right than RGB).

I don't at all mean to diminish the work, it's more a hunch that it's under-performing. I was dicking around with dithering last year, and had similar problems initially.

Thanks for checking the demo out. The code[1] is very much a work-in-progress - suggestions for algorithm improvements (they're not based on Floyd-Steinberg) are always welcome!

[1] - https://github.com/KaliedaRik/Scrawl-canvas/blob/master/sour...

One fast way to do palette reduction is by using a 16-bit RGB565 lookup table filled with all the closest colors relative to each entry index, then you can replace each pixel in the image using just a few bitwise ops and one array access.

That's an interesting approach!

I went a different way, converting each pixel to its LAB color space values to find the optimal palette for the image (based on preference arguments), then afterwards measuring each pixel against the palette colors to find the two closest colors before deciding which of those two colors to pick based on a distance propensity weighting against the semi-random number assigned to that pixel.

Coming up with highly efficient algorithms (for anything!) is not my strongest skill. Neither is trying to explain them.

The best palette-reducing algorithm I know is the one by Xiaolin Wu: https://www.ece.mcmaster.ca/~xwu/cq.c

That particular implementation is less than ideal. It has issues with correctness (the precision of FP32 accumulators was not enough for my use cases, needed an upgrade to FP64), performance (no SIMD), and subjective code quality (I tend to avoid global variables for things like that).

But the algorithm itself is awesome.

Could this be done in a opengl shader? That way it could be run on the GPU and improve performance a lot.

Shadertoy has [1] a dithering example that runs at 60fps, might be the same effect you have though

[1] https://www.shadertoy.com/view/NdsyD7

Nice work!

> Note that this is a resource-intensive filter. Memoization is strongly advised!

Can you make this be the default for non Safari browsers? This really made my CPU fan work hard. Also, why does this need to recalculate the image so many times a second if it is the same image each time? It really only needs to redraw when I change one of the options.

Thank you!

The demo is a part of the testing regime for my canvas library. I set the default to "don't memoize" because it's the quickest way to see how intense/computationally expensive the filter gets using different parameters. For most scenarios the output should be memoized (to stop unresponsive websites, device damage, etc)

My ultimate goal would be to get the filter working more efficiently on dynamic input eg a video media stream. So far only the simplest settings (2 colours with dither) are watchable: https://codepen.io/kaliedarik/pen/OJOaOZz

I remember when blue noise was the shit back in the 90's. And wow, what a difference it makes when you enable it.

can you say more about that?

I was on the graphics team and the tech lead (an engineer named Tom Dowdy) went off to SIGGRAPH one year and came back to the office stoked about blue noise. He said we ought to implement it in our dithering algorithm — which I believe he promptly did (guessing QuickTime).

Turning on/off Blue Noise in the OP's demo makes clear to me how good it was.

https://en.wikipedia.org/wiki/Dither#Digital_photography_and...

rest in pieces Tom -- honestly between you and me, he was popular and successful and then he passed away in an untimely way; makes one pause about this profession, and how the roads of success are paved by the bodies of the fallen

Reply on news.ycombinator.com