Home

Course Information

Topics

The course is a self-contained comprehensive introduction to modern analysis, processing, and synthesis of geometric shapes, with a good balance between theory, numerical methods, and applications. The course will address problems such as deformation-invariant similarity and correspondence of shapes, similarity and correspondence of shapes with different topology, partial similarity and correspondence. A wide variety of topics will be covered, including: metric geometry as a model of rigid and non-rigid shapes, geometric invariants, approximation of geodesic distances, multidimensional scaling methods and their use for invariant representations of non-rigid shapes, spectral methods and the Laplace-Beltrami operator, intrinsic similarity of shapes and the Gromov-Hausdorff distances, extrinsic and intrinsic self-similarity and symmetry, shape spaces and calculus of shapes. One of the main emphases of the course will be on practical methods. Examples of applications from computer vision and pattern recognition, computer graphics, and geometry processing will be shown, including: 2D and 3D shape recognition, expression-invariant face recognition, texture mapping, morphing and animation.

Lectures are available to organize some form of exam to obtain advanced credits (especially for PhD students).

Syllabus

Mon 14:30-17:00

Introduction

Dimensions of media - Evolution of technology - Human-machine interfaces - Medical imaging - Graphics and animation - Landscape - Shapes vs images - Non-rigid world from macro to nano - Rock, paper, scissors - Similarity and correspondence - Transformations - Topics - Tools - Formalities

Introduction to geometry I: the Greek way

Distances - Metric - Metric balls - Topology - Connectedness - Compactenss - Convergence - Length spaces - Restricted and intrinsic metric - Induced metric - Completeness - Convexity - Continuity - Homeomorphisms - Lipschitz continuity - Isometries - Groups - Self-isometry - Isometry groups - Symmetry - Almost isometries - Shapes as metric spaces - Similarity as metric

Introduction to geometry II: the German way

Manifolds - Embedded surfaces - Tangent plane - Normal - Orientability - First fundamental form - Intrinsic geometry - Area - Curvature - Principal curvatures - Directional derivative - Shape operator - Second fundamental form - Mean and Gaussian curvatures - Extrinsic geometry - Riemannian geometry - Nash's embedding theorem - Theorema egregium - Gauss-Bonnet formula - Intrinsic invariants

Tue 9:30-12:00

Discrete geometry

Discrete shape representation- Sampling - Sampling density - Sampling efficiency - Farthest point sampling - Sampling as representation - Voronoi tessellation - Optimal sampling - Centroidal Voronoi tessellation - Lloyd-Max algorithm - Sampling as clusring - Hochbaum-Shmoys theorem - Connectivity - Discrete topology - Delaunay tessellation - Triangular meshes - Barycentric coordinates - Manifold meshes - Geometry images - Skeleton

Shortest path problems

Shapes as graphs - Shortest paths in graphs - Bellman's principle of optimality - Dijkstra's algorithm - Metrication errors - Consistent metric approximation (Bernstein-de Silva-Langford-Tenenbaum theorem)

Fast marching methods I: eikonal equation

Metric discretization - Distance map on surfaces - Intrinsic gradient - Extrinsic gradient - Eikonal equation - Sub- and super-derivatives - Viscosity solution

Tue 14:00-17:30

Fast marching methods II: numerical schemes

Fast marching methods - Fast marching update step - Causality conditions - Monotonicity condition - Eikonal equation on parametric surfaces - Unfolding - Raster-scan fast marching - Parallel marching - Minimal geodesic - Distances on implicit surfaces - Narrow band fast marching

Numerical optimization: a dummy’s guide

Optimization problems - Local and global minimum - Convex functions - One-dimensional optimality conditions - Gradient - Gradient of a matrix function - Hessian - Optimality conditions - Optimization algorithms - Stopping criteria - Line search - Armijo rule - Steepest descent - Condition number - Q-norm - Preconditioning - Newton method - Frozen Hessian - Cholesky factorization - Truncated Newton - Non-convex optimization - Iterative majorization - Constrained optimization - Lagrange multipliers - KKT conditions - Penalty methods

Rigid shape similarity

Extrinsic shape similarity - Principal components - Geometric moments - Signal decomposition intuition - Moments distance - Other moments - Iterative closest point algorithms - Shape-to-shape distance - Point-to-point distance - Point-to-plane distance - Second-order point-to-shape distance - Closest points - Approximate nearest neighbors - Convergence - Enter numerical optimization - Local quadratic approximant - Iterative closest point algorithm revisited

Wed 9:30-12:30

Multidimensional scaling

Intrinsic vs extrinsic similarity - Canonical forms - Mapmaker's problem - Minimum distortion embedding - Multidimensional scaling - SMACOF algorithm - Multigrid MDS - Vector extrapolation - Expression-invariant face recognition

Spectral methods

Gram matrices - Classic MDS - Laplace-Beltrami operator - Discrete Laplace-Beltrami operator - Shape DNA

Wed 14:00-17:00

Diffusion geometry

Diffusion operators - heat operator - diffusion distances - scale invariance - commute time distance

Invariant shape similarity

Gromov-Hausdorff distance - Metric coupling - Correspondence - Assignment problems - Generalized multidimensional scaling - Discrete Gromov-Hausdorff distance - Connection to ICP distance - Connection to canonical form distance - Lp Gromov-Hausdorff distance - Measure coupling - Gromov-Wasserstein distance - Earth Mover's distance

Thu 9:30-12:30

Partial similarity

Partial similarity - Recognition by parts - Significance - Statistical significance - Intrinsic partial similarity - Extrinsic partial similarity - Regularized partial similarity

Symmetry and structure

Self-similarity and symmetry - Spectral properties - Structural regularity - Structural correspondence

Thu 14:00-17:00

Feature based methods and Shape retrieval

Local and global structure - feature descriptors - heat kernel signature - scale invariance - shape retrieval - ShapeGoogle - bags of words - expressions - global point signature - distance distributions

Invariant correspondence and Calculus of shapes

Correspondence between curves - Invariant parametrization - Canonical forms - Cauchy-Green tensor - Harmonic maps - Minimum-distortion correspondence - Texture transfer - Temporal super-resolution - Motion-compensated interpolation - Texture substitution - Metamorphing - Face caricaturization - Killing field - As isometric as possible morph - Intersection-free morphing

Conclusions

Friday

Open discussion