Welcome to the homepage of the lecture

Image Compression

Summer Term 2019

Image Compression

Received a Computer Science Teaching Award (Summer Term 2017)

Lecturer: Dr. Pascal Peter

Summer Term 2019

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

Monday 12-14 c.t., Building E1.3, Lecture Hall 001
Friday 14-16 c.t., Building E1.3, Lecture Hall 001
First lecture: Friday, April 12, 2019

G1: Thursday 8:30-10 s.t., Building E1.3, Seminar Room 016
G2: Thursday 10-12 c.t., Building E1.3, Seminar Room 016
First tutorial: Thursday, April 25, 2019

AnnouncementsDescriptionEntrance requirementsTutorialsExamsLecture notes/AssignmentsReferences

09/10/2019 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 11th, 2019 in the following timeslots, depending on your last (family) name:
A - Mo : 10:15 am - 10:45 am
Mü - Z : 10:45 am - 11:15 am

16/09/2019 An updated selftest problem has been uploaded that includes a few more transfer style questions.
23/07/2019 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 Friday, July 26th, 2019 in the following timeslots, depending on your last (family) name:
A - L : 10:15 am - 11:00 am
M - Z : 11:00 am - 11:45 am

12/07/2019 Please check here if you are admitted to the exam.
15/04/2019 Reminder: Lecture 3 has been moved to 17/04, 18:00 (sharp), Lecture Hall 001, due to the Easter holidays. Regular lectures resume on 26/04.
27/02/2019 Website is online.

Registration for this lecture was open until Monday, April 22. In addition to the individual registration, you also need to register for a tutorial group. If you have not done so already or want to change your group, you can do that here.
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 22, 2019 from 2:00 to 4:00 pm in Building E1.3, Lecture Hall 002.
The second written exam will take place on Monday, October 7, 2019 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 assignment 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.

Please check here whether you are admitted to the written exam. If you think that there is an error, please contact Pascal Peter immediately.

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 12/04 [download] [download]

PART I: Lossless Image Compression

2 Basic Entropy Coding I: Introduction to Information Theory 15/04 [download] [download]
3 Basic Entropy Coding II: Prefix-Free Codes
rescheduled due to public holidays: E1.3, HS001, 18-20 s.t.
17/04 [download] [download]
4 Basic Entropy Coding III: Huffman-Coding 26/04 [download] [download]
5 Basic Entropy Coding IV: Encoding Integers
11/07: corrected a typo on slide 11
29/04 [download] [download]
6 Arithmetic Coding I: Pure 0th-Order Coding 03/05 [download] [download]
7 Arithmetic Coding II: Integer Coding 06/05 [download] [download]
8 Adaptive and Higher Order Entropy Coding 10/05 [download] [download]
9 Higher Order Entropy Coding II: RLE, BWT, MTF, BZIP2 13/05 [download] [download]
10 Coding with Dictionaries 17/05 [download] [download]
11 Prediction by Partial Matching 20/05 [download] [download]
12 High-End Compression with PAQ 24/05 [download] [download]
13 Prediction, PNG, and gif 27/05 [download] [download]
14 Storing Binary Images 31/05 [download] [download]

PART II: Lossy Image Compression

15 Basics of Lossy Compression: Sampling and Quantisation 03/06 [download] [download]
16 Error Measures 07/06 [download] [download]
17 Transform-Coding I: Basic Concepts and JPEG
rescheduled due to public holidays: E1.3, HS001, 18-20 s.t.
12/06 [download] [download]
18 Transform-Coding II: JPEG2000, HEVC/BPG 14/06 [download] [download]
19 Fractal Image Compression 17/06 [download] [download]
20 Inpainting-based Compression I: PDE-based Interpolation (Inpainting Video, right click and save) 21/06 [download] [download]
21 Inpainting-based Compression II: Data Selection I
last updated on 24/06: fixed typos
24/06 [download] [download]
22 Inpainting-based Compression III: Data Selection II 28/06 [download] [download]
23 Inpainting-based Compression IV: Tonal Optimisation
rescheduled due to a conference
05/07 [download] [download]
24 Inpainting-based Compression V: R-EED 08/07 [download] [download]
25 Inpainting-based Compression VI: Exemplar-based Inpainting and Hybrid Approaches 12/07 [download] [download]
26 Image Compression with Convolutional Neural Networks 15/07 [download] [download]
27 A Short Introduction to Video Coding 19/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 17/04 C1: VDRs and Uniquely Decodable Codes
Solution C1
H1: Entropy Coding
Solution H1
2 25/04 C2: Extended Huffmann and Fibonacci Coding
Solution C2
H2: Entropy Coding
Solution H2
3 06/05 C3: Pure 0th Order Arithmetic Coding
Solution C3
H3: Arithmetic Coding
Solution H3
4 09/05 C4: Higher Order Coding
Solution C4
H4: Arithmetic Coding and BWT
Solution H4
5 20/05 C5: Higher Order Coding
Solution C5
H5: Dictionary Coding and PPM
Solution H5
6 27/05 no classroom work H6: LZSS, PAQ
Solution H6
7 03/06 C7: Predictions
Solution C7
Solution H7
8 12/06 C8: JPEG
Solution C8
see H7
9 17/06 no classroom work H9: JPEG
Solution H9
10 24/06 C10: Hausdorff Distance, Edge-based Compression
Solution C10
H10: Contraction Mappings
Solution H10
11 01/07 no classroom work H11: Inpainting and Data Selection
Includes bonus exercises.
02/07 corrected B1
Solution H11
12 08/07 C12: Subdivison Schemes
Solution C12
H12: Subdivision Schemes
Solution H12
13 24/06 Selftest Problem (will not be handed hin)
Selftest Solution
18/07 fixed typo in P1 (a).
-- 16/09 Updated Selftest Problem
Updated 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
last updated on 20/05: extended deadline
P3 Quantisation
P4 JPEG Light
last updated on 21/06: fixed typo in Makefile
P5 Inpainting and Data Optimisation
last updated on 06/07: fixed missing flag in homogenous inpainting

    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.

Imprint - Data protection