Formalities
- Lecturers: Alexander Bronstein, Michael Bronstein. CA: Maks Ovsjanikov
- Class is held in Gates 260 on Fridays, 10:00 - 12:50 (two lectures followed by a tutorial)
- Grade will consist of home assignments (40%) and project (60%). Students will be able to choose the topic of their project, and are encouraged to bring a topic related to their research.
- Textbook: A. M. Bronstein, M. M. Bronstein, R. Kimmel, Numerical geometry of non-rigid shapes, Springer 2008.
Lecture 1
- Introduction .ppt | .pdf
Welcome to non-rigid world - Rock, Paper and Scissors - Invariant similarity - Invariance - Invariant correspondence - Shape analysis and synthesis - Landscape - Course in a nutshell - Highlights
- Metric geometry .ppt | .pdf
Distances - Metric - Shapes as metric spaces - Similarity as metric - Examples of metric - Length spaces - Restricted and intrinsic metric - Induced metric - Completeness - Convexity - Isometries - Euclidean isometries - Geodesic isometries - Almost isometries
- Differential geometry I .ppt | .pdf
Manifolds - Charts and atlases - Smooth manifolds - Manifolds with boundary - 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
Tutorial 1
- Mathematical background .ppt | .pdf
Metric balls - Topology - Topological space - Connectedness - Compactness - Convergence - Continuity - Homeomorphisms - Lipschitz continuity - Isometries - Dilation - Groups - Self-isometries - Isometry groups - Symmetry
Home assignment 1 (due date: January 23, 2009)
- Problems 3, 6, 14, 16 from Problem set 1
Lecture 2
- Differential geometry II .ppt | .pdf
Extrinsic geometry - Riemannian geometry - Nash's embedding theorem - Bending and rigidity - Intrinsic definition of Gaussian curvature - Theorema egregium - Gauss-Bonnet formula - Intrinsic invariants
- Discrete geometry .ppt | .pdf
Discretization - Sampling - Farthest point sampling - Voronoi tessellation - Sufficient sampling density conditions - Optimal sampling - Centroidal Voronoi tessellation - Lloyd-Max algorithm - Sampling as clustering - Approximate optimal sampling - Hochbaum-Shmoys theorem
- Shortest path problems .ppt | .pdf
Shapes as graphs - Shortest paths in graphs - Bellman's principle of optimality - Dijkstra's algorithm - Metrication errors
MATLAB demos
- Farthest point sampling and Voronoi tessellation
Tutorial 2
- Discrete topology and discretization of geometric quantities .ppt | .pdf
Neighborhood - Connectivity - Delaunay tessellation - Triangular meshes - Barycentric coordinates - Manifold meshes - Geometry images - Geometric validity - Skeleton - Local feature size - Normal - Curvatures - Area - Approximation quality - Schwarz lantern
Home assignment 2 (due date: January 30, 2009)
- Problems 1, 2, 7, 11 from Problem set 2
- Show that the locations of the samples in the centroidal Voronoi tessellation is a local minimizer of the average squared cluster radius criterion.
Lecture 3
- Fast marching methods .ppt | .pdf
Distance map on surfaces - Intrinsic and extrinsic gradients - Eikonal equation - Viscosity solution - Fast marching methods - Update step - Causality condition - Monotonicity condition - Fast marching on obtuse meshes - Eikonal equation on parametric surfaces - Fast marching on parametric surfaces - Raster scan fast marching - Parallel marching - Minimal geodesic - Implicit surfaces
MATLAB demos
- Fast marching
Tutorial 3
- Consistent metric approximation in graphs .ppt | .pdf
Consistent metric approximation - Main idea - Sampling conditions - Surface properties - Sufficient conditions for consistency (Bernstein-de Silva-Langford-Tenenbaum theorem) - Why both conditions are important? - Probabilistic version
Lecture 4
- Numerical optimization .ppt | .pdf
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
- In the rigid kingdom .ppt | .pdf
Cinderela's tale - 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
MATLAB demos
- Iterative closest point
Tutorial 4
- Iterative closest point algorithms .ppt
Analytic expression for optimal rigid alignment with a given correspondence - Quaternions - Shape descriptors - Branch-and-bound - Globally-optimal rigid shape matching
Home assignment 3 (due date: February 13, 2009)
- Problem set 3
Lecture 5
- Multidimensional scaling .ppt | .pdf
Cinderella 2.0 - If it doesn't fit, you must acquit! - Metric model - Intrinsic vs extrinsic similarity - Canonical forms - Mapmaker's problem - Linial's example - Minimum distortion embedding - Multidimensional scaling - Stress - Matrix expression of L2-stress - LS-MDS - Gradient of L2-stress - Complexity - Majorizing inequality - Iterative majorization - SMACOF algorithm - Weighted stress - Variations on the stress theme - Iteratively reweighted LS - Multiresolution MDS - Correction - Modified stress - Two-grid MDS - Multigrid MDS - Vector extrapolation - Reduced rank extrapolation (RRE) - Safeguard
MATLAB demos
- SMACOF
- Canonical forms
- Multigrid MDS
Project topic presentation
Lecture 6
- Spectral methods .ppt | .pdf
Gram matrices - Classic MDS - Local methods - Laplacian matrix - Minimum eigenvalue problems - Laplacian eigenmaps - Laplace-Beltrami operator - Chladni plates - Laplace-Beltrami spectrum - Shape DNA - To hear the shape of the drum - GPS embedding - Discrete Laplace-Beltrami operator - No free lunch
- Non-Euclidean embedding .ppt | .pdf
Why non-Euclidean? - Non-Euclidean MDS - Spherical geometry - Spherical embedding - Generalized multidimensional scaling - Local representation - Geodesic distance approximation - A four-step dance - Minimization algorithm - Quadratic stress - How to move to adjacent triangles? - Point on edge - Point on vertex - MDS vs GMDS - Multiresolution
MATLAB demos
- Classic MDS
- GMDS
Tutorial 6
- Spectral methods .ppt
Connection of spectral MDS to PCA - Kernel trick for spherical MDS - Connection to kernel PCA - GPS embedding - Connection to canonical forms
Lecture 7
- Isometry-invariant similarity .ppt | .pdf
Invariant similarity - Equivalence - Similarity - Isometry-invariant distance Canonical forms distance - Gromov-Hausdorff distance - Metric coupling - Correspondence - GMDS - 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 - The analogy
- Topology-invariant similarity and diffusion geometry .ppt | .pdf
Limitations of intrinsic geometry - Joint intrinsic/extrinsic similarity - Computation of joint similarity - Shape morphing - Other intrinsic geometries - Diffusion on manifolds - Diffusion distance - Diffusion maps and canonical forms
MATLAB demos
- Diffusion maps
Tutorial 7
- Spectral correspondence and intrinsic symmetry .ppt
Spectral correspondence - GPS embedding - Self-similarity - Extrinsic vs intrinsic symmetry - Intrinsic symmetry detection - Symmetry detection using Laplace-Beltrami eigenfunctions
Lecture 8
- Partial similarity .ppt | .pdf
Greek mythology - Partial similarity - Human vision example - Visual agnosia - Recognition by parts - Significance - Multicriterion optimization - Pareto optimality - Set-valued partial similarity - Order relations - Scalar-valued partial similarity - Characteristic functions - Fuzzy sets - Partial similarity computation - Intrinsic partial similarity - Extrinsic partial similarity - Not only size matters - Boundary regularization - Mumford-Shah functional - Regularized partial similarity - tf-idf weighting - Statistical significance density
- 3D face recognition .ppt | .pdf
Biometrics in the age of Patriarchs - Biometrics in fairy tales - Biometrics in opera - First face recognition - Face recognition today - Recognition accuracy - What is a face? - The curse of expressions - Isometric model of expressions - How to canonize a person? - Telling identical twins apart - Comparing photometric properties - Spherical embedding - Partial similarity
Tutorial 8
- Feature-based similarity and correspondence .ppt
Features - Non-rigid descriptors - Bipartite graph matching - Limitations - Feature-based approaches in computer vision (video Google)
Lecture 9
- Invariant correspondence and calculus of shapes .ppt | .pdf
Natural correspondence - Correspondence between curves - Invariant parametrization - Canonical forms - Image processing insight - Intrinsic regularization - Cauchy-Green tensor - Physical insight - Harmonic maps - Minimum-distortion correspondence - Texture transfer - Calculus of shapes - Temporal super-resolution - Motion-compensated interpolation - Texture substitution - Metamorphing - Face caricaturization - Killing field - As isometric as possible morph
- Inverse problems .ppt | .pdf
Measurement - Reconstruction - Inverse problems - Ill-posedness - Prior knowledge - Regularization - Inverse problems with intrinsic prior - Solution of inverse problems with intrinsic prior - Joint similarity as inverse problem - Computation of the regularization term - Computation of dD(Z)/dZ using Dijkstra’s algorithm
- Inconsistency of Dijkstra’s algorithm - Computation of dD(Z)/dZ using Fast Marching - Shape-from-X
- Denoising - Bundle adjustment - Shape-to-image matching
Tutorial 9
- Morphing and shape processing .ppt
Intersection-free morphing - As isometric as possible morphing - Rigid motion metric - Isometric motion metric - Boundary value problem - Initial value problem
Project presentation
|