Overview: In this project, you will be creating code to compress and decompress image files.
Goal: To gain experience with compression algorithms.
Requirements: You are going to implement a compression algorithm in Python 3.x. You have been
given a set of example images and your goal is to compress them as much as possible without losing any
perceptible information â€“ upon decompression they should appear identical to the original images.
Images are essentially stored as a series of points of color, where each point is represented as a
combination of red, green and blue (rgb). Each component of the rgb value ranges between 0-255, so
for example: (100, 0, 200) would represent a shade of purple. Using a fixed length encoding, each
component of the rgb value requires 8 bits to encode (28 = 256) meaning that the entire rgb value
requires 24 bits to encode. You could use a compression algorithm like Huffman encoding to reduce the
number of bits needed for more common values and thereby reduce the total number of bits needed to
encode your image.
You can use the Pillow library of Python to read in image files and extract the rgb values of individual
points. To install the library in PyCharm, go to Project Settings -> Project Interpreter. To the right of the
list of packages will be a small + sign. Click on it to open up the window of available packages and search
for Pillow â€“ since there are several similarly named libraries, you want the one written by Alex Clark and
its full name should be Python Imaging Library (Fork). Then click on Install Package. (Itâ€™s possible you
may get an error if you have an older version of pip installed â€“ it would be listed on the prior page of
installed packages. If the error occurs, first install the latest version of pip, then install Pillow.)
Once you have Pillow installed, you can include the library into your project code with:
from PIL import Image
You can then open image files using, for example:
img = Image.open(“powercat.bmp”)
If you wanted to display the image in your standard image viewer, you could use:
If you want to access the pixel values of points in an image, youâ€™ll first need to call load() to create a
pixel access object and then you can access individual pixels using list notation:
width, height = img.size
px = img.load()
for x in range(width):
for y in range(height):
Your code should read in an image file, compute how many bits are required for a fixed length encoding
and then apply a compression algorithm to create a smaller encoding â€“ you need to implement the
compression, you cannot use a compression library. You should output how many bits are required to
store the image in your compressed format as well as the compression ratio achieved. When it comes
to saving your compressed image, you wonâ€™t be able to save it as a standard image format, since you will
have created your own encoding, but you can save the sequence of bits into a text or binary file.
Your code should also be able to prompt the user for the filename of a text file containing a compressed
sequence of bits and then decompress that file into the original image â€“ you can assume that the file
uses the same compression format as the last file you compressed. So, for example, if you compressed
pacificat.bmp into a series of bits stored in pacificat.txt and then the user asked you to decompress
alt_pacificat.txt, you could assume that alt_pacificat.txt used the same compression data structure as
pacificat.txt (it might be a subset of the data from the original image, for example).
There are a number of libraries that can help you store formatted data into a file from Python. If you
research the options and find a way to store your compression data structure into a file, such that the
user can select both a bit file and a data structure file and use the data structure to decompress the bit
file, then you can earn an extra half point on the rubric.
Your code should compute the following statistics each time the compression code is called on a file:
ï‚· Runtime in milliseconds of the compression process, including any time needed to create the
data structures used to help with the compression process.
ï‚· Number of bits needed by your algorithm to encode the contents of the file.
ï‚· Number of bits needed by a fixed length encoding to encode the contents of the file.
ï‚· The compression ratio achieved.
For the decompression process, you only need to track the runtime in milliseconds.
Algorithm: In addition to your code, you need to turn in a well-formatted document containing the
pseudo-code for your core algorithm (written in the same format as the textbook uses for pseudo-code)
along with any proofs you decide to include about your algorithm â€“ see grading section below.