[The University of Leicester]

Department of Mathematics & Computer Science



Next: CO7104 C++ Programming and Advanced Algorithm Up: MSc Previous: CO7008 Semantics of Programming Languages

CO7096 Compression Methods for Multimedia

CO7096 Compression Methods for Multimedia

Credits: 20 Convenor: Prof. R. Raman Semester: 1
Prerequisites: essential: none for MSc SEEE students.
Assessment: Coursework: 30% Three hour exam in May/June: 70%
Lectures: 36 Problem Classes: 6
Tutorials: none Private Study: 96
Labs: none Seminars: none
Project: none Other: none
Surgeries: 12 Total: 150

Subject Knowledge

Aims

To study methods for compression of symbolic data as well as audio, image and video data. To gain an appreciation of the ubiquity and importance of compression technologies.

Learning Outcomes

Students should achieve: broad knowledge of compression techniques as well as the mathematical foundations of data compression; factual knowledge about existing compression standards or commonly-used compression utilities; understanding of the ubiquity and importance of compression technologies in today's environment; elementary understanding of the need for modeling data and the underlying issues.

Methods

Class sessions together with course notes, recommended textbooks, problem classes with worksheets and model solutions, web support.

Assessment

marked courseworks, class tests, traditional written examination.

Subject Skills

Aims

To teach students how to compute basic statistics of data, and how to apply nontrivial algorithms to real-world problems.

Learning Outcomes

Students will be able to: understand and describe various models of data; understand the basic data compression algorithms and show how they work on a particular input; implement these algorithms; compare their efficiency in terms of speed and compression ratio.

Methods

Class sessions and problem classes.

Assessment

marked coursework, class tests, traditional written examination.

Explanation of Pre-requisites

There are two main prerequisites. Firstly, students should have some knowledge of how data of various kinds (numbers, characters, images and sound) are represented digitally in uncompressed format. This will be reviewed rapidly at the start of the course. Some elementary mathematics is also required. In particular, trigonometry: basic functions-$\cos$,$\sin$ and measuring angles in radians; probability: basic definitions and expected values; matrices: transposition and multiplication and recurrence relations: basic familiarity. Basic familiarity with the elements of computer systems and networks is also desirable.

Course Description

Data compression is about finding novel ways of representing data so that it takes very little storage, with the proviso that it should be possible to reconstruct the original data from the compressed version. Compression is essential when storage space is at a premium or when data needs to be transmitted and bandwidth is at a premium (which is almost always). The first thing that one learns about compression is that it is not ``one size fits all'' approach: the essence of compression is to determine characteristics of the data that one is trying to compress (typically one is looking for patterns that one can exploit to get a compact representation). This gives rise to a variety of data modeling and representation techniques, which is at the heart of compression. The convergence of the communications, computing and entertainment industries has made data compression a part of everyday life (e.g. MP3, DVD and Digital TV) and has thrown up a number of exciting new opportunities for new applications of compression technologies.

Syllabus

Introduction: Raw multimedia data representation, Transmission medium characteristics, Data compression, Adaptive and non-adaptive methods, Lossy and lossless compression, Introduction to information theory and Theoretical limits of compressibility. Compressing symbolic data: Run-length coding, Entropy coders: Huffman coding, arithmetic coding, Dictionary coders: LZ77, LZW, Other text compression methods: Block-sorting. Standard text compression utilities: compress, zip. Image compression: Monochrome, facsimile and grayscale compression, GIF compression, JPEG compression, Video compression: Frame-by-frame compression: M-JPEG. Inter-frame compression: MPEG. Audio compression: Speech coding: ADPCM; CD-quality audio: MPEG layer 3. Compression applications: Computer system applications, Communication network applications, Broadcast media applications, Consumer electronics applications, Publishing applications, Entertainment applications, Healthcare applications. Managing compressed data: Self-identifying compressed data, Error-proofing compression algorithms, Interaction between compression and other functions, Interaction between compression algorithms, Operating on compressed data, Archiving compressed data.

Reading list

Recommended:

Roy Hoffman, Data compression in digital systems, Chapman and Hall Digital Multimedia Standards Series, 1997.

Khalid Sayood, Introduction to Data Compression, Morgan Kaufmann Publishers, 2000 (2nd edition).

Background:

Andrew S. Tanenbaum, Structured Computer Organization, Prentice Hall, 1999 (4th edition).

Jean-loup Gailly, The comp.compression FAQ, www.faqs.org/faqs/compression-faq/.

Resources

Course notes, web page, study guide, worksheets, handouts, lecture rooms with a computer to CFS, data projector, two OHPs, past courseworks and examination papers.

Module Evaluation

Course questionnaires, course review.

Next: CO7104 C++ Programming and Advanced Algorithm Up: MSc Previous: CO7008 Semantics of Programming Languages

[University Home] [MCS Home] [University Index A-Z] [University Search] [University Help]

Author: N. Rahman, tel: +44 (0)116 252 3902
Last updated: 2003-09-23
MCS Web Maintainer
This document has been approved by the Head of Department.
© University of Leicester.