Why I love Metapost


I am writing some stuff about Conway’s Game of Life (and Scratch) – thinking about whether it is possible to explain to adults the basics of programming a computer using the Scratch Life script an an example: Life is more suitable for adults than say the Code Club fish chasing game and anyway it gives me an opportunity to indulge my fascination with the game.

To write the text I need to draw diagrams that explain how the rules work and I tried in both Xfig and Dia to do this. But it was a nightmare.

In contrast I could manage it very quickly in Metapost, even though the natural inclination is to steer clear of that and stick with the “point and drool” GUI based alternatives.

beginfig(1);
prologues:=3;

for i=0 upto 4:
draw (0, i*20 + 10) — (100, i*20 + 10);
draw (10 + i*20, 0) — (10 + i*20, 100);
draw (200, i*20 + 10) — (300, i*20 + 10);
draw (210 + i*20, 0) — (210 + i*20, 100);
endfor;

pickup pencircle scaled 12;
draw (140, 40) — (150, 50)–(140, 60) withcolor red;
linejoin:=mitered;

path a, b, c, d, e, f, g, h, j, k, l, m;
a = fullcircle scaled 10 shifted (40,40);
draw a;
fill a withcolor green;
b = fullcircle scaled 10 shifted (40,60);
draw b;
fill b withcolor green;
c = fullcircle scaled 10 shifted (60,60);
draw c;
fill c withcolor green;
h = fullcircle scaled 10 shifted (60,40);
draw h;
fill h withcolor green;
j = fullcircle scaled 10 shifted (40,20);
draw j;
fill j withcolor green;
k = fullcircle scaled 10 shifted (60,20);
draw k;
fill k withcolor green;

d = fullcircle scaled 10 shifted (220,40);
draw d;
fill d withcolor green;
e = fullcircle scaled 10 shifted (240,60);
draw e;
fill e withcolor green;
f = fullcircle scaled 10 shifted (260,60);
draw f;
fill f withcolor green;
g = fullcircle scaled 10 shifted (280,40);
draw g;
fill g withcolor green;
l = fullcircle scaled 10 shifted (240,20);
draw l;
fill l withcolor green;
m = fullcircle scaled 10 shifted (260,20);
draw m;
fill m withcolor green;
endfig;

Gives me this: (actually the original EPS is better as it is a vector format and the PNG won’t scale in the same way)

Conway's Game of Life patternMetapost is not widely known and under-appreciated.

Similarity, difference and compression


Perl
Perl (Photo credit: Wikipedia)

I am in York this week, being a student and preparing for the literature review seminar I am due to give on Friday – the first staging post on the PhD route, at which I have to persuade the department I have been serious about reading around my subject.

Today I went to a departmental seminar, presented by Professor Ulrike Hahne of Birkbeck College (and latterly of Cardiff University). She spoke on the nature of “similarity” – as is the nature of these things it was a quick rattle through a complex subject and if the summary that follows is inaccurate, then I am to blame and not Professor Hahne.

Professor Hahne is a psychologist but she has worked with computer scientists and so her seminar did cut into computer science issues. She began by stating that it was fair to say that all things are equally the same (or different) – in the sense that one can find an infinite number of things by which two things can be categorised in the same way (object A is weighs less that 1kg, object B weighs less than 1kg, they both weigh less than 2kgs and so on). I am not sure I accept this argument in its entirity – in what way is an object different from itself? But that’s a side issue, because her real point was that similarity and difference is a product of human cognition, which I can broadly accept.

So how do we measure similarity and difference? Well the “simplest” way is to measure the “distance” between two stimuli in the standard geometric way – this is how we measure the difference between colours in a colour space (about which more later) ie., the root of the sum of the squares of the distances. This concept has even been developed into the “universal law of generalisation”. This idea has achieved much but has major deficiencies.

Professor Hahne outlined some of the alternatives before describing her interest (and defence of) the idea that the key to difference was the number of mental transformations required to change one thing from another – for instance, how different is a square from a triangle? Two transformations are required, first to think of the triangle and then to replace the square with the triangle and so on.

In a more sophisticated way, the issue is the Kolmogorov complexity of the transformation. The shorter the program we can write to make the transformation, the more similar the objects are.

This, it strikes me, has an important application in computer science, or it least it could have. To go back to the colour space issue again – when I wrote the Perl module Image::Pngslimmer I had to write a lot of code that computed geometrical distances between colour points – a task that Perl is very poor at, maths is slow there. This was to implement the so-called “median cut” algorithm (pleased to say that the Wikipedia article on the median cut algorithm cites my code as an example, and it wasn’t even me who edited it to that, at least as far as I can remember!) where colours are quantised to those at the centre of “median cut boxes” in the colour space. Perhaps there is a much simpler way to make this transformation and so more quickly compress the PNG?

I asked Professor Hahne about this and she confirmed that her collaborator Professor Nick Chater of Warwick University is interested in this very question. When I have got this week out the way I may have a look at his published papers and see if there is anything interesting there.

 

More people getting it wrong about graphics formats


I subscribe to the Code Project mailing list. So every day I get an email with some links. Some stories are good (I started this blog in response to one). Some are very poor: I highlighted an earlier one about graphics formats like that.

And today I am going to do the same thing. Admittedly this one is not quite so poor. But it is still fundamentally wrong when it says

Portable Network Graphics
Image via Wikipedia

PNG is a lossless format. It is not. It may be lossless, and most PNGs out there are likely to be lossless, but stating that it is lossless a priori is just WRONG.

PNGs may be lossy – particularly if colour quantization is applied.

Furthermore PNGs are not magic machines that defy the third law of thermodynamics. If you have a lossy graphic – eg if your camera only produces compressed JPEGs then storing it as a PNG will not magic away the losses.

Horses for courses people: or, as we say in the trade, it’s a heuristic not an algorithm. There is not likely to be any simple answer to your question “what is the best format to use”: though in most cases JPEGs are the right format for (online) presentations of real world objects and PNGs are likely the best options for line drawings online (though maybe you will want to use SVG for that if they are generated programmatically).

Some advice you should ignore


I have an interest in graphic formats – I wrote the perl package Image::Pngslimmer a while back when I was hacking some perl database code that delivered (via Ajax) graphs and photographs.

I built the whole website for fun and learning purposes and so therefore used PNG graphics when JPEGs would have (for the photographs at least) been more appropriate.

So, therefore an article that begins:

Virtually every developer will use bitmaps at times in their programming. Or if not in their programming, then in a website, blog, or family photos. Yet many of us don’t know the trade-offs between a GIF, JPEG, or PNG file – and there are some major differences there. This is a short post on the basics which will be sufficient for most, and a good start for the rest. Most of this I learned as a game developer (inc. Enemy Nations) where you do need a deep understanding of graphics.

has my attention.

But what a load of rubbish it turns out to be. The author plainly doesn’t know what the “trade-offs” are either as he states:

PNG – 32-bit (or less), lossless compression, small file sizes – what’s not to like. Older versions of some browsers (like Internet Explorer) would display the transparent pixels with an off-white color but the newer versions handle it properly. Use this (in 32-bit mode using 8 bits for transparency) for everything.

…and…

JPEG – 24-bit only (i.e. no transparency), lossy (can be lossless but compressions drops a lot), small file sizes. There is no reason to use this format unless you have significant numbers of people using old browsers. It’s not a bad format, but it is inferior to PNG with no advantages.

This is seriously bad advice and it is also technically wrong.

First, PNG is not a lossless format. Many PNGs are indeed lossless, but they do not have to be.  A substantial part of the  code in the Image::Pngslimmer package is about using the median cut algorithm to produce a lossy PNG out of a lossless one by producing a best match set of colours for the image and then converting pixels to the colour in the set which is closest to them in RGB space (the median cut algorithm ensures that there are more members of the set in the bits of RGB space where there are more colours in the original image).

Second, JPEG remains by far the best way of representing photographs in the real world internet, where the trade-off between size and quality is important.  Look closely at the colour boundaries in a JPEG, especially a highly compressed one, and you can see how the edges are blurred and colours cross the boundaries – that is an artefact of the compression and indeed represents a loss (once compressed in this way the quality of the original image cannot be recovered). But it is also a highly efficient algorithm and can produce much smaller image files than the lossless PNG equivalent without any noticeable dimunition in quality for the average viewer.

As a parallel think of MP3s and FLACs for audio. Like FLACs, PNGs (can be) lossless and compressed – so delivering a much smaller file than the source WAV or similar file. But MP3s can be much smaller again without any noticeable dimunition in quality for most people on most equipment.

Yes, more and more people are connecting at 25Mb/s, but then more and more people are also connecting using GPRS, EDGE and low bandwidth 3G connections. Size still matters.

PNG is absolutely superior for representing line drawings (including artefacts such as graphs) as no one wants to see the lines start to fuzz. But that is a pretty limited subset of images on the internet.

So here is some proper advice: use JPEGs (at about 85% compression) for almost all photographs you want to put on the internet. If you have a line drawing or similar, prefer PNGs. If you have a truly lossless image (remember someone may have compressed it before it gets to you) and you need to keep it that way, then use the PNG format: but expect your file size to be very large.