Welcome to the homepage of the lecture

Interpolation and Approximation for Visual Computing

Winter Term 2023/2024

Home
About Us
People
Teaching
Research
Publications
Awards
Links
Contact
Internal

Interpolation and Approximation for Visual Computing

Lecturer: Vassillen Chizhov

Examiner: Dr. Joachim Weickert

Winter Term 2023/2024

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

Lectures: Sessions with Q&A and Tutorial Sections
The lectures will be held online (Zoom link has been shared over e-mail)
The tutorials will be held offline in E1.3 HS003
Wednesday, 10:15-12:00 (online)
Friday, 10:15-12:00 (E1.3 HS003)
Send me an e-mail if you haven't received an e-mail with the zoom link

Announcements – Description – Prerequisites – Tutorials – Registration – Exam – Contents – Complementary Material – Literature


Description

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 and approximation with polynomials
  • polynomial splines
  • least-squares fitting
  • some Fourier theory
  • PDE-based interpolation
  • radial basis functions
  • applications in image processing


Prerequisites

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.


Registration

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


Exams

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 written exams: the first on 29.02, 14-18 (E1 3, HS002), and the second on 28.03, 14-18 (E1 3, HS003) as seen in the exam calendar (you have to scroll down the page). You can bring an A4 "cheat" sheet (you can use both sides) handwritten by you yo the exam. 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.


Contents

Introductory Slides

Here you can find: Dr. Augustin's notes.
You can (and should) use the above notes and the course books to get more familiar with the material discussed during the lectures. While the books and notes provide some of the material, there may be topics discussed during the lectures that are included in neither.

Date Slides Notes Pages
25.10.2023 Polynomial Interpolation, Lagrange Basis 1--4
27.10.2023 Tutorial: Polynomial Interpolation, Determinant, Linear Systems, Lagrange Basis 1--4
01.11.2023 National Holiday
03.11.2023 Tutorial: Polynomial Interpolation, Determinant, Linear Systems, Lagrange Basis 1--4
08.11.2023 Monomial, Lagrange, and Newton Basis 4--12
10.11.2023 Tutorial: Monomial, Lagrange, and Newton Basis 4--12
15.11.2023 Interpolation Error, Approximation, Bernstein Basis 13--22
17.11.2023 Tutorial: Interpolation Error, Approximation, Bernstein Basis 13--22
22.11.2023 Tutorial: Interpolation Error, Approximation, Bernstein Basis 13--22
24.11.2023 Tutorial: Approximation
Solution: Divided Differences and Least-Squares 		13--22
29.11.2023 Splines and Mairhuber-Curtis. 23--55
01.12.2023 Tutorial: Splines 23--55
06.12.2023 Homework 1 Solutions 1--22
08.12.2023 Tutorial: Splines 23--55
13.12.2023 Scattered Data Interpolation and Approximation in 2D 55--74
15.12.2023 Tutorial: Multivariate Polynomials, Linear Triangles 55--74
20.12.2023 Tutorial: Polynomial Interpolation as ODE solution 23--34
22.12.2023 Tutorial: Polynomial Interpolation as ODE solution 23--34
27.12.2023 Winter Holidays
29.12.2023 Winter Holidays
03.01.2024 Splines: PDE and Variational Formulation 27--30, 135--138
05.01.2024 Tutorial: Approximation with P1 Elements
Solution: Approximation with P1 Elements 		67--74
10.01.2024 Tutorial: Splines PDE and Variational Formulation 27--30, 135--138
17.01.2024 Positive-definite Kernels, Fourier Transform 75--143
19.01.2024 Tutorial: Discretisation of Polyharmonic Interpolation 27--30, 135--138
24.01.2024 Complex Differentiation, Fourier Series, Fourier Transform 75--143
26.01.2024 Tutorial: Discretisation PDEs and Variational Formulation 27--30, 135--138


Complementary Code

Complementary Material

Date Reading Material
25.10.2023
  • Chapter 1 in Villiers' book until Lagrange basis
  • Chapter 2 in Davis' book until Systems Possessing the Interpolation Property
  • Chapter 1 in Fasshauer's book until the Mairhuber-Curtis theorem
  • Chapter 2 in Prenter's book until Method III (Newton)
27.10.2023 As practice you can solve exercises from chapter 2 to 2.5 in LADW. If you want some more details on the determinant see chapter 3 also.

You can also try exercises from Chapter 1 of Hoffman and Kunze's book.

For a book with more visualisations you can try Chapter 1 of this book.

Some videos on linear systems and Gaussian elimination.
03.11.2023 You can read on the Cofactor/Laplace expansion and on the Adjugate matrix. You can also find this in chapter 3.5 of LADW and in this book. Additionally, you may want to check out 4.3 for a visualization of how the determinant measures volumes.

For the Hermite cubic interpolation you can see this as well as B.1 and B.2 in appendix B of Dr. Augustin's notes.

You have the definition of a linear space in Appendix A 2.1 of Dr. Augustin's notes as well as here. A more detailed treatment can be found in chapters 1.1,1.2, and 1.7, of LADW, as well as chapter 2 here.
08.11.2023 You can read about linear spaces and bases in chapter 1 of LADW and in this book. You also have a bit on vector spaces in A.2 of Dr. Augustin's notes, in 1.2,1.3 of Davis' book, and in 1.2,1.5 of Prenter's book.

For Lagrange and Newton interpolation see 2.5 and 2.6 in Davis' book, 1.2,1.3 in Villiers' book, 2.3,2.4 in Prenter's book, and the Wikipedia articles on Lagrange polynomial and Newton polynomial.

For Hermite interpolation see B.1 in Dr. Augustin's notes, 1.4 in Villiers' book, chapter 3 of Prenter's book, and Wikipedia's article. For generalized Hermite interpolation see this paper. For Birkhoff interpolation see the following papers: Sc67, LZ71.
15.11.2023 For more details on error analysis for polynomial interpolation see chapter 2 in Villiers.

In chapters 7 and 8 in Davis, 6.6,6.7 of Prenter, chapter 4 and 7.2 in Villiers, you can find more theoretical details on approximation. In 7.8 of Farin you can find a short practical description and also here.

Orthogonal polynomials are discussed in chapter 10 of Davis' book, 7.3-7.6 in Villiers, and here.

You can read about Bernstein polynomials in 6.2 of Davis' book, chapter 4 and 5.1,5.2 in Farin's book, and here.
22.12.2023 A very detailed article with examples on Bezier curves.

A video on Bezier curves and a video on B-Splines.

A book on multivariate polynomial interpolation.

A blog post and article on the multivariate Bernstein basis on triangles.
11.01.2024 Notes summarising interpolation and approximation in finite-dimensional inner product spaces.
24.01.2024 Notes on complex differentiation.
06.02.2024 Computing Bezier derivatives with de Casteljau.
22.02.2024 Notes on finite differences and consistency.


Assignments

No. Title Date Submit until
HW1 Interpolation and Approximation with Polynomials 22.11 [download] 01.12
PR1 Project on Interpolation and Approximation 13.02 [download] 29.02
PR1 Example Images from the Project 18.02 [download] 29.02


Example Solutions

Literature

There is no specific text book for this class as it touches on many topics for which specialized books exist.

  • Mathematics of Approximation
    J. de Villiers, Springer, 2012.
  • Curves and Surfaces for CAGD: A Practical Guide
    G. Farin, Morgan Kaufmann, 2002.
  • Scattered Data Approximation
    H. Wendland, Cambridge University Press, 2005.
  • Meshfree Approximation Methods with MATLAB
    G. Fasshauer, World Scientific, 2007.
  • Interpolation and Approximation
    P. Davis, Dover, 1975.
  • Splines and Variational Methods
    P. M. Prenter, Wiley, 1989.
  • Spline Functions: Basic Theory
    L. L. Schumaker, Cambridge University Press, 2007.

These and further books can be found in the
mathematics and computer science library.

Further references will be provided during the lecture.

MIA Group
©2001-2023
The author is not
responsible for
the content of
external pages.

Imprint - Data protection