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 nonrigid shapes, Springer 2008.
Lecture 1
 Introduction .ppt  .pdf
Welcome to nonrigid 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  Selfisometries  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  GaussBonnet formula  Intrinsic invariants
 Discrete geometry .ppt  .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
 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 (Bernsteinde SilvaLangfordTenenbaum theorem)  Why both conditions are important?  Probabilistic version
Lecture 4
 Numerical optimization .ppt  .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
 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  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
 Iterative closest point
Tutorial 4
 Iterative closest point algorithms .ppt
Analytic expression for optimal rigid alignment with a given correspondence  Quaternions  Shape descriptors  Branchandbound  Globallyoptimal 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 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
 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  LaplaceBeltrami operator  Chladni plates  LaplaceBeltrami spectrum  Shape DNA  To hear the shape of the drum  GPS embedding  Discrete LaplaceBeltrami operator  No free lunch
 NonEuclidean embedding .ppt  .pdf
Why nonEuclidean?  NonEuclidean MDS  Spherical geometry  Spherical embedding  Generalized multidimensional scaling  Local representation  Geodesic distance approximation  A fourstep 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
 Isometryinvariant similarity .ppt  .pdf
Invariant similarity  Equivalence  Similarity  Isometryinvariant distance Canonical forms distance  GromovHausdorff distance  Metric coupling  Correspondence  GMDS  Discrete GromovHausdorff distance  Connection to ICP distance  Connection to canonical form distance  Lp GromovHausdorff distance  Measure coupling  GromovWasserstein distance  Earth Mover's distance  The analogy
 Topologyinvariant 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  Selfsimilarity  Extrinsic vs intrinsic symmetry  Intrinsic symmetry detection  Symmetry detection using LaplaceBeltrami eigenfunctions
Lecture 8
 Partial similarity .ppt  .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
 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
 Featurebased similarity and correspondence .ppt
Features  Nonrigid descriptors  Bipartite graph matching  Limitations  Featurebased 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  CauchyGreen tensor  Physical insight  Harmonic maps  Minimumdistortion correspondence  Texture transfer  Calculus of shapes  Temporal superresolution  Motioncompensated interpolation  Texture substitution  Metamorphing  Face caricaturization  Killing field  As isometric as possible morph
 Inverse problems .ppt  .pdf
Measurement  Reconstruction  Inverse problems  Illposedness  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  ShapefromX
 Denoising  Bundle adjustment  Shapetoimage matching
Tutorial 9
 Morphing and shape processing .ppt
Intersectionfree morphing  As isometric as possible morphing  Rigid motion metric  Isometric motion metric  Boundary value problem  Initial value problem
Project presentation
