Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Image Dithering: Eleven Algorithms and Source Code

tannerhelland.com

Post reply on HN
Print view View original

41–50 of 65 posts

Re: Image Dithering: Eleven Algorithms and Source Code

#41

Post by gruturo »

joosters wrote: post #34

Has anyone tried using the equivalent of animated GIFs to help with dithering? If you have a limited palette of colours, perhaps you could produce two dithered versions, with pixels sometimes having different colours in alternate frames. If the image is refreshed fast enough, two colours could blend into a third. The most extreme example could be 'dithering' a grey square into 1) a black square and 2) a white square,…

Yep - (cheap) monitor manufactures do it quite effectively. Many LCDs have less than 8bit per color and do exactly what you suggested.

Re: Image Dithering: Eleven Algorithms and Source Code

#42

Post by zero_iq »

joosters wrote: post #34

Has anyone tried using the equivalent of animated GIFs to help with dithering? If you have a limited palette of colours, perhaps you could produce two dithered versions, with pixels sometimes having different colours in alternate frames. If the image is refreshed fast enough, two colours could blend into a third. The most extreme example could be 'dithering' a grey square into 1) a black square and 2) a white square,…

This was especially common on 8-bit and 16-bit computers to fake 'high colour' displays on machines that had only limited colour capability. They often took advantage of the fact that people were using their machines with TVs with relatively slow-changing phoshor screens, so the flicker was less evident than on a modern monitor.

e.g. Photochrome on the Atari ST, was especially impressive at the time: https://www.youtube.com/watch?v=vPsY4P8bnVw

The most extreme version I've seen of this was on the ZX Spectrum, which had not only a very limited 15 colour palette, but also limited to 2 colours within each 8x8 block of the screen. Some bright spark came up with the idea of flipping rapidly between R, G, and B frames to give (limited) per-pixel RGB. Unfortunately it did flicker quite badly because of the extreme changes in colour levels (only two levels of each channel), and the fact that it required 3 whole frames to make a single colour virtual frame.

Example here: (not suitable if you have photosenstive epilepsy!) https://en.wikipedia.org/wiki/File:Parrot_rgb3.gif

Re: Image Dithering: Eleven Algorithms and Source Code

#43

Post by DonHopkins »

the8472 wrote: post #35

The article doesn't mention the void and cluster[0][1] ordered dithering (and modernized variants) which have the advantage of ordered dithering that they are highly parallelization, e.g. via GPU shaders but do not leave the easily spottable patterns of ordered dithering. For example the madVR[2] video renderer uses it for realtime video dithering to avoid banding shallow color gradients from 10bit sources or debande…

One technique I've experimented with is iteratively diffusing errors not just towards un-visited neighbors below and to the right, but also into the future. We are all interested in the future, for that is where you and I are going to spend the rest of our lives. [1]

It works nicely with video, and it makes still images (and images you're slowly panning and zooming with the Ken Burns effect [2]) look alive and detailed, as if they were live video.

Another variation of the serpentine scanning (aka boustrophedon transform [3]) you can apply when iteratively dithering an image is to rotate the scan direction 90 degrees each frame, so even frames scan horizontally, odd frames scan vertically, and the vertical and horizontal scan directions rotate round every four frames. That results in a completely uniform diffusion, even when each scan frame only diffuses errors to the next cell.

It spreads the error out over time, as well as space, which has a pleasing effect on the eyes, I think. Any one frame has artifacts, but they tend to cancel each other out over time, break up the log jams, and dance around local minima and without getting stuck at fixed points.

I've implemented some 8 bit anisotropic heat diffusion cellular automata, that exhibited a subtle drift because of the scan order. But rotating the scan order 90 degrees each frame completely eliminated the subtle drifting effect I was getting when using a fixed scan order. Here's a discussion about it I had with Rudy Rucker [4] who inspired some of the rules and pointed out the problem, and a demo [5], and source [6].

Here's one of my favorite spooky Heizenbugs:

>The original version of this code written in C running on a Sun did have an interesting bug: I was not initializing the "error" accumulator that carried the leftover of the average from cell to cell, so when different kinds of background activities were happening on the Sun, the error accumulator got initialized from the stack frame with a random undefined value! I noticed it when every time I typed to a terminal window, the dithering shivered! It was really spooky until I figured out what was going on!

[1] https://www.youtube.com/watch?v=jb6H14gVWjM

[2] https://en.wikipedia.org/wiki/Ken_Burns_effect

[3] https://en.wikipedia.org/wiki/Boustrophedon_transform

[4] http://donhopkins.com/mediawiki/index.php/CAM6_Simulator

[5] https://github.com/SimHacker/CAM6/blob/master/javascript/CAM...

Re: Image Dithering: Eleven Algorithms and Source Code

#44

Post by c3534l »

the8472 wrote: post #35

The article doesn't mention the void and cluster[0][1] ordered dithering (and modernized variants) which have the advantage of ordered dithering that they are highly parallelization, e.g. via GPU shaders but do not leave the easily spottable patterns of ordered dithering. For example the madVR[2] video renderer uses it for realtime video dithering to avoid banding shallow color gradients from 10bit sources or debande…

I find it amusing that someone would have a dedicated GPU, yet cannot fully render color images. I mean, I'm sure there's actually plenty of use-cases, but it's still funny.

Re: Image Dithering: Eleven Algorithms and Source Code

#45

Post by joosters »

zero_iq wrote: post #42
joosters wrote: post #34

Has anyone tried using the equivalent of animated GIFs to help with dithering? If you have a limited palette of colours, perhaps you could produce two dithered versions, with pixels sometimes having different colours in alternate frames. If the image is refreshed fast enough, two colours could blend into a third. The most extreme example could be 'dithering' a grey square into 1) a black square and 2) a white square,…

This was especially common on 8-bit and 16-bit computers to fake 'high colour' displays on machines that had only limited colour capability. They often took advantage of the fact that people were using their machines with TVs with relatively slow-changing phoshor screens, so the flicker was less evident than on a modern monitor. e.g. Photochrome on the Atari ST, was especially impressive at the time: https://www.yout…

Wow, that example parrot image is pretty impressive, given that it is just three colours, and I'm viewing it on an LCD!

I never knew anyone had tried that before on a spectrum. At first I thought you were just talking about the other trick, getting more than 2 colours per 8x8 by changing the palette as the raster scanned down the screen. The multi-colour parrot is way more adventurous!

I'd love to see the parrot image on an old CRT to get a feeling for what the effect might look like with the phosphor afterglow. Leaving the spectrum behind and using a bigger palette range, like on the ST, the effect seems much less epileptic fit inducing, because you can pick closer colours to switch between.

Re: Image Dithering: Eleven Algorithms and Source Code

#47

Post by tixzdk »

rabidsnail wrote: post #46

Also if you don't know what your target palette is you can do k-means clustering over colorspace, and the palette is the cluster centers (each point you're giving to k-means is an or vector).

K-medians or k-medoids yield more pleasing results in my experience

Re: Image Dithering: Eleven Algorithms and Source Code

#48

Post by rabidsnail »

spiderfarmer wrote: post #25
startling wrote: post #15

Earlier quoted context omitted.

These are the kinds of things, specifically, that gross me out about this story: (from http://geekfeminism.wikia.com/wiki/Sexualized_environment ) * In geek contexts, they are usually a way for heterosexual men to bond over their common attraction to women. This is othering for anyone who is not a heterosexual man, including, obviously, women, and contributes to their invisibility in the field. This sensation of excl…

This is othering for anyone who is not a heterosexual man I disagree. Women look at other women as well. It's very natural to feel excluded when groups of people over something you don't get excited about, whatever the subject. If, for example, people can contain their excitement about Magic cards when I'm around, I'm fine. There is a long tradition of sexual images, suggestions and approaches being used to shame, sc…

Forget abstractions for a second; there are people whom this makes uncomfortable (we know because they said so), and the cost of that is much higher than the very small benefit of using one image over another as a test image. Simple cost/benefit analysis says to use something else.

Re: Image Dithering: Eleven Algorithms and Source Code

#49

Post by rabidsnail »

joshvm wrote: post #33
startling wrote: post #15

Earlier quoted context omitted.

These are the kinds of things, specifically, that gross me out about this story: (from http://geekfeminism.wikia.com/wiki/Sexualized_environment ) * In geek contexts, they are usually a way for heterosexual men to bond over their common attraction to women. This is othering for anyone who is not a heterosexual man, including, obviously, women, and contributes to their invisibility in the field. This sensation of excl…

Bear in mind that computer vision has used a cropped image of Lena Söderberg (i.e. the infamous Lena image) for decades now. If you believe the anecdote, the image was not chosen as an in-joke or as a way of sexualising women. The researchers needed a high quality image of a human face (hence they cropped out her body) and they were tired of stock images. Someone in the lab had a playboy magazine and history was made…

That's all true, but that doesn't make it less squicky.

Re: Image Dithering: Eleven Algorithms and Source Code

#50

Post by pjc50 »

c3534l wrote: post #44
the8472 wrote: post #35

The article doesn't mention the void and cluster[0][1] ordered dithering (and modernized variants) which have the advantage of ordered dithering that they are highly parallelization, e.g. via GPU shaders but do not leave the easily spottable patterns of ordered dithering. For example the madVR[2] video renderer uses it for realtime video dithering to avoid banding shallow color gradients from 10bit sources or debande…

I find it amusing that someone would have a dedicated GPU, yet cannot fully render color images. I mean, I'm sure there's actually plenty of use-cases, but it's still funny.

"Fully render" is a strange way of putting it - most consumer hardware has only 8-bit colour depth, and lots of video compression algorithms will turn smooth gradients into blocky messes that would benefit from dithering.

If you're processing the decode at 10 or 16 bits and need to render at 8 bits, it's much better to dither than truncate.

Post reply on HN