Extreme Pedantry For The Win!

Last month I got a Penalty Charge Notice from Islington. I am the registered keeper of the vehicle in this alleged contravention:

I think normally I would’ve just sucked it up and paid the fine, but… they caught me in the wrong mood. Clearly the street furniture is arranged so as to maximise ticketing revenue from tourists. This appears immediately after a left-turn to enter the road. In the first picture (left) the brakes are on; the car is stopped because the driver is wondering how to interpret this fantastic and unusual display of road furniture. Locals will know about already and just drive around.

I wrote the following letter:

I have received a Penalty Charge Notice from Islington.

“LLATLA 2003″ is a reference to primary legislation London Local Authorities and Transport for London Act 2003.

On reviewing the relevant legislation I find that Islington fail to meet their statutory obligations with regard to the penalty charge notice (LLATLA 2003 Section 4 subection (8)).  I find that:
- there is failure to state the grounds on which Islington believe that the penalty charge is payable.  In particular, Islington should state whether their belief is that Section 4 subsection (5)(a) applies, or Section 4 subsection (5)(b) applies (referring to LLATLA 2003).  I am content that Section 4 subsection (7) does not apply;
- there is failure to state that the person on whom the notice is served may be entitled to make representations under paragraph 1 of Schedule 1 of LLATLA 2003;
- there is failure to specify the form in which any such representations are to be made.

If Islington intends to pursue this matter further, please send a revised penalty charge notice.

Today I got a letter from Steven Prieditis, Correspondence and Appeals Office, Islington Council. There’s some blurb, and then:

Due to an error when issuing the PCN thsi ticket has been cancelled.

[sic]

Yay!

I’m actually slightly disappointed. In the (now cancelled) PCN they allege: “Failing to drive in the direction shown by the arrow on a blue sign”.

That contravention did not take place. Referring to diagram 606 of The Traffic Signs Regulations and General Directions 2002, we can plainly see that the alleged offence would be failing to observe a sign like this:

“vehicular traffic must proceed in the direction indicated by the arrow”.

You can just about make out the blue sign in the pictures at the top of the article. It’s this:

(Diagram 610 of the regulations). And the description of that sign is “vehicular traffic must comply with the requirements prescribed in regulation 15″ (of The Traffic Signs Regulations and General Directions 2002).

Wrong sign. Didn’t happen.

PS I hereby license you to do whatever you like with the letter I wrote.

Earth, again

So unless you’re using OS X (or, apparently, Firefox 3.5b4 on Vista), my earlier article and MDIS and embedded colour profiles and what-not must’ve seemed a little bit mysterious. The two pictures of Earth will have looked the same (on computers that ignore the ICC profile embedded in the PNG).

It turns out that Apple’s ColorSync Utility will let you change an image’s ICC profile: either editing the image to fit the new profile, or just slapping a different profile on (I discovered this by reading the Help, making it the second useful fact I’ve learnt from OS X Help). Strangely, ColorSync can also resize an image. And it’s a magnification tool. Anyway, remapping the images into sRGB allows me to show you a simulated version of what I see. Your computer will ignore the embedded sRGB profile, but that’ll be okay, because it’ll look roughly right. That’s what sRGB is designed to do.

The top image is a simulation of the raw MDIS camera values in a linear space. The bottom image is the corrected version using the ICC profile I showed in the earlier article.

The middle image is the “just blat the pixels onto the graphics card” version that ignores all gamma and ICC profiles. As you can see, in terms of black level, it’s hard to distinguish its background from your display’s true black unless you put a true black right next to it.

PS This is supposed to be Earth. Does anyone recognise what we’re looking at? Technically there’s enough metadata in the original IMG files for me to answer that question, since the exact time of the exposure is recorded as well as exactly where the camera was pointing, but like that’s going to happen.

My laptop bag

Just got back from a weekend on the farm (actually that was a few weekends ago, but I only just got round to cleaning up the article). Thought it might be fun to clear out my laptop bag. My laptop bag is my man-bag, it’s a portable version of my life. The bag is a fairly ordinary looking black affair made out of the hide of baby seals. I blagged it from my mum after she retired from being a power manager. It’s clearly very well made as it suffers much abuse and has lasted very well indeed. Want to look inside?

Short IKEA pencil with big wedge-shaped rubber on the back. Ideal for sudoku (not that I ever do them).

A borrowed laser pointer. Doesn’t work.

10 Ultra Soft white tissues from FSC Mixed Sources.

Half a packet of Wrigley’s Extra Peppermint Sugarfree Gum. Odd, since I don’t chew gum. Also, I don’t particular like sugar-free products; it’s just another term for “contains aspartame”.

A badge (not a conference badge, for once).

A Keyboard Anthology, Edited by Howard Ferguson, Book 1 (Grades 1 & 2), ASBRM. You know, for the pianoforte.

The handmade slip case for my laptop.

Pilot V5. The only writing implement I can depend on.

Pair of cheap Aiwa earphones.

A cable with a headphone jack at both ends. This cable languished in my boxes of crud for years until I unexpectedly found a good use for it. More on that in a later article perhaps.

Darwin, “Voyage of the Beagle”. One of many half-read books, but this one is the one I currently carry around.

Dog eared fag end of a pack of almost uselessly small Post-It notes. Each one covers only 6 keys on my keyboard.

A blue USB memory stick that takes an SD card. A 2GB SD card, in fact.

Some keys.

A combination 3-way USB hub and N-way card reader. With a very short USB A to mini-B cable. The hub feature is not so useful, but the card reader often gets used for reading random people’s memory cards so I can copy their photos.

A MacBook VGA monitor cable dongle thingy.

Some more keys.

Another USB memory stick. Not modular, 128 MB of soldered memory.

Charger for Canon digital camera battery.

Charger for Nintendo DS. The last two items are slightly amusing, as the neither the camera nor the DS is in the bag.

What’s in your bag? Are you going to tidy it out / stock it up for the conference season?

OS X and X11

Apparently Matlab on the Mac is still in the stone-age of using X11, and it sucks.

Yes, Apple provide X11 with OS X. But you’re not supposed to use it. It’s not for lazy retards to base their Mac platform strategy on, it’s for desperate people who absolutely must use that X11 app that some scientist wrote back in 1993.

I find mathwork’s attitude a bit whiny. On moving away from X11: “this is a multi-year endeavor”. Well, yeah. I’m sure it is. But OS X has been out for over 8 years now!

Bottom line: if your answer to “do you have a Mac product” is “Yes, we use X11″, then you do not have a Mac product. You have an inexcusable pile of dingo turd. If the answer is “Yes, it’s written in Java” then you just upgraded your turd to offal. Congratulations.

Of course, this is just my opinion. My opinion and the opinion of every other Mac user. If we liked using X11, we’d all be using Linux already.

PS: Firefox gets it right. How hard can it be?

What Good is PyPNG? (and some MDIS pictures of Earth)

I originally wrote PyPNG so that I could manipulate PNG images using Python. My original itch was a tiling application. Since then I’ve been using to develop all sort of little image utilities and investigate PNGs. pipdither is written in Python and the initial version took about an afternoon of fairly lazy coding.

Python is a great language, and now that I’ve got a module for creating PNGs, it’s easy to create other image tools in Python.

Here is a link to an image of Earth taken from the Messenger spacecraft (a 2.1e6 octet file that you won’t be able to read). Messenger was on an Earth flyby on its way to map mercury when it took the image. The image is archived by NASA’s PDS and stored in its IMG format. Which is basically a whole boatload of metadata followed by the image data in row major order at 16-bits per pixel.

Because it’s basically just a bunch of numbers after the metadata, this is really easy to grok using Python. Here it is converted to PNG using PyPNG (this is a small 8-bit version, follow the link to get the full 12-bit version):

It looks rubbish. Someone has turned the brightness up too high on the telly. It looks rubbish for two reasons: a) I embedded a gAMA chunk to specify a gamma of 1.0 (linear); and, b) the camera’s black-level does not correspond to a code of 0. Here’s a histogram:

Sorry the histogram is a bit rubbish (the image is 12-bit, so the histogram is 4096 pixels wide). But you should be able to see that the first chunk of codes (on the left) are unused. That’s because even though there’s no light falling on the sensor, there’s thermal noise or some residual current drain, or something. So picture black is represented by a code of about 7%. And because I specified a gamma of 1.0 that 7% value in the PNG file actually looks not very dark at all.

Actually I had to fiddle with wordpress quite a lot to get it looking this bad. If left to its own devices wordpress will create its own scaled down version of the image and it THROWS AWAY the gAMA chunk. If your computer ignores the PNG’s gamma chunk then maybe the image doesn’t look to bad to you (a grey level of about 7% in some sort of perceptual space looks fairly black, not actually black, but good enough that you probably won’t tell unless you open a black image next to it).

So clearly to get a good image I should choose some black-level, 7% say, subtract 7% from all the pixel values and rescale to fit the full range. Yeah I could. But that would destroy the original data and impose my own processing on it. What if you wanted to do your own black-level compensation?

I had an idea. I could create an ICC profile that clamps the bottom 7% codes to black, then embed the profile in the PNG. The profile looks like this (in Apple’s ColorSync utility):

Apologies (yet again) for the fact that the screenshot doesn’t fit. WordPress would’ve scaled it, but apparently it falls over when trying to scale a 4-channel PNG. The screenshot has an alpha channel because it’s a shot of a Window and the window has chamfered corners which require alpha. How amusing.

Anyway. Input is on the x-axis, output is on the y-axis. You can see that this TRC curve maps the bottom 7% into 0, and the rest goes linearly.

This being the first time I’ve deliberately embedded a colour profile into a PNG image, I’m slightly gobsmacked that it actually works:

You get the best of both worlds. A plausible looking picture for viewing, and all the original image data if you want to dink around with it yourself.

I’m pretty sure that a gamma of 1 is correct, by the way, because the values in the IMG file are raw 12-bit sensor values and they generally respond linearly to light. Actually they’re not quite raw, the onboard computer has compressed the image before it was transmitted to Earth, you can see compression artefacts in the “noise” in the dark regions of the picture (if you look at the version that doesn’t have a colour profile).

PS If these images look the same, your computer isn’t doing colour collection. It sucks. It works on a Mac [ed: if you use Safari]. Try my later article to see a simulation of what it looks like when it works.

2-bit dither

An earlier article suggests we should pay attention to gamma, at least when the output is 1-bit deep. How should we dither when we want the output to be more than 1-bit deep. Say, dithering 8-bit input down to 2-bit output?

We need to decide:

- What output codes shall we use?
- How do we choose the each output code?

A general purpose dithering routine can use an arbitrary set of output codes. The number of output codes is determined by the desired bit-depth of the output. If we have a 2-bit output file, then that’s 4 output codes.

The easiest output codes to use are linear ones, because we’re doing the dithering in linear space (we are, right? Well, part of the reason for this blog article is to explore when that is worth doing). For example, a 2-bit output code in linear space can be selected with «int(round(v*3.0))». There’s a problem: this sucks. It sucks for all the same reasons that we use perceptual codes in the first place: we’re pissing away (output) precision on areas of the colour space where humans can’t perceive differences anyway; not enough buck for each bit.

This 8-bit ramp is dithered down to 2-bits and the gamma (of the 2-bit output image) is 1.0:

Black pixels extend from the left almost to the middle, so just 1 of the 3 adjacent pairs of output colours (0 n 1, 1 n 2, 2 n 3) are dithered over 50% of the image area. That doesn’t seem like a good thing. Also, the 2 lightest colours are very close to each other (perceptually), giving the effect that the right-hand end of the ramp looks “blown out” with not enough shading.

So, the output codes ought to be in some sort of perceptual space (mostly); it makes sense to allow the user to specify the output codes. Not just how many output codes (the bit depth), but also the distribution of the output codes, which amounts to selecting the output gamma. Yeah, I guess in general you want to specify some calibrated colour space; gamma is a simplification.

Two curves show the difference between picking output codes in linear space (gamma = 1.0) and in a perceptual space (gamma = 1.8). The (relative) intensity values appear on the right:

Error diffusion dithering (which is what pipdither does) is a general term for a number of algorithms all of which boil down to:
- pick an order to consider the pixels of an image;
- for each pixel:
– from the pixel’s value v, select an output code with value t;
– the error, v-t, is distributed to pixels not yet considered by adding some fraction of the error onto each of a number of pixels;

The differences between most error diffusion dithering algorithms amount to what pixels the error is distributed to and what fraction each pixel receives. I won’t be considering the error diffusion step in detail in this article.

So, how do we choose the output code? Since we are doing the dithering in linear space, we have presumably converted the input image into linear values (greyscale intensity). The easy thing then is to arrange the output codes in the same linear space (in other words, convert all the output codes into linear space), and pick the nearest output code corresponding to the value of each pixel. Actually pipdither allows you to favour higher codes or lower codes by placing the cutoff point between each pair of adjacent output codes some fraction of the way between them; the fraction can be specified (with the -c option in the unlikely event that anyone actually wants to use pipdither), and defaults to 0.75, favouring lower output codes. I may explain why in a later article.

The one problem with this algorithm: the images it produces look almost the same as the naïve algorithm that just ignores all considerations of gamma (pretending that the input and output are linear when in fact both are coded in perceptual space). So our new improved algorithm is just pissing away CPU performance for almost no gain in image quality. Still, at least we can be smug in the knowledge that it Does The Right Thing.

Can we actually tell any difference between my Right Thing gamma-aware algorithm and the naïve algorithm which knows nothing about gamma (and hence just pretends everything is linear)? The middle image (below) is a greyscale gradient with 256 grey values (8-bit). The other two images are dithers down to 2-bit. Can you tell which image is which algorithm?

Here’s a couple of spacemen. I think the difference between the two algorithms is more pronounced:

And I’d just like to point out that because of Apple’s 2-bit PNG bug, all of these “2-bit” PNGs are in fact 8-bit PNGs that just happen to only use 4 codes (I use pipdither -b 8 to increase a PNG image’s bit depth; no dithering takes places in that case).

Python: Tail Call Optimisation

Normally, two words are sufficient to explain why we need tail call optimisation.

Guido still doesn’t get it.

lambda, map, reduce, tail-call optimisation.

I’m going postal. I have shipped a copy of SICP to Guido.

[update 2009-05-20: Guido got the book]

Watchmen on the ice shelf

Note to self: When we have finally implemented our plans to rule the entire world with the iron fist of justice… Do not build evil lair on the calving face of an Antarctic ice shelf.

(Thought of this when I saw The Watchmen a few weeks ago, but saying goodbye to the Wordie Ice Shelf reminded me.)

Apple’s 2-bit PNG fail

It turns out that Apple Preview displays 2-bit greyscale PNG images incorrectly. I presume this is true of more or less any other application running on Mac OS X, because they all use the same imaging framework.

The middle image is a 2-bit greyscale PNG. It’s supposed to look like the top image, maybe it does for you. For me, on OS X 10.4 using Safari 3.2.1, it looks like the bottom image. The top and bottom images are 8-bit PNGs, and I trust those to be rendered correctly.

A 2-bit greyscale image can have pixel values of 0, 1, 2, or 3. These represent 0/3, 1/3, 2/3, 3/3 in some (grey) colour space that goes from 0 to 1. Clearly when being displayed on an 8-bit device the colours to use should be #000000 #555555 #AAAAAA #FFFFFF (in the absence of attempts to do colour management).

Apple’s OS X uses the 4 colours #000000 #555555 #777777 #FFFFFF when displaying a 2-bit greyscale PNG. There’s nothing special about the PNG I created. Apple get it wrong for any 2-bit greyscale PNG. 0×77 is not even a slightly wrong version of 0xAA. It’s just stupid and wrong. The only possible explanation I have is that 2-bit PNGs are handled with a hard-coded 4-entry palette, and someone typed “77″ instead of “AA” when typing the palette in.

Word of warning if you’re viewing the PngSuite image:

The PngSuite images generally have gAMA chunks. This one does, specifying a gamma of 1.0. Observe that, when rounded to an integer hex value, 255*(0×77/255.0)**(1/1.8) is 0xA7, which is the value that Apple uses, not the correct value of 0xCB.

When one is writing articles about dithering down to 2-bit greyscale images, this is not what one needs.

PS: Apple’s DigitalColor Meter rocks. And so many people have yet to discover it, lurking in the Utilities folder.

Dither and Gamma

Where every pixel counts.

Dithering (in images) turns this:

Into this:

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 x^2.5. And 0.5^2.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.5^0.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:

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:

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):

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?