Due: &run-length-encoding-due; Summary: In this assignment, you will explore techniques for efficiently (or not so efficiently) writing images to files. Purposes: To give you more experience with input and output. To help you think more about tradeoffs between speed, size, and clarity. Expected Time: Two to three hours. Collaboration: We encourage you to work in groups of size three. You may, however, work alone or work in a group of size two or size four. You may discuss this assignment with anyone, provided you credit such discussions when you submit the assignment. Submitting: Email your answer to &grader-email;. The title of your email should have the form &run-length-encoding-subject; and should contain your answers to all parts of the assignment. Scheme code should be in the body of the message. Warning: So that this assignment is a learning experience for everyone, we may spend class time publicly critiquing your work.

Over the past few classes, we have been exploring how one stores information about an image in in a file so that the image can be restored. As we've noted, there are a number of criteria one considers in designing a file format, including the file size for images, the accuracy of the representation, the computational cost of saving and restoring image files, the difficulty of writing the algorithms to save and restore files, and even the human readability of these files. So far, we have focused on a set of techniques in which we write one value for each pixel in the image, which means that our primary focus was on how little space one uses per pixels. However, if our concern is file size, we can achieve some improvement by storing sequences of pixels, rather than individual pixels. In this technique, which is called run-length encoding, when you have a sequence of pixels of the same color, you write one entry for all the pixels, rather than a separate entry for each pixel. Suppose the first five pixels in an image are purple. We would write the color purple and then the number 5. When reading the image back from a file, we read in color and number of repetitions, fill in that many pixels, and then go on to the next color/count pair. For example, consider a mostly-black 5x5 image with a single white pixel in the center. This image has 12 black pixels in sequence (five in the first row, five in the second row, two in the third row), one white pixel, and then another 12 black pixels (two more in the third row, five in the forth row, and five in the fifth row). We might represent this image as 5 5 0 0 0 12 255 255 255 1 0 0 0 12 Of course, nothing (other than our desire to produce the smallest file possible) says that we have to continue pixels from one row to the next. Hence, we could also represent the image as 5 5 0 0 0 5 0 0 0 5 0 0 0 2 255 255 255 1 0 0 0 2 0 0 0 5 0 0 0 5 In fact, we could even represent each pixel separately (which gives us a larger file than we would have otherwise). 5 5 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 255 255 255 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 How can we read such a file back into an image? We might use a procedure like the following.

Write (image-run-length-encode image filename), which writes an image to the specified file using run-length encoding. You can use the following strategy. To write the image, we iterate through both columns and rows (see image-run-length-decode for some ideas). While writing, we keep track of not only the current row and column, but also the most recent color encountered and the number of pixels we've already seen with that color. As we arrive at each pixel, we look at its color. If the current pixel's color is the same as the previous color, then we increment the count for that color and go on. If the current pixel's color is different from the previous color, we write the previous color and count, and continue with the new color and a count of 1. When we run out of pixels to write, we write the final color and count. Important hint: The obvious algorithm is to compare the color of each pixel to the color of the next pixel to the right, but this results in a lot of special cases for when you reach the end of a row or the end of the image. It gets complicated very quickly. Instead, think about comparing the color of the current pixel to the previous color, as suggested above. When using this strategy, think carefully about the initial values for the column, row, color, and count. You can assume the image contains at least one pixel.

Before beginning to write image-run-length-encode, you should make sure that you understand both the image file format and the instructions in image-run-length-decode. Try reading in the sample images. Modify a few lines and see the effect. Write a few files by hand and read them in. You should also make sure that you understand how pixel maps work. If not, go over the labs on pixel maps again.

Our first criterion in evaluating your assignment will be your success in writing a file that can be read back into the image using the algorithm above (even if the file is not as small as it could be). Our second criterion will be file size: Are you able to write the smallest possible file. Our third criterion will be elegance: Is your code clear and concise. Note: While we would probably use run-length encoding with the most efficient color representation, for the purposes of this assignment it is fine to use one of the human-readable representations. That is, you can choose whichever implementations of rgb-write, rgb-read, integer-write, and integer-read that you wish. Please include those implementations with your assignment.