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.

Projects

Shape Distributions+Boutin-Kemper (Daniel Chen)
[Report] + [Presentation]

[osada] "Shape Distributions." Osada et al., 2002

[BK] "Which point configurations are determined by their distribution of pairwise distances ", M. Boutin and G. Kemper, 2006.

[BK-1] "On reconstructing n-point configurations based on distrbutions of distances or areas ", M. Boutin and G. Kemper, 2003.

[BK-graphs] "Lossless representations of graphs using distrbutions", M. Boutin and G. Kemper, 2008.
Size Theory, Frosini et al. (Yi Ding)
[Report] + [Presentation]

[Frosini] "Using Matching distance in Size Theory, a survey", by d'Amico, Frosni and Landi, 2006.

[Frosini-multidim] "Stability in Multidimensional size theory", by Frosini et al., 2006.

Frosini's webpage. See the articles in wikipedia, start here.
An application of Shape Matching techniques (Yulin Jin)
Systematically Accelerating the Fracture Simulation Workflow using Shape Matching Techniques [Presentation]

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].

Class Schedule and notes

Monday 12-01. Project presentations (tentative date).
Monday 11-24. no class.
Monday 11-17. Course wrap-up: we review the main points in the course and discuss future directions.
Last Lecture slides
Monday 11-10. Gromov-Hausdorff distances in Euclidean spaces. We cover the main results in [M08-euclidean]. See also slides in .
Monday 11-03. L^p Gromov-Hausdorff distances, lower-bounds using shape distributions, shape contexts and the eccentricity function. We will cover last sections of [M07]
Monday 10-27. L^p Gromov-Hausdorff distances, construction and properties.
Lecture 5 slides
Monday 10-20. Gromov-Hausdorff distance: Implementation, critique. L^p GH distances.

Lecture 4 slides

Monday 10-13.

Lecture 3 notes and auxiliary slides

Reading assignment:

Finish reading [Elad-Kimmel].
All the theory parts of [MS05].

Monday 10-06. Introducing invariances, some proofs and the Gromov-Hausdorff distance.
Lecture 2 notes

Reading assignment:
- Up to Chapter 4 of [M07] "On the use of Gromov-Hausdorff for Shape Matching and Comparison", by F.Memoli. PBG 2007.
- Overview of some classical methods for shape matching: Veltkamp and Haagedoorn .
Monday 09-29. Orientation and Introduction + Background.
Lecture 1 slides

Suggested reading:
- Background: (you should eventually become familiar with the terminology below)
  - Definition of metric space. Hausdorff distance. Isometries and epsilon-isometries. Epsilon nets (coverings)
  - Probability measures, measure couplings and Earth Mover's distance (a.k.a. Wasserstein-Kantorovich-Rubinshtein distance)
  - Length metric spaces, geodesics-shortests paths
  - Multidimensional Scaling (MDS). ISOMAP
- Some papers you should start reading:
  - Overview of some classical methods for shape matching: Veltkamp and Haagedoorn .
  - Hilaga-et-al, Topology Matching for Fully Automatic Similarity Estimation of 3D..
  - Hamza-Krim, Geodesic Object Representation and Recognition.
  - Elad-Kimmel, On Bending Invariant Signatures for Surfaces.
  - Shape distributions, Shape Distributions.
  - Shape contexts, Shape Matching and Object Recognition Using Shape Contexts, and, Matching Shapes.
  - Size Theory, by Frosini et al. See the articles in wikipedia, start here.
  - Rubner et al., The Earth Mover's distance as... Also, Cohen's thesis on EMD has a lot of information.
  - Peyre et al. , Geodesic Eccentricity and Ruggeri-Saupe geodesic shape contexts. And an application to brain imaging.
  - Reuter et al. Shape DNA using Laplace-Beltrami eigenvalues .
Monday 09-22. no meeting .

Last modified: Tuesday 17th December 2008 02:13:21 PM PDT