Imaging & Data Compression

Unit Objective: This unit is designed to introduce the concept of binary imaging and the basic idea of data compression. Although the activities were written for an Algebra 2 course, they could easily be adapted for other courses.

Activity 1: “Tim” Activity: Making Images from Pixels

Objective: Students will make images using pixels and use binary to represent the pixels.

Wyoming Standards:     Math 1.1-Students represent and apply real numbers in a variety of forms.
Math 1.2-Students apply the structure and properties of the real number system.
Sci 2.2-Students use inquiry to conduct scientific investigations.

Materials Needed: Quarter sheets of graph paper, computer with projector, overhead, handouts

Time: 15 minutes

Directions: Find a picture to display on the computer projector. Magnify or Zoom In on the picture using image software such as Picture Viewer or Word to show the individual pixels that create the image. (Note: This is not new to most students, it is just a way to get them to focus on the topic).

Show the students an empty 11x5 grid on the overhead. A transparency copy of the teacher example will work great. Use a marker to create an image of your choice. We will use “Tim” for our image. Explain how each picture element (pixel) has a value as either white or black.

Using the grid next to your “Tim” image transfer all of the values using “0” for white and “1” for black.

Next give the students the handout. On the sheet there is a list of 0's and 1's. They should be able to easily transfer the data into a grid and color in the “1” cells to get the desired image from the binary data.

Give the students a quarter piece of graph paper and tell them to make a 11x5 rectangle on the box. Each student can then quickly make an image of their choice. They should keep their image secret from the other students.

Now have the students create a binary data set (list of 0's and 1's) for their image using the handout. When they are finished they can exchange their data set with a friend. The friend can then use the bottom grid to try to guess what the image looks like.

Handout

Example 1

Row 1:  0 1 1 1 0 0 1 0 1 0 0        Row 2:  0 0 0 1 0 0 1 0 1 0 0
Row 3:  0 1 1 1 0 0 1 1 1 0 0        Row 4:  0 1 0 0 0 0 0 0 1 0 0
Row 5:  0 1 1 1 0 0 0 0 1 0 0

Make Up Your Own Binary Data Set

Row 1:  ___________________________    Row 2:  ___________________________

Row 3:  ___________________________    Row 4:  ___________________________

Row 5:  ___________________________

“Tim” Sample for Teacher

Activity 2: CCD's and Digital Data

Objective: The students will explore how some telescopes and digital cameras work using CCD's. The students will understand how a data stream can be set up to “send” images.

Wyoming Standards:     Math 1.1-Students represent and apply real numbers in a variety of forms.
Math 1.2-Students apply the structure and properties of the real number system.
Sci 2.2-Students use inquiry to conduct scientific investigations.

Materials Needed: Post-it notes, quarter piece graph paper, overhead with grid

Time: 25 minutes

Related Links: Space Place “Pixel This” http://spaceplace.nasa.gov/en/educators/teachers_page2.shtml

Directions: Have a student volunteer come up to the front and create an image on a small grid. The small grid should be the same size as the grid which makes up your classroom desks. DO NOT INCLUDE THE FRONT ROW! They will become your registers. Make sure you include all the other desks even if nobody is sitting there. This is also a good time to point out that for this activity rows go across just like on a spreadsheet or in seats at a ball game or in an auditorium.

For example if you have a 4x6 setup for your desks, the student volunteer would make a mystery image that is only 4x5.

While the student is making the image have the other students each take one post-it note except for the front row. For our example all of the desks in the 4x5 grid will have a post-it note even if it is an empty desk.

Once the student has the mystery image done he or she will transfer the image to the post-it notes one pixel at a time. If the upper left pixel is filled in on the image, the student will tell the person sitting in the back-left desk to write “1” on their post-it note. If the pixel is empty, they would tell the students to write “0”. Repeat this process for all of the post-it notes. For our example there would be 20 post-it notes since the grid is 4x5.

Next the teacher will have to explain how a CCD gathers the image data once the image is recorded. The front row was intentionally left empty because they become the registers for collecting the data. Since each desk represents a single register keep in mind that a register can only hold one piece of data (a post-it note) at a time. Also the data stream can only be read by a computer chip one piece of data (a post-it note) at a time. To make this easier to see project a grid onto the board that has columns labeled with letters and rows labeled with numbers, the same as a spreadsheet.

To move data a CCD transfers data one row at a time, then reads each of the row entries one at a time. To show this have each person in Row 2 hand their post-it note forward one place. Next have Row 3 hand theirs to Row 2. Next have Row 4 hand theirs to Row 3. Make sure each row does this separately because each register (each desk) can only have one piece of data (one post-it) at a time.

Now that we have all the data moved forward one row, we can work on reading the individual post-its. Again remind the students that only one post-it can be at a desk at a time. To read the data to our image data collector on the board (you can pick one of the back row students to be the image data collector), have the student who is at the front-right hand it to the image data collector. This person can then put the post-it on the grid in the bottom-right cell which should correspond the where the post-it came from originally. In our example the first post-it came from cell D5 (or pixel D5). The front row people should hand their data to the right one desk at a time using the same method used for the rows: two post-its can NEVER be on the same desk at the same time. This is a data stream.

Once all of these are handed to the right and recorded by the image data collector, each row can then hand their post-it forward using the same process as before. The image data collector can then collect the post-its one at a time using the same process. Repeat each of the processes until the image is completed. It should look like a grid of 1's and 0's just like Activity 1. The students can then return to their seats.

The teacher should point out that a 1 megapixel (approximately 1 million pixels) image is formed by an CCD that is 1024x1024. Thus the image data collector would have to record over 1 million pieces of data to recreate the image. Modern CCD's used in telescopes and cameras are well beyond 1 megapixel.

Activity 3: File Compression Using JFK Speech Example

Objective: The students will explore how to compress data using a simple algorithm.

Wyoming Standards:    Math 1.3-Students explain their choice of estimation and problem solving
strategies and justify results of solutions in problem-solving  situations
involving real numbers.
Math 4.5-Students connect algebra with other mathematical topics.
Sci 2.2-Students use inquiry to conduct scientific investigations.

Materials Needed: Markerboard and projector

Time: 25 minutes

Directions: Write the following on the board:

This is a famous line from John F. Kennedy's 1961 inaugural address. Have the students count how many characters it contains. Characters will include letters, numbers, spaces, and punctuation marks. The quote has 17 words, made up of 61 letters, 16 spaces, one dash and one period. If each character  takes up one unit of memory, we get a total file size of 79 units.

To get the file size down we need to look for repeat patterns or “redundancies”. Students should notice that most of the words are used twice. We can create a “dictionary” as follows:

2  what
3  your
4  country
5  can
6  do
7  for
8  you
Now we can rewrite the original quote as: “1 not 2 3 4 5 6 7 8 -- 1 2 8 5 6 7 3 4”

Our compressed sentence only has 37 characters or units, but we also have to save the dictionary with the file. Our compressed sentence plus dictionary has 74 units. We did not save much but this was for only one sentence. If you looked at the rest of the speech you would see these words many more times.

Emphasize to the students that the process of using the dictionary to code and decode is called an 'algorithm'. In math the word “algorithm” is defined as “a finite list of well-defined instructions for accomplishing some task.” They use algorithms anytime they follow directions or a set of steps.

Another way we could compress the quote is by looking for patterns within the words themselves. For example if we used “#” to represent “as”. The new quote would look like: "#k not what your country can do for you -- #k what you can do for your country."

Have the students create their own symbols to create a dictionary for compressing the quote. Ideas could include using “\$” for “ou”, using “%” for “you”, and using “&” for “t_” (or “t space”). Have the students share some of their ideas with the class.

Activity 4: Lossy vs Lossless Compression

Objective: The students will determine if a compression algorithm is lossy or lossless. The students will also see and hear examples of data compression.

Wyoming Standards:  Math 4.5-Students connect algebra with other mathematical topics.

Materials Needed: Computer projector and good speakers, image and sound files to compare

Time: 10 minutes

Directions: Show the students the following paragraph using a projector or overhead:

The mericn Blck Ber is the most common ber species ntive to North meric. It lives throughout much of the continent, from northern Cnd nd lsk south into Mexico, from the tlntic to the Pcific. This includes 41 of the 50 U.S. sttes nd ll Cndin provinces except Prince Edwrd Islnd.

Ask the students to try to read the sentence (hint: all of the “a”'s were removed.

The original sentence was:

The American Black Bear is the most common bear species native to North America. It lives throughout much of the continent, from northern Canada and Alaska south into Mexico, from the Atlantic to the Pacific. This includes 41 of the 50 U.S. states and all Canadian provinces except Prince Edward Island.

Project the original sentence next to the compressed sentence to show how much shorter is was. This type of compression is called “lossy” because some of the data is actually lost. The activities before used “lossless” compression thus none of the data was lost. Point out that lossy compression works when enough of the original data is left  to make a close replication of the original. We probably would not want to take out many more letters in our bear example.

You can now show the students examples of lossy compression. Wikipedia has a good set of images to compare. You can show the students examples of sound files. Play a piece of music from a CD then play the same piece from an mp3 player. Apple iTunes works well for this. You may have to play the piece back and forth a few times. You many also have to focus only on particular instruments or notes to notice the difference.

lossless (1 CD=32 songs=2:45)        lossy (1 CD=240 songs=20:00)
This is how so many songs can fit on an mp3 player.