490GZ Project 2

CSE Home

About Us

Search

Contact Info

Objectives

• Learn how to implement vector quantization training, the GLA alorithm.
• Learn how to implement fast full search for the GLA algorithm and for VQ encoding.
• Learn about the quality of VQ images by examining differing codebook sizes and vector sizes.

Overview

Vector quantization (VQ) is a basic lossy coding method that can be used for images, speech, and other types of data. VQ requires training which can be very time consuming. However, using fast full search algorithms for multidimensional data, the time for training can be reduced. In addition fast full search algorithms can accelerate VQ encoding. In this project you will design and implement a version of the GLA algorithm. In addition, you will design a fast full search algorithm that can be used within the GLA algorithm for fast encoding. You will then experiment with your algorithm on different images to assess the quality with differing codebook sizes and vector sizes.

Coding Assignment

What we have provided

For this project we have provide only the code necessary to take an eight bit grayscale image in .pgm or .bmp formats and input it as an array and to take an array and output as an image in the same format. We have also provided 5 images in the BMP format.

The files you need

• To open an image: Image im = new Image("filename.bmp")
• To write an image: im.save("output.bmp")
• Useful data members:
  • im.width
  • im.height
  • im.pixel[i][j], i = column, j = row

What you should provide

1. A README file that explains how to extract your files and explains how to use your program. Included should be an explanation of your file format for codebooks.
2. GLA. The GLA code should take as input one or more images as a training set and output a codebook. You may sample from the images to create the codebook.
3. Fast Full Search (FFS). The FFS should take a vector and codebook, and return the index of the nearest codeword in the codebook. It should not use linear search but one of the fast full search methods found in the Zatloukal/Ladner paper or some other method found in the literature. FFS should be used in both the GLA and in the VQ encoder.
4. Encode/Decode (VQ). Both encoder and decoder have access to the same codebook. The VQ encoder takes an image and produces an index stream. The VQ decoder takes an index stream and outputs an image. The index file must have a specific format as explained below.
5. Two codebook files with 256 codewords each for 2 by 1 and 2 by 2 vector to be used for testing.

Index Stream Format

So that we can compare your data compressor with others we require a specific file format for the index stream.

1. The first four bytes represent an integer of the width of the image in blocks and the second four bytes represent the height of the image in blocks. Suppose you have an p x q (width by height) image partitioned into r x s blocks then the first two numbers are are w = p/r and h = q/s.
2. The next byte is the an integer representing how many bits make up one index. For example, if the codebook size is n, then the second, then this byte is log₂n interpreted as an integer.
3. The remainder of the file is a bit stream where each k = log₂ n bits is a k-bit index. The indices are output in raster order, first row of indices, second row of indices, and so on. Naturally, this bit stream is represented as bytes in the file. Suppose we have a codebook of size 128, then every 7 bits is an index, or every 7 bytes is 8 indices. The total length of the files should be k * w * h / 8 + 9 bytes.

Experimental Study

For the experimental study you will choose a lossless compressor (winzip, bzip2, etc.) for the index stream so that you can provide a rate distortion graph for your encoder/decoder. You should use at least three different codebooks based on different training sets (not Barbara) and do your testing only on the Barbara image. By choosing various codebook sizes and vector sizes plot at least 10 different bit rates vs. PSNR to compare the quality of the codebooks obtained from different training sets. Write a short paper that explains the details of your experimental setup and the results you obtained.

Contest

Due Date

There should be two files to turn in: the README file and a tar file with everything else (including the codebooks). The README should explain how to open the tar file, how to run the programs, and what your codebook files are. Go to the turn-in page to send us these files.

	Computer Science & Engineering University of Washington Box 352350 Seattle, WA  98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to nchernia]