Home Authors Book Resources Course Academic TOSCA
Slides
Video
Problems
Solutions





    Abstract

    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.


    Formalities

  • Lecturer: Dr. Michael Bronstein
  • Class is held on Thu, 12:30 - 14:30, Department of Electrical Engineering (Meyer building), room 351
  • Office hours: Taub 431, Thu 15:00-16:00
  • Grade will consist of home assignments (50%) and project (50%). Students will be able to choose the topic of their project, and are encouraged to bring a topic related to their research.
    • Information will be published on Facebook page.

    Prerequisites

  • Introduction to signal processing (044198)
  • Processing and analysis of images (046200)

    • Students without formal prerequisites but with sufficient background may obtain the permission to take the course from the teacher.

    Lecture 1

  • Introduction pptx | pdf
    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: the Greek way pptx | pdf
    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

    • Lecture 2

  • Introduction to geometry: the German way pptx | pdf
    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

    • Lecture 3

  • Discrete geometry pptx | pdf
    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

    • MATLAB demos

  • Farthest point sampling and Voronoi tessellation

    • Lecture 4

  • Shortest path problems pptx | pdf | video
    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 pptx | pdf | video1, video2
    Metric discretization - Distance map on surfaces - Intrinsic gradient - Extrinsic gradient - Eikonal equation - Sub- and super-derivatives - Viscosity solution - 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

    • MATLAB demos

  • Fast marching

    • See also

  • Parallel marching SIGGRAPH trailer

    • Lecture 5

  • Numerical optimization pptx | 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

    • MATLAB demos

  • Toy example of steepest descent

    • Lecture 6

  • Rigid shape analysis pptx | 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

  • ICP demo

    • Home Assignment 1 (Due date: May 15)
    Bonus (5 points) for those who fold the Steffen-Connely non-rigid polyhedron

    Lecture 7

  • Multidimensional scaling pptx | pdf | video1, video2
    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

  • Least-squares MDS (requires Accelerated MDS code)
  • Canonical forms
  • Multigrid MDS (requires Accelerated MDS code)

    • Lecture 8

  • Spectral methods pptx | pdf | video
    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 - Discrete vs discretized - No free lunch - Finite elements method

    • MATLAB demos

  • Classic MDS

    • Lecture 9

  • Diffusion geometry pptx | pdf
    Diffusion operators - Heat operator - Diffusion distances - Scale invariance - Commute time distance

    • MATLAB demos

  • Diffusion distances

    • Lecture 10

  • Invariant shape similarity pptx | pdf
    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

    • MATLAB demos

  • Generalized MDS

    • Lecture 11

  • Symmetry and structure pptx | pdf
    Self-similarity and symmetry in nature - Euclidean vs non-Euclidean regularity - Intrinsic vs extrinsic symmetry - Approximate symmetry - Branch and bound - Completion by composition - Local refinement - Partial symmetry - Regularity - Diffusion symmetry - Spectral properties - Intrinsic structural regularity - Parametrization - Grid detection - Applications - Structural correspondence - Ambiguities

    • Lecture 12

  • Partial similarity pptx | 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

    • Home Assignment 2 (Due date: June 30)

    Lecture 13

  • Feature-based methods and shape retrieval pptx | pdf
    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 pptx | pdf
    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

    • References

  • A. M. Bronstein, M. M. Bronstein, R. Kimmel, Numerical geometry of non-rigid shapes, Springer 2008 (available for borrowing in Central and CS libraries)
  • Annotated bibliography