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 not achievable.
The Challenge of Phase Unwrapping
In many remote sensing and medical imaging applications, such as Interferometric Synthetic Aperture Radar (InSAR) and Magnetic Resonance Imaging (MRI), sensors measure phase data that is inherently "wrapped" within a $(-\pi, \pi]$ interval. To reconstruct the actual physical surface or underlying tissue density, this data must be "unwrapped" into a continuous signal.
The primary difficulty in this process arises from residues—singularities caused by noise, signal aliasing, or sharp physical discontinuities (e.g., steep terrain or bone edges). If an unwrapping path circles an unbalanced number of positive and negative residues, a $2\pi$ error is introduced. Traditionally, this is framed as an $L^p$ norm minimization problem. While $L^2$ (least squares) solutions are computationally efficient, they often "smear" sharp edges. The $L^0$ norm is considered the ideal approach because it preserves sharp discontinuities by minimizing the total number of jumps, but it is notoriously NP-hard and computationally complex.
Methods: Balanced Spanning Forests
This paper reformulates the $L^0$ phase unwrapping problem as a Minimum Spanning Forest with Balance Constraints (MSFBCP). The core idea is to model the residues as vertices in a graph with polarities of $+1$ or $-1$.
- The MSFBCP Model: Instead of using complex geometric Steiner trees, the authors find a forest (a collection of trees) where each tree is "balanced"—meaning the sum of the polarities of the residues it connects is zero.
- Exact Branch-and-Cut Algorithm: The authors employ an integer programming formulation. To handle the computational load, they implement a dual ascent heuristic for preprocessing. This technique effectively "fixes" or eliminates up to 78% of the variables before the main optimization begins, transforming a dense graph problem into a sparse one.
- Hybrid Iterated Local Search (HILS): For large-scale problems, a hybrid metaheuristic is used. It combines local search moves—such as shifting a residue between trees—with a "set partitioning" optimization that periodically recombines the best components of previous solutions to approach a global optimum.
Key Insights
- Approximation Quality: While Steiner trees are theoretically more accurate for $L^0$ minimization, the authors demonstrate that Spanning Trees provide a high-quality approximation that is significantly more computationally tractable.
- Structural Constraints: By treating the zero-sum charge requirement as a structural constraint rather than just a goal, the authors can use sophisticated flow-based separation algorithms to identify and resolve "violated cuts" during optimization.
Results and Scalability
The proposed methods were evaluated on synthetic benchmarks (PUC-N), classic InSAR simulator data (Long’s Peak & Isola’s Peak), and real-world medical data (Head MRI).
- Efficiency: The Branch-and-Cut algorithm successfully solved instances with up to 128 residues to proven optimality in under an hour, a major milestone for this problem class.
- Superior Quality: On the "Long’s Peak" dataset, the MSFBCP model produced 32% fewer discontinuity points than the classic Goldstein algorithm and 9% fewer than the Minimum Cost Matching (MCM) approach.
- Large-Scale Performance: The HILS metaheuristic effectively processed the Head MRI dataset (nearly 2,000 residues), maintaining better structural preservation and fewer isolated regions than traditional methods.
Conclusion and Future Directions
The introduction of the Balanced Spanning Forest model brings optimal $L^0$-norm phase unwrapping closer to reality. While the exact method still faces challenges with very large instances (over 512 residues), the hybrid metaheuristic offers a powerful alternative. Future work may involve using MCM-generated solutions as "warm starts" for the metaheuristic and integrating these discrete optimization techniques into real-time signal processing pipelines for satellite and medical imaging.
Summary updated