# Shape Matching: A Metric Geometry Approach

### What's new?

• Added presentations and project reports.
• Added slides for Last Lecture.

### Course Info

 Instructor Facundo Mémoli, m e m o l i @ m a t h . s t a n f o r d . e d u Meetings: Mondays 2:15-4:05 PM, in 240-101 Prerequisites: I assume mathematical sophistication and familiarity with programming. However, the course is designed for a novice in the area. The grade will be based on class participation and a final project, which can be either an implementation or a survey paper. Grading: The course will not have any homework or tests. The grade will be based on class participation and a final project, which can be either an implementation or a survey paper. I will provide a list of possible projects early in the quarter. Literature: I will be providing slides/notes for the class, as well as supplementary readings, when appropriate.

### Course description and Syllabus

This seminar will touch upon the use of ideas from metric geometry for tackling the problem of Matching/Comparison of Shapes under invariances.

We will cover different ideas of Mikhail Gromov that have proved extremely useful in the context of this applied problem.

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. 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 Gromov-Hausdorff distances.

Connections with several standard approaches to the problem of shape comparison will be discussed.

Syllabus is [here]

### Resources

"Shape Matching using Gromov-Hausdorff distances." Introductory presentation.

[BBI] "A Course in Metric Geometry", by Burago-Burago-Ivanov, AMS Graduate Studies in Mathematics Volume 33

[Villani] "Topics in Optimal Transportation", by Cedric Villani, AMS Graduate Studies in Mathematics Volume 58

[M07] "On the use of Gromov-Hausdorff for Shape Matching and Comparison", by F.Memoli. PBG 2007.

[MS05] "A theoretical and computational framework for the isometry invariant recognition of point cloud data", by F.Memoli and G. Sapiro. Foundations of Computational Mathematics, 2005.

[Gromov] Metric structures for Riemannian and non-Riemmanian spaces, Birkhauser.

[M08-euclidean] "Gromov-hausdorff distance in Euclidean spaces", by F.Memoli. CVPR 2008.

[BBK06] "Efficient Computation of Isometry Invariant Distances between Surfaces", by Bronstein, Bronstein and Kimmel. SIAM 2006.

[BM] "Shape Matching and Object Recognition Using Shape Contexts", by Belongie et al, 2001.

[BM-1] "Matching Shapes", by Belongie et al, 2002.

### Assignments

• Assignment 3: this one is designed to help you get a better idea about the computational side of D_p, the invariants you read about in the previous assignment and the lower bounds in [M07]. You'll need the [pdf] with the description and the [zipfile] with some matlab code.
• Assignment 2: 1 page summary of each [osada], [Hamza-Krim] and [BK,BK-1].
• Assignment 1: 1 page summary of each [MS05] and [BBK06].