Back to search

University of Victoria (Canada)

An efficient numerical algorithm for the L2 optimal transport problem with applications to image processing

Abstract

dc:description.abstract

We present a numerical method to solve the optimal transport problem with a quadratic cost when the source and target measures are periodic probability densities. This method relies on a numerical resolution of the corresponding Monge-Ampère equation. We use an existing Newton-like algorithm that we generalize to the case of a non uniform final density. The main idea consists of designing an iterative scheme where the fully nonlinear equation is approximated by a non-constant coefficient linear elliptic PDE that we discretize and solve at each iteration, in two different ways: a second order finite difference scheme and a Fourier transform (FT) method. The FT method, made possible thanks to a preconditioning step based on the coefficient-averaged equation, results in an overall O(P LogP )-operations algorithm, where P is the number of discretization points. We prove that the generalized algorithm converges to the solution of the optimal transport problem, under suitable conditions on the initial and final densities. Numerical experiments demonstrating the robustness and efficiency of the method on several examples of image processing, including an application to multiple sclerosis disease detection, are shown. We also demonstrate by numerical tests that the method is competitive against some other methods available.

Degree

thesis:*
Level thesis:degree_level
Master of Science M.Sc.
Department thesis:degree_department
Department of Mathematics and Statistics
Year dc:date.issued
2010

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Saumier Demers, Louis-Philippe
Advisors dc:contributor.supervisor
  • Agueh, Martial
  • Khouider, Boualem

Subjects

dc:subject × 5

Rights

dc:rights
Statement dc:rights
  • Available to the World Wide Web
Language dc:language.iso
en, English

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1828/3157

Chain of custody

source
Harvested from
University of Victoria (Canada)
Base URL
dspace.library.uvic.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Saumier Demers, Louis-Philippe. An efficient numerical algorithm for the L2 optimal transport problem with applications to image processing. Master of Science M.Sc. thesis, 2010. http://hdl.handle.net/1828/3157