Wavelets


A copy of the original image with 149604 bytes of information and a transfer time of 5.00 seconds on a standard modem.	A wavelet compressed copy of the original image with 12253 bytes of information and a transfer time of 0.40 seconds on a standard modem (about 8% of the original size).	A second wavelet-compressed version of the original with 4452 bytes of information and a transfer time of 0.15 seconds on a standard modem (about 3% of the original size).
Obviously, there are only scant differences in quality, but the savings in time and size are significant. These images come from a fascinating site developed by Osmar R. Zaïane at the University of Alberta, Canada. The NCB recommends you take a look at other images and make similar adjustments using his wavelet controls. < http://www.cs.sfu.ca/CC/365/li/material/cgi-bin/wavelet.cgi >

Why Compress an Image?

According to Gonzalez and Woods, (Digital Image Processing, 2nd ed., Prentice Hall, 2002), compression is achieved by removing onr or more of the following redundances.

Coding Redundancy - The codes used to store information about each pixel is not optimal.

Interpixel Redundancy - Exploit the fact that nearby pixels in an image are often related to each other.

Psychovisual Redundancy - Remove information that is typically ignored by the human eye.

Basic Compression Algorithm

If appropriate, convert the image to a color space more amenable to eliminating psychovisual redundancies.

Transform this image to a new image. This transformation will exploit interpixel redundancies and result in an image whose energy is stored in a small area.

Encode the transformed image. The encoding scheme takes advantage of the fact that the energy of the transformed image is highly concentrated and produces short codes to represent the image information.

Transmit the image.

Image Basics

For the purpose of this explanation, we will only consider "grayscale" images.


Think of a grayscale image as a matrix where each element is an integer ranging from 0 to 255. We assign 0 to be black and 255 to be white.

Each integer between 0 and 255 is assigned a character. These characters (bytes) are the standard characters as assigned by the "ASCII" code, or the American Standard Code for Information Interchange. As luck would have it, there are exactly 256 characters on a standard keyboard.
Students of mathematics recognize that 256 = 2⁸. Thus we can express each character (byte) as a base two number comprised of only eight 0's and 1's.

For example the ASCII number 121 is "y" on the keyboard and in base two is

Thus every intensity could be stored as an eight-bit stream. The dimensions of our baboon image are 512 x 512 so the total number of bits needed to store the baboon is 512² x 8 = 2,097,152.

Background for Huffman Coding

In 1952 David Huffman made a simple observation:

Rather than use the same number of bits to represent each character, why not use a short bit stream for characters that appear often in an image and a longer bit stream for characters that appear infrequently in the image?

He then developed an algorithm to do just that. We refer to his simple algorithm as Huffman Coding. We will illustrate the algorithm with an example.

Suppose you want to perform Huffman coding on the word "seesaws." First observe that "s" appears three times (24 bits), "e" appears twice (16 bits), and "a" and "w" each appear once (16 bits). Thus, the total number of bits needed to represent "seesaws" is 56. Here is the ASCII and binary representation of each letter:

So in terms of bits, the word "seesaws" is

01110011011001010110010101110011011000010111011101110011

The first step in Huffman coding is based on probabilities: Assign a probability to each character and then sort from smallest to largest. The probabilites are in circles called "nodes" and then connect them with lines (branches).

Assignment of probabilities to "seesaws"

Now simply add the two smallest probabilites to create a new node. Branch the two small nodes off this one and resort the three remaining nodes.

Repeat the process by adding the two smallest probabilites on the top row, and then create a new node with everything below these nodes as branches. Sort again. When only two nodes remain on the top, simply add the probabilities together to get the 1 and a finished tree.

Now assign to each branch the value 0 and to each right branch the value of 1.

We can read the new bit stream for each character right off the tree! This is the new bit streams for the four characters:

Keyboard Character	Binary
s	0_two
e	11_two
a	100_two
w	101_two

The "s" apprears three times in "seesaws" so we need 3 bits to represent them. The character "e" appears twice (4 bits), while both "a" and "w" appear only once (3 bits). The total number of bits we need to represent "seesaws" has been reduced from the original 56 bits to only 13. Using the Huffman codes for each character we now write: