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