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. 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 - Gauss-Bonnet 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 - Lloyd-Max algorithm - Sampling as clustering - Approximate optimal sampling - Hochbaum-Shmoys 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 - 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
- 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 - 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
- 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 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
- 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 - Laplace-Beltrami operator - Discrete Laplace-Beltrami 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
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
Additional materials
- Metric-measure 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 - 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
Lecture 9
- Feature-based 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
Self-similarity and symmetry - Spectral properties - Structural regularity - Structural correspondence
- Invariant correspondence and calculus of shapes pptx | pdf
Minimum-distortion correspondence - Texture transfer - Temporal super-resolution - Motion-compensated 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 non-rigid shapes, Springer 2008
- Annotated bibliography
|