“Earth mover’s distances on discrete surfaces” by Solomon, Rustamov, Guibas and Butscher
Conference:
Type:
Title:
- Earth mover's distances on discrete surfaces
Session/Category Title: Geometry Processing
Presenter(s)/Author(s):
Moderator(s):
Abstract:
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.
References:
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
