Möbius voting for surface correspondence

Yaron Lipman, Thomas Funkhouser

Research output: Contribution to journalConference article

262 Scopus citations

Abstract

The goal of our work is to develop an efficient, automatic algorithm for discovering point correspondences between surfaces that are approximately and/or partially isometric. Our approach is based on three observations. First, isometries are a subset of the Möbius group, which has low-dimensionality - six degrees of freedom for topological spheres, and three for topological discs. Second, computing the Möbius transformation that interpolates any three points can be computed in closed-form after a mid-edge flattening to the complex plane. Third, deviations from isometry can be modeled by a transportation-type distance between corresponding points in that plane. Motivated by these observations, we have developed a Möbius Voting algorithm that iteratively: 1) samples a triplet of three random points from each of two point sets, 2) uses the Möbius transformations defined by those triplets to map both point sets into a canonical coordinate frame on the complex plane, and 3) produces "votes" for predicted correspondences between the mutually closest points with magnitude representing their estimated deviation from isometry. The result of this process is a fuzzy correspondence matrix, which is converted to a permutation matrix with simple matrix operations and output as a discrete set of point correspondences with confidence values. The main advantage of this algorithm is that it can find intrinsic point correspondences in cases of extreme deformation. During experiments with a variety of data sets, we find that it is able to find dozens of point correspondences between different object types in different poses fully automatically.

Original languageEnglish (US)
Article number72
JournalACM Transactions on Graphics
Volume28
Issue number3
DOIs
StatePublished - Jul 27 2009
EventACM SIGGRAPH 2009, SIGGRAPH '09 - New Orleans, LA, United States
Duration: Aug 3 2009Aug 7 2009

All Science Journal Classification (ASJC) codes

  • Computer Graphics and Computer-Aided Design

Fingerprint Dive into the research topics of 'Möbius voting for surface correspondence'. Together they form a unique fingerprint.

  • Cite this