Extreme image compression: the Twitter challenge

If a picture is worth a 1000 words, how much of a picture can you fit in 140 characters?

Mario Klingemann (Quasimondo on Flickr) had a fascinating — call it crazy if you like — idea: can you encode an image such that it can be sent as a single Twitter message (“tweet”)? Twitter allows 140 characters, which seems like nothing. It’s pretty much guaranteed that you’ll be able to get nothing meaningful out of so few bits, right?

Well, he came up with this, using a bunch of clever tricks: using the full Unicode range for “characters” (Chinese, etc.) to squeeze a few more bits’ worth, representing colours as blends of just 8 colours (3 bits!), and arriving at a Voronoi triangulation through a genetic algorithm:

“Mona Tweeta” © Quasimondo:Flickr/CC-BY-NC (210 bytes?)

The one on the right is the real Mona Lisa, and the left one is what fits in 140 characters, specifically the message: “圑嘌婂搒孵怤實恄幖戰怴搝愩娻屗奊唀唭嚟帧啜徠山峔巰喜圂嗊埯廇嗕患嚵幇墥彫壛嶂壋悟声喿墰廚埽崙嫖嘵奰恛嬂啷婕媸姴嚥娐嗪嫤圣峈嬻尤囮愰啴屽嶍屽嶰寂喿嶐唥帑尸庠啞彐啯廂喪帄嗆怠嗙开唅恰唦慼啥憛幮悐喆悠喚忐嗳惐唔戠啹媊婼捐啸抃岖嗅怲幀嗈拀唹坭嵄彠喺悠單囏庰抂唋岰媮岬夣宐彋媀恦啼彐壔姩宔嬀”

This is pretty impressive, you’d think, for 140 characters. But it gets better. Brian Campbell started a contest on Stack Overflow, and some brilliant approaches turned up.

Boojum wrote a nanocrunch.cpp, based on fractal compression, which can do this (on the left is the original, for comparsion):

by Boojum (490 bytes)

Sam Hocevar wrote img2twit, which segments the image into square cells and tries to randomly assign points and colours to them until something is close. It can do this:

img2twit by Sam Hocevar (250 bytes?)
You can watch a movie of the image evolving; it’s pretty cool!

There were also attempts at converting the image to a vector format and encoding that instead. Needless to say, it works well for vector-like images:
(almost perfect!)

but it’s hard to even convert some images to vector form:
by autotrace (before compression!)

Finally, this is how Dennis Lee’s record-holding “optimizing general-purpose losy image codec” DLI does:

Comparison: JPEG at 536 bytes, img2twit at 534 bytes, DLI at 534 bytes

Or if you want to be fair and compare at 250 bytes, here’s img2twit and DLI:

img2twit at ~250 bytes, DLI at 243 bytes

Amazing!

For silly amusement, you can read a liberal translation of the original message, or the Reddit thread with ASCII porn.

Disclaimer: I did not participate in any of this, and I know nothing about image compression, so no doubt there are errors in the above. Please point them out. All images are copyright the respective owners, and the quote in the first line is by Brian Campbell on Stack Overflow.

Advertisement

Reading aloud

There’s this poem, which you can read comfortably but trying to read which aloud is torture:

I take it you already know,
Of tough and bough and cough and dough.
Others may stumble, but not you,
On hiccough, thorough, laugh and through.
Well done! And now you wish, perhaps,
To learn of less familiar traps.

Beware of heard, a dreadful word,
That looks like beard and sounds like bird.
And dead: it’s said like bed, not bead —
For goodness’ sake, don’t call it ‘deed’!
Watch out for meat and great and threat,
(They rhyme with suite and straight and debt).

A moth is not a moth in mother,
Nor both in bother, broth in brother.
And here is not a match for there,
Nor dear and fear for bear and pear.
And then there’s dose and rose and lose –
Just look them up – and goose and choose.
And cork and work and card and ward,
And font and front and word and sword.

And do and go and thwart and cart –
Come, come, I’ve hardly made a start!

A dreadful language? Why man alive!
I’d mastered it when I was five.

Alternative last verse:

A dreadful language? Why, man alive!
I’d learned to talk it when I was five.
And yet to write it, the more I tried,
I hadn’t learned it at fifty-five.

So this poem is about spelling not corresponding to pronunciation and vice-versa. Wikipedia cites it as “From a letter published in the London Sunday Times in 1965 […] The author was only listed by T.S.W.”, but it’s at least as old as 1961, possibly much older.

The other poem is called The Chaos, and it’s by the Dutch teacher Gerard Nolst Trenité, illustrating how impossible it is to deduce pronunciation from spelling. It makes you doubt the pronunciation of many words you think you know. :-) He first published it in 1920, with 164 lines, and revised it many times until his death in 1946 (274 lines). It’s quite painful to read, so skim when it gets unbearable and save the rest for another sitting. Prof. David Madore has a version here, with the first few verses in IPA for AmE and BrE. What follows is a random excerpt only!

Dearest creature in creation
Studying English pronunciation,
I will teach you in my verse
Sounds like corpse, corps, horse and worse.

I will keep you, Susy, busy,
Make your head with heat grow dizzy;
Tear in eye, your dress you’ll tear;
Queer, fair seer, hear my prayer.
[…]
Sword and sward, retain and Britain
(Mind the latter how it’s written).
Made has not the sound of bade,
Say—said, pay—paid, laid but plaid.

Now I surely will not plague you
With such words as vague and ague,
But be careful how you speak,
Say: gush, bush, steak, streak, break, bleak,
[…]
Say, expecting fraud and trickery:
Daughter, laughter and Terpsichore,
Branch, ranch, measles, topsails, aisles,
Missiles, similes, reviles.
[…]
Billet does not end like ballet;
Bouquet, wallet, mallet, chalet.
Blood and flood are not like food,
Nor is mould like should and would.
[…]
Liberty, library, heave and heaven,
Rachel, loch, moustache, eleven.
We say hallowed, but allowed,
People, leopard, towed but vowed.
[…]
Stranger does not rhyme with anger,
Neither does devour with clangour.
Pilot, pivot, gaunt, but aunt,
Font, front, wont, want, grand and grant.
[…]
Say inveigh, neigh, but inveigle,
Make the latter rhyme with eagle.
Mind! Meandering but mean,
Valentine and magazine.
[…]
Don’t be down, my own, but rough it,
And distinguish buffet, buffet;
Brood, stood, roof, rook, school, wool, boon,
Worcester, Boleyn, to impugn.
[…]
Nor are proper names included,
Though I often heard, as you did,
Funny rhymes to unicorn,
Yes, you know them, Vaughan and Strachan.
[…]
Please don’t monkey with the geyser,
Don’t peel ‘taters with my razor,
Rather say in accents pure:
Nature, stature and mature.
[…]
Though the difference seems little,
We say actual, but victual,
Seat, sweat, chaste, caste, Leigh, eight, height,
Put, nut, granite, and unite.
[…]
Say aver, but ever, fever,
Neither, leisure, skein, receiver.
Never guess—it is not safe,
We say calves, valves, half, but Ralf.

Starry, granary, canary,
Crevice, but device, and eyrie,
Face, but preface, then grimace,
Phlegm, phlegmatic, ass, glass, bass.
[…]
Mind the O of off and often
Which may be pronounced as orphan,
With the sound of saw and sauce;
Also soft, lost, cloth and cross.

Pudding, puddle, putting. Putting?
Yes: at golf it rhymes with shutting.
Respite, spite, consent, resent.
Liable, but Parliament.

Seven is right, but so is even,
Hyphen, roughen, nephew, Stephen,
Monkey, donkey, clerk and jerk,
Asp, grasp, wasp, demesne, cork, work.
[…]
Pronunciation—think of Psyche!—
Is a paling, stout and spiky.
Won’t it make you lose your wits
Writing groats and saying ‘grits’?

It’s a dark abyss or tunnel
Strewn with stones like rowlock, gunwale,
Islington, and Isle of Wight,
Housewife, verdict and indict.

Don’t you think so, reader, rather,
Saying lather, bather, father?
Finally, which rhymes with enough,
Though, through, bough, cough, hough, sough, tough?

Hiccough has the sound of sup.
My advice is: GIVE IT UP!

There’s another version here. More poems here.

All of which reminds me of the following story about reading aloud. In the 4th century, where apparently it was common practice for everyone to read aloud, St. Augustine encountered a man (Bishop Ambrose) who read silently! He didn’t even move his lips! You couldn’t hear his voice while reading even if you stood very close to him! As Augustine reports (and it’s a matter of debate whether in amazement or in distaste):

When he read, his eyes scanned the page and his heart sought out the meaning, but his voice was silent and his tongue was still.

(Might want to take a look at this chapter from Alberto Manguel’s A History of Reading.)
But James Fenton disagrees: see The Guardian, Saturday 29 July 2006:

It is a myth that the ancients only or normally read out loud – a myth we appear to want to believe, since the evidence against it is strong. […]
Manguel shamelessly fudges the argument.

In order to read aloud well, especially when a text is written without breaks between words (as was classical practice), it seems important to possess the gift to read ahead simultaneously. Silent reading is a necessary adjunct to the kind of reading aloud for sound and sense Nietzsche admired. What shocked Augustine was that Ambrose read silently in front of visitors and refused to share his reading matter, and his thoughts, with them. But Augustine was perfectly capable of silent reading, and describes a key moment in his conversion as a moment of silent reading with a friend.

Finally, if I may rant again about spelling pronunciation: the character ~ is written “tilde”, but I wish people would stop calling it “till-day” or “tilled”! It is pronounced “til-duh”, as in the Australian ballad: “Waltzing Ma~, Waltzing Ma~…” or the name of the actress ~ Swinton (literally?)

TODO: Read about “the very notion of silent, individualized reading is scarcely known prior to the advent of the printing press (Goody and Watt: 42)” That’s Goody, Jack, and Watt, Ian, 1968, “The Consequences of Literacy.” In Literacy in Traditional Societies, edited by Jack Goody, pp. 27-68. Cambridge University Press. This is from Thomas Coburn, “Scripture” in India: Towards a Typology of the Word in Hindu Life, p.437. He goes on:

there has never been a happy marriage between the holy words of India, composed and transmitted orally, and the writing process. Particularly in contrast with, say, China, scribes in India have been of low social standing (Lancaster: 224-25), and the very act of writing was held to be ritually polluting: a late “Vedic text, the Aitareya Aranyaka (5.5.3) states that a pupil should not recite the Veda after he has eaten meat, seen blood or a dead body, had intercourse or engaged in writing” (Staal, 1979:122-23). The profoundly spoken character of India’s holy words is a matter on which we will reflect below, but for the moment it will suffice to note that we should not be misled by the fact that most of these words have eventually found their way onto the written or printed page. This is not their primary home, and Staal is not simply being mischievous in discerning a symbolic significance to the fact that Indian books “still tend to fall apart” (1979:123).

mplayer: changing speed without changing pitch (avoiding the chipmunk effect)

In mplayer, you can change the playback speed with [ or ], but that probably changes the pitch as well (naturally). Can be amusing the first time, but not after you realise that it is actually possible to do something sophisticated to avoid this. (Wikipedia calls it Audio timescale-pitch modification) Many other media players (including VLC and even Windows Media Player(?)) can do this automatically; here’s how to do it in mplayer.

Short answer:

Start mplayer as mplayer -af scaletempo
That’s it. The catch is that you need to get an mplayer which has the scaletempo filter, and we know how much the mplayer project loves making releases. (It’s not in Ubuntu at the time of writing.)

So, either

Get such an mplayer
e.g the deb from Sourceforge (here),

or

Start mplayer as mplayer -speed 1.5 -af ladspa=tap_pitch:tap_pitch:0:-33:-90:0 foo.avi

Seems even the latter might require installing the ladspa plugins.

For more on all this, see:

1. blog comments (with patches) at Pitch-Correct Play Speed with MPlayer
2. Change MPlayer Playback Speed
3. Mplayer FAQ: “How do i change mplayer speed but keep pitch the same?”

First thoughts on Google Wave

Just saw the demo for Google Wave. It’s impressive and ambitious. It’s hard to describe, but it’s a collaborative real-time thing (think Google Docs for everything) that can work like email, IM, blogs, forums, whatever you want — and can be embedded into, or integrates with, apparently everything: Orkut, Blogger, Google Maps, Google Code (the bug tracker), Twitter, etc. (They’ve already fulfilled the annoying-word requirement, by creating “twave”.)

They say it’s a “product, platform and protocol”.

I can see myself using this. (And thinking of the privacy implications (or the having-your-data-out-there-in-the-cloud-somewhere implications), it’s bloody scary.)

They’ve got pretty amazing sync. Search results and messages get updated in real time character-by-character, and the latter seems to make people cheer as if they’ve never seen good old talk.

Finally someone had the “playback” idea I have been trying to propose for years. (I was calling it the “undo bar” or “edit history bar”, or more recently “Time Machine for Emacs”, but whatever.) You can “play back” the edit history of a document (“wave”), seeing what changes each person made and in what order, and when the “wave” is a chess game, you can play back the chess game. Perfect.

They variously say it will be open-sourced, or that “a lion’s share of the code” will be open-sourced, but let’s hold off believing that until we see it. It’s extensible, so you can add your plugins to it. It’s a protocol, so you can write your own implementations of it. It’s a platform, so you can run it on your own servers. Now someone add a LaTeX compiler to it, and collaborative work with LaTeX will finally be possible.

If you have 80 minutes to spare, here’s the video, or an article at TechCrunch.