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

171–180 of 203 posts

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

#171

Post by dljsjr »

dahart wrote: post #97
dljsjr wrote: post #5

> According to Wikipedia, “Dither is an intentionally applied form of noise used to randomize quantization error”, and is a technique not only limited to images. It is actually a technique used to this day on audio recordings […] Dithering as a digital signal processing technique is also used frequently in the digital control of physical systems. One example of this is in the control of hydraulic servo valves[1]; the…

PWM signals are dithered by definition, and are probably the most common interface, no?

Servo valve dithering is overlaid on top of the PWM duty cycle.

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

#172

Post by BlueTemplar »

labawi wrote: post #164
BlueTemplar wrote: post #142

Earlier quoted context omitted.

Are you sure about sRGB being already good enough for averaging ? (As long as we don't want to go to a wider color space of course.) We have been recently taught how to do it 'properly', and we had to go through CIELAB 76 (which, AFAIK, is still an approximation, as human perception is actually non-euclidean).

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 corresponding to the same impression for a specific color.

And if you want to do perceptually accurate averaging, you're going to have to work in a perceptually uniform color space ! Which (even linear) sRGB isn't.

All that said, it's perfectly possible that linear sRGB is just good enough for most use cases of averaging, even despite not being perceptually uniform. Especially in OP's example with just 2 shades : black and white.

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

#173

Post by BlueTemplar »

steerablesafe wrote: post #157
BlueTemplar wrote: post #139

Earlier quoted context omitted.

I don't see why you would avoid talking about it. As far as I've understood, CRT monitor gamma has basically evolved to become the inverse of human eye gamma : http://poynton.ca/PDFs/Rehabilitation_of_gamma.pdf (With some changes for a less accurate, but more visually pleasing/exciting replication of brightness levels ?) Now, with many modern, digital screens (LCD, LED, e-ink?), as far as I've understood the electro-…

sRGB gamma is often approximated to 2.2 [1], but the actual function has a linear section near 0, and a non-linear section with gamma of 2.4, possibly to avoid numerical difficulties near 0. The document you cite claims that CRT gamma is typically between 2.35 and 2.55. Human eye gamma can probably be approximated with cieLAB, that is designed to be a perceptually uniform colorspace, which seemingly has a gamma of 3…

> ciaLAB is not state of the art though in perceptually uniform colorspaces.

Which are state of the art ?

> 1. It brings in perceptually uniform colorspaces to the discussion, while it's completely unnecessary. Perceptually uniform colorspaces are mostly unsuitable for arithmetic on colors like any other non-linear colorspace.

I don't get what you mean, linearity (dL'star') being defined wrt perceptual uniformity, isn't CIELAB 76 linear by definition (to an approximation) ?? And color arithmetic pretty much by definition implies dealing with distances and angles in a perceptually uniform color space, doesn't it ??

(I would really like to know, since it actually is the very topic of 'practical work' that we have to do for mid-January. We were told to do the transformations to CIELAB 76 and, after the modifications, back to sRGB, using the D65 illuminant.)

Otherwise, I didn't mention the finer details about CRT transfer functions because it didn't seem to be relevant enough.

> This is the most widespread bug in computer color and you don't need the history of CRTs to do that, and in fact this has nothing to do with perceptually uniform colorspaces.

Yeah, I know, and while just doing this kind of transformation might be just good enough for the most common color arithmetic, is it really good enough for all use cases ? To take an example from our practical work, seeing this kind of effect :

https://en.wikipedia.org/wiki/Impression,_Sunrise#Luminance

You know what, I think I'm going to try and do this practical work in two versions, one using just linear sRGB (and back). I'll see if I get noticeable differences. But that will have to wait a week or so, I'm too busy searching for internships right now (and have already spent too much time in this discussion...)

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

#174

Post by darusnna »

vanderZwan wrote: post #160
darusnna wrote: post #156

Earlier quoted context omitted.

For less visual artifacts it is recommended to use PRBS with 50% of the taps 0, 50% of the primitive polynomial tap 1. Same period (2^n-1), but less short-term correlations.

I have no idea what those parameters represent, but I'm very curious! Could you give a layman's explanation?

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 the optimal 50% probability, ie 50% of the state bits affect the output at each step, instead of just 2 or 3 taps out of 23.

Note: the LFSR sequence length will remain the same, 2^23-1 in either case. It's just that the short-term correlation between bits will be lower.

[0] https://en.wikipedia.org/wiki/Linear-feedback_shift_register...

[1] https://en.wikipedia.org/wiki/Primitive_polynomial_(field_th...

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

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

#175

Post by magicalhippo »

BlueTemplar wrote: post #168
magicalhippo wrote: post #161

Earlier quoted context omitted.

> I expected to have to do gamma correction when making a gradient recently, but in the end it looked like I didn't have to If you don't explicitly specify the color space you're working in, then you're using some implicitly defined color space in which case you basically need to know what that is (at least roughly). So traditionally in Windows, way back, when you created a bitmap, wrote some data to it and then drew…

Yes, and in almost all of these discussions, the implicit color space is (non-linear) sRGB. (IIRC Macs might have used a different default color space one-two decades ago ?) Also, I'm on Linux, and doing picture manipulation with Octave, but thank you for the links anyway !

Yeah I was just using Windows because that's what I was familiar with. I guess on Linux is can vary a lot more on the setup.

So yeah for Octave you need to know what Octave does with the data afterwards. If it's saving a matrix to a PNG say, it could assume the matrix is linear and convert to sRGB which would be a good choice if it also supported say OpenEXR files. However it could also just take the values raw, assuming you'd convert the data to sRGB before saving. Or even allow you to specify the color space in the iCCP chunk, which would give you more power.

Again, what it actually does is something that needs to be looked up.

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

#176

Post by vanderZwan »

darusnna wrote: post #174
vanderZwan wrote: post #160

Earlier quoted context omitted.

I have no idea what those parameters represent, but I'm very curious! Could you give a layman's explanation?

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!

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

#178

Post by twic »

HelloNurse wrote: post #169
twic wrote: post #166

I'm surprised the algorithm for producing blue noise is so complicated. Could you not generate white noise, then apply a high-pass filter? Say, by blurring it and then subtracting the blurred version from the original? Could you split the map into blocks, fill each block with a greyscale ramp, then shuffle the pixels inside the block? Could you take a random sudoku approach, where you start with a blank map, then ran…

The first technique is challenging because the filter needs to have a specific frequency response, without shortcuts. Such high quality filtering can be done more simply and more exactly with an inverse Fourier transform. The second technique doesn't seem promising because shuffling is very crude: differently shuffled small blocks are going to have border artifacts, repeating small blocks are going to have worse peri…

I tried the first couple of ideas:

https://gist.github.com/tomwhoiscontrary/337cb8aaef013327a89...

I only went as far as generating threshold maps, not actually using them. Couldn't see how to do that using ImageMagick, and didn't want to write it manually!

The high-pass filter maps "look okay", but i haven't looked at their spectrum. How important is it that they have a specific frequency response? What is the failure mode if they don't?

The shuffling maps don't "look" so hot. There aren't border artifacts or repeating blocks (and you wouldn't expect these a priori - not sure why you think that), but indeed, it's not very different to white noise.

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

#179

Post by BlueTemplar »

magicalhippo wrote: post #175
BlueTemplar wrote: post #168

Earlier quoted context omitted.

Yes, and in almost all of these discussions, the implicit color space is (non-linear) sRGB. (IIRC Macs might have used a different default color space one-two decades ago ?) Also, I'm on Linux, and doing picture manipulation with Octave, but thank you for the links anyway !

Yeah I was just using Windows because that's what I was familiar with. I guess on Linux is can vary a lot more on the setup. So yeah for Octave you need to know what Octave does with the data afterwards. If it's saving a matrix to a PNG say, it could assume the matrix is linear and convert to sRGB which would be a good choice if it also supported say OpenEXR files. However it could also just take the values raw, assu…

Yeah, since we're learning, we're not doing anything fancy on that side (at least yet), so (so far) working with sRGB bmp/png/jpg input and sRGB bmp output.

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

#180

Post by ayush000 »

cnity wrote: post #133
SoSoRoCoCo wrote: post #24

This is such a well-written article: it describes the impetus, it is researched, it has great examples both as code and as output, and it piques interest. In the late 1990's I contracted with an embedded software company to optimize a dithering algorithm for 8-bit MCUs that was used in most laser printers & copiers, and this paper is a really good overview.

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

Post reply on HN