Image Compression
Lecturer:
Pascal Peter
Summer Term 2017
Lecture (2h) with exercises (2h)
6 credit points
Lecture: Thursday 12-14 c.t., Building E1.3, Lecture Hall 001
First lecture: Thursday, April 20, 2017.
Tutor: Nane Neu
Office Hours: Wed 10-11, Building E1.3, Room 4.15
Tutorials:
G1 Monday 12-14 c.t., Building E1.3, Lecture Hall 001
G2 Wednesday 8:30-10 sharp, Building E1.3, Seminar Room 107
First tutorial: Monday, April 20, 2017.
Announcements –
Description –
Entrance requirements –
Tutorials –
Exams –
Lectures –
Assignments –
References
11/10/2017: The results of the second exam are now available.
04/08/2017: The results of the first exam are now available.
05/05/2017: Tutorial registration is closed.
27/04/2017: Tutorial registration is open.
New tutorial group available in two weeks (see lecture notes for details). Also note that the next
tutorial has been moved due to a holiday.
27/04/2017: Registration is closed.
20/04/2017: Registration is open.
14/03/2017: Website is online
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 11 assignments, this comes down to 11 x 12 = 132 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, August 3, 2017
at 2:00 pm in Building E1.3, Lecture Hall 002.
The second written exam will take place on Monday, October 9, 2017
at 2:00 pm in Building E1.3, Lecture Hall 002.
These are open book exams.
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.
Registration for this lecture was open until Thursday, April 27. If you did not register yet, please contact Pascal Peter.
Please remember that you also have to register online for both exams individually
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.
Results and Exam Inspection
You can find your result of the first exam here.
General statistics about this exam can be downloaded here.
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, August 12, 2017 in the following timeslots by family name:
A-M: 11:00 - 11:30
N-Z: 11:30 - 12:00
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
|
20/04 |
[download] |
[download] |
2 |
Theoretical Background and Entropy Coding I
|
27/04 |
[download] |
[download] |
3 |
Entropy Coding II
|
04/05 |
[download] |
[download] |
4 |
Arithmetic Coding I
|
11/05 |
[download] |
[download] |
5 |
Arithmetic Coding II and Adaptive Entropy Coding
|
18/05 |
[download] |
[download] |
6 |
Higher Order Coding, RLE, BWT, MTF, and Bzip2
Due to a holiday, this lecture is shifted:
23/05, 6 pm, E1.3, Lecture Hall 003
|
23/05 |
[download] |
[download] |
7 |
Coding with Dictionaries
|
01/06 |
[download] |
[download] |
8 |
PPM and PAQ
Due to a holiday, this lecture is shifted:
13/06, 6 pm, E1.3, Lecture Hall 003
|
13/06 |
[download] |
[download] |
9 |
Prediction and Lossless Image Compression (PNG, JPEG-LS, JBIG)
|
22/06 |
[download] |
[download] |
10 |
Basics of Lossy Image Compression and Fractal Image Compression
|
29/06 |
[download] |
[download] |
11 |
Transform-Based Image Compression (JPEG and JPEG 2000)
|
06/07 |
[download] |
[download] |
12 |
PDE-based Image Compression I
Video: Colour Inpainting
Video: Sparsification
|
13/07 |
[download] |
[download] |
13 |
PDE-based Image Compression II
|
20/07 |
[download] |
[download] |
14 |
Video Compression - An Overview
|
27/07 |
[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. |
Date |
Classroomwork |
Homework |
1 |
24/04 |
Classroom Work 1: VDRs and Uniquely Decodable Codes
(Optional Hint Sheet)
Sol. C1
|
N/A
|
2 |
03/05 |
Classroom Work 2: Entropy Coding
(Optional Hint Sheet)
Sol. C2
Due to a holiday, this tutorial is shifted:
03/05, 6 pm, E1.3, Lecture Hall 001
|
Homework 2: Entropy Coding
Sol. H2
|
3 |
08/05 |
Classroom Work 3: Extended Huffman and Fibonacci Coding
Sol. C3
|
Homework 3: Golomb and Fibonacci Coding
Sol. H3
|
4 |
15/05 |
Classroom Work 4: Pure Arithmetic Coding
(Optional Hint Sheet)
Sol. C4
|
Homework 4: Pure Arithmetic Coding
Sol. H4
|
5 |
22/05 |
Classroom Work 5: Integer Arithmetic Coding
(Optional Hint Sheet)
Sol. C5
|
Homework 5: Pure and Integer Arithmetic Coding
Sol. H5
|
6 |
29/05 |
Classroom Work 6: RLE, Higher-Order Entropy Coding
(Optional Hint Sheet)
Sol. C6
|
Homework 6: RLE, BWT, MTF
Sol. H6
|
7 |
12/06 |
Classroom Work 7: LZ78 and LZW
Sol. C7
|
Homework 7: LZSS
Sol. H7
|
8 |
19/06 |
Classroomwork 8: LZW
Sol. C8
|
Homework 8: PPM and PAQ
Sol. H8
|
9 |
26/06 |
Classroom Work 9: Prediction
Sol. C9
|
Homework 9: JBIG and JPEG-LS
Sol. H9
|
10 |
03/07 |
Classroom Work 10: Contraction Mappings, Hausdorff Distance
Sol. C10
|
Homework 10: Contraction Mappings
Sol. H10
|
11 |
10/07 |
Classroom Work 11: JPEG, YUV
Sol. C11
|
Homework 11: DCT, JPEG
Sol. H11
|
12 |
17/07 |
Classroom Work 12: Subdivison Schemes
Sol. C12
|
Homework 12: Subdivision Schemes
Sol. H12
|
13 |
24/07 |
Selftest Problem (will not be handed hin)
Selftest Solution
|
N/A
|
Participants can download optional programming assignments here.
Submitting your solutions to
these exercises together with some feedback yields up to 6 bonus points.
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.
|