Combinatorial Optimization and 2D Phase Unwrapping

Session : SS16-2 / SS16 : Résolution parallèle des problèmes mono ou multi objectifs (continu et/ou combinatoire)
Vendredi 12 février 10:30 - 11:50 Salle : RP9
Ian Herszterg, Marcus Poggi et Thibaut Vidal

The development and application of techniques in coherent signal processing have greatly increased over the past several years. Synthetic aperture radar, acoustic imaging, magnetic resonance, X-Ray crystallography and seismic processing are just a few examples in which coherent processing is required, resulting in the need for accurate and efficient phase unwrapping methods. The phase unwrapping problem consists in recovering a continuous phase signal from an originally wrapped phase data between the ]-pi,pi] interval. This paper proposes a new model for the L0-norm 2D phase unwrapping problem, in which the singularities of the wrapped phase image are associated to a graph where the vertices have different polarities (+1 and -1). The objective is to find a minimum cost balanced spanning forest where the sum of polarities is equal to zero in each tree. A set of primal and dual heuristics, a branch-and-cut algorithm and a hybrid metaheuristic method are proposed to address the problem, leading to an efficient approach for L0-norm 2DPU, previously viewed as highly desirable but intractable. A set of experimental results illustrates the effectiveness of the proposed methods, and its competitiveness with state-of-the-art algorithms.

Mots clés : signal processing, phase unwrapping, combinatorial optimization, balanced spanning forest, branch-and-cut, hybrid iterated local search