CS6604 - Data Compression
Spring 2008, CRN 16576
MWF 1:25pm, McBryde 316
|
|
|
Instructor
R.W. Ehrich, KW2 129, Office Hours: M, W 2:45 - 3:45 in McB 636, or by appointment (1-5420)
Objectives
We live in a world where data compression is a key part of almost
every aspect of computer and communications technology. No matter how
much storage we have in our computers we are always concerned with space
optimization and the algorithmic aspects of the efficiency we struggle to
achive. No matter what the cost of communication links, we are always
looking for techniques to achieve better transmission rates. Data
compression is grounded in information theory, and there are many
fundamental algorithms that we must deal with daily in our information
transmission and storage tasks. In this course we discuss the theoretical
underpinnings of data compression and cover many fundamental algorithms.
This course differs from previous offerings in that the course text by
Sayood is the 3rd revision of a classic text that has been available for
a number of years and covers both text and image compression. We may use
examples from the information retrieval field to see how text compression
has been integrated into retrieval software. The Bell, Cleary, and Witten
text, will serve as an important reference for the course.
Grading
The semester grade will be based upon assignments issued in class
(20%), one midterm (25%), at least one project (35%), and a comprehensive
final examination (20%). Not all homework assignments will be graded, but
students will not be told in advance which will be graded. Whenever
feasible, solutions will be provided.
Exams
Midterm, Monday, February 18
Final, Friday, May 2, 1:05pm - (NOTE: Classes end Wednesday, April 30)
Ethics
The
Honor Code
will be strictly enforced. It is a violation to represent joint work as
your own; always acknowledge any assistance you received in preparing work
that bears your name.
You are expected to work independently unless explicitly permitted to
collaborate on a particular assignment. It is not a violation to discuss
approaches to programs with others; however, it IS a violation to use code
fragments in your program that have been written by others without acknowledging
the source.
Please be considerate of your fellow students. In particular, please realize
that your classmates will likely need the reserve materials at the same time you
do... don't keep these materials out for long periods of time, expecially before
exams and assignment due dates.
Prerequisites
Undergraduate calculus, linear algebra, probability theory, and programming
competence in C, C++ or Java.
Project
To be determined
Text
Sayood, Khalid, Introduction to Data Compression,
3rd Edition, Morgan Kaufmann, 2006.
References
- Anderson, J.B. and Mohan, S., Source and Channel Coding,
Kluwer, 1991.
- Gersho, A. and Gray, R.M., Vector Quantization and Signal Compression,
Kluwer, 1992.
- Netravali, A.N., Digital Pictures, Representation and Compression,
Plenum, 1989.
- Rao, K.R. and Yip, P., Discrete Cosine Transform,
Academic Press, 1990.
- Storer, J.A., Data Compression Methods and Theory,
Computer Science Press, 1988.
- Williams, R.N., Adaptive Data Compression,
Kluwer, 1991.
References on Reserve
- Ash, Robert B., Information Theory,
John Wiley and Sons, 1965
- Bell, T.C., Cleary, J.G., and Witten, I.H., Text Compression,
Prentice Hall, 1990.
- Sayood, K., Introduction to Data Compression,
3rd Edition, Morgan Kaufmann, 2006.
- Witten, I.H., Moffat, A., and Bell, T.C., Managing Gigabytes,
2nd Edition, Morgan Kaufmann, 1999.
Papers in Reserve Collection
- Bell, T.C., Cleary, J.G., and Witten, I.H., Arithmetic Coding, in
Text Compression, Prentice Hall, 1990, Chapter 5.2.
- Bell, T.C., Witten, I.H., and Cleary, J.G., "Modeling for Text
Compression," ACM Computing Surveys (21), No. 4, pp. 557-591,
December 1989.
- Langdon, G.G., Pennebaker, W.B., Mitchell, J.L., Arps, R.B., and Rissanen,
J.J., A Tutorial on the Adaptive Q-Coder, IBM Research Report
RJ 5736 (57715), Yorktown Heights, 6/1/88.
- Welch, T.A., "A Technique for High-Performance Data Compression,"
IEEE Computer (17), pp. 8-19, June 1984.
- Witten, I.H., Neal, R., and Cleary, J.G., "Arithmetic Coding for Data Compression,"
CACM (30), pp. 520-540, June 1987.
- Ziv, J., and Lempel, A., "A Universal Algorithm for Sequential Data Compression,"
IEEE Trans. IT (23), pp. 337-343, May 1977.
- Ziv, J., and Lempel, A., "Compression of Individual Sequences via Variable-Rate Coding,"
IEEE Trans IT (24), pp. 530-536, May 1978.
Bitplane Coding
- Shapiro, Jerome, "Embedded Image Coding Using Zerotrees of Wavelet Coefficients,"
IEEE Trans. SP (41), pp. 3445-3462, December 1993.
- Said, A. and Pearlman, W.A., "A New, Fast, and Efficient Image Codec Based
on Set Partitioning in Hierarchical Trees,"
IEEE Trans. CSVT (6), pp. 243-250, June 1966.
- Taubman, David, "High Performance Scalable Image Compression with EBCOT,"
IEEE Trans. IP (9), pp. 1158-1170, July 2000.
- Taubman, D.S. and Marcellin, M.W., JPEG 2000, Kluwer, 2002.
Course Outline
| Information theoretic foundations | 15% |
- Lossless and lossy compression
- Modeling and coding
- Entropy, conditional entropy, information, channels
- Data models: static and adaptive
- Coding: Fano, Huffman, Golomb, Rice, Tunstall
-
- Encoding
- Decoding
- Adapatation
-
- Static techniques
- Adaptive coding: the LZ family
-
- PPM
- Burrows-Wheeler
- Move-to-front
- DMC
| Lossless image compression | 10% |
- Multiresolution
- CCITT Group 3 and 4
- JBIG, JBIG2
| Lossy coding preliminaries | 10% |
- Distortion
- Rate distortion
- Linear system models
| Scalar and vector quantization | 10% |
- Uniform and nonunform quantizers
- Adaptive quantization
- Lloyd-Max quantizer
- LBG quantizer
- Tree-structured quantizers
- Trellis-coded quantization
-
- Predictive DPCM
- Adaptive DPCM
- Delta modulation
-
- Bases, inner products, orthogonality and orthonormality
- Karhunen-Loéve transform
- DCT
- Walsh-Hadamard transform
- JPEG