Welcome to the Homepage of the Lecture

Image Compression

Winter Term 2014 / 2015

Image Compression

Lecturer: Pascal Peter

Examiner: Prof. Dr. Joachim Weickert

Winter Term 2014 / 2015
Lecture (2h) with exercises (2h) 6 credit points

Lecture: Thursday 10-12 c.t., Building E1.3, Lecture Hall 003
G1 Monday 14-16 c.t., Building E1.3, Lecture Hall 003
G2 Monday 16-18 c.t., Building E1.3, Lecture Hall 003

First lecture: Thursday, October 23, 2014.
First tutorial: Monday, November 3, 2014.

AnnouncementsDescriptionEntrance requirementsTutorialsExams LecturesAssignmentsReferences

14/04/2015: The results of the second exam are now available.
20/02/2015: The results of the first exam are now available.
12/02/2015: The admission list ist now online.
05/01/2015: Some mistakes in the schedule change information in Lecture 8 and Homework 8 were corrected. Sorry for the inconvenience.
18/12/2014: There are some schedule changes for January. Details can be found in Lecture 8.
21/11/2014: Group registration is now closed.
14/11/2014: In order to improve the lecture, we have added a second tutorial group!
03/11/2014: Registration is now officially closed.
21/10/2014: Registration is now open.
30/07/2014: Due to a conference in October, there is no tutorial on October 27 and no lecture on October 30.

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 12 assignments, this comes down to 12 x 12 = 144 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, February 19, 2015 at 2:00 pm in Building E2.2, Günter Hotz Lecture Theatre.
The second written exam will take place on Monday, April 13, 2015 at 2:00 pm in Building E1.3, Lecture Hall 002.
These are open book exams. You can find the rules for our exams in the
self test.
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.

Please remember that you also 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.

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 Thursday, April 16th, 2015 in the following timeslots, depending on your last (family) name:
A - M : 14:00 pm - 14:45 pm
N - Z : 14:45 pm - 15:30 pm

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

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 23/10 [download] [download]
2 Theoretical Background and Entropy Coding I 06/11 [download] [download]
3 Entropy Coding II 13/11 [download] [download]
4 Arithmetic Coding I 20/11 [download] [download]
5 Arithmetic Coding II and Adaptive Entropy Coding 27/11 [download] [download]
6 Higher Order Coding, RLE, BWT, MTF, and Bzip2 04/12 [download] [download]
7 Coding with Dictionaries 11/12 [download] [download]
8 PPM and PAQ 18/12 [download] [download]
9 Prediction and Lossless Image Compression (PNG, JPEG-LS, JBIG) 05/01 [download] [download]
10 Basics of Lossy Image Compression and Fractal Image Compression 08/01 [download] [download]
11 Transform-Based Image Compression (JPEG and JPEG 2000) 22/01 [download] [download]
12 PDE-based Image Compression I 29/01 [download] [download]
13 PDE-based Image Compression II 05/02 [download] [download]
14 Video Compression - An Overview 12/02 [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. Assignments Date Solutions
1 Classroom Work 1: VDRs and Uniquely Decodable Codes (Optional Hint Sheet) 23/10 Sol. C1
2 Classroom Work 2: Entropy Coding (Optional Hint Sheet)
Homework 2: Entropy Coding
6/11 Sol. C2
Sol. H2
3 Classroom Work 3: Extended Huffman and Fibonacci Coding
Homework 3: Golomb and Fibonacci Coding
13/11 Sol. C3
Sol. H3
4 Classroom Work 4: Pure Arithmetic Coding
Homework 4: Pure Arithmetic Coding
20/11 Sol. C4
Sol. H4
5 Classroom Work 5: Integer Arithmetic Coding
(Optional Hint Sheet)
Homework 5: Pure and Integer Arithmetic Coding
27/11 Sol. C5
Sol. H5
6 Classroom Work 6: RLE, Higher-Order Entropy Coding
(Optional Hint Sheet)
Homework 6: RLE, BWT, MTF
4/12 Sol. C6
Sol. H6
7 Classroom Work 7: LZ78 and LZW
Homework 7: LZSS
11/12 Sol. C7
Sol. H7
8 Homework 8: PPM, PAQ and LZW 18/12 Sol. H8
9 Classroom Work 9: Prediction
Homework 9: JBIG, JPEG-LS and Contractive Mappings
08/01 Sol. C9
Sol. H9
10 Classroom Work 10: Contraction Mappings, Hausdorff Distance 16/01 Sol. C10
11 Classroom Work 11: JPEG, YUV
Homework 11: DCT, JPEG
22/01 Sol. C11
Sol. H11
12 Classroom Work 12: R-EED, BTTC
Homework 12: EEDC, BTTC
29/01 Sol. C12
Sol. H12
13 Selftest Problem (will not be handed hin) 05/02 Solution

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