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

Lectures:
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

Tutorials:
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

Announcements – Description – Entrance requirements – Tutorials – Exams – Lecture notes/Assignments – References

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.

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	H7: JBIG, JPEG-LS 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).	N/A
--	16/09	Updated Selftest Problem Updated Selftest Solution	N/A

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	ic19-ex01.tar.gz
P2	Adaptive Arithmetic Coding last updated on 20/05: extended deadline	ic19-ex02.tar.gz
P3	Quantisation	ic19-ex03.tar.gz
P4	JPEG Light last updated on 21/06: fixed typo in Makefile	ic19-ex04.tar.gz
P5	Inpainting and Data Optimisation last updated on 06/07: fixed missing flag in homogenous inpainting	ic19-ex05.tar.gz

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.





---