Welcome to the homepage of the lecture

Image Compression

Summer Term 2018

Image Compression

Received a Computer Science Teaching Award (Summer Term 2017)

Lecturer: Dr. Pascal Peter

Summer Term 2018

Lecture (4h) with exercises (2h)
9 credit points

Monday 12-14 c.t., Building E1.3, Lecture Hall 001
Wednesday 10-12 c.t., Building E1.3, Lecture Hall 001
First lecture: Wednesday, April 11, 2018

G1: Thursday 14-16 c.t., Building E1.3, Seminar Room 015
G2: Thursday 16-18 c.t., Building E1.3, Seminar Room 015
First tutorial: Thursday, April 19, 2018

AnnouncementsDescriptionEntrance requirementsTutorialsExamsLecture notes/AssignmentsReferences

02/10/2018 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 Friday, October 5th, 2018, 10:15 am -- 11:15 am.
24/07/2018 You can find your result of the first exam here.
General statistics about this exam can be downloaded here.

18/07/2018 Lecture 28 takes place in E2.5, seminar room 4 (U16)
13/07/2018 Please check here if you are admitted to the exam.
18/04/2018 Registration is now closed.
11/04/2018 Registration is now open.
21/02/2018 Website is online

Registration for this lecture was open until Wednesday, April 18.

Keep in mind that in most courses of studies, you also have to register via the HISPOS system of the Saarland University

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 lossless image compression. We discuss the information theoretic background of so-called entropy coders (e.g. Huffman-coding, arithmetic coding, ...), talk about dictionary methods (e.g. LZW), and discuss state-of-the-art approaches like PPM and PAQ. These tools are not limited to compressing image data, but also form core parts of general data compression software such as BZIP2. Knowledge about entropy coding and prediction is key for understanding the classic and contemporary lossless codecs like PNG, gif or JBIG.

The second part of the lecture is dedicated to lossy image compression techniques. We deal with classic transformation based compression (JPEG, JPEG2000), but also with emerging approaches like inpainting-based compression. Furthermore, we consider related topics like human perception, error measurements, and offer a short introduction to video coding.

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. For the programming assignments, some elementary knowledge of C is required.

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. Homework consists of both theoretical and programming assignments, while classroom assignments are all theoretical. Working together in groups of up to 3 people is permitted and highly encouraged.

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

There will be two open book written exams:

The first written exam will take place on Monday, July 23, 2018 from 2:00 to 4:00 pm in Building E1.3, Lecture Hall 002.
The second written exam will take place on Monday, October 1, 2018 from 2:00 to 4:00 pm in Building E1.3, Lecture Hall 002.

You can find the detailed rules for our exams in the self test assignemnt that will be published towards the end of the semester.
You can participate in both exams, and the better grades counts. Please remember that you have to register online for the exam 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.

Lecture notes / Assignments

Participants can download course materials (lecture notes, assignments) here. For all assignments, example solutions will be provided. Additional organisational information, examples and explanations that may be relevant for your understanding and the exam are provided in the lectures and tutorials. It is solely your responsibility - not ours - to make sure that you receive this infomation.
The table below contains the planned topics for the lecture. The slides are available in two versions: the "script" version is printer friendly while the "slide" version retains the functionality to enlarge images and use slide navigation.

No. Title Date Script Slides
1 Introduction and Overview 11/04 [download] [download]

PART I: Lossless Image Compression

2 Basic Entropy Coding I: Introduction to Information Theory 16/04 [download] [download]
3 Basic Entropy Coding II: Prefix-Free Codes 18/04 [download] [download]
4 Basic Entropy Coding III: Huffman-Coding 23/04 [download] [download]
5 Basic Entropy Coding IV: Encoding Integers 25/04 [download] [download]
6 Arithmetic Coding I: Pure 0th-Order Coding 30/04 [download] [download]
7 Arithmetic Coding II: Integer Coding 02/05 [download] [download]
8 Adaptive and Higher Order Entropy Coding 07/05 [download] [download]
9 Higher Order Entropy Coding II: RLE, BWT, MTF, BZIP2 09/05 [download] [download]
10 Coding with Dictionaries 14/05 [download] [download]
11 Prediction by Partial Matching 16/05 [download] [download]
12 High-End Compression with PAQ 23/05 [download] [download]
13 Prediction, PNG, and gif 28/05 [download] [download]
14 Storing Binary Images 30/05 [download] [download]

PART II: Lossy Image Compression

15 Basics of Lossy Compression: Sampling and Quantisation 04/06 [download] [download]
16 Error Measures 06/06 [download] [download]
17 Transform-Coding I: Basic Concepts and JPEG 11/06 [download] [download]
18 Transform-Coding II: JPEG2000, HEVC/BPG 13/06 [download] [download]
19 Fractal Image Compression 18/06 [download] [download]
20 Inpainting-based Compression I: PDE-based Interpolation 20/06 [download] [download]
21 Inpainting-based Compression II: Data Selection I 25/06 [download] [download]
22 Inpainting-based Compression III: Data Selection II 27/06 [download] [download]
23 Inpainting-based Compression IV: Tonal Optimisation 02/07 [download] [download]
24 Inpainting-based Compression V: Subdivision Approaches 04/07 [download] [download]
25 Inpainting-based Compression VI: Exemplar-based Inpainting and Hybrid Approaches 09/07 [download] [download]
26 Image Compression with Convolutional Neural Networks 11/07 [download] [download]
27 A Short Introduction to Video Coding 16/07 [download] [download]
28 Summary and Outlook 18/07 [download] [download]

The assignments and the source code needed for the programming assignments will be provided here during the semester.

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 18/04 C1: VDRs and Uniquely Decodable Codes
Solution C1
H1: Entropy Coding
Solution H1
2 25/04 C2: Entropy Coding
Solution C2
H2: Entropy Coding
Solution H2
3 02/05 C3: Extended Huffman and Fibonacci Coding
Solution C3
H3: Arithmetic Coding
Solution H3
4 09/05 C4: No Classroom Work H4: Arithmetic Coding and BWT
Solution H4
5 16/05 C5: Higher Order Coding
Solution C5
H5: Dictionary Coding and PPM
Solution H5
6 23/05 C6: LZ78, LZW
Solution C6
Solution H6
7 30/05 C7: no classroom work H7: JBIG, JPEG-LS
Solution H7
8 04/06 C8: Predictions
Solution C8
H8: Quantisation
Solution H8
9 13/06 C9: JPEG
Solution C9
Solution H9
10 20/06 C10: Contraction Mappings, Hausdorff Distance
Solution C10
H10: Contraction Mappings
Solution H10
11 27/06 C11: Diffusion and Chain Codes
Solution C11
H11: Inpainting and Data Selection
Solution H11
12 04/07 C12: Subdivison Schemes
Solution C12
H12: Subdivision Schemes
Sol. H12
13 11/07 Selftest Problem (will not be handed hin)
Selftest Solution

In addition to the theoretical exercises, programming assignments can be downloaded below. They mostly follow a two-week rythm. The exact deadline can be found in the corresponding assignment descriptions.

No. Exercise Materials
P1 Huffman Coding
P2 Adaptive Arithmetic Coding
P3 Quantisation
P4 JPEG Light
P5 Inpainting and Data Optimisation

  • B. Jähne, H. Haußecker, P. Geißler, editors, Handbook of Computer Vision and its Applications. Volume 1: Sensors and Imaging. Academic Press, San Diego 1999.
  • S. Webb, The Physics of Medical Imaging. Institute of Physics Publishing, Bristol 1988.
  • C. L. Epstein, Introduction to the Mathematics of Medical Imaging. Pearson, Upper Saddle River 2003.
  • R. Blahut, Theory of Remote Image Formation. Cambridge University Press, 2005.
  • A. C. Kak, M. Slaney, Principles of Computerized Tomographic Imaging. SIAM, Philadelphia 2001.
  • Articles from journals and conferences.

Further references will be given during the lecture.

MIA Group
The author is not
responsible for
the content of
external pages.

Imprint - Data protection