Shape Matching and Metric Geometry

Course Info

Instructor Facundo Mémoli, m e m o l i @ m a t h . o s u . e d u
Course code CSE 5339 -- Spring 2014
Times: Mondays 3-4:50 PM.
Location: BE 184. Map
Description: This course will touch upon the use of ideas from metric geometry for tackling the problem of Matching/Comparison of Shapes under invariances.

The central idea is to consider shapes as metric spaces (or measure metric spaces) and, then, use one of various notions of distance between metric spaces to obtain a measure of dissimilarity between shapes. Connections with several standard approaches to the problem of shape comparison will be discussed.

The choice of the metric with which one augments the shapes encodes the degree of invariance one obtains from the dissimilarity measure. The main example in this family of notions of dissimilarity between shapes is the Gromov-Hausdorff distance.

We will start by reviewing the main approaches in the literature. Then we will discuss the requisite theoretical background from Metric Geometry and cover details about the numerical computation of lower bounds to the Gromov-Hausdorff distances.

Several possible research directions will be discussed.
Prerequisites: The course has minimal requisites: it is designed for students from Computer Science and Engineering, and Mathematics having knowledge of undergrad level math. Some knowledge of geometry will be useful, but not necessary. The course will provide the opportunity to explore different aspects of the material: interested students will have the opportunity of implementing some algorithms and/or exploring some research papers on different aspects of both the underlying mathematics and/or the algorithmic procedures.

Lectures and resources

Lecture 1 (Jan. 13th): [pdf slides]. [movie]. Kacyra's TED talk is here.
Lecture 2 (Jan. 27th):Reading assignment: Veltkamp and Hagedoorn. Metric geometry background -- overview-slides-1
Lecture 3 (Feb.3rd): Compact spaces, epsilon-nets, Hausdorff distance. Blacshke's theorem.
Lecture 4 (Feb.10th):Mazur-Ulam theorem. Hausdorff distance under isometries. Approximate isometries in Euclidean spaces. Hausdorff distance under Euclidean isometries -- implementation. Some references for the latter are: [1], and [2].
Lecture 5 (Feb.17th):[pdf slides]. [movie]. Reading assignment: [1], [2], [3], [4], [5]. Soft shapes: the geometry of probability measures.
Lecture 6 (Feb.24th): Reading assignment: EMD-soft, EMD-image-classification.
Lecture 7 (March 3rd): Reading assignment: "Invariant histograms" by Brinkmann and Olver. Write a 1 to 2 page summary of the paper, due on March 3rd during class.
Lecture 8 (March 17th): Reading assignment: Elad and Kimmel. Write a 2 page summary of the paper, due on March 17th during class. Make sure you understand MDS. We will start discussing the Gromov-Hausdorff distance.
Lecture 9 (March 24th): Will continue with the discussion of the Gromov-Hausdorff distance. References: Gromov-Hausdorff distances in Euclidean spaces and On the use of Gromov-Hausdorff distances for Shape Matching.
Lecture 10 (March 31th): Will continue with the discussion of the Gromov-Hausdorff distance and start talking about the Gromov-Wasserstein distance. References: Gromov-Hausdorff distances in Euclidean spaces and On the use of Gromov-Hausdorff distances for Shape Matching.
Lecture 11 (April 7th): Will continue with the discussion about the Gromov-Wasserstein distance. Reference: On the use of Gromov-Hausdorff distances for Shape Matching.
Lecture 12 (April 14th): Wrap up. Properties of space of all mm-spaces under GW distance. Persistent Homology and GH stability. Reference: Gromov–Wasserstein Distances and the Metric Approach to Object Matching.
Lecture 13 (April 21st): Talk (1) Various shape matching methods. Talk (2) A survey of Persistent Homology in 2014.
Lecture 14 (April 22nd): Talk (3) Harmonic soft maps and the relation to the Laplace Beltrami operator. Talk (4) Spectral smilarity of shapes.
Lecture 15 (April 25th): Talk (5) Wasserstein geometry of Gaussian measures. Talk (6) Averaging phylogeneric trees.