Abstract
The course is a selfcontained 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 deformationinvariant 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 nonrigid shapes, geometric invariants, approximation of geodesic distances, multidimensional scaling methods and their use for invariant representations of nonrigid shapes, spectral methods and the LaplaceBeltrami operator, intrinsic similarity of shapes and the GromovHausdorff distances, extrinsic and intrinsic selfsimilarity 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, expressioninvariant face recognition, texture mapping, morphing and animation.
Formalities
 Lecturer: Dr. Alex Bronstein
 Class is held on Thursdays, 16:00  18:00, Engineering Classes, room 003
 Grade will consist of home assignments (40%) and final exams (60%).
Information will be also published on Facebook page.
Prerequisites
 Knowledge of linear algebra and vector calculus
Lecture 1
 Introduction pptx  pdf
Dimensions of media  Applications  Landscape  Images vs Shapes  Invariance  Course in a nutshell  Highlights
 Introduction to geometry  metric geometry and topology pptx  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
Exercises
 Problem Set 1  metric geometry pdf
Solutions to some problems pdf
Lecture 2
 Introduction to geometry  manifolds and differential machinery pptx  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  Extrinsic geometry  Riemannian geometry  Nash's embedding theorem  Bending and rigidity  Intrinsic definition of Gaussian curvature  Theorema egregium  GaussBonnet formula  Intrinsic invariants
Additional materials
 A dummy's guide to differential calculus on manifolds pdf
 R. Connelly, A counterexample to the rigidity conjecture for polyhedra pdf
Exercises
 Problem Set 2  differential geometry pdf
Solutions to some problems pdf
Lecture 3
 Discrete geometry pptx  pdf
Discretization  Sampling  Farthest point sampling  Voronoi tessellation  Sufficient sampling density conditions  Optimal sampling  Centroidal Voronoi tessellation  LloydMax algorithm  Sampling as clustering  Approximate optimal sampling  HochbaumShmoys theorem  Connectivity  Delaunay tessellation  Triangular meshes  Barycentric coordinates  Manifold meshes  Geometry images  Geometric validity  Skeleton  Local feature size
Additional materials
 Shape discretization pdf
MATLAB demos
 Farthest point sampling and Voronoi tessellation
Exercises
 Problem Set 3  discrete geometry pdf
Solutions to some problems pdf
No lectures on March 25th (happy Passover!) and on April 1st (not a joke!). Next lecture is on April 8th.
Lecture 4
 Shortest path problems pptx  pdf
Shapes as graphs  Shortest paths in graphs  Bellman's principle of optimality  Dijkstra's algorithm  Metrication errors
 Fast marching methods pptx  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
 Numerical optimization pptx  pdf
Optimization problems  Local and global minimum  Convex functions  Onedimensional optimality conditions  Gradient  Gradient of a matrix function  Hessian  Optimality conditions  Optimization algorithms  Stopping criteria  Line search  Armijo rule  Steepest descent  Condition number  Qnorm  Preconditioning  Newton method  Frozen Hessian  Cholesky factorization  Truncated Newton  Nonconvex optimization  Iterative majorization  Constrained optimization  Lagrange multipliers  KKT conditions  Penalty methods
MATLAB demos
 Fast marching
Exercises
 Problem Set 4  shortest path problems pdf
No lectures on April 15th and 22nd. Next lecture is on April 29th.
Lecture 5
 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  Shapetoshape distance  Pointtopoint distance  Pointtoplane distance  Secondorder pointtoshape distance  Closest points  Approximate nearest neighbors  Convergence  Enter numerical optimization  Local quadratic approximant  Iterative closest point algorithm revisited
 Multidimensional scaling pptx  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 L2stress  LSMDS  Gradient of L2stress  Complexity  Majorizing inequality  Iterative majorization  SMACOF algorithm  Weighted stress  Variations on the stress theme  Iteratively reweighted LS  Multiresolution MDS  Correction  Modified stress  Twogrid MDS  Multigrid MDS  Vector extrapolation  Reduced rank extrapolation (RRE)  Safeguard
MATLAB demos
 ICP
 MDS
Exercises
 Problem Set 5  rigid shape similarity pdf
Solutions to some problems pdf
 Problem Set 6  multidimensional scaling pdf
Home assignment #4 for submission. Deadline: June 15th, 2010.
Lecture 6
 Spectral methods pptx  pdf
Gram matrices  Classic MDS  LaplaceBeltrami operator  Discrete LaplaceBeltrami operator  Shape DNA
 Diffusion geometry pptx  pdf
Diffusion operators  heat operator  diffusion distances  scale invariance  commute time distance
MATLAB demos
 Classic MDS
 Diffusion distances
Lecture 7
 Invariant shape similarity pptx  pdf
GromovHausdorff distance  Metric coupling  Correspondence  Assignment problems  Generalized multidimensional scaling  Discrete GromovHausdorff distance  Connection to ICP distance  Connection to canonical form distance  Lp GromovHausdorff distance  Measure coupling  GromovWasserstein distance  Earth Mover's distance
Additional materials
 Metricmeasure spaces pdf
MATLAB demos
 Generalized MDS
Lecture 8
 Partial shape similarity pptx  pdf
Greek mythology  Partial similarity  Human vision example  Visual agnosia  Recognition by parts  Significance  Multicriterion optimization  Pareto optimality  Setvalued partial similarity  Order relations  Scalarvalued partial similarity  Characteristic functions  Fuzzy sets  Partial similarity computation  Intrinsic partial similarity  Extrinsic partial similarity  Not only size matters  Boundary regularization  MumfordShah functional  Regularized partial similarity  tfidf weighting  Statistical significance density
Lecture 9
 Featurebased methods and shape retrieval problems 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
Home assignment #6 for submission. Deadline: July 15th, 2010.
Lecture 10
 Symmetry and structure pptx  pdf
Selfsimilarity and symmetry  Spectral properties  Structural regularity  Structural correspondence
 Invariant correspondence and calculus of shapes pptx  pdf
Minimumdistortion correspondence  Texture transfer  Temporal superresolution  Motioncompensated interpolation  Texture substitution  Metamorphing  Face caricaturization  Killing field  As isometric as possible morph
 Conclusion: computational metric geometry? pptx
Final exam
 Exam pdf
 Solution pdf
References
 A. M. Bronstein, M. M. Bronstein, R. Kimmel, Numerical geometry of nonrigid shapes, Springer 2008
 Annotated bibliography
