Compression Algorithms

Introduction

Why do we need compression?

Today’s modern smartphones have huge amount of storage, so why do we need compression? Let’s find out.

Question 1a

An iPhone camera has a resolution of 12 Megapixels and each pixel requires 3 bytes to store the image. How big would would an uncompressed image be?

Hint: Mega = million

Answer

12,000,000 x 3 = 36,000,000 Bytes

Question 1b

If an iPhone has a storage capacity of 32 Gigabytes, how many images could you store on it before you ran out of space?

Hint: Giga = Billion

32,000,000,000 / 36,000,000 = 888 photos

That means that without compression you would run out of space before you even took a thousand selfies….

Question 1c

Now image recording videos – A normal video would record 24 frames per second. Assuming your iPhone recorded at 4K resolution (3840×2160 pixels). How long could you record for before running out of space?

3840 x 2160 =    8,294,400 (Calculate the total number of pixels)

8,294,400 x 3 = 24,883,200 Bytes per frame (Calculate the total number of bytes)

24,883,200 x 24  = 597,196,800 Bytes per second (multiply by 24 to get how many bytes per second)

32,000,000,000 / 597,196,800 = 53.5 seconds!

And we haven’t even including recording the sound…

As you can see without compression your phone wouldn’t be very useful.

 

Run Length Encoding

Run Length Encoding (RLE) compression

Placing a grid overlay over a B&W image

Run length encoding works by identifying runs of identical data and recording the data, together with the number of pixels that it represents.

Take a look at the black and white sad image.

If we were to store this image matrix as text it would be (starting from the top-left and working line by line)

Uncompressed

wwwwwwwwwbbwwbbwwbbwwbbwwwwwwwwwwwwwwwwwwbbbbbbwwbwwwwbwwwwwwwww

We can compress this image by writing the length of the run of data followed by the data itself.

Compressed

9w2b2w2b2w2b2w2b18w6b2w1b4w1b9w

Here you can see that we have compressed the data by over 50% without losing any of the data. This form of compression was widely used to compression data when sending data via a fax machine, as all faxes are black and white.

If we wanted to we could reconstruct the original data using the compressed run length data. Compression where you can reconstruct the original data from the compressed data is known as lossless compression.

 

 

Activity

Activity

Have a go at creating a smiley face in the grid bow below!

Can you right down a compressed version of the image that you created using run length encoding?

Learning Log

Learning Log

You should now complete your learning log for today’s lesson.

 

Extension task

  • LZ compression
  • Huffman encoding

Resources