Optimal transport approximation of 2-dimensional measures. (English) Zbl 1524.65097
Summary: We propose a fast and scalable algorithm to project a given density on a set of structured measures defined over a compact 2D domain. The measures can be discrete or supported on curves, for instance. The proposed principle and algorithm are a natural generalization of previous results revolving around the generation of blue-noise point distributions, such as Lloyd’s algorithm or more advanced techniques based on power diagrams. We analyze the convergence properties and propose new approaches to accelerate the generation of point distributions. We also design new algorithms to project curves onto spaces of curves with bounded length and curvature or speed and acceleration. We illustrate the algorithm’s interest through applications in advanced sampling theory, nonphotorealistic rendering, and path planning.
MSC:
| 65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |
| 49M15 | Newton-type methods |
| 49Q22 | Optimal transportation |
| 65D10 | Numerical smoothing, curve fitting |
Keywords:
Wasserstein distance; optimization; measure theory; sampling theory; blue noise; curve projection; quantization; path planning; nonphotorealistic renderingReferences:
| [1] | B. Adcock, A. C. Hansen, C. Poon, and B. Roman, Breaking the coherence barrier: A new theory for compressed sensing, Forum Math. Sigma, 5 (2017), e4. · Zbl 1410.94030 |
| [2] | E. Akleman, Q. Xing, P. Garigipati, G. Taubin, J. Chen, and S. Hu, Hamiltonian cycle art: Surface covering wire sculptures and duotone surfaces, Computers & Graphics, 37 (2013), pp. 316-332. |
| [3] | F. Aurenhammer, Power diagrams: Properties, algorithms and applications, SIAM J. Comput., 16 (1987), pp. 78-96, . · Zbl 0616.52007 |
| [4] | F. Aurenhammer, Voronoi diagrams: A survey of a fundamental geometric data structure, ACM Comput. Surveys (CSUR), 23 (1991), pp. 345-405. |
| [5] | F. Aurenhammer, F. Hoffmann, and B. Aronov, Minkowski-type theorems and least-squares clustering, Algorithmica, 20 (1998), pp. 61-76. · Zbl 0895.68135 |
| [6] | M. Balzer, T. Schlömer, and O. Deussen, Capacity-constrained point distributions: A variant of Lloyd’s method, ACM Trans. Graphics, 28 (2009), 86. |
| [7] | C. Boyer, N. Chauffert, P. Ciuciu, J. Kahn, and P. Weiss, On the generation of sampling schemes for magnetic resonance imaging, SIAM J. Imaging Sci., 9 (2016), pp. 2039-2072, . · Zbl 1439.94003 |
| [8] | C. Boyer, P. Weiss, and J. Bigot, An algorithm for variable density sampling with block-constrained acquisition, SIAM J. Imaging Sci., 7 (2014), pp. 1080-1107, . · Zbl 1343.94021 |
| [9] | N. Chauffert, P. Ciuciu, J. Kahn, and P. Weiss, Comment représenter une image avec un spaghetti?, in GRETSI, Lyon, France, 2015. |
| [10] | N. Chauffert, P. Ciuciu, J. Kahn, and P. Weiss, A projection method on measures sets, Constr. Approx., 45 (2017), pp. 83-111. · Zbl 1362.41003 |
| [11] | N. Chauffert, P. Weiss, J. Kahn, and P. Ciuciu, Gradient Waveform Design for Variable Density Sampling in Magnetic Resonance Imaging, preprint, , 2014. · Zbl 1439.94003 |
| [12] | Z. Chen, Z. Shen, J. Guo, J. Cao, and X. Zeng, Line drawing for 3D printing, Computers & Graphics, 66 (2017), pp. 85-92. |
| [13] | City of Philadelphia, Open Data in the Philadelphia Region, , 2017. |
| [14] | P. L. Combettes and J.-C. Pesquet, Proximal splitting methods in signal processing, in Fixed-Point Algorithms for Inverse Problems in Science and Engineering, Springer, New York, 2011, pp. 185-212. · Zbl 1242.90160 |
| [15] | F. De Goes, K. Breeden, V. Ostromoukhov, and M. Desbrun, Blue noise through optimal transport, ACM Trans. Graphics, 31 (2012), 171. |
| [16] | F. de Gournay, J. Kahn, and L. Lebrat, Differentiation and Regularity of Semi-Discrete Optimal Transport with Respect to the Parameters of the Discrete Measure, preprint, , 2018. · Zbl 1475.49055 |
| [17] | J. B. Du, Interactive Media Arts, , 2017. |
| [18] | Q. Du, V. Faber, and M. Gunzburger, Centroidal Voronoi tessellations: Applications and algorithms, SIAM Rev., 41 (1999), pp. 637-676, . · Zbl 0983.65021 |
| [19] | L. C. Evans and J. Spruck, Motion of level sets by mean curvature I, J. Differential Geom., 33 (1991), pp. 635-681. · Zbl 0726.53029 |
| [20] | R. W. Floyd, An adaptive algorithm for spatial gray-scale, Proc. Soc. Inf. Disp., 17 (1976), pp. 75-77. |
| [21] | M. Fornasier, J. Haškovec, and G. Steidl, Consistency of variational continuous-domain quantization via kinetic theory, Appl. Anal., 92 (2013), pp. 1283-1298. · Zbl 1273.82030 |
| [22] | W. Gangbo and R. J. McCann, The geometry of optimal transportation, Acta Math., 177 (1996), pp. 113-161. · Zbl 0887.49017 |
| [23] | M. T. Gastner and M. Newman, Optimal design of spatial distribution networks, Phys. Rev. E, 74 (2006), 016117. |
| [24] | P. Giselsson and S. Boyd, Linear convergence and metric selection for Douglas-Rachford splitting and ADMM, IEEE Trans. Automat. Control, 62 (2017), pp. 532-544. · Zbl 1364.90256 |
| [25] | R. Glowinski, On alternating direction methods of multipliers: A historical perspective, in Modeling, Simulation and Optimization for Science and Technology, Springer, New York, 2014, pp. 59-82. · Zbl 1320.65098 |
| [26] | G. N. Grapiglia and Yu. Nesterov, Regularized Newton methods for minimizing functions with Hölder continuous Hessians, SIAM J. Optim., 27 (2017), pp. 478-506, . · Zbl 1406.49029 |
| [27] | L. Greengard and V. Rokhlin, A fast algorithm for particle simulations, J. Comput. Phys., 73 (1987), pp. 325-348. · Zbl 0629.65005 |
| [28] | A. Hertzmann, A survey of stroke-based rendering, IEEE Comput. Graphics Appl., 23 (2003), pp. 70-81, . |
| [29] | S. Hiller, H. Hellwig, and O. Deussen, Beyond stippling: Methods for distributing objects on the plane, Comput. Graphics Forum, 22 (2003), pp. 515-522. |
| [30] | F. Jarre and P. L. Toint, Simple examples for the failure of Newton’s method with line search for strictly convex minimization, Math. Program., 158 (2016), pp. 23-34. · Zbl 1346.90665 |
| [31] | L. V. Kantorovich, On the translocation of masses, Dokl. Akad. Nauk. USSR (NS), 37 (1942), pp. 199-201. · Zbl 0061.09705 |
| [32] | C. S. Kaplan, R. Bosch, et al., TSP Art, in Proceedings of Renaissance Banff: Mathematics, Music, Art, Culture Conference, The Bridges Organization, 2005, pp. 301-308. |
| [33] | S. Y. Kim, R. Maciejewski, T. Isenberg, W. M. Andrews, W. Chen, M. C. Sousa, and D. S. Ebert, Stippling by example, in Proceedings of the 7th International Symposium on Non-Photorealistic Animation and Rendering, ACM, New York, 2009, pp. 41-50. |
| [34] | J. Kitagawa, Q. Mérigot, and B. Thibert, Convergence of a Newton Algorithm for Semi-Discrete Optimal Transport, preprint, , 2016. · Zbl 1439.49053 |
| [35] | B. Lévy, A numerical algorithm for L2 semi-discrete optimal transport in 3D, ESAIM Math. Model. Numer. Anal., 49 (2015), pp. 1693-1715. · Zbl 1331.49037 |
| [36] | B. Lévy and E. L. Schwindt, Notions of optimal transport theory and how to implement them on a computer, Computers & Graphics, 72 (2018), pp. 135-148. |
| [37] | G. Li and T. K. Pong, Global convergence of splitting methods for nonconvex composite optimization, SIAM J. Optim., 25 (2015), pp. 2434-2460, . · Zbl 1330.90087 |
| [38] | S. Lloyd, Least squares quantization in PCM, IEEE Trans. Inform. Theory, 28 (1982), pp. 129-137. · Zbl 0504.94015 |
| [39] | M. McAsey and L. Mou, Optimal locations and the mass transport problem, Contemp. Math., 226 (1999), pp. 131-148. · Zbl 0915.90177 |
| [40] | Q. Mérigot, A multiscale approach to optimal transport, Comput. Graphics Forum, 30 (2011), pp. 1583-1592, . |
| [41] | Q. Mérigot, J. Meyron, and B. Thibert, An algorithm for optimal transport between a simplex soup and a point cloud, SIAM J. Imaging Sci., 11 (2018), pp. 1363-1389, . · Zbl 1401.49068 |
| [42] | L. Moisan, Affine plane curve evolution: A fully consistent scheme, IEEE Trans. Image Process., 7 (1998), pp. 411-420. · Zbl 0973.94002 |
| [43] | G. Monge, Mémoire sur la théorie des déblais et des remblais, De l’Imprimerie Royale, Paris, France, 1781. |
| [44] | Y. Nesterov, Gradient methods for minimizing composite functions, Math. Program., 140 (2013), pp. 125-161. · Zbl 1287.90067 |
| [45] | Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Appl. Optim. 87, Springer, New York, 2013. |
| [46] | R. Nishihara, L. Lessard, B. Recht, A. Packard, and M. I. Jordan, A general analysis of the convergence of ADMM, in Proceedings of ICML, Lille, France, 2015, pp. 343-352. |
| [47] | J. Nocedal and S. J. Wright, Numerical Optimization, Springer, New York, 1999. · Zbl 0930.65067 |
| [48] | G. Pages and B. Wilbertz, Optimal Delaunay and Voronoi quantization schemes for pricing American style options, in Numerical Methods in Finance, Springer, New York, 2012, pp. 171-213. · Zbl 1247.91199 |
| [49] | R. Peyré, Comparison between \(W_2\) distance and \(H^{-1}\) norm, and localization of Wasserstein distance, ESAIM Control Optim. Calc. Var., 24 (2018), pp. 1489-1501. · Zbl 1415.49031 |
| [50] | R. A. Polyak, Regularized Newton method for unconstrained convex optimization, Math. Program., 120 (2009), pp. 125-145. · Zbl 1189.90121 |
| [51] | D. Potts and G. Steidl, Fast summation at nonequispaced knots by NFFTs, SIAM J. Sci. Comput., 24 (2003), pp. 2013-2037, . · Zbl 1040.65110 |
| [52] | S. Schlechtweg, T. Germer, and T. Strothotte, RenderBots Multi-Agent Systems for Direct Image Generation, Comput. Graphics Forum, 24 (2005), pp. 137-148. |
| [53] | C. Schmaltz, P. Gwosdek, A. Bruhn, and J. Weickert, Electrostatic halftoning, Comput. Graphics Forum, 29 (2010), pp. 2313-2327. |
| [54] | J. Solomon, F. De Goes, G. Peyré, M. Cuturi, A. Butscher, A. Nguyen, T. Du, and L. Guibas, Convolutional Wasserstein distances: Efficient optimal transportation on geometric domains, ACM Trans. Graphics, 34 (2015), 66. · Zbl 1334.68267 |
| [55] | A. Tagliasacchi, I. Alhashim, M. Olson, and H. Zhang, Mean curvature skeletons, Comput. Graphics Forum, 31 (2012), pp. 1735-1744. |
| [56] | T. Teuber, G. Steidl, P. Gwosdek, C. Schmaltz, and J. Weickert, Dithering by differences of convex functions, SIAM J. Imaging Sci., 4 (2011), pp. 79-108, . · Zbl 1214.49017 |
| [57] | The CGAL Project, CGAL User and Reference Manual, CGAL Editorial Board, 4.9 ed., 2016, . |
| [58] | R. Ulichney, Digital Halftoning, MIT Press, Cambridge, MA, 1987. |
| [59] | C. Villani, Topics in Optimal Transportation, Grad. Stud. Math. 58, AMS, Providence, RI, 2003. · Zbl 1106.90001 |
| [60] | C. Villani, Optimal Transport: Old and New, Grundlehren Math. Wiss. 338, Springer, Berlin, Heidelberg, 2008. |
| [61] | L.-Y. Wei, Multi-class blue noise sampling, ACM Trans. Graphics, 29 (2010), 79. |
| [62] | S.-Q. Xin, B. Lévy, Z. Chen, L. Chu, Y. Yu, C. Tu, and W. Wang, Centroidal power diagrams with capacity constraints: Computation, applications, and extension, ACM Trans. Graphics, 35 (2016), 244. |
| [63] | A. Yezzi, Modified curvature motion for image smoothing and enhancement, IEEE Trans. Image Process., 7 (1998), pp. 345-352. |
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.
