×

Conformal Wasserstein distances: comparing surfaces in polynomial time. (English) Zbl 1217.53026

Summary: We present a constructive approach to surface comparison realizable by a polynomial-time algorithm. We determine the “similarity” of two given surfaces by solving a mass-transportation problem between their conformal densities. This mass transportation problem differs from the standard case in that we require the solution to be invariant under global Möbius transformations. We present in detail the case where the surfaces to compare are disk-like; we also sketch how the approach can be generalized to other types of surfaces.

MSC:

53B50 Applications of local differential geometry to the sciences
58D17 Manifolds of metrics (especially Riemannian)
53B20 Local Riemannian geometry

Software:

EMD
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] D.M. Boyer, Y. Lipman, E.St. Clair, J. Puente, B.A. Patel, T.A. Funkhouser, J. Jernvall, I. Daubechies, New algorithms to automatically quantify the geometric similarity of anatomical surfaces, submitted for publication.; D.M. Boyer, Y. Lipman, E.St. Clair, J. Puente, B.A. Patel, T.A. Funkhouser, J. Jernvall, I. Daubechies, New algorithms to automatically quantify the geometric similarity of anatomical surfaces, submitted for publication.
[2] Cela, E., The Quadratic Assignment Problem: Theory and Algorithms (Combinatorial Optimization) (1998), Springer
[3] Facundo Memoli, On the use of Gromov-Hausdorff distances for shape comparison, in: Symposium on Point Based Graphics, 2007.; Facundo Memoli, On the use of Gromov-Hausdorff distances for shape comparison, in: Symposium on Point Based Graphics, 2007. · Zbl 1254.54033
[4] Gu, Xianfeng David; Yau, Shing-Tung, Computational Conformal Geometry (2008), International Press: International Press Boston, Har/Cdr edition · Zbl 1144.65008
[5] Kantorovich, L., On the translocation of masses, C. R. Acad. Sci. URSS (N.S.), 37, 199-201 (1942) · Zbl 0061.09705
[6] Kimmel, R.; Bronstein, A. M.; Bronstein, M. M., Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching, Proc. Natl. Acad. Sci., 103, 5, 1168-1172 (2006) · Zbl 1160.65306
[7] Kra, Irwin; Farkas, Hershel M., Riemann Surfaces (1992), Springer · Zbl 0764.30001
[8] Lipman, Yaron; Daubechies, Ingrid, Surface comparison with mass transportation (2009), technical report
[9] Lipman, Yaron; Funkhouser, Thomas, Mobius voting for surface correspondence, Proc. SIGGRAPH. Proc. SIGGRAPH, ACM Trans. Graph., 28, 3 (2009)
[10] Mémoli, Facundo; Sapiro, Guillermo, A theoretical and computational framework for isometry invariant recognition of point cloud data, Found. Comput. Math., 5, 3, 313-347 (2005) · Zbl 1101.53022
[11] G. Monge, Mémoire sur la théorie des déblais et des remblais, in: Histoire de lʼAcadémie Royale des Sciences de Paris, avec les Mémoires de Mathématique et de Physique pour la même année, 1781, pp. 666-704.; G. Monge, Mémoire sur la théorie des déblais et des remblais, in: Histoire de lʼAcadémie Royale des Sciences de Paris, avec les Mémoires de Mathématique et de Physique pour la même année, 1781, pp. 666-704.
[12] Rubner, Y.; Tomasi, C.; Guibas, L. J., The earth moverʼs distance as a metric for image retrieval, Int. J. Comput. Vis., 40, 2, 99-121 (2000) · Zbl 1012.68705
[13] Springer, George, Introduction to Riemann Surfaces (1981), AMS Chelsea Publishing · Zbl 0501.30039
[14] Villani, Cedric, Topics in Optimal Transportation, Grad. Stud. Math., vol. 58 (March 2003), American Mathematical Society
[15] W. Zeng, X. Yin, Y. Zeng, Y. Lai, X. Gu, D. Samaras, 3d face matching and registration based on hyperbolic Ricci flow, in: CVPR Workshop on 3D Face Processing, 2008, pp. 1-8.; W. Zeng, X. Yin, Y. Zeng, Y. Lai, X. Gu, D. Samaras, 3d face matching and registration based on hyperbolic Ricci flow, in: CVPR Workshop on 3D Face Processing, 2008, pp. 1-8.
[16] W. Zeng, Y. Zeng, Y. Wang, X. Yin, X. Gu, D. Samaras, 3d non-rigid surface matching and registration based on holomorphic differentials, in: The 10th European Conference on Computer Vision (ECCV), 2008.; W. Zeng, Y. Zeng, Y. Wang, X. Yin, X. Gu, D. Samaras, 3d non-rigid surface matching and registration based on holomorphic differentials, in: The 10th European Conference on Computer Vision (ECCV), 2008.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.