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

Ditherpunk: The article I wish I had about monochrome image dithering

surma.dev

Post reply on HN
Print view View original

191–200 of 203 posts

Re: Ditherpunk: The article I wish I had about monochrome image dithering

#191

Post by enriquto »

crazygringo wrote: post #183
enriquto wrote: post #138

Earlier quoted context omitted.

> I'm also really curious what contexts this has been most successful in. E.g. was it used for dithering in images or games back in the 1990's when we were limited to 16-bit or 256-bit color? Or is this something more recently explored in academia or in some niche imaging applications? No need to speak in the past tense! It is not a "niche" application, either. Think about it: gray ink is almost never used. All print…

Huh, to be honest I feel like I've only ever seen halftoning when printing onto paper -- I've never associated dithering with printing at all. And the "linear dithering" you're describing, when I think of images in certain banknotes and passports or quality seals that I'd call "engraved", I've always assumed were hand-drawn by an artist. But I like what you're describing and linking to, as a way to achieve that hand-…

> Huh, to be honest I feel like I've only ever seen halftoning when printing onto paper -- I've never associated dithering with printing at all.

Yep, sorry about my sloppy terminology. I always use "halftoning" and "dithering" interchangeably. Yet, notice that today's printers are often matrix-based, i.e., like a high-resolution binary screen, with a bit of ink smearing depending on the type of paper/plastic.

> I've always assumed were hand-drawn by an artist.

Maybe some are still drawn by hand, but most printed stuff is at some point dithered automatically (and a lot of critical information can be embedded on the dithering patterns).

Re: Ditherpunk: The article I wish I had about monochrome image dithering

#192

Post by darusnna »

vanderZwan wrote: post #176
darusnna wrote: post #174

Earlier quoted context omitted.

The standard PRBS23 polynomial is X^23 + X^18 + 1. Most of the factors are zero. Only the factors for exp 23,18,1 are 1. This causes poor bit mixing - ie the output sequence will have strong correlation every 23 bits. Choosing a "fat" primitive polynomial, ie a polynomial not from this list[0] but rather a polynomial with 50% of the taps are 1 (but it still must be primitive[1]), increases the avalanche effect[2] to…

I'll be honest, that is a bit terse for a lay-person like me, but the links hopefully give enough pointers to properly grok what you said with a bit of reading. Thank you!

Note: in the software world, the equivalent construction to the LFSR with "fat" polynomial is the xorshift PRNG. For more details, see the book: Numerical Recipes, 3rd edition (not 2nd ed!), Chapter 7 random numbers, section 7.1 uniform RNG - history.

Re: Ditherpunk: The article I wish I had about monochrome image dithering

#193

Post by labawi »

BlueTemplar wrote: post #172
labawi wrote: post #164

Earlier quoted context omitted.

If you want physically accurate averaging (resize, blur etc), then RGB is fine, as long as you use linear values (or do long-winded transformed math). AFAIU it is by definition 100% physically accurate. As was said, sRGB uses gamma values, where typical math creates ill effects, as in many if not most typical programs. If you want to do perceptually uniform averaging of colors, color mixing / generating / artistic ef…

I'm not sure what you mean by "physically accurate" ? No color reproduction is going to be physically accurate, except by accident, since color is an (average) human qualia, not a physical observable. And especially because whatever the way that the colors are going to be reproduced, there's no guarantee that they will correspond to the same light spectrum than the original, since there's an infinity of spectra corre…

Yes, color is a human concept for certain stimuli, no recording or reproduction is 100% accurate and even the model is not perfect (different people have shifted color sensitivities, some are even tetrachromats and we are ignoring rods vs. cones altogether).

However, the stimuli is predominantly light, which can be quantified and certain operations with light are well studied. Not all, but most noticeable ones are and that is what is used when doing photorealistic rendering etc.

If you do a 2x downscale, you need to average 4 pixels together. Linear RGB should (by theory and definition) give you a (theoretically) physically accurate result, as if you did a physical 2x downscale by putting it further away in a uniformly lit room or whatever. You can't reproduce that precisely, but neither can you reproduce 1l + 1l of milk = 2l of milk.

This is in stark contrast to downsizing, blur or whatever "performed" in sRGB, where images get curiously darker and slightly off-color (or is it lighter?).

I'm not sure what is perceptual average of colors, but if you mix pixels in 1:1 ratio and apply blur / look from far away, there is only one correct result, and linear RGB average (is one way that) gives you the single correct result. (ignoring screen color reproduction deviations from what they are supposed to be)

Re: Ditherpunk: The article I wish I had about monochrome image dithering

#194

Post by fireattack »

BlueTemplar wrote: post #144
fireattack wrote: post #111

Earlier quoted context omitted.

I always feel we have way too many historical burdens (which were good compromises at the time) in (digital) image/video field. In no particular order (and some are overlapping), I can immediately think of gamma, RGB/YCbCr/whatever color models, different (and often limited) color spaces, (low-)color depth and dithering, chroma subsampling, PAL/NTSC, 1001/1000 in fps (think 29.97), interlaced, TV/PC range, different…

That's a bit like saying that we shouldn't use lossy image/video compression. Do you realize the amount of 'waste' that a 32bpc†, 4:4:4, imaginary color triangle gamut picture would have ? †it looks like the human eye has a sensitivity of 9 orders of magnitude, with roughly 1% discrimination (so add 2 orders of magnitude). So, looks like you would need at least 37 bits per color with a linear coding, the overwhelming…

I have no issue with lossy compression; but things like 4:2:0 aren't really typical lossy compression. It's like calling resizing an image to half its resolution "compression".

Also lossless compression can reduce plenty of "wasted" bits already (see: png vs bmp).

Re: Ditherpunk: The article I wish I had about monochrome image dithering

#195

Post by firebotipt »

Here's a trick. Before you do anything.... Add noise. Then use error diffusion. Looks pretty good for how crazy fast it is.

Figuring out the strength of the noise is tricky. Usually 5 to 10 percent. I'd suggest random RGB and not monochrome noise(so not quite how you've coded the randomness, but similar idea), as this should create more unique values and reduce patterned artifacts.

Re: Ditherpunk: The article I wish I had about monochrome image dithering

#196

Post by firebotipt »

pompez wrote: post #91

Is it just my eyes or does the gradient dithered in sRGB look more accurate that the one dithered in linear space?

The sRGB version is evenly balanced bitwise yet 'gamma free'. The linear RGB version appears bitwise imbalanced due to gamma correction, but cross your eyes and blur your vision, and you'll see the linear RGB is actually more gamma correct! (Better contrast and luminosity)

Re: Ditherpunk: The article I wish I had about monochrome image dithering

#197

Post by cnity »

ayush000 wrote: post #180
cnity wrote: post #133

Earlier quoted context omitted.

This guys' articles are wonderful. I was experimenting with compiling C to WASM[0] and Surma's was really helpful. [0]: https://surma.dev/things/c-to-webassembly/index.html

His HTTP203 series with Jake Archibald is amazing if you happen to be a frontend developer. https://www.youtube.com/watch?v=9-6CKCz58A8&list=PLNYkxOF6rc...

I'll give it a watch, thanks.

Re: Ditherpunk: The article I wish I had about monochrome image dithering

#198

Post by CyberRabbi »

nullc wrote: post #118
CyberRabbi wrote: post #116

Earlier quoted context omitted.

Very cool paper. Something that bothers me is that the Floyd-steinberg error diffusion without dithering looks superior than the version with the dithering. I think this demonstrates that perceptible patterns in the error (non-linear) don’t always look so bad.

One thing I've found (admittedly with audio) is that you can usually get away with less dither power than is needed to completely linearize the error, at the cost of some harmonics for pathological signals which still ends up being less noticeable than the higher power dither noise. I expect something similar to apply to images.

Right, I think that’s what’s going on in my image example.

I think this is a key lesson to people who apply these types of mathematical techniques to the lossy compression of data meant to be experienced by humans. Random noise is not always preferable to non-linear error, i.e. reducing non-linear error is not necessarily the equivalent of improving the perceived quality of the data in question. It can be but the function that determines what “looks good” or what “sounds good” to humans is probably a bit more complex.

This is something I’ve run into with image compression techniques but it applies here too (quantization being a form of compression). E.g. JPEG compresses images in 8x8 blocks because doing the whole image at once would look horrible. Figuring out the redundant information that can be thrown away with the least impact to image quality is still fundamentally an art.

Re: Ditherpunk: The article I wish I had about monochrome image dithering

#199

Post by cdelsolar »

the_af wrote: post #67
jVinc wrote: post #64

I am in the same boat as the author of having only recently played Return of the Obra Dinn between Christmas and new years. I cannot recommend it enough, if you haven't played it and like puzzlers you should pick it up. It's an extremely engaging story, and a narrative tool I have not previously encountered. No spoilers as this is revealed immediately, but essentially you are navigating past events through frozen tim…

I share your love for Return of the Obra Dinn, truly a masterpiece and a game which shocked me out of my usual apathy towards recent videogames. I have faith in Lucas Pope for whatever project he decides to tackle next. Two of his games are masterpieces, this one and Papers Please, and I also liked Helsing's Fire a lot. Whatever he does next, regardless of scope and theme, will surely please me.

This game was so freaking good, and I also agree, I'd become sort of bored of video games until this was recommended. I stayed glued to the game until I 100%ed it (didn't take me too long, maybe around 20 hours). I really really wish I could forget the game and replay it, or that there was a part 2, or something. Incredibly creative and well-made.

Re: Ditherpunk: The article I wish I had about monochrome image dithering

#200

Post by BlueTemplar »

fireattack wrote: post #194
BlueTemplar wrote: post #144

Earlier quoted context omitted.

That's a bit like saying that we shouldn't use lossy image/video compression. Do you realize the amount of 'waste' that a 32bpc†, 4:4:4, imaginary color triangle gamut picture would have ? †it looks like the human eye has a sensitivity of 9 orders of magnitude, with roughly 1% discrimination (so add 2 orders of magnitude). So, looks like you would need at least 37 bits per color with a linear coding, the overwhelming…

I have no issue with lossy compression; but things like 4:2:0 aren't really typical lossy compression. It's like calling resizing an image to half its resolution "compression". Also lossless compression can reduce plenty of "wasted" bits already (see: png vs bmp).

But they are ! Like other lossy forms of compression, chroma subsampling takes advantage of the human visual system's lower acuity for color differences than for luminance.
Post reply on HN