Numerical Algorithms for Visual Computing

You can also find an alternative webpage for the course here: https://www.mia.uni-saarland.de/Teaching/navc24.shtml

Examiner: Prof. Dr. Joachim Weickert
Lecturer: Vassillen Chizhov

Lectures (2h) + Tutorials (2h);
(6 ETCS points)

Lectures and Tutorials in person

• Monday, 12:15-14:00 (E1.3 HS001)
• Thursday, 14:15-16:00 (E1.3 HS001)

First session: Thursday, April 18, 2024
Organisational information would be communicated through the course forum.

 

Description

Motivation: Numerical algorithms are ubiquitous in visual computing disciplines such as image processing, computer vision, computer graphics, geometric modeling, machine learning, etc. As such, the analysis of a particular approach is often tied to an understanding of the numerical algorithms involved. Moreover, the mathematical ideas and notation required to understand and evaluate scientific publications in those fields require a certain level of familiarity with various topics from applied mathematics, that the course aims to provide.

Teaching Goals: The course is designed as a supplement for image processing and computer graphics lectures, to be attended before, after, or parallel to them. By the end of the course, participants should be familiar with a range of numerical methods and the mathematics on which those are based. They should also have a working understanding of how to model problems from the above fields mathematically, and what numerical algorithms, and under what assumptions, may be employed to solve those problems.

Contents: The course covers standard topics from scientific computing such as: working with floating point numbers and sources of error; signal, image, curve, and surface representations in a computer; numerical algorithms for linear systems of equations; linear least squares; iterative methods for nonlinear equations; basics from mathematical optimisation; numerical integration and differentiation; discretisations of ordinary and partial differential equations; the discrete Fourier transform; stochastic approaches. As the course aims to be useful to students from Visual Computing the teaching approach is biased towards applications in disciplines like image processing and computer graphics. For instance solvers for nonlinear systems of equations are studied from the point of view of intersecting and visualising complex surfaces, as well as solving nonlinear curve, image, and surface evolution equations such as the length/area shortening flow, and e.g. using it for curve/mesh denoising. On the other hand, probabilistic methods are studied in the context of Monte Carlo integration for ray-tracing, also for deriving denoising methods based on specific priors, and for the solution of stochastic differential equations. A more structured list of potential topics as well as example applications is given below.

Additional details

• Applications
  • path tracing
  • wave equation
  • ray-marching (intersections)
  • continuous-scale morphology
  • harmonic inpainting
  • heat diffusion
  • edge detection
• Linear Equations
  • coordinate systems, change of coordinates
  • linear and affine transformations: rotation, non-uniform scale, translation
  • intersections: plane, triangle, disk
  • linear systems of equations and linear least squares (projections)
  • iterative and direct linear system solvers
  • optimisation problems resulting in linear systems
• Nonlinear Equations
  • root-finding: bisection, fixed-point, Newton, secant
  • quadrics intersections, ray-marching (potentially fractals)
  • optimisation: gradient descent, Newton, quasi-Newton
  • nonlinear least squares and constrained optimisation
• Discrete Calculus
  • refresher of integration and differentiation
  • differential forms and generalised Stokes
  • numerical integration and differentiation
  • discrete differential calculus
• Integral and Differential Equations
  • differential equations: diffusion, wave, transport
  • integral equations: the rendering equation
  • surface flows, discrete differential geometry
  • integro-differential equations: volumetric scattering
  • finite differences, finite volumes, finite elements
  • Monte Carlo integration, importance sampling

 

Format

The lectures and tutorials will be held in person on

• Monday, 12:15-14:00 (E1.3 HS001)
• Thursday, 14:15-16:00 (E1.3 HS001).

There will be no mandatory homeworks, but various problems will be provided for additional practice.

 

Entrance requirements

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 math courses (such as Mathematik für Informatiker I-III). Nevertheless, the course will provide a refresher of the necessary concepts from linear algebra and calculus. Additionally students should have some basic programming skills C/Python (e.g. being able to work with arrays and program flow control). All material will be in English. Knowledge from image processing and rendering may be helpful, but is not required.

 

Assessments / Exams

There will be two written exams (you can check for collisions with other exams at the bottom of the following page):

• 29.07.2024, 14:00-17:00, E1.3 HS002
• 10.10.2024, 14:00-17:00, E1.3 HS002

You are allowed to bring a handwritten A4 "cheat sheet" (both sides can be written on) to the exam.

You can participate in both exams, and the better grades counts. Please remember that you have to register online for the exam in the LSF system of Saarland University.

If you cannot attend the exam, contact Vassillen Chizhov as early as possible. In case you cannot take part for medical reasons we need written proof (e.g. a certificate from a physician/Krankenschein) for the exact date of the exam.

 

References

The course will follow the most closely the book "Scientific Computing: An Introductory Survey" by Heath. While the latter has a large breadth it has insufficient depth in some topics, and as such parts of the course are also derived from some of the following materials.

• Numerical Algorithms for Visual Computing 2021 Notes
  M. Augustin, 2021.
• Scientific Computing: An Introductory Survey (Revised Second Edition)
  M. Heath, SIAM, 2018.
• Numerical Methods in Engineering with Python 3
  J. Kiusalaas, Cambridge University Press, 2013.
• Numerical Methods: An Inquiry-Based Approach with Python
  E. Sullivan, 2021.
• Matrix Computations (4th Edition)
  G. Golub, C. Van Loan, John Hopkins University Press, 2013.
• Numerical Linear Algebra: A Concise Introduction with MATLAB and Julia
  F. Bornemann, Springer, 2018.
• Iterative Methods for Sparse Linear Systems (Second Edition)
  Y. Saad, SIAM, 2003.
• Essential Partial Differential Equations
  D. Griffiths, J. Dold, D. Silvester, Springer Cham, 2015.
• A gentle introduction to the Finite Element Method
  F. Sayas, 2015.
• Finite Difference Methods for Ordinary and Partial Differential Equations
  R. J. LeVeque, SIAM, 2007.
• Numerical Solution of Partial Differential Equations in Science and Engineering
  L. Lapidus, G. F. Pinder, Wiley, 1999.
• Numerical Solution of Partial Differential Equations
  K. W. Morton, D. Mayers, Cambridge University Press, 2005.
• Robust Monte Carlo Methods for Light Transport Simulation
  E. Veach, Stanford University, 1997.
• Ray Tracing in One Weekend
  P. Shirley, 2018.

Most of these and further books can be found in the mathematics and computer science library.