Joint seminar with the GERAD-Canada Research Chair in Distribution Management-Canada Research Chair in Logistics and Transportation
TITLE: Phase unwrapping and operations research
SPEAKER: Thibaut Vidal, Pontifícia Universidade Católica do Rio de Janeiro, Brazil
DATE and VENUE: February 4, 2016, 10h30, room 4488, André-Aisenstadt Building, Université de Montréal Campus
ORGANIZER: Gilbert Laporte
ABSTRACT: Phase unwrapping is the process of recovering a continuous phase signal from an original signal wrapped in the ]-π,π] interval. It is a critical step of coherent signal processing, with applications such as synthetic aperture radar, acoustic imaging, magnetic resonance, X-ray crystallography, and seismic processing, and thus the subject of extensive research. In the field of computational optics, this problem is classically treated as a “norm-minimization” problem, in which one seeks to minimize the differences between the gradients of the original wrapped signal and those of the continuous solution. When the L0-norm is considered, the number of differences should be minimized, leading to a difficult combinatorial optimization problem closely related to Steiner trees.
In this presentation, we provide a concise description of the problem, show how closely it relates to combinatorial optimization and operations research, and finally introduce a new model for L0-norm phase unwrapping in 2D. In this model, the residues of the wrapped phase image are associated with a graph where the vertices have -1 or +1 polarities. The objective is to find a minimum-cost balanced spanning forest where the sum of the polarities is equal to zero in each tree. We introduce a set of primal and dual heuristics, a branch-and-cut algorithm, and a hybrid metaheuristic to efficiently find exact or heuristic solutions. These approaches move us one step closer towards good solutions for this problem, which were previously viewed, in the signal processing literature, as highly desirable but nonetheless intractable.
Joint work with Ian Herszterg and Marcus Poggi, in PUC-Rio, Pontifical Catholic University of Rio de Janeiro.