Two-Dimensional Phase Unwrapping via Balanced Spanning Forests

Ian Herszterg (), Marcus Poggi () and Thibaut Vidal ()
Additional contact information
Ian Herszterg: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332;
Marcus Poggi: Departamento de Informática, Pontifícia Universidade Católica do Rio de Janeiro, Rio de Janeiro 22451-000, Brazil
Thibaut Vidal: Departamento de Informática, Pontifícia Universidade Católica do Rio de Janeiro, Rio de Janeiro, Rio de Janeiro 22451-000, Brazil

INFORMS Journal on Computing, 2019, vol. 31, issue 3, 527–543

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 –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 –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 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 –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 (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0832 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:31:y:2019:i:3:p:527-543

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().