Welcome to the Homepage of the Lecture

Image Compression

Summer Term 2017

Image Compression

Lecturer: Pascal Peter

Summer Term 2017
Lecture (2h) with exercises (2h) 6 credit points

Lecture: Thursday 12-14 c.t., Building E1.3, Lecture Hall 001
First lecture: Thursday, April 20, 2017.

Tutor: Nane Neu
Office Hours: Wed 10-11, Building E1.3, Room 4.15

G1 Monday 12-14 c.t., Building E1.3, Lecture Hall 001
G2 Wednesday 8:30-10 sharp, Building E1.3, Seminar Room 107
First tutorial: Monday, April 20, 2017.

AnnouncementsDescriptionEntrance requirementsTutorialsExams LecturesAssignmentsReferences

04/08/2017: The results of the first exam are now available.

05/05/2017: Tutorial registration is closed.
27/04/2017: Tutorial registration is open. New tutorial group available in two weeks (see lecture notes for details). Also note that the next tutorial has been moved due to a holiday.
27/04/2017: Registration is closed.
20/04/2017: Registration is open.
14/03/2017: 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 11 assignments, this comes down to 11 x 12 = 132 points.

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

The first written exam will take place on Thursday, August 3, 2017 at 2:00 pm in Building E1.3, Lecture Hall 002.
The second written exam will take place on Monday, October 9, 2017 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 for this lecture was open until Thursday, April 27. If you did not register yet, please contact Pascal Peter. 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.

Results and Exam Inspection

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

Each student who has participated in the first written exam has the opportunity to inspect his/her graded solutions in room 4.10 in Bldg. E1.7 on Tuesday, August 8, 2017 in the following timeslots by family name:
A-M: 14:00 pm - 14:45 pm
N-Z: 14:45 pm - 15:30 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 20/04 [download] [download]
2 Theoretical Background and Entropy Coding I 27/04 [download] [download]
3 Entropy Coding II 04/05 [download] [download]
4 Arithmetic Coding I 11/05 [download] [download]
5 Arithmetic Coding II and Adaptive Entropy Coding 18/05 [download] [download]
6 Higher Order Coding, RLE, BWT, MTF, and Bzip2
Due to a holiday, this lecture is shifted:
23/05, 6 pm, E1.3, Lecture Hall 003
23/05 [download] [download]
7 Coding with Dictionaries 01/06 [download] [download]
8 PPM and PAQ
Due to a holiday, this lecture is shifted:
13/06, 6 pm, E1.3, Lecture Hall 003
13/06 [download] [download]
9 Prediction and Lossless Image Compression (PNG, JPEG-LS, JBIG) 22/06 [download] [download]
10 Basics of Lossy Image Compression and Fractal Image Compression 29/06 [download] [download]
11 Transform-Based Image Compression (JPEG and JPEG 2000) 06/07 [download] [download]
12 PDE-based Image Compression I
Video: Colour Inpainting Video: Sparsification
13/07 [download] [download]
13 PDE-based Image Compression II 20/07 [download] [download]
14 Video Compression - An Overview 27/07 [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. Date Classroomwork Homework
1 24/04 Classroom Work 1: VDRs and Uniquely Decodable Codes
Optional Hint Sheet)
Sol. C1
2 03/05 Classroom Work 2: Entropy Coding
Optional Hint Sheet)
Sol. C2
Due to a holiday, this tutorial is shifted:
03/05, 6 pm, E1.3, Lecture Hall 001
Homework 2: Entropy Coding
Sol. H2
3 08/05 Classroom Work 3: Extended Huffman and Fibonacci Coding
Sol. C3
Homework 3: Golomb and Fibonacci Coding
Sol. H3
4 15/05 Classroom Work 4: Pure Arithmetic Coding (Optional Hint Sheet)
Sol. C4
Homework 4: Pure Arithmetic Coding
Sol. H4
5 22/05 Classroom Work 5: Integer Arithmetic Coding
Optional Hint Sheet)
Sol. C5
Homework 5: Pure and Integer Arithmetic Coding
Sol. H5
6 29/05 Classroom Work 6: RLE, Higher-Order Entropy Coding
Optional Hint Sheet)
Sol. C6
Homework 6: RLE, BWT, MTF
Sol. H6
7 12/06 Classroom Work 7: LZ78 and LZW
Sol. C7
Homework 7: LZSS
Sol. H7
8 19/06 Classroomwork 8: LZW
Sol. C8
Homework 8: PPM and PAQ Sol. H8
9 26/06 Classroom Work 9: Prediction
Sol. C9
Homework 9: JBIG and JPEG-LS
Sol. H9
10 03/07 Classroom Work 10: Contraction Mappings, Hausdorff Distance
Sol. C10
Homework 10: Contraction Mappings
Sol. H10
11 10/07 Classroom Work 11: JPEG, YUV
Sol. C11
Homework 11: DCT, JPEG
Sol. H11
12 17/07 Classroom Work 12: Subdivison Schemes
Sol. C12
Homework 12: Subdivision Schemes
Sol. H12
13 24/07 Selftest Problem (will not be handed hin)
Selftest Solution

Participants can download optional programming assignments here. Submitting your solutions to these exercises together with some feedback yields up to 6 bonus points.

No. Exercise Materials
P1 Adaptive Arithmetic Coding
P1 JPEG Light

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
The author is not
responsible for
the content of
external pages.