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

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

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

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

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.

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	H6: LZSS, PAQ 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	H9: JPEG 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	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	ic18-ex01.tar.gz
P2	Adaptive Arithmetic Coding	ic18-ex02.tar.gz
P3	Quantisation	ic18-ex03.tar.gz
P4	JPEG Light	ic18-ex04.tar.gz
P5	Inpainting and Data Optimisation	ic18-ex05.tar.gz

• 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.