“Earth mover’s distances on discrete surfaces” by Solomon, Rustamov, Guibas and Butscher

  • ©Justin Solomon, Raif Rustamov, Leonidas (Leo) J. Guibas, and Adrian Butscher




    Earth mover's distances on discrete surfaces

Session/Category Title: Geometry Processing




    We introduce a novel method for computing the earth mover’s distance (EMD) between probability distributions on a discrete surface. Rather than using a large linear program with a quadratic number of variables, we apply the theory of optimal transportation and pass to a dual differential formulation with linear scaling. After discretization using finite elements (FEM) and development of an accompanying optimization method, we apply our new EMD to problems in graphics and geometry processing. In particular, we uncover a class of smooth distances on a surface transitioning from a purely spectral distance to the geodesic distance between points; these distances also can be extended to the volume inside and outside the surface. A number of additional applications of our machinery to geometry problems in graphics are presented.


    1. Agueh, M., and Carlier, G. 2011. Barycenters in the Wasserstein space. SIAM J. Math. Anal. 43, 2, 904–924.Google ScholarCross Ref
    2. Arnold, V. 2003. Lectures on Partial Differential Equations. Universitext. Springer. Google ScholarDigital Library
    3. Beckmann, M. 1952. A continuous model of transportation. Econometrica, 643–660.Google Scholar
    4. Benamou, J.-D., and Brenier, Y. 2000. A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem. Numerische Mathematik 84, 3, 375–393.Google ScholarCross Ref
    5. Bonneel, N., van de Panne, M., Paris, S., and Heidrich, W. 2011. Displacement interpolation using Lagrangian mass transport. TOG 30, 6 (Dec.), 158:1–158:12. Google ScholarDigital Library
    6. Bonneel, N., Rabin, J., Peyré, G., and Pfister, H. 2013. Sliced and Radon Wasserstein barycenters of measures. Tech. rep., Preprint Hal-00881872.Google Scholar
    7. Boyd, S., Parikh, N., Chu, E., Peleato, B., and Eckstein, J. 2011. Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3, 1 (Jan.), 1–122. Google ScholarDigital Library
    8. Campen, M., Heistermann, M., and Kobbelt, L. 2013. Practical anisotropic geodesy. Proc. SGP 32, 5, 63–71. Google ScholarDigital Library
    9. Canny, J., and Reif, J. 1987. New lower bound techniques for robot motion planning problems. In Found. Comp. Sci., no. 28, 49–60. Google ScholarDigital Library
    10. Chazal, F., Cohen-Steiner, D., and Mérigot, Q. 2010. Geometric inference for measures based on distance functions. Tech. Rep. 6930, INRIA, June.Google Scholar
    11. Chazal, F., Cohen-Steiner, D., and Mérigot, Q. 2011. Geometric inference for probability measures. Found. Comp. Math. 11, 6, 733–751. Google ScholarDigital Library
    12. Coifman, R. R., Lafon, S., Lee, A. B., Maggioni, M., Nadler, B., Warner, F., and Zucker, S. W. 2005. Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps. PNAS 102, 21, 7426–7431.Google ScholarCross Ref
    13. Connolly, C., Burns, J. B., and Weiss, R. 1990. Path planning using Laplace’s equation. In Proc. Conf. on Robotics and Automation, vol. 3, 2102–2106.Google Scholar
    14. Crane, K., Weischedel, C., and Wardetzky, M. 2013. Geodesics in heat: A new approach to computing distance based on heat flow. TOG 32, 5 (Oct.), 152:1–152:11. Google ScholarDigital Library
    15. de Goes, F., Cohen-Steiner, D., Alliez, P., and Desbrun, M. 2011. An optimal transport approach to robust reconstruction and simplification of 2d shapes. CGF 30, 5, 1593–1602. Google ScholarDigital Library
    16. de Goes, F., Breeden, K., Ostromoukhov, V., and Desbrun, M. 2012. Blue noise through optimal transport. TOG 31, 6 (Nov.), 171:1–171:11. Google ScholarDigital Library
    17. Deza, M. M., and Laurent, M. 2009. Geometry of Cuts and Metrics. Springer. Google ScholarDigital Library
    18. Dominitz, A., and Tannenbaum, A. 2010. Texture mapping via optimal mass transport. TVCG 16, 3, 419–433. Google ScholarDigital Library
    19. Feldman, M., and McCann, R. 2002. Monge’s transport problem on a Riemannian manifold. Trans. AMS 354, 4, 1667–1697.Google ScholarCross Ref
    20. Folland, G. B. 1999. Real analysis: modern techniques and their applications, vol. 361. Wiley New York.Google Scholar
    21. Fouss, F., Pirotte, A., Renders, J.-M., and Saerens, M. 2007. Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation. Trans. Knowledge and Data Eng. 19, 3, 355–369. Google ScholarDigital Library
    22. Gu, X., Luo, F., Sun, J., and Yau, S.-T., 2013. Variational principles for Minkowski type problems, discrete optimal transport, and discrete Monge-Ampère equations.Google Scholar
    23. He, B., Yang, H., and Wang, S. 2000. Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities. J. Optim. Theory and App. 106, 2, 337–356.Google ScholarDigital Library
    24. Jiang, X., Lim, L.-H., Yao, Y., and Ye, Y. 2011. Statistical ranking and combinatorial Hodge theory. Mathematical Programming 127, 1, 203–244. Google ScholarDigital Library
    25. Ju, T., Schaefer, S., and Warren, J. 2005. Mean value coordinates for closed triangular meshes. TOG 24, 3 (July), 561–566. Google ScholarDigital Library
    26. Kimmel, R., and Sethian, J. A. 1998. Computing geodesic paths on manifolds. In PNAS, 8431–8435.Google Scholar
    27. Lai, R., Liang, J., and Zhao, H.-K. 2013. A local mesh method for solving PDEs on point clouds. Inverse Prob. and Imaging 7, 3, 737–755.Google ScholarCross Ref
    28. Li, Y. 1998. A Newton acceleration of the Weiszfeld algorithm for minimizing the sum of Euclidean distances. Comp. Optim. and App. 10, 3, 219–242. Google ScholarDigital Library
    29. Lia, G., Guoa, L., Niea, J., and Liu, T. 2010. An automated pipeline for cortical sulcal fundi extraction. Medical Image Analysis 14, 3, 343–359.Google ScholarCross Ref
    30. Liang, J., and Zhao, H. 2013. Solving partial differential equations on point clouds. J. Sci. Comp. 35, 3, A1461–A1486.Google Scholar
    31. Lipman, Y., and Daubechies, I. 2011. Conformal Wasserstein distances: Comparing surfaces in polynomial time. Advances in Mathematics 227, 3, 1047–1077.Google ScholarCross Ref
    32. Lipman, Y., Rustamov, R., and Funkhouser, T. 2010. Biharmonic distance. TOG 29, 3 (June). Google ScholarDigital Library
    33. Lipman, Y., Puente, J., and Daubechies, I. 2013. Conformal Wasserstein distance: II. Computational aspects and extensions. Math. Comp. 82, 331–381.Google ScholarCross Ref
    34. Mémoli, F. 2011. Gromov–Wasserstein distances and the metric approach to object matching. Found. Comp. Math. 11, 4, 417–487. Google ScholarDigital Library
    35. Mérigot, Q. 2011. A multiscale approach to optimal transport. CGF 30, 5, 1583–1592.Google ScholarCross Ref
    36. Mitchell, J. S. B., Mount, D. M., and Papadimitriou, C. H. 1987. The discrete geodesic problem. SIAM J. Comput. 16, 4 (Aug.), 647–668. Google ScholarDigital Library
    37. Mullen, P., Memari, P., de Goes, F., and Desbrun, M. 2011. HOT: Hodge-optimized triangulations. TOG 30, 4 (July), 103:1–103:12. Google ScholarDigital Library
    38. Pan, S., and Jiang, Y. 2008. Smoothing Newton method for minimizing the sum of p-norms. J. Optim. Theory and App. 137, 2, 255–275.Google ScholarDigital Library
    39. Panozzo, D., Baran, I., Diamanti, O., and Sorkine-Hornung, O. 2013. Weighted averages on surfaces. TOG 32, 4 (July), 60:1–60:12. Google ScholarDigital Library
    40. Pele, O., and Werman, M. 2009. Fast and robust earth mover’s distances. In Proc. ICCV, 460–467.Google Scholar
    41. Plastria, F. 2011. The Weiszfeld algorithm: Proof, amendments, and extensions. In Found. of Location Anal., H. A. Eiselt and V. Marianov, Eds., vol. 155 of Operations Research & Management Science. 357–389.Google Scholar
    42. Polthier, K., and Preuss, E. 2003. Identifying vector field singularities using a discrete Hodge decomposition. In Vis. and Math. III, H.-C. Hege and K. Polthier, Eds. Springer, 113–134.Google Scholar
    43. Qi, L., Sun, D., and Zhou, G. 2002. A primal–dual algorithm for minimizing a sum of Euclidean norms. J. Comp. Applied Math. 138, 1, 127–150. Google ScholarDigital Library
    44. Rubner, Y., Tomasi, C., and Guibas, L. J. 2000. The earth mover’s distance as a metric for image retrieval. IJCV 40, 2 (Nov.), 99–121. Google ScholarDigital Library
    45. Rustamov, R. M., Lipman, Y., and Funkhouser, T. 2009. Interior distance using barycentric coordinates. In Proc. SGP, 1279–1288. Google ScholarDigital Library
    46. Santambrogio, F. 2009. Absolute continuity and summability of transport densities: simpler proofs and new estimates. Calc. Var. PDE 36, 3, 343–354.Google ScholarCross Ref
    47. Santambrogio, F. 2013. Prescribed-divergence problems in optimal transportation. MSRI lecture notes, October 2013.Google Scholar
    48. Sayas, F.-J., 2008. A gentle introduction to the finite element method.Google Scholar
    49. Schwarz, G. 1995. Hodge decomposition: a method for solving boundary value problems. Lecture notes in mathematics. Springer.Google Scholar
    50. Solomon, J., Nguyen, A., Butscher, A., Ben-Chen, M., and Guibas, L. 2012. Soft maps between surfaces. CGF 31, 5 (Aug.), 1617–1626. Google ScholarDigital Library
    51. Solomon, J., Guibas, L., and Butscher, A. 2013. Dirichlet energy for analysis of synthesis of soft maps. Proc. SGP 32, 5 (Aug.), 197–206. Google ScholarDigital Library
    52. Sun, J., Chen, X., and Funkhouser, T. A. 2010. Fuzzy geodesics and consistent sparse correspondences for deformable shapes. Proc. SGP 29, 5, 1535–1544.Google Scholar
    53. Surazhsky, V., Surazhsky, T., Kirsanov, D., Gortler, S. J., and Hoppe, H. 2005. Fast exact and approximate geodesics on meshes. TOG 24, 3 (July), 553–560. Google ScholarDigital Library
    54. Takano, Y., and Yamamoto, Y. 2010. Metric-preserving reduction of earth mover’s distance. Asia Pac. J. Oper. Res. 27, 39.Google ScholarCross Ref
    55. Tong, Y., Alliez, P., Cohen-Steiner, D., and Desbrun, M. 2006. Designing quadrangulations with discrete harmonic forms. In Proc. SGP, 201–210. Google ScholarDigital Library
    56. Villani, C. 2003. Topics in Optimal Transportation. AMS.Google Scholar
    57. Weiszfeld, E. 1937. Sur le point pour lequel la somme des distances de n points donnés est minimum. Tôhoku Math. J. 43, 355–386.Google Scholar
    58. Zhou, G., Toh, K., and Sun, D. 2003. Globally and quadratically convergent algorithm for minimizing the sum of Euclidean norms. J. Optim. Theory and App. 119, 2, 357–377.Google ScholarDigital Library

ACM Digital Library Publication: