Encode the image and output the encoded image

CS302 Data Structures

Spring 2012 – Dr. George Bebis

	Use a priority queue in image compression Implement and manipulate binary trees Learn about Huffman Coding Learn about bit and byte input/output

Huffman coding: Each pixel in a PGM image is represented by one byte or 8 bits. Huffman coding compresses an image by encoding the pixel values so that not all pixel values require 8 bits of storage.The key idea is assigning fewer bits to pixel values that appear more frequently in the image and more bits to pixel values that appear less frequently in the image. As a result, the size of the compressed image is smaller than the original one. Let us consider the 6x6 image shown below where every pixel is encoded using 8 bits. Storing this image would require 36x8= 288 bits. Since pixel values are between 0 and 7, we could assume 3 bits per pixel only; in this case, storing the image would require 36x3=108 bits. Using Huffman coding, however, it would require 93 bits.

Encoding/Decoding: To encode an image, we replace each pixel value by its corresponding bit encoding. Using the encoding shown in Figure 2, for example, the first row of the image shown in Figure 1 is encoded as follows: 10011010000001110. To decode a stream of pixel encodings, start at the root of the encoding tree, and follow a left-branch for a 0, a right branch for a 1. When you reach a leaf, write the pixel value stored at the leaf, and start again at the top of the tree. This process is repeated until all bit encodings have been decoded.

2. Repeat this step until there is only one tree: Choose two trees with the smallest weights, call these trees T1 and T2. Create a new tree whose root has a weight equal to the sum of the weights T1 + T2 and whose left subtree is T1 and whose right subtree is T2.

3. The single tree left after the previous step is an optimal encoding tree.

4. Encode the image and output the encoded/compressed image.

5. Read the encoded/compressed file you just created, decode it and output the decoded image.

bits using bitwise operators. Alternatively, you can use C++ classes to read and write bit streams; here is an example:
http://www.codeproject.com/Articles/332219/C-Classes-to-Read-and-Write-Bit-Stream Instructions
Each function should be discussed in a separate section with the name of the section being the same as the name of the function. Functions that you have implemented in previous assignments do not need to be described again (only if you have made significant modifications). The sections should be clearly separated from each other.