Image Compression

Key question

What is it that digital displays actually store so you can see what's being displayed?

What are pixels?

picture elements

pixel

(an element is a part of something)

Pixels in black and white

How could a computer store this image as numbers?

How could a computer record this image using just numbers? We’ve added a grid to give you some ideas. Share your ideas in the chat.

Monitor the chat and respond appropriately.

Potential answers include:

Saying 'black' and 'white' or variations of this, including 0 and 1 as binary digits.
Counting the number of black and white squares (pixels) and representing these with different notations such as W1, B3, W1 - this is the point where students are thinking about compressing their data.
Prompt students to discuss if we need some conventions, like where to start, do we go left to right, left down, right down, right to left? If we all agreed the first pixel was always white, what compression code could we create?

We’ve just discussed run-length encoding

There were some great ideas there. One way computers store images is by using run-length encoding. This is a form of compression, it makes the information take up less room when it is stored and transmitted. Each line of an image is described by how many pixels of each colour (runs) are used. For example, row A of this image would be 4, 2, 2. Row B would be 3, 1, 2, 1, 1.

What is the next line of code? Share your answer in the chat.

Wait until someone types in 3, 1, 2, 2.

Well done ___ (participant who wrote the correct code), you got it! This code uses the assumption that the first pixel is always white. How can we represent row D of this image using this convention? Put your suggestions in the chat.

Wait for a few suggestions.

Row D starts with a black pixel. But if we say the code is 1, 3, 2, 2 then the computer will think the first square is white. The rule is that the first number always states how many white squares there are. This is because most margins are white. So the code for row D is 0 (no white squares), 1, 3, 2, 2.

Let’s have a go at coding the rest of this image. Choose a row of the image and write the code for it in the chat. Remember to include what line your code is for!

Wait until each line has been coded. You may need to allocate lines to individuals.

Completed run-length encoding

I'm going to create the number 8 in this interactive. It will automatically show the run length code for each line. Watch and see if it follows the same rules as we established before.

Click on the grid to create the number 8 using the following pattern, but stop before the last line>. You can discuss what is happening with the codes and patterns with the group. You can either click on the pixels, or type in the codes on the right.

⬜⬛⬛⬛⬜
⬜⬛⬜⬛⬜
⬜⬛⬛⬛⬜
⬜⬛⬜⬛⬜
⬜⬛⬛⬛⬜

In the chat, type the code that you think is needed to finish the last line with three black pixels to finish off an image of the number 8.

Hopefully most will type in "1,3,1", which they may recognise from the earlier lines. Go ahead and enter the final line.

What is it that digital displays actually store so you can see what’s being displayed?

This exercise also shows the importance of agreeing on standards for compressed files, so that a file compressed on one computer can be decompressed on another. In this case, you need to know the order (left to right), and that the first pixel in each row is white. The version of run-length encoding (RLE) used in this exercise above only works well for black and white images, and isn’t so good for photographs, because the level of colour detail is so accurate that it’s very unlikely that two adjacent pixels are exactly the same colour.

A different method, called JPEG, works particularly well for colour photos. It finds patterns in the variations of the colours in a photo, and converts the patterns to numbers that are then compressed using RLE. Both JPEG and MP3 allow images and sound to be recorded on one brand of equipment and played back on a variety of devices.

The form of run-length encoding used in this exercise is most related to the technique used by fax machines, which are based on black and white scanning, but a modified version of RLE is also used in JPEG images.

Supporting Resources

CS Unplugged - Squeezing pictures into less space
https://www.csunplugged.org/en/topics/image-representation/squeezing-pictures-into-less-space/
CS Unplugged - Run Length Encoding worksheets
https://www.csunplugged.org/en/resources/run-length-encoding/
CS Unplugged at Home - Squeezing pictures
https://www.csunplugged.org/en/at-home/squeezing-pictures/
CS Unplugged - Colour by numbers
https://www.csunplugged.org/en/topics/image-representation/colour-by-numbers/
Computer Science Field Guide - Data Representation - Images and Colours
https://www.csfieldguide.org.nz/en/chapters/data-representation/images-and-colours/
Computer Science Field Guide - Pixel Viewer
https://www.csfieldguide.org.nz/en/interactives/pixel-viewer/
CS Unplugged - Video 1 - Run Length Encoding
https://www.youtube.com/watch?v=VsjpPs146d8
CS Unplugged - Video 2 - Run Length Encoding
https://www.youtube.com/watch?v=uaV2RuAJTjQ

Here are some supporting resources for you. I'll paste these links in the chat.

                            CS Unplugged - Squeezing pictures into less space
                            https://www.csunplugged.org/en/topics/image-representation/squeezing-pictures-into-less-space/
                        
                            CS Unplugged - Run Length Encoding worksheets
                            https://www.csunplugged.org/en/resources/run-length-encoding/
                        
                            CS Unplugged at Home - Squeezing pictures
                            https://www.csunplugged.org/en/at-home/squeezing-pictures/
                        
                            CS Unplugged - Colour by numbers
                            https://www.csunplugged.org/en/topics/image-representation/colour-by-numbers/
                        
                            Computer Science Field Guide - Data Representation - Images and Colours
                            https://www.csfieldguide.org.nz/en/chapters/data-representation/images-and-colours/
                        
                            Computer Science Field Guide - Pixel Viewer
                            https://www.csfieldguide.org.nz/en/interactives/pixel-viewer/
                        
                            CS Unplugged - Video 1 - Run Length Encoding
                            https://www.youtube.com/watch?v=VsjpPs146d8
                        
                            CS Unplugged - Video 2 - Run Length Encoding
                            https://www.youtube.com/watch?v=uaV2RuAJTjQ