CMSC 15100: Lab 6

CS151 Labs

Lab 6 will be collected from your subversion repository on Monday, November 7, at 5pm.

Update your repositories to receive starter materials in the directory lab6. Work in the file lab6/lab6.rkt. It is important that your lab file has exactly this name and location; we will be looking for your work under this name at collection time.

Image Compression

In this week's exercise, you will build a data compression tool for images. You will follow a (much simplified) lossless data compression scheme loosely based on that of the Graphics Interchange Format (GIF).

We will use the following terminology. We refer to an uncompressed image as a bitmap. A bitmap representation necessarily consists of a list of colors, and a number representing the width of the image. (The height of the image is implicit in the given width and the length of the color list.)

In order to understand the compressed image format for this exercise, we need some preliminary data definitions. First, a num-pair is simply a pair of numbers:

;; a num-pair is a
;; (make-pr a b)
;; for a, b numbers

A color table is a color-to-index map implemented as a binary search tree.

;; a color-table is either
;; - empty, or 
;; - (make-ct c i l r)
;; where c is a color,
;;       i (index) is a number,
;;       l is a color-table, and
;;       r is a color-table

We refer to a compressed image as a comp, using the following data definition:

;; a comp is a 
;; (make-comp w t ps)
;; where w (width) is a number,
;;       t is a color-table, and
;;       ps is a num-pair-list

Please note: the seed file lab6.rkt contains a typo. Please change the line that says (define-struct comp (c t is)) to (define-struct comp (c t ps)).

Run-length encoding a list is expressing it as a series of "runs" of particular elements. You will need to write a run-length encoding function as follows:

rle : numlist -> num-pair-list

(rle '(8 8 9 9 9 8 8 8)) => (list (make-pr 8 2) (make-pr 9 3) (mk-pr 8 3))

Write the Compressor

To compress an image, your program must do the following:

• build a color table (as a binary search tree) for the input image. Each distinct color should be assigned a unique index, which is stored as its entry i at its node in the color table.
• build a list of indices corresponding to the original image's color list.
• compress the list of indices using run-length encoding.

;; compress : img -> comp
;; generate comp (compressed image) from given image

You do not need to write a function to decompress a compressed image. (Not yet.)

An Illustration

To assist comprehension, here is an illustration of this compression scheme in action.

Here's a 3x7 pixel image before compression

And here's a representation of the same image after compression, with the color table on the left and the run-length encoded list of indices on the right:

Judge the Success of the Compression

Write two functions to help you measure how well (or poorly) your compressor succeeds at data compression. These functions will approximate the sizes of the images before and after compression, allowing comparison.

Compute the size in bytes of a bitmap according the following formula: 2 bytes for the width of the image, and 4 bytes per color in the color list. We are assuming here that 2 bytes, which can represent naturals up to 65535, is sufficient to represent the image width, and 4 bytes (one byte per color, one byte for alpha) is enough space for each color. (We are glossing over any extra space required, of which there would be some.)

Compute the size in bytes of a comp as follows: 2 bytes for the width, 4 bytes per color and 2 bytes per index in the color table, and 4 bytes per number pair in the list of number pairs.

Implement these functions:

;; size-bitmap : image -> num

;; size-comp : comp -> num

Look at the sample images (in lab6.rkt). Observe how compression performs on each. Think about the characteristics of images that are amenable to this kind of compression, and those that aren't.

Good luck, and have fun!