Welcome to the homepage of the lecture

Interpolation and Approximation for Visual Computing

Winter Term 2022

Interpolation and Approximation for Visual Computing

Lecturer: Vassillen Chizhov

Examiner: Dr. Joachim Weickert

Winter Term 2022

Lectures (3h) with exercises (1h);
(6 ETCS points)

Lectures: Sessions with Q&A and Tutorial Sections
The lectures will be held online (Zoom link shared over e-mail)
Monday, 14:15-16:00
Thursday, 14:15-16:00

AnnouncementsDescriptionPrerequisitesTutorialsRegistrationExamContents Assignments Literature

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.

In order to register for the lecture, write an e-mail to Vassillen Chizhov.
The subject line must begin with the tag [IAVC22].
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 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.

There will be two written exams: the first on 21.02, 14-17 (E1 3, HS002), and the second on 21.03, 14-17. 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.

Title Date
Mock Exam 1: Polynomials and Splines 17.11.2022

Course material will be made available on this homepage. Additional organizational information, examples and explanations that may be relevant for your understanding and the exam are provided in the online sessions and tutorials.

Introductory Slides

Here you can find: Dr. Augustin's notes.
We will follow the above notes for some topics (e.g. polynomials). However, I will occasionally provide more details on specific topics, and less on others. This will be made clear during the lectures. For instance, I plan to cover some more applications for interpolation and approximation for higher dimensions (e.g. finite elements, PDE inpainting).

Date Please prepare Pages
27.10.2022 Polynomial Interpolation, Lagrange Basis 1--4
31.10.2022 Polynomial Interpolation, Newton Interpolation 5--12
03.11.2022 Interpolation Error, Polynomial Approximation 13--22
07.11.2022 Splines I 23--34
10.11.2022 Splines II: B-Splines 34--46
14.11.2022 Splines III: Approximation and Smoothing Splines 46--53
17.11.2022 Solving Mock Exam I
21.11.2022 Solving Mock Exam I
24.11.2022 Higher Dimensions I: Mairhuber-Curtis Theorem and Multivariate Polynomials 55--59
28.11.2022 Higher Dimensions II: Tensor Product Splines, Affine Transformations 59--67
01.12.2022 Higher Dimensions III: Voronoi, Delaunay, and Multiharmonic Reconstruction 67--74
05.12.2022 Fourier Theory I: Approximation in Orthonormal Bases, Fourier Series 74--88
08.12.2022 Fourier Theory II: Fourier Transform, Convolution 88--98
12.12.2022 Fourier Theory III: Discrete Fourier and Cosine Transforms 98--101
15.12.2022 Fourier Theory IV: Degradation Phenomena in Reconstruction 101-110
19.12.2022 Synthesis Functions I: Sampling Theorem 111-115
22.12.2022 Synthesis Functions II: Inteprolation Using Synthesis Functions 115-124
02.01.2023 Synthesis Functions III: Transfer to Higher Dimensions 124-135
05.01.2023 Synthesis Functions IV: From Energy Minimizing Ideas 135-143
09.01.2023 Interpolation and Approximation in Inner Product Spaces
12.01.2023 Trigonometric Polynomial Approximation Exercises
16.01.2023 Interpolation in Reproducing Kernel Hilbert Spaces
19.01.2023 Fourier Transform, Convolution, Interpolation Exercises
23.01.2023 Convolution, Bochner's Theorem Exercises
26.01.2023 Mock Exam: Chebyshev Polynomials
30.01.2023 Mock Exam: Monomial, Newton, Lagrange, Hermite Bases
02.02.2023 Mock Exam: Hermite, De Casteljau, Approximation, Splines
06.02.2023 Mock Exam: B-Splines, Fourier, Theory

Title Date
Piecewise Constant Voronoi Interpolation and Approximation 06.12.2022
Tiled DCT-II Image Approximation 21.12.2022

Title Date
Mairhuber-Curtis Theorem 12.12.2022
Diagonalizing Properties of the Discrete Cosine Transforms 12.12.2022
The Discrete Cosine Transform 12.12.2022
Matrices Diagonalized by the Discrete Cosine and Discrete Sine Transforms 12.12.2022
Polyharmonic Splines Interpolation (Duchon) 05.01.2023
Ployharmonic Splines Interpolation (Meinguet) 05.01.2023

Title Date
Newton Interpolation, Least Squares 06.11.2022
Splines I 10.11.2022

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

MIA Group
The author is not
responsible for
the content of
external pages.

Imprint - Data protection