CSEP 590 A - Data Compression, Autumn 2007

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.

	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]