Interpolation and Approximation for Visual Computing
Dr. Matthias Augustin
Winter Term 2020
Lectures (3h) with exercises (1h);
(6 ETCS points)
Lectures: Online Sessions with Q&A and Tutorial Sections
Monday, 16:15-18:00
Thursday, 12:15-14:00
First online session: Thursday, November 05th, 2020
Announcements –
Description –
Prerequisites –
Tutorials –
Registration –
Exam –
Contents –
Assignments –
Literature
- 2021-02-02:
Sample solution to Assignment 05 online.
- 2021-01-25: Assignment 05 is online.
You can submit this assignment until 2021-02-01, 18:00 via e-mail to
Matthias Augustin.
Lecture notes updated: Including a missing factor in the third line of
Equation (5.1.10).
- 2020-11-23:
Exam guidelines online. Please note that you have submit a declaration of
consent for the exam to be held in digital form via video conference.
Quiz 05 online.
- 2020-10-29:
Schedule online. Reference version of lecture notes online. Introductory
slides online.
- 2020-10-05:
In order to protect your health and inhibit the spread of Sars-Cov2, this
year's iteration of IAVC will be fully digital. We will use Microsoft
Teams for communication and distributing lecture content. Regular teaching
will begin on Thursday, November 5, 2020, but you can already register for
the course.
Target group: Students in the Master Programme Visual Computing
Lecture aim: Give an introduction to the concepts of interpolation
and (function) approximation. This includes
- interpolation with polynomials,
- least-square fitting,
- polynomial splines,
- some Fourier theory,
- radial basis functions, and
- applications in image processing.
This course is suitable for students of visual computing, mathematics, and
computer science.
Students attending this course should be familiar with basic concepts of
(multi-dimensional) calculus and linear algebra as covered in introductory
maths course (such as Mathematik für Informatiker I-III). Mathematical
prerequisites which exceed the basic mathematics courses are provided within
the lecture notes. All material will be in English. Knowledge from image
processing may be helpful, but is not required.
Due to the current sitation caused by SARS-Cov2, this lecture will be closer
to an inverted classroom / blended learning setting. This means that for each
live online sessions, students will be required to prepare using the available
material. A schedule detailing the amount of content that you need to prepare
will be made available at the start of the lecturing period. Live sessions
themselves are intended to follow a Q&A structures and might present further
exercise material.
Due to a shorter lecture period, there will be a total of 5
homework assignments which will be graded.
Assignments will be published on the Teams file repository and this website.
Students are expected to submit their solutions to these assignments via email
to
Matthias Augustin within
one week after publications.
Working together in groups of up to 3 students is permitted and encouraged.
Some assignments contain programming exercises.
In order to qualify for the final exam, it is necessary to achieve 50% of the
points of all assignment sheets in total. All exams will be oral.
In order to register for the lecture, write an e-mail to
Matthias Augustin.
Registration is open until Monday, November 16, 12 am.
The subject line must begin with the tag [IAVC20].
Please use the following template for the e-mail:
First name: myFirstName
Last name: myLastName
Date of birth: dd.mm.yyyy
Student ID number: ...
Course of study: Bachelor/Master/...
Subject: Computer Science/Visual Computing/Mathematics/...
Note that the e-mail address from which you send this information will be used
to provide you with urgent information concerning the lecture.
Such information may include further regulations or urgent additional
remarks regarding assignment.
The information that you provide in your registration will be used to add
you to the course in MS Teams. As this addition needs to be done manually, it
might be delayed.
The registration is completely independent of
LSF/HISPOS.
They require a separate registration.
According to the regulations concerning storage and processing of
personal data (Art. 6 (1) Datenschutzgrundverordnung (DSGVO)) we
store and process your personal data for the purpose of lecture and
tutorial organisation only. I.e. we may use them to contact you, to
inform you about your grade, and to transmit your grades to the
examination office.
In order to qualify for the final exam, it is necessary to achieve 50% of the
points of all assignment sheets in total.
There will be two oral exams, one at the beginning and one at the end of
the semester break. In case of qualification, you are allowed to take part in
both exams. The better grade counts, but each exam will count as an attempt
individually.
Please remember that you have to register online for the exam
in the HISPOS system of the
Saarland University for each attempt separately.
The first exam takes place on
Monday, February 22, 2021.
The second exam takes place on
Wednesday, March 31, 2021.
Due to the ongoing pandemic of Sars-Cov2, exams will be conducted via
MS Teams. Further information is provided by these
guidelines
Note that in order to take the exam in this format, you have to submit a
declaration of consent.
This declaration of consent is in German and you have to submit the German
form. A translation to English for your convenience is available
here.
Introductory slides
Lecture notes
reference version
newest version
Topics for online sessions are according to the following schedule.
Links to additional exercises will be added to the schedule after each live session.
Date |
Please prepare |
Pages |
11/05 |
Chapter 1 up to Lemma 1.5
|
1--7 |
11/09 |
Theorem 1.6 to Example 1.15
|
7--15 |
11/12 |
Section 1.2
|
15--21 |
11/16 |
Chapter 2 up to Remark 2.11
|
23--30 |
11/19 |
Lemma 2.12 to Theorem 2.20
|
30--36 |
11/23 |
Lemma 2.21 to Corollary 2.26
|
36--43 |
11/26 |
Assignment 01
|
-- |
11/30 |
After Corollary 2.26 to end of Chapter 2
|
43--51 |
12/03 |
Chapter 3 up to before Section 3.2.1
|
53--60 |
12/07 |
Sections 3.2.1 and 3.2.2
|
60--65 |
12/10 |
Assignment 02
|
-- |
12/14 |
Section 3.3
|
65--72 |
12/17 |
Chapter 4 up to Example 4.5
|
73--78 |
01/04 |
Theorem 4.6 to Example 4.15
|
78--85 |
01/07 |
Assignment 03
|
-- |
01/11 |
Remark 4.16 to Remark 4.23
|
86--92 |
01/14 |
Lemma 4.24 to end of Section 4.3.2
|
92--99 |
01/18 |
Chapter 5 up to Remark 5.8
|
109--115 |
01/21 |
Assignment 04
|
-- |
01/25 |
After Remark 5.8 to Figure 5.2.4
|
115--122 |
01/28 |
Section 5.3 up to Example 5.19
|
122--131 |
02/01 |
Remark 5.20 to end of Section 5.4
|
131--139 |
02/04 |
Assignment 05
|
-- |
No. |
Title |
Date |
|
Submit until |
Assignment 01 |
Newton Interpolation |
11/16 |
[download] |
11/23 |
Assignment 02 |
Interpolation with B-Splines |
11/30 |
[download] |
12/07 |
Assignment 05 |
Interpolation with Synthesis Functions |
01/25 |
[download] |
02/01 |
No. |
Title |
Date |
|
Submit until |
Assignment 01 |
Interpolation and Approximation with Polynomials |
11/16 |
[download] |
11/23 |
Assignment 02 |
Splines and B-Splines |
11/30 |
[download] |
12/07 |
Assignment 03 |
Splines in 2D |
12/14 |
[download] |
01/04 |
Assignment 04 |
Trigonometric Polynomials |
01/11 |
[download] |
01/18 |
Assignment 05 |
Sampling Theorem and Synthesis Functions |
01/25 |
[download] |
02/01 |
No. |
Title |
Date |
|
Assignment 01 |
Interpolation and Approximation with Polynomials |
11/24 |
[download] |
Assignment 01 |
Sample Programme: Newton Interpolation |
11/24 |
[download] |
Assignment 02 |
Splines and B-Splines |
12/08 |
[download] |
Assignment 02 |
Sample Programme: Interpolation with B-Splines |
12/08 |
[download] |
Assignment 03 |
Splines in 2D |
01/05 |
[download] |
Assignment 04 |
Trigonometric Polynomials |
01/19 |
[download] |
Assignment 05 |
Sampling Theorem and Synthesis Functions |
02/02 |
[download] |
Assignment 05 |
Sample Programme: Interpolation with Synthesis Functions |
11/24 |
[download] |
There is no specific text book for this class as it touches on many topics
for which specialized books exist.
-
Introduction to Numerical Analysis
J. Stoer, R. Bulirsch, Springer, 1993.
English translation of the originally german version.
-
Numerical Methods
W. Boehm, H. Prautzsch, CRC Press, 1993.
-
Interpolation and Approximation
P. Davis, Blaisdell, 1963.
Reprinted by Dover, 2014.
-
Approximation Theory
O. Christensen, K. Christensen, Springer, 2005.
-
Mathematics of Approximation
J. de Villiers, Springer, 2012.
-
Fourier Analysis and Applications
C. Gasquet, P. Witomski, Springer, 1999.
-
The Fourier Transform and its Applications
R. N. Bracwell, McGraw Hill, 1999.
-
A Practical Guide to Splines
C. de Boor, Springer, 2001.
-
Multivariate Splines
C. Chui, SIAM, 1991.
-
Scattered Data Interpolation
H. Wendland, Cambridge University Press, 2005.
Most of these and further books can be found in the
mathematics and computer science library.
Further references will be provided during the lecture.
|