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. R. Kimmel, A. M. Bronstein, M. M. Bronstein, Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching, Proc. National Academy of Sciences (PNAS) 103 (2006), no. 5, 1168-1172. MR 2204074 (2006i:65022)
  • 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, third ed., Texts in Applied Mathematics, vol. 15, 2008. MR 2373954 (2008m:65001)
  • 4. Alexander Bronstein, Michael Bronstein, and Ron Kimmel, Numerical geometry of non-rigid shapes, 1st ed., Springer Publishing Company, Incorporated, 2008. MR 2493634 (2010b:68165)
  • 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 (2007i:53041)
  • 6. E. Cela, The quadratic assignment problem: Theory and algorithms (combinatorial optimization), Springer, 1998. MR 1490831 (99a:90001)
  • 7. Gerhard Dziuk, Finite elements for the $ \mbox {B}$eltrami operator on arbitrary surfaces, vol. 1357, Springer Berlin / Heidelberg, 1988. MR 976234 (90i:65194)
  • 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. Mikhail Gromov, M. Katz, P. Pansu, and S. Semmes, Metric structures for Riemannian and non-Riemannian spaces, Birkhäuser Boston, December 2006. MR 1699320 (2000d:53065)
  • 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. Hildebrandt, Klaus, Polthier, Konrad, Wardetzky, and Max, On the convergence of metric and geometric properties of polyhedral surfaces, Geometriae Dedicata 123 (2006), no. 1, 89-112. MR 2299728 (2008k:53009)
  • 15. L. Kantorovich, On the translocation of masses, C.R. (Dokl.) Acad. Sci. URSS (N.S.) 37 (1942), 199-201. MR 0009619 (5:174d)
  • 16. Irwin Kra, Hershel M. Farkas, Riemann surfaces, Springer, 1992. MR 583745 (82c:30067)
  • 17. M.D. Plummer, L. Lovász, Matching theory, North-Holland, 1986. MR 859549 (88b:90087)
  • 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. Yaron Lipman and Ingrid Daubechies, Conformal Wasserstein distances: Comparing surfaces in polynomial time, Advances in Mathematics (ELS), 227 (2011), no. 3, 1047-1077, (2011). 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 (2006f:68109)
  • 23. Patrick Billingsley, Convergence of probability measures, John Wiley & Sons, 1968. MR 0233396 (38:1718)
  • 24. Ulrich Pinkall and Konrad Polthier, Computing discrete minimal surfaces and their conjugates, Experimental Mathematics 2 (1993), 15-36. MR 1246481 (94j:53009)
  • 25. Konrad Polthier, Conjugate harmonic maps and minimal surfaces, Preprint No. 446, TU-Berlin, SFB 288 (2000).
  • 26. -, Computational aspects of discrete minimal surfaces, Global Theory of Minimal Surfaces, Proc. of the Clay Mathematics Institute 2001 Summer School, David Hoffman (Ed.), CMI/AMS (2005). MR 2167256 (2006i:53006)
  • 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, AMS Chelsea Publishing, 1981. MR 0092855 (19:1169g)
  • 32. Cedric Villani, Topics in optimal transportation (Graduate Studies in Mathematics, vol. 58), American Mathematical Society, March 2003. MR 1964483 (2004e:90003)
  • 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