Information Theory without the Theory: Pixel Fun, for everyone!

cover This is Part Two of a multi-part series in where I go into the basics of Information Theory. In Part One, I gave a basic run-down of what Information Theory involved, and an introduction to Compression. While I don't think you'll have to look at it for this post, it would make some of what I post here make sense.

"Jack, you didn't teach us nothin' about how you got the magic numbers for your Chemist vs Menswear example. How can I do my own compression if I don't know how to make magic numbers?!"

Ahh! I'll teach you, but there are a couple things you need to know beforehand - they're not boring, I promise, but they'll make what you see seem a little more nutty than they would otherwise!

This week, we'll look at the difference between a Lossless and a Lossy compression, and yes, they are exactly what they sound like.

Slinky Malinky

Take a slinky, you know, those spring-like coils of wire that you always got tangled up and could never undo. Well, assuming that you haven't already tangled it, pull it out. If you let go, it goes back into its coil form, right? However, if you pull it out again, you know it's exactly as it was the first time you pulled it out. If we replace the wire for bits of information, we get something known as Lossless Compression. Lossless compression is when we compress a piece of information using a particular algorithm that, when required, we can decompress the data in such a way that it is converted back to the original, same as the slinky. You use lossless compression in your everyday computing: .zip, .png and .flac are all examples of lossless formats.

But, where would we be without some examples?

Take this image:

Disregarding the blue about the outside, we have a black and white, 16 x 16 image. In a raw form, each of our pixels on the top-most line (left to right) would be stored something like this:

(0 0 0)(0 0 0)(255 255 255)(0 0 0)(0 0 0)(0 0 0)(0 0 0)(0 0 0)(0 0 0)(0 0 0)(0 0 0)(0 0 0)(255 255 255)(0 0 0)(0 0 0)(0 0 0)

Hmm. We have a poopton of (0 0 0) , or Black pixels there in a row. What if we did this?

(2(0 0 0))(1(255 255 255))(9(0 0 0))(1(255 255 255))(3(0 0 0))

Boom, immediately you see it is much smaller than what it was.

So, the first number within brackets gives the length of the pixels, and the next set of brackets are the colour. Immediately we have reduced the size of our image from 384 bits to 160 bits, over 50% smaller than our original line (excluding the brackets)!

Note: Although 255 and 0 are, well, 255 values apart, colours are stored in 8 bit blocks, or, 1111 1111 (255) and 0000 0000 (0) take up exactly the same amount of room in your computer. So while it takes more characters to type out 255, in reality, they're the same size!

This method is called Run Length Encoding, and is perhaps one of the most basic algorithms you can run over an image. In fact, it's a component of many more popular methods, but you can see it's error. Say we had a checkerboard pattern, alternating pixels were alternating colours - what space would we be saving then? We'd probably end up storing more information.

There are many more lossless algorithms for use in images, such as PNG, however the algorithm (or algorithms) and the methods behind them are really complex, and I don't reeealllly want to go boring your socks off. If you have time, then look up what is actually stored in one - Wikipedia, once again, does awesome at this.

Car Cube

Going from Slinky's, hows about a Car Crusher?

You're working at the local scrap yard and you have been tasked with crushing this soccer-mum style car. Before it is placed within the large plates designed to turn it into a cube, you notice it's about 3m x 2m.

Going with your childish desires, you smash that car up, smash it good, and what you're left with is a cube 1m x 1m. Say you had magic-hands and you could try and decompress the heap of metal, however if you try, it just wont be the same. Connections will be broken, and it'll still look like it's been through hell - it just wont be the same, you'd have lost things.

Once again, change out the car for our information, and the crusher for a compression algorithm, and you get Lossy Compression. Lossy compression is ideal for when you want the absolute minimal size possible, by discarding quality slightly for less space. However, its application is really only in media, such as audio and video - run lossy compression on something like a contract, and... you see the point.

There isn't really any description I can give for a lossy algorithm like I did for RLE, but I can give examples on how one might work:

Take JPEG for one, or the Joint Photographic Experts Group (bet you didn't know what that meant) format.

The way JPEG works is that it drops some of the colour and blends it in with the pixels around it, so saving space and slightly decreasing the quality of the image. The image below decreases compression from left to right, so the rightmost side has the least compression (highest quality)

Note: Since JPEG's release in 1992, there have been versions of it that support Lossless compression, however, most of the time it does Lossy.

Compression Battle Royale

So I went and made a bitmap file.

Made to the dimensions that were given to me when I opened up MS Paint, It is 1152 pixels x 648. As you can see, in raw .bmp bitmap form, it is 2.13MB! Loading this raw image on any page in New Zealand would definitely take 3-5 seconds.

Now, if we save it simply using the Paint PNG feature, we get the following image:

4.32kB! Four. Kilobytes!

I feel like I should explain myself here: The problem with compression formats is the fact the image requires metadata, this is information related to the algorithm used and the information about the image (where and when it was made), which takes up more of the space, but think about it - We went from 2.21MB (2210 kB) to 4kB. Thats 500 times smaller! It's a healthy trade, to be fair.

Lastly, here we have a Lossy compression, JPEG. I really went all out with this one and used Photoshop to create the smallest version of this image I could:

Look at that 2.57kB, we almost got half the size of our already pretty packed PNG version!

Ooo. Technology.

I think I'll leave it there for this week. Next week, I want to look at Huffman Coding, personally one of my favourite compression methods to do as it's easy to run through. If you want to see more on how compression can mess with videos, take a look at this- a guy has uploaded/downloaded the same video 1000 times, and it shows what happens to the information stored in the video over each cycle.

Once again, you can follow me on twitter @rack_jobinson, I still haven't tweeted, but I'm still understanding the balance between it and Snapchat. Also, comment below! Yes, I worked out how to make that work, so if there is something not right, let me know - I'm prone to mistakes!