Robust and accurate optimal transportation map by self-adaptive sampling

Yingshi WANG; Xiaopeng ZHENG; Wei CHEN; Xin QI; Yuxue REN; Na LEI; Xianfeng GU

doi:10.1631/FITEE.2000250

Your Location：

Home >

Browse articles >

Robust and accurate optimal transportation map by self-adaptive sampling

Regular Papers | Updated：2022-05-19

- Robust and accurate optimal transportation map by self-adaptive sampling
- 基于自适应采样的鲁棒精确最优传输映射
- Frontiers of Information Technology & Electronic Engineering Vol. 22, Issue 9, Pages: 1207-1220(2021)
- Affiliations：
  
  Department of Computer Science, Inner Mongolia University of Finance and Economics, Hohhot 010010, China
  School of Software, Dalian University of Technology, Dalian 116620, China
  Beijing Advanced Innovation Center for Imaging Technology, Capital Normal University, Beijing 100048, China
  Department of Computer Science, Stony Brook University, Stony Brook, NY 11794, USA
- Author bio：
  
  Na LEI, E-mail: nalei@dlut.edu.cn
  [ "Xianfeng GU, E-mail: gu@cs.stonybrook.edu" ]
- Funds：
- DOI：10.1631/FITEE.2000250
  CLC： O242;TP391
- Received：25 May 2020，
  
  Revised：2021-;8-19，
  
  Published：2021-09
- Accepted：
Scan QR Code
Yingshi WANG, Xiaopeng ZHENG, Wei CHEN, et al. Robust and accurate optimal transportation map by self-adaptive sampling[J]. Frontiers of Information Technology & Electronic Engineering, 2021, 22(9): 1207-1220.
DOI：

Yingshi WANG, Xiaopeng ZHENG, Wei CHEN, et al. Robust and accurate optimal transportation map by self-adaptive sampling[J]. Frontiers of Information Technology & Electronic Engineering, 2021, 22(9): 1207-1220. DOI： 10.1631/FITEE.2000250.

摘要

最优传输在工程、医疗等各领域扮演着重要角色，包括图形学中的曲面参数化、计算机视觉中的注册、深度学习中的生成模型等。对于平方距离传输成本，最优传输映射是Brenier势的梯度，可通过求解Monge-Ampère方程得到。此外，最优传输映射可归结为几何凸优化问题。Monge-Ampère方程高度非线性，在求解过程中，中间解需要始终保持严格凸。特别地，离散解的精确性严重依赖于目标测度的采样。因此，提出一种自适应采样算法，极大减少采样偏差，同时提高离散解的精确性和鲁棒性。实验结果验证了所提算法的有效性和高效性。

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.

关键词

Keywords

references

F Alauzet , , , A Loseille , , , A Dervieux , , , 等 . . Multi-dimensional continuous metric for mesh adaptation . . Proc 15 th Int Meshing Roundtable , , 2006 . . p. 191 - - 214 . . DOI: 10.1007/978-3-540-34958-7_12 http://doi.org/10.1007/978-3-540-34958-7_12 . .

T Apel , , , G Lube . . Anisotropic mesh refinement in stabilized Galerkin methods . . Num Math , , 1996 . . 74 ( ( 3 ): ): 261 - - 282 . . DOI: 10.1007/s002110050216 http://doi.org/10.1007/s002110050216 . .

T Apel , , , S Grosman , , , PK Jimack , , , 等 . . A new methodology for anisotropic mesh refinement based upon error gradients . . Appl Num Math , , 2004 . . 50 ( ( 3-4 ): ): 329 - - 341 . . DOI: 10.1016/j.apnum.2004.01.006 http://doi.org/10.1016/j.apnum.2004.01.006 . .

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

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

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

CL Bottasso . . Anisotropic mesh adaption by metric-driven optimization . . Int J Num Methods Eng , , 2004 . . 60 ( ( 3 ): ): 597 - - 639 . . DOI: 10.1002/nme.977 http://doi.org/10.1002/nme.977 . .

J Brandts , , , S Korotov , , , M Křížek . . On the equivalence of regularity criteria for triangular and tetrahedral finite element partitions . . Comp Math Appl , , 2008 . . 55 ( ( 10 ): ): 2227 - - 2233 . . DOI: 10.1016/j.camwa.2007.11.010 http://doi.org/10.1016/j.camwa.2007.11.010 . .

Y Brenier . . Polar factorization and monotone rearrangement of vector-valued functions . . Comm Pure Appl Math , , 1991 . . 44 ( ( 4 ): ): 375 - - 417 . . DOI: 10.1002/cpa.3160440402 http://doi.org/10.1002/cpa.3160440402 . .

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

SW Cheng , , , TK Dey , , , EA Ramos , , , 等 . . Sampling and meshing a surface with guaranteed topology and geometry . . SIAM J Comp , , 2007 . . 37 ( ( 4 ): ): 1199 - - 1227 . . DOI: 10.1137/060665889 http://doi.org/10.1137/060665889 . .

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

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

LP Chew . . Guaranteed-quality mesh generation for curved surfaces . . Proc 9 th Annual Symp on Computational Geometry , , 1993 . . p. 274 - - 280 . . DOI: 10.1145/160985.161150 http://doi.org/10.1145/160985.161150 . .

L Cui , , , X Qi , , , CF Wen , , , 等 . . Spherical optimal transportation . . Comp Aided Des , , 2019 . . 115 181 - - 193 . . DOI: 10.1016/j.cad.2019.05.024 http://doi.org/10.1016/j.cad.2019.05.024 . .

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

F de Goes , , , D Cohen-Steiner , , , P Alliez , , , 等 . . An optimal transport approach to robust reconstruction and simplification of 2D shapes . . Comp Graph Forum , , 2011 . . 30 ( ( 5 ): ): 1593 - - 1602 . . DOI: 10.1111/j.1467-8659.2011.02033.x http://doi.org/10.1111/j.1467-8659.2011.02033.x . .

F de Goes , , , K Breeden , , , V Ostromoukhov , , , 等 . . Blue noise through optimal transport . . ACM Trans Graph , , 2012 . . 31 ( ( 6 ): ): 171 DOI: 10.1145/2366145.2366190 http://doi.org/10.1145/2366145.2366190 . .

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

TK Dey , , , JA Levine . . Delaunay meshing of isosurfaces . . Proc Shape Modeling Int , , 2007 . . p. 241 - - 250 . . DOI: 10.1007/s00371-008-0224-1 http://doi.org/10.1007/s00371-008-0224-1 . .

TK Dey , , , T Ray . . Polygonal surface remeshing with Delaunay refinement . . Eng Comp , , 2010 . . 26 ( ( 3 ): ): 289 - - 301 . . DOI: 10.1007/s00366-009-0162-1 http://doi.org/10.1007/s00366-009-0162-1 . .

C Dobrzynski , , , P Frey . . Anisotropic Delaunay mesh adaptation for unsteady simulations . . Proc 17 th Int Meshing Roundtable , , 2008 . . p. 177 - - 194 . . DOI: 10.1007/978-3-540-87921-3_11 http://doi.org/10.1007/978-3-540-87921-3_11 . .

A Dominitz , , , A Tannenbaum . . Texture mapping via optimal mass transport . . IEEE Trans Vis Comput Graph , , 2010 . . 16 ( ( 3 ): ): 419 - - 433 . . DOI: 10.1109/TVCG.2009.64 http://doi.org/10.1109/TVCG.2009.64 . .

Q Du , , , DS Wang . . Anisotropic centroidal Voronoi tessellations and their applications . . SIAM J Sci Comput , , 2005 . . 26 ( ( 3 ): ): 737 - - 761 . . DOI: 10.1137/S1064827503428527 http://doi.org/10.1137/S1064827503428527 . .

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

XF Gu , , , F Luo , , , J Sun , , , 等 . . Variational principles for Minkowski type problems, discrete optimal transport, and discrete Monge-Ampère equations . . Asian J Math , , 2016 . . 20 ( ( 2 ): ): 383 - - 398 . . DOI: 10.4310/AJM.2016.v20.n2.a7 http://doi.org/10.4310/AJM.2016.v20.n2.a7 . .

XF Gu , , , F Luo , , , J Sun , , , 等 . . A discrete uniformization theorem for polyhedral surfaces . . J Diff Geom , , 2018 . . 109 ( ( 2 ): ): 223 - - 256 . . DOI: 10.4310/jdg/1527040872 http://doi.org/10.4310/jdg/1527040872 . .

P Guan , , , XJ Wang , , , 等 . . On a Monge-Ampère equation arising in geometric optics . . J Diff Geom , , 1998 . . 48 ( ( 2 ): ): 205 - - 223 . . DOI: 10.4310/jdg/1214460795 http://doi.org/10.4310/jdg/1214460795 . .

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

CE Gutiérrez , , , Q Huang . . The refractor problem in reshaping light beams . . Archive Ration Mech Anal , , 2009 . . 193 ( ( 2 ): ): 423 - - 443 . . DOI: 10.1007/s00205-008-0165-x http://doi.org/10.1007/s00205-008-0165-x . .

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

LV Kantorovich . . On a problem of Monge . . J Math Sci , , 2006 . . 133 ( ( 4 ): ): 1383 DOI: 10.1007/s10958-006-0050-9 http://doi.org/10.1007/s10958-006-0050-9 . .

J Kitagawa , , , Q Mèrigot , , , B Thibert . . Convergence of a Newton algorithm for semi-discrete optimal transport . . J Eur Math Soc , , 2019 . . 21 ( ( 9 ): ): 2603 - - 2651 . . DOI: 10.4171/JEMS/889 http://doi.org/10.4171/JEMS/889 . .

G Kunert . . Toward anisotropic mesh construction and error estimation in the finite element method . . Num Meth Partial Diff Equ , , 2002 . . 18 ( ( 5 ): ): 625 - - 648 . . DOI: 10.1002/num.10023 http://doi.org/10.1002/num.10023 . .

N Lei , , , KH Su , , , L Cui , , , 等 . . A geometric view of optimal transportation and generative mode . . Comp Aided Geomet Des , , 2019 . . 68 1 - - 21 . . DOI: 10.1016/j.cagd.2018.10.005 http://doi.org/10.1016/j.cagd.2018.10.005 . .

Y Liu , , , WP Wang , , , B Lévy , , , 等 . . On centroidal Voronoi tessellation-energy smoothness and fast computation . . ACM Trans Graph , , 2009 . . 28 ( ( 4 ): ): 1 - - 17 . . DOI: 10.1145/1559755.1559758 http://doi.org/10.1145/1559755.1559758 . .

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

Q Mérigot . . A multiscale approach to optimal transport . . Comp Graph Forum , , 2011 . . 30 ( ( 5 ): ): 1583 - - 1592 . . DOI: 10.1111/j.1467-8659.2011.02032.x http://doi.org/10.1111/j.1467-8659.2011.02032.x . .

J Meyron , , , Q Mérigot , , , B Thibert . . Light in power: a general and parameter-free algorithm for caustic design . . ACM Trans Graph , , 2018 . . 37 ( ( 6 ): ): 224 DOI: 10.1145/3272127.3275056 http://doi.org/10.1145/3272127.3275056 . .

S Nadeem , , , ZY Su , , , W Zeng , , , 等 . . Spherical parameterization balancing angle and area distortions . . IEEE Trans Vis Comput Graph , , 2017 . . 23 ( ( 6 ): ): 1663 - - 1676 . . DOI: 10.1109/TVCG.2016.2542073 http://doi.org/10.1109/TVCG.2016.2542073 . .

G Rong , , , Y Liu , , , W Wang , , , 等 . . GPU-assisted computation of centroidal Voronoi tessellation . . IEEE Trans Vis Comp Graph , , 2011 . . 17 ( ( 3 ): ): 345 - - 356 . . DOI: 10.1109/TVCG.2010.53 http://doi.org/10.1109/TVCG.2010.53 . .

J Ruppert . . A Delaunay refinement algorithm for quality 2-dimensional mesh generation . . J Algorithms , , 1995 . . 18 ( ( 3 ): ): 548 - - 585 . . DOI: 10.1006/jagm.1995.1021 http://doi.org/10.1006/jagm.1995.1021 . .

JR Shewchuk . . Delaunay refinement algorithms for triangular mesh generation . . Comput Geom , , 2002 . . 22 ( ( 1-3 ): ): 21 - - 74 . . DOI: 10.1016/S0925-7721(01)00047-5 http://doi.org/10.1016/S0925-7721(01)00047-5 . .

Y Sirois , , , J Dompierre , , , MG Vallet , , , 等 . . Mesh smoothing based on Riemannian metric non-conformity minimization . . Proc 15 th Int Meshing Roundtable , , 2006 . . p. 271 - - 288 . . DOI: 10.1007/978-3-540-34958-7_16 http://doi.org/10.1007/978-3-540-34958-7_16 . .

J Solomon , , , R Rustamov , , , L Guibas , , , 等 . . Earth mover's distances on discrete surfaces . . ACM Trans Graph , , 2014 . . 33 ( ( 4 ): ): 67 DOI: 10.1145/2601097.2601175 http://doi.org/10.1145/2601097.2601175 . .

J Solomon , , , F de Goes , , , G Peyré , , , 等 . . Convolutional Wasserstein distances: efficient optimal transportation on geometric domains . . ACM Trans Graph , , 2015 . . 34 ( ( 4 ): ): 66 DOI: 10.1145/2766963 http://doi.org/10.1145/2766963 . .

KH Su , , , L Cui , , , K Qian , , , 等 . . Area-preserving mesh parameterization for poly-annulus surfaces based on optimal mass transportation . . Comp Aided Geom Des , , 2016 . . 46 76 - - 91 . . DOI: 10.1016/j.cagd.2016.05.005 http://doi.org/10.1016/j.cagd.2016.05.005 . .

KH Su , , , W Chen , , , N Lei , , , 等 . . Volume preserving mesh parameterization based on optimal mass transportation . . Comp Aided Des , , 2017 . . 82 42 - - 56 . . DOI: 10.1016/j.cad.2016.05.020 http://doi.org/10.1016/j.cad.2016.05.020 . .

ZY Su , , , W Zeng , , , R Shi , , , 等 . . Area preserving brain mapping . . Proc IEEE Conf on Computer Vision and Pattern Recognition , , 2013 . . p. 2235 - - 2242 . . DOI: 10.1109/CVPR.2013.290 http://doi.org/10.1109/CVPR.2013.290 . .

ZY Su , , , YL Wang , , , R Shi , , , 等 . . Optimal mass transport for shape matching and comparison . . IEEE Trans Patt Anal Mach Intell , , 2015 . . 37 ( ( 11 ): ): 2246 - - 2259 . . DOI: 10.1109/TPAMI.2015.2408346 http://doi.org/10.1109/TPAMI.2015.2408346 . .

T ur Rehman , , , E Haber , , , G Pryor , , , 等 . . 3D nonrigid registration via optimal mass transport on the GPU . . Med Image Anal , , 2009 . . 13 ( ( 6 ): ): 931 - - 940 . . DOI: 10.1016/j.media.2008.10.008 http://doi.org/10.1016/j.media.2008.10.008 . .

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

XJ Wang . . On the design of a reflector antenna . . Inverse Probl , , 1996 . . 12 ( ( 3 ): ): 351 DOI: 10.1088/0266-5611/12/3/013 http://doi.org/10.1088/0266-5611/12/3/013 . .

XJ Wang . . On the design of a reflector antenna Ⅱ . . Calc Var Part Diff Equ , , 2004 . . 20 ( ( 3 ): ): 329 - - 341 . . DOI: 10.1007/s00526-003-0239-4 http://doi.org/10.1007/s00526-003-0239-4 . .

DM Yan , , , K Wang , , , B Levy , , , 等 . . Computing 2D periodic centroidal Voronoi tessellation . . 8 th Int Symp on Voronoi Diagrams in Science and Engineering , , 2011 . . p. 177 - - 184 . . DOI: 10.1109/ISVD.2011.31 http://doi.org/10.1109/ISVD.2011.31 . .

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

X Zhao , , , ZY Su , , , XD Gu , , , 等 . . Area-preservation mapping using optimal mass transport . . IEEE Trans Vis Comp Graph , , 2013 . . 19 ( ( 12 ): ): 2838 - - 2847 . . DOI: 10.1109/TVCG.2013.135 http://doi.org/10.1109/TVCG.2013.135 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰