Full Text:   <2095>

Summary:  <1116>

CLC number: O242; TP391

On-line Access: 2021-09-10

Received: 2020-05-25

Revision Accepted: 2020-09-27

Crosschecked: 2021-08-19

Cited: 0

Clicked: 2943

Citations:  Bibtex RefMan EndNote GB/T7714

 ORCID:

Na Lei

https://orcid.org/0000-0003-3361-0756

-   Go to

Article info.
Open peer comments

Frontiers of Information Technology & Electronic Engineering  2021 Vol.22 No.9 P.1207-1220

http://doi.org/10.1631/FITEE.2000250


Robust and accurate optimal transportation map by self-adaptive sampling


Author(s):  Yingshi Wang, Xiaopeng Zheng, Wei Chen, Xin Qi, Yuxue Ren, Na Lei, Xianfeng Gu

Affiliation(s):  Department of Computer Science, Inner Mongolia University of Finance and Economics, Hohhot 010010, China; more

Corresponding email(s):   nalei@dlut.edu.cn, gu@cs.stonybrook.edu

Key Words:  Optimal transportation, Monge-Ampère equation, Self-adaptive sampling


Yingshi Wang, Xiaopeng Zheng, Wei Chen, Xin Qi, Yuxue Ren, Na Lei, Xianfeng Gu. Robust and accurate optimal transportation map by self-adaptive sampling[J]. Frontiers of Information Technology & Electronic Engineering, 2021, 22(9): 1207-1220.

@article{title="Robust and accurate optimal transportation map by self-adaptive sampling",
author="Yingshi Wang, Xiaopeng Zheng, Wei Chen, Xin Qi, Yuxue Ren, Na Lei, Xianfeng Gu",
journal="Frontiers of Information Technology & Electronic Engineering",
volume="22",
number="9",
pages="1207-1220",
year="2021",
publisher="Zhejiang University Press & Springer",
doi="10.1631/FITEE.2000250"
}

%0 Journal Article
%T Robust and accurate optimal transportation map by self-adaptive sampling
%A Yingshi Wang
%A Xiaopeng Zheng
%A Wei Chen
%A Xin Qi
%A Yuxue Ren
%A Na Lei
%A Xianfeng Gu
%J Frontiers of Information Technology & Electronic Engineering
%V 22
%N 9
%P 1207-1220
%@ 2095-9184
%D 2021
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.2000250

TY - JOUR
T1 - Robust and accurate optimal transportation map by self-adaptive sampling
A1 - Yingshi Wang
A1 - Xiaopeng Zheng
A1 - Wei Chen
A1 - Xin Qi
A1 - Yuxue Ren
A1 - Na Lei
A1 - Xianfeng Gu
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 22
IS - 9
SP - 1207
EP - 1220
%@ 2095-9184
Y1 - 2021
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.2000250


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,郑晓朋2,陈伟2,3,齐鑫4,任玉雪3,雷娜2,3,顾险峰4
1内蒙古财经大学计算机系,中国呼和浩特市,010010
2大连理工大学软件学院,中国大连市,116620
3首都师范大学北京成像理论与技术高精尖创新中心,中国北京市,100048
4石溪大学计算机系,美国纽约州石溪镇,11794
摘要:最优传输在工程、医疗等各领域扮演着重要角色,包括图形学中的曲面参数化、计算机视觉中的注册、深度学习中的生成模型等。对于平方距离传输成本,最优传输映射是Brenier势的梯度,可通过求解Monge-Ampère方程得到。此外,最优传输映射可归结为几何凸优化问题。Monge-Ampère方程高度非线性,在求解过程中,中间解需要始终保持严格凸。特别地,离散解的精确性严重依赖于目标测度的采样。因此,提出一种自适应采样算法,极大减少采样偏差,同时提高离散解的精确性和鲁棒性。实验结果验证了所提算法的有效性和高效性。

关键词:最优传输;Monge-Ampère方程;自适应采样

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[1]Alauzet F, Loseille A, Dervieux A, et al., 2006. Multi-dimensional continuous metric for mesh adaptation. Proc 15th 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 34th Int Conf on Machine Learning, p.214-223.

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

[6]Bossen FJ, Heckbert PS, 1996. A pliant method for anisotropic mesh generation. Proc 5th 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 9th 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 17th 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 31st 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 15th 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. 8th 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.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2022 Journal of Zhejiang University-SCIENCE