Two-Dimensional Phase Unwrapping via Balanced Spanning Forests
Ian Herszterg, Marcus Poggi, Thibaut Vidal
INFORMS Journal on Computing Β· 2019 Β· Volume 31 Β· Issue 3
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. 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 unwrapped signal. When the L 0 L 0 βnorm is considered, the number of differences should be minimized, leading to a difficult combinatorial optimization problem. We propose an approximate model for the L 0 L 0 βnorm phase unwrapping problem in two dimensions (2D), in which the singularities of the wrapped phase image are associated with a graph where the vertices have β1 or + 1 + 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 to optimal solutions for 2D L 0 L 0 βnorm phase unwrapping; such solutions were previously viewed, in the signal processing literature, as highly desirable but not achievable.
Keywords
phase unwrapping, signal processing, combinatorial optimization, graphs, mathematical programming, branch-and-cut, metaheuristics
Enable JavaScript for citation tools and additional paper interactions.