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. 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:0016: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  Humanmachine interfaces  Medical imaging  Graphics and animation  Landscape  Shapes vs images  Nonrigid 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  Selfisometry  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  GaussBonnet 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 
LloydMax algorithm  Sampling as clusring  HochbaumShmoys 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 (Bernsteinde SilvaLangfordTenenbaum theorem)
 Fast marching methods pptx  pdf  video1, video2
Metric discretization  Distance map on surfaces  Intrinsic gradient  Extrinsic gradient  Eikonal equation  Sub and superderivatives  Viscosity solution  Fast marching methods  Fast marching update step  Causality conditions  Monotonicity condition  Eikonal equation on parametric surfaces  Unfolding  Rasterscan 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  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
 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  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
MATLAB demos
 ICP demo
Home Assignment 1 (Due date: May 15)
Bonus (5 points) for those who fold the SteffenConnely nonrigid 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 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
 Leastsquares 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  LaplaceBeltrami operator  Chladni plates  LaplaceBeltrami spectrum  Shape DNA  To hear the shape of the drum  GPS embedding  Discrete LaplaceBeltrami 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
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
MATLAB demos
 Generalized MDS
Lecture 11
 Symmetry and structure pptx  pdf
Selfsimilarity and symmetry in nature  Euclidean vs nonEuclidean 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  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
Home Assignment 2 (Due date: June 30)
Lecture 13
 Featurebased 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  CauchyGreen tensor  Harmonic maps  Minimumdistortion correspondence  Texture transfer  Temporal superresolution  Motioncompensated interpolation  Texture substitution  Metamorphing  Face caricaturization  Killing field  As isometric as possible morph  Intersectionfree morphing
References
 A. M. Bronstein, M. M. Bronstein, R. Kimmel, Numerical geometry of nonrigid shapes, Springer 2008 (available for borrowing in Central and CS libraries)
 Annotated bibliography
