CS 252: Algorithms

Seam carving, compression

Hand in your source code via Moodle by 8:30 AM Monday, 2 Nov 2015.

For this assignment, you will implement either seam carving or the Lempel-Ziv-Welch algorithm. You may write in Python, Java, C, or C++. Whichever language you choose, please make sure your program is runnable from the command line on the Macs in the CMC 3rd-floor labs.

Seam carving

Your program should support the command-line syntax:

or the equivalent in the other languages. So, for example:

would remove 20 successive vertical seams from boats.png, save the resulting image in carved_boats.png, and display on screen both the before and after images. Without the "--show", this same command would save the carved image in carved_boats.png, but would not display anything on screen. You may include other features for debugging or your own pleasure, but this core syntax must be supported.

I have written short image-processing samples in Python (image_example.py) and Java (ImageExample.java), in case you find them handy. The Java program uses only standard libraries. The Python program depends on the installation of pillow (importable as PIL). This is easy enough to install on your own machine ("pip install pillow"), but is already installed in the CMC 3rd-floor labs.

Lempel-Ziv-Welch

Your program should include the command-line syntax:

where action equals either "compress" or "decompress". For example, if you do this:

then the diff command should return no differences.

In addition to compressing and decompressing, your program should print a short summary of the operation to standard error, including the sizes (in bytes) of the input and output files. The summary should be simple, and look something like this:

Other notes

• Write your own code. You can consult the web for help on details, but don't take other people's code.
• Document your code as appropriate, use clean style and organization, etc. All the usual software quality attributes apply.
• Think ahead about how you will test your code, and what debugging assistance you might want to build in (e.g. a feature for showing your chosen seams in red). Don't depend only on trivial testing (e.g. a single one-sentence file for compression testing); give it a better workout, and consider boundary cases (e.g. empty files).
• Have fun.