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

https://scrawl-v8.rikweb.org.uk/demo/filters-027.html

by rikroots • 4 years ago

21 12 4 years ago

scrawl-v8.rikweb.org.uk

hx2a• 4 years ago

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.

rikroots3• 4 years ago

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

JKCalhoun2• 4 years ago

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

mistrial92• 4 years ago

can you say more about that?

JKCalhoun2• 4 years ago

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...

marginalia_nu• 4 years ago

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.

rikroots3• 4 years ago

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...

dubiousconst281• 4 years ago

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.

gitgud• 4 years ago

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

Const-me• 4 years ago

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.

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

Related Stories