Two-dimensional phase unwrapping via balanced spanning forests

Two-dimensional phase unwrapping via balanced spanning forests. Herszterg, I., Poggi, M., & Vidal, T. INFORMS Journal on Computing, 31(3):527–543, 2019.

Paper doi abstract bibtex 4 downloads

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 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 intractable.

@article{Herszterg2019,
abstract = {Phase unwrapping is the process of recovering a continuous phase signal from an original signal wrapped in the (−$\pi$,$\pi$] 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 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 intractable.},
annote = {1. Matheus Suknaic
2. Gabriel},
author = {Herszterg, I. and Poggi, M. and Vidal, T.},
doi = {10.1287/ijoc.2018.0832},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Herszterg, Poggi, Vidal/Herszterg, Poggi, Vidal - 2019 - Two-dimensional phase unwrapping via balanced spanning forests.pdf:pdf},
institution = {PUC-Rio},
journal = {INFORMS Journal on Computing},
mendeley-groups = {Teaching/INF2982-Modeling/Paper-Analysis,Teaching/INF2982-Modeling/Implementation},
number = {3},
pages = {527--543},
title = {{Two-dimensional phase unwrapping via balanced spanning forests}},
url = {https://arxiv.org/pdf/1812.08277.pdf},
volume = {31},
year = {2019}
}

Downloads: 4