Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Conformal Wasserstein distance: II. computational aspects and extensions
HTML articles powered by AMS MathViewer

by Y. Lipman, J. Puente and I. Daubechies PDF
Math. Comp. 82 (2013), 331-381 Request permission

Abstract:

This paper is a companion paper to [Yaron Lipman and Ingrid Daubechies, Conformal Wasserstein distances: Comparing surfaces in polynomial time, Adv. in Math. (ELS), 227 (2011), no. 3, 1047–1077, (2011)]. We provide numerical procedures and algorithms for computing the alignment of and distance between two disk-type surfaces. We provide a convergence analysis of the discrete approximation to the arising mass-transportation problems. We furthermore generalize the framework to support sphere-type surfaces, and prove a result connecting this distance to local geodesic distortion. Finally, we perform numerical experiments on several surface datasets and compare them to state-of-the-art methods.
References
  • Alexander M. Bronstein, Michael M. Bronstein, and Ron Kimmel, Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching, Proc. Natl. Acad. Sci. USA 103 (2006), no. 5, 1168–1172. MR 2204074, DOI 10.1073/pnas.0508601103
  • Mikael Fortelius, Jukka Jernvall, Alistair R. Evans, Gregory P. Wilson, High-level similarity of dentitions in carnivorans and rodents, Nature 445 (2007), 78–81.
  • Susanne C. Brenner and L. Ridgway Scott, The mathematical theory of finite element methods, 3rd ed., Texts in Applied Mathematics, vol. 15, Springer, New York, 2008. MR 2373954, DOI 10.1007/978-0-387-75934-0
  • Alexander M. Bronstein, Michael M. Bronstein, and Ron Kimmel, Numerical geometry of non-rigid shapes, Monographs in Computer Science, Springer, New York, 2008. With a foreword by Alfred M. Bruckstein. MR 2493634
  • Alexander M. Bronstein, Michael M. Bronstein, and Ron Kimmel, Efficient computation of isometry-invariant distances between surfaces, SIAM J. Sci. Comput. 28 (2006), no. 5, 1812–1836. MR 2272190, DOI 10.1137/050639296
  • Eranda Çela, The quadratic assignment problem, Combinatorial Optimization, vol. 1, Kluwer Academic Publishers, Dordrecht, 1998. Theory and algorithms. MR 1490831, DOI 10.1007/978-1-4757-2787-6
  • Gerhard Dziuk, Finite elements for the Beltrami operator on arbitrary surfaces, Partial differential equations and calculus of variations, Lecture Notes in Math., vol. 1357, Springer, Berlin, 1988, pp. 142–155. MR 976234, DOI 10.1007/BFb0082865
  • Y. Eldar, M. Lindenbaum, M. Porat, and Y. Zeevi, The farthest point strategy for progressive image sampling, 1997.
  • Bruce Fischl, Martin I. Sereno, Roger B. H. Tootell, and Anders M. Dale, High-resolution intersubject averaging and a coordinate system for the cortical surface, Hum. Brain Mapp 8 (1999), 272–284.
  • Daniela Giorgi, Silvia Biasotti, and Laura Paraboschi, SHREC:SHape REtrieval Contest: Watertight models track, http://watertight.ge.imati.cnr.it/, 2007.
  • Misha Gromov, Metric structures for Riemannian and non-Riemannian spaces, Progress in Mathematics, vol. 152, Birkhäuser Boston, Inc., Boston, MA, 1999. Based on the 1981 French original [ MR0682063 (85e:53051)]; With appendices by M. Katz, P. Pansu and S. Semmes; Translated from the French by Sean Michael Bates. MR 1699320
  • Xianfeng Gu and Shing-Tung Yau, Global conformal surface parameterization, SGP ’03: Proceedings of the 2003 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing (Aire-la-Ville, Switzerland, Switzerland), Eurographics Association, 2003, pp. 127–137.
  • Steven Haker, Lei Zhu, Allen Tannenbaum, and Sigurd Angenent, Optimal mass transport for registration and warping, International Journal on Computer Vision 60 (2004), 225–240.
  • Klaus Hildebrandt, Konrad Polthier, and Max Wardetzky, On the convergence of metric and geometric properties of polyhedral surfaces, Geom. Dedicata 123 (2006), 89–112. MR 2299728, DOI 10.1007/s10711-006-9109-5
  • L. Kantorovitch, On the translocation of masses, C. R. (Doklady) Acad. Sci. URSS (N.S.) 37 (1942), 199–201. MR 0009619
  • Hershel M. Farkas and Irwin Kra, Riemann surfaces, Graduate Texts in Mathematics, vol. 71, Springer-Verlag, New York-Berlin, 1980. MR 583745
  • L. Lovász and M. D. Plummer, Matching theory, North-Holland Mathematics Studies, vol. 121, North-Holland Publishing Co., Amsterdam; North-Holland Publishing Co., Amsterdam, 1986. Annals of Discrete Mathematics, 29. MR 859549
  • L.M. Parsons, M. Liotti, C.S. Freitas, L. Rainey, P.V. Kochunov, D. Nickerson, S.A. Mikiten, P.T. Fox, J.L. Lancaster, M.G. Woldorff, Automated talairach atlas labels for functional brain mapping, Human Brain Mapping 10 (2000), 120–131.
  • Y. Lipman and I. Daubechies, Conformal Wasserstein distances: comparing surfaces in polynomial time, Adv. Math. 227 (2011), no. 3, 1047–1077. MR 2799600, DOI 10.1016/j.aim.2011.01.020
  • Yaron Lipman and Thomas Funkhouser, Möbius voting for surface correspondence, ACM Transactions on Graphics (Proc. SIGGRAPH) 28 (2009), no. 3.
  • Facundo Memoli, On the use of Gromov-Hausdorff distances for shape comparison, Symposium on Point Based Graphics (2007).
  • Facundo Mémoli and Guillermo Sapiro, A theoretical and computational framework for isometry invariant recognition of point cloud data, Found. Comput. Math. 5 (2005), no. 3, 313–347. MR 2168679, DOI 10.1007/s10208-004-0145-y
  • Patrick Billingsley, Convergence of probability measures, John Wiley & Sons, Inc., New York-London-Sydney, 1968. MR 0233396
  • Ulrich Pinkall and Konrad Polthier, Computing discrete minimal surfaces and their conjugates, Experiment. Math. 2 (1993), no. 1, 15–36. MR 1246481
  • Konrad Polthier, Conjugate harmonic maps and minimal surfaces, Preprint No. 446, TU-Berlin, SFB 288 (2000).
  • Konrad Polthier, Computational aspects of discrete minimal surfaces, Global theory of minimal surfaces, Clay Math. Proc., vol. 2, Amer. Math. Soc., Providence, RI, 2005, pp. 65–111. MR 2167256
  • Y. Rubner, C. Tomasi, and L. J. Guibas, The earth mover’s distance as a metric for image retrieval, International Journal of Computer Vision 40 (2000), no. 2, 99–121.
  • B. Conroy, R.E. Bryan, P.J. Ramadge, J.V. Haxby, M.R. Sabuncu, B.D. Singer, Function-based intersubject alignment of human cortical anatomy, Cereb Cortex. (2009).
  • Alexander Schrijver, A course in combinatorial optimization, course notes, 2008.
  • Boris Springborn, Peter Schröder, and Ulrich Pinkall, Conformal equivalence of triangle meshes, ACM SIGGRAPH 2008 papers (New York, NY, USA), SIGGRAPH ’08, ACM, 2008, pp. 77:1–77:11.
  • George Springer, Introduction to Riemann surfaces, Addison-Wesley Publishing Co., Inc., Reading, Mass., 1957. MR 0092855
  • Cédric Villani, Topics in optimal transportation, Graduate Studies in Mathematics, vol. 58, American Mathematical Society, Providence, RI, 2003. MR 1964483, DOI 10.1090/gsm/058
  • W. Zeng, X. Yin, Y. Zeng, Y. Lai, X. Gu, and D. Samaras, 3d face matching and registration based on hyperbolic Ricci flow, CVPR Workshop on 3D Face Processing (2008), 1–8.
  • W. Zeng, Y. Zeng, Y. Wang, X. Yin, X. Gu, and D. Samaras, 3d non-rigid surface matching and registration based on holomorphic differentials, The 10th European Conference on Computer Vision (ECCV) (2008).
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC (2010): 65D18
  • Retrieve articles in all journals with MSC (2010): 65D18
Additional Information
  • Y. Lipman
  • Affiliation: Department of Mathematics and Computer Science, Weizmann Institute of Science, Rehovot, 76100 Israel
  • MR Author ID: 885123
  • J. Puente
  • Affiliation: Department of Mathematics, Princeton University, Princeton, New Jersey
  • I. Daubechies
  • Affiliation: Department of Mathematics, Duke University, Durham, North Carolina
  • MR Author ID: 54800
  • ORCID: 0000-0002-6472-1056
  • Received by editor(s): May 4, 2010
  • Received by editor(s) in revised form: October 10, 2010
  • Published electronically: July 16, 2012
  • © Copyright 2012 American Mathematical Society
    The copyright for this article reverts to public domain 28 years after publication.
  • Journal: Math. Comp. 82 (2013), 331-381
  • MSC (2010): Primary 65D18
  • DOI: https://doi.org/10.1090/S0025-5718-2012-02569-5
  • MathSciNet review: 2983027