Welcome to the Homepage of the Lecture

Image Compression

Winter Term 2015 / 2016

Image Compression

Lecturer: Pascal Peter

Examiner: Prof. Dr. Joachim Weickert

Winter Term 2015 / 2016
Lecture (2h) with exercises (2h) 6 credit points

Lecture: Thursday 12-14 c.t., Building E1.3, Lecture Hall 001
First lecture: Thursday, October 22, 2015.

Tutor: Aaron Wewior

Tutorials:
G1 Monday 12-14 c.t., Building E1.3, Seminar Room 015
G2 Monday 14-16 c.t., Building E1.3, Seminar Room 015
First tutorial: Monday, October 26, 2015.

Announcements – Description – Entrance requirements – Tutorials – Exams – Lectures – Assignments – References

18/04/2015: The results of the second exam are now available.

22/02/2016: The results of the first exam are now available.
09/02/2016: The admission list ist now online.
26/01/2016 The selftest problem is online.
29/10/2015 The first homework assignment (H2) is online.
22/10/2015 Due to a conference in November, all tutorial dates are shifted slightly. Tutorials already start on Monday, October 26 with a Classroom Assignment that yields 6 bonus points. In the first week, you can visit any of the two tutorials.
22/10/2015: Registration is open.
24/08/2015: The date of the first exam was shifted to February 19th, 2016.
30/07/2015: Website is online

Motivation: High resolution image data is becoming increasingly popular in research and commercial applications (e.g. entertainment, medical imaging). In addition, there is also a high demand for content distribution via the internet. Due to the resulting increase in storage and bandwith requirements, image compression is a highly relevant and very active area of research.

Teaching Goals: The course is designed as a supplement for image processing lectures, to be attended before, after or parallel to them. After the lecture, participants should understand the theoretical foundations of image compression and be familiar with a wide range of classical and contemporary compression methods.

Contents: The lecture can be seperated into two parts: The first half of the lecture deals with general data compression methods that are not focussed on the specific task of image compression. We discuss the information theoretic background of so-called entropy coders (e.g. Huffman-coding, arithmetic coding and many more) and talk about dictionary methods such as the approach by Lempel, Ziv, and Welch (LZW). Knowledge about these tools is necessary to understand certain steps in state of the art methods for image compression.

In the second part of the lecture, image compression algorithms and related topics such as error measures for evaluation purposes are introduced. In particular, we discuss lossless image compression algorithms based on predictions (PNG, JPEG-LS, JBIG), as well as lossy approaches based on transformations (JPEG, JPEG 2000). Furthermore, emerging novel compression concepts such as diffusion-based compression are presented. The lecture concludes with a short overview of video compression methods.

Basic mathematics courses (such as Mathematik für Informatiker I-III) are recommended. Understanding English is necessary. Image processing lectures such as "Image Processing and Computer Vision" are helpful for some specific topics, but not necessary.

The tutorials include homework assignments as well as classroom assignments. Homework assignments are handed in and graded, while classroom assignements are solved during the tutorials. Working together in groups of up to 3 people is permitted and highly encouraged.

For the homework assignments you can obtain up to 12 points per week. Actively participating in the classroom assignments gives you 6 more points per week, regardless of the correctness of your solutions. To qualify for both exams you need 2/3 of all possible points. For 12 assignments, this comes down to 12 x 12 = 144 points.

If you have questions concerning the tutorials, please do not hesitate to contact Pascal Peter.

The first written exam will take place on Friday, February 19, 2016 at 2:00 pm in Building E2.2, Günter Hotz Lecture Theatre.
The second written exam will take place on Tuesday, April 12, 2016 at 2:00 pm in Building E1.3, Lecture Hall 002.
These are open book exams. You can participate in both exams, and the better grades counts.

If you are admitted (i.e. reached enough points in the tutorials), you will find your matriculation number on this list.

Registration is closed. Please remember that you also have to register online for both exams individually in the HISPOS system of the Saarland University.

If you cannot attend the exam, contact Pascal Peter as early as possible. In case you have proof that you cannot take part for medical reasons or you have another exam on the same day, we can offer you an oral exam as a replacement. Note that we need written proof (e.g. a certificate from a physician/Krankenschein) for the exact date of the exam.

You can find your result of the first exam here.
General statistics about this exam can be downloaded here.

You can find your result of the second exam here.
General statistics about this exam can be downloaded here.

Each student who has participated in the second written exam has the opportunity to inspect his/her graded solutions in room 4.10 in Bldg. E1.7 on Tuesday, April 19rd, 2016 in the following timeslot:
14:00 pm - 15:00 pm

Participants of the course can download the lecture materials here after the lecture (access is password-protected). However, be aware that these slides are only provided to support the classroom teaching, not to replace it. Additional organisational information, such as examples and explanations that may be helpful or necessary to understand the content of the course (and thus relevant for the exam), will be provided in the lectures. It is solely your responsibility - not ours - to make sure that you receive this infomation.

Two versions of the lecture notes are provided. While the content is identical, the script-version is printer-friendly, while the slides contain advanced features like quick navigation via the side-bar and a convenient possibility for full-size display of the included images.

The topics given here are preliminary and might change slightly.

No.	Title	Date	Script	Slides
1	Introduction and Basic Concepts	22/10	[download]	[download]
2	Theoretical Background and Entropy Coding I	29/10	[download]	[download]
3	Entropy Coding II	05/11	[download]	[download]
4	Arithmetic Coding I	12/11	[download]	[download]
5	Arithmetic Coding II and Adaptive Entropy Coding	19/11	[download]	[download]
6	Higher Order Coding, RLE, BWT, MTF, and Bzip2	03/12	[download]	[download]
7	Coding with Dictionaries	10/12	[download]	[download]
8	PPM and PAQ	17/12	[download]	[download]
9	Prediction and Lossless Image Compression (PNG, JPEG-LS, JBIG)	07/01	[download]	[download]
10	Basics of Lossy Image Compression and Fractal Image Compression	14/01	[download]	[download]
11	Transform-Based Image Compression (JPEG and JPEG 2000)	21/01	[download]	[download]
12	PDE-based Image Compression I	28/01	[download]	[download]
13	PDE-based Image Compression II	04/01	[download]	[download]
14	Video Compression - An Overview	11/02	[download]	[download]

Participants can download assignments and solutions here. Classroom assignments are solved during the corresponding tutorial, homework has to be handed in before the end of the deadline given on the respective sheet (usually before the next lecture). For the classroom assignments an optional hint sheet is provided.

No.	Assignments	Date	Solutions
1	Classroom Work 1: VDRs and Uniquely Decodable Codes (Optional Hint Sheet)	26/10	Sol. C1
2	Classroom Work 2: Entropy Coding (Optional Hint Sheet) Homework 2: Entropy Coding	02/11	Sol. C2 Sol. H2
3	Classroom Work 3: Extended Huffman and Fibonacci Coding Homework 3: Golomb and Fibonacci Coding	09/11	Sol. C3 Sol. H3
4	Classroom Work 4: Pure Arithmetic Coding (Optional Hint Sheet) Homework 4: Pure Arithmetic Coding	16/11	Sol. C4 Sol. H4
5	Classroom Work 5: Integer Arithmetic Coding (Optional Hint Sheet) Homework 5: Pure and Integer Arithmetic Coding	23/11	Sol. C5 Sol. H5
6	Classroom Work 6: RLE, Higher-Order Entropy Coding (Optional Hint Sheet) Homework 6: RLE, BWT, MTF	07/12	Sol. C6 Sol. H6
7	Classroom Work 7: LZ78 and LZW Homework 7: LZSS	14/12	Sol. C7 Sol. H7
8	Homework 8: PPM, PAQ and LZW	21/12	Sol. H8
9	Classroom Work 9: Prediction Homework 9: JBIG and JPEG-LS	11/01	Sol. C9 Sol. H9
10	Classroom Work 10: Contraction Mappings, Hausdorff Distance Homework 10: Contraction Mappings	18/01	Sol. C10 Sol. H10
11	Classroom Work 11: JPEG, YUV Homework 11: DCT, JPEG	25/01	Sol. C11 Sol. H11
12	Classroom Work 12: Subdivison Schemes Homework 12: Subdivision Schemes	01/02	Sol. C12 Sol. H12
13	Selftest Problem (will not be handed hin)	26/01	Solution

There is no specific book that covers the complete content of this class. However, each of the following books covers several of the topics discussed in the lecture:

• T. Strutz: Bilddatenkompression. Vieweg+Teubner (in German)
• D. Hankerson, G. A. Harris, and P. D. Johnson, Jr.: Introduction to Information Theory and Data Compression. Chapman & Hall/CRC
• K. Sayood: Introduction to Data Compression. Morgan Kaufmann

Further references will be given during the lecture.

MIA Group
©2001-2023
The author is not
responsible for
the content of
external pages.

Imprint - Data protection