Retro prof in the lab University of Washington Department of Computer Science & Engineering
 CSE 490 G - Introduction to Data Compression, Winter 2006
  CSE Home   About Us    Search    Contact Info 

The course will have regular weekly assignments, several programming projects, a midterm and final exam.

Topics include:

  1. Preliminaries: lossless vs. lossy compression. Compression ratio. Compression/fidelity tradeoff. Uses of compression.
  2. Simple lossless encoding: Huffman coding and LZW coding.
  3. Basic information theory. Entropy and conditional entropy. Use of context. Limits of Huffman codes. Arithmetic coding.
  4. LZ77, Sequitur, Burrows-Wheeler Transform, PPM and other lossless coding methods.
  5. Run length coding, Golomb codes, group testing.
  6. Lossless compression standards: zip, gzip, bzip, unix compress, GIF, JBIG.
  7. Image compression preliminaries. Basis functions and transforms from an intuitive point of view. Fourier, DCT, and wavelet transforms.
  8. Properties of color, gray scale, and visual perception. Fidelity and distortion metrics: mean squared error, peak signal to noise ratio.
  9. Vector quantization. Full search VQ and generalized Lloyd algorithm. Tree-structured VQ. Pruned tree-structured VQ. Rate-distortion optimization.
  10. DCT Compression. JPEG.
  11. Wavelet Image Compression. SPIHT, UWIC, GTW, JPEG2000, and EBCOT.
  12. Video Compression. Motion compensation, temporal and spatial prediction. MPEG and H.263.
  13. Properties of audio perception. Audio coding. MP3.
  14. Properties of speech production and perception. Speech coding. LPC and MELP.
  15. Compression and networks. Forward error correction. Error concealment. Network protocols: ARQ, RTP, PET, ULP.

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