Dither and Gamma

2009-04-03

Where every pixel counts.

Dithering (in images) turns this:
swatch

Into this:
swatch-dither

As you can do doubt see, the upper image has shades of grey, the lower image has only black and white. The intermediate shades have been approximated by a sort of pseudo random dotty pattern. The lower image is a dithered version of the upper image.

So, one question is: “For a given grey area, how many white dots should we use, on average?” Well, opinions vary (and rightly so), but here’s one way of thinking about the problem: When viewed from a modest distance the dithered image should emit the same number of photons as the greyscale image would have (at least approximately). And that should be true for any reasonably sized patch of the image too. I’m aware that this is just one method of determining what an ideal dithering should do, but it’s the one I’m going to adopt for this article.

So a “50% grey” patch should, when dithered, end up as roughly 50% black pixels and 50% white pixels. There’s a problem. Gamma.

If your greyscale image file has the value 128 (out of 255) for a pixel, that doesn’t mean “produce a grey pixel that emits 50% as many photons as a white pixel”. Oh no. What it probably means in reality (regardless of what the file format says it should), is “write the value 0×80 into the framebuffer”, and what that actually corresponds to is “produce a pixel that emits 18% as many photons as a white pixel” (0×80 corresponds to a fraction of about 0.5; framebuffer values often correspond linearly to voltages on the CRT gun, and the CRT responds like x2.5. And 0.52.5 is about 0.18). The details are complicated and vary a lot, but the bottom line is: When dithering, a pixel value of 128/255 does not correspond to 50% intensity.

Gamma is the exponent used to convert from linear intensity space to gamma encoded space (when < 1), and at the other end to convert from gamma encoded space to photons (when > 1).

So when I said “50% grey”, above, implicitly meaning “a grey that emits 50% of the photons that white emits”, in a gamma encoded image that corresponds to a much larger pixel value. If the image is encoded with a gamma of 0.45 (a typical value used in “don’t care” PC image processing), then the encoded value of a grey that is 50% as intense as white is 0.50.45 = 0.732. Such a grey actually looks quite light.

So when you dither an image you had better convert the pixel values into a linear light space. If you don’t, then an area that has a colour of #808080 will come out with 50% white pixels, instead of 18%. Does it matter? Well, it certainly makes a difference:
as12-49-7281-g045-320

A crop from Nasa’s AS12-49-7281 showing Charles Conrad Jr. reflected in Alan L. Bean’s visor.

Dithered assuming a gamma of roughly 0.45:
g045

Dithered assuming image represents linear light intensity (in other words a gamma of 1, what you do if you just applied the dithering algorithm with no adjustment):
glin

Well, I hope you can see that the two dithered images are different. In the lower image the obvious differences are that the bloom-effect on the left hand side of the image is much more pronounced than it should be, and the visor looks more washed out than it really should be. The lens of Bean’s camera is also the wrong shade in the lower image, but that actually picks out a detail that we cannot see in the upper image, so it’s not all “bad”.

The author of Netpbm must have had a similar realisation. In 2004 pgmtopbm, which did dithering but without any gamma correction, was superseded by pamditherbw, which gamma corrects and dithers in one.

Why did I dither assuming a gamma of 0.45? Well, because the source image was a JPEG that appeared to contain no information about how it had been gamma encoded. If I assume that the picture is displayed on typical crappy (PC) hardware and has been adjusted until that looks okay, then that corresponds to an encoding gamma of about 0.45 (1/2.2). One way to think about this is that PCs implicitly assume that images they are showing have been encoded with a gamma of 0.45; if they’re made by people on PCs then they probably have effectively been encoded with a gamma 0.45 whether the person making the image knows it or not. Incidentally OS X, if left to its own devices, has an implicit encoding assumption of 0.56 (1/1.8).

The images on this page are PNG images with their gamma encoded expressly specified by gAMA chunk. On my machine, Mac OS X actually takes notice of a PNG’s gamma encoding and adjusts the displayed image accordingly (the implicit encoding of 0.56 mentioned above comes from the fact that a PNG image with no gamma encoding specified and a PNG image with a gamma of 0.56 will display identically (assuming they have the same pixels values!)). So if you’re viewing on a Mac, there’s a good chance that you’ll see what I see. That’s important for the greyscale version of the astronaut picture because the gamma encoding actually makes it display a little bit darker than it otherwise would.

The dithering is actually done by a Python program that uses PyPNG. The first dithered image is the result from «pipdither < in.png» where in.png is the greyscale PNG including a gAMA chunk (which pipdither respects by default); the second, lower, dithered image is the result from «pipdither -l» (the -l option causes it to assume linear input). At the moment pipdither (and friends) live, undocumented and unloved, in the code/ subdirectory of PyPNG’s source.

By the way, these dithered images are a great way to expose the fact that Exposé on a Mac point samples the windows when it resizes them. Try it, and learn to love the aliases. Do graphics cards have a convolution engine in them yet? And no, I wasn’t really counting bilinear filtering (though that would be a lot better than what Exposé does right now).

Dithering isn’t just used to convert an image to bilevel black-and-white. It can be used to convert an image to use any particular fixed set of colours (for example, the “web-safe” colours). Reducing the bit depth of an image, for example converting from 8-bit to 6-bit values, can be seen a special case of this (in that the fixed set is the complete lattice of 6-bit values). pipdither can’t (yet) do arbitrary conversion, it can currently only be used to reduce to a greyscale image’s bit depth. It currently has a bug whereby it effectively produces a PNG file in linear intensity space, but doesn’t generate a gAMA to tell you that.

So when you dither you ought to gamma correct the samples. But what value of gamma to use? This is problematic: Many images do not specify their encoding gamma, even when the file format allows it; even when it is specified, the gamma might include a factor for rendering intent (both PNG spec section 12, and Poynton’s Rehabilitation of Gamma suggest that it is reasonable for the gamma to be tweaked to allow for probable viewing conditions); you might have your own reasons (artistic intent, let’s say) for choosing a particular gamma.

I think the practical upshot of this is that any dithering tool ought to let you specify what gamma conversion to use (probably on both input and output). Does yours?

About these ads

8 Responses to “Dither and Gamma”

  1. pizer Says:

    The key here is the color space. You mostly deal with the sRGB color space which has a nonlinear mapping between pixel value and luminosity. It’s not exactly a gamma of 2.2 but close (at least for the upper brightness levels).

    Yes, dithering should be ideally done in “Linear RGB” space. This also applies to filtering. Imagine a lowpass filter on a checkerboard that turns alternating 0,255,0,255. into 128,128,128,…

    Cheers!
    SG

  2. drj11 Says:

    @pizer: I think you mean you mostly deal with sRGB. ;) In any case it’s not that images are deliberately coded in sRGB, it’s just that if you don’t know, don’t care, then it’s likely to be a good assumption when you need it.

    Filtering is the topic of an upcoming article, if I get round to it.

  3. drj11 Says:

    @mathew: Yes. It concerns “what pixels the error is distributed to and what fraction each pixel receives” (a quote from my later article). Whether to use Atkinson or Sierra Filter Lite (as pipdither currently does) or Floyd–Steinberg is an orthogonal concern from deciding to gamma correct the source image samples first.

  4. drj11 Says:

    From a quick eyeball it looks like Koch doesn’t gamma correct.

    Koch’s bun is a JPEG. By my measurements the area at about (142, 276) (with (0,0) being lower left) has code 0x7A (roughly). This corresponds to relative intensities of:
    0.48 (gamma=1)
    0.27 (gamma=1/1.8)
    0.20 (gamma=1/2.2)

    The same region on the Atkinson dithered image contains about 48% white pixels. Conclusion: Koch doesn’t gamma correct.

    To some extent Atkinson compensates for this by throwing away 25% of the error. That’s what creates the deep shadows in the Atkinson version.

  5. pizer Says:

    Frankly, I don’t like the “Atkinson dither”. It seem like it doesn’t push the quantization noise into higher spatial frequency bands as good as Floyd-Stainberg.

    I recently coded a Floyd-Steinberg noise shaper with a special perceptual weighting. It uses the linear RGB space for “error diffusion” and a nonlinear YUV-like color space to find the “best” match for the next pixel. Compared to GIMP it’s usually visually more pleasing, IMHO. It’s based on the fact that the human vision system has a high spatial resolution for the luminance part and a low spatial resolution for the chrominance part of the image. If you’re interested, I could write a blog post about it and show some results.

    Cheers!

  6. pizer Says:

    How about a challange? Post a link to a 16M-color image and I try to generate a nice 256-color version from it. :-)

    Cheers!

  7. drj11 Says:

    @pizer. Aha! I was thinking about changing pipdither so it does exactly what you suggest. Choose colours in some sort of perceptual space, but diffuse error in linear RGB. I’m glad you’ve tried it and like it.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: