Shape Comparison and Gromov-Hausdorff Distances

What's new?

Description

In this webpage I will be posting material related to my work on Shape Matching. At some point I plan to put together a webpage with information about different approaches to shape matching and shape analysis. My own work draws heavily from ideas due to Mikhael Gromov, and especially from Chapter 3½ of his green book. This probably sounds pretentious, so let me say that the subset of Gromov's ideas that I understand is very small, but those that I do, have been very useful.

Coming soon:

I got interested in this problem during my PhD time. I proposed using the Gromov-Hausdorff distance for formalizing the problem of shape matching under invariances. The first publication with these ideas is [MS04]. A more detailed presentation appeared later in [MS05] and [MS06].

In a nutshell, the main idea I proposed was to regard shapes as metric spaces, where the metric is chosen to reflect the degree of invariance one wishes to have. For example, if you care about invariance to rigid transformations, then the proposal is to look into the comparison of the Euclidean distance matrices of the two shapes. If you care about invariance to bends, then you should look at geodesic distance matrices, etc. Statements of stability come for free once you adopt this metric point of view.

I recently taught a CS-468 course on these topics at Stanford. You can find much material from the lectures, and links to papers in theat webpage.

Prof. Kimmel's group at the Technion got interested in the approach and have explored many applications of the original idea. They have even written a book that incorporates many of the ideas originally proposed in [MS04] and presents a large number of applications. They are teaching a CS course at Stanford in the Spring 2009. I strongly recommend you have a look at their book; if you are a Stanford affiliate, you can access the book online.

In [M08-euclidean] I study the connection between the the Gromov-Hausdorff distance and the Hausdorff distance in Euclidean spaces, modulo rigid isometries. This was an important building block of the framework that I wanted to do for some time. An extended version of this paper is coming soon.

Computation of Gromov-Hausdorff distances

Solving for the GH distance between two finite metric spaces leads to combinatorial optimization problems that are similar to the Bottleneck Quadratic Assignment problem and are NP-Hard.

The implementation in [MS04] and [MS05] was based on a heuristic and dealt directly with the combinatorial problem.

The implementation in [BBK06] revolves around a relaxation of the GH distance formulation that works for triangulated approximations of surfaces endowed with the (graph) geodesic distance. They give their procedure the somewhat pompous name GMDS (for generalized multidimensional scaling).

I think that after all the GH distance may not be the most adequate tool for tackling direct computational shape-matching problems. By this I mean that, it is probably not what you should try to compute directly in practice. The problem is that it leads to computationally hard combinatorial optimization problems. This, however, doesn't mean at all that it is not useful. The impression I have is that it is probably better to approach the computation of lower/upper bounds for the GH distance than its direct computation.

Furthermore, one of my goals when I started looking at this problem was to be able to inter-relate many pre-exisiting approaches to shape matching. I was unable to do so in a convicing way with the GH distance.

Gromov-Wasserstein distances

Naive relaxations of the GH distance lead to computing quantities that are no longer related to the GH distance-- in particular, they do not retain the desirable theoretical properties that the GH distance satisfies.

During my PhD thesis time I realized that maybe an L^p notion of GH distance would be better suited for practical applications. However, a naive definition of this L^p version clearly would not solve anything, and in any case, would probably not enjoy desirable properties. The correct change of perspective was carried out in [M07]. The new family of distances are better referred to as Gromov-Wasserstein distances and are closely related to the distance constructed by Prof. K. T. Sturm. Tied with this choice of a new distance is the fact that now shapes are represented as metric measure spaces, these are metric spaces which are also endowed with a notion of weight attached to each point.

An informal description of the construction of these distances is that the underlying Hausdorff engine in the Gromov-Hausdorff distance is substituted by a Mass Transportation distance, a.k.a. Wasserstein distance. Mass transportation distances are well known in the object recognition community under the name of Earth Mover's distance.

These distances lead to quadratic optimization problems with linear constraints and continuous variables. In addition, practical approaches such as Shape Distributions, the Hamza-Krim idea, or the Shape Contexts or Integral Invariants, and the Earth Mover's distance under invariances can all be related ot this new family of distances. In [CCGMO09] together with Fred Chazal, David Cohen-Steiner, Leo Guibas and Steve oudot we have obtained that certain signatures arising from persistence homology constructions are GW stable.

In [M09-sGW], a construction of a spectral notion of GW distance is exhibited. The goal was to identify a notion of distance between Riemannian manifolds under which things like the spectrum (proposed by Reuter et al. [ShapeDNA]) or other invariants arising from the heat kernel such as the diffusion distance or the HKS (heat kernel signature) of Sun et al. [HKS-09], are stable. Other lower bonds for this notion of distance are related to the proposal of Rustamov and the proposal of Bronstein et al.

The paper [M10-sGW] is a significantly extended version of [M09-sGW] where I provide all details about the construction of the spectral GW distance and look into connections with other spectral metrics on the category of Riemannian manifolds.

The paper [M09-Lp] is an extended version of [M07] where I explain the construction of the L^p distances in detail and elaborate on the connections to pre-exisiting approaches.

A long time ago I was chatting with Niloy Mitra who explained to me the importance of being able to perform partial shape matching. A paper on the use of L^p GH distances for partial shape matching is coming soon.

Publications