DOC PREVIEW
Stanford CS 468 - On the use of Gromov-Hausdorff Distances for Shape Comparison

This preview shows page 1-2-3-4 out of 11 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Eurographics Symposium on Point-Based Graphics (2007)M. Botsch, R. Pajarola (Editors)On the use of Gromov-Hausdorff Distances for ShapeComparisonFacundo Mémoli11Department of Mathematics, Stanford University, California, USA.AbstractIt is the purpose of this paper to propose and discuss certain modifications of the ideas concerning Gromov-Hausdorff distances in order to tackle the problems of shape matching and comparison. These reformulationsrender these distances more amenable to practical computations without sacrificing theoretical underpinnings. Asecond goal of this paper is to establish links to several other practical methods proposed in the literature forcomparing/matching shapes in precise terms. Connections with the Quadratic Assignment Problem (QAP) arealso established, and computational examples are presented.Categories and Subject Descriptors(according to ACM CCS): I.3.5 [Computer Graphics]: Computational Geometryand Object Modelling.1. IntroductionGiven the great advances in recent years in the fields of shapeacquisition and modelling, and the resulting huge collectionsof digital models that have been obtained it is of great impor-tance to be able to define and compute meaningful notionsof similarity between shapes which exhibit invariance to dif-ferent deformations and or poses of the objects representedby those shapes. It is the case that similar problems arise indifferent disciplines such as molecular biology, databases ofobjects, face recognition, matching of articulated objects andpattern recognition in general.There have been many approaches to the problem of (poseinvariant) shape matching and recognition in the literature,for example [HK03, LH05, OFCD02, RWP05, EK03, Fro90,RTG00, CG99, MS05]. In many cases the underlying idearevolved around the comparison of certain metric invariantsof the shapes so as to ascertain whether they were in fact thesame shape (up to a certain notion of invariance).The concept of Gromov-Hausdorff distances [Gro99] wasfirst proposed as a tool for formalizing shape comparisonideas in [MS05]. This distance is able to detect the metricsimilarity between the shapes as it operates on their metricSupported by DARPA grant number HR0011-05-1-0007.structure, that is, shapes are viewed as metric spaces. Thisnotion of distance compares the full metric information con-tained in the shapes, as opposed to other notions that mayonly compare simple (incomplete) invariants. Therefore twoshapes will be declared equal if and only if they are isomet-ric. This means that the invariance properties are to be en-coded by the metrics one chooses to endow the shapes with.For example, if the shapes are endowed with Euclidean met-rics, the underlying invariance is to rigid isometries.The ideas presented in this paper are not restricted to 3Dshapes as they can applied to any point clouds (sets of points)which are endowed with metric structures.This paper presents new results that extend the originaldefinition of Gromov-Hausdorff distances in a way such thatthe associated discrete problems one needs to solve in prac-tical applications are of an easier nature than yielded by pre-vious related approaches, [MS05,BBK06]. The practical ap-proach put forward in [MS05] was inherently combinatorialand hard to optimize. Another feature of this approach is thatthe approximation bounds between the discrete and contin-uous entities were probabilistic, and the proof of these re-quired the assumption that the shapes were actually smoothembedded manifolds.In [BBK06], the authors, also under the assumption thatthe underlying shapes are smooth surfaces, proposed a con-c! The Eurographics Association 2007.F. Mémoli / Gromov-Hausdorff Distancestinuous optimization setting which seemed to alleviate someof the impracticalities of the original proposal. They how-ever had to resort to local interpolation of the metrics in or-der to make their computations possible (this is where thesmoothness assumption is used). The underlying ideas werestill of a somewhat combinatorial nature in the sense thattheir matchings were maps between the shapes. In this pa-per we completely remove this feature from the frameworkand consider a different way of pairing two shapes whichdirectly leads to standard optimization problems where noadditional assumptions are needed, i.e. no assumption aboutthe smoothness of the underlying shape. We show that ourapproach leads to Quadratic Optimization Problems (QOPs)with linear constraints. In addition, this new set of ideas al-lows connecting the Gromov-Hausdorff framework to pre-existing approaches which have proven useful in the ShapeComparison/Matching arena. Examples of these methods arethose proposed by [OFCD02,HK03,EK03,CG99,KV05]. Inmore detail, our modified notion of Gromov-Hausdorff dis-tance will admit these notions of similarity as lower and/orupper bounds.Throughout our presentation we use some simple con-cepts from measure theory and point set topology which canbe consulted for example in [Dud02].The paper is organized as follows: Section §2 introducesthe problem of Shape Comparison in a general setting andpresents basic elements such as notions of shape similarityupon which the rest of the paper is based. Section §3 brieflydiscusses the idea of introducing invariances into our no-tions of similarity. Section §4 reviews the notion of Gromov-Hausdorff distance and its main properties. In that sectionwe also discuss connections with the Quadratic AssignmentProblem. Section §5 delves into the core of the paper where anew notion of proximity between metric spaces is introducedand its connections with the Gromov-Hausdorff distance andother notions are established. Some basic lower and upperbounds are presented there. Section §6 presents other moreinteresting lower and upper bounds for the proposed notionof similarity. The aim is twofold, on one hand doing thismakes apparent the connection to other approaches foundin the literature, and on the other it provides lower boundswhich are easily computable and consequently of practicalvalue. Section §7 discusses the computational aspect of ourideas, establishing that the problems one needs to solve inpractice are either Linear or Quadratic Optimization Prob-lems (with linear constraints). We present computational ex-amples in Section §8 and conclusions in Section §9. Due tospace limitations, long technical proofs are not given in thispaper and will be presented elsewhere.2. Comparing objectsAn object in


View Full Document

Stanford CS 468 - On the use of Gromov-Hausdorff Distances for Shape Comparison

Download On the use of Gromov-Hausdorff Distances for Shape Comparison
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view On the use of Gromov-Hausdorff Distances for Shape Comparison and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view On the use of Gromov-Hausdorff Distances for Shape Comparison 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?