Séminaire conjoint GERAD-Chaire de recherche du Canada en distributique-Chaire de recherche du Canada en logistique et en transport
TITRE : Phase unwrapping and operations research
CONFÉRENCIER : Thibaut Vidal, Pontifícia Universidade Católica do Rio de Janeiro, Brésil
DATE et ENDOIT : 4 février 2016, 10h30, salle 4488, Pavillon André-Aisenstadt, Campus de l’Université de Montréa
RESPONSABLE : Gilbert Laporte
RÉSUMÉ : 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.