{"id":100,"date":"2021-03-31T02:28:57","date_gmt":"2021-03-31T02:28:57","guid":{"rendered":"http:\/\/learnlearn.uk\/algorithms\/?page_id=100"},"modified":"2021-05-10T23:56:10","modified_gmt":"2021-05-10T23:56:10","slug":"compression-algorithms","status":"publish","type":"page","link":"https:\/\/learnlearn.uk\/algorithms\/compression-algorithms\/","title":{"rendered":"Compression Algorithms"},"content":{"rendered":"
\n

Introduction<\/h2>\n
\n\n

Why do we need compression?<\/h3>\n

Today’s modern smartphones have huge amount of storage, so why do we need compression? Let’s find out.<\/p>\n

Question 1a<\/strong><\/p>\n

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?<\/p>\n

Hint: Mega = million<\/em><\/p>\n

<\/i>Answer<\/div>
\n

12,000,000 x 3 = 36,000,000 Bytes<\/span><\/p>\n<\/div><\/div>\n

Question 1b<\/strong><\/p>\n

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

Hint: Giga = Billion<\/p>\n

<\/i><\/div>
\n

32,000,000,000 \/ 36,000,000 = 888 photos<\/span><\/p>\n<\/div><\/div>\n

That means that without compression you would run out of space before you even took a thousand selfies….<\/p>\n

Question 1c<\/strong><\/p>\n

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?<\/p>\n

<\/i><\/div>
\n

3840 x 2160 =\u00a0 \u00a0 8,294,400 (Calculate the total number of pixels)<\/p>\n

8,294,400 x 3 = 24,883,200 Bytes per frame (Calculate the total number of bytes)<\/p>\n

24,883,200 x 24\u00a0 =\u00a0597,196,800 Bytes per second (multiply by 24 to get how many bytes per second)<\/p>\n

32,000,000,000 \/ 597,196,800 =\u00a053.5 seconds!<\/span><\/p>\n

And we haven’t even including recording the sound…<\/p>\n<\/div><\/div>\n

As you can see without compression your phone wouldn’t be very useful.<\/p>\n

 <\/p>\n\n<\/div>

Run Length Encoding<\/h2>\n
\n\n

Run Length Encoding (RLE) compression<\/h3>\n
\"\"

Placing a grid overlay over a B&W image<\/p><\/div>\n

Run length encoding works by identifying runs of identical data and recording the data, together with the number of pixels that it represents.<\/p>\n

Take a look at the black and white sad image.<\/p>\n

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

Uncompressed<\/strong><\/p>\n

wwwwwwwwwbbwwbbwwbbwwbbwwwwwwwwwwwwwwwwwwbbbbbbwwbwwwwbwwwwwwwww<\/span><\/p>\n

We can compress this image by writing the length of the run of data followed by the data itself.<\/p>\n

Compressed<\/strong><\/p>\n

9w2b2w2b2w2b2w2b18w6b2w1b4w1b9w<\/span><\/p>\n

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

If we wanted to we could reconstruct the original data<\/strong> using the compressed run length data. Compression where you can reconstruct the original data from the compressed data is known as lossless<\/strong> compression.<\/p>\n

 <\/p>\n

 <\/p>\n\n<\/div>

Activity<\/h2>\n
\n\n

Activity<\/h3>\n

Have a go at creating a smiley face in the grid bow below!<\/p>\n