Abstract: optimal transportation plays a fundamental role in many fields in engineering and medicine, including surface parameterization in graphics, registration in computer vision, and generative models in deep learning. For quadratic distance cost, optimal transportation map is the gradient of the Brenier potential, which can be obtained by solving the monge-Ampère equation. Furthermore, it is induced to a geometric convex optimization problem. The monge-Ampère equation is highly non-linear, and during the solving process, the intermediate solutions have to be strictly convex. Specifically, the accuracy of the discrete solution heavily depends on the sampling pattern of the target measure. In this work, we propose a self-adaptive sampling algorithm which greatly reduces the sampling bias and improves the accuracy and robustness of the discrete solutions. Experimental results demonstrate the efficiency and efficacy of our method.

基于自适应采样的鲁棒精确最优传输映射

[1]Alauzet F, Loseille A, Dervieux A, et al., 2006. Multi-dimensional continuous metric for mesh adaptation. Proc 15^th Int Meshing Roundtable, p.191-214.

[2]Apel T, Lube G, 1996. Anisotropic mesh refinement in stabilized Galerkin methods. Num Math, 74(3):261-282.

[3]Apel T, Grosman S, Jimack PK, et al., 2004. A new methodology for anisotropic mesh refinement based upon error gradients. Appl Num Math, 50(3-4):329-341.

[4]Arjovsky M, Chintala S, Bottou L, 2017. Wasserstein generative adversarial networks. Proc 34^th Int Conf on Machine Learning, p.214-223.

[5]Berndt M, Shashkov MJ, 2003. Multilevel accelerated optimization for problems in grid generation. Proc 12^th Int Meshing Roundtable, p.351-359.

[6]Bossen FJ, Heckbert PS, 1996. A pliant method for anisotropic mesh generation. Proc 5^th Int Meshing Roundtable, p.115-126.

[7]Bottasso CL, 2004. Anisotropic mesh adaption by metric-driven optimization. Int J Num Methods Eng, 60(3):597-639.

[8]Brandts J, Korotov S, Křížek M, 2008. On the equivalence of regularity criteria for triangular and tetrahedral finite element partitions. Comp Math Appl, 55(10):2227-2233.

[9]Brenier Y, 1991. Polar factorization and monotone rearrangement of vector-valued functions. Comm Pure Appl Math, 44(4):375-417.

[10]Chen L, Xu JC, 2004. Optimal Delaunay triangulations. J Comp Math, 22(2):299-308.

[11]Cheng SW, Dey TK, Ramos EA, et al., 2007. Sampling and meshing a surface with guaranteed topology and geometry. SIAM J Comp, 37(4):1199-1227.

[12]Cheng SW, Dey TK, Shewchuk JR, 2012. Delaunay Mesh Generation. CRC Press, Boca Raton, USA.

[13]Chew LP, 1989. Guaranteed-Quality Triangular Meshes. Technical Report TR 89-983. Computer Science Department, Cornell University, USA.

[14]Chew LP, 1993. Guaranteed-quality mesh generation for curved surfaces. Proc 9^th Annual Symp on Computational Geometry, p.274-280.

[15]Cui L, Qi X, Wen CF, et al., 2019. Spherical optimal transportation. Comp Aided Des, 115:181-193.

[16]Cuturi M, 2013. Sinkhorn distances: lightspeed computation of optimal transportation distances. https://arxiv.org/abs/1306.0895

[17]de Goes F, Cohen-Steiner D, Alliez P, et al., 2011. An optimal transport approach to robust reconstruction and simplification of 2D shapes. Comp Graph Forum, 30(5):1593-1602.

[18]de Goes F, Breeden K, Ostromoukhov V, et al., 2012. Blue noise through optimal transport. ACM Trans Graph, 31(6):171.

[19]Dey TK, 2007. Curve and Surface Reconstruction: Algorithms with Mathematical Analysis. Cambridge University Press, NY, UK.

[20]Dey TK, Levine JA, 2007. Delaunay meshing of isosurfaces. Proc Shape Modeling Int, p.241-250.

[21]Dey TK, Ray T, 2010. Polygonal surface remeshing with Delaunay refinement. Eng Comp, 26(3):289-301.

[22]Dobrzynski C, Frey P, 2008. Anisotropic Delaunay mesh adaptation for unsteady simulations. Proc 17^th Int Meshing Roundtable, p.177-194.

[23]Dominitz A, Tannenbaum A, 2010. Texture mapping via optimal mass transport. IEEE Trans Vis Comput Graph, 16(3):419-433.

[24]Du Q, Wang DS, 2005. Anisotropic centroidal Voronoi tessellations and their applications. SIAM J Sci Comput, 26(3):737-761.

[25]Edelsbrunner H, 2001. Geometry and Topology for Mesh Generation. Cambridge University Press, Cambridge, England, UK.

[26]Gu XF, Luo F, Sun J, et al., 2016. Variational principles for Minkowski type problems, discrete optimal transport, and discrete Monge-Ampère equations. Asian J Math, 20(2):383-398.

[27]Gu XF, Luo F, Sun J, et al., 2018. A discrete uniformization theorem for polyhedral surfaces. J Diff Geom, 109(2):223-256.

[28]Guan P, Wang XJ, et al., 1998. On a Monge-Ampère equation arising in geometric optics. J Diff Geom, 48(2):205-223.

[29]Gulrajani I, Ahmed F, Arjovsky M, et al., 2017. Improved training of Wasserstein GANs. Proc 31^st Int Conf on Neural Information Processing Systems, p.5769-5779.

[30]Gutiérrez CE, Huang Q, 2009. The refractor problem in reshaping light beams. Archive Ration Mech Anal, 193(2):423-443.

[31]Huang WZ, 2006. Mathematical principles of anisotropic mesh adaptation. Commun Comput Phys, 1(2):276-310.

[32]Kantorovich LV, 2006. On a problem of Monge. J Math Sci, 133(4):1383.

[33]Kitagawa J, M‘erigot Q, Thibert B, 2019. Convergence of a Newton algorithm for semi-discrete optimal transport. J Eur Math Soc, 21(9):2603-2651.

[34]Kunert G, 2002. Toward anisotropic mesh construction and error estimation in the finite element method. Num Meth Partial Diff Equ, 18(5):625-648.

[35]Lei N, Su KH, Cui L, et al., 2019. A geometric view of optimal transportation and generative mode. Comp Aided Geomet Des, 68:1-21.

[36]Liu Y, Wang WP, Lévy B, et al., 2009. On centroidal Voronoi tessellation-energy smoothness and fast computation. ACM Trans Graph, 28(4):1-17.

[37]Löhner R, Cebral J, 2000. Generation of non-isotropic unstructured grids via directional enrichment. Int J Numl Meth Eng, 49(1-2):219-232.

[38]Mérigot Q, 2011. A multiscale approach to optimal transport. Comp Graph Forum, 30(5):1583-1592.

[39]Meyron J, Mérigot Q, Thibert B, 2018. Light in power: a general and parameter-free algorithm for caustic design. ACM Trans Graph, 37(6):224.

[40]Nadeem S, Su ZY, Zeng W, et al., 2017. Spherical parameterization balancing angle and area distortions. IEEE Trans Vis Comput Graph, 23(6):1663-1676.

[41]Rong G, Liu Y, Wang W, et al., 2011. GPU-assisted computation of centroidal Voronoi tessellation. IEEE Trans Vis Comp Graph, 17(3):345-356.

[42]Ruppert J, 1995. A Delaunay refinement algorithm for quality 2-dimensional mesh generation. J Algorithms, 18(3):548-585.

[43]Shewchuk JR, 2002. Delaunay refinement algorithms for triangular mesh generation. Comput Geom, 22(1-3):21-74.

[44]Sirois, Y, Dompierre J, Vallet MG, et al., 2006. Mesh smoothing based on Riemannian metric non-conformity minimization. Proc 15^th Int Meshing Roundtable, p.271-288.

[45]Solomon J, Rustamov R, Guibas L, et al., 2014. Earth mover’s distances on discrete surfaces. ACM Trans Graph, 33(4):67.

[46]Solomon J, de Goes F, Peyré G, et al., 2015. Convolutional Wasserstein distances: efficient optimal transportation on geometric domains. ACM Trans Graph, 34(4):66.

[47]Su KH, Cui L, Qian K, et al., 2016. Area-preserving mesh parameterization for poly-annulus surfaces based on optimal mass transportation. Comp Aided Geom Des, 46:76-91.

[48]Su KH, Chen W, Lei N, et al., 2017. Volume preserving mesh parameterization based on optimal mass transportation. Comp Aided Des, 82:42-56.

[49]Su ZY, Zeng W, Shi R, et al., 2013. Area preserving brain mapping. Proc IEEE Conf on Computer Vision and Pattern Recognition, p.2235-2242.

[50]Su ZY, Wang YL, Shi R, et al., 2015. Optimal mass transport for shape matching and comparison. IEEE Trans Patt Anal Mach Intell, 37(11):2246-2259.

[51]ur Rehman T, Haber E, Pryor G, et al., 2009. 3D nonrigid registration via optimal mass transport on the GPU. Med Image Anal, 13(6):931-940.

[52]Villani C, 2008. Optimal Transport: Old and New. Springer Science & Business Media, Berlin, Germany.

[53]Wang XJ, 1996. On the design of a reflector antenna. Inverse Probl, 12(3):351.

[54]Wang XJ, 2004. On the design of a reflector antenna II. Calc Var Part Diff Equ, 20(3):329-341.

[55]Yan DM, Wang K, Levy B, et al., 2011. Computing 2D periodic centroidal Voronoi tessellation. 8^th Int Symp on Voronoi Diagrams in Science and Engineering, p.177-184.

[56]Yau ST, 1998. S.S. Chern: a Great Geometer of the Twentieth Century. International Press of Boston, p.366.

[57]Zhao X, Su ZY, Gu XD, et al., 2013. Area-preservation mapping using optimal mass transport. IEEE Trans Vis Comp Graph, 19(12):2838-2847.