%CustomEntities; %CourseEntities; %CommonEntities; ]>

Due: &palettes-due; Summary: In this homework, you'll write procedures to load images from files that were stored using a color palette. You'll write one version that uses lists to represent palettes and another version that uses vectors. Finally, you'll compare the speed of both versions. Purposes: To bring closure to our consideration of using palettes to store image data efficiently. To gain more experience using vectors. To compare the efficiency of lists and vectors in a (somewhat) realistic context. Expected Time: Three to four 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 &profemail;. The title of your email should have the form &palettes-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.

In the reading and lab on palettes, we considered the use of list-based palettes to let us store images using smaller files (at the cost of some inaccuracy in the stored image). In the reading on vectors, we started to consider how vector-based palettes would let us load images faster. In this assignment, you will write procedures to load images using both list-based and vector-based palettes, and compare the speed of the two methods. To be able to accurately reproduce an image using the palette approach, the file must contain not only a color index for each pixel, but also the list of colors that make up the palette. Here is an example of such a file: 3 0 0 0 128 128 128 255 255 255 4 4 0 0 0 1 0 0 1 2 0 1 2 2 1 2 2 2 Here's what's going on in this file: The first line indicates that there are three colors in the palette. The next three lines give the RGB components for those three colors. The fifth line contains the width and height of the image. The final line gives an index into the palette for each of the 16 pixels. What should the image look like? 0 corresponds to black, 1 to grey, and 2 to white. We should expect to see that the upper left of the image is black, the lower right is white, and there is a grey line dividing the two. Try drawing the image on paper to see.

a. Copy the sample data above into a new file and save the file as sample.pal. b. Copy and paste the supporting code at the end of this assignment into MediaScript. c. If you already have a list of colors to use as a palette, here is code to save an image using that palette. (You may have written similar procedures for the lab on palettes.) Copy and paste this code into MediaScript. Read it and make sure you understand what is going on. d. Use palette-save-image to save a very small (e.g., 8 pixel by 10 pixel) image of your choice, using a small palette of your choice (such as rainbow-plus from the lab on palettes). Verify that the file produced is similar to the example given in the preliminaries above. (The whitespace and newlines will be different.)

You may have noticed that we have had you work with very small images throughout the labs and assignments on storing image data in files. There are two reasons for this. First, small image files are easier for you to read and verify they are correct (or at least reasonable). Second, our procedures for reading and writing image data have thus far been very slow. This slowness is in part due to the time it takes to write small bits of data to a remote disk. But it is also due in part to the time required to get and set pixel colors using image-get-pixel and image-set-pixel!. These procedures hide several steps having to do with GIMP's internal representation and management of images: They must obtain a reference to the top layer of the image, tell GIMP that an editing operation is about to begin so that it can prepare the appropriate data structures, do the actual get or set, and then tell GIMP that the editing operation is over so that it can replace the old data with the new data. All this takes time. It's much faster if we obtain the top layer, tell GIMP once that we are going to begin editing, do all of our sets and gets, and then tell GIMP we are done. Three procedures you've used before, image-variant, image-transform!, and image-compute-pixels! encapsulate this strategy. These procedures let you modify all the pixels in an image much faster than you could by writing a procedure that does numeric recursion over the column and row. Let's consider the use of similar procedures to help us write and read pixmaps more quickly. The procedure (image-scan-region image proc left top width height) lets us iterate over all the pixels in an image, left to right and top to bottom, and learn the color corresponding to each position in the image. For example, if canvas is a very small image, the following code should display on the screen the color corresponding to each row and column. (image-scan-region canvas (lambda (col row color) (display "col:") (display col) (display " row:") (display row) (display " color:") (display (rgb->string color)) (newline)) 0 0 (image-width canvas) (image-height canvas)) a. Using a small image of your choice, verify that the positions and colors are printed out, row by row, and that the original image is unchanged. Make sure you understand the parameters to image-scan-region. Now, consider how we can use this procedure to help us write pixmaps more quickly. Rather than doing numeric recursion over the row and the column, we will use image-scan-region. Here, we will be focusing our original, rgb-colors-as-components representation. You will write a version using palettes as part of the assignment. b. Use image-write-pixmap-faster to save a very small (e.g., 8 pixel by 10 pixel) image of your choice. Open the file and verify that it contains the data you expect (up to some differences in whitespace). Is it indeed faster than our original image-write-pixmap procedure? Finally, we would also like to read pixmaps faster as well. This is where encapsulating our interactions with the image really speeds things up a lot. We'll make use of another new procedure, (image-iterate-region! image proc left top width height). image-iterate-region! is similar to image-compute-pixels! except for two differences: First, proc takes the column and row as separate parameters. Second, image-iterate-region! is guaranteed to iterate over the image row-by-row, from left to right and top to bottom, which image-compute-pixels! is not. c. Based on what you just read, what do you expect the following code to do? (image-iterate-region! canvas (lambda (col row) (rgb-new (* col 20) 0 (* row 20))) 0 0 (image-width canvas) (image-height canvas)) d. Test the code and verify that it worked as you predicted. Now, let's consider how to use image-iterate-region! to read image data into a new image. We'll start with image-read-pixmap, and replace the recursive kernel with a call to image-iterate-region!. e. Use image-read-pixmap-faster to read back the pixmap file you wrote in step c above. Is it indeed faster than our original image-read-pixmap procedure?

Warning: During this assignment you may see errors similar to error: set-input-port: needs one argument. When you read and write larger files, as you will in this assignment, you are much more likely to see such errors. These errors are unpredictable, and we don't always know where in the bowels of the GIMP they are coming from. They are not your fault, and we apologize. The solution, crazy as it is, is just to try again.

Write a new version of palette-save-image that uses image-scan-region to write the image data, rather using than a recursive kernel. Use our version of palette-save-image and image-write-pixmap-faster as models for how to use a list-based palette and how to use image-scan-region.

Write (palette-load-image filename), which loads an image from a file. The procedure should assume the file has the following format: The number of colors in the palette. The colors in the palette, represented as RGB components. The width of the image. The height of the image. The colors in the image, represented as indexes into the palette. When your procedure works, you should be able to load the sample image from the preliminaries and see it in all its diagonal glory. > (image-show (palette-load-image "sample.pal")) Your implementation should use image-iterate-region! to set pixel colors efficiently, similar to how it is used in image-read-pixmap-faster. Use this procedure as a model for your procedure. You will also find it helpful to use the following procedure to read the list of RGB colors from the file.

In this part, you will adapt the code from Problem 2 to represent the palette using a vector rather than a list. The format of the files will be exactly the same. We will just change the data structure we use to store the palette while the image is being loaded. a. Write the procedure (rgb-vector-read source n), which reads n colors from source and stores them in a vector of the appropriate size. You can use rgb-list-read as a model, but remember that recursively filling in a vector is quite different from recursively building a list. You may want to also look at your definition of vector-fill! from the lab on vectors. Be sure to test your procedure before you go on. b. Write (vpalette-load-image filename). The new procedure should be very similar to palette-load-image; it will just use vectors instead of lists when reading and using the palette.

For list-based palettes, the bigger the palette is, the longer it will take to load the image. (Why?) We've constructed a series of images saved using progressively larger palettes, from 2 colors all the way up to 32 colors. You can find these files in the following locations: /home/davisjan/csc/151/samples/palettes/flowers-2.pal /home/davisjan/csc/151/samples/palettes/flowers-4.pal /home/davisjan/csc/151/samples/palettes/flowers-8.pal /home/davisjan/csc/151/samples/palettes/flowers-16.pal /home/davisjan/csc/151/samples/palettes/flowers-32.pal /home/davisjan/csc/151/samples/palettes/flowers-64.pal /home/davisjan/csc/151/samples/palettes/flowers-128.pal /home/davisjan/csc/151/samples/palettes/flowers-255.pal You can find the original JPEG image in /home/davisjan/csc/151/samples/palettes/flowers.jpg. Load and show this image so you can see what it looks like. Do the following experiments. Report your measurements and predictions in your writeup. a. Using a clock or stopwatch, measure how many seconds it takes to load each of the files. Be sure to record your measurements. Is there a pattern? Does there appear to be a relationship between palette size and time to load the image? b. Do you expect loading the same images with vpalette-load-image to follow the same pattern? Why or why not? c. Now, test your hypothesis. Repeat the instructions from part a using vpalette-load-image. Be sure to record your timings. d. Explain what you found.

Our primary considerations will be the correctness of your code (that is, can it successfully load .pal files using the required techniques?) and the clarity with which you present your findings from Problem 3. Our secondary concerns will be the elegance and conciseness of your solutions.

; +------------------------+------------------------------------------ ; | Palette-Based Encoding | ; +------------------------+ ; +---------------------+--------------------------------------------- ; +---------------------+--------------------------------------------- ; | Reading and Writing | ; +---------------------+ ; +-------------------------+----------------------------------------- ; | Miscellaneous Utilities | ; +-------------------------+