Conformal Wasserstein distance: II. computational aspects and extensions

Lipman, Y.; Puente, J.; Daubechies, I.

doi:10.1090/S0025-5718-2012-02569-5

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).