×

Convolutional Wasserstein distances: efficient optimal transportation on geometric domains. (English) Zbl 1334.68267


MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
65D05 Numerical interpolation
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
65K10 Numerical optimization and variational techniques
94A17 Measures of information, entropy

Software:

EMD
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agueh, M., and Carlier, G. 2011. Barycenters in the Wasserstein space.SIAM J. Math. Anal. 43, 2, 904–924. · Zbl 1223.49045
[2] Ashikhmin, M., and Shirley, P. 2000. An anisotropic Phong BRDF model.J. of Graph. Tools 5, 2, 25–32.
[3] Aubry, M., Schlickewei, U., and Cremers, D. 2011. The wave kernel signature: A quantum mechanical approach to shape analysis. InProc. ICCV Workshops, 1626–1633.
[4] Benamou, J.-D., and Brenier, Y. 2000. A computational fluid mechanics solution of the Monge-Kantorovich mass transfer problem.Numerische Mathematik 84, 3, 375–393. · Zbl 0968.76069
[5] Benamou, J.-D., Carlier, G., Cuturi, M., Nenna, L., and Peyré, G. 2015. Iterative Bregman projections for regularized transportation problems.SIAM J. Sci. Comp., to appear. · Zbl 1319.49073
[6] Blinn, J. F. 1977. Models of light reflection for computer synthesized pictures. InProc. SIGGRAPH, vol. 11, 192–198. · doi:10.1145/563858.563893
[7] Bonneel, N., van de Panne, M., Paris, S., and Heidrich, W. 2011. Displacement interpolation using Lagrangian mass transport.ACM Trans. Graph. 30, 6 (Dec.), 158:1–158:12.
[8] Bonneel, N., Rabin, J., Peyré, G., and Pfister, H. 2014. Sliced and Radon Wasserstein barycenters of measures.J. Math. Imaging and Vision, to appear. · Zbl 1332.94014
[9] Bregman, L. 1967. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming.USSR Comp. Math. and Math. Physics 7, 3, 200–217. · Zbl 0186.23807
[10] Burkard, R., and Çela, E. 1999. Linear assignment problems and extensions.Handbook of Combinatorial Optimization: Supplement 1, 75.
[11] Burkard, R., Dell’Amico, M., and Martello, S. 2009.Assignment Problems.SIAM.
[12] Carlier, G., Oberman, A., and Oudet, E. 2014. Numerical methods for matching for teams and Wasserstein barycenters. Preprint, Ceremade. · Zbl 1331.49042
[13] Cover, T., and Thomas, J. 2006.Elements of Information Theory.Wiley. · Zbl 1140.94001
[14] Crane, K., Weischedel, C., and Wardetzky, M. 2013. Geodesics in heat: A new approach to computing distance based on heat flow.ACM Trans. Graph. 32, 5 (Oct.), 152:1–152:11.
[15] Cuturi, M., and Doucet, A. 2014. Fast computation of Wasserstein barycenters. InProc. ICML, vol. 32.
[16] Cuturi, M. 2013. Sinkhorn distances: Lightspeed computation of optimal transportation. InProc. NIPS, vol. 26. 2292–2300.
[17] Davis, T. A. 2006.Direct Methods for Sparse Linear Systems.SIAM. · Zbl 1119.65021
[18] de Goes, F., Cohen-Steiner, D., Alliez, P., and Desbrun, M. 2011. An optimal transport approach to robust reconstruction and simplification of 2d shapes. InComputer Graph. Forum, vol. 30, 1593–1602.
[19] de Goes, F., Breeden, K., Ostromoukhov, V., and Desbrun, M. 2012. Blue noise through optimal transport.ACM Trans. Graph. 31, 6 (Nov.), 171:1–171:11.
[20] de Goes, F., Memari, P., Mullen, P., and Desbrun, M. 2014. Weighted triangulations for geometry processing.ACM Trans. Graph. 33, 3. · Zbl 1322.68217
[21] Delon, J. 2006. Movie and video scale-time equalization application to flicker reduction.IEEE Trans. on Image Proc. 15, 1, 241–248.
[22] Deming, W. E., and Stephan, F. F. 1940. On a least squares adjustment of a sampled frequency table when the expected marginal totals are known.Annals Math. Stat. 11, 4, 427–444. · Zbl 0024.05502
[23] Deriche, R. 1993. Recursively implementing the Gaussian and its derivatives. Tech. Rep. RR-1893.
[24] Desbrun, M., Meyer, M., Schröder, P., and Barr, A. H. 1999. Implicit fairing of irregular meshes using diffusion and curvature flow. InProc. SIGGRAPH, 317–324.
[25] Escalante, R., and Raydan, M. 2011.Alternating Projection Methods.Fundamentals of Algorithms. SIAM. · Zbl 1275.65031
[26] Ferradans, S., Papadakis, N., Peyré, G., and Aujol, J.-F. 2014. Regularized discrete optimal transport.SIAM J. Imaging Sci. 7, 3, 1853–1882. · Zbl 1308.90128
[27] Franklin, J., and Lorenz, J. 1989. On the scaling of multidimensional matrices.Linear Algebra and its Applications 114, 717–735. · Zbl 0674.15001
[28] Johnson, D. B. 1977. Efficient algorithms for shortest paths in sparse networks.J. ACM 24, 1 (Jan.), 1–13. · Zbl 0343.68028
[29] Ju, T., Schaefer, S., and Warren, J. 2005. Mean value coordinates for closed triangular meshes.ACM Trans. Graph. 24, 3 (July), 561–566.
[30] Kantorovich, L. 1942. On the transfer of masses (in Russian).Doklady Akademii Nauk 37, 2, 227–229.
[31] Kim, Y.-H., and Pass, B. 2013. Multi-marginal optimal transport on Riemannian manifolds.arXiv:1303.6251. · Zbl 1328.49044
[32] Knight, P. 2008. The Sinkhorn–Knopp algorithm: Convergence and applications.SIAM J. on Matrix Anal. and Applications 30, 1, 261–275. · Zbl 1166.15301
[33] Léonard, C. 2012. From the Schrödinger problem to the Monge-Kantorovich problem.J. Funct. Anal. 262, 4, 1879–1920. · Zbl 1236.49088
[34] Lipman, Y., and Daubechies, I. 2011. Conformal Wasserstein distances: Comparing surfaces in polynomial time.Adv. Math. 227, 3, 1047–1077. · Zbl 1217.53026
[35] MacNeal, R. 1949.The Solution of Partial Differential Equations by means of Electrical Networks.PhD thesis, Caltech.
[36] Malliavin, P., and Stroock, D. W. 1996. Short time behavior of the heat kernel and its logarithmic derivatives.J. Differential Geom. 44, 3, 550–570. · Zbl 0873.58063
[37] McCann, R. J. 1997. A convexity principle for interacting gases.Adv. Math. 128, 1, 153–179. · Zbl 0901.49012
[38] Mérigot, Q. 2011. A multiscale approach to optimal transport.Comp. Graph. Forum 30, 5, 1583–1592.
[39] Mosek ApS, 2014. Mosek version 7. https://mosek.com.
[40] Papadakis, N., Provenzi, E., and Caselles, V. 2011. A variational model for histogram transfer of color images.IEEE Trans. Image Proc. 20, 6, 1682–1695. · Zbl 1372.94202
[41] Pharr, M., and Humphreys, G. 2010.Physically Based Rendering, Second Edition: From Theory To Implementation.Morgan Kaufmann, July.
[42] Pitié, F., Kokaram, A. C., and Dahyot, R. 2007. Automated colour grading using colour distribution transfer.Comp. Vision and Image Understanding 107(July), 123–137.
[43] Rubner, Y., Tomasi, C., and Guibas, L. J. 2000. The earth mover’s distance as a metric for image retrieval.Int. J. Comput. Vision 40, 2 (Nov.), 99–121. · Zbl 1012.68705
[44] Schwartzburg, Y., Testuz, R., Tagliasacchi, A., and Pauly, M. 2014. High-contrast computational caustic design.ACM Trans. Graph. 33, 4 (July), 74:1–74:11. · Zbl 06863179
[45] Sinkhorn, R. 1964. A relationship between arbitrary positive matrices and doubly stochastic matrices.Annals of Math. Stat. 35, 2, 876–879. · Zbl 0134.25302
[46] Sinkhorn, R. 1967. Diagonal equivalence to matrices with prescribed row and column sums.American Math. Monthly 74, 4, 402–405. · Zbl 0166.03702
[47] Solomon, J., Nguyen, A., Butscher, A., Ben-Chen, M., and Guibas, L. 2012. Soft maps between surfaces.Comp. Graph. Forum 31, 5 (Aug.), 1617–1626.
[48] Solomon, J., Guibas, L., and Butscher, A. 2013. Dirichlet energy for analysis and synthesis of soft maps.Comp. Graph. Forum 32, 5, 197–206.
[49] Solomon, J., Rustamov, R., Guibas, L., and Butscher, A. 2014. Earth mover’s distances on discrete surfaces.ACM Trans. Graph. 33, 4 (July), 67:1–67:12. · Zbl 1396.65063
[50] Solomon, J., Rustamov, R., Leonidas, G., and Butscher, A. 2014. Wasserstein propagation for semi-supervised learning. InProc. ICML, 306–314.
[51] Varadhan, S. R. S. 1967. On the behavior of the fundamental solution of the heat equation with variable coefficients.Comm. on Pure and Applied Math. 20, 2, 431–455. · Zbl 0155.16503
[52] Villani, C. 2003.Topics in Optimal Transportation.Graduate Studies in Mathematics. AMS. · Zbl 1106.90001
[53] Zhao, X., Su, Z., Gu, X. D., Kaufman, A., Sun, J., Gao, J., and Luo, F. 2013. Area-preservation mapping using optimal mass transport.IEEE Trans. Vis. and Comp. Graphics 19, 12.
[54] Zhu, J.-Y., Lee, Y. J., and Efros, A. A. 2014. AverageExplorer: Interactive exploration and alignment of visual data collections.ACM Trans. Graph. 33, 4 (July), 160:1–160:11.
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.