skip to main content

Explore Research Products in the NSF-PAR

Title: FFT-OT: A Fast Algorithm for Optimal Transportation
An optimal transportation map finds the most economical way to transport one probability measure to the other. It has been applied in a broad range of applications in vision, deep learning and medical images. By Brenier theory, computing the optimal transport map is equivalent to solving a Monge-Amp\`ere equation. Due to the highly non-linear nature, the computation of optimal transportation maps in large scale is very challenging. This work proposes a simple but powerful method, the FFT-OT algorithm, to tackle this difficulty based on three key ideas. First, solving Monge-Amp\`ere equation is converted to a fixed point problem; Second, the obliqueness property of optimal transportation maps are reformulated as Neumann boundary conditions on rectangular domains; Third, FFT is applied in each iteration to solve a Poisson equation in order to improve the efficiency. Experiments on surfaces captured from 3D scanning and reconstructed from medical imaging are conducted, and compared with other existing methods. Our experimental results show that the proposed FFT-OT algorithm is simple, general and scalable with high efficiency and accuracy.  more » « less
Award ID(s):
1762287
NSF-PAR ID:
10291670
Author(s) / Creator(s):
;
Date Published:
Journal Name:
Proceedings of International Conference on Computer Vision (ICCV)
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; ; ; ; ( , Proceedings of International Meshing Roundtable)
    null (Ed.)
    Optimal transportation (OT) finds the most economical way to transport one measure to another and plays an important role in geometric modeling and processing. Based on the Brenier theorem, the OT problem is equivalent to the Alexandrov problem, which is the dual to the Pogorelov problem. Although solving the Alexandrov/Pogorelov problem are both equivalent to solving the Monge-Amp\`{e}re equation, the former requires second type boundary condition and the latter requires much simpler Dirichlet boundary condition. Hence, we propose to use the Pogorelov map to approximate the OT map. The Pogorelov problem can be solved by a convex geometric optimization framework, in which we need to ensure the searching inside the admissible space. In this work, we prove the discrete Alexandrov maximum principle, which gives an apriori estimate of the searching. Our experimental results demonstrate that the Pogorelov map does approximate the OT map well with much more efficient computation. 
    more » « less
  2. ; ; ; ; ; ; ; ( , IPMI 2021: Information Processing in Medical Imaging)
    null (Ed.)
    Biomarkers play an important role in early detection and intervention in Alzheimer’s disease (AD). However, obtaining effective biomarkers for AD is still a big challenge. In this work, we propose to use the worst transportation cost as a univariate biomarker to index cortical morphometry for tracking AD progression. The worst transportation (WT) aims to find the least economical way to transport one measure to the other, which contrasts to the optimal transportation (OT) that finds the most economical way between measures. To compute the WT cost, we generalize the Brenier theorem for the OT map to the WT map, and show that the WT map is the gradient of a concave function satisfying the Monge-Ampere equation. We also develop an efficient algorithm to compute the WT map based on computational geometry. We apply the algorithm to analyze cortical shape difference between dementia due to AD and normal aging individuals. The experimental results reveal the effectiveness of our proposed method which yields better statistical performance than other competiting methods including the OT. 
    more » « less
  3. ; ; ; ; ( , Proceedings of International Meshing Roundtable)
    null (Ed.)
    Optimal transportation finds the most economical way to transport one probability measure to another, and it plays an important role in geometric modeling and processing. In this paper, we propose a moving mesh method to generate adaptive meshes by optimal transport. Given an initial mesh and a scalar density function defined on the mesh domain, our method will redistribute the mesh nodes such that they are adapted to the density function. Based on the Brenier theorem, solving an optimal transportation problem is reduced to solving a Monge-Amp\`ere equation, which is difficult to compute due to the high non-linearity. On the other hand, the optimal transportation problem is equivalent to the Alexandrov problem, which can finally induce an effective variational algorithm. Experiments show that our proposed method finds the adaptive mesh quickly and efficiently. 
    more » « less
  4. ; ; ; ; ; ; ; ( , Mathematics, Computation and Geometry of Data)
    Optimal transportation (OT) maps play fundamental roles in many engineering and medical fields. The computation of optimal transportation maps can be reduced to solve highly non-linear Monge-Ampere equations. In this work, we summarize the geometric variational framework to solve optimal transportation maps in Euclidean spaces. We generalize the method to solve worst transportation maps and discuss about the symmetry between the optimal and the worst transportation maps. Many algorithms from computational geometry are incorporated into the method to improve the efficiency, the accuracy and the robustness of computing optimal transportation. 
    more » « less
  5. ; ; ; ; ; ; ; ( , Mathematics, Computation and Geometry of Data)
    Optimal transportation maps play fundamental roles in many engineering and medical fields. The computation of optimal transportation maps can be reduced to solve highly non-linear Monge-Ampere equations. This work summarizes the geometric variational frameworks for spherical optimal transportation maps, which offers solutions to the Minkowski problem in convex differential geometry, reflector design and refractor design problems in optics. The method is rigorous, robust and efficient. The algorithm can directly generalized to higher dimensions. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email