Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Conformal Wasserstein distance: II. computational aspects and extensions

Authors: Y. Lipman, J. Puente and I. Daubechies
Journal: Math. Comp. 82 (2013), 331-381
MSC (2010): Primary 65D18
Published electronically: July 16, 2012
MathSciNet review: 2983027
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. 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,
  • 2. Mikael Fortelius, Jukka Jernvall, Alistair R. Evans, Gregory P. Wilson, High-level similarity of dentitions in carnivorans and rodents, Nature 445 (2007), 78-81.
  • 3. 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
  • 4. 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
  • 5. 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,
  • 6. Eranda Çela, The quadratic assignment problem, Combinatorial Optimization, vol. 1, Kluwer Academic Publishers, Dordrecht, 1998. Theory and algorithms. MR 1490831
  • 7. 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,
  • 8. Y. Eldar, M. Lindenbaum, M. Porat, and Y. Zeevi, The farthest point strategy for progressive image sampling, 1997.
  • 9. 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.
  • 10. Daniela Giorgi, Silvia Biasotti, and Laura Paraboschi, SHREC:SHape REtrieval Contest: Watertight models track,, 2007.
  • 11. 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
  • 12. 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.
  • 13. 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.
  • 14. 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,
  • 15. L. Kantorovitch, On the translocation of masses, C. R. (Doklady) Acad. Sci. URSS (N.S.) 37 (1942), 199–201. MR 0009619
  • 16. Hershel M. Farkas and Irwin Kra, Riemann surfaces, Graduate Texts in Mathematics, vol. 71, Springer-Verlag, New York-Berlin, 1980. MR 583745
  • 17. 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
  • 18. 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.
  • 19. Y. Lipman and I. Daubechies, Conformal Wasserstein distances: comparing surfaces in polynomial time, Adv. Math. 227 (2011), no. 3, 1047–1077. MR 2799600,
  • 20. Yaron Lipman and Thomas Funkhouser, Möbius voting for surface correspondence, ACM Transactions on Graphics (Proc. SIGGRAPH) 28 (2009), no. 3.
  • 21. Facundo Memoli, On the use of Gromov-Hausdorff distances for shape comparison, Symposium on Point Based Graphics (2007).
  • 22. 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,
  • 23. Patrick Billingsley, Convergence of probability measures, John Wiley & Sons, Inc., New York-London-Sydney, 1968. MR 0233396
  • 24. Ulrich Pinkall and Konrad Polthier, Computing discrete minimal surfaces and their conjugates, Experiment. Math. 2 (1993), no. 1, 15–36. MR 1246481
  • 25. Konrad Polthier, Conjugate harmonic maps and minimal surfaces, Preprint No. 446, TU-Berlin, SFB 288 (2000).
  • 26. 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
  • 27. 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.
  • 28. 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).
  • 29. Alexander Schrijver, A course in combinatorial optimization, course notes, 2008.
  • 30. 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.
  • 31. George Springer, Introduction to Riemann surfaces, Addison-Wesley Publishing Company, Inc., Reading, Mass., 1957. MR 0092855
  • 32. Cédric Villani, Topics in optimal transportation, Graduate Studies in Mathematics, vol. 58, American Mathematical Society, Providence, RI, 2003. MR 1964483
  • 33. 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.
  • 34. 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

J. Puente
Affiliation: Department of Mathematics, Princeton University, Princeton, New Jersey

I. Daubechies
Affiliation: Department of Mathematics, Duke University, Durham, North Carolina

Received by editor(s): May 4, 2010
Received by editor(s) in revised form: October 10, 2010
Published electronically: July 16, 2012
Article copyright: © Copyright 2012 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society