Home Authors Book Resources Course Academic TOSCA Slides Video Problems Solutions

 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