COMP 150 MDC - Fall 2016 - Homework 8

Code due Monday, 12 December, 2016 at 11:30 PM

Report due Monday, 12 December, 2016 at 4:30 PM

Report problems to ablumer via email

In this assignment you will explore compression of images using vector quantization. For simplicity, the images will be grayscale with pixel values in the range 0 - 255. The vectors will be 16-dimensional, obtained from 4 x 4 blocks of pixels.

I have written a program, imagepixels, that takes an image file and breaks it up into pixel vectors and writes them to a text file. It also takes a file of vectors and converts it back into an image file. The first line of the text file gives the number of 4 x 4 blocks vertically and horizontally. If the original image has size that's not a multiple of 4, the last few rows and columns are dropped. You can run the program by

./imagepixels d imagefile pixelfile

to get the text file corresponding to an image, or

./imagepixels e pixelfile imagefile

to convert the pixels back to an image. I recommend using .bmp as the output image format so there's no extra compression.
This program and some test images are in ~ablumer/150mdchw8

Your program should read in the vectors from a pixelfile and find a dictionary of vectors that gives a good quantization of the image. Your program should use the LBG algorithm as described in the book. At a minimum, the user should be able to select one of several compression levels (which will determine the dictionary size), the maximum number of iterations of LBG, and the number of random restarts. If the number of iterations is zero, it should just make a random selection of vectors from the blocks of the image. If there is more than one random restart it should keep the best solution and report on the quality of the other solutions. Extra credit will be given for trying other experiments. Your program should read a pixelfile as created and expected by my program, and write a file in the same format. You can then use my program with the "e" option to convert the output of your program to an image so you can check the quality of the image.

Write a report on your program and any extra features you created. Submit your code using this command:

provide comp150mdc a8 file1 file2 ...

You can also submit your report along with your code, or you can turn in a paper copy to my mailbox in the CS office in Halligan.