Robust and accurate optimal transportation map by self-adaptive sampling

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.