Minimum-Distortion Isometric Shape Correspondence Using EM Algorithm


Creative Commons License

SAHİLLİOĞLU Y., Yemez Y.

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, vol.34, no.11, pp.2203-2215, 2012 (Peer-Reviewed Journal) identifier identifier identifier

  • Publication Type: Article / Article
  • Volume: 34 Issue: 11
  • Publication Date: 2012
  • Doi Number: 10.1109/tpami.2012.26
  • Journal Name: IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE
  • Journal Indexes: Science Citation Index Expanded, Scopus
  • Page Numbers: pp.2203-2215
  • Keywords: 3D isometric shape correspondence, multidimensional scaling, spectral embedding, isometric distortion, greedy optimization, bipartite perfect matching, EM algorithm

Abstract

We present a purely isometric method that establishes 3D correspondence between two (nearly) isometric shapes. Our method evenly samples high-curvature vertices from the given mesh representations, and then seeks an injective mapping from one vertex set to the other that minimizes the isometric distortion. We formulate the problem of shape correspondence as combinatorial optimization over the domain of all possible mappings, which then reduces in a probabilistic setting to a log-likelihood maximization problem that we solve via the Expectation-Maximization (EM) algorithm. The EM algorithm is initialized in the spectral domain by transforming the sampled vertices via classical Multidimensional Scaling (MDS). Minimization of the isometric distortion, and hence maximization of the log-likelihood function, is then achieved in the original 3D euclidean space, for each iteration of the EM algorithm, in two steps: by first using bipartite perfect matching, and then a greedy optimization algorithm. The optimal mapping obtained at convergence can be one-to-one or many-to-one upon choice. We demonstrate the performance of our method on various isometric (or nearly isometric) pairs of shapes for some of which the ground-truth correspondence is available.