CSEP 590 A - Data Compression, Autumn 2007

University of Washington Computer Science & Engineering

CSE Home

About Us

Contact Info

Instructor:

Richard E. Ladner (ladner@cs.washington.edu)
Office: CSE 632, 543-9347

Teaching Assistant:

Rahul Vanam (rahulv@u.washington.edu)
Rahul will have office hours in the atrium on Thursdays between 6:00 and 6:30 pm.

Course Description

Basic information theory: entropy. Lossless data compression techniques: Huffman coding, arithmetic coding, and dictionary methods including LZW, LZ77, and Sequitur. Use of context, structure, and prediction to improve compression. Basic signal processing: Fourier and discrete cosine transforms, wavelet transforms, quantization. Fidelity and distortion metrics, rate-distortion analysis. Image compression: vector quantization, DCT coding, wavelet coding. Video compression: motion compensation and prediction. Audio compression. Image, video, and audio compression standards including JPEG, JPEG2000, MP3, MPEG and H.26x.

Tentative Course Syllabus

Meeting Times:

Thursdays 6:30-9:20 pm, EEB 045 (EE Building Basement)
There is no meeting on October 18th. Instead there will be a meeting on Monday, November 19th from 6:30 - 8:20 in CSE 305. This lecture will be video taped and will be available a few days after the lecture.
Video of lecture from 11/19/07

Assignments:

Assignments are due in class (late assignments not accepted without prior approval).

Assignment 1 due 10/4/07
Assignment 2 due 10/11/07
Assignment 3 due 10/25/07
Assignment 4 due 11/1/07
Assignment 5 due 11/8/07
Assignment 6 due Monday 11/19/07
Assignment 7 due 1/29/07

Project:

Project 1 due 11/14/07

Reading:

9/27/07 - 10/4/07: Information Theory, Huffman Coding, Golomb Coding, Tunstall Coding, Arithmetic Coding Sayood, pages 1 - 115
10/5/07 - 10/11/07: LZW, LZ77, Sayood, pages 117 - 140
10/12/07 - 10/25/07: Sequitur Paper 1 , Paper 2 . Burrows-Wheeler Transform, Sayood, pages 149 - 155.
10/26/07 - 11/8/07: Transform coding, Sayood, pages 392 - 422, Scalar and Vector Quanization, pages 227 - 322. Nearest neighbor search: Paper
11/9/07 - 11/15/07: Wavelet transform coding and SPIHT, Sayood, pages 455 - 479, 486 - 492, Priority-Based Arithmetic Coding for Wavelets, Context-Based Arithmetic Coding for the DCT: Achieving high compression rates with block transforms and simple context modeling; Optional Reading: Alternative Transforms
11/16/07 - 11/29/07: Group testing for wavelets: Paper , JPEG 2000 Paper . Video compression, Sayood, pages 571 - 588.
Reading on MobileASL MobileASL publications

Lectures:

Lecture 1 handouts, Lecture 1 full slides: Course Policies, Introduction to Data compression, Entropy, Variable Length Codes
Lecture 2 handouts, Lecture 2 full slides: Adaptive Huffman Coding
Lecture 3 handouts, Lecture 3 full slides: Arithmetic Coding
Lecture 4 handouts, Lecture 4 full slides: Dictionary Coding, LZW, LZ77
Lecture 5 handouts, Lecture 5 full slides: Sequitur
Lecture 6 handouts, Lecture 6 full slides: Predictive Coding, Burrows-Wheeler Transform
Lecture 7 handouts, Lecture 7 full slides: Lossy Image Compression, Transform Coding, JPEG
Lecture 8 handouts, Lecture 8 full slides: Scalar Quantization, Vector Quantization
Lecture 9 handouts, Lecture 9 full slides: Wavelet Transform Coding Priority-Based Arithmetic Coding for Wavelets (PACW)
Lecture 10 handouts, Lecture 10 full slides: Context Based Arithmetic Coding for the DCT (CBACD)
Lecture 11 handouts, Lecture 11 full slides: SPIHT and GTW
Lecture 12 handouts, Lecture 12 full slides: EBCOT and JPEG 2000
Lecture 13 handouts, Lecture 13 full slides: Video Compression
handouts, full slides: MobileASL
handouts, full slides: The H.264/AVC Video Coding Standard by Gary Sullivan
handouts, full slides: Motion Estimation and Intra Frame Prediction in H.264/AVC Encoder by Rahul Vanam
handouts: Perceptual Audio Coding by Henrique Malvar

CSEP 590 Message Board

Please see the CSEP 590 Message Board for announcements and discussion. The TA will monitor the message board several times per day to field questions. In particular he will check the message board between 4:00 and 5:00 every weekday.

Text Books

Khalid Sayood, Introduction to Data Compression, Third Edition, Morgan Kaufmann Publishers, 2006.

Data Compression Resources

These resources may be helpful in your studies.

Final Exam

6:30-8:20 p.m. Thursday, Dec. 13, 2007
Final Exam study guide

Tentative Grading Weights

Weekly assignments (50%)
Project (20%)
Final exam (30%)

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